IntCodeUtils.mesa
Copyright Ó 1986, 1987, 1991 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) December 21, 1987 2:40:50 pm PST
JKF July 27, 1988 9:33:03 am PDT
Willie-s, September 23, 1991 5:55 pm PDT
DIRECTORY
Basics USING [LongNumber],
IntCodeDefs USING [Label, Location, Node, NodeList, Var, VarList, Word];
Node walking routines
Visitor:
TYPE =
PROC [node: Node]
RETURNS [Node];
The type of callback procedure for the following routines. In most cases the visitor must return a var node when given a var node.
MapNode:
PROC [node: Node, visitor: Visitor];
Applies visitor to update each of the component nodes in node (visitor is not applied to node). Component nodes of component nodes are not visited.
MapNodeList:
PROC [nodeList: NodeList, visitor: Visitor];
Applies visitor to update each of the component nodes in the given node list. Component nodes of component nodes are not visited.
MapVarList:
PROC [varList: VarList, visitor: Visitor];
Applies visitor to update each of the component nodes in the given variable list. Component nodes of component nodes are not visited.
MapLocation:
PROC [location: Location, visitor: Visitor];
Applies visitor to update each of the component nodes in location. Component nodes of component nodes are not visited.
VisitLabels:
PROC [node: Node, visitor: LabelVisitor, fullTree:
BOOL, visitNIL:
BOOL ¬
FALSE];
VisitLabels applies visitor to labels under node. If fullTree, then VisitLabels will completely traverse the tree rooted at node. If NOT fullTree, then VisitLabels will only visit the label directly under node, and will not visit component nodes of node. If visitNIL, then labels that are NIL will be visited as well as non-NIL labels.
LabelVisitor:
TYPE =
PROC [label: Label, node: Node, define:
BOOL]
RETURNS [Label];
The callback routine is passed the label, the closest node that the label occurs in, and a flag indicating whether this is the definition point for the label.
Word conversion routines
PrincOpsHost: BOOL = (BITS[WORD] = 16);
SwapWords:
PROC [w: Basics.LongNumber]
RETURNS [Basics.LongNumber] =
INLINE {
RETURN[[pair[w.hi, w.lo]]];
};
WordToInt:
PROC [w: Word]
RETURNS [
INT] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[w]].int]
ELSE RETURN[LOOPHOLE[w]];
};
IntToWord:
PROC [i:
INT]
RETURNS [Word] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[i]].bits]
ELSE RETURN[LOOPHOLE[i]];
};
WordToCard:
PROC [w: Word]
RETURNS [
CARD] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[w]].card]
ELSE RETURN[LOOPHOLE[w]];
};
CardToWord:
PROC [c:
CARD]
RETURNS [Word] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[c]].bits]
ELSE RETURN[LOOPHOLE[c]];
};
WordToReal:
PROC [w: Word]
RETURNS [
REAL] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[w]].real]
ELSE RETURN[LOOPHOLE[w]];
};
RealToWord:
PROC [r:
REAL]
RETURNS [Word] =
INLINE {
IF PrincOpsHost THEN RETURN[SwapWords[LOOPHOLE[r]].bits]
ELSE RETURN[LOOPHOLE[r]];
};
Equality & side effect routines
SideEffectFree:
PROC [node: Node, noSignals:
BOOL]
RETURNS [
BOOL];
Returns TRUE if the evaluation of node is guaranteed to not have side effects (conservative: may return FALSE even when actually side effect free).
IF noSignals THEN raising a signal is considered to be a side effect.
SideEffectFreeList:
PROC [nodes: NodeList, noSignals:
BOOL]
RETURNS [
BOOL];
Returns TRUE if the evaluation of all nodes in the list is guaranteed to not have side effects (conservative: may return FALSE even when actually side effect free).
IF noSignals THEN raising a signal is considered to be a side effect.
SimplyEqual:
PUBLIC
PROC [n1, n2: Node]
RETURNS [
BOOL];
Returns TRUE if the nodes are structurally equal according to a conservative determination determination (may return FALSE even when the nodes are equal).
SimplyEqualList:
PUBLIC
PROC [nl1, nl2: NodeList]
RETURNS [
BOOL];
Returns TRUE if the node lists are structurally equal according to a conservative determination (may return FALSE even when the lists are equal).
IsSimple:
PUBLIC
PROC [node: Node, level: SimplicityLevel]
RETURNS [
BOOL];
Returns TRUE if the node given is sufficiently simple. A procedure call or side-effect is always not simple.
IsSimpleList:
PUBLIC
PROC [list: NodeList, level: SimplicityLevel]
RETURNS [
BOOL];
Returns TRUE if IsSimple is TRUE for every node in the list. An empty list is always simple.
SimplicityLevel:
TYPE =
RECORD [
derefs: [0..4) ¬ 0,
max # of deref nodes to allow & still be simple
simpleOps: [0..4) ¬ 0,
max # of simple operations to allow & still be simple
(any procedure call is not simple, indexing is a simple op)
noSignals:
BOOL ¬
FALSE,
if noSignals, then raising a signal is considered to be a side effect (not simple)
maxBits:
CARD16 ¬ 0
max # of bits to allow & still be simple (0 => no limit)
];
IDTab types & routines
An IdTab provides an association between Id's and Value's. It is useful for keeping track of various properties for Id's.
The idea for converting this into non-Cedar code is to replace Value: TYPE = REF with Value: TYPE = LONG POINTER. Then the user is obligated to perform the discrimination based on static knowledge. Luckily we don't have to do that yet.
IdTab: TYPE = REF IdTabRep;
IdTabRep:
TYPE =
RECORD [
entries: INT ¬ 0,
data: REF ¬ NIL
];
Id: TYPE = INT;
Value:
TYPE =
REF;
NullValue: Value = NIL;
NewIdTab:
PROC
RETURNS [IdTab];
Returns a new id tab with no elements.
Fetch:
PROC [idTab: IdTab, id: Id]
RETURNS [Value];
Fetches the value associated with the given id in the given table. Returns NullValue if there was no value.
Store:
PROC [idTab: IdTab, id: Id, val: Value ¬ NullValue]
RETURNS [Value];
Stores a new value for the given id. Returns the old value (or NullValue if none). Storing NullValue is equivalent to deleting the old value.
Insert:
PROC [idTab: IdTab, id: Id, val: Value]
RETURNS [Value];
Stores a new value for the given id only if there was no previous value. Returns the old value (or NullValue if none). Inserting NullValue is a null operation.
Enumerate:
PROC [idTab: IdTab, visitor: IdTabVisitor];
IdTabVisitor: TYPE = PROC [id: Id, value: Value] RETURNS [stop: BOOL ¬ FALSE];
Applies the visitor to each association in the table.