CSCI 330: Programming Language Concepts Instructor: Pranava K. Jha Functional Languages Functional Programming вЂў Models a program as a mathematical function mapping the inputs to the outputs. вЂў Avoids the notion of state and mutable data, and therefore has no side effects. вЂў Has declarative flow of control; promotes function composition instead of statement composition. вЂў Influenced by lambda calculus. Historical Origins вЂў The functional models grew out of work undertaken by Alan Turing, Alonzo Church, Stephen Kleene, Emil Post, etc. during 1930s. вЂ“ Different formalizations of the notion of an algorithm, or effective procedure, based on automata, symbolic manipulation, recursive function definitions, and combinatorics. вЂў These results led Church to conjecture that any intuitively appealing model of computing would be equally powerful as well. вЂ“ This conjecture is known as ChurchвЂ™s thesis. Historical Origins вЂў ChurchвЂ™s model of computing is called the lambda calculus. вЂ“ Based on the notion of parameterized expressions (with each parameter introduced by an occurrence of the letter О»вЂ”hence the notationвЂ™s name. вЂ“ Lambda calculus was the inspiration for functional programming. вЂ“ One employs it to compute by substituting parameters into expressions, just as one computes in a high-level functional program by passing arguments to functions. Functional Programming Concepts вЂў Functional languages such as Lisp, Scheme, FP, ML, Miranda, and Haskell are an attempt to realize Church's lambda calculus in practical form as a programming language вЂў Key idea: Do everything by composing functions. вЂ“ no mutable state вЂ“ no side effects Concepts in Functional Programming вЂў вЂў вЂў вЂў вЂў вЂў вЂў First-class function values and higher-order functions Extensive polymorphism List types and operators Recursion Structured function returns Constructors (aggregates) for structured objects Garbage collection Constructs in Functional Programming вЂў Building blocks are functions. вЂў No statement composition, but function composition. вЂў No variable assignments, but a local variable can be bound to a single value. вЂў No loops, but recursion. вЂў Conditional flow with if-then-else or input patterns. Examples from Haskell gcd a b | a == b = a | a > b = gcd (a-b) b | a < b = gcd a (b-a) fact 0 = 1 fact n = n * fact (n-1) Recursion does a nifty job of replacing looping x := 0; i := 1; j := 100; while i < j do x := x + i*j; i := i + 1; j := j вЂ“ 1 end while return x becomes f(0,1,100) where f(x, i, j) == if i < j then f (x + i*j, i+1, j-1) else x Functional Programming Concepts вЂў Pure Lisp is purely functional; all other Lisps have imperative features вЂў All early Lisps dynamically scoped вЂ“ Not clear whether this was deliberate or if it happened by accident вЂў Scheme and Common Lisp statically scoped вЂ“ Common Lisp provides dynamic scope as an option for explicitly-declared special functions вЂ“ Common Lisp now THE standard Lisp вЂў Very big; complicated (The Ada of functional programming) Functional Programming Concepts вЂў Scheme is a particularly elegant Lisp вЂў Other functional languages вЂ“ ML вЂ“ Miranda вЂ“ Haskell вЂ“ FP вЂў Haskell is the leading language for research in functional programming.