New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

T Distrib Comp in Second Life

by: Trent Dare

T Distrib Comp in Second Life CS 491

Marketplace > University of New Mexico > ComputerScienence > CS 491 > T Distrib Comp in Second Life
Trent Dare
GPA 3.76

Lance Williams

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Lance Williams
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 22 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 491 at University of New Mexico taught by Lance Williams in Fall. Since its upload, it has received 7 views. For similar materials see /class/212199/cs-491-university-of-new-mexico in ComputerScienence at University of New Mexico.


Reviews for T Distrib Comp in Second Life


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/15
Applications of Continuations Daniel P Friedman Indiana University Organization The lecture is in three parts In the rst part we de ne primarily by example the key terms These are conventional procedures escape procedures and continuations The primitive notions of lambdaquot and callcc are presented In the second part we develop examples of simple applications speci cally a simple LISP like BREAK and a CYCLE pro cedure which loops inde nitely but makes available the ability to break out of the loop Also in this section we point out that callCC is not strictly necessary if all procedures are written in continuation passing style We complete this section by demonstrating that even the unpopular GO TO style programming of LISP7s PRDG looks reasonable in the presence of the proper uses of callCC In the last section we develop a DISPATCHER for synchronous processes At the end of these notes are two special features The rst is a set of ten exercises that we hope you will enjoy Some of them are puzzles designed to challenge and others are more realistic like adding asynchronous processes and exception handling to the DISPATCHER Finally we have included two appendices In Appendix A we have presented a meta circular interpreter for a fully curried version of a subset of Scheme which includes call CC and lambdaquot In Appendix B we have included the remaining code necessary to test DISPATCHER Lecture Notes 7 Applications of Continuations Page 2 Outline I Key Terms and De nitions 1 Properties of Scheme 2 Description of escape procedures 3 Notation for characterizing escape procedures 4 Invoking escape procedures is replacing the control stack 5 lambdaquot the creator of general escape procedures 6 callCC a creator of escape procedures 7 Describing escape procedures created by callCC 8 A very simple example of callCC 9 Continuations describe the rest of the computation 10 Continuations are rstclass objects II MetaProgramming 1 Default Law of callCC 2 With lambdaquot the Default Law of callCC is not true 3 A simple LISPlike BREAK 4 How to construct lambdaquot 5 Programming in continuationpassing style 6 MetaProgramming with callCC CYCLE 7 LISP s PRUG with G0 and RETURN GO TO programming revisited III Synchronous Processes 1 Continuations as synchronous processes 2 Extending the language of processes 3 Swapping and running the current process 4 Creating processes 5 HALT and DISPATCHER 6 Exercises IV References 1 Programming and Reasoning with Continuations 2 Continuations for Semantic Descriptions V Appendices A A metacircular interpreter which includes lambdaquot and callCC B Supporting code for DISPATCHER Lecture Notes 7 Applications of Continuations Page 3 I Key Terms and De nitions l l Properties of Scheme The programming language Scheme is a call by value lexically scoped dialect of LISP with first class procedures A condition imposed on any implementation is that it be properly tail recursive In simple terms this means that there is no control stack growth when unnecessary and that in particular the cost of simple loops written using recursion is minimal A subset of the language is functional but the entire language supports imperative concepts such as inputoutput assignment to lexical variables and first class continuations 1 2 Description of escape procedures Suppose we consider the following simple expression 24 f 0 3 Possible outcomes 1 f O is 4 so the result is 18 2 f is undefined at 0 leading to an error message and causing the computation to abort 3 f is undefined at 0 leading to an infinite loop eg define f lambda n if zero 11 f n n 4 f O is 4 but f is an escape procedure so the result is 4 1 3 Notation for characterizing escape procedures We introduce a notation for characterizing escape procedures If f is a procedure its corresponding escape procedure is fquot iquot does exactly what f does but fquot escapes as the answer and it is subsequently printed Sometimes this is referred to as escaping to the top level 07 read eval prz nt loop The simplest escape procedure corresponds to the identity I If fquot Iquot then the result is 0 and no division occurs A more powerful escape procedure is quot Consider 3 quot 4 5 gt 9 But note that this is similar to 3 Iquot 4 5 gt 9 l 4 Invoking escape procedures is replacing the control stack In the expression above the contents of the control stack at the time of invoking quot 4 5 is lt3 gt Invoking the escape procedure has the effect of forgetting the current contents of the control stack and processing only the quot and its arguments Although it appears that Iquot 4 5 is the same as quot 4 5 they are not operationally the same There is more growth of the control stack with Iquot 4 5 This understanding of the growth Lecture Notes 7 Applications of Continuations Page 4 of the control stack will play a role later when we look at sophisticated uses of escape procedures 1 5 lambdaquot the creator of general escape procedures Given any lambda expression we can form its corresponding escape counterpart So that lambda X becomes lambdaquot X We assume the existence of such a capability Later we clarify how such objects are built l 6 callCC a creator of escape procedures Scheme has a feature for creating escape procedures internally and making them available to the user In Scheme these procedures also interact with uids However for purposes of this lecture we will not discuss the vagaries of uids See 9 for a discussion of continuations in the presence of uids These escape procedures correspond to the control stack in the run time architecture The control stack corresponds to the continuation in a continuation semantics That is why these particular escape procedures are often referred to as continuations or continuation objects In Scheme one writes call with Current continuation e This has the effect of invoking e kquot where kquot is the escape procedure corresponding to the expression instance Call with current Continuation e From here on call with current contLnuation77 is shortened to callcc l 7 Describing escape procedures created by callCC For example suppose we have the expression 3 callCC lambda kquot then kquot can be formed by replacing the callCC expression by a fresh variable say v and abstracting with v over the result kquot lambdaquot V 3 V 1 8 A very simple example of callCC Let7s practice callCC lambda kquot k 5 4 8 Lecture Notes 7 Applications of Continuations Page 5 gt First form kquot lambdaquot v v 8 gt Evaluate kquot 5 4 knowing the value of kquot gt Evaluate kquot 5 gt 13 is the result the waiting division is forgotten since kquot is an escape procedure 1 9 Continuations describe the rest of the computation Another simple example callcc lambda kquot kquot 5 4 8 3 gt First form kquot lambdaquot v v 8 3 gt Evaluate kquot 5 4 gt Evaluate kquot 5 gt Evaluate lambdaquot v v 8 3 5 gt Result is 39 The use of 77 is arbitrary here What we mean is whatever is left to do In this case the only thing left to do is multiplication Of course it could have been any f and in that case we would have all the work of f left to do This next example shows that it is not always completely obvious what is meant by the rest of the computation let u 3 2 callCC lambda 3 jquot u 4 8 3 Here the work of u becoming 577 occurs prior to determining the value for jquot The continuation jquot is the same as kquot Since 3 2 is 5 both expressions yield the same result l lO Continuations are rstclass objects With callCC we might choose to save away the escape procedure but not invoke it until later in the computation callCC lambda kquot begin set 8quot kquot display quotinside bodyquot 5 8 Lecture Notes 7 Applications of Continuations Page 6 gt First form kquot lambdaquot v v 8 gt Evaluate the body begin set 8quot kquot display quotInside bodyquot 5 gt The lexical variable 8quot is set to lambdaquot v v 8 Inside body77 is printed and 5 is returned as the result of the body gt 13 is the answer of the entire expression Later we may invoke 8quot 35 O 100 gt 43 II MetaProgramming ll l Default Law of callCC The reason that 5 is sent to the waiting in the previous example is that we claim callcc lambda kquot e callcc lambda kquot kquot e That is the continuation waiting for the result is the same as the escape procedure created by callCC From this equation we know that e defaults to kquot e Thus in our example callCC lambda kquot kquot begin set 8quot kquot display quotInside bodyquot 5 8 The result is kquot 5 or 13 Lecture Notes 7 Applications of Continuations Page 7 ll 2 With lambdaquot the Default Law of callCC is not true Escaping by applying callCC to an escape procedure z39e a procedure lambdaquot imposes on the user even more control responsibility The user of the language is then required to make every decision about exiting from the body of the applied escape proce dure Look at the following two examples They appear equivalent using the Default Law from above But that equation used lambda not lambdaquot With lambdaquot being applied to the current continuation we get different behaviors 3 callcc lambdaquot kquot kquot 8 Here we would get 11 3 callcc lambdaquot kquot 8 But here we would just get 8 We conclude this portion of the lecture with the reminder that callcc may be passed either a conventional or an escape procedure and the continuation is always an escape procedure like kquot ll 3 A simple LISPlike BREAK By saving continuations we can write a BREAK procedure that allows for the computation to RESUME at the discretion of the user Upon invocation of BREAK a message will be returned to top level The system listening loop will then be in control until the user executes RESUME at which time the argument to RESUME will be the value of the original BREAK invocation define BREAK lambda message callcc lambda kquot set RESUME kquot lambdaquot x x message BREAK is a fascinating example where the use of first class continuations leads to an elegant solution Brian Smith chose a more sophisticated version of BREAK as an example of the power of re ection 25 ll 4 How to construct lambdaquot Next we consider how to form lambdaquot i e and note why we cannot think about lambdaquot as part of Scheme but must always construct it at run time We define a procedure INVDKEND CDNT which takes as an argument a procedure f of no arguments and invokes f as if it were an escape procedure Given INVDKEND CDNT we can syntactically express lambdaquot lambdaquot id e laTmbda id INVUKENU CDNT lambda e Lecture Notes 7 Applications of Continuations Page 8 Below is the procedure make INVDKENU CDNT followed by its invocation define make INVDKEND CDNT lambda CallCC lambda k set INVDKEND CDNT lambda th k th lambda INVUKENU CDNT make INVUKENU CUNT The make INVDKENU CDNT must be invoked from the top level When we form the kquot for building the definition of INVUKEND CDNT we see that it is lambdaquot v v with no continuation Hence we are invoking the procedure of zero arguments in the empty or top level continuation when we pass it to INVDKEND CDNT The clue that this is happening is the double left parentheses around the callCC By binding INVDKEND CONT to a procedure whose sole purpose is to invoke its argument we can guarantee that there is no continuation waiting for its result Think what would happen if instead we invoked 5 make INVDKEND CDNT at top level ll 5 Programming in continuation passing style The following program yields the sum of the nodes in a binary search tree If a 0 is found in the tree the result is 0 define sum bst lambda t callcc lambda exit letrec sum bst lambda t cond null t 0 zero info t exitquot 0 else info t sum bst left t sum bst right tll sum bst t Below is the equivalent definition in continuation passing style 26 Lecture Notes 7 Applications of Continuations Page 9 define sum bst lambda t letrec sum bst lambda t k cond null t k OX zero info t 0 else sum bst left t lambda resultl sum bst right t lambda result2 k info t resultl result2 sum bst t lambda X X Such programs can be read and written with practice Consider the else line It says Imagine that you have the result of the left tree and call it resultl then imagine you have the result of the right tree and call it result2 then take the sum of the information at the root of the tree with the sum of resultl and result2 and pass this value to the waiting continuation k The zero test line says to abandon the waiting continuation and return the value 0 to the continuation of the original invoker of bst Some find this a bit awkward but the real dif culty is that writing in this style often imposes its will on every program For instance if one uses a mapping procedure then the procedure that is being mapped might also be required to be in this style To quote James S Miller 19 Unfortunately the procedures resulting from the conversion process are often dif cult to understand The argument that continuations need not be added to the Scheme language is factually correct It has as much validity as the state ment that the names of the formal parameters can be chosen arbitrarily And both of these arguments have the same basic aw the form in which a statement is written can have a major impact on how easily a person can understand the statement While understanding that the language does not inherently need any extensions to support programming us ing continuations the Scheme community nevertheless chose to add one operation to the language to ease the chore77 Lecture Notes 7 Applications of Continuations Page 10 ll 6 MetaProgramming with callCC CYCLE We can meta program CYCLE works for in nite loops With an EXIT CYCLE WITH define CYCLE lambda f callcc lambda kquot letrec loop lambda f kquot loopl loop The protocol for CYCLE follows CYCLE lambda EXITCYCLEWITH e The expectation is that somewhere Within the e there is at least one invocation of EXIT CYCLE WITH This way the infinite loop will terminate With the argument to the rmEXIT CYCLE WITH thatitencounu s ll 7 LISP s PRDG with G0 and RETURN GO TO programming revisited Let us consider LISP7s PRUG PRDG id labell e1 labeln1 e714 label71 en let id l CallCC lambda GU let RETURN lambda v GD lambda vl letrec labe11 lambda e1 labelg llabeln1 lambda en1 labeln labeln lambda en RETURN labe11 Lecture Notes 7 Applications of Continuations Page 11 With this de nition we avoid any risk of losing tail recursion Even if the program contains an instance of bizarre code like begin GD X print 3 it will still be run as if the instance were just GD x The reason that we need invoke only labeli instead of GO labeli is that these particular invocations are always in tail recursive position These definitions are strictly more general than necessary For example it is possible to have instances of f labeli f RETURN and f GD within the e Furthermore labeli RETURN and GD may be stored away for later use This is how some of the mecha nisms for non blind backtracking such as a bien tot and au revoir of Conniver27 were implemented III Synchronous Processes Ill l Continuations as synchronous processes We will next focus on the process oriented aspects of continuations A continuation rep resents a locus of control and we can use this to implement processes 30 A process scheduler can be designed based on a ready queue of continuations If we think about a sequence of expressions begin 81 82 then whenever Si binds a continuation its continuation looks like lambdaquot waste Sill Si2 These are called command continuations because we are not interested in the value of the continuation invocation We show this by choosing the argument name waste which should not occur free within Si s For example define foo lambda display 2 callCC lambda akquot display 3 callcc lambda bkquot display 5 callcc lambda ckquot display 7 Lecture Notes 7 Applications of Continuations Page 12 If we invoke foo at the top level with no context then akquot lambdaquot waste display callcc lambda bkquot display 5 callCC lambda ckquot display 7 A bkquot lambdaquot waste display 5 callCC lambda ckquot display 7 Ckquot lambdaquot waste display 7 Ill 2 Extending the language of processes We extend the language of expressions to include PAUSE HANDLER If in our example we replace callcc lambda ikquot by a procedure invocation of PAUSE HANDLER we will get something that looks like this define foo lambda display 2 PAUSE HANDLER display 3 PAUSE HANDLER display 5 PAUSE HANDLER display 7 Then the procedure for PAUSE HANDLER would be responsible for the callCC define PAUSEHANDLER lambda callcc lambda kquot What is left is to decide what to do with these continuations that we have bound with call CC In this simple example we will 1 Insert the continuation into the process queue 2 Delete kquot 26 a process object from the front of the queue Lecture Notes 7 Applications of Continuations Page 13 3 Invoke 23 RUN the continuation kquot Hence we de ne PAUSE HANDLER as def ine PAUSEHAND LER lambda callcc lambda kquot swap run the processq kquot Ill 3 Swapping and running the current process swap run does the three steps alluded to above define swap run lambda q kquot q en q kquot RUN q de q define RUN lambda kquot kquot waste RUN invokes the continuation that is removed from the process queue Ill 4 Creating processes The only issue remaining is the development of a protocol for processes code which uses the PAUSE HANDLER feature What should we do when there is nothing left to process A simple solution is to require an insertion of a HALT command We clarify this protocol by introducing CREATE PROCESS Processes like continuations that are carved out of processes must be procedures of one argument define CREATEPROCESS lambda th lambda v th HALT Ill 5 HALT and DISPATCHER We next define the DISPATCHER procedure as a simple synchronous process scheduler Each time DISPATCHER is invoked a new queue is created The queue created by create q exitquot is built with the exit continuation The queue invokes the exitquot continuation whenever there is an attempt to delete a process from an empty queue This will exit DISPATCHER If the queue is not empty we sucessfully remove an element from the queue Lecture Notes 7 Applications of Continuations Page 14 and RUN it We include PAUSE HANDLER in the de nition of DISPATCHER so that it Will close over the free variable the process q define DISPATCHER lambda initialize q callcc lambda exit let the process q create q exitquot set HALT lambda RUN the process q deq set PAUSEHANDLER lambda callcc lambda kquot swap run the processq kquot initialize q the process q HALT The invoker of DISPATCHER passes a procedure Which takes a queue as an argument This procedure is invoked just prior to RUNning surprisingly With HALT the rst process We use it to initialize the queue For a demonstration of how we used the initialize q procedure and for all the code necessary to run DISPATCHER see Appendix B H N to 4 QTY 0A Lecture Notes 7 Applications of Continuations Page 15 Ill 6 Exercises The BREAK program is not very general Suppose that another invocation of BREAK occurs Then the RESUME would not be correct Redesign the BREAK procedure so that the RESUME interface is unchanged but that many instances of BREAK can co exist A slightly more general variant of CYCLE is to allow the users program the ability to loop back to the top Here the protocol would be as follows CYCLE lambda EXIT CYCLEWITH AGAIN e An example lambda n m CYCLE lambda EXITCYCLEWITH AGAIN if I1 m EXITCYCLEWITH I1 if n m 5 begin display quotexplicit loopingquot newline set 11 subl n AGAIN set 11 subl n display quotimplicit loopingquot newline 24 3 If the variable AGAIN is free in e then any invocation of AGAIN within e will take it to the top of the loop Be careful to guarantee that these invocations of AGAIN are tail recursive Reynolds 22 has a different approach to PRUG He builds as many escape procedures as there are labels but each procedure is the concatenation of all the statements below the label This has the disadvantage of generating larger programs and the advantage of avoiding the generated uses of labeli lmplement PRUG using his approach Find out how exception handlers are bound in your Scheme system and wire PAUSE HANDLER to it Run test programs which have no instances of PAUSE HANDLER physically within the program but which invoke PAUSE HANDLER as a result of an exception Find out how pre emption works in your Scheme system and wire PAUSE HANDLER to it Run test programs which have no instances of PAUSE HANDLER physically within the program but which invoke PAUSE HANDLER as a result of something external to the program This yields asynchronous processes Some Scheme systems use engines for modeling timed preemption l2 were just a step away from a coroutine system In a coroutine system the decision as to which process is run when a pause occurs becomes the responsibility of the writer of 1 00 D O Lecture Notes 7 Applications of Continuations Page 16 the code We can use the continuations to represent coroutines just as we used them to represent processes We introduce a new command RESUME C which relinquishes control and runs the coroutine C Add RESUME as a command to the DISPATCHER by including another operation on the queue For a completely different approach to coroutines see 13 or 29 What changes should be made to insure that the language supported by DISPATCHER would allow invocations of DISPATCHER Hint The solution to this exercise might surprise you The programming language ICON 9 has an interesting control facility Each expression in ICON has 0 I or many values Create an interface which extends the notion of expressions to those having multiple values as is done in ICON Are continuations too general Consider the following puzzle Suppose that we only have a primitive STATE which we de ne as follows def ine STATE lambda callcc lambda kquot kquot kquot Is it possible to define callCC in terms of STATE Consider a program that includes in addition to the standard expressions three types of special purpose expressions MILESTONE DEVIL and ANGEL The computation described by the program has the goal of finishing despite the existence of devils A devil sends control back to the last milestone The value given to the devil is passed to the continuation commencing at the milestone as if that value were the result returned by the milestone expression Presumably this allows the computation to take a different path possibly avoiding the devil that is lurking somewhere ahead on the previously used path If another devil or maybe even the same devil is subsequently encountered then control passes back to the penultimate milestone not to the one just used In other words each milestone can be returned to exactly once a succession of devils pushes the computation back to earlier and earlier states An angel sends the computation forward to where it was when it most recently encountered a devil The value passed as a parameter to the angel is given to the devils continuation as if it were the value of the devil A succession of angels pushes the computation forward to more advanced states A milestone is a procedure of one argument that acts as the identity as well as recording the current context for later use by devils If a devil or angel is encountered with no milestone or devil remaining the devil or angel has no effect To recharge any milestone the milestone must be re evaluated Implement the procedures MILESTONE DEVIL and ANGEL There is no non determinism this is however an example of non blind backtracking For an example of blind backtracking with continuations see 11 Lecture Notes 7 Applications of Continuations Page 17 1 N 9 5 U Q 1 90 3 BURGE W Recursive Programming Techniques Addison Wesley Reading Mass 1975 CLINGER WD DP FRIEDMAN AND M WAND A scheme for a higher level semantic algebra ln Algebraic Methods in Semantics edited by J Reynolds and M Nivat Cambridge University Press London 1985 2377250 DYBVIG R KENT Three Implementation Models for Scheme PhD dissertation University of North Carolina at Chapel Hill 1987 DYBVIG R KENT The Scheme Programming Language Prentice Hall Englewood Cliffs NeW Jersey 1987 FELLEISEN M The Calculi of Lambda u CS Conuersion A Syntactic Theory of Con trol and State in Imperative Higher Order Programming Languages PhD dissertation Indiana University 1987 FELLEISEN M The theory and practice of first class prompts In Proc 15th ACM Symposium on Principles of Programming Languages 1988 to appear FELLEISEN M DP FRIEDMAN E KOHLBECKER AND B DUBA theory of sequential control Theor Comput Sci523 1987 2057237 A syntactic FRIEDMAN DP CT HAYNES AND E KOHLBECKER Programming with contin uations 1n Program Transformations and Programming Environments edited by P Pepper Springer Verlag Heidelberg 1985 2637274 GRISWOLD RALPH E The Evaluation of Expressions in lCON ACM Trans Pro gram Lang Syst 44 1982 5637584 HAYNES CT Logic continuations J Logic Program 4 1987 1577176 HAYNES CT AND DP FRIEDMAN Embedding continuations in procedural objects ACM Trans Program Lang Syst 94 1987 5827598 HAYNES CT AND DP FRIEDMAN Abstracting timed preemption With engines Journal of Computer Languages Pergamon Press 122 1987 109 121 HAYNES CT DP FRIEDMAN AND M WAND Obtaining coroutines from con tinuations Journal of Computer Languages Pergamon Press 11 1986 1437153 JOHNSON GF AND D DUGGAN Stores and partial continuations as first class ob jects in a language and its environment In Proc 15th ACM Symposium on Principles Lecture Notes 7 Applications of Continuations Page 18 SMITH BRIAN CANTWELL of Programming Languages 1988 to appear JOHNSON GF GLiA language and environment for interactively experimenting With denotational de nitions In Proc SICPLAN 87 Symposium on Interpreters and Interpretive Techniques SICPLAN Notices 227 1987 1657176 LANDIN PJ A correspondence between ALGOL 60 and Church7s lambda notation Commun AOM 82 1965 8101 1587165 LANDIN PJ The next 700 programming languages Commun ACM 93 1966 1577166 LANDIN PJ An abstract machine for designers of computing languages In Proc IFIP Congress 1965 4387439 MILLER JAMES S Multischeme A Parallel Processing System Based on MIT Scheme PhD dissertation Massachusetts Institute of Technology 1987 REES J AND W CLINGER Eds The revised3 report on the algorithmic language Scheme SIGPLAN Notices 2112 1986 37779 REYNOLDS J C De nitional interpreters for higher order programming languages In Proc ACM Annual Conference 1972 7177740 REYNOLDS JC GEDANKENiA simple typeless language based on the principle of completeness and the reference concept Commun ACM 135 1970 3087319 ROJAS GUILLERMO J A Computational Model for Observation in Quantum Mechan ics Master7s Thesis Massachusetts Institute of Technology 1986 SMITH BRIAN CANTWELL Reflection and Semantics in a Procedural Language PhD dissertation Massachusetts Institute of Technology 1982 Re ection and semantics in Lisp Proc 11th ACM Symposium on Principles of Programming Languages 1984 23735 STEELE GUY L Rabbit A Compiler for Scheme Master7s Thesis Massachusetts Institute of Technology 1978 SUSSMAN GJ AND DV MCDERMOTT From PLANNER to CONNIVERiA genetic approach In Proceedings of the Fall Joint Computer Conference 41 AFlPS Press Reston Va 1972 117171179 Lecture Notes 7 Applications of Continuations Page 19 28 SUSSMAN GJ AND G STEELE Scheme An interpreter for extended lambda cal culus Memo 349 MIT Al Lab 1975 29 TALCOTT C The Essence of RumiA Theory of the Intensional and Ezrtensional Aspects of Lisp type Computation PhD dissertation Stanford University 1985 30 WAND M Continuation based multiprocessing In Proc 1980 ACM Conference on Lisp and Functional Programming 1980 19728 31 WAND M AND DP FRIEDMAN The mystery of the tower revealed a non reflective description of the re ective tower In Proc 1986 ACM Conference on Lisp and Func tional Programming 1986 2987307 Appendices AppendixA A metacircular interpreter which includes lambdaquot and callCC In order to help clarify the meanings of the forms used in this lecture we include an interpreter which will run in Scheme This interpreter is derived from one in Issues of side effects are germane but are ignored as the goals of this lecture are primarily about the applications of continuations See Johnson and Duggan 14 for a further study of stores As usual we assume the expression is curried A good exercise is to rewrite this program in continuation passing style record case e is described in detail in Dybvig Lecture Notes 7 Applications of Continuations Page 20 It matches against the car e and lexically binds While pairing against the Cdr e define M let extend lambda r var val lambda i if eq 1 var val r i lambda e r CallCC lambda Iquot letrec U lambda e r cond number e e symbol e r ex else record case e quote lit lit lambda is b lambda v U b extend r car is v lambdaquot is e lambda v Iquot lambda U e extend r car is v if test t pt f pt if U test r U t pr r U f pt rl callCC f callcc U f rX else U car e r U cadr e r lambda U e r The special form execute below builds an environment With just two identi ers and cons Feel free to add additional symbols to the environment but remember that every thing is curried extend syntax execute execute e M e let lambda x lambda y x y cons lambda x lambda y cons x y lambda i cond eq i eq 1 Cons cons else error i quotundefined id AppendixB Supporting code for DISPATCHER Lecture Notes 7 Applications of Continuations Page 21 Queues created by create q respond to en q and de q messages If an attempt is made to delete something from an empty queue then the continuation Which was passed as an argument to create q is invoked The test for an empty queue is not needed if an enqueue has just preceded it A good exercise is to add a new message that combines the actions of en q and de q Then swap run becomes RUN q en q de q kquot define create q lambda where to exit when emptyquot let head tail t lambda msg case car msg en q if null head begin set head cons cadr msg head set tail head begin set Cdr tail cons cadr msg set tail Cdr tail de q if null head where to exit when emptyquot done beginO car head if eq head tail set head set head Cdr head Lecture Notes 7 Applications of Continuations Page 22 The procedures process maker build q and test create a test program define process maker lambda n CREATEPROCESS lambda display n PAUSEHANDLER newline display quotabout to haltquot newline PAUSEHANDLER display n define build q lambda maker n lambda q letrec loop lambda n cond zero n queue built else q en q maker n loop subl n loop n define test lambda DISPATCHER build q process maker 8


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.