Programming Languages Design Specification and Implementation G22 2210 001 Rob Strom October 5 2006 Administrative Alternative mailing address for me robstrom us ibm com Everyone should subscribe to the class mailing list http www cs nyu edu mailman listinfo g22 2110 001 fa06 Reading Scott chapter 7 types in actual languages Pierce chapter 8 type inferencing theory Programming Languages Core Exam Syntactic issues regular expressions context free grammars CFG BNF Imperative languages program organization control structures Types in imperative languages strong typing type equivalence unions and discriminated types in C and Ada Block structure visibility and scoping issues parameter passing Systems programming and weak typing exposing machine characteristics type coercion pointers arrays in C Run time organization of block structured languages static scoping activation records dynamic and static chains displays Programming in the large abstract data types modules packages and namespaces in Ada Java and C Functional programming list structures higher order functions lambda expressions garbage collection metainterpreters in Lisp and Scheme Type inference and ML Object Oriented programming classes inheritance polymorphism dynamic dispatching Constructors destructors and multiple inheritance in C interfaces in Java Generic programming parametrized units and classes in C Ada and Java Concurrent programming threads and tasks communication race conditions and deadlocks protected methods and types in Ada and Java Closures A closure is a function whose execution has access to an external environment LISP was the earliest language to do closures and it did them the other way dynamic Static generally considered better Scheme is basically LISP with closures done right AddX revisited define makeAddX returns a function lambda x lambda y x y define add3 makeAddX 3 add3 4 makeAddX 3 4 Another higher order function define mapcar lambda fn lst if null lst nil cons fn car lst mapcar fn cdr lst mapcar add3 4 7 3 Scheme Applicative example define isort lambda l letrec defines a list of bindings here just 1 insert inserts item x in sorted order to list l lambda x l if null l list x if x car l cons x l cons car l insert x cdr l means this insert the below is executed in the context of the bindings if null l nil insert car l isort cdr l isort 3 20 13 2 Continuations A procedure with parameters to tell you what to do with an answer after computing it In Continuation Passing Style CPS instead of returning a result you pass the result to the continuation that was passed to you define mysqrt x sqrt x normal definition of mysqrt display mysqrt 4 normal call to display mysqrt of 4 mysqrt 4 2 normal call to compute sqrt 4 2 define mysqrt x k k sqrt x CPS definition of mysqrt mysqrt 4 display CPS call to display mysqrt of 4 mysqrt 4 lambda x x 2 CPS call to compute sqrt 4 2 define factorial n if n 1 1 n factorial n 1 normal definition of factorial factorial 4 2 normal call to compute 4 2 define factorial n k if n 1 k 1 factorial n 1 lambda ret k n ret factorial 4 lambda x x 2 CPS call to compute 4 2 Using CPS and closures To return multiple values x y z instead of packing it into a single object like x y z and later unpacking simply call the continuation passing x y z Instead of alternate exits e g succeed and return x y z vs fail and return nothing use multiple continuations Example CPS plus closures define get expr prefix lambda lst a list of unparsed tokens success continuation parsedexpr unparsed parsedexpr expr tree of prefix of lst unparsed rest failure continuation unparsed letrec make closure lambda parsedexpr parsedexpr expr parsed so far cont a continuation handle has suffix handle has no suffix handle has suffix lambda operator unparsed handle has no suffix lambda unparsed letrec expr parsedexpr handle has suffix method lambda operator unparsed handle has no suffix method lambda unparsed success parsedexpr unparsed cont handle has suffix method handle has no suffix method Find the term following the operator lambda parsedterm unparsed If there is one term found extend the expression save it in the closure parsedterm term tree unparsed rest of lst make closure cons expr list parsedterm and once again try to find a suffix lambda has suffix method If there isn t one this is a bad expression e g A B has no suffix method get additive operator unparsed has suffix method has no suffix method letrec got term lambda parsedterm rest term not found lambda failure operator unparsed make closure cons expr unparsed list parsedexpr parsedterm get term prefix lst term found term not found lambda has suffix has no suffix get additive operator rest has suffix has no suffix define get expr lambda lst no term lambda rest failure rest get expr prefix lst lambda parsed unparsed if empty unparsed display parsed display error get term prefix rest got term no term lambda unparsed display error Call cc by example call with current continuation lambda exit for each lambda x if negative x exit x 54 0 37 3 245 19 t 3 define list length lambda obj call with current continuation lambda return letrec r lambda obj cond null obj 0 pair obj r cdr obj 1 else return f r obj list length 1 2 3 4 4 list length a b c f Macros These are ways to extend Scheme They are invoked on static expressions rather than on values Scheme introduced hygienic macros Hygiene If a macro transformer inserts a binding for an identifier the new binding will not capture other identifiers of the same name introduced elsewhere Referential Transparency If a macro transformer inserts a free reference to an identifier the reference refers to the binding that was visible where the transformer was specified regardless of any local bindings that may surround the use of the macro See also Generics Ada Templates C Parametrized Types Java Eval This allows you to create an arbitrary expression representing a Scheme program as a data object and then execute it There is an interpreter that one can write in scheme that emulates eval what is surprising is how short the program is a Scheme interpreter in Scheme is a shorter program that your homework program The interpreter is sometimes called a metacircular definition of the language See http academic evergreen edu curricular fofc00 eval html Types Languages differ on What has types run time or compile time entities What counts as type equivalence What counts as compatibility How types are inferred How much users can define