Scheme 5 v RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES () H. ABELSON R. K. DYBVIG C. T. HAYNES G. J. ROZAS N. I. ADAMS IV D. P. FRIEDMAN

Transcription

1 Scheme 5 v (FP) Guy Lewis Steele David Madore Scheme R 5 RS Scheme wangyg@contextfree.net Scheme 9 R 5 RS 1999 Hisao Suzuki ( euske/doc/r5rs-ja/index.html) 2000 Dai Inukai ( iwao/scheme/r5rsj/html/r5rsj toc.html) v v v v v v0.9.0

2 Scheme 5 v RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES () 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 Lisp Guy Lewis Steele Jr. Gerald Jay Sussman Scheme Scheme Scheme Scheme Scheme / 7 BNF Scheme Scheme Scheme

3 3 Scheme Scheme lambda Lisp Scheme lambda Scheme goto Scheme (Escape ) Scheme Common Lisp Scheme (Hygienic macro) Miller Jim Philbin John Ramsdell Mike Shaff Jonathan Shapiro Julie Sussman Perry Wagle Daniel Weise Henry Wu Ozan Yigit Carol Fessenden Daniel Friedman Christopher Haynes Scheme Texas Instruments TI Scheme [30] MIT Scheme[17] T[22] Scheme 84[11] Common Lisp[27] Algol 60[18] Betty Dexter TEX Donald Knuth Betty MIT Indiana Oregon NEC (ARPA) N C-0505 MIT (NSF) NCS NCS Indiana Scheme 1975 [28] 1978 [25] MIT [26] Scheme MIT Yale Indiana [21, 17, 10] Scheme 1984 [1] Scheme Scheme Scheme [4] 1985 MIT Indiana 1986 [23] 1988 [6] Xerox PARC Scheme Scheme Alan Bawden Michael Blair George Carrette Andy Cromarty Pavel Curtis Jeff Dalton Olivier Danvy Ken Dickey Bruce Duba Marc Feeley Andy Freeman Richard Gabriel Yekta Gürsel Ken Haase Robert Hieb Paul Hudak Morry Katz Chris Lindblad Mark Meyer Jim

4 4 Scheme 5 SCHEME 1. Scheme 1.1. Scheme Scheme Algol Scheme Scheme APL Snobol Lisp Algol 60 Pascal C Scheme (Continuation) (Extent) Scheme Scheme APL Lisp Scheme 3.5 Scheme Common Lisp ML Scheme Scheme (Non-local exits) (Backtracking) (Coroutine) 6.4 Scheme ML C APL Haskell (Lazy-evaluation) Algol 60 (Call-by-name) Haskell Algol 60 Scheme Scheme Scheme Scheme Common Lisp 1.2. Lisp Scheme Scheme Scheme Scheme eval Scheme read read Scheme Scheme (optional) Scheme Scheme Scheme Scheme (library) Scheme Scheme Scheme Scheme Scheme Scheme Scheme Scheme (Unspecified) Scheme

5 template template category qualifier category qualifier library optional category syntax (template) expression variable expression thing 1... thing thing 1 thing 2... thing category (vector-ref vector k) vector-ref vector k (make-vector k) (make-vector k fill) make-vector 3.2 vector-ref vector-ref obj list, list 1,... list j, z, z 1,... z j,... x, x 1,... x j,... y, y 1,... y j,... q, q 1,... q j,... n, n 1,... n j,... k, k 1,... k j, = (* 5 8) = 40 (* 5 8) 40 (* 5 8) ? (Predicate) 3.4! (Mutation ) -> list->vector 2. Scheme Scheme 7.1 Scheme Foo FOO #x1ab #X1ab 2.1. Scheme Scheme Scheme lambda q list->vector soup + V17a <=? a34ktmns the-word-recursion-has-many-meanings! $ % & * + -. / : < = ^ _ ~ Scheme

