C SC 520 Principles of Programming LanguagesPrinciples of ProgrammingLanguagesLecture 09CoroutinesC SC 520 Principles of Programming Languages2Subroutines vs Coroutines• Subroutine call/returncall A A Bcall B returncall B B′′′′return returnseparateactivationentryentryentryC SC 520 Principles of Programming Languages3Subroutines vs Coroutines (cont.)• Coroutine resume/resumeresume A A Bresume Bresume Aresume Bresume Aresume ?/return• Non-nested lifetimes ⇒ abandon stack• Activation lifetimes potentially unlimited if no “return”sameactivationentryentry?C SC 520 Principles of Programming Languages4Simple Coroutines• No recursion• Only one activation of each coroutine at any timeresume B: *a = pc + 2jrst @b(control returns here)resume BABa →→→→ b →→→→resumption pointpc →→→→activesuspendedC SC 520 Principles of Programming Languages5Recursive Coroutines• Initial resume (call) of X:! create activation for X! resume execution at entry point• resume Y : suspend current activation! Resume which activation of Y?• resume ? ≡≡≡≡ return! anonymous resume! “terminated” activation• Call ≡≡≡≡ create & resumeC SC 520 Principles of Programming Languages6Recursive Coroutines—the problemproc x { proc y { proc z{⋮⋮⋮⋮ ⋮⋮⋮⋮ ⋮⋮⋮⋮⋮⋮⋮⋮ ⋮⋮⋮⋮ ⋮⋮⋮⋮call y call z resume y⋮⋮⋮⋮ ⋮⋮⋮⋮ ⋮⋮⋮⋮⋮⋮⋮⋮ ⋮⋮⋮⋮ ⋮⋮⋮⋮resume z resume x return⋮⋮⋮⋮⋮⋮⋮⋮return} } }caller of z?resumerof z?C SC 520 Principles of Programming Languages7Recursive Coroutines—solutions• SIMULA 67! return (“detach” in Simula 67) in z resumes “caller of z”• SL5! return resumes in latest activation that resumed z! With bindings at activation creationC SC 520 Principles of Programming Languages8SL5• Activations (called “environments”) are first class objects• p := procedure ( . . . ) . . . end! Creates a procedure (“template”) and assigns it to p• e := create p! Uses template to create activation (including variable storage, continuation point &c.)• e := e with ( . . . )! Transmits arguments (through “transmitters” for each argument)• resume e! Suspends current activation and resume in e! Suspender becomes latest resumer of e• return [to e]! Suspends current activation ! Returns control to most recent resumer [to e ]• No deallocation of ARs—they are garbage collectedC SC 520 Principles of Programming Languages9SL5 Primitives• Let c = currently executing AR• e := create pe = allocate(p)e.cont = entrypoint(p)e.creator = ce.resumer = cfor each X nonlocal in p do {t = cwhile t != nil doif X public in t thene.X.lval = t.X.lvalelse t = t.creatorif t == nil then error(X)}C SC 520 Principles of Programming Languages10SL5 Primitives (cont.)• e := e with (a₁, a₂, …, an)e.par[1]= transmitter₁(a₁). . .• resume ec.cont = resumepoint// e.creator untouchede.resumer = cc = egoto c.contresumepoint:C SC 520 Principles of Programming Languages11SL5 Primitives (cont.)• returnc.cont = resumepointc = c.resumergoto c.contresumepoint:• return to ec.cont = resumepoint// no alteration of e.resumerc = egoto c.contresumepoint:C SC 520 Principles of Programming Languages12Procedure Call/Return—special casef(a₁, a₂, …, an) ⇒ resume (create fwith (a₁, a₂, …, an))return ⇒ return• Binding is dynamice= allocate(f)e.cont = entrypoint(f) e.creator = c // “access link”e.resumer = c // dynamic link// bind nonlocals using creator chaine.par[1]= transmitter₁(a₁). . .e := create fwith(a₁,…,an)C SC 520 Principles of Programming Languages13Procedure Call/Return (cont.)e.cont = resumepointe.resumer = c // redundantc = egoto c.cont // entrypoint(f)resumepoint:. . .e.cont = resumepoint //never usedc = c.resumer // follow dlgoto c.cont // entrypoint(f)resumepoint:. . .resume ereturnC SC 520 Principles of Programming Languages14SIMULA 67• Can create class instances (= objects) subordinate to block (AR) in which created• All objects are “attached” to some AR during execution• When suspended, AR is “detached”• class p(...);declarations;begin ... end p;! Defines class template with formal parameters• e :- new p(...);! Creates an object (AR) of class p: [ref(p) e;]! Transmits arguments! Commences execution in AR of e! AR e is “attached” to the suspended (creating) ARC SC 520 Principles of Programming Languages15SIMULA 67 (cont.)• detach;! Suspend current activation! Resume in AR to which current is “attached”! Current AR marked “detached”! Approximately a “return”! end ⇒⇒⇒⇒ detach (blocks detach when exited)• call(e)! If e is detached, mark AR e as “attached” to caller (current AR)! Suspend caller (current AR)! Resume in AR e• resume(e)! If e is detached, suspend current AR and resume execution in AR e! e is “attached” to AR to which current AR is “attached”—resume passes its attachment to eC SC 520 Principles of Programming Languages16SIMULA 67 (cont.)cfe efee:-new Classdetachf:-new Classdetachcall(e)resume(f)detachcall(e)detachsame AR esame AR ftimeC SC 520 Principles of Programming Languages17SIMULA 67 Primitives• Let c = currently executing AR• e :- new p( . . . );e = allocate(p){ transmit parameters (CBN, CBV in Simula67)}e.cont = entrypoint(p)e.attached = c // attacher of e is c{ using c.sl and snl(p) and c’s snl, calculateAR in which p was defined (created)& put ptr into t}c.sl = tc.cont = resumepointc.attached = nilc = egoto c.contresumepoint:C SC 520 Principles of Programming Languages18SIMULA67 Primitives (cont.)• detach; c.cont = resumepointif c.attached == nil then error()else { t = c.attachedc.attached = nilc = t // back to attachergoto c.cont}resumepoint:C SC 520 Principles of Programming Languages19SIMULA67 Primitives (cont.)• call(e) —no parametersif e.attached != nil then error()e.attached = c // e attached to callerc.cont = resumepointc.attached = nilc = egoto c.contresumepoint:• resume(e)if e.attached != nil then error()e.attached = c.attached // e inherits attacherc.cont = resumepointc.attached = nilc = egoto c.contresumepoint:C SC 520 Principles of Programming Languages20SIMULA67 Exampleouter block: begin class A; … detach; … ;ref(A) U,V;U :- new A;inner block: begin class B; … detach; … ;ref(B) X;ref(A) W;V :- W :- new A;X :- new B;. . .pc →→→→ L: call(X);. . .end inner block;. .
View Full Document
Unlocking...