6.001, Spring 2004—Recitation 25 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsSpring 2004Recitation 25Stack and ProceduresContractsInput Register(s) whose value is read and used before it is written.Output Register(s) designated as output.Modifies Register(s) whose value after the code block could differ from their original value.1. What is the contract for the following code:expt(assign result (const 1))expt-loop(test (op <=) (reg arg1) (const 0))(branch (reg continue))(assign result (op *) (reg result) (reg arg0))(assign arg1 (op -) (reg arg1) (const 1))(goto (label expt-loop))Input:Output:Modifies:2. What is the contract for the following code:foo(assign y (reg x))(assign x (op cons) (reg x) (reg y))(test (op null?) (reg x))(branch (label yack))(assign val (const 2))(assign x (reg y))(goto (reg continue))yack(assign foo (const 7))(assign val (op car) (reg x))(goto (reg continue))Input:Output:Modifies:6.001, Spring 2004—Recitation 25 2Save and Restore(save reg)Place the value in register reg on top of the stack. This will also increment the stack pointer(sp). If the stack has no space left (by default, 1000 elements), a ”stack overflow” error issignalled. To place the value in the registe r result on the s tack:(save result)(restore reg)Take the top value off the stack and put it in register reg. This will also decrement the stackpointer (sp). If the stack has nothing on it, a ”stack underflow” error is signalled. To removethe top element of the stack and place it in the register result:(restore result)Procedure Call1. save things you care about2. assign values to the inputs, including continue to an appropriate label3. goto the procedure’s label4. return label5. restore things you cared about, in reverse orderProblems3. Implement aexpb, which computes aeb. You should call expt in your solution.4. Translate list-copy into register machine code:(define (list-copy lst)(if (null? lst)’()(cons (car lst)(list-copy (cdr lst)))))6.001, Spring 2004—Recitation 25 3Register machine code:list-copy(test (op null?) (reg arg0))(branch (label list-copy-done))(save arg0)(save continue)(assign arg0 (op cdr) (reg arg0))(assign continue (label list-copy-after))(goto (label list-copy))list-copy-afterlist-copy-done(assign result (const ()))(goto (reg continue))5. Translate list-ref into register code, verbatim:(define (list-ref lst k)(if (= k 0)(car lst)(list-ref (cdr lst) (- k 1))))Register machine code:list-ref(test (op =) (reg arg1) (const 0))(branch (label list-ref-done))list-ref-done(assign result (op car) (reg arg0))(goto (reg continue))6.001, Spring 2004—Recitation 25 46. Translate sum-of-exps into register code:(define (sum-of-exps lst)(if (null? lst)0(+ (expt 2.71828 (car lst))(sum-of-exps lst))))You should unroll the recursive call into a loop (don’t translate the code
View Full Document
Unlocking...