CSE 341:Programming LanguagesAutumn 2005Lecture 7 — Motivation; BNF; First-Class FunctionsCSE 341 Autumn 2005, Lecture 7 1Today• (course motivation)• Summarize what we’ve learned with a concise and well-knownnotation for recursively-defined language constructs• Begin first-class functionsCSE 341 Autumn 2005, Lecture 7 2Why these 3 Languages?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 s yste m (vindication imminent! )complementary t o OO-s tyle 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.CSE 341 Autumn 2005, Lecture 7 3Runners-UpRunners-up: Miranda (laziness, simplicity and purity), Haskell(laziness, nonproprietary implementation, but difficult type system),Prolog (unification and backtracking), CPR(R) (everything that Prologhas plus constraints).There are thousands of other languages as well . . .CSE 341 Autumn 2005, Lecture 7 4Why not some popular ones?• Java: you’ve already studied it in 142/143. We’ll look at someadditional features at the end of course and compare it with theother languages we’ve been studying (e.g., interfaces, anonymousinner classes, container types)• C: lots of “implementation-dependent” behavior (a bad prope rty),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.CSE 341 Autumn 2005, Lecture 7 5Are these useful?We focus on interesting language concepts in ML/Scheme/Smalltalk.“Real” programming needs file I/O, s trings, floating-point, graphicslibraries, project managers, unit testers, threads, foreign-functioninterfaces, . . .• These languages have all that and more!• Just not course focusCSE 341 Autumn 2005, Lecture 7 6Summary 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, ...CSE 341 Autumn 2005, Lecture 7 7First-Class Functions• Functions are values. (Variables in the e nvironment are bound tothem.)• We c an pass functions to other functions.– Factor common parts and abstract different parts.• We c an return functions as values from other functions.CSE 341 Autumn 2005, Lecture 7 8Type 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 ty pe as other parts of argument/result.• Some hand-waving about “equality types”We w ill study this parametric polym orphism more later.Without it, ML would be a pain (e.g., a different list library for everylist-element type).Curious fact: If f:int->int, there are lots of values f could return. Iff:’a->’a, whenever f returns, it returns its argument!CSE 341 Autumn 2005, Lecture 7 9Anonymous 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 (bette r style when poss ible):(fn x => e)• Cannot do this for recursive functions (why?)CSE 341 Autumn 2005, Lecture 7 10Returning 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 t o mov e beyond being a noviceprogrammer.CSE 341 Autumn 2005, Lecture 7
View Full Document
Unlocking...