Chapter 7
Lowering From the Flow Stage
Conversion from the Flow stage to the Exec stage turns a module of Code IR whose functions call the operations of the Flow dialect into a module at the Exec stage, so that the backends print the rules of a grammar as they print the compositions. Conversion is complete: the structure of each function, its blocks, loops, branches, exits, assignments and the arithmetic and logic of its conditions, its locals and its registers are kept, and every call of an operation of the Flow dialect becomes a call of the primitive operation that stands for it. The result is verified at the Exec stage (see Invariants), where an operation of the Flow dialect is not legal, so that a call left unconverted is reported. Operations of the Action dialect, which are legal at both stages, are kept as they are.
The Module
The module at the Exec stage lists the Exec and Action dialects as the dialects legal in it. It declares:
- the component
runtime, the state of the runtime that the primitives change; - the registers and handle types of the Flow module, the handle types in the component
runtime; - every operation of the Action dialect that the Flow module declares, unchanged;
- a primitive operation for each operation of the Flow dialect that the Flow module declares (below).
Operations of Primitives
The primitive that stands for an operation of the Flow dialect is named runtime. followed by the operation's name
without flow., as runtime.matchLit stands for flow.matchLit; the correspondence is one to one. It is an operation
of the kind primitive (printed primitive op) of the Exec dialect and the component runtime, and has the signature,
contract, cost bound, laws, features and immediate operand of the Flow operation, of the same type; an operation
without a primitive, or whose immediate is of another type than its primitive's, is not converted. The state
component of the Flow dialect is runtime, in the places where the Flow operation names it. The arguments of a call
are those of the Flow call, in the same order, so that passes see the reads that the Flow dialect declares. A primitive
has no reference model, because each target prints it in place, in its own form; the conformance of a target per
primitive is checked as Printing describes.
Variables, Registers and Labels
- The variables, registers and labels of the Flow function keep their names, types and meaning in the Exec function:
the registers
posandcutare the registers of the machine, and a register that holds a handle, the environment or the frame, is read and assigned with the calls that the Flow function holds. - A label without a name, which no printer shows, is named
loop.followed by a number.
The Function
The function keeps its name, its parameters, its locals and its body, and its attributes become the attributes of the Exec stage: each attribute of the Flow function except the record of the forms of the lowering, which the passes of the Flow stage consume before the conversion, so a function that still holds forms is not converted. The verifier of the Exec stage rejects a function whose attributes are of another stage, as it rejects an operation of the Flow dialect. The body is a block labeled with the function's failure label, so that an exit to that label leaves the body; the code that holds the printed body continues after success and after failure. The functions of the Flow dialect are described in Functions.
Action Expressions
An action expression of the action language, the action of a rule or of a line of an Operators Rule, the action expression of a predicate or the
value of a binding, is lowered from Core IR into a function of its own, in a module that declares the abstract machine, the
compositions of the operators of action expressions (Values) with every function they call, the component runtime,
and the operations of the leaves of action expressions below, which are operations of the Action dialect and legal at both stages. Two optimizations of a target are options of the
lowering:
- With
field-compare(a typed parser of Go), a comparison (==,!=,<,<=,>,>=) of which an operand reads a field is a call ofaction.compareon two operands: a field read is read byaction.fieldOperand, after the value it reads from, and any other operand is its value made an operand byaction.operand, in the order written. A string field is then compared without making a value of it. - With
text-dispatch, a predicate that compares the text of one capture with string literals,text($x) == "a" || text($x) == "b"and so on, first testsaction.uncontrolled: without limit controls it takes the text of the capture withtextand tests whetheraction.textInfinds it among the distinct literals; with them it evaluates the action expression as written. With two or more distinct literals the result is bound to a local first, which a target may print as one switch over the literals; with one distinct literal (repeats collapse) it is returned directly, as a plain equality.
A cast to a type that every value fits checks nothing; a target that charges a step for each subexpression charges one for it too.
The function evaluates the action expression's operands in the order that the action expression evaluates them and calls one composition for
each operation of the action expression: binary for a binary operator, unary for a unary one, member for a member read, with
the kind of the member read and the name of the field or capture that the name of the member selects (Member
Kinds), length and text for the built-in functions, convert for a conversion to a
named node type and conforms for a cast. The function returns the action expression's value and its failure, null when the action expression
does not fail, as a composition does. Each composition that can fail is the value of a Let of its value and its
failure, followed by a branch that returns the null value and the failure when there is one. A cast keeps its operand
in a local and, when conforms rejects it, returns the failure that action.castError makes of it. The caller handles
the failure: a predicate or a binding fails, and an action ends the parse with an evaluation error. A target that
evaluates an action in place, inside the function of its rule, instead of calling the action expression's function, ends the parse
at each failure with action.raise. A logical operator calls logic on its left
operand, and evaluates its right operand and calls logic on it only when the left one does not decide the result.
An equality or inequality of two calls of text compares the two strings with action.textEqual, without making a
value of either.
A tuple literal and a call of list take the mark of the elements gathered (the component gathered) with action.kids, push the
value of each element with push, charging a step for it with seq.step before, take the elements gathered above the
mark with action.elemsAbove and make the tuple or list value of them with hull. A call of concat pushes the
elements of each argument with pushItems, charging a step for the argument; when every argument is a call of list
or such a call of concat, the elements of the arguments are pushed as list pushes them, without making the lists
of the arguments; a call of map among them pushes its elements as map pushes them, below. A struct literal evaluates its field values in the order written. A target whose structs are made of
their fields makes an empty struct with action.struct and, for each field in that order, charges a step with
seq.step, sets the field with action.setField and widens the range of the struct with cover; made then records
the struct. A target with a constructor for each struct type calls it once, with action.new followed by the number
of fields that the type declares, passing the values in the order the type declares the fields and nil for a field
that the literal does not give; a value is kept in a local before the next one is evaluated only when the literal
gives the fields in another order.
A built-in function that takes a function (map, filter, foldl and foldr) evaluates its arguments other than
the lambda in the order written, reads the elements of its list argument with items, which fails for a value that
is not a list, a tuple or nil, and loops over them. Each step of the loop charges a step with seq.step, takes the
element with itemAt and evaluates the body of the lambda in place, with its parameters bound to locals of the loop;
a parameter is read with val.unbox, since it may hold a box. map takes the mark of the elements gathered with
action.kids after its list argument, pushes the value of the body for each element with push and makes the list
value of the values above the mark with hull. filter does the same, but calls filterKeep on the value of the
body and pushes the element itself, as it is, with action.keep when it keeps it. foldl and foldr keep the
accumulator, their first argument, in a local, bind it and the element to the parameters, and assign the value of the
body to it; foldr takes the elements from the last. A call map($x, (e) => e.$f) of a projected capture x, a
capture whose elements the target keeps as the captures f of the elements, makes a list value of the elements of
x as they are with action.copyList; when it is an argument of a concat whose arguments are pushed as they are
made, its elements are pushed with pushItems, as those of an argument of concat.
A target that does not bound the work leaves out the calls of seq.step. A target that charges a step for each subexpression of an action expression under budget controls lowers it with a call
of action.spend at the start of each subexpression, before its operands; it also calls action.spend once for each tuple
literal and each call of list, including those whose elements a concat pushes, after the values of the elements
and before the first push, once for each argument of a concat whose arguments are not pushed as list
pushes them and for each projected map among the arguments of one whose are, before its pushItems, and once for
each other call of map, before items. A variable is read into a local where the action expression
reads it, since reading it charges the budget; the other leaves are operands of the calls that read them. The
function takes the context that the action expression is applied to as its one parameter, which member, push, pushItems, hull and
made take. An action expression lowered for its value returns it and has the signature of the callable type Action. An action expression that the
target evaluates in place, which assigns the value as its last statement to a local of the function that the target
declares, has no results and is never a Action handle.
The operations of the leaves are primitive operations of the Action dialect, of the component runtime, each with an
immediate operand of the type that the table names:
| Operation | Immediate operand | Contract |
|---|---|---|
action.const |
the constant | Returns the constant. |
action.read |
the capture, local or variable | Returns its value. |
action.name |
a name | Returns the name, an operand of member, push and pushItems. |
action.field |
a member and the name it reads | Returns the name of the field or the capture that the member reads, an operand of member. A target whose comparison of names charges less for the same string data than for equal bytes cuts it from the name of the member, so that the charge does not depend on whether equal literals share their data. |
action.nodeType |
the name of a named node type | Returns the node type, an operand of convert. |
action.castType |
the cast | Returns the checked type of the cast, an operand of conforms. |
action.raise |
none | Ends the parse with the failure it is given, for an action evaluated in place. |
action.castError |
the cast | Returns the failure of the cast of the value it is given. |
action.textEqual |
none | Returns whether two strings are equal, as == compares them. |
action.fromStr |
none | Returns a string as a value. |
action.spend |
none | Charges one step of the budget, under budget controls. |
action.struct |
the struct literal | Returns a new struct of the type of the literal with no field set and an empty range. |
action.setField |
the name of the field | Sets the field of a struct that the action expression is making to a value. |
action.fromObj |
none | Returns a struct, list value or tuple value as a value. |
action.copyList |
none | Returns a new list value of the elements that items returned, as they are, charging for copying them under budget controls. |
action.newN |
the struct literal | Returns the struct that the constructor of its type makes of the values of its N declared fields. |
action.fieldOperand |
the name of the member | Reads the field of a value as member does and returns it as an operand of action.compare, with the failure of the read; a string field stays a string. |
action.operand |
none | Returns a value as an operand of action.compare. |
action.compare |
the comparison operator | Applies the comparison to two operands as binary does, comparing two strings directly, and returns the value and the failure. |
action.uncontrolled |
none | Returns whether the parse runs without limit controls. |
action.textIn |
the distinct literals | Returns whether a string is one of the literals, charging nothing. |