6.001 Tutorial 11Structure and Interpretation of Computer Programs May 14, 2007Register Machines and EC EvalRegister MachinesRegister machines execute a sequence of instructions. Instructions are single operations that operateon simple operands (such as a constant, or the value of a register). By default, the instructions areexecuted in order, but some instructions can cause the machine to jump to other locations in thesequence (either conditionally or unconditionally). Only a small, fixed set of variables (“registers”)and a stack are available for storing values.Calling Procedures• save any registers you need the value of after the call is made• assign argument registers and the continue register. Note that some or all of these might alreadybe assigned to the appropriate values.• goto procedure• Place the return label after the goto• restore the registers that were saved, in reverse orderThe Explicit Control Evaluatoreval−dispatch and everything it dispatches to (ev−if, ev−lambda, etc) have th e following contract:Inputs exp – The expression to evaluate Modifies Everythingenv – The environment to evaluate in Stack Unchangedcontinue – The label to return toOutputs result – The value of the expressionTranslating ProgramsWrite the equivalent Scheme code for the following. What does this code do?foo( t e s t ( op <) ( reg arg0 ) ( reg arg1 ) )( branch ( l a b e l foo− done ) )( a s s i g n a rg0 ( op −) ( r eg arg0 ) ( r eg arg1 ) )( got o ( l a b e l f o o ) )foo− done( a s s i g n r e s u l t ( op =) ( r eg arg 0 ) ( co n s t 0 ) )( got o ( re g con t i n ue ) )16.001 SICP Register Machines and EC EvalWrite sum−digits that computes the sum of the digits in x (in base 10). (Assume (op quotient) and(op remainder) are available)sum− digitsAdding orWe want to add a version of or to the explicit contr ol evaluator. Like Scheme’s or, this is short-circuiting, guarantees left-to-right evaluation, and returns th e value of the first non-false subex-pression. The following operations are provided• clauses applied to an or expr ession returns all of the subexpressions of the or• no−clauses? returns true if there are n ot further clauses• first−clause returns the first subexpression of a list of clauses• rest−clauses returns all of the subexpressions except the first one from a list of clausesWhat follows is the incomplete code for ev−or, which implements the evaluation of or expressions.This will be called with the or expression in exp, the current environment in env, and the labelexpecting the return value of the or in the continue register.ev− or1 ( a s s i g n unev ( op c l a u s e s ) ( r e g exp ) )2 ( s ave c o n t in ue )3 ( a s s i g n c o n ti n ue ( l a b e l aft e r − or− c l a u se )or− loop4 ( t e s t ( op no − clause s? ) ( re g unev ) )5 ( branch ( l a b e l end − c lau ses ) )678 ( s ave unev )9 ( s ave env )10 ( got o)afte r − or − cl au se111213 ( t e s t ( op f a l s e ? ) )14 ( branch)15 ( r e s t o r e c o n tin u e )16en d − clause s17 ( a s s i g n v a l ( c o n st f a l s e ) )181926.001 SICP Register Machines and EC EvalBrainteaser1The continue register can be thought of as an extra argument to a procedure that explicitly tells itwhere to go after it has computed its result. There is a similar style of programming in Schemeknown as Continuation Passing Style (or CPS). In CPS, we assume that procedures do not returnvalues. Instead, every procedure takes an additional argument known as its continuation. Thevalue of this argument must be a function of one argument. Instead of retur ning a value in thetypical way, the p rocedure calls its continuation with what would have been its return value.CPS can be a handy tool to have in your programming tool box because it provides more flexibilitythan typical Scheme applications – for example, you can have multiple continuations (such as asuccess continuation and a failure continuation), or you can “return” multiple values by requiringyour continuation to take more than one argument. When us ing it as a tool like this, you typicallyonly use it in a few key locations instead of subscribing to it whole-sale.While it’s incredibly tedious to write an entire p rogram in CPS, it’s also very powerful. A continua-tion explicitly captures the future of a computation as a first-class value. For example, by observingthat you don’t have to return to your continuation, you can write things like multi-threading sys-tems where a context switch is performed by s aving away the current continuation and invokingsome other, previously saved continuation.Just to get your feet wet with CPS, try writing fact in this style.( d e f i n e ( f a c t n k ) ; ; k i s t h e c o n t i n u a t i o n argumentHere’s a test case that simply displays four factorial.( f a c t 4 (lambda ( r e s u l t ) ( p r i n t f ”4 ! = ˜a˜n” r e s u l t ) ) )Brainteaser2As you’ll learn this week in class, there are limits to the power of computation. There are somethings that simply cannot be computed. The classic example of this is the halting problem: givena program, it is impossible to decide whether or not that program will ever terminate.Most people find th is result unintuitive. Isn’t it obvious whether or not a program w ill terminate?We’ve learned good programming techniques that allow us to structure our code so its behavior isclear. Here’s a function to try your halting intuition on known as the “McCarthy 91 function”:( d e f i n e ( mc91 n )(cond ((<= n 100) ( mc91 ( mc91 (+ n 1 1 ) ) ) )( e l s e (− n 1 0 ) ) ) )For what values of n does this function terminate? For what values does it not terminate?36.001 SICP Register Machines and EC EvalReferenceArguments(const C) A constant value. It acts somewhat like quote. To get the number one, you would use (const1). To get the list (1 2) you would use (const (1 2)).(reg R) Retrieve the value of a register R. To get the value of the register arg0, you would use (reg arg0).(label L) Retrieve the offset of the given label L. To get the value of the label loop-top, you would use(label loop-top). The actual value of this is a number, the index of the instruction that appearsright after the …
View Full Document
Unlocking...