Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le Premier LISP Didier Verna didier@lrde.epita.fr http://www.lrde.epita.fr/˜did

Le Premier LISP Didier Verna didier@lrde.epita.fr http://www.lrde.epita.fr/˜didier Séminaire du LRDE, 19 Juin 2002 Table des matières Table des matières Nativité.................................................................................................. 3 S-expressions ou S-exp...................................................................... 5 Les sept Opérateurs Primitifs .................................................................. 7 Dénotation Fonctionnelle ................................................................... 16 Application à LISP ................................................................................ 17 Fonctions récursives.............................................................................. 19 Quelques Fonctions............................................................................ 20 Le Miracle............................................................................................. 25 Explications......................................................................................... 26 Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 1 Table des matières Bilan...................................................................................................... 34 Les apports de LISP.............................................................................. 35 Y-combinator........................................................................................ 36 Dynamic Scoping.................................................................................. 37 Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 2 Nativité Nativité • MIT, Laboratoire d’Intelligence Artiﬁcielle, 1960 • Projet «Advice Taker» (1958) : manipulation d’expressions représentant des phrases déclaratives et impératives en vue de déductions • IBM 704 • John Mc Carthy : «Recursive Functions of Symbolic Expressions and their Computation by Machine.» Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 3 Nativité IBM 704 Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 4 S-expressions ou S-exp S-expressions ou S-exp Premier soucis : déﬁnir une «expression» (S comme «symbolic») ¯ Une S-exp est un atome ou une liste d’expressions ¯ Une liste est une séquence parenthésée d’expressions séparées par des espaces ¯ Un atome est une séquence de lettres foo () (foo) (foo bar) (foo (bar) baz) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 5 S-expressions ou S-exp Valeurs des S-exp Une S-exp a une valeur (analogie mathématique : «1 + 1» →2) • Une S-exp non atomique s’écrit (OP ARG1 ARG2 ...) • OP est un «opérateur» • ARGx est un «argument» ¯ La valeur d’une S-exp est déﬁnie comme l’application de l’opérateur à ses arguments ¯ On déﬁni 7 opérateurs «primitifs» (axiomes) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 6 S-expressions ou S-exp Les sept Opérateurs Primitifs Les sept Opérateurs Primitifs Opérateur n◦1 : (quote x) Retourne x ((quote x) est aussi noté ’x) > (quote a) a > ’(a b c) (a b c) > (quote ’(a b c)) (quote (a b c)) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 7 S-expressions ou S-exp Les sept Opérateurs Primitifs Opérateur n◦2 : (atom x) Retourne t si la valeur de x est atomique, () sinon (t représente vrai, () représente faux) (l’atome nil est équivalent à ()) > (atom ’a) t > (atom ’(a b c)) () > (atom ’()) t Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 8 S-expressions ou S-exp Les sept Opérateurs Primitifs Remarque : évaluation des arguments Contrairement à quote, atom évalue son argument > (atom (atom ’a)) t > (atom ’(atom ’a)) () = ⇒quote est un élément distinctif de LISP : c’est l’opérateur permettant de faire la distinction entre code et données (conséquence de leur équiva- lence structurelle en LISP) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 9 S-expressions ou S-exp Les sept Opérateurs Primitifs Opérateur n◦3 : (eq x y) Retourne t si les valeurs de x et y sont le même atome, () sinon > (eq ’a ’a) t > (eq ’a ’b) () > (eq ’() ’()) t > (eq ’(a b c) ’(a b c)) () Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 10 S-expressions ou S-exp Les sept Opérateurs Primitifs Opérateurs n◦4 et 5 : (car x) et (cdr x) Retournent le premier élément (le reste) de la valeur de x (cette valeur doit donc être une liste) > (car ’(a b c)) a > (cdr ’(a b c)) (b c) > (car ’()) () > (cdr nil) () Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 11 S-expressions ou S-exp Les sept Opérateurs Primitifs La vérité sur car, cdr et les listes Découlent de l’architecture matérielle de l’IBM 704 • car : Contents of Address Register • cdr : Contents of Decrement Register • Une liste n’est en fait composée que d’un car et d’un cdr • Le car et le cdr sont séparés par des points : (car . cdr) = ⇒La notation par espacement est en réalité un raccourci d’écriture pour des listes de listes. Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 12 S-expressions ou S-exp Les sept Opérateurs Primitifs Exemples a nil (a) <=> (a . nil) nil nil (nil . nil) () a b c a nil b c nil a b nil (a b) <=> (a . (b)) <=> (a . (b . nil)) (a b . c) <=> (a . (b . c)) (a (b) c) <=> (a . ((b) c)) <=> (a . ((b) . (c))) <=> (a . ((b . nil) . (c . nil))) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 13 S-expressions ou S-exp Les sept Opérateurs Primitifs Opérateur n◦6 : (cons x y) Retourne la liste de car la valeur de x et de cdr la valeur de y (y est supposé être une liste) > (cons ’a ’(b c)) (a b c) > (cons ’a (cons ’b (cons ’c ’()))) (a b c) > (car (cons ’a ’(b c))) a > (cdr (cons ’a ’(b c))) (b c) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 14 S-expressions ou S-exp Les sept Opérateurs Primitifs Opérateur n◦7 : (cond (p1 e1) . . . (pn en)) Évalue les S-exp pi jusqu’à ce que l’une d’elles retourne t, puis retourne l’évaluation de la S-exp ei correspondante. > (cond ((eq ’a ’b) ’first) ((atom ’a) ’second)) second > (cond ((eq ’a ’b) ’first) ((eq ’c ’d) ’second) (t ’default)) default Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 15 Dénotation Fonctionnelle Dénotation Fonctionnelle • 5 opérateurs sur 7 évaluent toujours leurs arguments • Les deux autres sont quote et cond • Tout opérateur du premier type sera appelé «fonction» Ambigüité du terme mathématique «fonction» : • Les formes x + y2, f(x, y) etc sont appelées «fonctions» • Mais x + y2(3, 4) = 13 ou 19 ? ? = ⇒Notation λ de Church (1941) : λ((x1, . . . , xn), ϵ) λ((x, y), x + y2)(3, 4) = 19 Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 16 Dénotation Fonctionnelle Application à LISP Application à LISP Fonction LISP : • (lambda (p1 ...pn) e) • Les pi sont des atomes (paramètres) • e est une S-exp Appel de fonction LISP : • ((lambda (p1 ...pn) e) a1 ...an) • Les ai sont évalués • e est évaluée avec remplacement de chaque occurrence de pi par la valeur de ai Remarque : La valeur d’un ai peut très bien être une fonction. . . Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 17 Dénotation Fonctionnelle Application à LISP Exemples > ((lambda (x) (cons x ’(b c))) ’a) (a b c) > ((lambda (x y) (cons x (cdr y))) ’z ’(b c)) (z c) > ((lambda (f) (f ’(b c))) ’(lambda (x) (cons ’a x))) >> ((lambda (x) (cons ’a x)) ’(b c)) (a b c) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 18 Dénotation Fonctionnelle Fonctions récursives Fonctions récursives Rochester signale l’inadéquation de la notation lambda pour les fonctions récursives : fact = (lambda (n) (* n (fact ? ? ? (-1 n)))) = ⇒Nouvelle notation : • (label f (lambda (p1 ...pn) e)) • (defun f (p1 ...pn) e) Même comportement qu’une lambda-expression, mais toute occurrence de f est en plus évaluée à la lambda-expression elle-même. (defun fact (n) (* n (fact (-1 n)))) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 19 Quelques Fonctions Quelques Fonctions Commençons par des raccourcis. . . • (cadr e) : (car (cdr e)) • (cdar e) : (cdr (car e)) • (c[ad]+r e) : . . . • (list e1 . . .en) : (cons e1 ...(cons en ’()) ...) > (cadr ’((a b) (c d) e)) (c d) > (cdar ’((a b) (c d) e)) (b) > (list ’a ’b ’c) (a b c) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 20 Quelques Fonctions Quelques Opérateurs Logiques • null : (defun null (x) (eq x ’())) • not : (defun not (x) (cond (x ’()) (’t ’t))) • and : (defun and (x y) (cond (x (cond (y ’t) (’t ’()))) (’t ’()))) Le Premier LISP , Didier Verna - Séminaire du LRDE, 19 Juin 2002 21 Quelques Fonctions append Retourne la concaténation de deux listes (defun append (x y) (cond ((null x) y) (’t (cons (car x) (append (cdr x) y)))) > (append ’(a b) ’(c d)) (a b c d) > (append ’() ’(a b)) (a b) > (append ’(nil) uploads/s3/ courslisp-id4554-pdf.pdf