'&$%CSE 341:Programming LanguagesDan GrossmanWinter 2008Lecture 17— Implementing languages, especially higher-order functionsDan Grossman CSE341 Winter 2008, Lecture 17 1'&$%Where are we• Today:– Finish static vs. dynamic typing (arguments 2–5)– Learn how closures are actually implemented (key to hw 5)• Friday: Modularity in Scheme• Monday: Ruby basics• Later: More concepts and contrasts– At least as important as programming details– (for life and, say, the final)Dan Grossman CSE341 Winter 2008, Lecture 17 2'&$%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• Write a compiler in langage 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 Winter 2008, Lecture 17 3'&$%An interpreterA “direct” language implementation is often just writing ourevaluation rules for our language in another language.• “eval” takes an environment and an expression and returns a v alue(the subset of expressions that we define to be answers)• “eval” 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”Dan Grossman CSE341 Winter 2008, Lecture 17 4'&$%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 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 Winter 2008, Lecture 17 5'&$%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.• Challenge problem in homework 5Dan Grossman CSE341 Winter 2008, Lecture 17 6'&$%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 to a language without free variables: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 argument.• Application passes a closure’s code its own environment for theextra argument.• Evaluating variables uses this extra argument.– Compiler translates them to environment-reads.Plus: Lots of data-structure optimizations so variable-lookup is fast(often a read from a known-size record).Dan Grossman CSE341 Winter 2008, Lecture 17
View Full Document
Unlocking...