Mardi 18 octobre

• Notion de continuation
• Fonction usuelles
• Continuations et exceptions
• Continuations et itérateurs

• La recherche d'un élément dans un arbre avec continuations
• Le livre de chevet de tous les étudiants en programmation fonctionnelle (Scheme) du MIT (l'autre, à Boston, MA): Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, Julie Sussman, MIT Press.
• Le cours de programmation de l'X: Les principe des langages de programmation, Gilles Dowek
• Le cours de sémantique de l'X: Introduction à la théorie des langages de programmation, Gilles Dowek, Jean-Jacques Lévy

Le livre d'Abelson et Sussman a eu un énorme impact sur l'enseignement de la programmation et la popularité de la programmation fonctionnelle en Scheme. Le livre est entièrement disponible en ligne, associé à un site Web qui rassemble une mine d'exercices et de projets passionnants. Voici un article qui explique l'importance de ce livre.

In 2011, to celebrate the 150th anniversary of MIT, the Boston Globe made a list of the most important innovations developed there. They asked me to explain the importance of SICP, and this is what I sent them:

SICP was revolutionary in many different ways. Most importantly, it dramatically raised the bar for the intellectual content of introductory computer science. Before SICP, the first CS course was almost always entirely filled with learning the details of some programming language. SICP is about standing back from the details to learn big-picture ways to think about the programming process. It focused attention on the central idea of abstraction – finding general patterns from specific problems and building software tools that embody each pattern. It made heavy use of the idea of functions as data, an idea that's hard to learn initially, but immensely powerful once learned. (This is the same idea, in a different form, that makes freshman calculus so notoriously hard even for students who've done well in earlier math classes.) It fit into the first CS course three different programming paradigms (functional, object oriented, and declarative), when most other courses didn't even really discuss even one paradigm.

[…] In my experience, relatively few students appreciate how much they're learning in my course while they're in it. But in surveys of all our CS students, it turns out to be among the most popular courses in retrospect, and I regularly get visits and emails from long-gone students to tell me about how they're using in their work ideas that they thought were impractical ivory-tower notions as students. The invention of the MapReduce software for data parallelism at Google, based on functional programming ideas, has helped eliminate that ivory-tower reputation.

Brian Harvey, University of California, Berkeley

9 octobre 2017

• Notion d'exception
• Exceptions Caml, harnais try/with
• Exceptions et itération: break et continue
• Exceptions et récursion

• La recherche d'un élément dans un arbre
• La vidéo de la semaine: The promise, the limits, and the beauty of software, Grady Booch, IBM Fellow. Transcription anglaise disponible. Grady Booch is an IBM Fellow and the author of numerous books on software design and architecture as well as volumes on UML (which he co-developed with Ivar Jacobsen and James Rumbaugh). In 2007, Grady stopped by Yahoo! to meet with Yahoo! software architects and, while here, he gave an open lecture for engineers. This is a version of a lecture originally given to the British Computer Society in honor of Alan Turing.
• L'article de la semaine: What really happened on Mars? et la réponse de Glenn Reeves, JPL, responsable du logiciel de la mission spatiale Mars Pathfinder en 1997.

Real-World (Out of This World) Story: The Mars Pathfinder mission was widely proclaimed as “flawless” in the early days after its July 4th, 1997 landing on the Martian surface. Successes included its unconventional “landing” – bouncing onto the Martian surface surrounded by airbags, deploying the Sojourner rover, and gathering and transmitting voluminous data back to Earth, including the panoramic pictures that were such a hit on the Web. But a few days into the mission, not long after Pathfinder started gathering meteorological data, the spacecraft began experiencing system resets. The press reported these failures in terms such as “software glitches” and “the computer was trying to do too many things at once”. Read What really happened on Mars? Also, be sure to read this followup message from Glenn Reeves of JPL, who led the software team for the Mars Pathfinder spacecraft. Michael B. Jones, Microsoft

2 octobre 2017

• Notion de référence, égalité, identité
• Effets de bord
• Structures modifiables
• Listes modifiables

Manuel Caml, 6.7 Expressions ==Function application==

Function application is denoted by juxtaposition of (possibly labeled) expressions. The expression expr argument1 … argumentn evaluates the expression expr and those appearing in argument1 to argumentn. The expression expr must evaluate to a functional value f, which is then applied to the values of argument1, …, argumentn.

The order in which the expressions expr, argument1, …, argumentn are evaluated is not specified.

==Local definitions==

