Section4 5

Information about Section4 5

Published on June 17, 2007

Author: Barbara

Source: authorstream.com

Content

Declarative Programming Techniques Lazy Execution (VRH 4.5):  Declarative Programming Techniques Lazy Execution (VRH 4.5) Carlos Varela RPI Adapted with permission from: Seif Haridi KTH Peter Van Roy UCL Overview:  Overview What is declarativeness? Classification, advantages for large and small programs Control Abstractions Iterative programs Higher-order programming Basic operations, loops, data-driven techniques, laziness, currying Modularity and non-declarative needs File and window I/O, large-scale program structure Limitations and extensions of declarative programming Lazy Evaluation Lazy evaluation:  Lazy evaluation The functions written so far are evaluated eagerly (as soon as they are called) Another way is lazy evaluation where a computation is done only when the result is needed declare fun lazy {Ints N} N|{Ints N+1} end Calculates the infinite list: 0 | 1 | 2 | 3 | ... Lazy evaluation (2):  Lazy evaluation (2) Write a function that computes as many rows of Pascal’s triangle as needed We do not know how many beforehand A function is lazy if it is evaluated only when its result is needed The function PascalList is evaluated when needed fun lazy {PascalList Row} Row | {PascalList {AddList Row {ShiftRight Row}}} end Lazy evaluation (3):  Lazy evaluation (3) Lazy evaluation will avoid redoing work if you decide first you need the 10th row and later the 11th row The function continues where it left off declare L = {PascalList [1]} {Browse L} {Browse L.1} {Browse L.2.1} Landlt;Futureandgt; [1] [1 1] Lazy execution:  Lazy execution Without lazyness, the execution order of each thread follows textual order, i.e., when a statement comes as the first in a sequence it will execute, whether or not its results are needed later This execution scheme is called eager execution, or supply-driven execution Another execution order is that a statement is executed only if its results are needed somewhere in the program This scheme is called lazy evaluation, or demand-driven evaluation Example:  Example B = {F1 X} C = {F2 Y} D = {F3 Z} A = B+C Assume F1, F2 and F3 are lazy functions (see Haskell) B = {F1 X} and C = {F2 Y} are executed only if and when their results are needed in A = B+C D = {F3 Z} is not executed since it is not needed Example:  Example In lazy execution, an operation suspends until its result are needed The suspended operation is triggered when another operation needs the value for its arguments In general multiple suspended operations could start concurrently B = {F1 X} C = {F2 Y} A = B+C Demand Example II:  Example II In data-driven execution, an operation suspends until the values of its arguments results are available In general the suspended computation could start concurrently B = {F1 X} C = {F2 Y} A = B+C Data driven Using Lazy Streams:  Using Lazy Streams fun {Sum Xs A Limit} if Limitandgt;0 then case Xs of X|Xr then {Sum Xr A+X Limit-1} end else A end end local Xs S in Xs={Ints 0} S={Sum Xs 0 1500} {Browse S} end How does it work?:  How does it work? fun {Sum Xs A Limit} if Limitandgt;0 then case Xs of X|Xr then {Sum Xr A+X Limit-1} end else A end end fun lazy {Ints N} N | {Ints N+1} end local Xs S in Xs = {Ints 0} S={Sum Xs 0 1500} {Browse S} end Improving throughput:  Improving throughput Use a lazy buffer It takes a lazy input stream In and an integer N, and returns a lazy output stream Out When it is first called, it first fills itself with N elements by asking the producer The buffer now has N elements filled Whenever the consumer asks for an element, the buffer in turn asks the producer for another element The buffer example:  The buffer example The buffer:  The buffer fun {Buffer1 In N} End={List.drop In N} fun lazy {Loop In End} In.1|{Loop In.2 End.2} end in {Loop In End} end Traversing the In stream, forces the producer to emit N elements The buffer II:  The buffer II fun {Buffer2 In N} End = thread {List.drop In N} end fun lazy {Loop In End} In.1|{Loop In.2 End.2} end in {Loop In End} end Traversing the In stream, forces the producer to emit N elements and at the same time serves the consumer The buffer III:  The buffer III fun {Buffer3 In N} End = thread {List.drop In N} end fun lazy {Loop In End} E2 = thread End.2 end In.1|{Loop In.2 E2} end in {Loop In End} end Traverse the In stream, forces the producer to emit N elements and at the same time serves the consumer, and requests the next element ahead Larger Example:The Sieve of Eratosthenes:  Larger Example: The Sieve of Eratosthenes Produces prime numbers It takes a stream 2...N, peals off 2 from the rest of the stream Delivers the rest to the next sieve Sieve Filter Sieve Xs Xr X Ys Zs X|Zs Lazy Sieve:  Lazy Sieve fun lazy {Sieve Xs} X|Xr = Xs in X | {Sieve {LFilter Xr fun {$ Y} Y mod X \= 0 end }} end fun {Primes} {Sieve {IntsFrom 2}} end Lazy Filter:  Lazy Filter For the Sieve program we need a lazy filter fun lazy {LFilter Xs F} case Xs of nil then nil [] X|Xr then if {F X} then X|{LFilter Xr F} else {LFilter Xr F} end end end Define streams implicitly:  Define streams implicitly Ones = 1 | Ones Infinite stream of ones 1 cons Ones Define streams implicitly:  Define streams implicitly Xs = 1 | {LMap Xs fun {$ X} X+1 end} What is Xs ? 1 cons +1 Xs? The Hamming problem:  The Hamming problem Generate the first N elements of stream of integers of the form: 2a 3b5c with a,b,c  0 (in ascending order) The Hamming problem:  The Hamming problem Generate the first N elements of stream of integers of the form: 2a 3b5c with a,b,c  0 (in ascending order) The Hamming problem:  The Hamming problem Generate the first N elements of stream of integers of the form: 2a 3b5c with a,b,c  0 (in ascending order) 1 cons H Lazy File Reading:  Lazy File Reading fun {ToList FO} fun lazy {LRead} L T in if {File.readBlock FO L T} then T = {LRead} else T = nil {File.close FO} end L end {LRead} end This avoids reading the whole file in memory List Comprehensions:  List Comprehensions Abstraction provided in lazy functional languages that allows writing higher level set-like expressions In our context we produce lazy lists instead of sets The mathematical set expression {x*y | 1x 10, 1y x} Equivalent List comprehension expression is [X*Y | X = 1..10 ; Y = 1..X] Example: [1*1 2*1 2*2 3*1 3*2 3*3 ... 10*10] List Comprehensions:  List Comprehensions The general form is [ f(x,y, ...,z) | x  gen(a1,...,an) ; guard(x,...) y  gen(x, a1,...,an) ; guard(y,x,...) .... ] No linguistic support in Mozart/Oz, but can be easily expressed Example 1:  Example 1 z = [x#x | x  from(1,10)] Z = {LMap {LFrom 1 10} fun{$ X} X#X end} z = [x#y | x  from(1,10), y  from(1,x)] Z = {LFlatten {LMap {LFrom 1 10} fun{$ X} {LMap {LFrom 1 X} fun {$ Y} X#Y end } end } } Example 2:  Example 2 z = [x#y | x  from(1,10), y  from(1,x), x+y10] Z ={LFilter {LFlatten {LMap {LFrom 1 10} fun{$ X} {LMap {LFrom 1 X} fun {$ Y} X#Y end } end } } fun {$ X#Y} X+Y=andlt;10 end} } Implementation of lazy execution:  Implementation of lazy execution s ::= skip empty statement | ... | thread s1 end thread creation | {ByNeed fun{$} e end x} by need statement The following defines the syntax of a statement, s denotes a statement zero arity function variable Implementation:  Implementation some statement f x {ByNeed fun{$} e end X,E } stack store A function value is created in the store (say f) the function f is associated with the variable x execution proceeds immediately to next statement f Implementation:  Implementation some statement f x : f {ByNeed fun{$} e end X,E } stack store A function value is created in the store (say f) the function f is associated with the variable x execution proceeds immediately to next statement f (fun{$} e end X,E) Accessing the ByNeed variable:  Accessing the ByNeed variable X = {ByNeed fun{$} 111*111 end} (by thread T0) Access by some thread T1 if X andgt; 1000 then {Browse hello#X} end or {Wait X} Causes X to be bound to 12321 (i.e. 111*111) Implementation:  Implementation Thread T1 X is needed start a thread T2 to execute F (the function) only T2 is allowed to bind X Thread T2 Evaluate Y = {F} Bind X the value Y Terminate T2 Allow access on X Lazy functions:  Lazy functions fun lazy {From N} N | {From N+1} end fun {From N} fun {F} N | {From N+1} end in {ByNeed F} end Exercises:  Exercises Write a lazy append list operation LazyAppend. Can you also write LazyFoldL? Why or why not? Exercise VRH 4.11.5 (pg 339) Exercise VRH 4.11.10 (pg 341) Exercise VRH 4.11.13 (pg 342) Exercise VRH 4.11.17 (pg 342) Read VRH Sections 6.4.3, 7.1 and 7.2

Related presentations


Other presentations created by Barbara

Solar System
17. 06. 2007
0 views

Solar System

Advanced SQL Injection
30. 08. 2007
0 views

Advanced SQL Injection

PrivateExchange
22. 04. 2008
0 views

PrivateExchange

07 fordjob1
17. 04. 2008
0 views

07 fordjob1

20061011114434853
13. 04. 2008
0 views

20061011114434853

Bruce Lambert Army Corps
10. 04. 2008
0 views

Bruce Lambert Army Corps

SPAC2007 Juan Rodriguez
09. 04. 2008
0 views

SPAC2007 Juan Rodriguez

Chapter7
07. 04. 2008
0 views

Chapter7

tourism chapter 04
30. 03. 2008
0 views

tourism chapter 04

LAC International Trade
28. 03. 2008
0 views

LAC International Trade

feb2006final
27. 03. 2008
0 views

feb2006final

virtualcommunities
26. 03. 2008
0 views

virtualcommunities

Mickey Mouse
26. 06. 2007
0 views

Mickey Mouse

1who gets tb in nyc
27. 09. 2007
0 views

1who gets tb in nyc

lijian
12. 10. 2007
0 views

lijian

O2 Diesel
08. 11. 2007
0 views

O2 Diesel

American Romanticism
30. 08. 2007
0 views

American Romanticism

233nm60
30. 08. 2007
0 views

233nm60

MBA Lecture Series v2
30. 08. 2007
0 views

MBA Lecture Series v2

hep2005 talk MarkVagins
09. 10. 2007
0 views

hep2005 talk MarkVagins

Control Tech
05. 12. 2007
0 views

Control Tech

DasuCMSTriggerUCSD
07. 10. 2007
0 views

DasuCMSTriggerUCSD

ams ppt
30. 08. 2007
0 views

ams ppt

Question Answering
16. 11. 2007
0 views

Question Answering

Facts x about Finland
22. 11. 2007
0 views

Facts x about Finland

OWAS PAppSecEU2006 CLASP Project
30. 08. 2007
0 views

OWAS PAppSecEU2006 CLASP Project

OWASP Flyer Sep06
30. 08. 2007
0 views

OWASP Flyer Sep06

fun with hyperplanes 2007
28. 12. 2007
0 views

fun with hyperplanes 2007

american history
28. 12. 2007
0 views

american history

Frank Garber Presentation
02. 01. 2008
0 views

Frank Garber Presentation

DPS07 65 01 Fritzius
03. 01. 2008
0 views

DPS07 65 01 Fritzius

Teaching Political Sociology
04. 01. 2008
0 views

Teaching Political Sociology

Gaming in Education
07. 01. 2008
0 views

Gaming in Education

Plume tracking hardware
07. 01. 2008
0 views

Plume tracking hardware

Altera
28. 11. 2007
0 views

Altera

dead reckon cdr
07. 01. 2008
0 views

dead reckon cdr

Infections 3
04. 12. 2007
0 views

Infections 3

CMC IR1001
27. 09. 2007
0 views

CMC IR1001

class2 3
16. 11. 2007
0 views

class2 3

mixload
06. 11. 2007
0 views

mixload

web query 0609
07. 11. 2007
0 views

web query 0609

FSA
27. 12. 2007
0 views

FSA

CompanyDossier
29. 09. 2007
0 views

CompanyDossier

Hunting For Black Holes
28. 11. 2007
0 views

Hunting For Black Holes

DAR
20. 02. 2008
0 views

DAR

8 Soci 1015 Chapter7 Family
24. 02. 2008
0 views

8 Soci 1015 Chapter7 Family

ABSSEI Oswald
29. 02. 2008
0 views

ABSSEI Oswald

NeMO Curr Part3 v2
26. 06. 2007
0 views

NeMO Curr Part3 v2

nelson sheinberg Presentation
26. 06. 2007
0 views

nelson sheinberg Presentation

n0002 SPIE1
26. 06. 2007
0 views

n0002 SPIE1

Metric System 1
26. 06. 2007
0 views

Metric System 1

media kit
26. 06. 2007
0 views

media kit

March 14 PMI Presentation
26. 06. 2007
0 views

March 14 PMI Presentation

fountain of age
26. 06. 2007
0 views

fountain of age

Lifting Equation
13. 12. 2007
0 views

Lifting Equation

Dietary Guidelines
04. 03. 2008
0 views

Dietary Guidelines

upshur pc1
10. 03. 2008
0 views

upshur pc1

crossref
30. 08. 2007
0 views

crossref

ddbppt
20. 11. 2007
0 views

ddbppt

DEPBasicsCourse
30. 12. 2007
0 views

DEPBasicsCourse

guerra
12. 11. 2007
0 views

guerra

James F Cooper
30. 08. 2007
0 views

James F Cooper

lubin talk
03. 01. 2008
0 views

lubin talk

NDD presentation compressed
30. 08. 2007
0 views

NDD presentation compressed

madcooper
07. 12. 2007
0 views

madcooper

graduacion1
01. 01. 2008
0 views

graduacion1

GBIF demo Japan081003
27. 11. 2007
0 views

GBIF demo Japan081003

20061019 1732 oberauer hql06
15. 11. 2007
0 views

20061019 1732 oberauer hql06

phpulse oct
05. 01. 2008
0 views

phpulse oct

media searching
26. 06. 2007
0 views

media searching

Smith Core values
17. 06. 2007
0 views

Smith Core values

Smith1
17. 06. 2007
0 views

Smith1

Significance of the Cross
17. 06. 2007
0 views

Significance of the Cross

Sharp
17. 06. 2007
0 views

Sharp

section 2 attitude to food
17. 06. 2007
0 views

section 2 attitude to food

Spirituality
17. 06. 2007
0 views

Spirituality

sonnet presentation
17. 06. 2007
0 views

sonnet presentation

Star addition tutorial
17. 06. 2007
0 views

Star addition tutorial

stand up comedy
17. 06. 2007
0 views

stand up comedy

SS 1SBrown
17. 06. 2007
0 views

SS 1SBrown

Emerson Transcendentalism
30. 08. 2007
0 views

Emerson Transcendentalism

ABinEurope
23. 11. 2007
0 views

ABinEurope

TextMining 06
03. 10. 2007
0 views

TextMining 06

oct04ach
05. 11. 2007
0 views

oct04ach

SCP2
17. 06. 2007
0 views

SCP2

transcendentalism
30. 08. 2007
0 views

transcendentalism

micro ch03 presentation
04. 10. 2007
0 views

micro ch03 presentation

SC morning
17. 06. 2007
0 views

SC morning

ISIC cobrandNEUenglish
18. 03. 2008
0 views

ISIC cobrandNEUenglish

02b LisbonWeb
30. 12. 2007
0 views

02b LisbonWeb

ProvenceArchitecture
05. 11. 2007
0 views

ProvenceArchitecture

san diego 04
01. 11. 2007
0 views

san diego 04

noemie 2
26. 06. 2007
0 views

noemie 2

Community Service PP 06 FOR WEB
05. 11. 2007
0 views

Community Service PP 06 FOR WEB

Sections3 7
17. 06. 2007
0 views

Sections3 7

ECE TRANS WP29 GRSP 41 inf09e
26. 11. 2007
0 views

ECE TRANS WP29 GRSP 41 inf09e

srwg graz
26. 11. 2007
0 views

srwg graz

Meydan
23. 11. 2007
0 views

Meydan

LWS05
02. 11. 2007
0 views

LWS05

mal 2005 bra
30. 08. 2007
0 views

mal 2005 bra

Standards Aligned Classroom
17. 06. 2007
0 views

Standards Aligned Classroom

steenkampNVDRS
06. 03. 2008
0 views

steenkampNVDRS