CSE341, Fall 2011, Lecture 17 SummaryStandard Disclaimer: This lecture summary is not necessarily a complete substitute for attending class,reading the associated code, etc. It is designed to be a useful resource for students who attended class andare later reviewing the material.This lecture covers three topics that are all directly relevant to the upcoming homework assignment in whichyou will use Racket to write an interpreter for a small programming language:• Racket’s structs for defining new (dynamic) types in Racket and contrasting them with manually taggedlists [This material was actually covered in the “Monday section” and only briefly reviewed in the othermaterials for this lecture.]• How a programming language can be implemented in another programming language, including keystages/concepts like parsing, compilation, interpretation, and variants thereof• How to implement higher-order functions and closures by explicitly managing and storing environmentsat run-timeOne-of types with lists and dynamic typingIn ML, we studied one-of types (in the form of datatype bindings) almost from the beginning, since theywere essential for defining many kinds of data. Racket’s dynamic typing makes the issue less central sincewe can simply use primitives like booleans and cons cells to build anything we want. Building lists and treesout of dynamically typed pairs is particularly straightforward.However, the concept of one-of types is still prevalent. For example, a list is null or a cons cell wherethere cdr holds a list. Moreover, Racket extends its Scheme predecessor with something very similar toML’s constructors — a special form called struct — and it is instructive to contrast the two language’sapproaches.Before seeing struct, let’s consider Racket without it. There is no type system to restrict what we passto a function, put in a pair, etc. However, there are different kinds of values — various kinds of numbers,procedures, pairs, strings, symbols, booleans, the empty-list — and built-in predicates like number? andnull? to determine what kind of value some particular value is. For values that have “parts” (cons cells),there are built-in functions for getting the parts (car and cdr). So in a real sense, all Racket values arein “one big datatype” and primitives like + check the “tags” of their arguments (e.g., is it a number usingnumber?) and raise an exception for a “run-time type error” before performing some computation (e.g.,addition) and making a new “tagged” value (e.g., a new number). These “tags” are like ML constructors,but it is like our whole language has exactly one datatype, everything is in it, all tags are implicit andautomatically inserted, and the primitives implicitly include case expressions that raise exceptions for thewrong tags.Given struct-less Racket, we can still “code up” our own datatypes as an idiom. One reasonable approachis to use lists where the first list element is a symbol1to indicate which variant of a one-of type you have.For example, consider this ML datatype:datatype exp = Const of int | Add of exp * exp | Negate of expOne way to represent similar values in Racket is to use lists where the first element is ’Const, ’Add, or’Negate. If it is ’Const, we will have one more list element which is a number. If it is ’Add, we will1See The Racket Guide for a discussion of what symbols are. In short, they are constants that you can compare using eq?,which is fast. They are not strings despite the obvious similarity. A symbol is an atom, meaning it has no subparts: you cannotextract a character of a symbol. There are primitives to convert between symbols and strings, but there are also primitives toconvert between numbers and strings, which are clearly not the same thing.1have two more list elements holding subexpressions. Notice Racket’s dynamic typing—specifically lists withelements of different types—is essential. So we could build an expression like this:(list ’Negate (list ’Add (list ’Const 2) (list ’Const 2)))Then functions processing expressions could check the car of the list to see what sort of expression they haveand we could use cond-expressions to “code up” ML-style case expressions without the pattern-matching.However, it is bad style to assume this sort of data representation all over a large program. Instead, weshould abstract our decisions into helper functions and then use this interface throughout our program.While the entire notion of an exp datatype is just “in our head” (nowhere does our Racket code define whatan exp is), we still know what we need, namely:• A way to build each kind of expression (constructors)• A way to test for the different possibilities (predicates)• A way to extract the different pieces of each kind of expressionTo keep things simple, we won’t have the extractors raise errors for the wrong kind of thing, though weprobably should. Defining all the helper functions is easy:2(define (Const i) (list ’Const i))(define (Add e1 e2) (list ’Add e1 e2))(define (Negate e) (list ’Negate e))(define (Const? x) (eq? (car x) ’Const))(define (Add? x) (eq? (car x) ’Add))(define (Negate? x) (eq? (car x) ’Negate))(define Const-int cadr)(define Add-e1 cadr)(define Add-e2 caddr)(define Negate-e cadr)Now we can write expressions in a much better, more abstract style:(Negate (Add (Const 2) (Const 2)))Here is an interpreter for our little expression language, using the interface we defined:(define (eval-exp e)(cond [(Const? e) e][(Add? e) (let ([v1 (Const-int (eval-exp (Add-e1 e)))][v2 (Const-int (eval-exp (Add-e2 e)))])(Const (+ v1 v2)))][(Negate? e) (Const (- 0 (Const-int (eval-exp (Negate-e e)))))][#t (error "eval-exp expected an exp")]))2cadr and caddr are built-in functions that are shorter versions of (lambda(x) (car (cdr x))) and (lambda(x) (car (cdr(cdr x)))) respectively. Similar functions are predefined for any combination of car and cdr up to four uses deep. This supportreflects the historical idiom of using cons cells to code up various datatypes.2As discussed more below, our interpreter takes an expression (in this case for arithmetic) and produces avalue (an expression that cannot be evaluated more; in this case a constant).While this sort of interface is good style in struct-less Racket, it still requires us to remember to use it and“not cheat.” Nothing prevents a bad programmer from writing (list ’Add #f), which
View Full Document
Unlocking...