CSE Machine

What does it do

• keep track of deferred operations
• keep track of what environment to return to (after a function is done)
• keep track of the result of evaluating expressions

Control

• In the beginning, it will contain the whole program
  • As the program runs, it stores what we still need to execute

Stash

• Any primitive values get put onto the stash
• The last value on the stash is what the program will output after it is done
  • If there are no values on the stash at the end, will output undefined

How to evaluate a program

When encountering ? as the next item on control, first, remove the item, then:

Expression

e.g. 1 * 2 + 3 * 4 is the next item on control

1. Decompose expression
   1. Remove 1 * 2 + 3 * 4 from control
   2. Push the operator + onto the control
   3. Push the arguments onto the control, from right to left (so that the leftmost operation will be evaluated first), so push 3 * 4, then 1 * 2

Value

e.g. true, 1, [1, 2, 3]

1. Push value onto stash note: if the value is a compound value (function object, pair, array), then it will be created in the environment area, and pointed to by the item on the stash

Operator

e.g. >=, +, !

1. Take the top n required values from the stash (e.g. 1 and 2) and apply the operator (for +, >= etc. it is 2 values, but for ! it is 1 value)
2. Remove the top 2 values from the stash
3. Push the result onto the stash (3)

Sequence

e.g.

1 + 2;
3 * 4;
5 / 6;

1. Decompose sequence (1+2;, 3*4;,5/6;)
2. Push parts onto control from bottom up, with pop statements inbetween so push in this order: 5/6;, pop, 3*4;, pop, 1+2;
   1. Push a pop right after every value-producing statement, apart from the first statement in the sequence. i.e. pops will be added so that the sequence results in the value of the last value-producing statement being pushed onto the stash

Block

e.g.

{
	const x = 1;
	x + 1;
}

1. Find all declarations in the block (const x = 1;)
2. Push an env instruction onto the control, which points to the current environment
   1. Only if there are more statements that access names on the rest of the control (so the program block will not result in an env)
3. Create an environment frame that extends the current environment
4. Add the declaration to the environment, so the frame will contain x:=
5. Push the contents of the block onto the control, so const x = 1; x + 1; (it is either a sequence or an expression)

env instruction

1. Change the current environment to the environment that the env instruction is pointing to

While loop

e.g. while (i > 1) { i = i + 1; }

1. Push the while instruction onto the control (it contains the entire definition of the while loop)
2. Push the predicate (i > 1) onto the control
3. Push undefined onto the control (this is because while loops are value producing, so if the contents of the loop are not run, the stash will contain undefined)

while instruction

1. Check whether the value on the stash is true
2. If true
   1. Push the predicate onto the control
   2. Push the body of the loop onto the control (as a block {...})
   3. Push pop onto the control (this is to remove the previous result of executing the while loop)
3. If false
   1. Do nothing (remember to remove the while instruction from the control)

Conditional expression or statement

e.g. conditional expression x > 1 ? 1 + 2 : 3 + 4; or conditional statement if(x > 1) { 1 + 2; } else { 3 + 4; }

1. Push branch onto the control (the branch instruction will “store” both sides of the conditional expression (1+2 and 3+4))
2. Push the predicate expression onto the control (true) note:

• Both of these are value-producing, i.e. the result of evaluating their contents will be put onto the stash
• Both of these are considered one entry in a sequence, i.e. the entire if ... else ... will be pushed onto the control when a sequence is evaluated

For loop

For 1101S, don’t need to know how for loops work

branch instruction

e.g. branch (that contains 1+2 : 3+4)

1. Push the expression that corresponds with the top value on the stash onto the control as a block, so if the value on the stash is true, then push {1+2;} onto the control
2. Remove the top value (or pop) from the stash

Assignment statement

e.g. const abc = 1 + 2;

1. Push onto the conrol: pop then asgn abc
2. Push onto the control the assignment expression (1 + 2)

Name

e.g. abc

1. Search for the name in the current environment
2. Push the value found onto the stash
   1. If this value is a function, push the word closure, which points to the function found
   2. If this value is a pair or array, push the word pair/array, which points to the pair or array

asgn instruction

e.g. asgn abc

1. Search for the name in the current environment abc in this case
2. Set the value of abc to the top item on the stash

pop instruction

1. Remove the top value (or pop) from the stash

Logical composition

e.g. x && y

1. Push the corresponding conditional statement onto the control
   1. x && y → x ? y : false
   2. x || y → x ? true : y

Lambda expression

e.g. x => {1+1; return x * x;}

1. Draw the function in the current environment (the two circles, with right circle pointing to the current environment)
2. Push the function onto the stash (represented by the word closure, which points to the function created in 1.)

Function statement

e.g. function sum(x, y) {return x + y;}

1. Push a constant assignment onto the control (const sum = (x,y) => ...)

Function call/application

e.g. sum(1,2 + 3);

1. Push onto the control: call n, where n is number of arguments, so call 2 in this case
2. Push onto the control: the function argument expressions, from right to left, so 2 + 3 then 1 (this corresponds to left to right evaluation)
3. Push the name of the function onto the control

call instruction

e.g. call 2

1. Take n items from the stash, in this case 2. The topmost item will be the rightmost argument to the function
2. After taking n items from the stash, there should be a closure on the stash.
3. If there are more statements that access names on the rest of the control, push an env instruction that points to the current environment
   1. To tell whether we need an env instruction, just check if we need to return to the current environment after the function is done
4. If the function is a compound function (not simple) (i.e. there is a return statement and there are statements apart from the return statement), push a mark instruction onto the control
5. Evaluate this closure with the arguments from 1.
   1. If there are arguments, extend the function’s environment with a frame that contains the arguments
   2. If the function is simple, push the contents of the function (the expression that the function returns) onto the control
   3. If it is compound (not simple), push the whole function body block onto the control

return statement

e.g. return 1 + 2;

1. Remove the top value (or pop) from the control
   1. If the popped value is not a mark instruction, push a return instruction onto the control
   2. If it is a mark instruction, do not push anything onto the control, then push the expression onto the control (1+2) note: this is equivalent to popping from control until a mark is removed