Scheme

Gérald Sussman et Guy Steele sont revenus sur la naissance de Scheme dans un article intitulé The First Report on Scheme Revisited[2] et publié en 1998.

En 1973, Carl Hewitt propose son modèle d'acteur et écrit avec ses étudiants une implémentation en Lisp appelée Planner-73, puis PLASMA (acronyme de PLAnner-like System Modeled on Actors). Sussman et Steele voulant mieux comprendre le modèle d’Hewitt, notamment en le reliant aux notions traditionnelles de la programmation, écrivent un petit interprète Lisp et des primitives pour créer des acteurs et envoyer des messages entre eux. Ils utilisent la même syntaxe pour les fonctions et les acteurs, les premières étant des fermetures déclarées par le mot clef lambda et retournant une valeur, et les seconds par alpha. Les acteurs ne retournant pas, mais appellent des continuations, qui sont les autres acteurs qu’il connait.

Le langage est nommé « Schemer », suivant le nommage des langages Planner et Conniver, desquels il s’inspire. Cependant, le système ITS utilisé à l’époque limite les noms de fichiers à 6 caractères, tronquant le nom à « SCHEME ». Sussman et Steele disent ne plus se souvenir de pourquoi ils n’ont pas choisi d’abréger en « SCHMR », comme Planner et Conniver qui utilisaient « PLNR » et « CNVR ».

Ils découvrent, après avoir écrit des programmes avec des acteurs, que l’implémentation de l’interprète était identique, que le code à évaluer concerne des fonctions ou des acteurs, et qu’il en était de même pour le code qui crée les fonctions et acteurs. La différence entre le fait que seules les fonctions retournent des valeurs et pas les acteurs n’existait pas dans l’implémentation, mais seulement dans les primitives utilisées dans le corps des définitions des fonctions et acteurs. Ils en déduisent que les acteurs et les fermetures sont en fait le même concept, et Hewitt l’a lui-même admis plus tard.

Ces découvertes sur l’embryon qu’était alors Scheme ont mené à trois conclusions majeures. En premier lieu, le modèle d’acteur d’Hewitt se représentait parfaitement en λ-calcul. Ce n’était pas nouveau en soi pour les théoriciens de la sémantique dénotationnelle, mais Scheme a permis d’apporter une dimension pratique à ces théories. Ensuite, il est apparu que le formalisme simple et petit du λ-calcul peut servir à un noyau d’un langage de programmation expressif et puissant[note 1], Scheme est donc un λ-calcul appliqué. Le corollaire est immédiat : la sémantique dénotationnelle est équivalente à la sémantique opérationnelle. Enfin, la quête d’un langage ultime pour l’intelligence artificielle s’est révélée tourner en rond, puisque les travaux sur les langages ont commencé par Lisp, suivi de CONVERT, puis Planner, Conniver, PLASMA, lui-même suivi par un dialecte simplifié de Lisp.

Les variables sont typées dynamiquement et leur portée est lexicale :

 (define var1 value)
  (let ([var2 value])
    ...)

Listes :

  (cons 1 (cons 2 (cons 3 (cons 4 '()))))

Cette concaténation peut être abrégée en

  (list 1 2 3 4)

ou en

  '(1 2 3 4)

Fonctions : elles sont définies comme des lambda-expressions

  (define fun
    (lambda (arg1 arg2)
       ...))

ou plus simplement

  (define (fun arg1 arg2)
    ...)

Application à une liste :

  (apply fun (list value1 value2))

Évaluations conditionnelles :

  (cond (test1 expr1)
        (test2 expr2)
        ...
        (else exprn))

et aussi

  (if condition
        then-expr
        else-expr)

Exemple 1 - calcul d'une factorielle :

  (define (factorial n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

 (factorial 5)
 ;; ⇒ 120

Exemple 2 - définition d'une fonction map, qui applique une lambda-expression (qui élève son argument au carré) à tous les éléments d'une liste :

  (define (map f lst)
    (cond ((null? lst) lst)
          (else (cons (f (car lst))
                      (map f (cdr lst))))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;;  ⇒ (1 4 9 16)

Versions tail-récursives des deux exemples précédents :

  (define (factorial n)
    (let loop ((fact 1)
               (n n))
      (cond ((= n 0) fact)
            (else (loop (* n fact) (- n 1))))))

 (factorial 5)
 ;; ⇒ 120

  (define (map f lst)
    (do ((lst lst (cdr lst))
         (res '() (cons (f (car lst)) res)))
        ((null? lst) (reverse res))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;; ⇒ (1 4 9 16)

Scheme reprend la syntaxe des S-expressions de Lisp en changeant quelques mots clefs. Une expression scheme est soit une valeur atomique (nombre, chaîne de caractère, identificateur, etc.), soit une liste d’expressions. Les différences notables avec Lisp sont :

• Portée lexicale à travers des fermetures ;
• Espace de noms unique pour fonctions et variables : Scheme utilise define là où Lisp choisissait ou defvar ou defun ;

Common Lisp vs. Scheme