111Streams and Streams and Lazy EvaluationLazy Evaluationin Lisp in Lisp 22UMBCUMBCan Honors University in Marylandan Honors University in MarylandOverviewOverviewDifferent models of expression evaluationDifferent models of expression evaluationLazy vs. eager evaluationLazy vs. eager evaluationNormal vs. applicative order evaluationNormal vs. applicative order evaluationComputing with streams in LispComputing with streams in Lisp33UMBCUMBCan Honors University in Marylandan Honors University in MarylandMotivationMotivation••Streams in UnixStreams in Unix••Modeling objects changing with time without Modeling objects changing with time without assignment.assignment.••Describe the timeDescribe the time--varying behavior of an object varying behavior of an object as an infinite sequence x1, x2,as an infinite sequence x1, x2,……••Think of the sequence as representing a Think of the sequence as representing a function x(t).function x(t).••Make the use of lists as conventional interface Make the use of lists as conventional interface more efficient.more efficient.44UMBCUMBCan Honors University in Marylandan Honors University in MarylandUnix PipesUnix PipesUnixUnix’’s pipe supports a kind of stream oriented processings pipe supports a kind of stream oriented processingE.g.: E.g.: % cat mailbox | addresses | sort | % cat mailbox | addresses | sort | uniquniq| more| moreOutput from one process becomes input to another. Data Output from one process becomes input to another. Data flows one bufferflows one buffer--full at a timefull at a timeBenefits: Benefits: we may not have to wait for one stage to finish before we may not have to wait for one stage to finish before another can start; another can start; storage is minimized; storage is minimized; works for large and even works for large and even infiniteinfinitestreams of datastreams of datacat addr sort uniq more255UMBCUMBCan Honors University in Marylandan Honors University in MarylandEvaluation OrderEvaluation OrderFunctional programs are evaluated following a Functional programs are evaluated following a reductionreduction(or evaluation or simplification) (or evaluation or simplification) processprocessThere are two common ways of reducing There are two common ways of reducing expressionsexpressionsApplicative orderApplicative orderEager evaluation Eager evaluation ––evaluate expressions if evaluate expressions if you *might* need their valueyou *might* need their valueNormal orderNormal orderLazy evaluation Lazy evaluation ––evaluate expressions only evaluate expressions only when you *know* you need their valuewhen you *know* you need their value66UMBCUMBCan Honors University in Marylandan Honors University in MarylandApplicative OrderApplicative OrderIn applicative order, expressions at In applicative order, expressions at evaluated following the parsing tree evaluated following the parsing tree (deeper expressions are evaluated first)(deeper expressions are evaluated first)This is the evaluation order used in most This is the evaluation order used in most programming languagesprogramming languagesItIt’’s the default order for Lisp, in particulars the default order for Lisp, in particularEG: (square (+ a (* b 2)))EG: (square (+ a (* b 2)))77UMBCUMBCan Honors University in Marylandan Honors University in Maryland(square (+ A (* B 2)))(square (+ A (* B 2)))SQUARE+*AB212345688UMBCUMBCan Honors University in Marylandan Honors University in MarylandNormal OrderNormal OrderIn normal order, expressions are evaluated only In normal order, expressions are evaluated only if and when their value is neededif and when their value is neededHence: lazy evaluationHence: lazy evaluationThis is needed for some special forms This is needed for some special forms e.g., (if (< a 0) (print e.g., (if (< a 0) (print ‘‘foo) (print foo) (print ‘‘bar))bar))Some languages use normal order evaluation as Some languages use normal order evaluation as their default.their default.Normal is sometimes more efficient than Normal is sometimes more efficient than applicative order since unused computations applicative order since unused computations need not be doneneed not be doneNormal order can handle expressions that Normal order can handle expressions that never converge to normal formsnever converge to normal forms399UMBCUMBCan Honors University in Marylandan Honors University in MarylandMotivation: Motivation: Sum primes between N and MSum primes between N and M••Traditional iterative versionTraditional iterative version(defun sum-primes (lo hi);; sum the primes between LO and HI(do ((sum 0))((> lo hi) sum) (if (prime? lo) (setf sum (+ sum lo)))(setf lo (1+ lo))))••And the And the ““functionalfunctional””version:version:(defun sum-primes (lo hi);; sum the primes between LO and HI(reduce #’+ 0 (filter #’prime? (interval lo hi))))(defun interval (lo hi);; return a list of the integers between lo and hi(if (> lo hi) nil (cons lo (interval (1+ lo) hi))))1010UMBCUMBCan Honors University in Marylandan Honors University in MarylandMotivationMotivationThe functional version is interesting and The functional version is interesting and conceptually elegant, but inefficient.conceptually elegant, but inefficient. Constructing, copying and (ultimately) garbage collecting the lists adds a lot of overhead Experienced Lispers know that the best way to optimize a program is to eliminate unnecessary consing Worse yet, suppose we want to know the Worse yet, suppose we want to know the second prime larger than a million?second prime larger than a million?(first (rest (filter prime? (interval 1000000 1100000))))Can we use the idea of a stream to make Can we use the idea of a stream to make this approach viable?this approach viable?1111UMBCUMBCan Honors University in Marylandan Honors University in MarylandStreams in LispStreams in Lisp• We can push features for streams into a programming language.• Makes some approaches to computation simple and elegant• Lisp’s closure mechanism used to implement these features.• Can formulate programs elegantly as sequence manipulators while attaining the efficiency of incremental computation.1212UMBCUMBCan Honors University in Marylandan Honors University in MarylandStreams in