Planche : 1
Planche : 2
Tout ce que vous voulez savoir sur Scheme
Scheme est un langage universel, on peut donc écrire Scheme en Scheme.
C'est la fameuse fonction eval.
La définition de cette fonction est à la fois un manuel de référence,
un outil de génie logiciel (traceur, metteur au point ...), un
outil linguistique pour développer de nouveaux langages et la base de
la programmation réflexive.
Planche : 3
La fonction eval
(define (evaluate e env)
(if (atom? e)
(cond ((symbol? e) (lookup e env))
((or (number? e) (string? e) (char? e) (boolean? e))
e )
(else (wrong "Cannot evaluate" e)) )
(case (car e)
((quote) (cadr e))
((if) (if (evaluate (cadr e) env)
(evaluate (caddr e) env)
(evaluate (cadddr e) env) ))
((begin) (eprogn (cdr e) env))
((set!) (update! (cadr e) env (evaluate (caddr e) env)))
((lambda) (make-function (cadr e) (cddr e) env))
(else (invoke (evaluate (car e) env)
(evlis (cdr e) env) )) ) ) )
Planche : 4
Itérateurs autour d'eval
(define (evlis exps env)
(if (pair? exps)
(cons (evaluate (car exps) env)
(evlis (cdr exps) env) )
'() ) )
(define (eprogn exps env)
(if (pair? exps)
(if (pair? (cdr exps))
(begin (evaluate (car exps) env)
(eprogn (cdr exps) env) )
(evaluate (car exps) env) ) ) )
En DrScheme: (begin) induit le message
malformed begin.
Planche : 5
Environnement
(define (lookup id env)
(if (pair? env)
(if (eq? (caar env) id)
(cdar env)
(lookup id (cdr env)) )
(wrong "No such binding" id) ) )
(define (update! id env value)
(if (pair? env)
(if (eq? (caar env) id)
(set-cdr! (car env) value)
(update! id (cdr env) value) )
(wrong "No such binding" id) ) )
En DrScheme: a (define a 3) est légal mais induit le
message reference to undefined identifier: a avec
undefined au sens de « non initialisé ».
Planche : 6
Fonctions
(define (make-function variables body env)
(lambda (values)
(eprogn body (extend env variables values)) ) )
(define (invoke fn args)
(if (function? fn)
(fn args)
(wrong "Not a function" fn) ) )
(define function? procedure?)
Planche : 7
Extension d'environnement
(define (extend env names values)
(cond ((pair? names)
(if (pair? values)
(cons (cons (car names) (car values))
(extend env (cdr names) (cdr values)) )
(wrong "Too less values") ) )
((null? names)
(if (null? values)
env
(wrong "Too much values") ) )
((symbol? names) (cons (cons names values) env)) ) )
Planche : 8
Boucle fondamentale
(define (toplevel)
(display (evaluate (read) global-env))
(toplevel) )
Planche : 9
Environnement initial
(define (wrap-primitive name behavior comparator arity)
(lambda (values)
(if (comparator (length values) arity)
(apply behavior values)
(wrong "Incorrect arity" name) ) ) )
(define global-env
(list (cons 'car (wrap-primitive 'car car = 1))
(cons 'cons (wrap-primitive 'cons cons = 2))
(cons 'list (wrap-primitive 'list list >= 0))
... ) )
Il y a quelques fonctions un peu spéciales comme apply et
call/cc.
Planche : 10
Les différentes couches
eval est paramétré par deux types abstraits:
-
les environnements (lookup, update! et
extend),
- les fonctions (make-function, function?
et invoke).
Mais eval est aussi paramétré par;
-
les formes spéciales définies dans evaluate
- et bien sûr par l'environnement initial.
On peut exprimer ces dépendances en Scheme directement:
(define (build-evaluator env-repr fn-repr evaluate-repr global-env-repr)
(call-with-values (env-repr)
(lambda (lookup update! extend)
(call-with-values (fn-repr lookup update! extend)
(lambda (make-function function? invoke)
(call-with-values
(evaluate-repr lookup update! extend
make-function function? invoke )
(lambda (evaluate)
(define (evlis exps env)
(if (pair? exps)
(cons (evaluate (car exps) env)
(evlis (cdr exps) env) )
'() ) )
(define (eprogn exps env)
(if (pair? exps)
(if (pair? (cdr exps))
(begin (evaluate (car exps) env)
(eprogn (cdr exps) env) )
(evaluate (car exps) env) ) ) )
(call-with-values
(global-env-repr lookup update! extend
make-function function? invoke
evaluate evlis eprogn )
(lambda (global-env)
(define (toplevel)
(display (evaluate (read) global-env))
(toplevel) )
toplevel ) ) ) ) ) ) ) ) )
(define myScheme
(build-evaluator
(lambda ()
(define LOOKUP ...)
(define UPDATE! ...)
(define EXTEND ...)
(values LOOKUP UPDATE! EXTEND) )
(lambda (lookup update! extend)
(define MAKE-FUNCTION ...)
(define INVOKE ...)
(values MAKE-FUNCTION INVOKE) )
(lambda (lookup update! extend make-function function? invoke)
(define EVAL ...)
(values EVAL) )
(lambda (lookup update! extend make-function function? invoke
evaluate evlis eprogn )
(define GLOBALENV ...)
(values GLOBALENV) ) ) )
(myScheme)
J'oublais! call-with-values et values sont des
traits nouveaux du R5RS qui peuvent s'écrire comme:
(define values list)
(define (call-with-values producer consumer)
(apply consumer (producer)) )
((call-with-values (lambda () (values null? '() cons cdr))
(lambda (zero? one * pred)
(define (fact n)
(if (zero? n)
one
(* n (fact (pred n))) ) )
fact ) )
'(a b c) ) ;
Ce document a été traduit de LATEX par
HEVEA.
Scheme en Scheme