September 15, 1981
Preliminary formal semantics of Interdoc
DRAFT —PLEASE DO NOT QUOTE—DRAFT
GRAMMAR
script::= versionId item
item::= value | binding | label
value::= term | node
term::= primary | primary op term
op::= "+" | "−" | "*" | "/"
primary::= literal | invocation | application | selection | sequence
literal::= Boolean | integer | hexint | real | string
invocation::= name | universal
name::= id ( "." id )*
universal::= "$" name
application::= invocation "[" item* "]"
selection::= "(" term "|" item* "|" item* ")"
sequence::= "(" ( value | binding )* ")"
node::= "{" item* "}"
binding::= name mode rhs
mode::= "=" | ":" | ":=" | "←"
rhs::= value | op term | "’" item* "’" | "[" [ invocation ] "|" binding* "]"
label::= mark | link
mark::= invocation "#"
link::= id "@!" | name "@" | name "!"
SEMANTIC FUNCTIONS
R: expression, environment −> expression-- Reduction
C: expression −> expression-- Contents
B: expression, environment −> environment-- Bindings
M: expression −> expression-- Marks
L: expression −> expression-- Link introductions
S: expression −> expression-- Link sources
T: expression −> expression-- Link targets
GRAMMATICAL FEATURE X SEMANTIC FUNCTION MATRIX
FEATURES:FUNCTIONS:RCBMLST
term ::= primary op term+=−−−−−
primary ::= literal= =−−−−−
invocation ::= id+−+−−−−
invocation ::= name "." id +−+−−−−
universal ::= "$" name= =−−−−−
application ::= invocation "[" item* "]"+−−−−−−
selection ::= "(" term "|" item1* "|" item2* ")"+−+−−−−
sequence ::= "(" ( value | binding )* ")"+=+−−−−
node ::= "{" item* "}"+=+−−−−
item* ::= item1 item*+++++++
binding ::= name mode rhs−−+−−−−
rhs ::= "’" item* "’"+−−−−−−
rhs ::= "[|" binding* "]"+−−−−−−
rhs ::= "[" invocation "|" binding* "]"+−−−−−−
mark ::= invocation "#"+−−+−−−
link ::= id "@!"= −−−+−−
link ::= name "@"= −−−−+−
link ::= name "!"= −−−−−+
− Semantic function produces Nil or E or does not apply.
+ Non-trivial semantic equation.
= For R: passes value unchanged; for C: value same as R.
PRESENTATION BY FEATURE
DRAFT —PLEASE DO NOT QUOTE—DRAFT
[E is used to represent the value of the environment in which the feature
occurs.]
term ::= primary op term
op ::= "+" | "−" | "*" | "/"
R = C = R<primary>(E) op R<term>(E)
B = E
M = L = S = T = Nil
-- Both the primary and the term must reduce to numbers; the arithmetic
operators are evaluated right-to-left (a la APL, without precedence) and bind less
tightly than application.
primary ::= literal
literal ::= Boolean | integer | hexint | real | string
R = C = literal
B = E
M = L = S = T = Nil
-- The basic contents of a document.
invocation ::= id
R = R<valOf(id, E)>(E)
B = B<valOf(id, E)>(E)
where
valOf(id, E) = locVal(id, whereBound(id, E))-- Gets innermost value
whereBound(id, E) = CASE-- Gets innermost binding
locBinding(id, E) ~= None=> E
locBinding("Outer", E) ~= None=>
whereBound(id, locVal("Outer", E))
True=> Null
-- Both attributes and definitions are looked up in the current environment;
depending on the current binding of id, this may produce values and/or
bindings; if the binding’s rhs was quoted, the expression is evaluated at the
point of invocation.
invocation ::= name "." id
R = R<valOf(id, R<name>(E))>(E)
B = B<valOf(id, R<name>(E))>(E)
-- Qualified names are treated as "nested" environments.
universal ::= "$" name
R = C = "$" name
B = E
M = L = S = T = Nil
-- Names prefixed with a $ are presumed to be directly meaningful, and are not
looked up in the environment.
application ::= invocation "[" item* "]"
R = apply(invocation, R<item*>(E), E)
B = E
where
apply(invocation, value*, E) =
CASE R<invocation>(E) OF
"$equal"=> value1 = value2
"$greater"=> value1 > value2
. . .
"$subscript"=> value1[value2]-- value1: sequence, value2: int
"$contents"=> "(" C<inner(value1)> ")"
"$marks"=> "(" M<inner(value1)> ")"
"$links"=> "(" L<inner(value1)> ")"
"$sources"=> "(" S<inner(value1)> ")"
"$targets"=> "(" T<inner(value1)> ")"
ELSE => R<invocation>([[Null | "Outer" "=" E] | "Value" "=" value*])
inner("{" value* "}") = value*
-- If the invocation does not evaluate to one of the standard external function
names, the current environment is augmented with a binding of the value of the
argument list to the identifier Value, and the value is the result of the
invocation in that environment; this allows function definition within the
language.
selection ::= "(" term "|" item1* "|" item2* ")"
R = if R<term>(E) then R<item1*>(E) else R<item2*>(E)
B = if R<term>(E) then B<item1*>(E) else B<item2*>(E)
-- This is a standard conditional expression/binding, using syntax borrowed from
Algol 68.
sequence ::= "(" item* ")"
R = C = "(" R<item*>(E) ")"
B = B<item*>(E)
M = L = S = T = Nil
-- Parentheses group a sequence of items as a single value; bindings in the
sequence affect the environment of items to the right in the containing node,
but labels are disallowed. Parentheses may also be used to override the
right-to-left evaluation of arithmetic operators; an operand sequence must reduce
to a single numeric value.
node ::= "{" item* "}"
R = C = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"
B = locVal("Outer", (B<"Sub" item*>([Null | "Outer" "=" E])))
M = L = S = T = Nil
-- Nodes have nested environments, and affect the containing environment only
through persistent (:=) bindings to ids with outer VAR (:) bindings. The items
of a node are implicitly prefixed with the id Sub, which may be bound to any
information intended to be common to all subnodes in a scope.
item* ::= ""
R = C = M = L = S = T = Nil
B = E
-- The empty sequence of items has no value and no effect; this is the basis for
the following recursive definition.
item* ::= item1 item*
R = R<item1>(E) R<item*>(B<item1>(E))
B = B<item*>(B<item1>(E))
For F in {C, M, L, S, T}:
F = F<item1> F<item*>
-- In general, the value of a sequence of items is just the sequence of item
values; binding items affect the environment of items to their right; Nil does not
change the length of a result sequence.
binding ::= name mode rhs
R = Nil
B = bind(name, mode, R<rhs>(E), E)
where
bind(id, mode, value, E) = CASE
bindingOf(id, E) = "="=> E-- Can’t rebind constants
mode = ":=" => assign(id, value, E)
True=> [E | id mode value]
bind(id "." name, mode, value, E) =
[E | id bindingOf(id, E) bind(name, mode, value, valOf(id, E))]
bindingOf(id, E) = locBinding(id, whereBound(id, E))
assign(id, value, E) = CASE
locBinding(id, E) = ":"=> [E | id ":" value]
bindingOf(id, E) = ":"=> bind("Outer." id, ":=", value, E)
True=> E -- Can only assign to vars
-- This adds a single binding to E; bindings have no other "side effects" and no
value.
binding ::= name mode op term
= <name mode name op term>
-- This is just a convenient piece of syntactic sugar for the common case of
updating a binding.
rhs ::= "’" item* "’"
R = item*
-- A quoted rhs is evaluated at the point of invocation, rather than the point of
binding.
rhs ::= "[|" binding* "]"
R = [B<binding*>([Null | "Outer" "=" E]) | "Outer" "=" Null]
-- This creates a new environment value that may be used much like a record.
rhs ::= "[" invocation "|" binding* "]"
R =[B<binding*>([R<invocation>(E) | "Outer" "=" E]) | "Outer" "=" Null]
-- This creates a new environment value that is an extension of an existing one.
mark ::= invocation "#"
R = R<invocation>(E) "#"
M = invocation
B = E
C = L = S = T = Nil
-- This gives the containing node the property denoted by the mark to which
the invocation reduces.
link ::= id "@!"
R = id "@!"
L = id
B = E
C = M = S = T = Nil
-- This defines the scope of the set of links whose "main" component is id.
link ::= name "@"
R = name "@"
S = name
B = E
C = M = L = T = Nil
-- This identifies the containing node as a "source" of the link name.
link ::= name "!"
R = name "!"
T = prefixes(name)
B = E
C = M = L = S = Nil
where
prefixes(id) = id
prefixes(name "." id) = name "." id prefixes(name)
-- This identifies the containing node as a "target" of each of the links that is a
prefix of name.
DRAFT —PLEASE DO NOT QUOTE—DRAFT
HINTS TO IMPLEMENTORS
Scopes: The scope of a binding always begins (textually) at the point where the
binding appears, and extends strictly to its right. This should simplify the
processing of environments in a single left-to-right scan. Constant bindings are
unchangeable within a scope.
Environment restoration: Some constructs in the language are not allowed to have
a "net effect" on the environment, even though they may contain internal
bindings that will be in effect for some or all of their substructures. Thus, a
program to process Interdoc scripts must make provision for restoration of saved
environments. The amount of bookkeeping required to do this can be minimized
by the following observations:
- A rhs always produces a value (which may be an environment), which is
then bound to a name in the environment that obtained when the binding was
encountered. Thus, occurrence of a bindingMode (=, :, :=, ←) signals a potential
restoration point.
- Any application (but not every invocation), any term containing infix ops,
and any mark will leave the environment unchanged. Thus the appearance of
an operator, the bracket surrounding an argument list, or # signals a potential
restoration point; the environment to be saved is the one BEFORE the invocation
to its left. (One-character lookahead before invocation is prudent.)
- Environments are NOT restored at the end of sequences.
- The environment at the end of a node is the final value of the Outer
component of the node’s environment; unless the node contains persistent (:=)
bindings, this will be the same as the environment just prior to the node.
Coding tricks for common structures:
- Attributes that tend to persist across boundaries in the dominant structure (e.g.,
Bravo character looks, which persist from paragraph to paragraph unless
explicitly changed by the user) should generally be represented by VAR (:)
bindings at a high-level node in the script; changes would then be represented
by persistent (:=) bindings at the points where they occur.
- Persistent bindings can also be used to record changes to "running" information
(e.g., section number, figure number).
- Information (e.g., marks) repeated in all subnodes of a node should be bound to
Sub, and hence associated with the subnodes implicitly.
- Very compact encodings can often be obtained by using single-character id’s
for common sequences of items; each editor can have its own set, tuned to its
own usages. When reading a script produced by a different editor, it will be
necessary to know the bindings for these abbreviations.
- Common editing operations may be represented by definitions with short names
(e.g., Look Keep 40 in Bravo might become "L.K[40]").
APPENDICES
ALTERNATE PRESENTATIONS OF THE SEMANTIC EQUATIONS
DRAFT —PLEASE DO NOT QUOTE—DRAFT
PRESENTATION BY FUNCTION
R: expression, environment −> expression-- Reduction
R<construct>(E) = CASE <construct> OF
<primary op term>=> R<primary>(E) op R<term>(E)
<literal>=> literal
<id>=> R<valOf(id, E)>(E)
<name "." id>=> R<valOf(id, R<name>(E))>(E)
<"$" name>=> "$" name
<invocation "[" item* "]"> => apply(invocation, R<item*>(E), E)
<"(" term "|" item1* "|" item2* ")"> =>
if R<term>(E) then R<item1*>(E) else R<item2*>(E)
<"(" item* ")">=> "(" R<item*>(E) ")"
<"{" item* "}">=> "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"
<>=> Nil
<item1 item*>=> R<item1>(E) R<item*>(B<item1>(E))
<name mode rhs>=> Nil
<"’" item* "’">=> item*
<"[|" binding* "]">=>
[B<binding*>([Null | "Outer" "=" E]) | "Outer" "=" Null]
<"[" invocation "|" binding* "]"> =>
[B<binding*>([R<invocation>(E) | "Outer" "=" E]) | "Outer" "=" Null]
<invocation "#">=> R<invocation>(E) "#"
<link>=> link
C: expression −> expression-- Content of node
C<construct> = CASE <construct> OF
<value>=> value
<label>=> Nil
<item1 item*>=> C<item1> C<item*>
B: expression, environment −> environment-- Bindings
B<construct>(E) = CASE <construct> OF
<id>=> B<valOf(id, E)>(E)
<name "." id>=> B<valOf(id, R<name>(E))>(E)
<"(" term "|" item1* "|" item2* ")">(E) =>
if R<term>(E) then B<item1*>(E) else B<item2*>(E)
<"(" item* ")">=> B<item*>(E)
<"{" item* "}">=>
locVal("Outer", (B<"Sub" item*>([Null | "Outer" "=" E])))
<item1 item*>=> B<item*>(B<item1>(E))
<name mode rhs>=> bind(name, mode, R<rhs>(E), E)
ELSE=> E
M: expression −> expression-- Sequence of marks
M<construct> = CASE <construct> OF
<name "#">=> name
<item1 item*>=> M<item1> M<item*>
ELSE=> Nil
L: expression −> expression-- Sequence of links
L<construct> = CASE <construct> OF
<id "@!">=> id
<item1 item*>=> L<item1> L<item*>
ELSE=> Nil
S: expression −> expression-- Sequence of source links
S<construct> = CASE <construct> OF
<name "!">=> prefixes(name)
<item1 item*>=> S<item1> S<item*>
ELSE=> Nil
T: expression −> expression-- Sequence of target links
T<construct> = CASE <construct> OF
<name "@">=> name
<item1 item*>=> T<item1> T<item*>
ELSE=> Nil
SEMANTICS: REDUCTION AND BINDING
R: expression, environment −> expression-- Reduction
B: expression, environment −> environment-- Bindings
R&B<construct>(E) denotes the pair R<construct>(E); B<construct>(E)
[Unless explicitly given below, B<construct>(E) = E.]
R<primary op term>(E) = R<primary>(E) op R<term>(E)
R<literal>(E) = literal
R&B<id>(E) = R&B<valOf(id, E)>(E)
R&B<name "." id>(E) = R&B<valOf(id, R<name>(E))>(E)
R<"$" name>(E) = "$" name
R<invocation "[" item* "]">(E) = apply(invocation, R<item*>(E), E)
R&B<"(" term "|" item1* "|" item2* ")">(E) =
if R<term>(E) then R&B<item1*>(E) else R&B<item2*>(E)
R&B<"(" item* ")">(E) = "(" R<item*>(E) ")" ; B<item*>(E)
R&B<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}";
locVal("Outer", (B<"Sub" item*>([Null | "Outer" "=" E])))
R<>(E) = Nil
R&B<item1 item*>(E) = R<item1>(E) R<item*>(B<item1>(E));
B<item*>(B<item1>(E))
R&B<name mode rhs>(E) = Nil; bind(name, mode, R<rhs>(E), E)
<name mode op term> = <name mode name op term>-- Syntactic sugar
R<"’" item* "’">(E) = item*--Usable only in rhs of binding
R<"[|" binding* "]">(E) = [B<binding*>([Null | "Outer" "=" E]) | "Outer" "=" Null]
R<"[" invocation "|" binding* "]">(E) =
[B<binding*>([R<invocation>(E) | "Outer" "=" E]) | "Outer" "=" Null]
R<invocation "#">(E) = R<invocation>(E) "#"
R<link>(E) = link
SEMANTICS OF CONTENTS AND LABELS
C: expression −> expression-- Contents of node
M: expression −> expression-- Sequence of marks
L: expression −> expression-- Sequence of links
S: expression −> expression-- Sequence of source links
T: expression −> expression-- Sequence of target links
[These functions all return the empty string, Nil (which does not lengthen a
sequence), except as specified below.]
C<value> = value
C<label> = Nil
C<item1 item*> = C<item1> C<item*>
M<name "#"> = name
M<item1 item*> = M<item1> M<item*>
L<id "@!"> = id
L<item1 item*> = L<item1> L<item*>
S<name "!"> = prefixes(name)
S<item1 item*> = S<item1> S<item*>
T<name "@"> = name
T<item1 item*> = T<item1> T<item*>
prefixes(id) = id
prefixes(name "." id) = name "." id prefixes(name)
DRAFT —PLEASE DO NOT QUOTE—DRAFT