Ch 15 The Abstract Stack Machine PDF

Preview

Summary

Abstract Stack Machine...

Description

Ch 15: The Abstract Stack Machine abstract stack machine: model programs in presence of mutable state ASM properly accounts for locations of data in the computer's memory hides many of the details of the computer's actual memory structure & representation of data 15.1 Parts of the ASM values: finished results such as integers, tuples of values, records, functions, or constructors applied to values ex.

0, 1, (1, (2, 3)), {x = 0; y = 1}, Cons(3, Nil)

expressions: computations in progress ex.

1 + 2 * 3, (f x), p.x, begin match...with...end

ASM gives explicit algorithm for implementing substitution using a stack, refines notion of value & computation model to keep track of where in memory data structures reside 3 basic parts of ASM model workspace: keeps track of expression or command that computer is currently simplifying, as program evaluates, contents of workspace change stack: keeps track of a sequence of bindings that map identifiers to their values new bindings are added to stack when

let

expression is simplified

when an identifier is encountered during simplification, assoc value can be found in stack keeps track of partially simplified expressions heap: models computer's memory, used for storage of non-primitive data values

specifies abstractly where data structures reside, shows how they reference one another 15.2 Values and References to the Heap ASM makes distinction btwn two kinds of values primitive values: integers, booleans, characters, & other small pieces of data for which computer provides basic operations references: address or location of a piece of data in the heap draw a reference as an arrow, start of the arrow is reference itself (address), arrow points to piece of data in heap (location) heap contains 3 diff kinds of data cell: labeled by a datatype constructer (ex. Cons or Nil) & contains a sequence of constructor arguments arguments to constructor are values constructor names take up some amt of space in heap record: contains a value for each of its fields field names of a record don't take up space in heap mark mutable record fields using a doubled box (ex. record of type point ) function: anonymous function value 15.1 shows stack binding for

append

is a reference to the code for

function itself bc append is recursive (use of identifier append in the body has been replaced w reference to code for whole function) append

References as Abstract Locations reference = abstract representation of location in heap doesn't matter exactly where the location being pointed to is

if references point to the same location → aliases, sharing among data structures 15.3 Simplification in the ASM processes program by repeatedly simplifying workspace until contains only a value creates new bindings in the stack, allocates data structures in the heap, and can modify contents of mutable record fields starts with entire program in workspace, stack and heap are empty begins with leftmost (ready) subexpression and simplifies it expression involving a primitive operator is ready if all of its arguments are values, simplified by replacing the expression with its result let expression let x : t = e is ready if e is a value, simplified by adding a new binding for the identifier x to e at END of stack, leave body in workspace variable is always ready, simplified by looking up binding associated w variable in the stack & replacing it (most recent to least recent bindings) conditional expression if e then e1 else e2 is ready if e is true or false, simplified by replacing w e1 or e2 Shadowing and the Stack stack: only PUSH elements on to the stack and POP them off in a last-in-firstout manner stack discipline ensures that most recently defined value will be used during computation Simplifying Datatype Constructors and

match

data constructors (ex. Cons, Nil) interact w heap, simplifying constructor allocates some space on heap, creates a reference to newly allocated space constructor is ready if all its arguments are values, simplified by allocating a heap cell w constructor tag and replacing the constructor expression w newly created reference

match expression is simplified by finding first pattern starting from pat1 and working toward patN, once matching pattern is found, ASM adds new stack bindings for each identifier in the pattern workspace is then modified to contain branchX, branch body corresponding to patX if pattern doesn't match, ASM aborts the computation w

Match_failure

error

Simplifying Functions 3 parts: moving function values to the heap calling a function returning a value computed by function to some enclosing workspace top level declarations → shorthand for naming anonymous functions ASM simplifies declaration into fun expression then moves to the heap, replaces fun expression w newly created reference let → binding for function name on stack calling a function function may be nested within a larger expression that needs to be simplified ASM must keep track of where the value computed by a function call should be returned function call is ready to simplify if function is a reference and all of its arguments are values 1 saves current workspace to stack, marks the spot where "answer" should be returned w a hole 2 adds new stack bindings for each of the called function's parameters 3 workspace replaced by the body of the function once function call has been initiated & function body is in workspace, simplification continues

when workspace contains a value and there is at least one saved workspace on stack, ASM returns the value to the old workspace popping - removing all of the stack bindings that have been introduced since last saved workspace, replaces current workspace w/ last saved worksapce ⟶ replaces answer "hole" w value v Simplifying Mutable Record Operations Rules for simplifying records, field projections, & mutable field updates record expression is ready if each of its fields is a value, simplify record by allocating record structure in heap & replace record expression w reference to that structure mark mutable fields of a record using double-lined box record field projection expression (ex.

p.x

) is ready if p is a value,

simplified by replacing expression by value stored in x field of record in heap mutable field update expression (ex.

p.x x let x2 = fun x -> x ;; run_failing_test "structural equality: functions" (fun () -> x1 = x2)

can use reference equality to determine if two function values are stored in same heap location (fun () -> x1 == x1) (fun () -> not (x1 == x2))...