Revised 5 Report on the Algorithmic Language Scheme [ Scheme ] RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES (Editors) H. ABELSON R. K. DYBVIG C.

Transcription

1 Revised 5 Report on the Algorithmic Language Scheme [ Scheme ] RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES (Editors) H. ABELSON R. K. DYBVIG C. T. HAYNES G. J. ROZAS N. I. ADAMS IV D. P. FRIEDMAN E. KOHLBECKER G. L. STEELE JR. D. H. BARTLEY R. HALSTEAD D. OXLEY G. J. SUSSMAN G. BROOKS C. HANSON K. M. PITMAN M. WAND Robert Hieb Scheme Scheme Scheme Lisp Guy Lewis Steele Jr. Gerald Jay Sussman Scheme Scheme Scheme BNF Scheme Eval Translated into Japanese by Hisao Suzuki <suzuki@acm.org>

2 2 Revised 5 Scheme : We intend this report to belong to the entire Scheme community, and so we grant permission to copy it in whole or in part without fee. In particular, we encourage implementors of Scheme to Scheme use this report as a starting point for manuals and Scheme other documentation, modifying it as necessary. Scheme : Alan Bawden, Michael Blair, George Carrette, Andy Cromarty, Pavel Curtis, Jeff Dalton, Olivier Danvy, Ken Dickey, Bruce Duba, Marc Fee- Lisp ley, Andy Freeman, Richard Gabriel, Yekta Gürsel, Ken Scheme Haase, Robert Hieb, Paul Hudak, Morry Katz, Chris Lindblad, Mark Meyer, Jim Miller, Jim Philbin, John Ramsdell, goto Scheme Mike Shaff, Jonathan Shapiro, Julie Sussman, Perry Wagle, Daniel Weise, Henry Wu, Ozan Yigit Scheme 311 version 4 Scheme Carol Fessenden, Daniel Friedman, Common Lisp Christopher Haynes TI Scheme Language Scheme (hygienic macro) Reference Manual [30] Texas Instruments, Inc. MIT Scheme[17], T[22], Scheme 84[11],Common Lisp[27], Algol 60[18] TEX Betty Dexter Donald Knuth Scheme 1975 [28] 1978 [25] MIT Massachusetts Institute of Technology Indiana Oregon [26] 1981 NEC Research Institute 1982 MIT Yale MIT Indiana Scheme Advanced Research Projects Agency [21, 17, 10] Scheme N C-0505 Indiana NFS NCS [1] Scheme NCS Scheme Scheme [4] 1985 MIT Indiana 1986 [23] 1988 [6] Xerox PARC Scheme Scheme

3 1. Scheme 3 1. Scheme 1.1. Scheme Scheme Scheme Scheme Algol Scheme Scheme (exact arithmetic) Common Lisp Scheme ( ) ( 1.2. ) APL Snobol Lisp ( Scheme Lisp ( ) ) Algol 60 Pacal, C Scheme Scheme Scheme (continuation) (extent) Scheme Scheme eval Scheme Scheme (!) read read APL Lisp (7.1.2 ) Scheme (properly tail-recursive) Scheme Scheme (optional) Scheme Scheme Common Lisp ML Scheme Scheme (library) 6.4 (primitive) Scheme ML C APL Haskell Algol 60

4 4 Revised 5 Scheme < > 1 category italic (vector-ref vector k) vector-ref vector k ( ) (make-vector k) (make-vector k fill) make-vector 3.2 vector-ref vector-ref (unspecified) obj list, list 1,... list j,... (6.3.2 ) z, z 1,... z j,... x, x 1,... x j,... y, y 1,... y j,... q, q ,... q j,... n, n 1,... n j, k, k 1,... k j, = template category (* 5 8) = 40 (* 5 8) 40 template qualifier category (* 5 8) 40 qualifier category 3.3 template < > < > < >? (predicate) < 1>... < > 0 (3.4 )! (mutation procedure) < 1> < 2>...

