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 2005—9CSc 520Principles of ProgrammingLanguages9: Scheme — Metacircular InterpretationChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—9IntroductionIn this lecture I’m going to show how you can defineScheme by writing a metacircular 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 2005—9Let 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 2005—9Let Expressions...Let-expressions can be nested:> (let ((x 5) (c 4))(let ((v (* 4 x))(t (* 2 c)))(+ v t)))28[4]520—Spring 2005—9Imperative 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 2005—9Imperative 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 2005—9Dotted 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)calledcar 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 2005—9Dotted 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 2005—9Dotted 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 2005—9Dotted Pairs...(cons A B) can be thought of as first creating acons-cell on the heap (using malloc, for example),and then setting thecar 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 2005—9LoopsScheme’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)· · ·)(termination cond return value)loop body)[11]520—Spring 2005—9Loops...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 2005—9Association 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 2005—9Association 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 2005—9Association Lists...We can actually have more than one value:> (assoc ’bob ’((bob 5 male)(jane 32 ’female)))(bob 5 male)[15]520—Spring 2005—9ApplyApply 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 2005—9Eval(eval arg) evaluates its argument.> (eval ’(+ 4 5))9> (eval ’(cons ’a ’(b c))) (a b c)[17]520—Spring 2005—9Eval...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 2005—9Programs 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 2005—9Evaluation OrderSo far, we have said that to evaluate an expression(op arg1 arg2 arg3) we first evaluate thearguments, then apply the operatorop 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 2005—9Evaluation 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 2005—9Evaluation 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 all the arguments,although only one value will ever be needed.[22]520—Spring
View Full Document
Unlocking...