'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2008Lecture 17— define-struct; Implementing higher-order functionsDan Grossman CSE341 Spring 2008, Lecture 17 1'&$%Data in SchemeRecall ML’s approach to each-of, one-of, and self-referential types:datatype t =Foo of int | Bar of int * int | Baz of string * tPure Scheme’s approach:• There is One Big Datatype holding every value.• Built-in predicates like null?, number?, procedure?• Primitives implicitly raise errors for “wrong variant”• Use pairs (lists) for each-of types• Can also use for one-of types with explicit “tags”– Like our force/delay with a boolean field– Symbols better style• Use helper functions like caddr (and/or define your own).Dan Grossman CSE341 Spring 2008, Lecture 17 2'&$%Dynamic typingThere is still good reason to have support for constructors:• Make a foo that has fields x, y, z• Test to see if you have a foo or notBut with dynamic typing:• Constructors are not “grouped” into types (just added to the OneBig Datatype)• The fields can hold anythingOrthogonally: We don’t have pattern-matching.Dan Grossman CSE341 Spring 2008, Lecture 17 3'&$%define-structDrScheme extends Scheme with define-struct, e.g.:(define-struct card (suit value))Semantics: Introduce several new bindings...• constructor (make-card) that takes arguments and make values(like cons)• predicate (card?) that takes 1 argument, return #t only forvalues made from the right constructor (like cons?).• accessors (card-suit, card-value) that take 1 argument, returna field, or call error for values not made from the rightconstructor (like car and cdr).• mutators (set-card-suit!, set-card-value!) that are likeaccessors except they mutate field contents (like set-car! andset-cdr!).Dan Grossman CSE341 Spring 2008, Lecture 17 4'&$%Idiom for ML datatypesInstead of a datatype with n constructors, you just usedefine-struct n times.That “these n go together” is just convention.Instead of case, you have a cond with n predicates and one“catch-all” error case.For homework 5:;; a variable, e.g., (make-var "foo")(define-struct var (string));; a constant number, e.g., (make-int 17)(define-struct int (num))(define-struct add (e1 e2)) ;; add two expressions(define-struct ifgreater (e1 e2 e3 e4)) ;; etc....Dan Grossman CSE341 Spring 2008, Lecture 17 5'&$%define-struct is specialdefine-struct creates a new variant for The One Big Datatype.Claim: define-struct is not a function.Claim: define-struct is not a macro.It could be a macro except for one key bit of its semantics: Valuesbuilt from the constructor cause every other predicate (including allbuilt-in ones like pair?) to return #f.Advantage: abstraction and bug-catching (clients can’t “abuse” yourthings as though they were something else)Disadvantage: Can’t write “generic” code that has a case for everypossible variant in every Scheme program (like eval).Dan Grossman CSE341 Spring 2008, Lecture 17 6'&$%Implementing LanguagesMostly 341 is about language meaning, not “how can animplementation do that”, but it’s important to “dispel the magic”.At super high-level, there are two ways to implement a language A:• Write an interpreter in language B that evaluates a program in A– Like we just saw for a little expression language• Write a compiler in language B that translates a program in A toa program in language C (and have an implementation of C)In theory, this is just an implementation decision.HW5: An interpreter for mupl in Scheme.Most interesting thing about mupl: higher-order functions.Dan Grossman CSE341 Spring 2008, Lecture 17 7'&$%How is one lan guage insi de another?How is:(make-negate (make-add (make-const 2) (make-const 2)))a “program” instead of"- (2 + 2)"Because parsing — turning a string/file into a tree of datatype-likethings is covered in CSE401.These trees are called abstract-syntax trees (or ASTs).They are ideal program representations for passing to an interpreter.We can write them by hand, or write a parser, or write code thatproduces them.Dan Grossman CSE341 Spring 2008, Lecture 17 8'&$%An interpreterA “direct” language implementation is often just writing ourevaluation rules for our language in another language.• Languages with variables need interpreters with environments• “eval-prog” takes an environment and an expression and returns avalue (the subset of expressions that we define to be answers)• An environment is just a mapping from variables to values (e.g.,an association list)• “eval-prog” uses recursion– Example: To evaluate an addition expression, evaluate the twosubexpressions under the same environment, then...• For homework 5, expressions & environments are all we need– Exceptions or mutation can require more inputs/outputs to“eval-prog”Dan Grossman CSE341 Spring 2008, Lecture 17 9'&$%Implementing Higher-Order FunctionsThe magic: How is the “right environment” around for lexical scope(the environment from when the function was defined)?Lack of magic: Implementation keeps it around!Interpreter:• The interpreter has a “current environment”• To evaluate a function (expression), create a closure (value), apair of the function and the “current environment”.• Application will now apply a closure to an argument: Interpretfunction body, but instead of using “current environment”, useclosure’s environment extended with the argument.Note: This is directly implementing the semantics from week 3.Dan Grossman CSE341 Spring 2008, Lecture 17 10'&$%Is that expensive?Building a closure is easy; you already have the environment.Since environments are immutable, it’s easy to share them.Still, a given closure doesn’t need most of the environment, so forspace efficiency it can be worth it to make a new smaller environmentholding only the function’s free variables.• That is, an approximation of the things a call to the functionmight look up.• Challenge problem in homework 5Dan Grossman CSE341 Spring 2008, Lecture 17 11'&$%Compiling Higher-Order FunctionsThe key to the interpreter approach: The interpreter has an explicitenvironment and can “change” it to implement lexical scope.We can also compile higher-order functions to a language withouthigher-order functions:Instead of an implicit environment, we pass an explicit environment toevery function.• As with interpreter, we build a closure to evaluate functions.• But all functions now take one extra
View Full Document
Unlocking...