Subroutine ClosuresDeep BindingSubroutine Closuresldots Subroutine Closuresldots First-Class SubroutinesFirst-Class Subroutinesldots First-Class Subroutinesldots First-Class Subroutinesldots Call-With-Current-ContinuationCall-With-Current-Continuationldots Call-With-Current-Continuationldots Call-With-Current-Continuationldots Readings and References520—Spring 2005—35CSc 520Principles of ProgrammingLanguages35: Procedures — ClosuresChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—35Subroutine ClosuresA closure is a structure(procedure_addr,environment).To pass C() to A we construct a closure consisting ofC’s address and the static link that would have beenused ifC would have been called directly:program M;procedure A(procedure P)P();endprocedure C(); begin end;beginA(C);end[2]520—Spring 2005—35Deep BindingWhen a reference to a procedure is created (forexample by passing it as a reference to anotherprocedure), when are scope rules applied?1. When the reference is first created?2. When the routine is first called?Early binding of a referencing environment (what Pascaluses) is calleddeep binding.[3]520—Spring 2005—35Subroutine Closures...procedure A(I:integer; procedure P)procedure B(); begin write(I); end;beginif I > 1 then P() else A(2,B);endprocedure C(); begin end;beginA(1,C);endThere are two I:s when B is called.[4]520—Spring 2005—35Subroutine Closures...I=1P={C,*}static linkI=2P={B,*}static linkstatic linkB()A(2,B)A(1,C)mainA closure was created for B when A(2,B) was closed,henceB will print 1.[5]520—Spring 2005—35First-Class SubroutinesA language construct is first-class if it can be passed asa parameter, returned from a subroutine, or assigned toa variable.A language construct is second-class if it can bepassed as a parameter but not be returned from asubroutine, or assigned to a variable.A language construct is third-class if it can’t even bepassed as a parameter.Procedures are second-class in most imperativelanguages.[6]520—Spring 2005—35First-Class Subroutines...If a procedure can be returned as the result of afunction we could reference an environment that hasgone out of scope:procedure A() : procedure;var x : integer := 5;procedure B();write(x);endbeginreturn B;end;beginvar X : procedure := A();X();end[7]520—Spring 2005—35First-Class Subroutines...In functional languages functions are first-class.Functional languages specify that local variables haveunlimited extent — they exist for as long as someonereferences them.Algol-like languages specify that local variables havelimited extent — they exist until the scope in which theyare declared is exited.Objects with limited extent can be stored on a stack.Objects with unlimited extent must be stored on theheap.[8]520—Spring 2005—35First-Class Subroutines...C and C++ do not have nested scope — no problem.Modula-2 — global procedures are first-class (can bestored), local procedures are third-class.Modula-3 — global procedures are first-class, localprocedures are second-class (can be passed asparameters).Ada 83 — procedures are third class.Ada 95 — nested procedures can be returned if thescope in which it was declared is at least as wide asthat of the declared return type. I.e. a procedure canonly be propagated to an area of the program where thereferencing environment is active.[9]520—Spring 2005—35Call-With-Current-ContinuationThe Scheme built-in functioncall-with-current-continuation (also calledcall/cc) takes a function as argument:call-with-current-continuation (foo)(foo cont)foo takes a continuation as argument.(call/cc foo) calls foo, passing it the currentcontinuation.A continuation is a closure that holds the currentprogram counter and environment.[10]520—Spring 2005—35Call-With-Current-Continuation...foo can invoke the continuation and immediately returnto the situation as it was when the call was made.Any intermediate stack frames are popped off.Continuations are first-class: you can store them invariables, return them from functions, etc.call/cc can be used as a general building-block toconstruct a variety of control structures, such asiterators and coroutines.Continuations can, for example, be used to quickly exita tree-search procedure once the node we’re looking forhas been found.[11]520—Spring 2005—35Call-With-Current-Continuation...The function throws the continuation the value 99 whichmakes it pop out of the current evaluation and return 99:> (call/cc (lambda (c) (c 99)))99The expression (* [] 76) is never executed. Rather,the function pops out and returns 99:> (call/cc (lambda (c) (* (c 99) 76)))99[12]520—Spring 2005—35Call-With-Current-Continuation...Continuations can be stored in variables and invokedlater:> (let ((cont #f))(call/cc (lambda (k) (set! cont k)))(cont #f))99Or, like this:> (define cont #f)> (+ 5 (call/cc(lambda (e) (set! cont e) (* 4 3))))17> (cont 10)15[13]520—Spring 2005—35Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...