DOC PREVIEW
UA CSC 520 - Metacircular Interpretation

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 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 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)loopbody)[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

UA CSC 520 - Metacircular Interpretation

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Metacircular Interpretation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Metacircular Interpretation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Metacircular Interpretation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?