Left-to-right evaluation

The left-to-right evaluation required by the informal semantics of Appel's language need not be strictly followed, provided that the results are those that would be obtained with left-to-right evaluation. Expressions can therefore be evaluated in any order, provided that all of the memory accesses are properly sequenced.

Memory operations depend upon one another because they manipulate a shared data structure. The LIDO CHAIN implements a depth-first, left-to-right dependence relation, so this construct can be used to enforce the sequence of memory operations.

The MemoryDep chain corresponds to the memory of the interpreter. It does not carry a value from one computation to another, as do the Value, Left and Right attributes. Therefore it should be declared of type VOID:

Left-to-right evaluation[38] :

CHAIN MemoryDep: VOID;

RULE: Program ::= Stm
COMPUTE
  CHAINSTART Stm.MemoryDep="done";
END;

RULE: Stm ::= id ':=' Exp
COMPUTE
  Stm.MemoryDep=Store(id,Exp.Value) <- Exp.MemoryDep;
END;

RULE: Exp ::= id
COMPUTE
  Exp.Value=Fetch(id) <- Exp.MemoryDep;
  Exp.MemoryDep=Exp.Value;
END;

This macro is invoked in definition 49.

Note that each computation is ``inserted'' into the chain -- the computation depends on the chain (via <-), and the subsequent chain depends on the computation (via =). Thus the computations are ordered along a depth-first, left-to-right traversal of the tree. That tree traversal corresponds to a text-order traversal if none of the text's phrases were re-ordered when the tree was built.

A VOID chain has no physical existence in the final implementation, and therefore it occupies no space and requires no computation time. It's only purpose is to make dependence explicit so that the computations can be arranged in the proper order.

Store and Fetch provide the actual memory access. They are exported by an abstract data type whose implementation is given in Section 3.3. This illustrates the normal division of labor for such specifications: LIDO is concerned with the global dependence among computations that are defined by abstract data types.

Dependence among print statements is a consequence of the output device, not the memory. Thus that dependence can be enforced using another chain corresponding to the output device:

Print statement sequencing[39] :

CHAIN OutputDep: VOID;

RULE: Program ::= Stm
COMPUTE
  CHAINSTART Stm.OutputDep="done";
END;

RULE: Stm ::= 'print' '(' ExpList ')'
COMPUTE
  Stm.OutputDep=
    PTGOut(
      PTGLine(
        CONSTITUENTS Exp.Value SHIELD Exp
        WITH (PTGNode, PTGSeq, PTGValue, PTGNull))) <- ExpList.OutputDep;
END;

This macro is invoked in definition 49.

The actual construction of the line to be printed is treated as a problem of structured output: A Value is an integer, two Values can be assembled into a Seq by separating them with a space, and a Value or Seq resulting from the argument(s) of a print statement constitutes a Line that should be terminated by a newline character. These statements can be formalized in the specification language of a pattern-based text generator:

Output patterns[40] :

Value: SPMdollar; int
Seq:   $ { " " } SPMdollar;
Line:  $ "\n"

This macro is invoked in definition 50.

For each pattern, the generator will create a function whose name is PTG followed by the name of the pattern. That function has a number of arguments based on the $ markers in the pattern, and returns an object of type PTGNode. A built-in function PTGOut writes the value specified by its argument to the standard output stream.

CONSTITUENTS is a remote attribution that reaches down the tree to gather values. In this example it seeks all Value attributes of Exp nodes that are not SHIELDed by other Exp nodes. It will apply PTGValue to each such attribute to obtain a value of type PTGNode. It will then use PTGSeq to combine adjacent values. If there is a subtree containing no Exp nodes, CONSTITUENTS will use PTGNull to generate a value of type PTGNode. (PTGNull is a built-in function that creates a PTGNode representing the empty string.)