Programming Languages: Design, Specification, and ImplementationAdministrativeProgramming Languages Core ExamClosuresAddX, revisitedAnother higher-order functionScheme: Applicative exampleContinuationsUsing CPS and closuresExample: CPS plus closuresCall/cc – by exampleMacrosEvalTypesClasses of typesSafety IssuesTypestateClasses of Types, continuedProgramming Languages:Design, Specification, and ImplementationG22.2210-001Rob StromOctober 5, 2006AdministrativeAlternative mailing address for me: [email protected]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))ContinuationsA procedure with parameters to tell you what to do with an answer after computing itIn 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! + 2Using 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 continuationsExample: CPS plus closures(define get-expr-prefix (lambda (lst ; a list of unparsed tokenssuccess ; continuation(parsedexpr unparsed) parsedexpr : expr-tree of prefix of lst, unparsed : restfailure ; 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) )) ( (term-found (lambda (parsedterm unparsed) ; parsedterm :term-tree, unparsed: rest of lst (make-closure (cons ‘expr (list parsedterm)) (lambda (has-suffix-method has-no-suffix-method) (get-additive-operator unparsed has-suffix-method has-no-suffix-method))) (term-not-found (lambda (unparsed) (failure unparsed))) (get-term-prefix lst term-found term-not-found) ) ))) (define get-expr (lambda lst) (get-expr-prefix lst (lambda (parsed, unparsed) (if (empty? unparsed) (display parsed) (display ‘error))(lambda(unparsed) (display ‘error)) ; Find the term following the +/- operator; If there is one, extend the expression, save it in the closure,; and once again try to find a suffix; If there isn’t one, this is a bad expression, e.g. A * B + )letrec (got-term (lambda (parsedterm rest)(make-closure (cons ‘expr (list parsedexpr operator parsedterm)) (lambda (has-suffix has-no-suffix) (get-additive-operator rest has-suffix has-no-suffix)))) (no-term (lambda rest) (failure rest))) (get-term-prefix rest got-term no-term))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