CSE341: Programming Languages Lecture 17 Structs, Implementing Languages, Implementing Higher-Order Functions Dan Grossman Fall 2011 Review • 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, accessors Fall 2011 2 CSE341: 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 notions Fall 2011 3 CSE341: 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 macro Fall 2011 4 CSE341: Programming Languages inttag 42 Implementing PLs Most 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 5 CSE341: Programming Languages Ways to implement a language Two 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 straight Very first language needed a hardware implementation Fall 2011 6 CSE341: Programming LanguagesReality more complicated Evaluation (interpreter) and translation (compiler) are your options – But in modern practice have both and multiple layers A 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 executes Racket uses a similar mix Fall 2011 7 CSE341: Programming Languages Sermon Interpreter versus compiler versus combinations is about a particular language implementation, not the language definition So clearly there is no such thing as a “compiled language” or an “interpreted language” – Programs cannot “see” how the implementation works Unfortunately, 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 8 CSE341: Programming Languages Okay, they do have one point In 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, combination Fall 2011 9 CSE341: Programming Languages Digression: eval in Racket Appropriate idioms for eval are a matter of contention – Often but not always there is a better way – Programs with eval are harder to analyze We won’t use eval, but no point in leaving it mysterious – It works on nested lists of symbols and other values Fall 2011 10 CSE341: 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 6 Further 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 curious Fall 2011 11 CSE341: 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 12 CSE341: Programming Languages Parsing Call Function + Negate Constant 4 x x x Var Var Static checking (what checked depends on PL) Possible Errors / warnings Rest of implementation Possible Errors / warningsSkipping those steps Alternately, we can embed our language
View Full Document
Unlocking...