6 6 Scheme symbol (Whitespace) Scheme Token ) (;) Scheme ;;; The FACT computes the factorial ;;; of a non-negative integer. (define fact (lambda (n) (if (= n 0) 1 ;Base case: return 1 (* n (fact (- n 1)))))) Pair ( ) ` " \ [ ] { } # #t #f #\ #( ) #e #i #b #o #d #x lambda lambda let let* letrec do Scheme Algol Pascal Common Lisp Lisp lambda lambda boolean? symbol? char? vector?? pair? number? string? port?

7 3. 7 (boolean) (pair) (symbol) (number) (char character) (string) (vector) (port) () Scheme #f #f Scheme #f 3.3. Scheme Lisp (8 13) 28 #e #x1c ( ) (8. (13. ())) Scheme quote read write / (+ 2 6) Scheme Scheme string-set! car vector-ref string-ref eqv? 6.1 symbol->string 3.5. Scheme Scheme call-with-current-continuation [8] Steele Sussman Scheme Scheme (Actor) Steele Sussman (Tail context) lambda lambda tail expression (lambda formals definition * expression * tail expression )

8 8 Scheme 5 tail expression 7 expression tail expression (if expression tail expression tail expression ) (if expression tail expression ) (cond cond clause + ) (cond cond clause * (else tail sequence )) (case expression case clause + ) (case expression case clause * (else tail sequence )) (and expression * tail expression ) (or expression * tail expression ) (let ( binding spec *) tail body ) (let variable ( binding spec *) tail body ) (let* ( binding spec *) tail body ) (letrec ( binding spec *) tail body ) (let-syntax ( syntax spec *) tail body ) (letrec-syntax ( syntax spec *) tail body ) (begin tail sequence ) (do ( iteration spec *) ( test tail sequence ) expression *) cond clause ( test tail sequence ) case clause (( datum *) tail sequence ) tail body definition * tail sequence tail sequence expression * tail expression cond ( expression 1 => expression 2 ), expression 2 expression 2 apply call-with-current-continuation call-with-values eval eval f g h x (lambda () (if (g) (let ((x (h))) x) (and (g) (f)))) Scheme h let h h let 4. quasiquote variable syntax 3.1 (define x 28) x = (quote datum ) datum constant syntax syntax syntax (quote datum ) datum datum Scheme 3.3 Scheme (quote a) = a (quote #(a b c)) = #(a b c) (quote (+ 1 2)) = (+ 1 2) (quote datum ) datum

9 4. 9 a = a #(a b c) = #(a b c) () = () (+ 1 2) = (+ 1 2) (quote a) = (quote a) a = (quote a) "abc" = "abc" "abc" = "abc" = = #t = #t #t = #t 3.4 set-car! string-set! ( operator operand 1... ) syntax Scheme (+ 3 4) = 7 ((if #f + *) 3 4) = 12 + * lambda values values apply (Combinations) Lisp Scheme Lisp () Scheme () (lambda formals body ) syntax formals body lambda lambda lambda lambda body body (lambda (x) (+ x x)) = ((lambda (x) (+ x x)) 4) = 8 (define reverse-subtract (lambda (x y) (- y x))) (reverse-subtract 7 10) = 3 (define add4 (let ((x 4)) (lambda (y) (+ x y)))) (add4 6) = 10 formals ( variable 1... ): variable : variable ( variable 1... variable n. variable n+1 ): n n formals variable ((lambda x x) ) = ( ) ((lambda (x y. z) z) ) = (5 6) lambda eqv? eq? 6.1

10 10 Scheme (if test consequent alternate ) (if test consequent ) syntax syntax test consequent alternate if test consequent alternate test alternate (if (> 3 2) yes no) = yes (if (> 2 3) yes no) = no (if (> 3 2) (- 3 2) (+ 3 2)) = (set! variable expression ) syntax expression variable variable set! set! (define x 2) (+ x 1) = 3 (set! x 4) = (+ x 1) = (cond clause 1 clause 2... ) clause ( test expression 1... ) library syntax test clause ( test => expression ) clause else (else expression 1 expression 2... ). cond clause test test clause expression clause expression cond clause test expression test clause => expression expression test cond test else else expression expression (cond ((> 3 2) greater) ((< 3 2) less)) = greater (cond ((> 3 3) greater) ((< 3 3) less) (else equal)) = equal (cond ((assv b ((a 1) (b 2))) => cadr) (else #f)) = 2 (case key clause 1 clause 2... ) library syntax key clause (( datum 1... ) expression 1 expression 2... ), datum datum clause else (else expression 1 expression 2... ). case key datum key eqv? 6.1 datum clause clause case key datum else case case (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

11 4. 11 (and test 1... ) library syntax test #t (and (= 2 2) (> 2 1)) = #t (and (= 2 2) (< 2 1)) = #f (and 1 2 c (f g)) = (f g) (and) = #t (or test 1... ) library syntax test #f (or (= 2 2) (> 2 1)) = #t (or (= 2 2) (< 2 1)) = #t (or #f #f #f) = #f (or (memq b (a b c)) (/ 3 0)) = (b c) let let* letrec Scheme Algol 60 let let* letrec (Mutually recursive) (let bindings body ) bindings (( variable 1 init 1 )... ), library syntax init body variable init variable init body body variable body (let ((x 2) (y 3)) (* x y)) = 6 (let ((x 2) (y 3)) (let ((x 7) (z (+ x y))) (* z x))) = 35 let (let* bindings body ) bindings (( variable 1 init 1 )... ), body library syntax let* let ( variable init ) let* (let ((x 2) (y 3)) (let* ((x 7) (z (+ x y))) (* z x))) = 70 (letrec bindings body ) bindings (( variable 1 init 1 )... ), library syntax body variable variable init init variable body body variable letrec (letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) (odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))) (even? 88)) = #t letrec variable init Scheme letrec init lambda

12 12 Scheme (begin expression 1 expression 2... ) library syntax expression expression (Side effect) (define x 0) (begin (set! x 5) (+ x 1)) = 6 (begin (display "4 plus 1 equals ") (display (+ 4 1))) = 4 plus 1 equals (do (( variable 1 init 1 step 1 )... ) ( test expression... ) command... ) library syntax do expression do init variable init variable test command step variable step variable test expression expression expression do variable init do do variable step ( variable init ) ( variable init variable ) (do ((vec (make-vector 5)) (i 0 (+ i 1))) ((= i 5) vec) (vector-set! vec i i)) = #( ) (let ((x ( ))) (do ((x x (cdr x)) (sum 0 (+ sum (car x)))) ((null? x) sum))) = 25 (let variable bindings body ) library syntax let let do let body variable body variable body (let loop ((numbers ( )) (nonneg ()) (neg ())) (cond ((null? numbers) (list nonneg neg)) ((>= (car numbers) 0) (loop (cdr numbers) (cons (car numbers) nonneg) neg)) ((< (car numbers) 0) (loop (cdr numbers) nonneg (cons (car numbers) neg))))) = ((6 1 3) (-5-2)) (delay expression ) library syntax delay force (Call by need) (delay expression ) (Promise) force expression expression force 6.4 delay (quasiquote qq template ) ` qq template syntax syntax (Backquote) (Quasiquote) qq template ` qq template qq template qq template qq template `(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) `(( foo,(- 10 3)),@(cdr (c)).,(car (cons)))

13 4. 13 = ((foo 7). cons) `#(10 5,(sqrt 4),@(map sqrt (16 9)) 8) = #( ) `(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 template (quasiquote qq template ), expression (unquote expression ),@ expression (unquote-splicing expression ) write Scheme (quasiquote (list (unquote (+ 1 2)) 4)) = (list 3 4) (quasiquote (list (unquote (+ 1 2)) 4)) = `(list,(+ 1 2) 4) (quasiquote (list (unquote (+ 1 2)) 4)) qq template quasiquote unquote unquote-splicing 4.3. Scheme (Macros) ( keyword datum...) keyword datum (Use) (Transformer) Scheme [14, 15, 2, 7, 9] define Let-syntax letrec-syntax let letrec 5.3 (let-syntax bindings body ) bindings (( keyword transformer spec )... ) syntax keyword transformer spec syntax-rules body keyword let-syntax keyword body keyword body (let-syntax ((when (syntax-rules () ((when test stmt1 stmt2...) (if test (begin stmt1 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 (letrec-syntax bindings body ) let-syntax syntax letrec-syntax keyword body keyword bindings body letrec-syntax (letrec-syntax ((my-or (syntax-rules () ((my-or) #f)