The let and let rec constructs bind value names locally. The construct let pattern1 = expr1 and … and patternn = exprn in expr evaluates expr1, …, exprn in some unspecified order…

Documentation des bibliothèques Ocaml Boolean operations

val (&&) : bool → bool → bool
The boolean 'and'. Evaluation is sequential, left-to-right: in e1 && e2, e1 is evaluated first, and if it returns false, e2 is not evaluated at all.

val (||) : bool → bool → bool
The boolean 'or'. Evaluation is sequential, left-to-right: in e1 || e2, e1 is evaluated first, and if it returns true, e2 is not evaluated at all.

• Le type milist des listes d'entiers modifiables
• La réponse de Xavier Leroy à ma question concernant l'ordre d'évaluation des arguments des fonctions
• L'article de la semaine: The four Rs of programming language design, Dominic Orchard

Language designers are forever searching for the “proper language” for a domain, task, or class of programs, such that everything – such as correctness, optimisations, abstractions, high-level structures, solutions to a problem, etc. – becomes clearer when the language is used. The four Rs capture the key aspects of programming language’s affect on programs, in its ability to improve reading, writing, running, and reasoning.

These are four important areas that we need to consider when designing effective languages. The four Rs are not meant to argue whether a language is “good” or “bad”, or to unilaterally promote one over the other. Instead, the four Rs provide a framework for thinking critically about the effectiveness of languages and language features. Trade-offs between the four Rs have given a broad and beautiful spectrum of programming languages over the last 70 years. I await further languages with excitement and hope that with better languages everything might become clearer.

The four Rs of programming language design, Dominic Orchard

25 septembre 2017

• Théorie des catégories
• Produit et somme catégoriques
• Application aux listes

• Les types ilist et itree avec une approche catégorique
• Le livre de la semaine: Basic Category Theory for Computer Scientists, Benjamin C. Pierce
  • Une présentation des enjeux conceptuels et de son influence sur les mathématiques actuelles: l'article de Stanford Encyclopedia of Philosophy
  • Une courte introduction (20 pages): WOMP 2004: Category Theory, Bert Guillou and Haris Skiadas, Warmup on Mathematics Programs, University of Chicago
• Le grand homme de la semaine: Dana Scott
• La page Wikipedia de la semaine: Théorie des catégories

Abstract nonsense, or general abstract nonsense, is a popular term used by mathematicians to describe certain kinds of arguments and concepts in category theory or applications. The term goes back a long way, and even predates the foundation of category theory as a subject itself. Referring to a joint paper with Samuel Eilenberg that introduced the notion of a “category” in 1942, Saunders Mac Lane wrote the subject was 'then called “general abstract nonsense”'.

The term is believed to have been coined by the mathematician Norman Steenrod, himself one of the developers of the categorical point of view. This term is used by practitioners as an indication of mathematical sophistication or coolness rather than as a derogatory designation.

“Logical abstract nonsense is a subfield of general abstract nonsense”, Language Log

• Pour vous cultiver: la page Wikipedia sur Nicolas Bourbaki et son influence sur les mathématiques françaises, en particulier son “indifférence” (sic) à la théorie des catégories. Voici une citation de Saunders MacLane, l'un des grands noms de ce domaine, mentionnée sur cette page.

Categorical ideas might well have fitted in with the general program of Nicolas Bourbaki […]. However, his first volume on the notion of mathematical structure was prepared in 1939 before the advent of categories. It chanced to use instead an elaborate notion of an échelle de structure which has proved too complex to be useful.

Apparently as a result, Bourbaki never took to category theory. At one time, in 1954, I was invited to attend one of the private meetings of Bourbaki, perhaps in the expectation that I might advocate such matters. However, my facility in the French language was not sufficient to categorize Bourbaki. […]

The official Bourbaki discussion of mathematical structure […] is perhaps the ugliest piece of writing to have come from Bourbaki's pen. Nobody else makes much use of this, and Bourbaki himself just mutters from time to time about “transport of structure”. He was too conservative to recognize other better descriptions of structure when they arose (Eilenberg-MacLane, Ehresmann, Lawvere, Gabriel-Zisman). Saunders MacLane, “Letters to the Editor”, The Mathematical Intelligencer, vol. 8, n° 2, 1986, p. 5.

18 septembre 2017

• Listes Ocaml
• Notion de type abstrait: constructeurs, accesseurs, observateurs, combinateurs, notion d'interface de programmation (API)
• Fonctions classiques: approches concrète et abstraites
• Itérateurs: map et reduce

