IntroductionLet ExpressionsLet Expressionsldots Imperative FeaturesImperative Featuresldots Dotted PairsDotted Pairsldots Dotted Pairsldots Dotted Pairsldots LoopsLoopsldots Association ListsAssociation Listsldots Association Listsldots ApplyEvalEvalldots Programs as DataEvaluation OrderEvaluation Orderldots Evaluation Orderldots Evaluation Orderldots A Metacircular InterpreterA Metacircular Interpreterldots A Metacircular Interpreterldots A Metacircular Interpreterldots A Metacircular Interpreterldots A Metacircular Interpreterldots A Metacircular Interpreterldots A Metacircular Interpreterldots Readings and References520 —Spring 2008 — 40CSc 520Principles of ProgrammingLanguages40 : Scheme — Metacircular InterpretationChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 40IntroductionIn this lecture I’m going to show how you can defineScheme by writing ametacircular interpreter for thelanguage, i.e. an interpreter for Scheme written inScheme.Before we can do that, we first need to learn a few morethis about the language[2]520 —Spring 2008 — 40Let ExpressionsA let-expression binds names to values:(let ((name1value1) (name2value2) ...)expression)The first argument to let is a list of (name value)pairs. The second argument is the expression toevaluate.> (let ((a 3) (b 4) (square (lambda (x)(*x x)))(plus +))(sqrt (plus (square a) (square b))))5.0[3]520 —Spring 2008 — 40Let Expressions...Let-expressions can be nested:> (let ((x 5) (c 4))(let ((v (*4 x))(t (*2 c)))(+ v t)))28[4]520 —Spring 2008 — 40Imperative FeaturesScheme is an impure functional language.I.e., Scheme has imperative features.I.e., in Scheme it is possible to program withside-effects.(set! var value) Change the value of var to value.(set-car! var value) Change the car-field of thecons-cell var to value.(set-cdr! var value) Change the cdr-field of thecons-cell var to value.[5]520 —Spring 2008 — 40Imperative Features...Example:> (let ((x 2) (l ’(a b)))(set! x 3)(set-car! l ’(c d))(set-cdr! l ’(e))(display x) (newline)(display l) (newline))3((c d) e)[6]520 —Spring 2008 — 40Dotted PairsS-expressions are constructed using dotted pairs.It is implemented as a struct (called a cons-cell)consisting of two fields (the size of a machine word)called car and cdr.We can manipulate these fields directly:> ’(1 . 2)(1 . 2)> (cons "stacy’s" "mom")("stacy’s" . "mom")> ’(1 . (2 . 3))(1 2 . 3)> (cons 1 2)(1 . 2)[7]520 —Spring 2008 — 40Dotted Pairs...When the second part of a dottend pair (the cdr-field)is a list, and the innermost cdr-field is the empty list,we get a “normal” Scheme list:> ’(1 . ())(1)> ’(1 . (2 . ()))(1 2)> ’(1 . (2 3))(1 2 3)[8]520 —Spring 2008 — 40Dotted Pairs...We can use set-car! and set-cdr! to manipulatethe fields of a cons-cell directly:> (define x ’(1 . 2))> (set-car! x ’a)> x(a . 2)> (set-cdr! x ’(2 3))> x(a 2 3)[9]520 —Spring 2008 — 40Dotted Pairs...(cons A B) can be thought of as first creating acons-cell on the heap (using malloc, for example),and then setting the car and cdr fields to A and B,respectively:> (define x (cons 0 0))> x(0 . 0)> (set-car! x ’1)> (set-cdr! x ’())> x(1)[10]520 —Spring 2008 — 40LoopsScheme’s “for-loop” do takes these arguments:1. A list of triples (var init update) which declares avariable var, with an initial value init, and which getsupdated using the expression update, on each iteration;2. A pair (termination_cond return_value) which gives thetermination condition and return value of the loop; and3. a loop body:(do ((var1 init1 update1)(var12 init2 update2)· · ·)(terminationcond return value)loop body)[11]520 —Spring 2008 — 40Loops...Sum the numbers 1 to 4, printing out intermediateresults:> (do ((i 1 (+ i 1))(sum 0 (+ sum i)))((= i 5) sum)(display sum)(newline))013610[12]520 —Spring 2008 — 40Association ListsAssociation lists are simply lists of key-value pairs thatcan be searched sequentially:> (assoc ’bob ’((bob 22) (joe 32) (bob 3)))(bob 22)The list is searchedy the list from beginning to end,returning the first pair with a matching key:(assoc key alist) Search for key; compare usingequal?.(assq key alist) Search for key; compare usingeq?.(assv key alist) Search for key; compare usingeqv?.[13]520 —Spring 2008 — 40Association Lists...> (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))> (assv 5 ’((2 3) (5 7) (11 13)))(5 7)[14]520 —Spring 2008 — 40Association Lists...We can actually have more than one value:> (assoc ’bob ’((bob 5 male)(jane 32 ’female)))(bob 5 male)[15]520 —Spring 2008 — 40ApplyApply returns the result of applying its first argument toits second argument.> (apply + ’(6 7))13> (apply max ’(2 5 1 7))7[16]520 —Spring 2008 — 40Eval(eval arg) evaluates its argument.> (eval ’(+ 4 5))9> (eval ’(cons ’a ’(b c))) (a b c)[17]520 —Spring 2008 — 40Eval...eval and quote are each other’s inverses:> (eval ’’(+ 4 5))(+ 4 5)> (eval (eval ’’(+ 4 5)))9> (eval (eval (eval ’’’(+ 4 5))))9[18]520 —Spring 2008 — 40Programs as DataScheme is homoiconic, self-representing, i.e. programsand data are both represented the same (asS-expressions).This allows us to write programs that generateprograms - useful in AI, for example.> (define x ’car)> (define y ’’(a b c))> (define p (list x y))> p(car ’(a b c))> (eval p)a[19]520 —Spring 2008 — 40Evaluation OrderSo far, we have said that to evaluate an expression(op arg1 arg2 arg3) we first evaluate thearguments, then apply the operator op to the resultingvalues.This is known as applicative-order evaluation.Example:(define (double x) (*x x))> (double (*3 4))⇒ (double 12)⇒ (+ 12 12)⇒ 24[20]520 —Spring 2008 — 40Evaluation Order...This is not the only possible order of evaluationIn normal-order evaluation parameters to a function arealways passed unevaluated.This sometimes leads to extra work:(define (double x) (*x x))> (double (*3 4))⇒ (+ (*3 4) (*3 4)))⇒ (+ 12 (*3 4))⇒ (+ 12 12)⇒ 24[21]520 —Spring 2008 — 40Evaluation Order...Applicative-order can sometimes also lead to morework than normal-order:(define (switch x a b c)(cond((< x 0) a)((= x 0) b)((> x 0) c)))> (switch -1 (+ 1 2) (+ 2 3) (+ 3 4))Here, applicative-order evaluates
View Full Document