14 14 Scheme 5 ((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 temp) (if y) y))) = transformer spec (syntax-rules literals syntax rule... ) literals syntax rule ( pattern template ) syntax rule pattern pattern pattern ( pattern...) ( pattern pattern.... pattern ) ( pattern... pattern ellipsis ) #( pattern...) #( pattern... pattern ellipsis ) template ( element...) ( element element.... template ) #( element...) element ellipsis template ellipsis... syntax-rules syntax-rules syntax rule syntax rule literals... syntax rule pattern syntax rule (Literal identifier) let-syntax letrec-syntax literals (Subform)... (Subpattern) literals F P P P F P (P 1... P n ) F n P 1 P n P (P 1 P 2... P n. P n+1 ) F n P 1 P n F n cdr P n+1 P (P 1... P n P n+1 ellipsis ) ellipsis... F n F n P 1 P n F P n+1 P #(P 1... P n ) F n P 1 P n P #(P 1... P n P n+1 ellipsis ) ellipsis... F n F n P 1 P n F P n+1 P (Datum) equal? F P syntax rule (Subtemplate)

15 syntax-rules 7.3 let cond (let ((=> #f)) (cond (#t => ok))) = ok cond => => => (let ((=> #f)) (if #t (begin => ok))) (let ((=> #f)) (let ((temp #t)) (if temp ( ok temp)))) Scheme 4 Scheme Scheme (begin form 1... ) begin 5.2. program body (define variable expression ) (define ( variable formals ) body ) formals lambda (define variable (lambda ( formals ) body )) (define ( variable. formal ) body ) formal (define variable (lambda formal body )) variable (define variable expression ) (set! variable expression ) variable variable set! (define add3 (lambda (x) (+ x 3))) (add3 3) = 6 (define first car) (first (1 2)) = 1 Scheme body lambda let let* letrec let-syntax letrec-syntax body body body variable body (let ((x 5)) (define foo (lambda (y) (bar x y))) (define bar (lambda (a b) (+ (* a b) a))) (foo (+ x 3))) = 45 body letrec let

16 16 Scheme 5 (let ((x 5)) (letrec ((foo (lambda (y) (bar x y))) (bar (lambda (a b) (+ (* a b) a)))) (foo (+ x 3)))) letrec body variable expression (begin definition 1... ) begin 5.3. program (define-syntax keyword transformer spec ) keyword transformer spec syntax-rules keyword define-syntax (define define 3) (begin (define begin list)) (let-syntax ((foo (syntax-rules () ((foo (proc args...) body...) (define proc (lambda (args...) body...)))))) (let ((x 3)) (foo (plus x y) (+ x y)) (define foo x) (plus foo x))) 6. Scheme Scheme abs Scheme 6.1. #t #f eq? equal? eqv? eq? (eqv? obj 1 obj 2 ) eqv? obj 1 obj 2 eqv? #t eqv? Scheme eqv? #t obj 1 obj 2 #t #f obj 1 obj 2 (string=? (symbol->string obj1) (symbol->string obj2)) = #t obj 1 obj (Uninterned symbol) eqv? obj 1 obj 2 = 6.2 obj 1 obj 2 char=? obj 1 obj 2 obj 1 obj obj 1 obj 2 (Location tag) eqv? #f obj 1 obj obj 1 obj 2 #t #f obj 1 obj 2

17 6. 17 (string=? (symbol->string obj 1) (symbol->string obj 2)) = #f obj 1 obj 2 obj 1 obj 2 = #f obj 1 obj 2 char=? #f obj 1 obj 2 obj 1 obj 2 obj 1 obj 2 (eqv? a a) = #t (eqv? a b) = #f (eqv? 2 2) = #t (eqv? () ()) = #t (eqv? ) = #t (eqv? (cons 1 2) (cons 1 2))= #f (eqv? (lambda () 1) (lambda () 2)) = #f (eqv? #f nil) = #f (let ((p (lambda (x) x))) (eqv? p p)) = #t eqv? eqv? (eqv? "" "") = (eqv? #() #()) = (eqv? (lambda (x) x) (lambda (x) x)) = (eqv? (lambda (x) x) (lambda (y) y)) = eqv? gen-counter gen-loser (define gen-counter (lambda () (let ((n 0)) (lambda () (set! n (+ n 1)) n)))) (let ((g (gen-counter))) (eqv? g g)) = #t (eqv? (gen-counter) (gen-counter)) = #f (define gen-loser (lambda () (let ((n 0)) (lambda () (set! n (+ n 1)) 27)))) (let ((g (gen-loser))) (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)) = (letrec ((f (lambda () (if (eqv? f g) f both))) (g (lambda () (if (eqv? f g) g both)))) (eqv? f g)) = #f Scheme eqv? (eqv? (a) (a)) = (eqv? "a" "a") = (eqv? (b) (cdr (a b))) = (let ((x (a))) (eqv? x x)) = #t eqv? Scheme Scheme (Bit pattern) (eq? obj 1 obj 2 ) eq? eqv? eq? eqv? eq? eqv? eq? eqv? eq? eqv? (eq? a a) = #t (eq? (a) (a)) = (eq? (list a) (list a)) = #f (eq? "a" "a") = (eq? "" "") = (eq? () ()) = #t (eq? 2 2) = (eq? #\A #\A) = (eq? car car) = #t (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

18 18 Scheme 5 eqv? eq? eq? eqv? eq? eq? eqv? eq? eqv? (equal? obj 1 obj 2 ) library equal? equal? eqv? equal? equal? (equal? a a) = #t (equal? (a) (a)) = #t (equal? (a (b) c) (a (b) c)) = #t (equal? "abc" "abc") = #t (equal? 2 2) = #t (equal? (make-vector 5 a) (make-vector 5 a)) = #t (equal? (lambda (x) x) (lambda (y) y)) = 6.2. Lisp Common Lisp MacLisp [20] Common Lisp Scheme Scheme Scheme number complex real rational integer Scheme fixnum flonum (number) (complex) (real) (rational) (integer) Scheme Scheme number? complex? real? rational? integer? Scheme 3 Scheme Scheme Scheme Scheme inexact->exact Scheme Scheme Scheme Scheme

19 6. 19 Scheme length vector-length string-length + - * quotient remainder modulo max min abs numerator denominator gcd lcm floor ceiling truncate round rationalize expt Scheme / Scheme IEEE [12] Scheme sqrt 4 2 sqrt Scheme Scheme #b #o #d #x #e #i # s f d l short single double long short single long double e Scheme double Scheme F0 single L0 long (number? obj ) (complex? obj ) (real? obj ) (rational? obj ) (integer? obj ) #t #f z (zero? (imag-part z)) (real? z) x (= x (round x)) (integer? x) (complex? 3+4i) = #t (complex? 3) = #t

20 20 Scheme 5 (real? 3) = #t (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 rational? real? complex? number? (exact? z) (inexact? z) Scheme (= z 1 z 2 z 3... ) (< x 1 x 2 x 3... ) (> x 1 x 2 x 3... ) (<= x 1 x 2 x 3... ) (>= x 1 x 2 x 3... ) #t Lisp = zero? min max (+ z 1... ) (* z 1... ) (+ 3 4) = 7 (+ 3) = 3 (+) = 0 (* 4) = 4 (*) = 1 (- z 1 z 2 ) (- z) (- z 1 z 2... ) optional (/ z 1 z 2 ) (/ z) (/ z 1 z 2... ) optional (- 3 4) = -1 ( ) = -6 (- 3) = -3 (/ 3 4 5) = 3/20 (/ 3) = 1/3 (abs x) abs (abs -7) = 7 library (zero? z) (positive? x) (negative? x) (odd? n) (even? n) library library library library library #t #f (max x 1 x 2... ) library (min x 1 x 2... ) library (max 3 4) = 4 ; (max 3.9 4) = 4.0 ; (quotient n 1 n 2 ) (remainder n 1 n 2 ) (modulo n 1 n 2 ) n 2 n 1 /n 2 (quotient n 1 n 2) = n 1/n 2 (remainder n 1 n 2) = 0 (modulo n 1 n 2) = 0 n 1 /n 2 (quotient n 1 n 2) = n q (remainder n 1 n 2) = n r (modulo n 1 n 2) = n m

21 6. 21 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 r n 1 n m n 2 n 1 n 2 n 2 0 (= n 1 (+ (* n 2 (quotient n 1 n 2)) (remainder n 1 n 2))) = #t (modulo 13 4) = 1 (remainder 13 4) = 1 (modulo -13 4) = 3 (remainder -13 4) = -1 (modulo 13-4) = -3 (remainder 13-4) = 1 round IEEE inexact->exact (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 (modulo -13-4) = -1 (remainder -13-4) = -1 (rationalize x y) library (remainder ) = -1.0 ; (gcd n 1... ) library (lcm n 1... ) library (gcd 32-36) = 4 (gcd) = 0 (lcm 32-36) = 288 (lcm ) = ; (lcm) = 1 (numerator q) (denominator q) 0 1 (numerator (/ 6 4)) = 3 (denominator (/ 6 4)) = 2 (denominator (exact->inexact (/ 6 4))) = 2.0 (floor x) (ceiling x) (truncate x) (round x) floor x ceiling x truncate x x round x x rationalize x y (Simplest) r 1 = p 1 /q 1 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 2/5 2/7 3/5 0 = 0/1 (rationalize (inexact->exact.3) 1/10) = 1/3 ; (rationalize.3 1/10) = #i1/3 ; (exp z) (log z) (sin z) (cos z) (tan z) (asin z) (acos z) (atan z) (atan y x) log z 10 asin acos atan (sin 1 )(cos 1 )(tan 1 ) atan (angle (make-rectangular x y)) log z π π log 0 log sin 1 z cos 1 z tan 1 z

22 22 Scheme 5 sin 1 z = i log(iz + 1 z 2 ) cos 1 z = π/2 sin 1 z tan 1 z = (log(1 + iz) log(1 iz))/(2i) [27] [19] (sqrt z) z (expt z 1 z 2 ) z 1 z 2 z 1 0 z 1 z 2 0 z z = z2 log z1 = e (make-rectangular x 1 x 2 ) (make-polar x 3 x 4 ) (real-part z) (imag-part z) (magnitude z) (angle z) x 1 x 2 x 3 x 4 z 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 π < x angle π n x angle = x 4 + 2πn magnitude abs abs magnitude (exact->inexact z) (inexact->exact z) exact->inexact z inexact->exact z (number->string z) (number->string z radix) radix radix 10 number->string (let ((number number) (radix radix)) (eqv? number (string->number (number->string number radix) radix))) z 10 [3, 5] number->string z z z 10 NaN (string->number string) (string->number string radix) string radix radix radix string "#o177" radix 10 string string->number #f (string->number "100") = 100 (string->number "100" 16) = 256 (string->number "1e2") = (string->number "15##") = Scheme string->number string string->number #f string string->number #f string string->number #f string # string->number #f string string->number #f

23 Scheme #t #f Scheme (if cond and or do) Scheme #f #f Scheme #t Lisp Scheme #f nil #t = #t #f = #f #f = #f (not obj ) obj not #t #f (not #t) = #f (not 3) = #f (not (list 3)) = #f (not #f) = #t (not ()) = #f (not (list)) = #f (not nil) = #f (boolean? obj ) library library obj #t #f boolean? #t #f (boolean? #f) = #t (boolean? 0) = #f (boolean? ()) = #f Pair Dotted pair car cdr cons car cdr car cdr car cdr set-car! set-cdr! cdr X X list X cdr list X car car cdr car cdr Scheme (c 1. c 2 ) c 1 car c 2 cdr (4. 5) car 4 cdr 5 (4. 5) () (a b c d e) (a. (b. (c. (d. (e. ()))))) (a b c. d) (a. (b. (c. d))) cdr set-cdr! (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 read datum ` datum, datum,@ datum quote quasiquote unquote unquote-splicing datum Scheme Scheme expression datum

24 24 Scheme read Scheme 3.3 (pair? obj ) obj pair? #t #f (pair? (a. b)) = #t (pair? (a b c)) = #t (pair? ()) = #f (pair? #(a b)) = #f (cons obj 1 obj 2 ) car obj 1 cdr obj 2 eqv? (cons a ()) = (a) (cons (a) (b c d)) = ((a) b c d) (cons "a" (b c)) = ("a" b c) (cons a 3) = (a. 3) (cons (a b) c) = ((a b). c) (car pair) pair car car (car (a b c)) = a (car ((a) b c d)) = (a) (car (1. 2)) = 1 (car ()) = (cdr pair) pair cdr cdr (cdr ((a) b c d)) = (b c d) (cdr (1. 2)) = 2 (cdr ()) = (set-car! pair obj ) obj pair car set-car! (define (f) (list not-a-constant-list)) (define (g) (constant-list)) (set-car! (f) 3) = (set-car! (g) 3) = (set-cdr! pair obj ) obj pair cdr set-cdr! (caar pair) (cadr pair).. (cdddar pair) (cddddr pair) library library.. library library car cdr caddr (define caddr (lambda (x) (car (cdr (cdr x))))). Scheme (null? obj ) obj #t #f (list? obj ) library library obj #t #f (list obj... ) (list? (a b c)) = #t (list? ()) = #t (list? (a. b)) = #f (let ((x (list a))) (set-cdr! x x) (list? x)) = #f (list a (+ 3 4) c) = (a 7 c) (list) = () (length list) list (length (a b c)) = 3 (length (a (b) (c d e))) = 3 (length ()) = 0 (append list... ) library library library list list (append (x) (y)) = (x y) (append (a) (b c d)) = (a b c d) (append (a (b)) ((c))) = (a (b) (c)) list (append (a b) (c. d)) = (a b c. d) (append () a) = a

25 6. 25 (reverse list) library list (reverse (a b c)) = (c b a) (reverse (a (b c) d (e (f)))) = ((e (f)) d (b c) a) (list-tail list k) library list k list k list-tail (define list-tail (lambda (x k) (if (zero? k) x (list-tail (cdr x) (- k 1))))) (list-ref list k) library list k (list-tail list k) car list k (list-ref (a b c d) 2) = c (list-ref (a b c d) (inexact->exact (round 1.8))) = c (memq obj list) (memv obj list) (member obj list) library library library list car obj list k list (list-tail list k) list obj #f obj list memq eq? memv eqv? member equal? (memq a (a b c)) = (a b c) (memq b (a b c)) = (b c) (memq a (b c d)) = #f (memq (list a) (b (a) c)) = #f (member (list a) (b (a) c)) = ((a) c) (memq 101 ( )) = (memv 101 ( )) = ( ) (assq obj alist) (assv obj alist) (assoc obj alist) library library library alistassociation list alist car obj alist car obj #f obj list car assq eq? assv eqv? assoc equal? (define e ((a 1) (b 2) (c 3))) (assq a e) = (a 1) (assq b e) = (b 2) (assq d e) = #f (assq (list a) (((a)) ((b)) ((c)))) = #f (assoc (list a) (((a)) ((b)) ((c)))) = ((a)) (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 eqv? Scheme Pascal Scheme read write eqv? string->symbol / Scheme (Slashification) / Scheme (Uninterned symbols) / (symbol? obj ) obj #t #f (symbol? foo) = #t (symbol? (car (a b))) = #t (symbol? "bar") = #f (symbol? nil) = #t (symbol? ()) = #f (symbol? #f) = #f (symbol->string symbol) symbol read

26 26 Scheme 5 Scheme string->symbol string->symbol string-set! Scheme (symbol->string flying-fish) = "flying-fish" (symbol->string Martin) = "martin" (symbol->string (string->symbol "Malvina")) = "Malvina" (string->symbol string) string Scheme symbol->string Scheme (eq? mississippi mississippi) = #t (string->symbol "mississippi") = "mississippi" (eq? bitblt (string->symbol "bitblt")) = #f (eq? JollyWog (string->symbol (symbol->string JollyWog))) = #t (string=? "K. Harper, M.D." (symbol->string (string->symbol "K. Harper, M.D."))) = #t #\ character #\ character name #\a ; #\A ; #\( ; #\ ; #\space ; #\newline ; #\ character #\ character name #\ character character character #\space #\space #\ -ci Case insensitive (char? obj ) obj #t #f (char=? char 1 char 2 ) (char<? char 1 char 2 ) (char>? char 1 char 2 ) (char<=? char 1 char 2 ) (char>=? char 1 char 2 ) (char<? #\A #\B) #t (char<? #\a #\b) #t (char<? #\0 #\9) #t (char-ci=? char 1 char 2 ) library (char-ci<? char 1 char 2 ) library (char-ci>? char 1 char 2 ) library (char-ci<=? char 1 char 2 ) library (char-ci>=? char 1 char 2 ) library char=? (char-ci=? #\A #\a) #t (char-alphabetic? char) (char-numeric? char) (char-whitespace? char) (char-upper-case? letter) (char-lower-case? letter) library library library library library #t #f ASCII 52 10

27 6. 27 (char->integer char) (integer->char n) char->integer char->integer integer->char char<=? <= (Order-preserving isomorphisms) (char<=? a b) = #t and (<= x y) = #t x y integer->char (<= (char->integer a) (char->integer b)) = #t (char<=? (integer->char x) (integer->char y)) = #t (char-upcase char) (char-downcase char) library library (char-ci=? char char 2 ) char 2 char char-upcase char-downcase (") (\) "The word \"recursion\" has many meanings." Scheme 0 1 string start end start end start end start end string -ci Case insensitive (string? obj ) obj #t #f (make-string k) (make-string k char) make-string k char char string (string char... ) (string-length string) string (string-ref string k) library k string string-ref string k (string-set! string k char) k string string-set! char string k (define (f) (make-string 3 #\*)) (define (g) "***") (string-set! (f) 0 #\?) = (string-set! (g) 0 #\?) = (string-set! (symbol->string immutable) 0 #\?) = (string=? string 1 string 2 ) library (string-ci=? string 1 string 2 ) library #t #f string-ci=? string=? (string<? string 1 string 2 ) library (string>? string 1 string 2 ) library (string<=? string 1 string 2 ) library (string>=? string 1 string 2 ) library (string-ci<? string 1 string 2 ) library (string-ci>? string 1 string 2 ) library (string-ci<=? string 1 string 2 ) library (string-ci>=? string 1 string 2 ) library string<? char<? Scheme string=? string-ci=?

28 28 Scheme 5 (substring string start end) library string start end 0 start end (string-length string). substring string start end (string-append string... ) library (string->list string) (list->string list) library library string->list list->string list list equal? string->list list-> string (string-copy string) string (string-fill! string char) library library char string #(obj... ) ( ) 2 "Anna" #(0 ( ) "Anna") #(0 ( ) "Anna") = #(0 ( ) "Anna") (vector? obj ) obj #t #f (make-vector k) (make-vector k fill) k fill (vector obj... ) library list (vector a b c) = #(a b c) (vector-length vector) vector (vector-ref vector k) k vector vector-ref vector k (vector-ref #( ) 5) = 8 (vector-ref #( ) (let ((i (round (* 2 (acos -1))))) (if (inexact? i) (inexact->exact i) i))) = 13 (vector-set! vector k obj ) k vector vector-set! obj vector k vector-set! (let ((vec (vector 0 ( ) "Anna"))) (vector-set! vec 1 ("Sue" "Sue")) vec) = #(0 ("Sue" "Sue") "Anna") (vector-set! #(0 1 2) 1 "doe") = ; (vector->list vector) (list->vector list) library library vector->list vector list->vector list

29 6. 29 (vector->list #(dah dah didah)) = (dah dah didah) (list->vector (dididit dah)) = #(dididit dah) (vector-fill! vector fill) library fill vector vector-fill! 6.4.? (? obj ) obj #t #f (? car) = #t (? car) = #f (? (lambda (x) (* x x))) = #t (? (lambda (x) (* x x))) = #f (call-with-current-continuation?) = #t (apply proc arg 1... args) proc args (append (list arg 1... ) args) proc (apply + (list 3 4)) = 7 (define compose (lambda (f g) (lambda args (f (apply g args))))) ((compose sqrt *) 12 75) = 30 (map proc list 1 list 2... ) library list proc list list map proc list proc list (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) (for-each proc list 1 list 2... ) library for-each map for-each proc map for-each proc list for-each (let ((v (make-vector 5))) (for-each (lambda (i) (vector-set! v i (* i i))) ( )) v) = #( ) (force promise) library promise delay (force (delay (+ 1 2))) = 3 (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) (define tail (lambda (stream) (force (cdr stream)))) (head (tail (tail a-stream))) = 2 force delay (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

30 30 Scheme 5 delay force force (define force (lambda (object) (object))) (delay expression ) (make-promise (lambda () expression )) (define-syntax delay (syntax-rules () ((delay expression) (make-promise (lambda () expression))))) 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)))))))) make-promise delay force force #t #f (eqv? (delay 1) 1) = (pair? (delay (cons 1 2))) = (Implicit forcing) cdr + (+ (delay (* 3 7)) 13) = 34 (call-with-current-continuation proc) proc call-with-current-continuation (Escape ) proc Scheme dynamic-wind before after call-with-current-continuation call-with-values call-with-values proc Scheme call-with-current-continuation call-with-current-continuation (call-with-current-continuation (lambda (exit) (for-each (lambda (x) (if (negative? x) (exit x))) ( )) #t)) = -3 (define list-length (lambda (obj) (call-with-current-continuation (lambda (return) (letrec ((r (lambda (obj) (cond ((null? obj) 0) ((pair? obj) (+ (r (cdr obj)) 1)) (else (return #f)))))) (r obj)))))) (list-length ( )) = 4 (list-length (a b. c)) = #f call-with-current-continuation call-with-current-continuation Scheme

