'&$%CSE 341:Programming LanguagesWinter 2005Lecture 7— Motivation and First-Class FunctionsCSE341 Winter 2005, Lecture 7 1'&$%Today• Finish course motivaton• Summarize what we’ve learned with a concise and well-knownnotation for recursively-defined language constructs• Begin first-class functionsCSE341 Winter 2005, Lecture 7 2'&$%Why these 3?Functional programming (ML, Scheme) encourages recursion,discourages mutation, provides elegant, lightweight support forfirst-class code. Support for extensibility complements OO.• ML has a polymorphic type system (vindication imminent!)complementary to OO-style subtyping, a rich module system forabstract types, and rich pattern-matching.• Scheme has dynamic typing, “good” macros, fascinating controloperators, and a minimalist design.• Smalltalk has classes but not types, an unconventionalenvironment, and a complete commitment to OO.Runners-up: Haskell (laziness and purity), Prolog (unification andbacktracking), thousands of others...CSE341 Winter 2005, Lecture 7 3'&$%Why not some popular ones?• Java: you know it, will contrast at end of course (e.g., interfaces,anonymous inner classes, container types)• C: lots of “implementation-dependent” behavior (a bad property),and we have CSE303• C++: an enormous language, and unsafe like C• Perl: advantages (strings, files, ...) not foci of this course. Pythonor Ruby would be closer.CSE341 Winter 2005, Lecture 7 4'&$%Are these useful?The way we use ML/Scheme/Smalltalk in 341 can make them seemalmost “silly” precisely because we focus on interesting languageconcepts“Real” programming needs file I/O, strings, floating-point, graphicslibraries, project managers, unit testers, threads, foreign-functioninterfaces, ...• These languages have all that and more!• If Java were in 341, it would seem “silly” tooSomewhat outdated links:• ML: http://www.cs.princeton.edu/˜appel/smlnj/projects.html• OCaml: http://caml.inria.fr/users programs-eng.htmlCSE341 Winter 2005, Lecture 7 5'&$%Summary and Some NotationLearned the syntax, typing rules, and semantics for (a big) part of MLCan summarize abstract syntax with (E)BNF. Informally:t ::= int | bool | unit | dtname| t1-> t2| t1* t2| {x1=t1, ..., xn=tn}e ::= 34 | x | (e1,e2) | if e1then e2else e3| let b1... bnin e end | e1e2| case e of p1=> e1| ... | pn=> en| e1+ e2| {x1=e1, ..., xn=en} | C eb ::= val p = e | fun f p = e| datatype dtname = C1 of t1| ... | Cn of tnp ::= 34 | x | _ | C p | (p1,p2) | {x1=p1, ..., xn=pn}Things left out of this grammar: n-tuples, field-accessors,floating-point, boolean constants, andalso/orelse, lists, ...CSE341 Winter 2005, Lecture 7 6'&$%First-Class Functions• Functions are values. (Variables in the environment are bound tothem.)• We can pass functions to other functions.– Factor common parts and abstract different parts.• Most polymorphic functions take functions as arguments.– Non-example: fun f x = 42• Some functions taking functions are polymorphic.CSE341 Winter 2005, Lecture 7 7'&$%Type Inference and PolymorphismML can infer function types based on function bodies. Possibilities:• The argument/result must be one specific type.• The argument/result can be any type, but may have to be thesame type as other parts of argument/result.• Some hand-waving about “equality types”We will study this parametric polymorphism more later.Without it, ML would be a pain (e.g., a different list library for everylist-element type).Fascinating: If f:int->int, there are lots of values f could return. Iff:’a->’a, whenever f returns, it returns its argument!CSE341 Winter 2005, Lecture 7 8'&$%Anonymous FunctionsAs usual, we can write functions anywhere we write expressions.• We already could:(let fun f x = e in f end)• Here is a more concise way (better style when possible):(fn x => e)• Cannot do this for recursive functions (why?)CSE341 Winter 2005, Lecture 7 9'&$%Returning FunctionsSyntax note: -> “associates to the right”• t1->t2->t3 means t1->(t2->t3)Again, there is nothing new here.The key question: What about free variables in a function value?What environment do we use to evaluate them?Are such free variables useful?You must understand the answers to move beyond being a noviceprogrammer.CSE341 Winter 2005, Lecture 7
View Full Document
Unlocking...