Transcript ppt
Delayed Evaluation • Special forms in Scheme (e.g., if and cond) do not use applicative order evaluation – Only one of two or more expressions is actually evaluated – Evaluation of some expressions is delayed until after another is evaluated (e.g., a then b or c in (if a b c) in Scheme) • With procedures another form of delay may occur – Procedure does some computation before calling another – May decide whether or not to call it at all – Useful especially for recursive calls – selective descent of a data structure, termination conditions, etc. CSE 425: Functional Programming II Lazy Evaluation • Six rules (the Scheme run-time environment follows) – – – – All arguments to user defined functions are delayed All local bindings (e.g., let and letrec) are delayed All arguments to constructors (e.g., cons) are delayed All arguments to other pre-defined functions (e.g., * and +) are forced (to be evaluated as soon as possible) – All function valued arguments are forced – All conditions in selection forms (e.g., if, cond) are forced • Efficiency considerations: using delay, force yourself – It’s efficient not to compute results you don’t need – However, if a delayed expression is repeatedly evaluated then you can lose some of that benefit CSE 425: Functional Programming II Functions as Values • Functions can be computed and returned by other functions, passed as arguments to other functions – I.e., functions are “first class” data values • Composition of one function with another – If f : X → Y and g : Y → Z then (g סf)(x) = g(f(x)) • Composition is itself a higher-order function – Function(s) as parameter(s) and/or returns another function CSE 425: Functional Programming II Stream Oriented Functional Programs • A program may compute only part of a long list – Allows the rest to be ignored if the program halts sooner – A program may make arbitrary progress through a list – Alternatively, allows the list to be unbounded in length • Motivates a model of programs operating on streams – Can abstract away notion of the length of a list – Allows functional programs to handle abstractions like the standard input, output, and error streams, files, etc. – Also known as the generator-filter programming model • Taken farther, supports databases, etc. naturally – Data input, output, and manipulation, user input, file input and output, etc. all handled similarly via interacting functions CSE 425: Functional Programming II Today’s Studio Exercises • We’ll continue to look at ideas from Scott Chapter 10 – Especially delayed evaluation, continuations, etc. • Today’s exercises are again all in C++ – Please take advantage of the on-line reference manual pages that are linked on the course web site – The text books also may be helpful for some exercises – As always, please ask us for help as needed • When done, email your answers to the course account with subject line “Functional Programming Studio II” – Send to [email protected] CSE 425: Functional Programming II