Slide 1ReviewDefines treesML’s view of Racket’s “type system”Implementing PLsWays to implement a languageReality more complicatedSermonOkay, they do have one pointDigression: eval in RacketFurther digression: quotingBack to implementing a languageSkipping those stepsThe arith-exp exampleThe interpreter“Macros”What’s missingHigher-order functionsFunction callsIs that expensive?Free variables examplesFree variables examplesCompiling higher-order functionsCSE341: Programming LanguagesLecture 17Structs, Implementing Languages, Implementing Higher-Order FunctionsDan GrossmanFall 2011Review•Given pairs and dynamic typing, you can code up “one-of types” by using first list-element like a constructor name:•But much better and more convenient is Racket’s structs–Makes a new dynamic type (pair? answers false)–Provides constructor, predicate, accessorsFall 2011 2CSE341: Programming Languages(define (const i) (list 'const i))(define (add e1 e2) (list 'add e1 e2))(define (negate e) (list 'negate e))(struct const (i) #:transparent)(struct add (e1 e2) #:transparent)(struct negate (e) #:transparent)Defines trees•Either lists or structs (we’ll use structs) can then let us build trees to represent compound data such as expressions•Since Racket is dynamically typed, the idea that a set of constructors are variants for “an expression datatype” is in our heads / comments –Skipping: Racket’s contracts have such notionsFall 2011 3CSE341: Programming Languages(add (const 4) (negate (add (const 1) (negate (const 7)))))ML’s view of Racket’s “type system”One way to describe Racket is that it has “one big datatype”–All values have this same one type•Constructors are applied implicitly (values are tagged)–42 is implicitly “int constructor with 42”•Primitives implicitly check tags and extract data, raising errors for wrong constructors–+ is implicitly “check for int constructors and extract data”–[Actually Racket has a numeric tower that + works on]•Built-in: numbers, strings, booleans, pairs, symbols, procedures, etc.–Each struct creates a new constructor, a feature many dynamic languages do not have–(struct …) can be neither a function nor a macroFall 2011 4CSE341: Programming Languagesinttag 42Implementing PLsMost of the course is learning fundamental concepts for using PLs–Syntax vs. semantics vs. idioms–Powerful constructs like pattern-matching, closures, dynamically typed pairs, macros, …An educated computer scientist should also know some things about implementing PLs–Implementing something requires fully understanding its semantics–Things like closures and objects are not “magic”–Many programming tasks are like implementing PLs•Example: rendering a document (“program” is the [structured] document and “pixels” is the output)Fall 2011 5CSE341: Programming LanguagesWays to implement a languageTwo fundamental ways to implement a PL A•Write an interpreter in another language B–Better names: evaluator, executor–Take a program in A and produce an answer (in A)•Write a compiler in another language B to a third language C–Better name: translator–Translation must preserve meaning (equivalence)We call B the metalanguage; crucial to keep A and B straightVery first language needed a hardware implementationFall 2011 6CSE341: Programming LanguagesReality more complicatedEvaluation (interpreter) and translation (compiler) are your options–But in modern practice have both and multiple layersA plausible example:–Java compiler to bytecode intermediate language–Have an interpreter for bytecode (itself in binary), but compile frequent functions to binary at run-time–The chip is itself an interpreter for binary•Well, except these days the x86 has a translator in hardware to more primitive micro-operations that it then executesRacket uses a similar mixFall 2011 7CSE341: Programming LanguagesSermonInterpreter versus compiler versus combinations is about a particular language implementation, not the language definitionSo clearly there is no such thing as a “compiled language” or an “interpreted language”–Programs cannot “see” how the implementation worksUnfortunately, you hear these phrases all the time–“C is faster because it’s compiled and LISP is interpreted”–Nonsense: I can write a C interpreter or a LISP compiler, regardless of what most implementations happen to do–Please politely correct your managers, friends, and other professors Fall 2011 8CSE341: Programming LanguagesOkay, they do have one pointIn a traditional implementation via compiler, you do not need the language implementation to run the program–Only to compile it–So you can just “ship the binary”But Racket, Scheme, LISP, Javascript, Ruby, … have eval–At run-time create some data (in Racket a list, in Javascript a string) and treat it as a program–Then run that program–Since we don’t know ahead of time what data will be created and therefore what program it will represent, we need a language implementation at run-time to support eval•Could be interpreter, compiler, combinationFall 2011 9CSE341: Programming LanguagesDigression: eval in RacketAppropriate idioms for eval are a matter of contention–Often but not always there is a better way–Programs with eval are harder to analyzeWe won’t use eval, but no point in leaving it mysterious–It works on nested lists of symbols and other valuesFall 2011 10CSE341: Programming Languages(define (make-some-code y) ; just returns a list (if y (list 'begin (list 'print "hi") (list '+ 4 2)) (list '+ 5 3)))(eval (make-some-code #t)) ; prints "hi", result 6Further digression: quoting•Quoting (quote …) or '(…) is a special form that makes “everything underneath” atoms and lists, not variables and calls–But then calling eval on it looks up symbols as code–So quote and eval are inverses•There is also quasiquoting–Everything underneath is atoms and lists except if unquoted–Languages like Ruby, Python, Perl eval strings and support putting expressions inside strings, which is quasiquoting•We won’t use any of this: see The Racket Guide if curiousFall 2011 11CSE341: Programming Languages(list 'begin (list 'print "hi") (list '+ 4 2)) (quote (begin (print "hi") (+ 4 2)))Back to implementing a language"(fn x => x + x) 7"Fall 2011 12CSE341: Programming
View Full Document
Unlocking...