CSE 3302 Programming LanguagesDisclaimerResourcesHistoryFunctional ProgrammingFunctional Programming LanguagesWe can use functional programming in imperative languagesWhy does it matter, anyway?Functional Programming Languages in UseSchemeScheme: Lisp dialectExpressionsEvaluation of ExpressionsEager EvaluationLazy Evaluation: Special FormsSlide 16Slide 17Other Special FormsListsData structuresBox diagramsOther list manipulation operations: based on car, cdr, consLambda expressions /function valuesFunction values as dataHigher-order functionsSlide 26let expressions as lambdas:CSE 3302 Programming LanguagesChengkai LiFall 2007Functional Programming Language(Introduction and Scheme)Lecture 17 – Functional Programming, Spring 20081CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 2008Disclaimer•Many of the slides are based on “Introduction to Functional Programming” by Graham Hutton, lecture notes from Oscar Nierstrasz, and lecture notes of Kenneth C. Louden.Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20082Resources•Textbook: Chapter 11•Tutorial:–The Scheme Programming Language http://www.scheme.com/tspl3/(Chapter 1-2)–Yet Another Haskell Tutorial http://www.cs.utah.edu/~hal/htut(Chapter 1-4, 7)•Implementation:•DrScheme http://www.drscheme.org/ •Hugs http://www.haskell.org/hugs/ (download WinHugs)•(Optional) Further reading:–Reference manual:Haskell 98 Report http://haskell.org/haskellwiki/Definition–A Gentle Introduction to Haskell 98 http://www.haskell.org/tutorial/Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20083Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20084.4HistoryLambda Calculus(Church, 1932-33)formal model of computationLisp (McCarthy, 1960)Scheme, 70ssymbolic computations with listsAPL (Iverson, 1962)algebraic programming with arraysISWIM (Landin, 1966)let and where clausesequational reasoning; birth of “pure” functional programming ...ML (Edinburgh, 1979)Caml 1985, Ocamloriginally meta language for theorem provingSASL, KRC, Miranda(Turner, 1976-85)lazy evaluationHaskell(Hudak, Wadler, et al., 1988)“Grand Unification” of functional languages ...5Functional Programming•Functional programming is a style of programming:Imperative Programming:–Program = Data + Algorithms OO Programming:–Program = Object. message (object)Functional Programming:–Program = Functions Functions•Computation is done by application of functionsLecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20086Functional Programming Languages•A functional language supports and advocates for the style of FP.•Important Features:Everything is function (input->function->output)No variables or assignments ( only constant values, arguments, and returned values. Thus no notion of state, memory location)No loops (only recursive functions)No side-effect (Referential Transparency): the value of a function depends only on the values of its parameters. Evaluating a function with the same parameters gets the same results. There is no state. Evaluation order or execution path don’t matter. (random() and getchar() are not referentially transparent.)Functions are first-class values: functions are values, can be parameters and return values, can be composed.Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 2008Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20087We can use functional programming in imperative languages•Imperative style int sumto(int n){ int i, sum = 0; for(i = 1; i <= n; i++) sum += i; return sum;}•Functional style: int sumto(int n){ if (n <= 0) return 0; else return sumto(n-1) + n;}Why does it matter, anyway?The advantages of functional programming languages:•Simple semantics, concise, flexible•``No’’ side effect•Less bugsIt does have drawbacks:•Execution efficiency•More abstract and mathematical, thus more difficult to learn and use.Even if we don’t use FP languages:•Features of recursion and higher-order functions have gotten into most programming languages.Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20088Functional Programming Languages in UsePopular in prototyping, mathematical proof systems, AI and logic applications, research and education.Scheme:Document Style Semantics and Specification Language (SGML stylesheets) GIMP Guile (GNU’s official scripting language)EmacsHaskellLinspire (commerical Debian-based Linux distribution)Xmonad (X Window Manager)XSLT (Extensible Stylesheet Language Transformations)Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 20089Lecture 17 – Functional Programming, Spring 200810CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 2008SchemeLecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 200811Scheme: Lisp dialect•Syntax (slightly simplified):expression atom | listatom number | string | identifier | character | booleanlist '(' expression-sequence ')'expression-sequence expression expression-sequence | expression•Everything is an expression: programs, data, … Thus programs are executed by evaluating expressions.•Only 2 basic kinds of expressions: –atoms: unstructured–lists: the only structure (a slight simplification).Lecture 17 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT-Arlington ©Chengkai Li, 200812Expressions42 —a number"hello" —a string#T —the Boolean value "true"#\a —the character 'a'(2.1 2.2 3.1) —a list of numbershello —a identifier(+ 2 3) —a list (identifier "+" and two numbers)( (+ 2 3) (/ 6 2)) —a list (identifier "*" and two lists)Evaluation of ExpressionsPrograms are executed by evaluating expressions. Thus semantics are defined by evaluation rules of expressions.Evaluation Rules:•number | string: evaluate to itself•Identifier: looked up in the environment, i.e., dynamically maintained symbol table•List: recursively evaluate the elements (more details in following slides)Lecture 17 – Functional Programming,
View Full Document