History of Programming Languages Functional ProgrammingCunning PlanGone In Sixty SecondsWhy Study History?Slide 5Slide 6Slide 7Slide 8Slide 9Modern EraSlide 11Slide 12Slide 13Functional ProgrammingStateSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25List Syntax in OCamlFunctional ExampleImperative CodeSlide 29Functional-Style AdvantagesFunctional-Style DisadvantagesML Innovative FeaturesType SystemPattern MatchingPattern Matching MistakesPolymorphismHigher-Order FunctionsThe Story of FoldThe House That Fold BuiltIt’s Lego TimeTougher LegosMap From FoldSorting ExamplesPartial Application and CurryingApplicabilityHomework#1History of Programming LanguagesHistory of Programming Languages Functional ProgrammingFunctional Programming#2Cunning Plan•History Lesson•Functional Programming–OCaml– Types– Pattern Matching– Higher-Order Functions•Basic Syntax•Data Structures• Higher-Order Functions– Fold#3Gone In Sixty Seconds•Imperative: change state, assignments• Structured: if/block/routine control flow• Object-Oriented: message passing (= dynamic dispatch), inheritance• Functional: functions are first-class citizens that can be passed around or called recursively. We can avoid changing state by passing copies.#6#7Surprise Liberal Arts Trivia•The Ulster Cycle (or Red Branch Cycle) is one of the four great sagas of this country's mythology. It includes prominent figures such as Cú Chulainn and queen Méabh, as well as the tragic Deirdre (source of Yeats and Synge plays). The earliest of the stories available is dated to the 8th century and refers to events and characters of the 7th.#8So What's It About?• The longest and most important story of the cycle is the Táin Bó Cúailnge or "Cattle Raid of Cooley", in which Medb raises an enormous army to invade the Cooley peninsula and steal the Ulaid's prize bull [...] Warfare mainly takes the form of cattle raids [...] Cú Chulainn [...] staves off Medb's army for months, slaying every champion the queen sends to meet him. [...] Medb, of course, is not finished with Cú Chulainn, and seeks her revenge on him through more trickery.–Wikipedia and others, emphasis mine• In order words: “A deadly cycle of cattle raids and revenge attacks between some of the country's groups.”#9One Reason Why• Reason is a biological product -- a tool whose power is inherently and substantially restricted. It has improved how we do things; it has not changed why we do things. Reason has generated knowledge enabling us to fly around the world in less than two days. Yet we still travel for the same purposes that drove our ancient ancestors -- commerce, conquest, religion, romance, curiosity, or escape from overcrowding, poverty, and persecution. To deny that reason has a role in setting our goals seems, at first, rather odd. A personal decision to go on a diet or take more exercise appears to be based upon reason. The same might be said for a government decision to raise taxes or sign a trade treaty. But reason is only contributing to the 'how' portion of these decisions; the more fundamental 'why' element, for all of these examples, is driven by instinctive self-preservation, emotional needs, and cultural attitudes. We are usually reluctant to admit the extent to which these forces govern our behavior, and accordingly we often recruit reason to explain and justify our actions.– Donald B. Calne, Within Reason: Rationality and Human Behavior#10Modern Era•1972 – C1972 – CSystems programming, ASMSystems programming, ASM•1983 – Ada1983 – AdaUS DOD, static type safetyUS DOD, static type safety•1983 – C++1983 – C++classes, default args, STLclasses, default args, STL•1987 – Perl 1987 – Perl dynamic scripting languagedynamic scripting language•1990 – Python1990 – Pythoninterp OO + readabilityinterp OO + readability•1991 – Java1991 – Javaportable OO lang (for iTV)portable OO lang (for iTV)•1993 – Ruby1993 – RubyPerl + SmalltalkPerl + Smalltalk•1996 – OCaml1996 – OCamlML + C++ML + C++•2000 – C#2000 – C#“simple” Java + delegates“simple” Java + delegatesI invented the term Object-Oriented, and I did not have C++ in mind. - Alan Kay#11 Time Travel•Back to an earlier time when the US was worried about a Communist “perfect attack”•In Soviet Russia, noun verbs you! (-1 Redundant)#13Oh what a tangled web we weave,When first we practise to deceive!- Sir Walter Scott, 1771-1832FunctionalObject- OrientedStructured ImperativeThere are only two kinds of programming languages: those people always [complain] about and those nobody uses. - Bjarne StroustrupI fear the new OO systems may suffer the fate of LISP, in that they can do many things, but the complexity of the class hierarchies may cause them to collapse under their own weight.- Bill JoyComputer language design is just like a stroll in the park. Jurassic Park, that is. - Larry Wall#14Functional Programming•You know OO and Structured Imperative•Functional Programming–Computation = evaluating (math) functions– Avoid “global state” and “mutable data”– Get stuff done = apply (higher-order) functions– Avoid sequential commands•Important Features– Higher-order, first-class functions–Closures and recursion– Lists and list processing#15State•The state of a program is all of the current variable and heap values• Imperative programs destructively modify existing stateSET {x}add_elem(SET, y)#16State•The state of a program is all of the current variable and heap values• Imperative programs destructively modify existing stateSET {x,y}#17State•The state of a program is all of the current variable and heap values• Imperative programs destructively modify existing state••Functional programs yield new similar states over timeSET {x,y}SET_1 {x}SET_2 = add_elem(SET_1, y)#18State•The state of a program is all of the current variable and heap values• Imperative programs destructively modify existing state••Functional programs yield new similar states over timeSET {x,y}SET_1 {x} SET_2 {x,y}SET_2 = add_elem(SET_1, y)#19Basic OCaml•Let's Start With Cdouble avg(int x, int y) { double z = (double)(x + y); z = z / 2; printf(“Answer is %g\n”, z); return z; }#20Basic OCaml•Let's Start With Cdouble avg(int x, int y) { double z = (double)(x + y); z = z / 2; printf(“Answer is %g\n”, z); return z; }let avg (x:int) (y:int) : float = beginlet avg