Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Functional Languages and Higher-Order Functions 1Functional Languages andHigher-Order FunctionsLeonidas FegarasFunctional Languages and Higher-Order Functions 2First-Class Functions•Data values are first-class if they can–be assigned to local variables–be components of data structures–be passed as arguments to functions–be returned from functions–be created at run-time•How functions are treated by programming languages?Language passed as arguments returned from functions nested scopeJava No No NoC Yes Yes NoC++ Yes Yes NoPascal Yes No YesModula-3 Yes No YesScheme Yes Yes YesML Yes Yes YesFunctional Languages and Higher-Order Functions 3Function Types•A new type constructor(T1,T2,...,Tn)  T0Takes n arguments of type T1, T2, ..., Tn and returns a value of type T0Unary function: T1  T0 Nullary function: ()  T0•Example:sort ( A: int[], order: (int,int)  boolean ) { for (int i = 0; i<A.size; i++) for (int j=i+1; j<A.size; j++) if (order(A[i],A[j])) switch A[i] and A[j]; } boolean leq ( x: int, y: int ) { return x <= y; } boolean geq ( x: int, y: int ) { return x >= y; } sort(A,leq) sort(A,geq)Functional Languages and Higher-Order Functions 4How can you do this in Java?interface Comparison { boolean compare ( int x, int y );}void sort ( int[] A, Comparison cmp ) {for (int i = 0; i<A.length; i++) for (int j=i+1; j<A.length; j++) if (cmp.compare(A[i],A[j])) ...}class Leq implements Comparison { boolean compare ( int x, int y ) { return x <=y; }}sort(A,new Leq());Functional Languages and Higher-Order Functions 5... or betterclass Comparison { abstract boolean compare ( int x, int y );}sort(A,new Comparison() { boolean compare ( int x, int y ) { return x <=y; } })Functional Languages and Higher-Order Functions 6Nested Functions•Without nested scopes, a function may be represented as a pointer to its code•Functional languages (Scheme, ML, Haskell), as well as Pascal and Modula-3, support nested functions–They can access variables of the containing lexical scope plot ( f: (float)  float ) { ... } plotQ ( a, b, c: float ) { p ( x: float ) { return a*x*x + b*x + c; } plot(p);}•Nested functions may access and update free variables from containing scopes•Representing functions as pointers to code is not good any moreFunctional Languages and Higher-Order Functions 7Closures•Nested functions may need to access variables in previous frames in the stack•Function values is a closure that consists of–a pointer to code–an environment (dictionary) for free variables•Implementation of the environment:–It is simply a static link to the beginning of the frame that defined the function plot ( f: (float)  float ) { ... } plotQ ( a, b, c: float ) { p ( x: float ) { return a*x*x + b*x + c; } plot(p);}plotQplotfpcodefor pclosure of pRun-time stacktopbottomFunctional Languages and Higher-Order Functions 8What about Returned Functions?•If the frame of the function that defined the passing function has been popped out from the run-time stack, the static link will be a dangling pointer()  int make_counter () {int count = 0;int inc () { return count++; }return inc;}make_counter()() + make_counter()();c = make_counter();c()+c();Functional Languages and Higher-Order Functions 9Frames in Heap!•Solution: heap-allocate function frames–No need for run-time stack–Frames of all lexically enclosing functions are reachable from a closure via static link chains–The GC will collect unused frames•Problem: Frames will make a lot of garbage look reachableFunctional Languages and Higher-Order Functions 10Escape Analysis•Local variables need to be–stored in heap only if they can escape–accessed after the defining function returns•It happens only if–the variable is referenced from within some nested function–the nested function is returned or passed to some function that might store it in a data structure•Variables that do not escape are allocated on a stack frame rather than on heap•No escaping variable => no heap allocation•Escape analysis must be global–Often approximate (conservative analysis)Functional Languages and Higher-Order Functions 11Functional Programming Languages•Programs consist of functions with no side-effects•Functions are first class values•Build modular programs using function composition•No accidental coupling between components•No assignments, statements, for-loops, while-loops, etc•Supports higher-level, declarative programming style•Automatic memory management (garbage collection)•Emphasis on types and type inference–Built-in support for lists and other recursive data types–Type inference is like type checking but no type declarations are required•Types of variables and expressions can be inferred from context–Parametric data types and polymorphic type inference•Strict vs lazy functional programming languagesFunctional Languages and Higher-Order Functions 12Lambda Calculus•The theoretical foundation of functional languages is lambda calculus–Formalized by Church in 1941–Minimal in form–Turing-complete•Syntax: if e1, e2, and e are expressions in lambda calculus, so are–Variable: v–Application: e1 e2–Abstraction: v. e•Bound vs free variables•Beta reduction:–(v. e1) e2  e1[e2/v](e1 but with all free occurrences of v in e1 replaced by e2)–need to be careful to avoid the variable capturing problem (name clashes)Functional Languages and Higher-Order Functions 13Church encoding: Integers•Integers:–0 = s. z. z–1 = s. z. s z–2 = s. z. s s z–6 = s. z. s s s s s s z–... they correspond to successor (s) and zero (z)•Simple arithmetic:–add = n. m. s. z. n s (m s z)add 2 3 = (n. m. s. z. n s (m s z)) 2 3=  s. z. 2 s (3 s z)=  s. z. (s. z. s s z) s ((s. z. s s s z) s z)=  s. z. (s. z. s s z) s (s s s z)=  s. z. s s s s s z= 5Functional Languages and Higher-Order Functions 14Other Types•Booleans–true = t. f. t–false = t. f. f–if pred e1 e2 = pred e1 e2•eg, if pred is true, then (t. f. t) e1 e2 = e1•Lists–nil = c. n. n–[2,5,8] = c. n. c 2 (c 5 (c 8 n))–cons = x. r.  c. n. c x (r c n)•cons 2