5 2. 5 -> list->vector (;) (comment) Scheme 2. Scheme Scheme 7.1 ;;; FACT ;;; (factorial) (define fact Foo FOO (lambda (n) #x1ab #X1ab (if (= n 0) 1 ; : 1 (* n (fact (- n 1)))))) Scheme Scheme ( lambda q ) list->vector soup (6.3.2 ) + V17a (4.1.4 ) <=? a34ktmns the-word-recursion-has-many-meanings ( ) (6.3.2 )! $ % & * + -. / : < = ^ _ ~ (4.1.2 ) ` (4.2.6 ) Scheme,,@ (4.2.6 ) " (6.3.5 ) ( ) \ (6.3.4 ) (4.1.2 ) (6.3.5 ) (6.3.3 ) [ ] { } 2.2. # (whitespace character) ( ) #t #f (6.3.1 ) #\ (6.3.4 ) #( (6.3.6 ) )

6 6 Revised 5 Scheme #e #i #b #o #d #x (6.2.4 ) 3. Scheme #f (true) #f Scheme (syntactic keyword) (false) #f (bound) (variable) (environment) 3.3. Scheme ( Lisp) (external representation) (8 13) (binding construct) #e #x1c lambda ( ) (8. (13. ())) lambda (6.3.2 ) let, let*, letrec, do (4.1.4, 4.2.2, ( ) ) Algol Pascal Common Lisp Lisp Scheme (4.1.2 quote ) read (6.6.2 ) write (6.6.3 ) (region) lambda lambda (+ 2 6) Scheme (4 6 ) (unbound) 3.2. ( ) boolean? pair? symbol? number? char? string? vector? port? 6 procedure?

7 ( Steele Sussman Scheme ) Scheme string-set! (actor) car vector-ref string-ref Steele Sussman eqv? (6.1 ) (tail call) (tail context) < > ( ) (lambda < > < >* < >* < >) (mutable) (immutable) < > symbol->string 7 < > < > 3.5. (if < > < > < >) (if < > < >) (cond <cond > + ) Scheme (cond <cond >* (else < >)) (case < > Scheme <case > + ) (case < > <case >* (else < >)) call-with-current-continuation (and < >* < >) (or < >* < >) (let (< >*) < >) (let < > (< >*) < >) [8] (let* (< >*) < >) : (letrec (< >*) < >) (let-syntax (< >*) < >)

8 8 Revised 5 Scheme (letrec-syntax (< >*) < >) (begin < >) (do (< >*) (< > < >) < >*) <cond > (< > < >) <case > ((< >*) < >) < > < >* < > < > < >* < > < > (3.1 ) (define x 28) x = cond (< 1 > => < 2 >) < 2 > (quote < >) ( ) < > < 2 > < > (quote < >) < > < > Scheme (3.3 apply call-with-current-continuation ) Scheme call-with-values eval eval (quote a) = a (quote #(a b c)) = #(a b c) (quote (+ 1 2)) f g h = (+ 1 2) x (quote < >) < > (lambda () (if (g) (let ((x (h))) x) (and (g) (f)))) a #(a b c) () (+ 1 2) = = = = a #(a b c) () (+ 1 2) (quote a) = (quote a) a = : h (quote a) let (quote) h (h let ) "abc" = "abc" "abc" = "abc" = = #t = #t (primitive expression type) #t = #t (derived expression type) 3.4 ( ) quasiquote set-car! string-set! 7.3

9 (reverse-subtract 7 10) = 3 (< > < 1>... ) (define add4 (let ((x 4)) (lambda (y) (+ x y)))) (add4 6) = 10 ( ) < > (+ 3 4) = 7 (< 1 >... ): ((if #f + *) 3 4) = 12 + < >: * lambda (4.1.4 ) (6.4 values < > ) values apply (< 1 >... < n >. < n+1 >): ( ) n n ( 1 ) : Lisp : < > < > ((lambda x x) ) = ( ) : Lisp () ((lambda (x y. z) z) Scheme ) = (5 6) () eqv? eq? lambda ( ) (6.1 ) (lambda < > >) : < > < > (if < > < > < >) : lambda lambda (if < > < >) : < > < > < > : if < > lambda (6.3.1 ) < > ( ) < > ( lambda ) < > ( ) < > ( ) (lambda (x) (+ x x)) = ((lambda (x) (+ x x)) 4) = 8 (define reverse-subtract (lambda (x y) (- y x))) (if (> 3 2) yes no) = yes (if (> 2 3) yes no) = no (if (> 3 2) (- 3 2) (+ 3 2)) = 1

10 10 Revised 5 Scheme : < > < > (set! < > < >) < > < > ((< 1>... ) < 1> < 2>... ), < > set! < > < > set! < > else (define x 2) (else < 1> < 2>... ). (+ x 1) = 3 (set! x 4) = : case < > (+ x 1) = 5 < > < > < > (eqv? ) (6.1 ) < > 4.2. < > ( ) case ( ) 4.3 < > < > 7.3 else ( ) case ( ) case (cond < 1 > < 2 >... ) : < > (< > 1 >... ) (case < > < 1 > < 2 >... ) (case (* 2 3) (( ) prime) (( ) composite)) = composite (case (car (c d)) ((a) a) ((b) b)) = < > < > (case (car (c d)) ((a e i o u) vowel) ((w y) semivowel) (< > => < >) (else consonant)) = consonant < > else (else < 1 > < 2 >... ). (and < 1>... ) : cond < > < > < > (6.3.1 (6.3.1 ) ) < > < > < > #t < > < > ( ) cond ( ) < > < > < > (and (= 2 2) (> 2 1)) = #t < > (and (= 2 2) (< 2 1)) = #f < > => < > (and 1 2 c (f g)) = (f g) (and) = #t < > ( (or < 1>... ) ) cond < > < > (6.3.1 else ) else < > ( ) #f (cond ((> 3 2) greater) ((< 3 2) less)) = greater (cond ((> 3 3) greater) (or (= 2 2) (> 2 1)) = #t ((< 3 3) less) (or (= 2 2) (< 2 1)) = #t (else equal)) = equal (or #f #f #f) = #f (cond ((assv b ((a 1) (b 2))) => cadr) (or (memq b (a b c)) (else #f)) = 2 (/ 3 0)) = (b c)

11 < > < > let, let*, letrec Scheme Algol 60 : let < > let* < > ( ) < > letrec < > < > < > ( ) < > letrec (let < > < >) (letrec ((even? : < > (lambda (n) ((< 1> < 1>)... ), (if (zero? n) #t < > < > (odd? (- n 1))))) (odd? < > (lambda (n) (if (zero? n) : < > ( #f ) (even? (- n 1)))))) < > (even? 88)) < > < > ( = #t ) < > < > letrec < > < > (let ((x 2) (y 3)) (* x y)) = 6 Scheme (let ((x 2) (y 3)) letrec (let ((x 7) < > lambda (z (+ x y))) (* z x))) = let (let* < > < >) (begin < 1 > < 2 >... ) : < > < > < > ((< 1> < 1>)... ), < > (define x 0) : let* let (< > < >) (begin (set! x 5) let* (+ x 1)) = 6 (let ((x 2) (y 3)) (let* ((x 7) (z (+ x y))) (* z x))) = 70 (letrec < > < >) (do ((< 1 > < 1> < 1>) : < > ((< 1> < 1>)... ), ( ) (begin (display "4 plus 1 equals ") (display (+ 4 1))) = 4 plus 1 equals ) (< > < >... ) < >... )

12 12 Revised 5 Scheme do nonneg (cons (car numbers) neg))))) = ((6 1 3) (-5-2)) < > do < > ( ) < > < > < > (delay < >) < > delay (lazy evaluation) (6.3.1 ) call by need force < > < > (delay < >) (promise) < > < > < > < > (force ) < > < > < > < > ( ) delay force (6.4 ) < > do < > < > do do < > < > (quasiquote <qq >) (< > < >) (< > < > < >) `<qq > (do ((vec (make-vector 5)) (i 0 (+ i 1))) ((= i 5) vec) <qq > (vector-set! vec i i)) = #( ) `<qq > <qq > (let ((x ( ))) (do ((x x (cdr x)) <qq > (sum 0 (+ sum (car x)))) ( unquote ((null? x) sum))) = 25 ) (@) (let < > < > < >) let let do - - <qq > let < > < > `(list,(+ 1 2) 4) = (list 3 4) < > (let ((name a)) `(list,name,name)) < > = (list a (quote a)) < > `(a,(+ 1 2),@(map abs (4-5 6)) b) = (a b) (let loop ((numbers ( )) `(( foo,(- 10 3)),@(cdr (c)).,(car (cons))) (nonneg ()) = ((foo 7). cons) (neg ())) `#(10 5,(sqrt 4),@(map sqrt (16 9)) 8) (cond ((null? numbers) (list nonneg neg)) = #( ) ((>= (car numbers) 0) (loop (cdr numbers) (cons (car numbers) nonneg) unquote neg)) ((< (car numbers) 0) (loop (cdr numbers) unquote 1

13 `(a `(b,(+ 1 2),(foo,(+ 1 3) d) e) f) = (a `(b,(+ 1 2),(foo 4 d) e) f) (let ((name1 x) (name2 y)) `(a `(b,,name1,,name2 d) e)) = (a `(b,x, y d) e) `<qq > (quasiquote <qq >),< > (unquote < >),@< > (unquote-splicing < >) car write (quasiquote (list (unquote (+ 1 2)) 4)) = (list 3 4) let-syntax letrec-syntax let letrec (quasiquote (list (unquote (+ 1 2)) 4)) = `(list,(+ 1 2) 4) i.e., (quasiquote (list (unquote (+ 1 2)) 4)) 5.3 quasiquote, unquote, unquote-splicing (let-syntax < > < >) <qq > : < > < > < > 4.3. syntax-rules < > Scheme < > (macro) (< > < >...) : let-syntax < > < > < > < > < > < > (let-syntax ((when (syntax-rules () (use) ((when test stmt1 stmt2...) (if test (begin stmt1 (transformer) stmt2...)))))) (let ((if #t)) (when if (set! if now)) if)) = now (let ((x outer)) (let-syntax ((m (syntax-rules () ((m) x)))) (let ((x inner)) (m)))) = outer ( ) define (5.2 ) ((< > < >)... ) (letrec-syntax < > < >) : let-syntax : letrec-syntax (hygienic) (referentially transparent) < > Scheme < > [14, 15, 2, 7, 9]

14 14 Revised 5 Scheme < > < > < > letrec-syntax < > (letrec-syntax ((my-or (syntax-rules () < >... ((my-or) #f) ((my-or e) e) ((my-or e1 e2...) < > (let ((temp e1)) (if temp temp < > (my-or e2...))))))) (let ((x #f) (y 7) (temp 8) : (let odd?) (if even?)) (my-or x let-syntax letrec-syntax (let temp) (if y) y))) = < > (syntax-rules < > < >... )... : < > < >... < >... (< > < >) < > < > < > F P < > (< >...) (< > < >.... < >) (< >... < > < >) #(< >...) #(< >... < > < >) < > P P F P (P 1... P n ) F P 1 P n n (< >...) (< > < >.... < >) #(< >...) P (P 1 P 2... P n. P n+1 ) < > < > F P 1 P n n < > < >... ( n cdr P n+1 ) P (P 1... P n P n+1 < >) : syntax-rules < >... F n P 1 P n n syntax-rules < > F P n+1 < >

15 P #(P 1... P n ) 5. F P 1 P n n P #(P 1... P n P n+1 < >) < >... Scheme F n P 1 P n 4 n F P n+1 Scheme P F P equal? ( Scheme ) < > = (begin < 1 >... ) begin syntax-rules < > < > let cond 7.3 (define < > < >) ( ) (define (< > < >) < >) (let ((=> #f)) < > (cond (#t => ok))) = ok cond => ( ) => (let ((=> #f)) (if #t (begin => ok))) (define (< >. < >) < >) (let ((=> #f)) (let ((temp #t)) (if temp ( ok temp)))) (define < > (lambda (< >) < >)). < > (define < > (lambda < > < >)).

16 16 Revised 5 Scheme < > (define < > < >) < > (define-syntax < > < >) (set! < > < >) < > < > syntax-rules < > < > < > set! define-syntax (define add3 (lambda (x) (+ x 3))) (add3 3) = 6 (define first car) (first (1 2)) = 1 Scheme (define define 3) (begin (define begin list)) (let-syntax ((foo (syntax-rules () < > ( lambda, let, let*, letrec ((foo (proc args...) body...) let-syntax, letrec-syntax (define proc ) (lambda (args...) (internal body...)))))) definition) < > (let ((x 3)) < > (foo (plus x y) (+ x y)) < > (define foo x) (plus foo x))) (let ((x 5)) (define foo (lambda (y) (bar x y))) (define bar (lambda (a b) (+ (* a b) a))) (foo (+ x 3))) = Scheme ( < > letrec ) Scheme let abs (let ((x 5)) (letrec ((foo (lambda (y) (bar x y))) ( ) (bar (lambda (a b) (+ (* a b) a)))) + (foo (+ x 3)))) letrec < > = < > < > (4.1.6 ) Scheme (begin < 1 >... ) = begin

17 obj 1 obj 2 (predicate) (#t #f) obj 1 obj 2 = #f (equivalence predicate) ( obj 1 obj 2 char=? ) #f eq? ( ) equal? eqv? eq? obj 1 obj 2 obj 1 obj 2 (eqv? obj 1 obj 2 ) eqv? obj obj 1 obj 2 1 obj 2 ( #t ) eqv? Scheme (eqv? a a) = #t eqv? #t : (eqv? a b) = #f (eqv? 2 2) = #t (eqv? () ()) = #t obj 1 obj 2 #t #f (eqv? ) = #t (eqv? (cons 1 2) (cons 1 2))= #f obj 1 obj 2 (string=? (symbol->string obj1) (symbol->string obj2)) = #t (eqv? (lambda () 1) (lambda () 2)) = #f (eqv? #f nil) = #f (let ((p (lambda (x) x))) (eqv? p p)) = #t : obj 1 obj eqv? eqv? eqv? obj 1 obj 2, (6.2 (eqv? "" "") = = ) (eqv? #() #()) = (eqv? (lambda (x) x) (lambda (x) x)) = obj 1 obj 2 char=? (eqv? (lambda (x) x) (6.3.4 ) (lambda (y) y)) = obj 1 obj 2 eqv? gen-counter obj 1 obj 2 (3.4 ) gen-loser obj 1 obj 2 (4.1.4 ) (define gen-counter (lambda () eqv? #f : (let ((n 0)) (lambda () (set! n (+ n 1)) n)))) obj 1 obj 2 (3.2 ) (let ((g (gen-counter))) (eqv? g g)) = #t obj 1 obj 2 #t #f (eqv? (gen-counter) (gen-counter)) = #f obj 1 obj 2 (define gen-loser (lambda () (string=? (symbol->string obj 1 ) (let ((n 0)) (symbol->string obj 2)) (lambda () (set! n (+ n 1)) 27)))) = #f (let ((g (gen-loser)))

18 18 Revised 5 Scheme (eqv? g g)) = #t (eqv? (gen-loser) (gen-loser)) = (letrec ((f (lambda () (if (eqv? f g) both f))) (g (lambda () (if (eqv? f g) both g)))) (eqv? f g)) = (eq? obj 1 obj 2 ) : eq? eqv? eq? eqv? eq? eqv? eq? eqv? (letrec ((f (lambda () (if (eqv? f g) f both))) (g (lambda () (if (eqv? f g) g both)))) (eqv? f g)) (equal? obj 1 obj 2 ) = #f equal? ( ) eqv? equal? eqv? equal? (eqv? (a) (a)) = (eqv? "a" "a") = (equal? a a) = #t (eqv? (b) (cdr (a b))) = (equal? (a) (a)) = #t (let ((x (a))) (eqv? x x)) = #t (equal? (a (b) c) (a (b) c)) = #t (equal? "abc" "abc") = #t : eqv? (equal? 2 2) = #t (equal? (make-vector 5 a) (make-vector 5 a)) = #t (equal? (lambda (x) x) (lambda (y) y)) = 6.2. eq? eqv? eqv? Lisp eq? eqv? Common Lisp MacLisp [20] eq? Common Lisp eqv? eq? eqv? Scheme (eq? a a) = #t (eq? (a) (a)) = (eq? (list a) (list a)) = #f Scheme (eq? "a" "a") = Scheme (eq? "" "") = (eq? () ()) = #t number, complex, real, rational, (eq? 2 2) = integer Scheme (eq? #\A #\A) = (eq? car car) = #t fixnum flonum (let ((n (+ 2 3))) (eq? n n)) = (let ((x (a))) (eq? x x)) = #t (let ((x #())) (eq? x x)) = #t (let ((p (lambda (x) x))) (eq? p p)) = #t :

19 number ( ) complex ( ) real ( ) rational ( ) integer ( ) Scheme Scheme number?, complex?, real?, rational?, Scheme integer? Scheme Scheme 3 Scheme Scheme fixnum flonum ( ) flonum Scheme Scheme length, vector-length, string-length Scheme exact ( ) inexact ( ) : + - * quotient remainder modulo max min abs numerator denominator gcd lcm floor ceiling truncate round rationalize expt + / inexact->exact

20 20 Revised 5 Scheme flonum short single long IEEE 32-bit and 64-bit floating point standards double ) e [12] double flonum F0 : flonum single L0 sqrt long ( square root 2 ) ( ) (sqrt ) flonum flonum flonum flonum Scheme (number? obj ) (complex? obj ) (real? obj ) (rational? obj ) (integer? obj ) #t #f (radix prefix) #b (binary, z (real? z) ), #o (octal, ), #d (decimal, ), #x (hexadecimal, ) x (integer? x) (zero? (imag-part z)) (= x (round x)) (complex? 3+4i) = #t (exact) #e (inexact) #i (complex? 3) = #t (exactness (real? 3) = #t prefix) (real? i) = #t (real? #e1e10) = #t (rational? 6/10) = #t # (rational? 6/3) = #t (integer? 3+0i) = #t (integer? 3.0) = #t (integer? 8/4) = #t : s, f, d, l short, single, double, long ( : rational? real? complex? number?

21 6. 21 (+ 3 4) = 7 (+ 3) = 3 (+) (* 4) = = 0 4 (exact? z) (*) = 1 (inexact? z) (- z 1 z 2 ) Scheme (- z) (- z 1 z 2... ) (/ z 1 z 2 ) (= z 1 z 2 z 3... ) (/ z) (< x 1 x 2 x 3... ) (/ z 1 z 2... ) (> x 1 x 2 x 3... ) (<= x 1 x 2 x 3... ) (>= x 1 x 2 x 3... ) ( ) (- 3 4) = -1 ( ) = -6 #t (- 3) = -3 (/ 3 4 5) = 3/20 (/ 3) = 1/3 : Lisp : (abs x) abs (absolute value) = zero? (abs -7) = 7 (zero? z) (quotient n 1 n 2 ) (positive? x) (remainder n 1 n 2 ) (negative? x) (modulo n 1 n 2 ) (odd? n) ( ) n 2 (even? n) #t n 1 /n 2 : #f (quotient n 1 n 2) = n 1/n 2 (remainder n 1 n 2 ) = 0 (max x 1 x 2... ) (modulo n 1 n 2) = 0 (min x 1 x 2... ) (maximum) n 1 /n 2 : (minimum) (quotient n 1 n 2 ) = n q (max 3 4) = 4 ; (remainder n 1 n 2) = n r (max 3.9 4) = 4.0 ; (modulo n 1 n 2 ) = n m : n ( q n 1 /n 2, 0 < n r < n 2, 0 < n m < n 2, n r n m n 1 n 2, n ) min max r n 1, n m n 2 n 1 n 2 ( 0) : (= n 1 (+ (* n 2 (quotient n 1 n 2)) (remainder n 1 n 2 ))) (+ z 1... ) = #t (* z 1... )

22 22 Revised 5 Scheme (modulo 13 4) = 1 (remainder 13 4) = 1 (modulo -13 4) = 3 (remainder -13 4) = -1 (modulo 13-4) = -3 (remainder 13-4) = 1 (modulo -13-4) = -1 (remainder -13-4) = -1 (remainder ) = -1.0 ; (floor -4.3) = -5.0 (ceiling -4.3) = -4.0 (truncate -4.3) = -4.0 (round -4.3) = -4.0 (floor 3.5) = 3.0 (ceiling 3.5) = 4.0 (truncate 3.5) = 3.0 (round 3.5) = 4.0 ; (round 7/2) = 4 ; (round 7) = 7 (rationalize x y) (gcd n 1... ) rationalize x y (lcm n 1... ) r 1, r 2 r 1 = p 1 /q 1, (greatest common divisor) (least common multiple) r 2 = p 2 /q 2 ( ) p 1 p 2 q 1 q 2 r 1 r 2 3/5 4/7 ( 2/7 3/5) (gcd 32-36) = 4 (gcd) = 0 (2/7 3/5 (lcm 32-36) = 288 2/5 ) 0 = 0/1 (lcm ) = ; (lcm) = 1 (rationalize (inexact->exact.3) 1/10) = 1/3 ; (numerator q) (rationalize.3 1/10) = #i1/3 ; (denominator q) (numerator) (denominator) (log z) (exp z) (sin z) 0 1 (cos z) (tan z) (numerator (/ 6 4)) = 3 (asin z) (denominator (/ 6 4)) = 2 (denominator (acos z) (exact->inexact (/ 6 4))) = 2.0 (atan z) (atan y x) (floor x) (ceiling x) log z ( ) asin, (truncate x) acos, atan arcsine (sin 1 ), arccosine (round x) (cos 1 ), arctangent (tan 1 ) floor x atan ceiling x truncate (angle (make-rectangular x y)) ( x x ) round x x log, arcsine, arccosine, arctangent log z ( π, π] : round IEEE floating point log 0 log standard sin 1 z, cos 1 z, tan 1 z : : inexact->exact sin 1 z = i log(iz + 1 z 2 )

23 6. 23 cos 1 z = π/2 sin 1 z inexact->exact z tan 1 z = (log(1 + iz) log(1 iz))/(2i) [27] [19] branch cut (sqrt z) z (number->string z) (number->string z radix) (expt z 1 z 2 ) radix 2, 8, 10, 16 radix 10 number->string z 1 z 2 z 1 0 z z 2 z2 log z1 1 = e (number) (radix) (let ((number number) 0 z z = (radix radix)) (eqv? number (string->number (number->string number (make-rectangular x 1 x 2 ) radix) (make-polar x 3 x 4 ) radix))) (real-part z) (imag-part z) (magnitude z) z 10 (angle z) x 1, x 2, x 3, x 4 z ( ) [3, 5] z = x 1 + x 2 i = x 3 e ix 4 (make-rectangular x 1 x 2) = z (make-polar x 3 x 4 ) = z (real-part z) = x 1 (imag-part z) = x 2 (magnitude z) = x 3 (angle z) = x angle number->string : z : z flonum 10 NaN, flonum π < x angle π n (string->number string) x angle = x 4 + 2πn (string->number string radix) : magnitude abs (string) abs magnitude radix 2, 8, 10, 16 radix string ( "#o177") radix (exact->inexact z) 10 string (inexact->exact z) string->number #f exact->inexact z (string->number "100") = 100 (string->number "100" 16) = 256 (string->number "1e2") = (string->number "15##") =

24 24 Revised 5 Scheme : string->number (boolean? obj ) string->number string boolean? obj #t #f #t #f #f string->number string (boolean? #f) = #t #f (boolean? 0) = #f string->number (boolean? ()) = #f #f string->number # #f string->number pair ( dotted pair ) ( #f ) car cdr cons car cdr car cdr 6.3. car cdr set-car! set-cdr! Scheme (the empty list) cdr X #t ( ) X #f Scheme (if, cond, and, or, do) list X cdr list ( ) X ( ) car Scheme #f car cdr #f car cdr Scheme #t : Lisp Scheme #f nil ( ) : #t = #t Scheme ( ) #f = #f dotted notation (c 1. c 2 ) c 1 car #f = #f c 2 cdr (4. 5) car 4 cdr 5 (4. 5) (not obj ) not obj #t #f (not #t) = #f () (not 3) = #f (not (list 3)) = #f (not #f) = #t (a b c d e) (not ()) = #f (not (list)) = #f (not nil) = #f (a. (b. (c. (d. (e. ())))))

25 6. 25 (cons a ()) = (a) (cons (a) (b c d)) = ((a) b c d) (cons "a" (b c)) = ("a" b c) (improper list) (cons a 3) = (a. 3) (cons (a b) c) = ((a b). c) : (a b c. d) pair car car (a. (b. (c. d))) (car (a b c)) = a cdr (car ((a) b c d)) = (a) set-cdr! (car (1. 2)) = 1 (car ()) = : (define x (list a b c)) (define y x) y = (a b c) (list? y) = #t (set-cdr! x 4) = x = (a. 4) (eqv? x y) = #t y = (a. 4) (list? y) = #f (set-cdr! x x) = (list? x) = #f (car pair) (cdr pair) pair cdr cdr (cdr ((a) b c d)) = (b c d) (cdr (1. 2)) = 2 (cdr ()) = (set-car! pair obj ) pair car obj set-car! read < > `< >,< > (define (f) (list not-a-constant-list)),@< > (define (g) (constant-list)) quote quasiquote (set-car! (f) 3) = unquote unquote-splicing (set-car! (g) 3) = < > Scheme (set-cdr! pair obj ) Scheme < > < > (7.1.2 ) read pair cdr obj set-cdr! Scheme 3.3 (caar pair) (pair? obj ) (cadr pair).. pair? obj #t.. #f (cdddar pair) (cddddr pair) (pair? (a. b)) = #t car cdr (pair? (a b c)) = #t caddr (pair? ()) = #f (pair? #(a b)) = #f (define caddr (lambda (x) (car (cdr (cdr x))))). 4 (cons obj 1 obj 2 ) 28 car obj 1 cdr obj (null? obj ) 2 (eqv? ) obj #t #f

26 26 Revised 5 Scheme (list? obj ) (define list-tail (lambda (x k) obj #t #f (if (zero? k) x (list-tail (cdr x) (- k 1))))) (list? (a b c)) = #t (list? ()) = #t (list? (a. b)) = #f (let ((x (list a))) (set-cdr! x x) (list? x)) = #f (list-ref list k) (list-ref (a b c d) 2) = c (list obj... ) (list-ref (a b c d) (inexact->exact (round 1.8))) = c list k ( (list-tail list k) car ) list k (list a (+ 3 4) c) = (a 7 c) (list) = () (memq obj list) (memv obj list) (member obj list) (length list) list car obj list list k < (length (a b c)) = 3 list (list-tail list k) (length (a (b) (c d e))) = 3 obj list ( (length ()) = 0 ) #f memq eq? obj list memv eqv? member equal? (append list... ) (memq a (a b c)) = (a b c) list list (memq b (a b c)) = (b c) (memq a (b c d)) = #f (memq (list a) (b (a) c)) = #f (append (x) (y)) = (x y) (member (list a) (append (a) (b c d)) = (a b c d) (b (a) c)) = ((a) c) (append (a (b)) ((c))) = (a (b) (c)) (memq 101 ( )) = (memv 101 ( )) = ( ) list (assq obj alist) (assv obj alist) (append (a b) (c. d)) = (a b c. d) (assoc obj alist) (append () a) = a alist ( association list ) alist (reverse list) car obj alist obj car list ( ) #f assq eq? obj alist car (reverse (a b c)) = (c b a) assv eqv? assoc equal? (reverse (a (b c) d (e (f)))) = ((e (f)) d (b c) a) (define e ((a 1) (b 2) (c 3))) (assq a e) = (a 1) (assq b e) = (b 2) (list-tail list k) (assq d e) = #f (assq (list a) (((a)) ((b)) ((c)))) list k = #f list k (assoc (list a) (((a)) ((b)) ((c)))) list-tail = ((a))

27 6. 27 (assq 5 ((2 3) (5 7) (11 13))) = (assv 5 ((2 3) (5 7) (11 13))) = (5 7) : memq, memv, member, assq, assv, assoc #t #f string->symbol string->symbol string-set! (eqv? ) : (symbol->string flying-fish) = "flying-fish" Scheme (symbol->string Martin) = "martin" (symbol->string (string->symbol "Malvina")) Pascal = "Malvina" (string->symbol string) string Scheme read write read (eqv? ) symbol->string string->symbol write/read : (eq? mississippi mississippi) = #t : Scheme (string->symbol "mississippi") write/read slashification = "mississippi" (eq? bitblt (string->symbol "bitblt")) = #f (eq? JollyWog slashification write/read (string->symbol (symbol->string JollyWog))) = #t (string=? "K. Harper, M.D." (symbol->string (string->symbol "K. Harper, M.D."))) (symbol? obj ) = #t obj #t #f (symbol? foo) = #t (printed character) (symbol? (car (a b))) = #t #\< > (symbol? "bar") = #f (symbol? nil) = #t #\< > : (symbol? ()) = #f (symbol? #f) = #f #\a ; #\A ; (symbol->string symbol) #\( ; #\ ; symbol #\space ; (4.1.2 ) read #\newline ;

28 28 Revised 5 Scheme #\< > #\< > #\< > < > < > #\space (char-alphabetic? char) #\s (char-numeric? char) pace (char-whitespace? char) (char-upper-case? letter) (char-lower-case? letter) #\ #t #f ASCII -ci ( case insensitive ) : (char? obj ) obj #t #f (char->integer char) (integer->char n) char->integer (char=? char 1 char 2 ) char->integer (char<? char 1 char 2 ) (image) integer-> (char>? char 1 char 2 ) char char<=? (char<=? char 1 char 2 ) <= (char>=? char 1 char 2 ) : (char<=? a b) = #t (<= x y) = #t x y integer->char (char<? #\A #\B) #t (<= (char->integer a) (char<? #\a #\b) #t (char->integer b)) = #t (char<? (char<=? (integer->char x) #\0 #\9) #t (integer->char y)) = #t (char-upcase char) (char-downcase char) (char-ci=? char char 2 ) char 2 char char-upcase char-downcase (char-ci=? char 1 char 2 ) (char-ci<? char 1 char 2 ) (char-ci>? char 1 char 2 ) (string) (sequence of characters) (char-ci<=? char 1 char 2 ) (") (char-ci>=? char 1 char 2 ) (\) char=? (char-ci=? #\A #\a) #t "The word \"recursion\" has many meanings."

29 6. 29 (define (f) (make-string 3 #\*)) (define (g) "***") (string-set! (f) 0 #\?) = Scheme (string-set! (g) 0 #\?) = (string-set! (symbol->string immutable) 0 #\?) = (length) (string=? string 1 string 2 ) (valid index) (string-ci=? string 1 string 2 ) 0 1 #t #f string-ci=? start end string string=? start end start end (string<? string 1 string 2 ) start end string (string>? string 1 (string<=? string 1 string 2 ) string 2 ) (string>=? string 1 string 2 ) (string-ci<? string 1 string 2 ) (string-ci>? string -ci ( case insensitive ) 1 string 2 ) (string-ci<=? string 1 string 2 ) (string-ci>=? string 1 string 2 ) (string? obj ) string<? obj #t #f char<? (make-string k) (make-string k char) string=? string-ci=? make-string k char char string (substring string start end) (string char... ) string start end 0 start end (string-length string). substring string start ( ) end ( ) (string-length string) string (string-append string... ) (string-ref string k) k string string-ref string k (string->list string) (list->string list) (string-set! string k char) string->list k string string-set! list-> string k char string list

30 30 Revised 5 Scheme (vector a b c) = #(a b c) string->list list->string equal? (vector-length vector) (string-copy string) vector string (vector-ref vector k) (string-fill! string char) string char k vector vector-ref vector k (vector-ref #( ) ) = 8 (vector-ref #( ) ( : ) (let ((i (round (* 2 (acos -1))))) (if (inexact? i) (inexact->exact i) i))) = 13 (length) (valid index) (vector-set! vector k obj ) k vector vector-set! 1 vector k obj vector-set! #(obj... ) (2 (let ((vec (vector 0 ( ) "Anna"))) 2 2 2) 2 "Anna" (vector-set! vec 1 ("Sue" "Sue")) : vec) #(0 ( ) "Anna") = #(0 ("Sue" "Sue") "Anna") (vector-set! #(0 1 2) 1 "doe") = ; : #(0 ( ) "Anna") = #(0 ( ) "Anna") (vector->list vector) (list->vector list) (vector? obj ) vector->list vector obj #t #f list->vector list (make-vector k) (vector->list #(dah dah didah)) (make-vector k fill) = (dah dah didah) k (list->vector (dididit dah)) fill = #(dididit dah) (vector-fill! vector fill) (vector obj... ) vector fill vector-fill! list

31 for-each map for-each proc procedure? map for-each proc list for-each (procedure? obj ) obj #t #f (let ((v (make-vector 5))) (procedure? car) = #t (procedure? car) = #f (procedure? (lambda (x) (* x x))) = #t (procedure? (lambda (x) (* x x))) = #f (call-with-current-continuation procedure?) = #t (define compose (lambda (f g) (lambda args (f (apply g args))))) ((compose sqrt *) 12 75) = 30 (for-each proc list 1 list 2... ) (for-each (lambda (i) (vector-set! v i (* i i))) ( )) v) = #( ) (force promise) promise (force) (4.2.5 delay ) (apply proc arg 1... args) force ( memoize proc args ) proc (append (list arg 1... ) args) (force (delay (+ 1 2))) = 3 (apply + (list 3 4)) = 7 (let ((p (delay (+ 1 2)))) (list (force p) (force p))) = (3 3) (define a-stream (letrec ((next (lambda (n) (cons n (delay (next (+ n 1))))))) (next 0))) (define head car) (map proc list 1 list 2... ) (define tail (lambda (stream) (force (cdr stream)))) list proc list (head (tail (tail a-stream))) list = 2 map proc list force delay proc list force (map cadr ((a b) (d e) (g h))) = (b e h) (map (lambda (n) (expt n n)) ( )) = ( ) (map + (1 2 3) (4 5 6)) = (5 7 9) (let ((count 0)) (map (lambda (ignored) (set! count (+ count 1)) count) (a b))) = (1 2) (2 1) (define count 0) (define p (delay (begin (set! count (+ count 1)) (if (> count x) count (force p))))) (define x 5) p = (force p) = 6 p = (begin (set! x 10) (force p)) = 6

32 32 Revised 5 Scheme delay force (+ (delay (* 3 7)) 13) = 34 force : (call-with-current-continuation proc) (define force (lambda (object) proc (object))) (delay <expression>) call-with-current-continuation ( ) (escape procedure) proc : Scheme (make-promise (lambda () <expression>)) dynamic-wind before after : call-with-current-continuation (define-syntax delay (syntax-rules () ((delay expression) call-with-values (make-promise (lambda () expression))))), call-with-values make-promise : (define make-promise (lambda (proc) (let ((result-ready? #f) (result #f)) (lambda () (if result-ready? result (let ((x (proc))) (if result-ready? result (begin (set! result-ready? #t) (set! result x) result)))))))) (eqv? (delay 1) 1) = (pair? (delay (cons 1 2))) = proc Scheme call-with-current-continuation call-with-current-continuation (call-with-current-continuation (lambda (exit) (for-each (lambda (x) : (if (negative? x) force force force (exit x))) ( )) make-promise #t)) = -3 (define list-length delay force : (lambda (obj) (call-with-current-continuation (lambda (return) force (letrec ((r (lambda (obj) (cond ((null? obj) 0) force ((pair? obj) (+ (r (cdr obj)) 1)) #t #f (else (return #f)))))) : (r obj)))))) (list-length ( )) = 4 (list-length (a b. c)) = #f cdr + : force implicit forcing ( ) : call-with-current-continuation

33 6. 33 call-with-current-continuation (dynamic-wind before thunk after) thunk ( Scheme ) before after (continuation) ( ) (call-with-current-continuation ) before thunk 7 after (dynamic extent) Scheme call-with-current-continuation call-with-current-continuation : Scheme exit return goto 1965 Peter Landin [16] J (call-with-current-continuation ) John Reynolds [24] 1972 Sussman Steele 1975 Scheme catch MacLisp Reynolds Scheme catch call-with-current-continuation 1982 dynamic-wind thunk call/cc dynamic-wind after (values obj...) dynamic-wind ( ) after ( ) call-with-values dynamic-wind thunk values : dynamic-wind before (define (values. things) (call-with-current-continuation dynamic-wind ( ) (lambda (cont) (apply cont things)))) before dynamic-wind before (call-with-values producer consumer) after after producer ( ) before after consumer consumer call-with-values (call-with-values (lambda () (values 4 5)) (lambda (a b) b)) (let ((path ()) (c #f)) (let ((add (lambda (s) = 5 (set! path (cons s path))))) (dynamic-wind (call-with-values * -) = -1 (lambda () (add connect)) (lambda ()

34 34 Revised 5 Scheme 6.5. Eval (add (call-with-current-continuation (lambda (c0) (set! c c0) talk1)))) (lambda () (add disconnect))) (if (< (length path) 4) (c talk2) (reverse path)))) = (connect talk1 disconnect connect talk2 disconnect) scheme-report-environment ( car) (eval ) scheme-report-environment (interaction-environment) write (eval expression environment-specifier) (port) (input) (output) expression Scheme expression Scheme Scheme environment-specifier Scheme eval (call-with-input-file string proc) ( ) (call-with-output-file string proc) : eval null-environment scheme-report-environment string proc call-with-input-file (eval (* 7 3) (scheme-report-environment 5)) call-with-output-file = 21 proc (let ((f (eval (lambda (f x) (f x x)) (f + 10)) (null-environment 5)))) proc = 20 proc ( ) proc read (scheme-report-environment version) (null-environment version) : Scheme version 5 Scheme (the Revised 5 Report on Scheme) call-with-current-continuation scheme-report-environment call-with-input-file call-with-output-file (specifier) null-environment (input-port? obj ) (output-port? obj ) obj #t #f version version 5 (current-input-port) (current-output-port)

35 6. 35 (with-input-from-file string thunk) end of file (with-output-to-file string thunk) read end of file string end of file thunk with-input-from-file with-output-to-file port current-inputport read current-input-port current-output-port ( (read) (write obj ) ) thunk (read-char) thunk (read-char port) with-input-from-file with-output-to-file thunk ( port ) port end of file port current-input-port (open-input-file filename) (peek-char) (peek-char port) port port end of file (open-output-file filename) port current-input-port : peek-char port read-char port read-char peek-char peek-char peek-char read-char (close-input-port port) (close-output-port port) (eof-object? obj ) port port obj end of file #t #f end of file end of file read (char-ready?) (read) (char-ready? port) (read port) port #t read Scheme #f char-ready #t read < > port read-char ( ) read port end of file port char-ready? #t port current-input-port port : char-ready? end of file ( )

36 36 Revised 5 Scheme char-ready? char-ready? end of file #t end of file (load filename) filename Scheme load load (write obj ) current-input-port current-output-port (write obj port) load obj port : load load #\ write port current-output-port (transcript-on filename) (transcript-off) filename (display obj ) transcript-on (display obj port) Scheme obj port (transcript) transcript-off write write-char display port current-output-port : write display slashification slashify write display (newline) (newline port) end of line port port current-output-port (write-char char) (write-char char port) char ( ) port port current-output-port

37 < > quote lambda if set! begin cond and or case let let* letrec do delay quasiquote 7.1. < > < > < > < > #t #f BNF Scheme < > #\ < > #\ < > < > space newline #x1a #X1a < > < > " < >* " BNF : < > <" \ > < >* < > 0 \" \\ < > + 1 < > < > <2 > <8 > <10 > <16 > <R > <R > <R > <R > <R > <R > ( ) R = 2, 8, 10, 16 <2 > <8 > <16 > (decimal radix) < > <R > <R > <R > <R > <R > ( <R <R > ) < > <R > + <R > i <R > - <R > i <R > + i <R > - i : [ ] { } + <R > i - <R > i + i - i < > < > < > < > <R > < > <R > < > < > <R > <R > ( ) #( `,,@. <R > / <R > < > < > ( ) " ; <R > < > < > <10 > <10 > < > < > ;. <10 > + #* < > < > > < > <10 > +. <10 >* #* < > < > < >* <10 > + # +. #* < > <R > <R > + #* < > < > < >* <R > <R > < > < > < > <R > < > < > < > < > a b c... z < > < > < >! $ % & * / : < = < > > <10 > + >? ^ _ ~ < > e s f d l < > < > < > < > < > < > + - < > < > < > #i #e < > + <2 > #b < > <8 > #o < > < > <10 > < > #d else => define <16 > #x unquote unquote-splicing <2 > 0 1

38 38 Revised 5 Scheme <8 > < > <10 > < > (cond <cond > + ) <16 > <10 > a b c d e f (cond <cond >* (else < >)) (case < > <case > + ) (case < > < > read (6.6.2 ) <case >* < > (else < >)) < > (and < >*) (or < >*) < > < > < > (let (< >*) < >) < > < > < > (let < > (< >*) < >) < > < > < > (let* (< >*) < >) < > < > (letrec (< >*) < >) < > < > < > (begin < >) < > (< >*) (< > +. < >) (do (< >*) < > (< > <do >) < > < > < > < >*) < > `,,@ (delay < >) < > #(< >*) < > < > < > < > < > < > < > < > < > < > < > <cond > (< > < >) (< >) (< > => < >) < > < > <case > ((< >*) < >) < > (< > < >) < > (< > < > < >) (< > < >) < > < > < > < > <do > < > < > < < > < > < > > (< > < >*) < < > < > < > > < > < > < > < < > < > (quote < >) > < > (< > < >*) (let-syntax (< >*) < >) < > < > (letrec-syntax (< >*) < >) < < > < > > (< > < >) < > (lambda < > >) < > (< >*) < > (< > +. < >) < > < >* < > < > < >* < > < > < > < > (if < > < > < >) < > < > < > < > < > < > < > < > (set! < > < >) D = 1, 2, 3,... D (depth) < > < 1> <qq 0> < > < D> `<qq D> (quasiquote <qq D>) <qq D> < >

39 7. 39 < qq D> < qq D> < D> < qq D> < > > < > < > (begin < > + ) (<qq D>*) < > (define < > < >) (<qq D> + (define (< > <def >) < >). <qq D>) <qq D> < D + 1> < qq D> (begin < >*) <def > < >* < >*. < > < > #(<qq D>*) (define-syntax < > < >) < D>,<qq D 1> (unquote <qq D 1>) <qq D> <qq D> 7.2. < D> < D>,@<qq D 1> Scheme (unquote-splicing <qq D 1>) < > < qq D> [29] : < D> < D>... < D> < D> s k s k (1 ) #s s s t s t s k s k t a, b McCarthy if t then a else b < > ρ[x/i] i x ρ (syntax-rules (< >*) < >*) x in D D x < > (< > < >) x D D x < > < > ( ) (< >*) (< > +. < >) (< >* < > < >) #(< >*) #(< >* < > < >) < > < > > < > < > < > < > < > (< >*) permute unpermute ( ) (< > +. < >) #(< >*) < > < > < > new < > < > : new σ L σ (newσ L) < > < > 2 = false. < > <... > < > <...> K K P P < > < >* E[[((lambda (I*) P ) <undefined>... )]]

40 40 Revised 5 Scheme I* P E[[I] = λρκ. hold (lookup ρ I) P P (single(λɛ. ɛ = undefined <undefined> undefined ( ) E wrong, send ɛ κ)) (semantic function) E[[(E 0 E*)]] = λρκ. E*(permute( E 0 E*)) ρ (λɛ*. ((λɛ*. applicate (ɛ* 1) (ɛ* 1) κ) K Con (constants), (unpermute ɛ*))) I Ide (identifiers) E[[(lambda (I*) Γ* E 0 )]] = E Exp (expressions) λρκ. λσ. Γ Com = Exp (commands) new σ L send ( new σ L, λɛ*κ. #ɛ* = #I* tievals(λα*. (λρ. C[[Γ*]ρ (E[[E 0 ]]ρ κ )) (extends ρ I* α*)) Exp K I (E 0 E*) (lambda (I*) Γ* E 0 ) (lambda (I*. I) Γ* E 0 ) (lambda I Γ* E 0 ) (if E 0 E 1 E 2 ) (if E 0 E 1 ) (set! I E) E[[(lambda (I*. I) Γ* E 0)]] = λρκ. λσ. new σ L α L (locations) send ( new σ L, ν N λɛ*κ. #ɛ* #I* T = {false, true} tievalsrest Q (λα*. (λρ. C[[Γ*]ρ (E[[E 0 ]]ρ κ )) (extends ρ (I* I ) α*)) H ɛ* R (#I*), E p = L L T wrong in E) E v = L* T κ E s = L* T (update (new σ L) unspecified σ), M = {false, true, null, undefined, unspecified} wrong σ (miscellaneous) φ F = L (E* K C) E[[(lambda I Γ* E 0 )]] = E[[(lambda (. I) Γ* E 0 )]] ɛ E = Q + H + R + E p + E v + E s + M + F E[[(if E 0 E 1 E 2)]] = λρκ. E[[E 0 ]] ρ (single (λɛ. truish ɛ E[[E 1 ]]ρκ, σ S = L (E T) (stores) E[[E 2]]ρκ)) ρ U = Ide L E[[(if E 0 E 1 )]] = θ C = S A λρκ. E[[E 0]] ρ (single (λɛ. truish ɛ E[[E 1]]ρκ, κ K = E* C send unspecified κ)) A (answers) undefined ( ) X unspecified ( ) K : Con E E : Exp U K C E* : Exp* U K C C : Com* U C C K E[[K]] = λρκ. send (K[[K]]) κ ɛ*, wrong in E) κ (update (new σ L) unspecified σ), wrong σ E[[(set! I E)]] = λρκ. E[[E]] ρ (single(λɛ. assign (lookup ρ I) ɛ (send unspecified κ))) E*[[ ]] = λρκ. κ E*[[E 0 E*]] = λρκ. E[[E 0]] ρ (single(λɛ 0. E*[[E*]] ρ (λɛ*. κ ( ɛ 0 ɛ*)))) C[[ ]] = λρθ. θ C[[Γ 0 Γ*]] = λρθ. E[[Γ 0 ]] ρ (λɛ*. C[[Γ*]]ρθ)

41 lookup : U Ide L lookup = λρi. ρi extends : U Ide* L* U extends = λρi*α*. #I* = 0 ρ, extends (ρ[(α* 1)/(I* 1)]) (I* 1) (α* 1) wrong : X C send : E K C send = λɛκ. κ ɛ [ ] single : (E C) K single = λψɛ*. #ɛ* = 1 ψ(ɛ* 1), wrong new : S (L + {error}) hold : L K C hold = λακσ. send (σα 1)κσ assign : L E C C assign = λαɛθσ. θ(update αɛσ) update : L E S S update = λαɛσ. σ[ ɛ, true /α] [ ] tievals : (L* C) E* C tievals = λψɛ*σ. #ɛ* = 0 ψ σ, new σ L tievals (λα*. ψ( new σ L α*)) (ɛ* 1) (update(new σ L)(ɛ* 1)σ), wrong σ tievalsrest : (L* C) E* N C tievalsrest = λψɛ*ν. list (dropfirst ɛ*ν) (single(λɛ. tievals ψ ((takefirst ɛ*ν) ɛ ))) dropfirst = λln. n = 0 l, dropfirst (l 1)(n 1) takefirst = λln. n = 0, l 1 (takefirst (l 1)(n 1)) truish : E T truish = λɛ. ɛ = false false, true permute : Exp* Exp* unpermute : E* E* [ ] [permute ] applicate : E E* K C applicate = λɛɛ*κ. ɛ F (ɛ F 2)ɛ*κ, wrong onearg : (E K C) (E* K C) onearg = λζɛ*κ. #ɛ* = 1 ζ(ɛ* 1)κ, wrong twoarg : (E E K C) (E* K C) twoarg = λζɛ*κ. #ɛ* = 2 ζ(ɛ* 1)(ɛ* 2)κ, wrong list : E* K C list = λɛ*κ. #ɛ* = 0 send null κ, list (ɛ* 1)(single(λɛ. cons ɛ* 1, ɛ κ)) cons : E* K C cons = twoarg (λɛ 1ɛ 2κσ. new σ L (λσ. new σ L send ( new σ L, new σ L, true in E) κ (update(new σ L)ɛ 2σ ), wrong σ ) (update(new σ L)ɛ 1σ), wrong σ) less : E* K C less = twoarg (λɛ 1 ɛ 2 κ. (ɛ 1 R ɛ 2 R) send (ɛ 1 R < ɛ 2 R true, false)κ, wrong < ) add : E* K C add = twoarg (λɛ 1ɛ 2κ. (ɛ 1 R ɛ 2 R) send ((ɛ 1 R + ɛ 2 R) in E)κ, wrong + ) car : E* K C car = onearg (λɛκ. ɛ E p hold (ɛ E p 1)κ, wrong car ) cdr : E* K C [car ] setcar : E* K C setcar = twoarg (λɛ 1ɛ 2κ. ɛ 1 E p (ɛ 1 E p 3) assign (ɛ 1 E p 1) ɛ 2 (send unspecified κ), wrong set-car!, wrong set-car! ) eqv : E* K C eqv = twoarg (λɛ 1ɛ 2κ. (ɛ 1 M ɛ 2 M) send (ɛ 1 M = ɛ 2 M true, false)κ, (ɛ 1 Q ɛ 2 Q) send (ɛ 1 Q = ɛ 2 Q true, false)κ, (ɛ 1 H ɛ 2 H) send (ɛ 1 H = ɛ 2 H true, false)κ, (ɛ 1 R ɛ 2 R) send (ɛ 1 R = ɛ 2 R true, false)κ, (ɛ 1 E p ɛ 2 E p ) send ((λp 1 p 2. ((p 1 1) = (p 2 1) (p 1 2) = (p 2 2)) true, false) (ɛ 1 E p) (ɛ 2 E p )) κ,

42 42 Revised 5 Scheme (ɛ 1 E v ɛ 2 E v )..., (ɛ 1 E s ɛ 2 E s )..., (ɛ 1 F ɛ 2 F) send ((ɛ 1 F 1) = (ɛ 2 F 1) true, false) κ, send false κ) apply : E* K C apply = twoarg (λɛ 1 ɛ 2 κ. ɛ 1 F valueslist ɛ 2 (λɛ*. applicate ɛ 1 ɛ*κ), wrong apply ) valueslist : E* K C valueslist = onearg (λɛκ. ɛ E p cdr ɛ (λɛ*. valueslist ɛ* (λɛ*. car ɛ (single(λɛ. κ( ɛ ɛ*))))), ɛ = null κ, wrong values-list ) cwcc : E* K C [call-with-current-continuation] cwcc = onearg (λɛκ. ɛ F (λσ. new σ L applicate ɛ new σ L, λɛ*κ. κɛ* in E κ (update (new σ L) unspecified σ), wrong σ), wrong ) values : E* K C values = λɛ*κ. κɛ* cwv : E* K C [call-with-values] cwv = twoarg (λɛ 1ɛ 2κ. applicate ɛ 1 (λɛ*. applicate ɛ 2 ɛ*)) ((cond (test) clause1 clause2...) (let ((temp test)) (if temp temp (cond clause1 clause2...)))) ((cond (test result1 result2...)) (if test (begin result1 result2...))) ((cond (test result1 result2...) clause1 clause2...) (if test (begin result1 result2...) (cond clause1 clause2...))))) (define-syntax case (syntax-rules (else) ((case (key...) clauses...) (let ((atom-key (key...))) (case atom-key clauses...))) ((case key (else result1 result2...)) (begin result1 result2...)) ((case key ((atoms...) result1 result2...)) (if (memv key (atoms...)) (begin result1 result2...))) ((case key ((atoms...) result1 result2...) clause clauses...) (if (memv key (atoms...)) (begin result1 result2...) (case key clause clauses...))))) (define-syntax and (syntax-rules () ((and) #t) ((and test) test) ((and test1 test2...) (if test1 (and test2...) #f)))) 7.3. (define-syntax or (syntax-rules () ( lambda if, ((or) #f) set!) delay ((or test) test) 6.4 (define-syntax cond (syntax-rules (else =>) ((cond (else result1 result2...)) (begin result1 result2...)) ((cond (test => result)) (let ((temp test)) (if temp (result temp)))) ((cond (test => result) clause1 clause2...) (let ((temp test)) (if temp (result temp) (cond clause1 clause2...)))) ((cond (test)) test) ((or test1 test2...) (let ((x test1)) (if x x (or test2...)))))) (define-syntax let (syntax-rules () ((let ((name val)...) body1 body2...) ((lambda (name...) body1 body2...) val...)) ((let tag ((name val)...) body1 body2...) ((letrec ((tag (lambda (name...) body1 body2...))) tag) val...))))

43 (define-syntax let* (syntax-rules () ((let* () body1 body2...) (let () body1 body2...)) ((let* ((name1 val1) (name2 val2)...) body1 body2...) (let ((name1 val1)) (let* ((name2 val2)...) body1 body2...))))) (define-syntax letrec (syntax-rules () ((letrec ((var1 init1)...) body...) (letrec "generate temp names" (var1...) () ((var1 init1)...) body...)) ((letrec "generate temp names" () (temp1...) ((var1 init1)...) body...) (let ((var1 <undefined>)...) (let ((temp1 init1)...) (set! var1 temp1)... body...))) ((letrec "generate temp names" (x y...) (temp...) ((var1 init1)...) body...) (letrec "generate temp names" (y...) (newtemp temp...) ((var1 init1)...) body...)))) (define-syntax begin (syntax-rules () ((begin exp) exp) ((begin exp1 exp2...) (let ((x exp1)) (begin exp2...))))) do letrec (if #f #f) letrec (define-syntax do ( Scheme (syntax-rules () ) <undefined> ((do ((var init step...)...) (test expr...) command...) (letrec ((loop (lambda (var...) (if test (begin (if #f #f) expr...) (begin command... (loop (do "step" var step...)...)))))) (loop init...))) ((do "step" x) x) ((do "step" x y) y))) (define-syntax begin (syntax-rules () ((begin exp...) ((lambda () exp...))))) begin begin

44 44 Revised 5 Scheme integrate-system y k = f k (y 1, y 2,..., y n ), k = 1,..., n Revised 4 report [6] Scheme Runge-Kutta system-derivative ( Scheme IEEE [13] y 1,..., y n ) : ( y 1,..., y n) initial-state h integrate-system (essential) (inessential) (define integrate-system (lambda (system-derivative initial-state h) (let ((next (runge-kutta-4 system-derivative h))) (letrec ((states load with-input-from-file with-outputto-file transcript-on transcript-off (delay (map-streams next (cons initial-state interaction-environment states))))) - / IEEE states)))) runge-kutta-4 f runge-kutta-4 (define runge-kutta-4 (lambda (f h) (let ((*h (scale-vector h)) (*2 (scale-vector 2)) (*1/2 (scale-vector (/ 1 2))) (*1/6 (scale-vector (/ 1 6)))) (lambda (y) syntax-rules ;; y is a system state (let* ((k0 (*h (f y))) ( multiple-value return) (k1 (*h (f (add-vectors y (*1/2 k0))))) eval dynamic-wind (k2 (*h (f (add-vectors y (*1/2 k1))))) (k3 (*h (f (add-vectors y k2))))) (add-vectors y (*1/6 (add-vectors k0 (*2 (*2 k2) k3)))))))) (define elementwise (lambda (f) (lambda vectors (generate-vector (vector-length (car vectors)) the Internet Scheme Repository Scheme (lambda (i) (apply f Scheme (map (lambda (v) (vector-ref v i)) vectors))))))) (define generate-vector (lambda (size proc) (let ((ans (make-vector size))) (letrec ((loop

45 (lambda (i) (cond ((= i size) ans) (else (vector-set! ans i (proc i)) (loop (+ i 1))))))) (loop 0))))) (define add-vectors (elementwise +)) (define scale-vector (lambda (s) (elementwise (lambda (x) (* x s))))) (define map-streams (lambda (f s) (cons (f (head s)) (delay (map-streams f (tail s)))))) 45 [4] William Clinger, editor. The revised revised report on Scheme, or an uncommon Lisp. MIT Artificial car Intelligence Memo 848, August Also published cdr as Computer Science Department Technical Report 174, Indiana University, June C dv C dt = i L v C R L di L dt = v C (define damped-oscillator (lambda (R L C) (lambda (state) (let ((Vc (vector-ref state 0)) (Il (vector-ref state 1))) (vector (- 0 (+ (/ Vc (* R C)) (/ Il C))) (/ Vc L)))))) (define the-states (integrate-system (damped-oscillator ) #(1 0).01)) [1] Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs, second edition. MIT Press, Cambridge, [2] Alan Bawden and Jonathan Rees. Syntactic closures. In Proceedings of the 1988 ACM Symposium on Lisp and Functional Programming, pages [3] Robert G. Burger and R. Kent Dybvig. Printing map-streams map : ( floating-point numbers quickly and accurately. In ) ( ) Proceedings of the ACM SIGPLAN 96 Conference on Programming Language Design and Implementation, pages (define head car) (define tail [5] William Clinger. How to read floating point numbers (lambda (stream) (force (cdr stream)))) accurately. In Proceedings of the ACM SIGPLAN 90 Conference on Programming Language Design and Implementation, pages Proceedings published as SIGPLAN Notices 25(6), June [6] William Clinger and Jonathan Rees, editors. The revised 4 report on the algorithmic language Scheme. In ACM Lisp Pointers 4(3), pages 1 55, [7] William Clinger and Jonathan Rees. Macros that integrate-system work. In Proceedings of the 1991 ACM Conference on Principles of Programming Languages, pages [8] William Clinger. Proper Tail Recursion and Space Efficiency. To appear in Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, June [9] R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation 5(4): , [10] Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes. Scheme 311 version 4 reference manual. Indiana University Computer Science Technical Report 137, February Superseded by [11]. [11] D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand. Scheme 84 interim reference manual. Indiana University Computer Science Technical Report 153, January 1985.

46 46 Revised 5 Scheme [12] IEEE Standard IEEE Standard for Binary Floating-Point Arithmetic. IEEE, New York, [13] IEEE Standard IEEE Standard for the Scheme Programming Language. IEEE, New York, [14] Eugene E. Kohlbecker Jr. Syntactic Extensions in the Programming Language Lisp. PhD thesis, Indiana University, August [15] Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. In Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, pages [16] Peter Landin. A correspondence between Algol 60 and Church s lambda notation: Part I. Communications of the ACM 8(2):89 101, February [17] MIT Department of Electrical Engineering and Computer Science. Scheme manual, seventh edition. September [25] Guy Lewis Steele Jr. and Gerald Jay Sussman. The revised report on Scheme, a dialect of Lisp. MIT Artificial Intelligence Memo 452, January [26] Guy Lewis Steele Jr. Rabbit: a compiler for Scheme. MIT Artificial Intelligence Laboratory Technical Report 474, May [27] Guy Lewis Steele Jr. Common Lisp: The Language, second edition. Digital Press, Burlington MA, [28] Gerald Jay Sussman and Guy Lewis Steele Jr. Scheme: an interpreter for extended lambda calculus. MIT Artificial Intelligence Memo 349, December [29] Joseph E. Stoy. Denotational Semantics: The Scott- Strachey Approach to Programming Language Theory. MIT Press, Cambridge, [30] Texas Instruments, Inc. TI Scheme Language Reference Manual. Preliminary version 1.0, November [18] Peter Naur et al. Revised report on the algorithmic language Algol 60. Communications of the ACM 6(1):1 17, January [19] Paul Penfield, Jr. Principal values and branch cuts in complex APL. In APL 81 Conference Proceedings, pages ACM SIGAPL, San Francisco, September Proceedings published as APL Quote Quad 12(1), ACM, September [20] Kent M. Pitman. The revised MacLisp manual (Saturday evening edition). MIT Laboratory for Computer Science Technical Report 295, May [21] Jonathan A. Rees and Norman I. Adams IV. T: A dialect of Lisp or, lambda: The ultimate software tool. In Conference Record of the 1982 ACM Symposium on Lisp and Functional Programming, pages [22] Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan. The T manual, fourth edition. Yale University Computer Science Department, January [23] Jonathan Rees and William Clinger, editors. The revised 3 report on the algorithmic language Scheme. In ACM SIGPLAN Notices 21(12), pages 37 79, December [24] John Reynolds. Definitional interpreters for higher order programming languages. In ACM Conference Proceedings, pages ACM, 1972.