• Le type ilist et quelques fonctions classiques
• Le livre de la semaine: Types de données et algorithmes, Marie-Claude Gaudel, Michèle Soria, Christine Froidevaux
• Le module de la semaine: The List Module
• La page Wikipedia de la semaine: le modèle de programmation Map-Reduce

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper.

Programs written in this functional style are automatically parallelized and executed on a large cluster of com- modity machines. The run-time system takes care of the details of partitioning the input data, scheduling the pro- gram’s execution across a set of machines, handling ma- chine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to eas- ily utilize the resources of a large distributed system.

Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google’s clusters every day.

MapReduce: simplified data processing on large clusters, Jeffrey Dean, Sanjay Ghemawat, Proceeding Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation (OSDI'04), Volume 6, Page 10

10 septembre 2017

• Historique, grands noms
• Présentation générale: interprète interactif, synthèse de type, évaluation
• Types et opérateurs de base: int, float, char, string, bool, synthèse de type
• Notion de liaison: let et let…in
• Fonctions: définition explicite, lambda-expressions, curryfication, ordre supérieur

• La page de la semaine: A History of Caml
• Le grand homme de la semaine: Robin Milner, The elegant pragmatist
• Literate Programming: Computer programming as an art, Donald E. Knuth, ACM Turing award lecture, 1974. Voir aussi la page des lauréats de la médaille Turing.
• Lambda-Calcul: voir la bibliographie ci-dessous

Cette page contient toute la procédure pour installer proprement et facilement Ocaml sur votre machine.

Il existe un MOOC Ocaml Introduction to Functional Programming in OCaml sur la plateforme FUN (France Université Numérique).

C'est la référence la plus à jour sur le sujet. Le cours est enseigné par 3 des meilleurs spécialistes: Roberto Di Cosmo, Yann Régis-Gianas et Ralf Treinen, tous les trois de l'Université Paris Diderot (Paris 7).

• The OCaml system: documentation and user’s manual, Xavier Leroy et al.
• Developing Applications With Objective Caml, Emmanuel Chailloux, Pascal Manoury and Bruno Pagano, available as written in 2000, still quite valuable
• Using, Understanding, and Unraveling The OCaml Language, From Practice to Theory and vice versa, Didier Rémy, APPSEM’2000 summer school

Un livre en français: Apprendre à programmer en OCaml, Jean-Christophe Filliâtre et Sylvain Conchon

Vous trouverez d'autres livres à cette adresse.

La référence historique du cours est le livre Approche fonctionnelle de la programmation, Guy Cousineau et Michel Mauny, malheureusement maintenant épuisé.

• Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay Sussman, Julie Sussman, MIT Press.

• Le cours de programmation de l'X: Les principe des langages de programmation, Gilles Dowek
• Le cours de sémantique de l'X: Introduction à la théorie des langages de programmation, Gilles Dowek, Jean-Jacques Lévy

• Une petite introduction: Introduction au lambda-calcul, Pierre Lescanne, ENS Lyon; voir aussi la suite sur la page générale du cours
• La Bible, approche française: Lambda-calcul, types et modèles, Jean-Louis Krivine
• La Bible, approche anglo-saxonne: The Lambda Calculus: Its Syntax and Semantics, H.P. Barendregt
• Théorie des types: A Modern Perspective on Type Theory, From its Origins until Today, F.D. Kamareddine, T. Laan, Rob Nederpelt

• Une petite introduction: Basic Category Theory for Computer Scientists, Benjamin C. Pierce
• Application à ML: Computational category theory, David E. Rydeheard, Rod M. Burstall

• Théorie des types: Categories for Types, Roy L. Crole
• Équations récursives aux domaines: Mathematical theory of domains, Viggo Stoltenberg-Hansen, Ingrid Lindström, Edward R. Griffor

• Conceptual mathematics, F. William Lawvere, Stephen H. Schanuel
• Logique, ensembles, catégories, le point de vue constructif, Pierre Ageron

• Site de référence. Nous utilisons la version 4 (4.04 en septembre 2017).
• Documentation en ligne
• Gestionnaire de paquetage OCaml: OPAM. Voici les paquetages recommmandés
  • base-unix: Unix library distributed with the OCaml compiler
  • caml-mode: OCaml code editing commands for Emacs
  • depext: Query and install external dependencies of OPAM packages
  • ocp-indent: A simple tool to indent OCaml programs
  • tuareg: OCaml mode for GNU Emacs and XEmacs.
  • user-setup: Helper for the configuration of editors for the use of OCaml tools