Transcription
COS 326 Functional programming: an elegant weapon for the modern age
In 1936, Alonzo Church inventedthe lambda calculus. He calledit a logic, but it was a languageof pure functions -- the world'sfirst programming language.He said:"There may, indeed, be otherapplications of the system thanits use as a logic."Alonzo ChurchPrinceton Prof1929-1967
Alonzo Church1936 -- developed lambda calculusAlan Turing1936 -- developed Turing machinesRobert Harper (CMU): The lambda directly and immediately relevant to this day,rather than something that collects dust on the shelf. No one cares one bit aboutthe details of a Turing Machine; for it fails to address the central issue ofmodularity.
Vastly Abbreviated FP Designer HistoryAlonzo Church:lambda calculus1930’sJohn McCarthy:LISP1958Guy Steele & Gerry Sussman:Schemelate 1970’sRobin Milner, Mads Tofte, & Robert HarperStandard ML1980’sXavier Leroy:Ocaml1990’sDon Syme:F#2000’s4
Where do I fit in?Alonzo ChurchPrinceton Prof1929–1967Robert ConstableDeveloped NuprlThereom ProverBob HarperDevelopedStandard MLSteven KleenePrinceton PhD 1934IAS 1939-1940Greg MorrisettDevelopedTyped Assembly LanguageDavid WalkerPrinceton Prof 2002-
A bit of fun: http://www.malevole.com/mv/misc/killerquiz/m alevole - Program m ing Language Inventor or Serial Killer?1/ 20/ 10 2:34 PMHave a go at these I recently made for E4: Janey Thomson's Marathon · Captcha Invaders · The RatherDifficult Gamehttp:/ / www.m alevole.com / m v/ m isc/ killerquiz/Page 1 of 16
Vastly Abbreviated FP GeneologyLCF TheoremProver (70s)LISP(50s-now)Edinburgh MLScheme(70s-now)Caml(80s-now)Miranda (80s)Haskell(90s - now)Standard ML(90s - now)OCaml(90s - now)Scala(00s - now)F#(now)Racket(00s-now)untypedCoq(80s - now)lazycall-by-valuetyped, polymorphicdependentlytyped
But Why Functional Programming Now? Functional programming will introduce you to new ways tothink about and structure your programs:–––––new reasoning principlesnew abstractionsnew design patternsnew algorithmselegant code Technology trends point to increasing parallelism:– multicore, gpu, data center– functional programming techniques such as map-reduce providea plausible way forward for many applications
Functional Languages: Who’s using them?map-reduce in their data centersScala forcorrectness, maintainability, flexibilityErlang forconcurrency,Haskell formanaging PHPF# in Visual StudioHaskell tosynthesize hardwarewww.artima.com/scalazine/articles/twitter on /haskellwiki/Haskell in industryO’Camlfor reliabilityHaskellfor specifyingequity derivativesCoq proof of4-color theorem
Functional Languages: Join the crowd Elements of functional programming are showing up all over– F# in Microsoft Visual Studio– Scala combines ML (a functional language) with Objects runs on the JVM– C# includes “delegates” delegates functions– Python includes “lambdas” lambdas more functions– Javascript find tutorials online about using functional programmingtechniques to write more elegant code– C libraries for map-reduce enabled functional parallelism at Google– Java has generics and GC– .
COURSE LOGISTICS
Course StaffProf David WalkerTA Naga Kattaoffice: COS 211email: dpw@csoffice: COS 311email: nkatta@csoffice hours: MW 12:20-1office hours: M 2:30-3, T 3-3:30
Resources Web: http://www.cs.princeton.edu/ dpw/courses/cos326-12/ Lecture schedule and readings:– (coursehome)/lectures.php Assignments:– (coursehome)/assignments.php– first assignment due next week: tuesday sept 25! Precepts (Friend 007, 50min, Th 7:30, Fr 11)– first half of semester (intermittent in 2nd half) Install OCaml: (coursehome)/resources.php
Difficult Game. Vastly Abbreviated FP Geneology LCF Theorem . Edinburgh ML Miranda (80s) Haskell (90s - now) Standard ML (90s - now) OCaml (90s - now) Caml (80s-now) F# (now) LISP (50s-now) Scheme (70s-now) lazy typed, polymorphic . -functional programming techniques such as map-reduce provide a plausible way forward for many applications .