31 6. 31 call-with-current-continuation Scheme exit return goto 1965 Peter Landin[16] J-operator John Reynolds[24] Scheme Sussman Steele catch Reynolds MacLisp Scheme catch 1982 call-with-current-continuation call/cc (values obj...) call-with-values values (define (values. things) (call-with-current-continuation (lambda (cont) (apply cont things)))) (call-with-values producer consumer) producer consumer consumer call-with-values (call-with-values (lambda () (values 4 5)) (lambda (a b) b)) = 5 (call-with-values * -) = -1 (dynamic-wind before thunk after) thunk before after call-with-current-continuation thunk (Dynamic extent) before thunk after Scheme call-with-current-continuation call-with-current-continuation thunk dynamic-wind dynamic-wind after dynamic-wind after thunk dynamic-wind dynamic-wind before dynamic-wind before dynamic-wind before dynamic-wind after after before after (let ((path ()) (c #f)) (let ((add (lambda (s) (set! path (cons s path))))) (dynamic-wind (lambda () (add connect)) (lambda () (add (call-with-current-continuation (lambda (c0) (set! c c0) talk1)))) (lambda () (add disconnect))) (if (< (length path) 4) (c talk2) (reverse path)))) 6.5. = (connect talk1 disconnect connect talk2 disconnect) (eval expression environment-specifier) expression expression Scheme

32 32 Scheme 5 environment-specifier Scheme eval eval null-environment scheme-report-environment (eval (* 7 3) (scheme-report-environment 5)) = 21 (let ((f (eval (lambda (f x) (f x x)) (null-environment 5)))) (f + 10)) = 20 (scheme-report-environment version) (null-environment version) version Scheme 5 5 scheme-report-environment Scheme null-environment Scheme version version 5 Scheme Scheme eval scheme-report-environment car scheme-report-environment (interaction-environment) optional Scheme Scheme Ports (Port) Scheme Scheme Scheme (call-with-input-file string proc) library (call-with-output-file string proc) library string proc call-with-input-file call-with-output-file proc proc proc proc Scheme Scheme call-with-current-continuation call-with-input-file call-with-output-file (input-port? obj ) (output-port? obj ) obj #t #f (current-input-port) (current-output-port) (with-input-from-file string thunk) optional (with-output-to-file string thunk) optional string thunk with-input-from-file with-output-to-file current-input-port current-output-port (read) (write obj ) thunk thunk with-input-from-file with-output-to-file thunk (open-input-file filename) (open-output-file filename)

33 6. 33 (close-input-port port) (close-output-port port) port port (read) (read port) library library read Scheme datum read port port (End of file) port current-input-port (read-char) (read-char port) port port port current-input-port (peek-char) (peek-char port) port port port current-input-port peek-char port read-char port read-char peek-char peek-char read-char peek-char (eof-object? obj ) obj #t #f Scheme read (char-ready?) (char-ready? port) port #t #f char-ready #t port read-char port char-ready? #t port current-input-port char-ready? char-ready? char-ready? #f (write obj ) (write obj port) library library port obj #\ write port current-output-port (display obj ) (display obj port) library library port obj write-char write display port current-output-port write display write display (newline) (newline port) library library port port current-output-port (write-char char) (write-char char port) port char port current-output-port

34 34 Scheme (load filename) optional filename Scheme load load current-input-port current-output-port load load (transcript-on filename) (transcript-off) optional optional filename transcript-on Scheme transcript-off 7. Scheme 7.1. BNF Scheme #x1a #X1a empty BNF thing * thing thing + thing Token intertoken space delimiter [ ] { } token identifier boolean number character string ( ) #( `,,@. delimiter whitespace ( ) " ; whitespace space or newline comment ; all subsequent characters up to a line break atmosphere whitespace comment intertoken space atmosphere * identifier initial subsequent * peculiar identifier initial letter special initial letter a b c... z special initial! $ % & * / : < = >? ^ _ ~ subsequent initial digit special subsequent digit special subsequent + peculiar identifier syntactic keyword expression keyword else => define unquote unquote-splicing expression keyword quote lambda if set! begin cond and or case

35 7. 35 let let* letrec do delay quasiquote variable any identifier that isn t also a syntactic keyword boolean #t #f character #\ any character #\ character name character name space newline string " string element * " string element any character other than " or \ \" \\ number num 2 num 8 num 10 num 16 num R complex R real R ureal R uinteger R prefix R R = 2, 8, 10, 16 decimal 2 decimal 8 decimal 16 num R prefix R complex R complex R real R real real R real R + ureal R i real R - ureal R i real R + i real R - i + ureal R i - ureal R i + i - i real R sign ureal R ureal R uinteger R uinteger R / uinteger R decimal R decimal 10 uinteger 10 suffix. digit 10 + #* suffix digit digit 10 * #* suffix digit 10 + # +. #* suffix uinteger R digit R + #* prefix R radix R exactness exactness radix R suffix empty exponent marker sign digit 10 + exponent marker e s f d l sign empty + - exactness empty #i #e radix 2 #b radix 8 #o radix 10 empty #d radix 16 #x digit digit digit 10 digit digit 16 digit 10 a b c d e f datum read expression datum datum simple datum compound datum simple datum boolean number character string symbol symbol identifier compound datum list vector list ( datum *) ( datum +. datum ) abbreviation abbreviation abbrev prefix datum abbrev prefix `,,@ vector #( datum *) expression variable literal call lambda expression conditional assignment derived expression macro use macro block literal quotation self-evaluating self-evaluating boolean number character string quotation datum (quote datum ) call ( operator operand *) operator expression operand expression lambda expression (lambda formals body ) formals ( variable *) variable ( variable +. variable ) body definition * sequence sequence command * expression command expression conditional (if test consequent alternate ) test expression consequent expression alternate expression empty assignment (set! variable expression ) derived expression (cond cond clause + ) (cond cond clause * (else sequence )) (case expression case clause + )

36 36 Scheme 5 (case expression case clause * (else sequence )) (and test *) (or test *) (let ( binding spec *) body ) (let variable ( binding spec *) body ) (let* ( binding spec *) body ) (letrec ( binding spec *) body ) (begin sequence ) (do ( iteration spec *) ( test do result ) command *) (delay expression ) quasiquotation cond clause ( test sequence ) ( test ) ( test => recipient ) recipient expression case clause (( datum *) sequence ) binding spec ( variable expression ) iteration spec ( variable init step ) ( variable init ) init expression step expression do result sequence empty macro use ( keyword datum *) keyword identifier macro block (let-syntax ( syntax spec *) body ) (letrec-syntax ( syntax spec *) body ) syntax spec ( keyword transformer spec ) D = 1, 2, 3,... D quasiquotation quasiquotation 1 qq template 0 expression quasiquotation D ` qq template D (quasiquote qq template D ) qq template D simple datum list qq template D vector qq template D unquotation D list qq template D ( qq template or splice D *) ( qq template or splice D +. qq template D ) qq template D quasiquotation D + 1 vector qq template D #( qq template or splice D *) unquotation D, qq template D 1 (unquote qq template D 1 ) qq template or splice D qq template D splicing unquotation D splicing unquotation D,@ qq template D 1 (unquote-splicing qq template D 1 ) quasiquotation list qq template D unquotation D splicing unquotation D unquotation splicing unquotation D transformer spec (syntax-rules ( identifier *) syntax rule *) syntax rule ( pattern template ) pattern pattern identifier ( pattern *) ( pattern +. pattern ) ( pattern * pattern ellipsis ) #( pattern *) #( pattern * pattern ellipsis ) pattern datum pattern datum string character boolean number template pattern identifier ( template element *) ( template element +. template ) #( template element *) template datum template element template template ellipsis template datum pattern datum pattern identifier any identifier except... ellipsis the identifier program command or definition * command or definition command definition syntax definition (begin command or definition + ) definition (define variable expression ) (define ( variable def formals ) body ) (begin definition *) def formals variable * variable *. variable syntax definition

37 7. 37 (define-syntax keyword transformer spec ) (lambda I Γ* E 0 ) (if E 0 E 1 E 2 ) (if E 0 E 1 ) (set! I E) 7.2. Scheme [29]... s k s k 1 #s s s t s t s k s k t a, b McCarthy t a b ρ[x/i] ρ x i x in D x D x D x D (Expression continuation) permute unpermute new new σ L σ (new σ L) 2 = false K K P P E[[((lambda (I*) P ) undefined... )]] I* P P P undefined undefined E K Con I Ide E Exp Γ Com = Exp Exp K I (E 0 E*) (lambda (I*) Γ* E 0 ) (lambda (I*. I) Γ* E 0 ) α L ν N T = {false, true} Q H R E p = L L T E v = L* T E s = L* T M = {false, true, null, undefined, unspecified} φ F = L (E* K C) ɛ E = Q + H + R + E p + E v + E s + M + F σ S = L (E T) ρ U = Ide L θ C = S A κ K = E* C A X K : Con E E : Exp U K C E* : Exp* U K C C : Com* U C C K E[[K]] = λρκ. send (K[[K]]) κ E[[I]] = λρκ. hold (lookup ρ I) (single(λɛ. ɛ = undefined wrong undefined variable, send ɛ κ)) E[[(E 0 E*)]] = λρκ. E*(permute( E 0 E*)) ρ (λɛ*. ((λɛ*. applicate (ɛ* 1) (ɛ* 1) κ) (unpermute ɛ*))) E[[(lambda (I*) Γ* E 0)]] = λρκ. λσ. new σ L send ( new σ L, λɛ*κ. #ɛ* = #I* tievals(λα*. (λρ. C[[Γ*]]ρ (E [E 0 ]ρ κ )) (extends ρ I* α*)) ɛ*,

38 38 Scheme 5 wrong wrong number of arguments in E) κ (update (new σ L) unspecified σ), wrong out of memory σ E [(lambda (I*. I) Γ* E 0)] = λρκ. λσ. new σ L send ( new σ L, λɛ*κ. #ɛ* #I* tievalsrest (λα*. (λρ. C [Γ*]ρ (E [E 0 ]ρ κ )) (extends ρ (I* I ) α*)) ɛ* (#I*), wrong too few arguments in E) κ (update (new σ L) unspecified σ), wrong out of memory σ E [(lambda I Γ* E 0)]] = E [(lambda (. I) Γ* E 0)] E [(if E 0 E 1 E 2)]] = λρκ. E[[E 0]] ρ (single (λɛ. truish ɛ E [E 1 ]ρκ, E [E 2 ]ρκ)) E [(if E 0 E 1)]] = λρκ. E[[E 0]] ρ (single (λɛ. truish ɛ E [E 1 ]ρκ, send unspecified κ)) undefined unspecified 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 [Γ*]ρθ) 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 = λɛκ. κ ɛ [implementation-dependent] single : (E C) K single = λψɛ*. #ɛ* = 1 ψ(ɛ* 1), wrong wrong number of return values 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 /α] [implementation-dependent] tievals : (L* C) E* C tievals = λψɛ*σ. #ɛ* = 0 ψ σ, new σ L tievals (λα*. ψ( new σ L α*)) (ɛ* 1) (update(new σ L)(ɛ* 1)σ), wrong out of memory σ 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* [implementation-dependent] [inverse of permute] applicate : E E* K C applicate = λɛɛ*κ. ɛ F (ɛ F 2)ɛ*κ, wrong bad onearg : (E K C) (E* K C) onearg = λζɛ*κ. #ɛ* = 1 ζ(ɛ* 1)κ, wrong wrong number of arguments twoarg : (E E K C) (E* K C) twoarg = λζɛ*κ. #ɛ* = 2 ζ(ɛ* 1)(ɛ* 2)κ, wrong wrong number of arguments 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) κ

39 7. 39 (update(new σ L)ɛ 2σ ), wrong out of memory σ ) (update(new σ L)ɛ 1σ), wrong out of memory σ) less : E* K C less = twoarg (λɛ 1ɛ 2κ. (ɛ 1 R ɛ 2 R) send (ɛ 1 R < ɛ 2 R true, false)κ, wrong non-numeric argument to < ) add : E* K C add = twoarg (λɛ 1ɛ 2κ. (ɛ 1 R ɛ 2 R) send ((ɛ 1 R + ɛ 2 R) in E)κ, wrong non-numeric argument to + ) car : E* K C car = onearg (λɛκ. ɛ E p hold (ɛ E p 1)κ, wrong non-pair argument to car ) cdr : E* K C [similar to 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 immutable argument to set-car!, wrong non-pair argument to 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 1p 2. ((p 1 1) = (p 2 1) (p 1 2) = (p 2 2)) true, false) (ɛ 1 E p) (ɛ 2 E p)) κ, (ɛ 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 bad argument to apply ) valueslist : E* K C valueslist = onearg (λɛκ. ɛ E p cdr ɛ (λɛ*. valueslist ɛ* (λɛ*. car ɛ (single(λɛ. κ( ɛ ɛ*))))), ɛ = null κ, wrong non-list argument to 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 out of memory σ), wrong bad argument ) values : E* K C values = λɛ*κ. κɛ* cwv : E* K C [call-with-values] cwv = twoarg (λɛ 1ɛ 2κ. applicate ɛ 1 (λɛ*. applicate ɛ 2 ɛ*)) 7.3. lambda if set! delay 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) ((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...)

40 40 Scheme 5 (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)))) (define-syntax or (syntax-rules () ((or) #f) ((or 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...)))) (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...))))) letrec <undefined> Scheme (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...) ((lambda () exp...))))) begin lambda begin (define-syntax begin (syntax-rules () ((begin exp) exp) ((begin exp1 exp2...) (let ((x exp1)) (begin exp2...))))) do letrec (if #f #f) (define-syntax do

41 41 (syntax-rules () ((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))) 4 [6] Scheme IEEE Scheme [13] Scheme IEEE true load with-input-from-file with-output-tofile transcript-on transcript-off interaction-environment - / IEEE port syntax-rules eval Internet Scheme Scheme Scheme

42 42 Scheme 5 integrate-system Runge-Kutta y k = f k (y 1, y 2,..., y n ), k = 1,..., n system-derivative y 1,..., y n y 1,..., y n initial-state h integrate-system (define integrate-system (lambda (system-derivative initial-state h) (let ((next (runge-kutta-4 system-derivative h))) (letrec ((states (cons initial-state (delay (map-streams next states))))) 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) ;; y is a system state (let* ((k0 (*h (f y))) (k1 (*h (f (add-vectors y (*1/2 k0))))) (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 k1) (*2 k2) k3)))))))) (define elementwise (lambda (f) (lambda vectors (generate-vector (vector-length (car vectors)) (lambda (i) (apply f (map (lambda (v) (vector-ref vectors))))))) v i)) (loop 0))))) (define add-vectors (elementwise +)) (else (vector-set! ans i (proc i)) (loop (+ i 1))))))) (define scale-vector (lambda (s) (elementwise (lambda (x) (* x s))))) map-streams map (define map-streams (lambda (f s) (cons (f (head s)) (delay (map-streams f (tail s)))))) car cdr (define head car) (define tail (lambda (stream) (force (cdr stream)))) integrate-system 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)) (define generate-vector (lambda (size proc) (let ((ans (make-vector size))) (letrec ((loop (lambda (i) (cond ((= i size) ans)