*start* 05228 00024 USm Date: 15 July 1981 6:44 pm PDT (Wednesday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status To: Horning cc: Mitchell Jim, Here is my rendering (rending?) of my whiteboard and an attempt to solve a few loose ends. The item of which I am most unsure is the mechanism for connecting environments and the binding function in the semantics section. Have at it. ---------------------------------- We imagine an InterDoc script being processed in the following manner (or in any algorithmically equivalent way, of course): Parse the script, evaluating environment transformations (called functions in the semantics) as soon as parsed. In general, these functions may return zero or more "values": if zero, then the function has no effect on the tree structure being generated from the script; if one or more, then each of these becomes a leaf subnode of the node currently being elaborated. A node with its own substructure may also be returned. Basic InterDoc Semantics The kinds of values that can be represented in an InterDoc script are primitiveValue: NIL Boolean: {F,T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: atom:  (the null id), bold, thisIsAnAtom, Helvetica, . . . label: #A123, #anAtom, #Paragraph the empty environment: nullEnv modifier: {var,local,const,propagate,none} and sequences of primitiveValues; environment: id > value X modifier function: environment > value node: (labels, function) -> function X value The expression forms of interest come from the following set: literal id -- (should probably also have ~id) id.n -- n a name op(n,v,m) -- ( op in {+,,*,/,and,or,...}, v a value, m a modifier) bind(n,v,m) bindq(n,v,m) compose(e1,e2) invoke(n) cond(e1,e2,e3) -- if e1 then e2 else e3 The semantics of these expression forms are defined by the following evaluation rules (E=Eval,  denotes an environment; (id) is the value associated with id in ;  is the modifier of id in ; [id_(v,m)]() means " with id bound to (v,m)"): binding(id,nullEnv)=none binding(id,) = if =none then binding(id,(parent)) else  E(id,) = if =none then E(parent.id,) else (id) E(id,nullEnv) = id E(literal,) = primitiveValue(literal) E(id.n,) = E(n,(id)) E(compose(e1,e2),) = E(e2,E(e1,)) E(invoke(n),) = E(n,)() E(cond(e1,e2,e3),) = if E(e1,)=T then E(e2,) else E(e3,) E(bindq(id,v,m),) = id=parent => [ERROR_T]() binding(id,)=const => [ERROR_T]() m=var and binding(id,)=var => [id_(v,var)]([parent_E(bindq(id,v,propagate),(parent))]()) m=propagate and =none => [parent_E(bindq(id,v,propagate),(parent))]() T => [id_(v,m)]() E(bindq(id.n,v,m),) = [id_E(bindq(n,v,m),(id))]() E(bind(n,v,m),) = E(bindq(n,E(v,),m),) E(op(n,v,m),) = E(bindq(n, op(E(n,),E(v,)),m),) Notes: [ERROR_T]() simply notes that an error has occurred in a bindq in  How semantics are associated with an entire document: Each environment initially contains only its parent (as the id "parent"). When a valid bindq(id,v,var) is evaluated in an environment , it may have environmental impact on both  and (parent). It will have an effect on (parent) if already bound as var in the parent chain, in which case its effect on (parent) is bindq(id,v,propagate), which, since parent is a component of , alters  to be [parent_E(bindq(id,v,propagate),(parent))](); then, this altered , ' is further altered by modifying id, i.e., [id_(v,var)]('). An "propagate" bindq in  has the semantics that it is passed on to (parent) if =none and acts like bindq(id,v,local) otherwise. When an id is referred to and =none, then the value is sought in (parent), i.e., E(parent.id,) is evaluated (this is a recursive definition). I don't think this lengthening rule causes any problems assuming that direct assignments to parent are not allowed (the first line in the semantics of bindq rules this out). Semantics of labels: A label #atom on a node gives that node membership in the set named by atom. Multiple labels place a single node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for InterDocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] structure* ")" label ::= "#" atom structure ::= envTrans | content content ::= literal | ["'"] name | node literal ::= Boolean | integer | hexint | real | string | label name ::= atom ( "." atom)* atom ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id envTrans ::= singleTrans | compoundTrans singleTrans ::= name [ "%" ] rhs -- % means var rhs ::= Op ( compoundTrans | content ) | "." compoundTrans compoundTrans ::= "{" singleTrans* "}" Op ::= "=" | "_" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . Missing or in question: literal sequences optional quote before name in a content *start* 04792 00024 USm Date: 16 July 1981 3:36 pm PDT (Thursday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 1 To: Mitchell cc: Horning We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). In general, these functions may return zero or more "values": if zero, then the function has no effect on the tree structure being generated from the script; if one or more, then each of these becomes a leaf subnode of the node currently being elaborated. A node with its own substructure may also be returned. Basic InterDoc Semantics The kinds of values that can be represented in an InterDoc script are primitiveValue: NIL Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anAtom, #Paragraph the empty environment: nullEnv modifier: {var, local, const, assign, none} and sequences of primitiveValues; environment: id > value, modifier function: environment > value node: labels, function The functional expressions of interest come from the following set: -- by convention n: name, v: value, m: modifier, e: expression literal name -- id ( '. id)* op(n, v, m) -- ( op in {+, , *, /, and, or, ... }) bindq(n, v, m) bind(n, v, m) compose(e1, e2) invoke(n) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, function) The semantics of these expressions are defined by the following evaluation rules (E for evaluate,  denotes an environment; (id) is the value bound to id in ;  is the modifier of id in ; [id_(v, m)]() means " with id bound to (v, m)"): modifier(id, nullEnv)=none modifier(id, ) = if =none then modifier(id, (outer)) else  E(id, nullEnv) = id E(id, ) = if =none then E(id, (outer)) else (id) E(id.n, ) = E(n, (id)) E(literal, ) = primitiveValue(literal) E(compose(e1, e2), ) = E(e2, E(e1, )) E(invoke(n), ) = E(E(n, ), ) E(cond(e1, e2, e3), ) = if E(e1, )=T then E(e2, ) else E(e3, ) E(bindq(id, v, m), ) = modifier(id, )=const =>  m=assign => { =local =>  =var => [id_(v, var)]() =none => [outer_(E(bindq(id, v, assign), (outer)), local)]() } T => [id_(v, m)]() E(bindq(id.n, v, m), ) = [id_E(bindq(n, v, m), (id))]() E(bind(n, v, m), ) = E(bindq(n, E(v, ), m), ) E(op(n, v, m), ) = E(bindq(n, OP(E(n, ), E(v, )), m), ) -- where OP denotes the binary function associated with op E(node(l, f), ) = E(outer, E(f, [outer_(, local)](nullEnv))) How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in . However, the value of a bindq(id, v, assign) in an environment  will change  by rebinding id in the "innermost" environment (following the chain of outer's) in which it is bound, provided that binding has the modifier var. When an id is referred to and =none, then the value is sought recursively in (outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #atom on a node gives that node membership in the set named by atom. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: Note that we should really be using this syntax above, both to define the syntax of expressions, and in the left-hand side of the semantic equations. The low-level syntax for InterDocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] content* ")" label ::= "#" id content ::= literal | ["'"] name | node | envTrans literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id envTrans ::= singleTrans | compoundTrans singleTrans ::= name rhs rhs ::= Op ( compoundTrans | content ) | "." compoundTrans compoundTrans ::= "{" singleTrans* "}" Op ::= "=" | "_" | "%" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . -- % means var Missing or in question: literal sequences optional quote before name in a content *start* 05190 00024 USm Date: 16 July 1981 7:41 pm PDT (Thursday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 2 To: Mitchell cc: Horning We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). In general, these functions may return zero or more "values": if zero, then the function has no effect on the tree structure being generated from the script; if one or more, then each of these becomes a leaf subnode of the node currently being elaborated. A node with its own substructure may also be returned. Basic InterDoc Semantics The kinds of values that can be represented in an InterDoc script are primitiveValue: NIL Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anAtom, #Paragraph the empty environment: nullEnv modifier: {var, local, const, assign, none} and sequences of primitiveValues; environment: id > value, modifier function: environment > value node: labels, function The functional expressions of interest come from the following set: -- by convention n: name, v: value, m: modifier, e: expression literal name -- id ( '. id)* bind(n, m, op, v) -- ( op in {', +, , *, /, and, or, ... }) compose(e1, e2) invoke(n) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, function) The semantics of these expressions are defined by the following evaluation rules (E for evaluate, V for value,  denotes an environment; (id) is the value bound to id in ;  is the local modifier of id in ; [id_(v, m)]() means " with id bound to (v, m)"): E(n, ) =  E(literal, ) =  E(compose(e1, e2), ) = E(e2, E(e1, )) E(invoke(n), ) = E(V(n, ), ) E(cond(e1, e2, e3), ) = if V(e1, )=T then E(e2, ) else E(e3, ) E(bind(n, m, op, v), ) = bindq(n, m, apply(op, n, v, ), ) E(node(l, f), ) = E(outer, E(f, [outer_(, local)](nullEnv))) V(id, nullEnv) = id V(id, ) = if =none then V(id, (outer)) else (id) V(id.n, ) = V(n, (id)) V(literal, ) = primitiveValue(literal) V(invoke(n), ) = V(V(n, ), ) V(cond(e1, e2, e3), ) = if V(e1, )=T then V(e2, ) else V(e3, ) V(node(l, f), ) = node(l, evalNode(f, )) bindq(id, m, v, ) = modifier(id, )=const =>  m=assign => { =var => [id_(v, var)]() =none and modifier(id,)=var => [outer_(bindq(id, assign, v, (outer)), local)]() T =>  } T => [id_(v, m)]() bindq(id.n, m, v, ) = [id_bindq(n, m, v, (id))]() modifier(id, nullEnv)=none modifier(id, ) = if =none then modifier(id, (outer)) else  apply(op, n, v, ) = op=QUOTE => v op=PLUS => E(n, )+E(v, ) . . . How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in . However, the value of a bindq(id, assign, v) in an environment  will change  by rebinding id in the "innermost" environment (following the chain of outer's) in which it is bound, provided that binding has the modifier var. When an id is referred to and =none, then the value is sought recursively in (outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #atom on a node gives that node membership in the set named by atom. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: Note that we should really be using this syntax above, both to define the syntax of expressions, and in the left-hand side of the semantic equations. The low-level syntax for InterDocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] content* ")" label ::= "#" id content ::= literal | name | node | envTrans literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id envTrans ::= singleTrans | compoundTrans singleTrans ::= name ( "=" | ":" | ":=" | "_" ) rhs rhs ::= [ op ] content | ["."] compoundTrans compoundTrans ::= "{" singleTrans* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . Notes: node: the effect of content* is obtained using compose content: if a literal, it becomes part of the fringe and has no effect Missing or in question: literal sequences when explaining semantics of labels, the set of nodes you get are those in the dominant structure, not any nodes salted away in the environment that happen to have labels. *start* 04728 00024 USm Date: 17 July 1981 10:38 am PDT (Friday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 3 To: Interdoc [The following is incomplete, and not internally consistent. We broadcast it in its present state to indicate the style and magnitude of the definition we are proposing. Please do not take the fine details overly seriously.] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). A separate function is used to compute the "value" of a node. Basic InterDoc Semantics The kinds of values that can be represented in an InterDoc script are primitiveValue: NIL Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anAtom, #Paragraph the empty environment: nullEnv mode: {VAR, LOCAL, CONST, ASSIGN, NONE} and sequences of primitiveValues; environment: id > value, mode function: environment > value node: labels, function The "abstract syntax" of scripts involves the following constructors: -- by convention n: name, v: value, m: mode, e: expression literal name -- id ( '. id)* compose(e1, e2) invoke(n) cond(e1, e2, e3) -- if e1 then e2 else e3 bind(n, m, op, v) -- ( op in {', +, , *, /, and, or, ... }) node(labels, function) The semantics of these expressions are defined by the following evaluation rules (E for evaluate, V for value,  denotes an environment; (id) is the value bound to id in ;  is the LOCAL mode of id in ; [id_(v, m)]() means " with id bound to (v, m)"): E(n, ) =  E(literal, ) =  E(compose(e1, e2), ) = E(e2, E(e1, )) E(invoke(n), ) = E(V(n, ), ) E(cond(e1, e2, e3), ) = if V(e1, )=T then E(e2, ) else E(e3, ) E(bind(n, m, op, v), ) = bindq(n, m, apply(op, n, v, ), ) E(node(l, f), ) = E(outer, E(f, [outer_(, LOCAL)](nullEnv))) V(id, nullEnv) = id V(id, ) = if =NONE then V(id, (outer)) else (id) V(id.n, ) = V(n, (id)) V(literal, ) = primitiveValue(literal) V(invoke(n), ) = V(V(n, ), ) V(cond(e1, e2, e3), ) = if V(e1, )=T then V(e2, ) else V(e3, ) V(node(l, f), ) = node(l, evalNode(f, )) evalNode(f, ) = to be defined bindq(id, m, v, ) = mode(id, )=CONST =>  m=ASSIGN => { =VAR => [id_(v, VAR)]() =NONE and mode(id,)=VAR => bindq(outer.id, ASSIGN, v, ) T =>  } T => [id_(v, m)]() bindq(id.n, m, v, ) = [id_(bindq(n, m, v, (id)), LOCAL)]() mode(id, nullEnv)=NONE mode(id, ) = if =NONE then mode(id, (outer)) else  apply(op, n, v, ) = op=BLANK => V(v, ) op=QUOTE => v op=PLUS => V(n, )+V(v, ) . . . How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in . However, the value of a bindq(id, ASSIGN, v, ) will change  by reBinding id in the "innermost" environment (following the chain of outers) in which it is bound, provided that binding has the mode VAR. When an id is referred to and =NONE, then the value is sought recursively in (outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for InterDocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] content* ")" label ::= "#" id content ::= literal | name | node | binding literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] content | ["."] compoundBinding compoundBinding ::= "{" singleBinding* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . Missing or in question: literal sequences *start* 05044 00024 USm Subject: Current Level 0/1 Interdoc status/rev. 4 To: Interdoc [Incorporating corrections to the local errors noted during the meeting this afternoon.] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). A separate function is used to compute the "value" of a node. Basic Interdoc Semantics The kinds of values that can be represented in an InterDoc script are primitiveValue: NIL Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anAtom, #Paragraph the empty environment: nullEnv mode: {VAR, LOCAL, CONST, ASSIGN, NONE} and sequences of primitiveValues; environment: id > value, mode expressions -- (unevaluated) syntax given below The "abstract syntax" of scripts involves the following constructors: -- by convention n: name, v: value, m: mode, e: expression literal name -- id ( '. id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 bind(n, m, op, v) -- ( op in {', +, , *, /, and, or, ... }) node(labels, function) The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function, V denotes the value function, C denotes an environment, generally the "current" one, C(id) denotes the value bound to id in C, C denotes the mode bound to id in C (NONE, if id isn't bound in C), (C | id_v, m) means "C with (v, m) bound to id". E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment apply: op, mode, value, environment > value insert: value, list > list modeOf: id, environment > mode E[literal](C) = C E[n](C) = E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C E[e1 e*](C) = E[e*](E[e1](C)) E[cond(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[bind(n, m, o, v)](C) = bindq(n, m, apply(o, n, v, C), C) E[node(l, f)](C) = V[outer](E[f](nullEnv | outer_C, LOCAL)) Compound binding, with & without "." V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if C=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(e)](C) = e V[] = NIL V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) V[cond(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[bind(n, m, o, v)](C) = NIL V[node(l, e)](C) = node(l, V[e](C)) Compound binding, with & without "." bindq(id, m, v, C) = modeOf(id, C)=CONST => C m=ASSIGN => { C=VAR => (C | id_v, VAR) C=NONE and modeOf(id,C)=VAR => bindq(outer.id, ASSIGN, v, C) T => C } T => (C | id_v, m) bindq(id.n, m, v, C) = (C | id_bindq(n, m, v, C(id)), LOCAL) modeOf(id, nullEnv)=NONE modeOf(id, C) = if C=NONE then modeOf(id, C(outer)) else C apply(o, n, v, C) = o=BLANK => V[v](C) o=QUOTE => v o=PLUS => V[n](C)+V[v](C) . . . /* insert(NIL, l) = l */ How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, v, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and C=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for InterDocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] content* ")" label ::= "#" id content ::= literal | ["'"] name | node | binding literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] content | ["."] compoundBinding compoundBinding ::= "{" content* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . Missing or in question: literal sequences syntax for conditionals *start* 05942 00024 USm Date: 17 July 1981 6:41 pm PDT (Friday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 5 To: Interdoc [Incorporating corrections to the local errors noted during the meeting this afternoon, plus a treatment of environment-valued expressions (see the new cases in apply, E[inner], etc.).] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). A separate function is used to compute the "value" of a node. Basic Interdoc Semantics The kinds of values that can be represented in an Interdoc script are primitiveValue: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments, which map ids to values and modes expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression v: value, literal name -- id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, _, := } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization _ denotes assignment to a previously declared variable := denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C C denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_v, m) means "C with (v, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C E[e1 e*](C) = E[e*](E[e1](C)) E[cond(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, f)](C) = V[outer](E[f](nullEnv | outer_C, LOCAL)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{inner}](C) = (inner | outer_C, LOCAL) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if C=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(e)](C) = e V[] = NIL V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) V[cond(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](C)) V[bind(n, m, op, v)](C) = NIL V[{inner}](C) = V[inner](C) ? bindq(id, m, v, C) = modeOf(id, C)=CONST => C m=ASSIGN => { C=VAR => (C | id_v, VAR) modeOf(id, C)=VAR => bindq(outer.id, ASSIGN, v, C) T => C } T => (C | id_v, m) bindq(id.n, m, v, C) = (C | id_bindq(n, m, v, C(id)), LOCAL) modeOf(id, nullEnv)=NONE modeOf(id, C) = if C=NONE then modeOf(id, C(outer)) else C apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) op=BRACES => (E[e](nullEnv | outer_C, LOCAL) | outer_nullEnv, LOCAL) op=DOTBRACES => (E[e](V[n](C) | outer_C, LOCAL) | outer_nullEnv, LOCAL) . . . -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, v, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and C=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some contents, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] content* ")" label ::= "#" id content ::= literal | ["'"] name | node | binding literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] content | ["."] compoundBinding compoundBinding ::= "{" content* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . Missing or in question: literal sequences syntax for conditionals *start* 08566 00024 USm Date: 21 July 1981 4:39 pm PDT (Tuesday) From: Mitchell.PA Subject: A Laurel document rendered in syntax of Interdoc 0/1 rev. 6 To: Interdoc Here follow two renderings of a sample Laurel message as an Interdoc script using rev. 6 of the syntax, which is appended to this message. Each assumes some external definitions (e.g., font, margins), which are not specified here. The examples are intended to illustrate different ways of using the language; we have not decided which we prefer. Your comments would be appreciated. (#Rendering1: TextDoc -- has style "TextDoc" justified_F -- "_" means overridable default font_.{family=TimesRoman size=10 face_normal} margins_.{left_2540 right_19050} leading_.{x_1 y_1} -- overridable default leadings LaurelInfo= -- Laurel information for easy access; none is changeable { pieces={hdr=#Heading body=#Body}-- internal references to labelled nodes time=<18 June 1981 9:18 am PDT (Thursday)> from= subject= to= cc= authenticated=T } (#Heading: -- "#Heading" is the label of this node Paragraph -- it's a paragraph LaurelInfo.time -- place the value of LaurelInfo.time here LaurelInfo.from LaurelInfo.subject LaurelInfo.cc ) (#Body: leading.y_6 -- override outer y leading (Paragraph ) -- node which is a paragraph (Paragraph ) (Paragraph ) ) ) --------------------------- The "fields" of MsgInfo could be handled using labels, making repetitions OK, and the external environment might well contain a definition of LaurelStyle LaurelStyle= '{ TextDoc P_Paragraph justified_F font_.{family=TimesRoman size=10 face_normal} margins_.{left_2540 right_19050} leading_.{x_1 y_1} PrintForm= '( P #time #from #subject #to leading.y_6 #Body #cc ) } Now the Laurel document would be described by the following script: (#Rendering2: LaurelStyle (#Heading: (#time:<18 June 1981 9:18 am PDT (Thursday)>) (#from: authenticated=T ) (#subject:) (#to:) (#cc:) ) (#Body: (P ) (P ) (P ) ) ) --------------------------- Current Level 0/1 Interdoc status/rev. 6 [Incorporating corrections to the local errors noted during the meeting this afternoon, plus a treatment of environment-valued expressions (see the new cases in apply, E[inner], etc.).] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). A separate function is used to compute the "value" of a node. Basic Interdoc Semantics The kinds of values that can be represented in an Interdoc script are primitiveValue: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments, which map ids to values and modes expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression v: value, literal name -- id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, :=, _ } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization := denotes assignment to a previously declared variable _ denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C C denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_v, m) means "C with (v, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C E[e1 e*](C) = E[e*](E[e1](C)) E[cond(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, f)](C) = V[outer](E[f](nullEnv | outer_C, LOCAL)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{inner}](C) = (inner | outer_C, LOCAL) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if C=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(e)](C) = e V[] = NIL V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) V[cond(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](C)) V[bind(n, m, op, v)](C) = NIL V[{inner}](C) = V[inner](C) bindq(id, m, v, C) = modeOf(id, C)=CONST => C m=ASSIGN => { C=VAR => (C | id_v, VAR) modeOf(id, C)=VAR => bindq(outer.id, ASSIGN, v, C) T => C } T => (C | id_v, m) bindq(id.n, m, v, C) = (C | id_bindq(n, m, v, C(id)), LOCAL) modeOf(id, nullEnv)=NONE modeOf(id, C) = if C=NONE then modeOf(id, C(outer)) else C apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) op=BRACES => (E[e](nullEnv | outer_C, LOCAL) | outer_nullEnv, LOCAL) op=DOTBRACES => (E[e](V[n](C) | outer_C, LOCAL) | outer_nullEnv, LOCAL) . . . -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, v, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and C=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some expression, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] expression* ")" label ::= "#" id expression ::= literal | ["'"] name | node | binding | conditional literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] expression | ["."] compoundBinding compoundBinding ::= "{" expression* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . conditional ::= "IF(" expression "," expression [ "," expression ] ")" Missing or in question: literal sequences relational operators Jim H. and Jim M. *start* 04250 00024 USm Date: 22 July 1981 5:10 pm PDT (Wednesday) From: Mitchell.PA Subject: A Star document rendered in Interdoc/rev. 6. To: Horning cc: Mitchell This example is taken from page 130 of the Star Functional Specification and shows a page of a paginated document with a diagram and a footnote (I recommend that you have that page in front of you when analyzing this rendition): Interdoc/Interchange/6.0 -- we probably should have some sort of header (#p7: newPage (Paragraph -- => justified_F (footRef=#fn1 fn1ref_(FootnoteRef 1) fn1ref) -- FootnoteRef style for the contents, "1" < which has shown our techniques to be valid. Other data can be collected by future changes to your accounting and billing packages, which will allow us to perform even better analyses and lead to better problem discovery and correction.> ) (Paragraph ) (#Frame1: Frame frameProps_.{ -- defaults set by invoking Frame horizontal_flushLeft vertical_floating size_{height_7100 width_9300} edges.expandingRightEdge_T border_dots1} (#r1: Rectangle upperleft_{x_2540 y_700} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1000 width_2700} lineType_solid2 shading_7} (Title ) ) --? perhaps rectProps shouldn't be a contained environment (#r2: Rectangle upperleft_{x_7300 y_1500} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1000 width_1800} lineType_solid2 shading_7} (Title ) ) (#r3: Rectangle upperleft_{x_200 y_3000} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1300 width_2500} lineType_solid2 shading_7} (Title ) ) (#r4: Rectangle upperleft_{x_200 y_3000} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1300 width_2800} lineType_solid2 shading_7} (Title ) ) (#r5: Rectangle upperleft_{x_4200 y_5500} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1300 width_1600} lineType_solid2 shading_7} (Title ) ) (#r6: Rectangle upperleft_{x_6700 y_5500} rectProps_.{ -- defaults set by invoking Rectangle size_{height_1300 width_1600} lineType_solid2 shading_7} (Title ) ) (#l1out: Line lineProps_.{lineType_solid2 from_#r1 to_#l24in}) (#l2out: Line lineProps_.{lineType_solid2 from_#r2 to_#l1out}) (#l3in: Line lineProps_.{lineType_solid2 from_#l-34in to_#r3}) (#l-4in: Line lineProps_.{lineType_solid2 from_#l-34in to_#r4}) (#l-34in: Line lineProps_.{lineType_solid2 from_#l3in to_#l4in}) (#l4out: Line lineProps_.{lineType_solid2 from_#r4 to_#l56in}) (#l56in: Line lineProps_.{lineType_solid2 from_#l5in to_#l6in}) (#l5in: Line lineProps_.{lineType_solid2 from_#l56in to_#r5}) (#l6in: Line lineProps_.{lineType_solid2 from_#l56in to_#6}) ) -- end of #Frame1 (Paragraph ) (Paragraph ) (#fn1: Footnote fn1ref -- place the node with the superscripted 1 here ) ) -- end of page *start* 06264 00024 USm Date: 24 July 1981 4:03 pm PDT (Friday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 7 To: Donahue cc: Mitchell, Horning [Jim D., We'd like you to put on your formal semanticist hat and constructively criticize both the form and the content of the following. Jim H. & Jim M.] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, evaluating environment transformation functions as soon as parsed (so that the environment of each piece of content is available during parsing). A separate function is used to compute the "value" of a node. Basic Interdoc The kinds of values that can be appear in an Interdoc script are literals: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments, which map ids to values and modes expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression literal name: id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, :=, _ } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization := denotes assignment to a previously declared variable _ denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C localMode(id, C) denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_e, m) means "C with (e, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = if modeOf(n, C)=NONE then C else E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C -- Basis E[e1 e*](C) = E[e*](E[e1](C)) -- Composition E[cond(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, e)](C) = V[outer](E[e](nullEnv | outer_C, LOCAL)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{e}](C) = E[e](C) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if localMode(id, C)=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(e)](C) = e V[] = NIL -- Basis V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) -- Composition V[cond(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](nullEnv | outer_C, LOCAL)) V[bind(n, m, op, e)](C) = NIL V[{e}](C) = V[e](C) bindq(id, m, e, C) = modeOf(id, C)=CONST => C m=ASSIGN => { localMode(id, C)=VAR => (C | id_e, VAR) modeOf(id, C)=VAR => bindq(outer.id, m, e, C) T => C } T => (C | id_e, m) bindq(id.n, m, e, C) = (C | id_bindq(n, m, e, V[id](C)), modeOf(id, C)) modeOf(n, nullEnv)=NONE modeOf(id, C) = if localMode(id, C)=NONE then modeOf(id, C(outer)) else localMode(id, C) modeOf(id.n, C) = if localMode(id, C)=NONE then modeOf(id.n, C(outer)) else modeOf(n, V[id](C)) apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) . . . op=BRACES => (E[e](nullEnv | outer_C, LOCAL) | outer_nullEnv, LOCAL) op=DOTBRACES => (E[e](V[n](C) | outer_C, LOCAL) | outer_nullEnv, LOCAL) -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment, C, initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, e, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and localMode(id, C)=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some expression, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] expression* ")" label ::= "#" id expression ::= literal | ["'"] name | node | binding | conditional literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] expression | ["."] compoundBinding compoundBinding ::= "{" expression* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . conditional ::= "IF(" expression "," expression [ "," expression ] ")" Missing or in question: literal sequences relational operators *start* 07854 00024 USm Date: 28 July 1981 12:32 pm PDT (Tuesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 8 To: Mitchell, Donahue cc: Horning [Primarily, have a look at SECOND TRY.] We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. Basic Interdoc Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments unevaluated expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression literal name: id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, :=, _ } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization := denotes assignment to a previously declared variable _ denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n  [FIRST TRY] The semantics of scripts are defined by the following equations, where MEnv denotes the "meaning" of an environment MExp denotes the meaning" of an expression C denotes an environment, generally the "current" one MEnv: Environment > ( Expression > Expression ) MExp: Expression > ( Environment > Environment ) lookup: Name, Environment > Expression MEnv(C)[literal] = literal MEnv(C)[n] = lookup(n, C) MEnv(C)[quote(e)] = e MEnv(C)[] = NIL -- Basis MEnv(C)[e1 e*] = insert(MEnv(C)[e1], MEnv[e*](MExp[e1](C))) -- Composition HALT-- THIS DOESN'T LOOK LIKE AN IMPROVEMENT   [SECOND TRY] TYPE Environment OPERATORS null: > Environment bindq: Id, Mode, Expression, Environment > Environment enter: Environment > Environment exit: Environment > Environment lookup: Id, Environment > Expression bindable: Id, Mode, Environment > Boolean persistent: Id, Environment > Boolean AXIOMS lookup(id, null) == id lookup(id, bindq(id', m, e, C)) == if id = id' and bindable(id', m, C) then e else lookup(id, C) lookup(id, enter(C)) == lookup(id, C) exit(null) == null -- or "undefined"? exit(bindq(id, m, e, C)) == if m = ASSIGN and persistent(id, C) then bindq(id, m, e, exit(C)) else exit(C) exit(enter(C)) == C bindable(id, m, null) == TRUE bindable(id, m, bindq(id', m', e, C)) == if id = id' then (m' ~= CONST) and (m = ASSIGN => m' = VAR) and bindable(id, CONST, C) else bindable(id, m, C) bindable(id, m, enter(C)) == bindable(id, m, C) persistent(id, null) == FALSE persistent(id, bindq(id', m', e, C)) == persistent(id, C) and (id = id' => m' = ASSIGN) persistent(id, enter(C)) == bindable(id, ASSIGN, C)  The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C localMode(id, C) denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_e, m) means "C with (e, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = if modeOf(n, C)=NONE then C else E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C -- Basis E[e1 e*](C) = E[e*](E[e1](C)) -- Composition E[cond(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, e)](C) = V[outer](E[e](nullEnv | outer_C, LOCAL)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{e}](C) = E[e](C) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if localMode(id, C)=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(e)](C) = e V[] = NIL -- Basis V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) -- Composition V[cond(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](nullEnv | outer_C, LOCAL)) V[bind(n, m, op, e)](C) = NIL V[{e}](C) = V[e](C) bindq(id, m, e, C) = modeOf(id, C)=CONST => C m=ASSIGN => { localMode(id, C)=VAR => (C | id_e, VAR) modeOf(id, C)=VAR => bindq(outer.id, m, e, C) T => C } T => (C | id_e, m) bindq(id.n, m, e, C) = (C | id_bindq(n, m, e, V[id](C)), modeOf(id, C)) modeOf(n, nullEnv)=NONE modeOf(id, C) = if localMode(id, C)=NONE then modeOf(id, C(outer)) else localMode(id, C) modeOf(id.n, C) = if localMode(id, C)=NONE then modeOf(id.n, C(outer)) else modeOf(n, V[id](C)) apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) . . . op=BRACES => (E[e](nullEnv | outer_C, LOCAL) | outer_nullEnv, LOCAL) op=DOTBRACES => (E[e](V[n](C) | outer_C, LOCAL) | outer_nullEnv, LOCAL) -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment, C, initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, e, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and localMode(id, C)=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some expression, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] expression* ")" label ::= "#" id expression ::= literal | ["'"] name | node | binding | conditional literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= singleBinding | compoundBinding singleBinding ::= name mode rhs mode ::= "=" | ":" | ":=" | "_" rhs ::= [ op ] expression | ["."] compoundBinding compoundBinding ::= "{" expression* "}" op ::= "'" | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . conditional ::= "IF(" expression "," expression [ "," expression ] ")" Missing or in question: literal sequences relational operators *start* 06076 00024 USm Date: 28 July 1981 3:45 pm PDT (Tuesday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 9 To: Mitchell, Horning We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. Basic Interdoc Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments unevaluated expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression literal name: id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, :=, _ } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization := denotes assignment to a previously declared variable _ denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C localMode(id, C) denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_e, m) means "C with (e, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = if modeOf(n, C)=NONE then C else E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C -- Basis E[e1 e*](C) = E[e*](E[e1](C)) -- Composition E[IF(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, e)](C) = V[outer](E[e](nullEnv | outer_C, CONST)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{e}](C) = E[e](C) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if localMode(id, C)=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(n)](C) = n V[] = NIL -- Basis V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) -- Composition V[IF(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](nullEnv | outer_C, CONST)) V[bind(n, m, op, e)](C) = NIL V[{e}](C) = V[e](C) bindq(id, m, e, C) = modeOf(id, C)=CONST => C m=ASSIGN => assign(id, e, C) T => (C | id_e, m) bindq(id.n, m, e, C) = (C | id_bindq(n, m, e, V[id](C)), modeOf(id, C)) modeOf(n, nullEnv)=NONE modeOf(id, C) = if localMode(id, C)=NONE then modeOf(id, C(outer)) else localMode(id, C) modeOf(id.n, C) = if localMode(id, C)=NONE then modeOf(id.n, C(outer)) else modeOf(n, V[id](C)) assign(id, e, C) = localMode(id, C)=VAR => (C | id_e, VAR) modeOf(id, C)=VAR => bindq(outer.id, ASSIGN, e, C) T => C apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) . . . op=BRACES => (E[e](nullEnv | outer_C, CONST) | outer_nullEnv, CONST) op=DOTBRACES => (E[e](V[n](C) | outer_C, CONST) | outer_nullEnv, CONST) -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment, C, initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, e, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and localMode(id, C)=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some expression, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] expression* ")" label ::= "#" id expression ::= literal | name | "'" name | conditional | node | binding | "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= name mode [ op ] expression mode ::= "=" | ":" | ":=" | "_" op ::= "'" | "." | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . conditional ::= "IF(" expression "," expression [ "," expression ] ")" Missing or in question: literal sequences binary & relational operators quote expressions in general *start* 08976 00024 USm Date: 28 July 1981 7:49 pm PDT (Tuesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 10 To: Mitchell, Horning cc: Donahue  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "(" labels expression* ")" labels ::= [label* ":"] label ::= "#" id expression ::= literal | name | "'" expression | conditional | binding | node | "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression [ "," expression ] ")" binding ::= name mode op expression mode ::= "=" | ":" | ":=" | "_" op ::= | "." | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . SEMANTIC EQUATIONS R denotes the expression reduction function T denotes the environment transformation function E denotes an environment, generally the "current" one E(id) denotes the value bound to id in E localMode(id, E) denotes the mode bound to id in E (None, if id isn't bound in E) [E | id_e, m] means "E with (e, m) bound to id" R: expression > ( environment > expression ) T: expression > ( environment > environment ) R<> = <> -- Basis R(E) = (E) R(T(E))> -- Composition R(E) = R(NullEnv) = R(E) = if localMode(id, E)=None then (E(Outer))> else R(E) = (R(E))> R<"'" e>(E) = R<"IF(" e1 "," e2 "," e3 ")">(E) = if R(E) then (T(E))> else (T(E))> R(E) = <> R<"(" labels e* ")">(E) = <"(" labels R([NullEnv | Outer_E, Const]) ")"> R<"{" e "}">(E) = (E)> T<>(E) = E -- Basis T(E) = T(T(E)) -- Composition T(E) = E T(E) = if modeOf(n, E)=None then E else T(E)>(E) T<"'" e>(E) = E T<"IF(" e1 "," e2 "," e3 ")">(E) = if R(E) then T(T(E)) else T(T(E)) T(E) = bindq(n, m, apply(op, n, e, E), E) T<"(" labels e* ")">(E) = R(T([NullEnv | Outer_E, Const])) T<"{" e "}">(E) = T(E) modeOf(n, NullEnv) = None modeOf(id, E) = if localMode(id, E)=None then modeOf(id, E(Outer)) else localMode(id, E) modeOf(id.n, E) = modeOf(n, R(E)) bindq(id, m, e, E) = modeOf(id, E)=Const => E m=Assign => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), modeOf(id, E)] assign(id, e, E) = localMode(id, E)=Var => [E | id_e, Var] modeOf(id, E)=Var => bindq(Outer.id, Assign, e, E) True => E apply(op, n, e, E) = op=BLANK => R(E) op=QUOTE => e op=PLUS => R(E)+R(E) . . . op=BRACES => [T[NullEnv | Outer_E, Const] | Outer_NullEnv, Const] op=DOTBRACES => [T[R(E) | Outer_E, Const] | Outer_NullEnv, Const] Missing or in question: literal sequences binary & relational operators e.id? ------------------- Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments unevaluated expressions The "abstract syntax" of expressions involves the following constructors: -- by convention n: name, e: expression literal name: id ( "." id)* quote(e) compose(e1, e2) cond(e1, e2, e3) -- if e1 then e2 else e3 node(labels, e) bind(n, m, op, e) where m is in { =, :, :=, _ } (or CONST, VAR, ASSIGN, LOCAL, respectively) = denotes constant binding : denotes variable declaration and initialization := denotes assignment to a previously declared variable _ denotes a local binding (cannot be affected by subnodes) and op is in { , ', +, , *, /, AND, OR, , ., ... } (or BLANK, QUOTE, PLUS, MINUS, TIMES, DIVIDE, ... ) binds to the current value of e ' binds to the expression e +, , *, /, AND, OR, ... bind to the result of a binary operation between the current value of n and the current value of e bind to a nested environment containing only the bindings resulting from e . uses e to update the bindings in the environment bound to n The semantics of scripts are defined by the following evaluation rules, where E denotes the environment transformation function V denotes the value function C denotes an environment, generally the "current" one C(id) denotes the value bound to id in C localMode(id, C) denotes the mode bound to id in C (NONE, if id isn't bound in C) (C | id_e, m) means "C with (e, m) bound to id" E: expression > ( environment > environment ) V: expression > ( environment > value ) bindq: name, mode, value, environment > environment modeOf: id, environment > mode apply: op, mode, value, environment > value insert: value, list > list E[literal](C) = C E[n](C) = if modeOf(n, C)=NONE then C else E[V[n](C)](C) E[quote(n)](C) = C E[](C) = C -- Basis E[e1 e*](C) = E[e*](E[e1](C)) -- Composition E[IF(e1, e2, e3)](C) = if V[e1](C) then E[e2](E[e1](C)) else E[e3](E[e1](C)) E[node(l, e)](C) = V[outer](E[e](nullEnv | outer_C, CONST)) E[bind(n, m, op, e)](C) = bindq(n, m, apply(op, n, e, C), C) E[{e}](C) = E[e](C) V[literal](C) = literal V[id](nullEnv) = id V[id](C) = if localMode(id, C)=NONE then V[id](C(outer)) else C(id) V[id.n](C) = V[n](V[id](C)) V[quote(n)](C) = n V[] = NIL -- Basis V[e1 e*](C) = insert(V[e1](C), V[e*](E[e1](C))) -- Composition V[IF(e1, e2, e3)](C) = if V[e1](C) then V[e2](E[e1](C)) else V[e3](E[e1](C)) V[node(l, e)](C) = node(l, V[e](nullEnv | outer_C, CONST)) V[bind(n, m, op, e)](C) = NIL V[{e}](C) = V[e](C) bindq(id, m, e, C) = modeOf(id, C)=CONST => C m=ASSIGN => assign(id, e, C) T => (C | id_e, m) bindq(id.n, m, e, C) = (C | id_bindq(n, m, e, V[id](C)), modeOf(id, C)) modeOf(n, nullEnv)=NONE modeOf(id, C) = if localMode(id, C)=NONE then modeOf(id, C(outer)) else localMode(id, C) modeOf(id.n, C) = if localMode(id, C)=NONE then modeOf(id.n, C(outer)) else modeOf(n, V[id](C)) assign(id, e, C) = localMode(id, C)=VAR => (C | id_e, VAR) modeOf(id, C)=VAR => bindq(outer.id, ASSIGN, e, C) T => C apply(op, n, e, C) = op=BLANK => V[e](C) op=QUOTE => e op=PLUS => V[n](C)+V[e](C) . . . op=BRACES => (E[e](nullEnv | outer_C, CONST) | outer_nullEnv, CONST) op=DOTBRACES => (E[e](V[n](C) | outer_C, CONST) | outer_nullEnv, CONST) -- insert(NIL, l) = l How semantics are associated with an entire document: Each environment, C, initially contains only its "inherited" environment (bound to the id "outer"). Most bindings take place directly in C. However, the value of a bindq(id, ASSIGN, e, C) will change C by rebinding id in the "innermost" environment (following the chain of outers) in which it is bound, if that binding has the mode VAR. When an id is referred to and localMode(id, C)=NONE, then the value is sought recursively in C(outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Interdoc Syntax: The low-level syntax for Interdocs is the following (basically it represents the dominant tree structure by the nonterminal "node", each of which can have some set of labels, some expression, which may be actual data (the body of the document), transformations on the environment, or subtrees: node ::= "(" [label* ":"] expression* ")" label ::= "#" id expression ::= literal | name | "'" name | conditional | node | binding | "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id binding ::= name mode [ op ] expression mode ::= "=" | ":" | ":=" | "_" op ::= "'" | "." | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . conditional ::= "IF(" expression "," expression [ "," expression ] ")" ------------------- *start* 05746 00024 USm Date: 29 July 1981 7:46 pm PDT (Wednesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 11 To: Mitchell, Horning cc: Donahue [This is shorter, more general, and I hope cleaner than previous versions. Numerous small bugs have been fixed as I tracked down subtleties. I'd particularly like scrutiny of the equations involving nested environments, marked by interior s.]  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug (?) semantics of braces and dot.  Mode > binding. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "(" labels expression* ")" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" ] primary primary ::= literal | id | primary "." id | conditional | node | "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression [ "," expression ] ")" lhs ::= name binding op binding ::= "=" | ":" | ":=" | "_" op ::= | "." | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) bound(id, E) = (locBinding(id, E) ~= None) R<>(E) = "" -- Basis T<>(E) = E R(E) = R(E) R(T(E)) -- Composition T(E) = T(T(E)) R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = bound(id, E) => E(id) bound(Outer, E) => R(E(Outer)) True => id T(E) = if R(E)=id then E else T(E)>(E) R

(E) = R(R

(E)) T

(E) = T(E)>(E) R<"IF(" e1 "," e2 "," e3 ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2 "," e3 ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = "" T(E) = bindq(n, m, apply(op, n, p, E), E) R<"(" labels e* ")">(E) = "(" labels R([Null | Outer_E, Const]) ")" T<"(" labels e* ")">(E) = (T([Null | Outer_E, Const]))(Outer) R<"{" e* "}">(E) = [T<"{" e* "}">(E) | Outer_Null, Const] ? T<"{" e* "}">(E) = T([Null | Outer_E, Const]) ? bindingOf(id, E) = if ~bound(id, E) and bound(Outer, E) then bindingOf(id, E(Outer)) else locBinding(id, E) bindq(id, m, e, E) = bindingOf(id, E) = "=" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, n, p, E) = op = "" => R

(E) op = "." => R

([R(E) | Outer_E, Const]) ? op = "+" => R(E)+R

(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: id:  (the null id), bold, thisIsAnId, Helvetica, . . . label: #A123, #anId, #Paragraph the empty environment: nullEnv the empty list: NIL environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. *start* 06157 00024 USm Date: 30 July 1981 6:49 pm PDT (Thursday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 12 To: Mitchell, Horning cc: Donahue  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "(" labels expression* ")" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" ] primary primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name binding op binding ::= "=" | ":" | ":=" | "_" op ::= | "." | "+" | "-" | "*" | "/" | "AND" | "OR" | . . . SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value locally bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) -- Basis R<>(E) = "" -- Empty list T<>(E) = E -- Identity -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = if valOf(id, E)=id then id else R(E) T(E) = if valOf(id, E)=id then E else T(E) R

(E) = R(R

(E)) T

(E) = if valOf(id, R

(E))=id then E else T(E))>(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = "" -- Empty list T(E) = bindq(n, m, apply(op, n, p, E), E) R<"(" labels e* ")">(E) = "(" labels R([Null | Outer_E, Const]) ")" T<"(" labels e* ")">(E) = (T([Null | Outer_E, Const]))(Outer) R<"{" e* "}">(E) = [T<"{" e* "}">(E) | Outer_Null, Const] T<"{" e* "}">(E) = T([Null | Outer_E, Const]) R<"VAL{" e* "}">(E) = R(E) T<"VAL{" e* "}">(E) = E whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding(Outer, E) ~= None => whereBound(id, E(Outer)) True => Null valOf(id, E) = (whereBound(id, E))(id) -- Gets innermost value bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding bindq(id, m, e, E) = bindingOf(id, E) = "=" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, n, p, E) = op = "" => R

(E) op = "." => R

([R(E) | Outer_E, Const]) op = "+" => R(E)+R

(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. ------------------------------------------------------------ *start* 06841 00024 USm Date: 30 July 1981 9:55 pm PDT (Thursday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 13 To: Mitchell, Horning Last edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; required changing CONST binding op ("=") to "=="; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "(" labels expression* ")" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" ] disjunction disjunction ::= [ disjunction "OR" ] conjunction conjunction ::= [ conjunction "AND" ] negation negation ::= [ "NOT" ] relation relation ::= [ sum relOp ] sum relOp ::= "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" sum ::= [ sum addOp ] product addOp ::= "+" | "-" product ::= [ product multOp ] primary multOp ::= "*" | "/" | "MOD" primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "{" expression* "}" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF{" expression "," expression* [ "," expression* ] "}" lhs ::= name binding op binding ::= "==" | ":" | ":=" | "_" op ::= | "." | addOp | multOp a:='NOT VAL{leftMargin=120} r==12.5*pt IF{a=b, leftMargin_5, leftMargin_10} SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value locally bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) -- Basis R<>(E) = nothing -- just what it says T<>(E) = E -- Identity -- Expression sequence R(E) = R(E) -- "nothing" disappears R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = if valOf(id, E)=id then id else R(E) T(E) = if valOf(id, E)=id then E else T(E) R

(E) = R(R

(E)) T

(E) = if valOf(id, R

(E))=id then E else T(E))>(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = "" -- Empty list T(E) = bindq(n, m, apply(op, n, p, E), E) R<"(" labels e* ")">(E) = "(" labels R([Null | Outer_E, Const]) ")" T<"(" labels e* ")">(E) = (T([Null | Outer_E, Const]))(Outer) R<"{" e* "}">(E) = [T<"{" e* "}">(E) | Outer_Null, Const] T<"{" e* "}">(E) = T([Null | Outer_E, Const]) R<"VAL{" e* "}">(E) = R(E) T<"VAL{" e* "}">(E) = E whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding(Outer, E) ~= None => whereBound(id, E(Outer)) True => Null valOf(id, E) = (whereBound(id, E))(id) -- Gets innermost value bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding bindq(id, m, e, E) = bindingOf(id, E) = "==" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, lhs, rhs, E) = op = "" => R(E) op = "." => R([R(E) | Outer_E, Const]) op = "+" => R(E)+R(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: {F, T} integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "==" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. Log of Changes  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  *start* 00808 00024 USm Date: 31 July 1981 10:39 am PDT (Friday) From: Horning.pa Subject: Re: Current Level 0/1 Interdoc status/rev. 13 In-reply-to: Your message of 30 July 1981 9:55 pm PDT (Thursday) To: Mitchell cc: Horning Jim, Given the expected infrequency of Boolean expressions (or infix operators), I guess I'm not enamoured of adding that much syntax for precedence. Left-to-right plus explicit bracketing will be OK. I suggest instead expression ::= [ lhs ] [ "'" | "." | op ] primary primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "{" expression ( [ op ] expression )* "}" op ::= "+" | "" | "*" | "/" | "MOD" | "NOT" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" Note that since you use EQ, "=" is still available for Const binding. Jim H. *start* 04028 00024 USm Date: 23 July 1981 5:00 pm PDT (Thursday) From: Mitchell.PA Subject: A Star document rendered in Interdoc/rev. 6. To: Interdoc This example is taken from page 130 of the Star Functional Specification and shows one page of a paginated document with a diagram and a footnote (I recommend that you have that page in front of you when analyzing this rendition): . . . -- pages 1 .. 6 supposedly precede this one (#p7: newPage (Paragraph.justified_F -- redefine Paragraph with justification off fn1ref_(FootnoteRef footRef=#fn1 1) -- FootnoteRef node with contents, "1" fn1ref -- place the footnote ref < which has shown our techniques to be valid. Other data can be collected by future changes to your accounting and billing packages, which will allow us to perform even better analyses and lead to better problem discovery and correction.> ) (Paragraph ) (#Frame1: Frame -- defaults are set by invoking Frame horizontal_flushLeft vertical_floating size_{height_7100 width_9300} edges.expandingRightEdge_T border_dots1 (#r1: Rectangle -- defaults are set by invoking Rectangle upperleft_{x_2540 y_700} size_{height_1000 width_2700} lineType_solid2 shading_7 (Title ) ) (#r2: Rectangle upperleft_{x_7300 y_1500} size_{height_1000 width_1800} lineType_solid2 (Title ) ) (#r3: Rectangle upperleft_{x_200 y_3000} size_{height_1300 width_2500} lineType_solid2 (Title ) ) (#r4: Rectangle upperleft_{x_200 y_3000} size_{height_1300 width_2800} lineType_solid2 (Title ) ) (#r5: Rectangle upperleft_{x_4200 y_5500} size_{height_1300 width_1600} lineType_solid2 (Title ) ) (#r6: Rectangle upperleft_{x_6700 y_5500} size_{height_1300 width_1600} lineType_solid2 (Title ) ) (#l1out: Line lineType_solid2 in_#r1 out_#l24in) (#l2out: Line lineType_solid2 in_#r2 out_#l1out) (#l3in: Line lineType_solid2 in_#l-34in out_#r3) (#l-4in: Line lineType_solid2 in_#l-34in out_#r4) (#l-34in: Line lineType_solid2 in_#l3in out_#l4in) (#l4out: Line lineType_solid2 in_#r4 out_#l56in) (#l56in: Line lineType_solid2 in_#l5in out_#l6in) (#l5in: Line lineType_solid2 in_#l56in out_#r5) (#l6in: Line lineType_solid2 in_#l56in out_#6) ) -- end of #Frame1 (Paragraph ) (Paragraph ) (#fn1: Footnote fn1ref -- place the node with the superscripted 1 here ) ) -- end of page Here a few of the definitions of "styles" invoked in the above example (see page 148 of the Star spec for what they mean): Rectangle_{ constraint_UNCONSTRAINED upperleft_{x_0 y_0} size_{height_1000 width_2000} lineType_solid1 shading_0 } Line_{ constraint_UNCONSTRAINED lineType_solid1 arrowHead_{in_none out_none} } *start* 07079 00024 USm Date: 31 July 1981 4:28 pm PDT (Friday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 14 To: Mitchell, Horning Last edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | "." | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name binding binding ::= "=" | ":" | ":=" | "_" op ::= "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLES: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value locally bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) -- Basis R<>(E) = nothing -- just what it says T<>(E) = E -- Identity -- Expression sequence R(E) = R(E) -- "nothing" disappears R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = if valOf(id, E)=id then id else R(E) T(E) = if valOf(id, E)=id then E else T(E) R

(E) = R(R

(E)) T

(E) = if valOf(id, R

(E))=id then E else T(E))>(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = apply(op, p1, p2, E) T(E) = E R<"NOT" p>(E) = if R

(E)=True then False else True T<"NOT" p>(E) = E R(E) = nothing -- Empty list T(E) = bindq(n, m, apply(op, n, e, E), E) R<"(" labels e* ")">(E) = "(" labels R([Null | Outer_E, Const]) ")" T<"(" labels e* ")">(E) = (T([Null | Outer_E, Const]))(Outer) R<"(" e* ")">(E) = [T<"(" e* ")">(E) | Outer_Null, Const] T<"(" e* ")">(E) = T([Null | Outer_E, Const]) R<"VAL(" e* ")">(E) = R(E) T<"VAL(" e* ")">(E) = E whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding(Outer, E) ~= None => whereBound(id, E(Outer)) True => Null valOf(id, E) = (whereBound(id, E))(id) -- Gets innermost value bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding bindq(id, m, e, E) = bindingOf(id, E) = "=" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, lhs, rhs, E) = op = "" => R(E) op = "." => R([R(E) | Outer_E, Const]) op = "+" => R(E)+R(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Last edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. *start* 07201 00024 US Date: 7 Aug. 1981 4:41 pm PDT (Friday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 15 To: Mitchell, Horning Last edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | "." | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name binding binding ::= "=" | ":" | ":=" | "_" op ::= "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLES: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value locally bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) -- Basis R<>(E) = nothing -- just what it says T<>(E) = E -- Identity -- Expression sequence R(E) = R(E) -- "nothing" disappears R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = if valOf(id, E)=id then id else R(E) T(E) = if valOf(id, E)=id then E else T(E) R

(E) = R(R

(E)) T

(E) = if valOf(id, R

(E))=id then E else T(E))>(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = apply(op, p1, p2, E) T(E) = E R<"NOT" p>(E) = if R

(E)=True then False else True T<"NOT" p>(E) = E R(E) = nothing -- Empty list T(E) = bindq(n, m, apply(op, n, e, E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | Outer_E, Const]) "}" T<"{" labels e* "}">(E) = (T([Null | Outer_E, Const]))(Outer) R<"(" e* ")">(E) = [T<"(" e* ")">(E) | Outer_Null, Const] T<"(" e* ")">(E) = T([Null | Outer_E, Const]) R<"VAL(" e* ")">(E) = R(E) T<"VAL(" e* ")">(E) = E whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding(Outer, E) ~= None => whereBound(id, E(Outer)) True => Null valOf(id, E) = (whereBound(id, E))(id) -- Gets innermost value bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding bindq(id, m, e, E) = bindingOf(id, E) = "=" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, lhs, rhs, E) = op = "" => R(E) op = "." => R([R(E) | Outer_E, Const]) op = "+" => R(E)+R(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Last edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Last edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. *start* 07956 00024 US Date: 13 Aug. 1981 5:36 pm PDT (Thursday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 16 To: Mitchell, Horning [Jim, I did a fair amount of doodling, primarily in an attempt to transform the semantic equations to a form where their correctness will be "more nearly obvious." Some of the changes I like, but I'm not really wedded to any of them.] Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- In question: treatment of primitive identifiers side effects in expressions operations on nested environments: font_.(size_10) Missing: literal sequences ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode bindingMode ::= "=" | ":" | ":=" | "_" op ::= "." | "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLE: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E, if locBinding(id, E) ~= None locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) N. B. T(E) = E , if no explicit value is given below. -- Basis R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => bind("Outer".id, ":=", e, E) True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. *start* 00301 00024 USm From: dawson.pa Date: 14-Aug-81 15:23:11 PDT Subject: DocumentInterchange^.pa To: Horning cc: Dawson I would like to add my name to this DL but can't using Maintain. Maintain says it doesn't exist. Is there a funny character in the name, or has it gone away, or what? John *start* 07201 00024 USm Date: 7 Aug. 1981 4:41 pm PDT (Friday) From: Mitchell.PA Subject: Current Level 0/1 Interdoc status/rev. 15 To: Mitchell, Horning Last edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | "." | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "VAL" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name binding binding ::= "=" | ":" | ":=" | "_" op ::= "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLES: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind expressions and "modes" to identifiers: Null denotes the "empty" environment [E | id_e, m] means "E with (e, m) bound to id" E(id) denotes the value locally bound to id in E Null(id) = id [E | id'_e, m](id) = if id=id' then e else E(id) locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id'_e, m]) = if id=id' then m else locBinding(id, E) -- Basis R<>(E) = nothing -- just what it says T<>(E) = E -- Identity -- Expression sequence R(E) = R(E) -- "nothing" disappears R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R<"'" p>(E) = p T<"'" p>(E) = E R(E) = literal T(E) = E R(E) = if valOf(id, E)=id then id else R(E) T(E) = if valOf(id, E)=id then E else T(E) R

(E) = R(R

(E)) T

(E) = if valOf(id, R

(E))=id then E else T(E))>(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R(E) = apply(op, p1, p2, E) T(E) = E R<"NOT" p>(E) = if R

(E)=True then False else True T<"NOT" p>(E) = E R(E) = nothing -- Empty list T(E) = bindq(n, m, apply(op, n, e, E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | Outer_E, Const]) "}" T<"{" labels e* "}">(E) = (T([Null | Outer_E, Const]))(Outer) R<"(" e* ")">(E) = [T<"(" e* ")">(E) | Outer_Null, Const] T<"(" e* ")">(E) = T([Null | Outer_E, Const]) R<"VAL(" e* ")">(E) = R(E) T<"VAL(" e* ")">(E) = E whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding(Outer, E) ~= None => whereBound(id, E(Outer)) True => Null valOf(id, E) = (whereBound(id, E))(id) -- Gets innermost value bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding bindq(id, m, e, E) = bindingOf(id, E) = "=" => E m = ":=" => assign(id, e, E) True => [E | id_e, m] bindq(id.n, m, e, E) = [E | id_bindq(n, m, e, R(E)), bindingOf(id, E)] assign(id, e, E) = locBinding(id, E) = ":" => [E | id_e, ":"] bindingOf(id, E) = ":" => bindq(Outer.id, ":=", e, E) True => E apply(op, lhs, rhs, E) = op = "" => R(E) op = "." => R([R(E) | Outer_E, Const]) op = "+" => R(E)+R(E) . . . Missing or in question: literal sequences binary & relational operators ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bindq(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in E(Outer). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Last edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Last edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. *start* 07956 00024 USm Date: 13 Aug. 1981 5:36 pm PDT (Thursday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 16 To: Mitchell, Horning [Jim, I did a fair amount of doodling, primarily in an attempt to transform the semantic equations to a form where their correctness will be "more nearly obvious." Some of the changes I like, but I'm not really wedded to any of them.] Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- In question: treatment of primitive identifiers side effects in expressions operations on nested environments: font_.(size_10) Missing: literal sequences ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode bindingMode ::= "=" | ":" | ":=" | "_" op ::= "." | "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLE: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E, if locBinding(id, E) ~= None locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) N. B. T(E) = E , if no explicit value is given below. -- Basis R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => bind("Outer".id, ":=", e, E) True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Braces create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if preceded by VAL, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. *start* 08870 00024 USm Date: 17 Aug. 1981 11:40 am PDT (Monday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 17 To: Mitchell, Horning [Jim, For discussion this afternoon. Jim H.] Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" ------------------- In question: treatment of primitive identifiers (vs. labels) side effects in expressions (why only in conditionals?) operations on nested environments: font_.(size_10) merging environments reduced transformations Missing: literal sequences operations on sequences (subscripting) ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" labels expression* "}" labels ::= [label* ":"] label ::= "#" name expression ::= [ lhs ] [ "'" | op ] rhs rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode bindingMode ::= "=" | ":" | ":=" | "_" op ::= "." | "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLE: {#examplenode: a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Null locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = literal; E R&T(E) = if bindingOf(id, E)=None then id; E else R&T(E) R&T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R&T(T(E)) else R&T(T(E)) R&T<"NOT" p>(E) = if R

(E) then False else True; E R&T(E) = op = "." => R([R(E) | "Outer" = E ?]); E op = "+" => R(E)+R(E); E . . . R&T(E) = ""; bind(n, m, R(E), E) R&T(E) = ""; bind(n, m, e, E) R&T(E) = ""; bind(n, m, R(E), E) R&T<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}"; locVal("Outer", (T([Null | "Outer" = E]))) R&T<"(" e* ")">(E) = R(E); E R&T<"ENV(" e* ")">(E) = [T(E) | "Outer" = Null]; T(E) ? bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => bind("Outer".id, ":=", e, E) True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: #A123, #anId, #Paragraph the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to Outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Parentheses create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; if not preceded by ENV, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- *start* 09077 00024 USm Date: 17 Aug. 1981 7:05 pm PDT (Monday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 18 To: Mitchell, Horning [Jim, Jim H.] Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes ------------------- In question: operations on nested environments: font_.(size_10) merging environments reduced transformations structured labels getEnv operator labels outside dominant structure non-printing nodes Missing: operations on sequences and environments (subscripting and enumeration) substitution of  for Null, Nil, etc. ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" expression* "}" expression ::= [ lhs ] [ "'" | op ] | name ":!" -- :! for label declaration rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" | label literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id label ::= name "!" conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode bindingMode ::= "=" | ":" | ":=" | "_" op ::= "." | "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLE: {node.example! a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Null locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = literal; E R&T(E) = if bindingOf(id, E)=None then id; E else R&T(E) R&T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"NOT" p>(E) = if R

(E) then False else True; E R&T(E) = op = "." => R([R(E) | "Outer" = E ?]); E op = "+" => R(E)+R(E); E . . . R&T(E) = ""; bind(n, m, R(E), E) R&T(E) = ""; bind(n, m, e, E) R&T(E) = ""; bind(n, m, R(E), E) R&T<"{" e* "}">(E) = "{" R([Null | "Outer" = E]) "}"; locVal("Outer", (T([Null | "Outer" = E]))) R&T<"(" e* ")">(E) = R&T(E) R&T<"ENV(" e* ")">(E) = [T(E) | "Outer" = Null]; T(E) ? bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => bind("Outer".id, ":=", e, E) True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: A123!, anId!, Paragraph! the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to Outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Parentheses create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; ? if not preceded by ENV, it is executed for value, and the environment is then discarded. Semantics of labels: A label #id on a node in the dominant structure gives that node membership in the set named by id. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" *start* 09690 00024 USm Date: 19 Aug. 1981 9:58 am PDT (Wednesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 19 To: Mitchell, Horning, Lampson Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) ------------------- In question: subscripting: sequences, yes; nodes, labels, sets, environments, no evaluation of subscript expressions merging environments labels outside dominant structure non-printing nodes generalize apply to non-literal operands (distribute over sequences?) IF, NOT, apply when arguments are not literals, partial evaluation bind op in environment? Missing: operations on sequences and environments (subscripting and enumeration) substitution of  for Null, Nil, etc. ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" expression* "}" expression ::= [ lhs ] [ "'" | op ] | name ":!" -- :! for label declaration rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" | label literal ::= Boolean | integer | hexint | real | string | label name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id label ::= name "!" conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode bindingMode ::= "=" | ":" | ":=" | "_" op ::= "%" | "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" SYNTACTIC EXAMPLE: {node.example! a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Null locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = literal; E R&T(E) = if bindingOf(id, E)=None then id; E else R&T(E) R&T

(E) = R&T(E))>(E) -- Subscript should go here R&T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"NOT" p>(E) = if R

(E) then False else True; E R&T(E) = p2; E R&T(E) = R([R(E) | "Outer" = E]); [T([R(E) | "Outer" = E]) | "Outer" = Null] R&T(E) = apply(R(E), op, R(E)); E R&T(E) = ""; bind(n, m, R(E), E) = -- Syntactic sugar R&T<"{" e* "}">(E) = "{" R([Null | "Outer" = E]) "}"; locVal("Outer", (T([Null | "Outer" = E]))) R&T<"(" e* ")">(E) = R&T(E) bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null apply(arg1, op, arg2) = op = "+" => arg1+arg2 . . . bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", e, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Boolean: (F, T) integer: ... -3, -2, -1, 0, 1, 2, 3, ... real: 1.2E5, . . . string: label: A123!, anId!, Paragraph! the empty environment: Null the empty list: NIL id:  (the null id), bold, thisIsAnId, Helvetica, . . . (unless bound, taken to denote a primitive) environments unevaluated expressions How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to Outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound to an environment transformation in the containing environment. Parentheses create a nested environment; if preceded by a dot, it is initialized to the value of the name in the binding; ? if not preceded by ENV, it is executed for value, and the environment is then discarded. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes *start* 10516 00024 USm Date: 19 Aug. 1981 6:56 pm PDT (Wednesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 20 To: Mitchell, Horning, Lampson Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. ------------------- In question: merging environments (OPEN) declaration of "main" labels labels outside dominant structure non-printing nodes (semicolon?) bind op names in environment? structured primitive names, naming authorities how to syntactically distinguish operator application infix vs. prefix for general operators (APL?) treatment of unbound qualified names  as id vs. binary op vs. sign on numbers Missing: enumeration over sequences and environments substitution of  for Null, Nil, etc., as appropriate ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR node ::= "{" expression* "}" expression ::= [ lhs ] rhs | name ":!" -- :! for label declaration rhs ::= [ "NOT" ] primary ( op primary )* primary ::= literal | id | primary "." id | conditional | node | [ "ENV" ] "(" expression* ")" literal ::= Boolean | integer | hexint | real | string | label | atom name ::= id ( "." id)* id ::= (letter | "" ) ( letter | "" | digit )* -- "" is the null id label ::= name "!" atom ::= "$" id conditional ::= "IF(" expression "," expression* [ "," expression* ] ")" lhs ::= name bindingMode [ "'" | op ] bindingMode ::= "=" | ":" | ":=" | "_" op ::= "+" | "" | "*" | "/" | "MOD" | "AND" | "OR" | "LT" | " LE" | "EQ" | "NE" | "GE" | "GT" | "SUB" SYNTACTIC EXAMPLE: {node.example! a:='NOT margins.left EQ 120 margins.left_100 r=12.5*pt IF(a, leftMargin_+5, leftMargin_+10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Null locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T(E) = literal; E R&T(E) = if bindingOf(id, E)=None then "$" id; E else R&T(E) R&T

(E) = R&T(E))>(E) R&T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"NOT" p>(E) = NOT R

(E); E R&T(E) = p2; E R&T(E) = apply(R(E), op, R(E)); E R&T(E) = ""; bind(n, m, R(E), E) = -- Syntactic sugar R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T<"(" e* ")">(E) = R&T(E) R&T<"ENV(" e* ")">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E R&T<"{" e* "}">(E) = "{" R([Null | "Outer" = E]) "}"; locVal("Outer", (T([Null | "Outer" = E]))) R&T(E) =  bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null apply(arg1, op, arg2) = op = "+" => arg1+arg2 . . . op = "SUB" => arg1[arg2] bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", e, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- id:  (the null id), bold, thisIsAnId, Helvetica, . . . Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! primitive properties and operators: $id the empty environment: Null the empty list: NIL unevaluated expressions environments sets (sequences) of nodes with given labels How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to Outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties. Parentheses are used purely for grouping (e.g., creating a sequence value for a binding). ENV is used to create a new environment, which behaves much like a record. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its properties. (Variant: all properties on the path back to the root.) STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) *start* 10548 00024 USm Subject: Current Level 0/1 Interdoc status/rev. 21 To: Mitchell, Horning, Lampson Edited by Jim H. on 20 Aug. 1981 1:27 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish between properties (marks) and labels. only the "main" id of a label is declared. eliminate  an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. ------------------- In question: labels outside dominant structure non-printing nodes (semicolon?) bind op names in environment? structured primitive names, naming authorities treatment of unbound qualified names ------------------- We envision an Interdoc script being processed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to "primitives" by evaluating constant subexpressions and replacing names by the values to which they are bound in the current environment, and - transforming the environment as indicated by the expressions. BASIC INTERDOC GRAMMAR item ::= expression | binding | id ":!" -- :! for label declaration expression ::= id | expression "." id | literal | application | property | node id ::= letter ( letter | digit )* literal ::= Boolean | integer | hexint | real | string | label | external label ::= name "!" name ::= id ( "." id)* external ::= "$" name application ::= ( op | expression ) "(" item* ( "," item* )* ")" op ::= "'" | "+" | "" | "*" | "/" property ::= expression "#" node ::= "{" item* "}" binding ::= name [ op ] bindingMode ( expression | "(" item* ")" ) bindingMode ::= "=" | ":" | ":=" | "_" SYNTACTIC EXAMPLE: {node.example! -- Places this in node and node.example ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a nonstandard property a:='(NOT(EQ(margins.left, 120))) margins.left_100 r=*(12.5,pt) IF(a, margins.left+_5 margins.right_5, margins.left+_10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Null locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T(E) = literal; E R&T(E) = if bindingOf(id, E)=None then "$" id; E else R&T(E) R&T

(E) = R&T(E))>(E) R&T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"NOT" p>(E) = NOT R

(E); E R&T(E) = p2; E R&T(E) = apply(R(E), op, R(E)); E R&T(E) = ""; bind(n, m, R(E), E) = -- Syntactic sugar R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T<"(" e* ")">(E) = R&T(E) R&T<"ENV(" e* ")">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E R&T<"{" e* "}">(E) = "{" R([Null | "Outer" = E]) "}"; locVal("Outer", (T([Null | "Outer" = E]))) R&T(E) =  bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null apply(arg1, op, arg2) = op = "+" => arg1+arg2 . . . op = "SUB" => arg1[arg2] bind(id, m, e, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, e, E) -- Assign at right level True => [E | id m e] bind(id.n, m, e, E) = [E | id bindingOf(id, E) bind(n, m, e, R(E))] assign(id, e, E) = locBinding(id, E) = ":" => [E | id ":" e] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", e, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- id:  (the null id), bold, thisIsAnId, Helvetica, . . . Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! primitive properties and operators: $id the empty environment: Null the empty list: NIL unevaluated expressions environments sets (sequences) of nodes with given labels How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", p, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). Perverse explicit bindings to Outer might create loops, leaving some ids undefined, but there seems to be little reason to clutter up the semantics by forbidding such assignments. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties. Parentheses are used purely for grouping (e.g., creating a sequence value for a binding). ENV is used to create a new environment, which behaves much like a record. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its properties. (Variant: all properties on the path back to the root.) STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. *start* 11578 00024 USm Date: 20 Aug. 1981 5:40 pm PDT (Thursday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 22 To: Mitchell, Horning, Lampson [Jim, I think I've fixed the syntax problems we discussed. However, we should discuss how palatable this syntax is--I made a number of relatively arbitrary decisions for the sake of getting something definite as soon as possible. Jim H.] Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). ------------------- Not done: State the formal semantics of labels and properties. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, and - transforming the environment as indicated by the binding items. BASIC INTERDOC GRAMMAR item ::= primary | binding | id ":!" -- :! for label declaration primary ::= id | primary "." id | literal | application | property | node id ::= letter ( letter | digit )* literal ::= Boolean | integer | hexint | real | string | label | external label ::= name "!" name ::= id ( "." id)* external ::= "$" name application ::= ( op | primary ) "(" item* ( "," item* )* ")" op ::= "'" | "+" | "" | "*" | "/" property ::= primary "#" node ::= "{" item* "}" binding ::= name [ op ] bindingMode ( primary | "(" item* ")" ) bindingMode ::= "=" | ":" | ":=" | "_" SYNTACTIC EXAMPLE: {Book.example! -- Places this in Book and Book.example ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a nonstandard property a:='(NOT(EQ(margins.left, 120))) margins.right_100 r=*(12.5, pt) IF(a, margins.left+_5 margins.right_5, margins.left+_10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Nil = "" locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T(E) = R&T(E) R&T

(E) = R&T(E))>(E) R&T(E) = literal; E R&T(E) = operate(op, arg*, E) R&T

(E) = operate(R

(E), arg*, E) R&T

(E) = R

(E) "#"; E R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R&T(E) = ""; bind(n, m, R

(E), E) = -- Syntactic sugar = R&T<"(" item* ")">(E) = R&T(E) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) =  bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null operate(op, arg*, E) = op = $QUOTE => arg*; E op = $HIDE => ""; E op = $ENV => [T([Null | "Outer" = E]) | "Outer" = Null]; E True => apply(op, eval(arg*, E)) apply(op, val1, ... , valn) = op = $IF => if val1.R then val2 else val3 op = "+" OR op = $PLUS => val1.R + ... + valn.R; E ... op = $LIST => val1 op = $SUBSCRIPT => val1[val2.R] -- val1: sequence, val2.R: int eval("", E) = Nil eval(arg1 arg*, E) = R&T(E), eval(arg*, E) bind(id, m, val, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, val, E) -- Assign at right level True => [E | id m val] bind(id.n, m, val, E) = [E | id bindingOf(id, E) bind(n, m, val, R(E))] assign(id, val, E) = locBinding(id, E) = ":" => [E | id ":" val] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", val, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! external names: $name the empty environment: Null the empty list: NIL sequences of values unevaluated expressions environments sets (sequences) of nodes with given labels How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", val, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). The (implicit) "outermost" environment binds each id to the external name $id. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties. Parentheses are used for grouping (e.g., creating a sequence value for a binding), and to delimit the argument list of an operator. The operator $ENV is used to create a new environment, which behaves much like a record. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES It should be clarified that the "view" of the dominant structure is ALWAYS controlled by the properties of its nodes. (E.g., text is not always there to be "shown".) Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its (local) properties, and don't remove any of them OR if you understand ALL properties of ALL nodes in the path back to the root. The presentation of this material could be clarified by a table that relates constructions in the notation to their intended uses and meanings. We should check our characterset for disjointness with Interpress.DoubtfulChars. STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. *start* 11654 00024 USm Date: 21 Aug. 1981 6:58 pm PDT (Friday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 23 To: Mitchell, Horning, Lampson Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. ------------------- Not done: State the formal semantics of labels and properties. Sets of properties, etc. (Cf. Mitchell's Font example.) Sort out "records" vs. quoted bindings. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, and - transforming the environment as indicated by the binding items. BASIC INTERDOC GRAMMAR item ::= primary | binding primary ::= id | primary "." id | literal | application | property | node id ::= letter ( letter | digit )* literal ::= Boolean | integer | hexint | real | string | label | external label ::= name "!" name ::= id ( "." id)* external ::= "$" name | op op ::= "+" | "" | "*" | "/" application ::= primary "(" item* ( "," item* )* ")" property ::= primary "#" node ::= "{" item* "}" binding ::= name [ op ] bindingMode rhs | id ":!" bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= [ "'" ] ( primary | "(" item* ")" ) SYNTACTIC EXAMPLE: {Book.example! -- Places this in Book and Book.example ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a nonstandard property a:='NOT(EQ(margins.left, 120)) margins.right_100 r=*(12.5, pt) IF(a, margins.left+_5 margins.right_5, margins.left+_10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Nil = "" locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T(E) = R&T(E) R&T

(E) = R&T(E))>(E) R&T(E) = literal; E R&T

(E) = CASE R

(E) OF $if => if R(E) then R&T(E) else R&T(E) "+" => R(E) + ... + R(E); E ... $val => R(E); E $list => R&T(E) $sub => R&T(E)[R(E)] -- Subscript, arg1: sequence | node, arg2.R: int $hide => ""; E R&T

(E) = R

(E) "#"; E R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = ""; bind(n, m, R(E), E) = -- Syntactic sugar = R&T<"'" p>(E) = p; E R&T<"(" item* ")">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E -- Construct a "record" environment value R&T<"'(" item* ")">(E) = item*; E R&T(E) = ??; E bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, val, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, val, E) -- Assign at right level True => [E | id m val] bind(id "." n, m, val, E) = [E | id bindingOf(id, E) bind(n, m, val, R(E))] assign(id, val, E) = locBinding(id, E) = ":" => [E | id ":" val] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", val, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! external names: $name the empty environment: Null the empty list: NIL sequences of values unevaluated expressions environments sets (sequences) of nodes with given labels How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", val, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). The (implicit) "outermost" environment binds each id to the external name $id. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties. Parentheses are used for grouping (e.g., creating a sequence value for a binding), and to delimit the argument list of an operator. The operator $ENV is used to create a new environment, which behaves much like a record. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES It should be clarified that the "view" of the dominant structure is ALWAYS controlled by the properties of its nodes. (E.g., text is not always there to be "shown".) Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its (local) properties, and don't remove any of them OR if you understand ALL properties of ALL nodes in the path back to the root. The presentation of this material could be clarified by a table that relates constructions in the notation to their intended uses and meanings. We should check our characterset for disjointness with Interpress.DoubtfulChars. STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). *start* 12386 00024 USm Date: 24 Aug. 1981 6:42 pm PDT (Monday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 24 To: Mitchell, Horning Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. ------------------- Not done: Determine the (informal) semantics of labels. State the formal semantics of labels and properties. Sets of properties, etc. (Cf. Mitchell's Font example.) SET/LIST operators ($append $union ?) notation for list constants Sort out "records" vs. quoted bindings. Some syntactic marker to replace $env. Consider style for use of temporary local definitions. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, alternately - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, and - transforming the environment as indicated by the binding items. BASIC INTERDOC GRAMMAR item ::= primary | binding primary ::= id | primary "." id | literal | application | property | node id ::= letter ( letter | digit )* literal ::= Boolean | integer | hexint | real | string | label | external label ::= name "!" name ::= id ( "." id)* external ::= "$" name | op op ::= "+" | "" | "*" | "/" application ::= primary "(" item* ( "," item* )* ")" property ::= primary "#" node ::= "{" item* "}" binding ::= name connection rhs | id ":!" connection ::= bindingMode | op bindingMode | bindingMode "'" bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= primary | "(" item* ")" SYNTACTIC EXAMPLE: {Book.example! -- Places this in Book and Book.example ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property a:='NOT(EQ(margins.left, 120)) margins.right_100 r=*(12.5, pt) IF(a, margins.left+_5 margins.right_5, margins.left+_10) } SEMANTICS R denotes the expression reduction function: R: expression > ( environment > expression ) T denotes the environment transformation function: T: expression > ( environment > environment ) R&T(E) denotes the pair R(E); T(E) R&T: ( expression, environment ) > ( expression, environment ) Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Nil = "" locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) R&T(E) = R&T(E) R&T

(E) = R&T(E))>(E) R&T(E) = literal; E R&T

(E) = CASE R

(E) OF $if => if R(E) then R&T(E) else R&T(E) "+" => R(E) + ... + R(E); E ... $val => R(E); E $list => R&T(E) $sub => R&T(E)[R(E)] -- Subscript, arg1: sequence | node, arg2.R: int $hide => ""; E R&T

(E) = R

(E) "#"; E R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = ""; bind(n, m, R(E), E) = -- Syntactic sugar = R&T<"'" p>(E) = p; E R&T<"(" item* ")">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E -- Construct a "record" environment value R&T<"'(" item* ")">(E) = item*; E R&T(E) = ??; E bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null bind(id, m, val, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants m = ":=" => assign(id, val, E) -- Assign at right level True => [E | id m val] bind(id "." n, m, val, E) = [E | id bindingOf(id, E) bind(n, m, val, R(E))] assign(id, val, E) = locBinding(id, E) = ":" => [E | id ":" val] bindingOf(id, E) = ":" => [E | "Outer" "=" bind(id, ":=", val, locVal("Outer", E))] True => E -- Can only assign to vars ------------------- Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! external names: $name the empty environment: Null the empty list: NIL sequences of values unevaluated expressions environments sets (sequences) of nodes with given labels How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", val, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). The (implicit) "outermost" environment binds each id to the external name $id. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties. Parentheses are used for grouping (e.g., creating a sequence value for a binding), and to delimit the argument list of an operator. The operator $ENV is used to create a new environment, which behaves much like a record. Semantics of labels: A label name! on a node gives that node membership in the sets identified by name (and its prefixes); the "main" identifier of a set name must be declared at the root of a subtree containing all its members. Multiple labels place the node in multiple sets, and a unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES It should be clarified that the "view" of the dominant structure is ALWAYS controlled by the properties of its nodes. (E.g., text is not always there to be "shown".) Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent. The presentation of this material could be clarified by a table that relates constructions in the notation to their intended uses and meanings. We should check our characterset for disjointness with Interpress.DoubtfulChars. Put in contents if: Put in environment if: effect is local to node has scope is directly edited is only indirectly edited is to be bound locally needs delayed or global binding STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. *start* 13389 00024 USm Date: 25 Aug. 1981 11:34 am PDT (Tuesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 25 To: Mitchell, Horning Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. ------------------- Open questions: Use of ( ... ) vs. [ ... ] (especially in application). Sort out "records" vs. quoted bindings. Sets of properties, etc. (Cf. Mitchell's Font example.) SET/LIST operators ($append $union ?) semantics of $list Non-uniform semantics of quote. Subtle distinctions between quoted and unquoted ( ... ) Semantics of quoted [ ... ] ? We should check our characterset for disjointness with Interpress.DoubtfulChars. Not done: State the formal semantics of labels and properties. Consider style for use of temporary local definitions. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items, and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property a:='NOT[EQ[margins.left, 120]] margins.right_100 r=*[12.5, pt] IF[a, margins.left+_5 margins.right_5, margins.left+_10] } GRAMMAR item ::= primary | binding | label primary ::= literal | invocation | application | property | node | "(" item* ")" literal ::= Boolean | integer | hexint | real | string | external | op external ::= "$" name name ::= id ( "." id)* id ::= letter ( letter | digit )* op ::= "+" | "" | "*" | "/" invocation ::= id | primary "." id application ::= primary "[" item* ( "," item* )* "]" property ::= primary "#" node ::= "{" item* "}" binding ::= name connection rhs connection ::= bindingMode | op bindingMode | bindingMode "'" bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= primary | "[" item* "]" label ::= id ":!" | name "!" | name "@" SEMANTICS R&T(E) = R&T(E) R&T

(E) = R&T(E))>(E) R&T(E) = literal; E R&T

(E) = CASE R

(E) OF $if => if R(E) then R&T(E) else R&T(E) "+" => R(E) + ... + R(E); E ... $val => R(E); E $list => R&T(E) $subscript => R&T(E)[R(E)] -- arg1: sequence | node, arg2.R: int $hide => "" ; E R&T

(E) = R

(E) "#"; E R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; E -- List constructor R&T<"[" item* "]">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E -- Construct a "record" environment value R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = "" ; bind(n, m, R(E), E) = -- Syntactic sugar = R&T<"'" p>(E) = p; E R&T<"'(" item* ")">(E) = item*; E ?? R&T<"'[" item* "]">(E) = ?? R&T

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. *start* 14892 00024 USm Date: 25 Aug. 1981 4:08 pm PDT (Tuesday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 26 To: Mitchell, Horning Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). ------------------- Open questions: Use of ( ... ) vs. [ ... ] (especially in application). Sort out "records" vs. quoted bindings. Sets of properties, etc. (Cf. Mitchell's Font example.) SET/LIST operators ($append $union ?) semantics of $list Non-uniform semantics of quote. Subtle distinctions between quoted and unquoted ( ... ) Semantics of quoted [ ... ] ? We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. use of various bracket pairs. enlarge op with a few more single-character operators? Possible node operators (purely in semantic domain, not operators?). $properties: node, environment > sequence -- All #'s $marks: node, environment > sequence -- All !'s $references: node, environment > sequence -- All @'s $contents: node, environment > sequence -- The rest (fringe) Consider restricting $subscript just to sequences, not nodes. Note that $if is the only operator that requires multiple sequences (hence commas, different syntax for argument list and sequence). Worth going back to treating it as a special case? Not done: Consider style for use of temporary local definitions. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items, and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property a:='NOT[EQ[margins.left, 120]] margins.right_100 r=*[12.5, pt] IF[a, margins.left+_5 margins.right_5, margins.left+_10] } GRAMMAR item ::= primary | binding | label primary ::= literal | invocation | application | property | node | sequence literal ::= Boolean | integer | hexint | real | string | external | op external ::= "$" name name ::= id ( "." id)* id ::= letter ( letter | digit )* op ::= "+" | "" | "*" | "/" invocation ::= id | primary "." id application ::= primary "[" item* ( "," item* )* "]" property ::= primary "#" node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name connection rhs connection ::= bindingMode | op bindingMode | bindingMode "'" bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= primary | "[" item* "]" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) R&T(E) = literal; E R&T(E) = R&T(E) R&T

(E) = R&T(E))>(E) R&T

(E) = CASE R

(E) OF $if => if R(E) then R&T(E) else R&T(E) "+" => R(E) + ... + R(E); E ... $val => R(E); E $list => R&T(E) $subscript => R&T(E)[R(E)] -- arg1: sequence | node, arg2.R: int $hide => "" ; E R&T

(E) = R

(E) "#"; E R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; E -- List constructor R&T<"[" item* "]">(E) = [T([Null | "Outer" = E]) | "Outer" = Null]; E -- Construct a "record" environment value R&T<>(E) = ""; E R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = "" ; bind(n, m, R(E), E) = -- Syntactic sugar = ?? R&T<"'" p>(E) = p; E R&T<"'(" item* ")">(E) = item*; E ?? R&T<"'[" item* "]">(E) = ?? R&T

(E) = R

(E) M(E) = prefixes(name) U(E) = prefixes(name) P&M&U(E) = P&M&U(E)>(E) P&M&U<"(" item* ")">(E) = P&M&U(E) P&M&U(E) = P(E) P(T(E)); M(E) M(T(E)); U(E) U(T(E)) prefixes(id) = id prefixes(name "." id) = name "." id prefixes(name) NOTATION FOR ENVIRONMENTS Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Nil = "" locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) VALUE SPACE Expressions in an Interdoc script may denote literal values: Booleans: (F, T) integers: ... -3, -2, -1, 0, 1, 2, 3, ... reals: 1.2E5, . . . strings: labels: A123!, anId!, Paragraph.Example! external names: $name the empty environment: Null the empty list: NIL sequences of values unevaluated expressions environments DISCUSSION How semantics are associated with an entire document: Each environment, E, initially contains only its "inherited" environment (bound to the id Outer). Most bindings take place directly in E. However, the value of a bind(id, ":=", val, E) will change E by rebinding id in the "innermost" environment (following the chain of Outers) in which it is bound, if that binding has the binding ":" (Var). Identifiers bound with binding "=" (Const) may not be rebound in inner environments. When an id is referred to and locBinding(id, E)=None, then the value is sought recursively in locVal("Outer"). The (implicit) "outermost" environment binds each id to the external name $id. Nodes are delimited by brackets. The contents of each node are implicitly prefixed by Sub, which will generally be bound in the containing environment to a quoted expression performing an environment transformation, and perhaps supplying some properties and marks. Parentheses are used to denote a sequence value. to delimit the argument list of an operator. Square brackets are used to denote a new environment value, which behaves much like a record. Semantics of labels: A mark name! on a node makes that node a "target" of the label name (and its prefixes); a reference name@ makes it a "source." The "main" identifier of a label must be declared (using name:!) at the root of a subtree containing all its sources and targets. The label represents a set of directed arcs, one from each of its sources to each of its destinations. Multiple marks make the node a target of in multiple labels. A unique label on a node places it in a singleton set, i.e., identifies it uniquely. OTHER NOTES It should be clarified that the "view" of the dominant structure is ALWAYS controlled by the properties of its nodes. (E.g., text is not always there to be "shown".) Conservative rules for editor treatment of script subtrees created by other editors: -It's OK to display a node if you understand at least one of its properties. -It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent. -It's OK to copy a node if that doesn't move any labels outside their scope, and you understand ALL properties of its new parent. -it's OK to delete a (subtree rooted at a) node if you understand ALL properties of its parent. The presentation of this material could be clarified by a table that relates constructions in the notation to their intended uses and meanings. Put in contents if: Put in environment if: effect is local to node has scope is directly edited is only indirectly edited is to be bound locally needs delayed or global binding STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  GENSYM IS AN EDITOR, NOT AN INTERCHANGE, FUNCTION.  STANDARDIZE CONCEPTS, NOT NAMES. HISTORY LOG  Bring the syntax up front.  Further develop parallelism between grammar and semantic equations.  Write semantic equations in terms of concrete syntax.  Quote general expressions.  V, E, C > R, T, E .  [...] > <...> for quotation of script expressions.  (E | id_e, m) > [E | id_e, m] for local binding.  Introduce primary to disambiguate expression* , factor lhs from binding.  Introduce Sub component to initialize nodes.  Debug semantics of braces and dot.  Mode > binding.  Debug semantics of (fix up indirection).  Add VAL.  Edited by Mitchell, 30 July 1981 9:21 pm PDT (Thursday): Changed grammar to allow more complete expression syntax; couldn't use "<" or ">" as operators because they delimit strings. Moved history log to end of message. Edited by Mitchell, 31 July 1981 12:20 pm PDT (Friday) Simplified expression syntax. Expressions with embedded binary operators are simply interpreted in a right-to-left fashion; e.g., x_a*b+c means x_a*(b+c). Fixed up semantic equations to reflect this. Exchanged the use of {}s and ()s. Edited by Mitchell, 7 Aug. 1981 4:40 pm PDT (Friday) Fixed error in semantics when exchanging the use of {}s and ()s. Edited by Horning 13 Aug. 1981 4:47 pm PDT (Thursday). E(id) > locVal(id, E) --Remove conflict with f(E). Outer > "Outer" Const > "=" id lookup rule modified (R & T) [E | id_e, m] > [E | id m e] "." as infix op expressions are evaluated left-to-right (except for binding operator) Reverse VAL/ENV default for parens. bindq > bind binding > bindingMode expand definition of apply inline default T(E) = E add comments to semantic equations ------------------- R<>(E) = Nothing -- The empty expression -- Expression sequence R(E) = R(E) R(T(E)) -- List insert T(E) = T(T(E)) -- Composition R(E) = literal R(E) = if bindingOf(id, E)=None then id else R(E) T(E) = if bindingOf(id, E)=None then E else T(E) R<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then R(T(E)) else R(T(E)) T<"IF(" e1 "," e2* "," e3* ")">(E) = if R(E) then T(T(E)) else T(T(E)) R<"NOT" p>(E) = if R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. *start* 15206 00024 USm Subject: Current Level 0/1 Interdoc status/rev. 27 To: Mitchell, Horning Edited by Jim H. on 26 Aug. 1981 11:43 am PDT (Wednesday). ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. use of various bracket pairs. enlarge op with a few more single-character operators? Possible node operators (purely in semantic domain, not operators?). $properties: node, environment > sequence -- All #'s $marks: node, environment > sequence -- All !'s $references: node, environment > sequence -- All @'s $contents: node, environment > sequence -- The rest (fringe) Consider restricting $subscript just to sequences, not nodes.  Syntax for selections. Not done: Consider style for use of temporary local definitions. disallow [ ... ] as independent item (semantically?) ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items, and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property a:='NOT[EQ[margins.left 120]]' margins.right_100 r=12.5*pt IF a (margins.left_+5 margins.right_5) margins.left+_10 -- Implicit FI  a | (margins.left_+5 margins.right_5) | margins.left+_10   (a | margins.left_+5 margins.right_5 | margins.left+_10)  -- Algol 68 } GRAMMAR item ::= term | node | sequence | binding | property | label term ::= primary ( op term )* | selection -- Ops apply right to left primary ::= literal | invocation | application literal ::= Boolean | integer | hexint | real | string | external | op external ::= "$" name name ::= id ( "." id )* id ::= letter ( letter | digit )* op ::= "+" | "" | "*" | "/" invocation ::= id | lookup "." id lookup ::= invocation | external -- Syntactically subsumed by primary application ::= lookup "[" item* "]" selection ::= IF term item item  selection ::= term "|" item "|" item   selection ::= "(" term "|" item* "|" item* ")"  node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= item | op term | "'" item* "'" | "[" item* "]" property ::= lookup "#" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) [Unless explicitly given below, T(E) = E.] R(E) = R(E) op R(E) R(E) = literal R&T(E) = R&T(E) R&T(E) = R&T(E))>(E) R&T(E) = CASE R(E) OF $val => R(E); E $list => "(" R(E) ")" ; E $subscript => R&T(E)[R(E)] -- item1: sequence | node, item2: int $hide => Nil ; E ... R&T<"IF" term item1 item2>(E) = if R(E) then R&T(E) else R&T(E) R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" = E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" = E]))) R<"(" item* ")">(E) = "(" R(E) ")" R<>(E) = Nil R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = Nil ; bind(n, m, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[" item* "]">(E) = [T([Null | "Outer" = E]) | "Outer" = Null], E) -- Construct a "record" environment value; usable only in rhs of binding R(E) = R(E) "#" R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). *start* 15461 00024 USm Subject: Current Level 0/1 Interdoc status/rev. 28 To: Mitchell, Horning Edited by Jim H. on 26 Aug. 1981 7:11 pm PDT (Wednesday). ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. Eliminate side-effects for $subscript (actually, all applications). Add application of defined functions. Note that Value[ ... ] allows use of temporary (hidden) local definitions, Nil[ ... ] allows placement of hidden nodes. ( ... ) creates list/sequence values (without hiding bindings). ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. use of various bracket pairs. enlarge op with a few more single-character operators? Possible node operators (purely in semantic domain, not operators?). $properties: node, environment > sequence -- All #'s $marks: node, environment > sequence -- All !'s $references: node, environment > sequence -- All @'s $contents: node, environment > sequence -- The rest (fringe) Consider restricting $subscript just to sequences, not nodes. Extend selection to CASE? Fix to semantics of := ?? Not done: ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items (recording the components of each node's environment in a form convenient to the editor), and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property a:='NOT[EQ[margins.left 120]]' margins.right_100 r=12.5*pt (a | margins.left_+5 margins.right_5 | margins.left+_10) -- conditional: Algol68 } GRAMMAR item ::= term | node | sequence | binding | property | label term ::= primary | primary op term | selection -- Ops apply right to left primary ::= literal | invocation | application literal ::= Boolean | integer | hexint | real | string | external | op external ::= "$" name name ::= id ( "." id )* id ::= letter ( letter | digit )* op ::= "+" | "" | "*" | "/" invocation ::= id | lookup "." id lookup ::= invocation | external -- Syntactically subsumed by primary application ::= lookup "[" item* "]" selection ::= "(" term "|" item* "|" item* ")" -- Algol 68 style conditional node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= item | op term | "'" item* "'" | "[" item* "]" property ::= lookup "#" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) [Unless explicitly given below, T(E) = E.] R(E) = literal R&T(E) = R&T(E) R&T(E) = R&T(E))>(E) R(E) = CASE R(E) OF "$equal" => R(E) = R(E) "$greater" => R(E) > R(E) . . . "$subscript" => R(E)[R(E)] -- item1: sequence | node, item2: int ELSE => R([E | "Value" "=" R(E)]) R(E) = R(E) op R(E) R&T<"(" term "|" item1* "|" item2* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" "=" E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; T(E) R<>(E) = Nil R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = Nil; bind(n, m, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[" item* "]">(E) = [T([Null | "Outer" "=" E]) | "Outer" "=" Null] -- Construct a "record" environment value; usable only in rhs of binding R(E) = R(E) "#" R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). *start* 15765 00024 USm Date: 27 Aug. 1981 7:51 pm PDT (Thursday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 29 To: Mitchell, Horning Edited by Jim H. on 26 Aug. 1981 7:11 pm PDT (Wednesday). ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. Eliminate side-effects for $subscript (actually, all applications). Add application of defined functions. Note that Value[ ... ] allows use of temporary (hidden) local definitions, Nil[ ... ] allows placement of hidden nodes. ( ... ) creates list/sequence values (without hiding bindings). Tidy up definition of assign, using bind("Outer." ...). Introduce value nonterminal into grammar (rule out more nonsense). rhs ::= ... | "[" [ lookup ] "|" binding* "]" . Remove $ name from literal (to lookup). Change nonterminal lookup to invocation. ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. enlarge op with a few more single-character operators? %, &, \ Possible node operators (purely in semantic domain, not operators?). $properties: node, environment > sequence -- All #'s $marks: node, environment > sequence -- All !'s $references: node, environment > sequence -- All @'s $contents: node, environment > sequence -- The rest (fringe) Consider restricting $subscript just to sequences, not nodes. Extend selection to CASE? Not done: ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items (recording the components of each node's environment in a form convenient to the editor), and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property Font_[Font | size_10*pt face_bold] a:='NOT[EQ[margins.left 120]]' margins.right_100 r=12.5*pt (a | margins.left_+5 margins.right_5 | margins.left+_10) -- conditional: Algol68 } GRAMMAR item ::= value | binding | property | label value ::= term | node | sequence term ::= primary | primary op term -- Ops apply right to left primary ::= literal | invocation | application | selection literal ::= Boolean | integer | hexint | real | string | op op ::= "+" | "" | "*" | "/" invocation ::= name | external name ::= id ( "." id )* id ::= letter ( letter | digit )* external ::= "$" name application ::= invocation "[" value* "]" selection ::= "(" term "|" item* "|" item* ")" -- Algol 68 style conditional node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= value | op term | "'" item* "'" | "[" [ invocation ] "|" binding* "]" property ::= invocation "#" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) [Unless explicitly given below, T(E) = E.] R(E) = R(E) op R(E) R(E) = literal R&T(E) = R&T(E) R&T(E) = R&T(E))>(E) R<"$" name>(E) = "$" name R(E) = CASE R(E) OF "$equal" => R(E) = R(E) "$greater" => R(E) > R(E) . . . "$subscript" => R(E)[R(E)] -- value1: sequence | node, value2: int ELSE => R([E | "Value" "=" R(E)]) R&T<"(" term "|" item1* "|" item2* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" "=" E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; T(E) R<>(E) = Nil R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = Nil; bind(n, m, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[" invocation "|" binding* "]">(E) = [T([R(E) | "Outer" "=" E]) | "Outer" "=" Null] R<"[|" binding* "]">(E) = [T([Null | "Outer" "=" E]) | "Outer" "=" Null] R(E) = R(E) "#" R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). *start* 15962 00024 USm Date: 28 Aug. 1981 2:09 pm PDT (Friday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 30 To: Mitchell, Horning, Guttag Edited by Jim H. on 28 Aug. 1981 2:08 pm PDT (Friday). [Changes since 25 August] ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. Eliminate side-effects for $subscript (actually, all applications). Add application of defined functions. Note that Value[ ... ] allows use of temporary (hidden) local definitions, Nil[ ... ] allows placement of hidden nodes. ( ... ) creates list/sequence values (without hiding bindings). Tidy up definition of assign, using bind("Outer." ...). Introduce value nonterminal into grammar (rule out more nonsense). rhs ::= ... | "[" [ lookup ] "|" binding* "]" . Change nonterminal lookup to invocation. Remove $ name from literal (to invocation). Add node operators: $properties -- All #'s $marks -- All !'s $references -- All @'s $contents -- The rest (fringe) Restrict $subscript just to sequences, not nodes. ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. enlarge op with a few more single-character operators? %, &, \ Possible node operators (purely in semantic domain, not operators?). Extend selection to CASE? Not done: ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items (recording the components of each node's environment in a form convenient to the editor), and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property Font_[Font | size_10*pt face_bold] factorial_'(LT[Value 2] | 1 | Value* factorial(Value-1))' a:='NOT[EQ[margins.left factorial[5]]]' margins.right_100 r=12.5*pt (a | margins.left_+5 margins.right_5 | margins.left+_10) -- conditional: Algol68 } GRAMMAR item ::= value | binding | property | label value ::= term | node | sequence term ::= primary | primary op term -- Ops apply right to left primary ::= literal | invocation | application | selection literal ::= Boolean | integer | hexint | real | string | op op ::= "+" | "" | "*" | "/" invocation ::= name | external name ::= id ( "." id )* id ::= letter ( letter | digit )* external ::= "$" name application ::= invocation "[" value* "]" selection ::= "(" term "|" item* "|" item* ")" -- Algol 68 style conditional node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= value | op term | "'" item* "'" | "[" [ invocation ] "|" binding* "]" property ::= invocation "#" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) [Unless explicitly given below, T(E) = E.] R(E) = R(E) op R(E) R(E) = literal R&T(E) = R&T(E) R&T(E) = R&T(E))>(E) R<"$" name>(E) = "$" name R(E) = apply(invocation, R(E), E) apply(invocation, value*, E) = CASE R(E) OF "$equal" => value1 = value2 "$greater" => value1 > value2 . . . "$subscript" => value1[value2] -- value1: sequence, value2: int "$contents" => C "$properties" => P(E) "$marks" => M(E) "$references" => U(E) ELSE => R([E | "Value" "=" value*]) R&T<"(" term "|" item1* "|" item2* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" "=" E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; T(E) R<>(E) = Nil R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = Nil; bind(n, m, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[" invocation "|" binding* "]">(E) = [T([R(E) | "Outer" "=" E]) | "Outer" "=" Null] R<"[|" binding* "]">(E) = [T([Null | "Outer" "=" E]) | "Outer" "=" Null] R(E) = R(E) "#" R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). *start* 16589 00024 US Subject: Current Level 0/1 Interdoc status/rev. 31 To: Mitchell, Horning, Guttag Edited by Jim H. on 1 Sept. 1981 3:09 pm PDT (Tuesday). ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. enlarge op with a few more single-character operators? %, &, \ Extend selection to CASE? Better way to present semantics? Not done: Compressed syntactic example. Label ::= Mark | Source | Target | Link Properties/Attributes Format for description of standard properties $ hidden # R&T&P&M&U > R&B&M&S&T Hints to implementors: environment restoration points coding tricks for common structures Editor levels Internal definition/invocation Nesting of nodes Links ------------------- STANDARD CARD  WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING.  EVERY SCRIPT IS PARSED BEFORE BEING INTERPRETED.  STANDARDIZE CONCEPTS, NOT NAMES.  COMBINING DOCUMENTS IS AN EDITOR, NOT AN INTERCHANGE, TASK.  GENSYM IS AN EDITOR FUNCTION. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the script, repeatedly - reducing each expression to its "dominant structure," containing only literals, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - transforming the environment as indicated by the binding items (recording the components of each node's environment in a form convenient to the editor), and - recording the links indicated by label references and marks. BASIC INTERDOC SYNTACTIC EXAMPLE: {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a property Font_[Font | size_10*pt face_bold] factorial_'(LT[Value 2] | 1 | Value*factorial(Value-1))' a:='NOT[EQ[margins.left factorial[5]]]' margins.right_100 r=12.5*pt (a | margins.left_+5 margins.right_5 | margins.left+_10) -- conditional: Algol68 } -- Or, using short identifiers, and omitting comments and unnecessary spaces: {b.e!ep um#f_[f|s_10*pt fc_bo]fa_'(l[Value 2]|1|Value*fa(Value-1))' a:='n[e[m.l fa[5]]]'m.r_100 r=12.5*pt(a|m.l_+5 m.r_5|m.l+_10)} GRAMMAR item ::= value | binding | property | label value ::= term | node | sequence term ::= primary | primary op term -- Ops apply right to left primary ::= literal | invocation | application | selection literal ::= Boolean | integer | hexint | real | string | op op ::= "+" | "" | "*" | "/" invocation ::= name | external name ::= id ( "." id )* id ::= letter ( letter | digit )* external ::= "$" name application ::= invocation "[" item* "]" selection ::= "(" term "|" item* "|" item* ")" -- Algol 68 style conditional node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= value | op term | "'" item* "'" | "[" [ invocation ] "|" binding* "]" property ::= invocation "#" label ::= id ":!" | name "!" | name "@" SEMANTICS R: expression > environment > expression -- Reduction T: expression > environment > environment -- Transformation R&T(E) denotes the pair R(E); T(E) [Unless explicitly given below, T(E) = E.] R(E) = R(E) op R(E) R(E) = literal R&T(E) = R&T(E) R&T(E) = R&T(E))>(E) R<"$" name>(E) = "$" name R(E) = apply(invocation, R(E), E) R&T<"(" term "|" item1* "|" item2* ")">(E) = if R(E) then R&T(E) else R&T(E) R&T<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"; locVal("Outer", (T<"Sub" item*>([Null | "Outer" "=" E]))) R&T<"(" item* ")">(E) = "(" R(E) ")" ; T(E) R<>(E) = Nil R&T(E) = R(E) R(T(E)); T(T(E)) R&T(E) = Nil; bind(n, m, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[" invocation "|" binding* "]">(E) = [T([R(E) | "Outer" "=" E]) | "Outer" "=" Null] R<"[|" binding* "]">(E) = [T([Null | "Outer" "=" E]) | "Outer" "=" Null] R(E) = R(E) "#" R

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). Edited by Jim H. on 28 Aug. 1981 2:08 pm PDT (Friday). ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. Eliminate side-effects for $subscript (actually, all applications). Add application of defined functions. Note that Value[ ... ] allows use of temporary (hidden) local definitions, Nil[ ... ] allows placement of hidden nodes. ( ... ) creates list/sequence values (without hiding bindings). Tidy up definition of assign, using bind("Outer." ...). Introduce value nonterminal into grammar (rule out more nonsense). rhs ::= ... | "[" [ lookup ] "|" binding* "]" . Change nonterminal lookup to invocation. Remove $ name from literal (to invocation). Add node operators: $properties -- All #'s $marks -- All !'s $references -- All @'s $contents -- The rest (fringe) Restrict $subscript just to sequences, not nodes. *start* 22301 00024 US Date: 4 Sept. 1981 4:39 pm PDT (Friday) From: Horning.pa Subject: Current Level 0/1 Interdoc status/rev. 32 To: Mitchell, Horning, Lampson [Candidate for circulation to Interdoc^, with history log removed.] Edited by Jim H. on 4 Sept. 1981 4:03 pm PDT (Friday). Compressed syntactic example. Re-order sections, in preparation for circulation to Interdoc^. Label ::= Mark | Source | Target | Link R&T&P&M&U > R&B&M&S&T external names > universal names remove op as literal $ hidden # Properties(present/absent)/Attributes(have values and scopes) Format for description of standard properties Editor levels Internal definition/invocation Nesting of nodes Links Hints to implementors: environment restoration points coding tricks for common structures ------------------- Open questions: We should rethink our character assignments. check our characterset for disjointness with Interpress.DoubtfulChars. enlarge op with a few more single-character operators? %, &, \ Better way to present semantics? Not done: ------------------- STANDARD CARDS 1. WE ARE DESIGNING A STANDARD FOR INTERCHANGE, NOT EDITING. 2. EVERY SCRIPT IS PARSED BEFORE BEING INTERPRETED. 3. STANDARDIZE CONCEPTS, NOT NAMES. 4. COMBINING DOCUMENTS IS AN EDITOR, NOT AN INTERCHANGE, TASK. 5. GENSYM IS AN EDITOR FUNCTION. 6. CHARACTER-SET AND LEXICAL ISSUES CAN BE RESOLVED AT THE END. 7. GET THE TECHNICAL BASIS RIGHT BEFORE WORRYING ABOUT THE POLITICAL ISSUES. ------------------- We envision an Interdoc script being input and viewed in any manner equivalent to the following: Parse the entire script, repeatedly - reducing each expression to its "dominant structure," containing only literals and structural delimiters, by replacing identifiers by the values to which they are bound in the current environment, by applying operators, and by removing binding items, - determining the properties of each node from its marks, - recording the sources and targets for all links, and - transforming the environment as indicated by the binding items (recording the relevant attributes for each node in a form convenient to the particular editor). BASIC INTERDOC SYNTACTIC EXAMPLE {Book.example! -- Links to this from Book@ and Book.example@ ExampleParagraph -- Invokes a definition $UniqueMark12356# -- Adds a mark Font_[Font | size_10*pt face_bold] factorial_'(LT[Value 2] | 1 | Value*factorial(Value-1))' a:='NOT[EQ[margins.left factorial[5]]]' margins.right_100 r=12.5*pt (a | margins.left_+5 margins.right_5 | margins.left+_10) -- conditional: Algol68 } -- Or, using short identifiers, and omitting comments and unnecessary spaces: {b.e!ep um#f_[f|s_10*pt fc_bo]fa_'(l[Value 2]|1|Value*fa(Value-1))' a:='n[e[m.l fa[5]]]'m.r_100 r=12.5*pt(a|m.l_+5 m.r_5|m.l+_10)} GRAMMAR item ::= value | binding | label value ::= term | node | sequence term ::= primary | primary op term op ::= "+" | "" | "*" | "/" primary ::= literal | invocation | application | selection literal ::= Boolean | integer | hexint | real | string invocation ::= name | universal name ::= id ( "." id )* id ::= letter ( letter | digit )* universal ::= "$" name application ::= invocation "[" item* "]" selection ::= "(" term "|" item* "|" item* ")" node ::= "{" item* "}" sequence ::= "(" item* ")" binding ::= name bindingMode rhs bindingMode ::= "=" | ":" | ":=" | "_" rhs ::= value | op term | "'" item* "'" | "[" [ invocation ] "|" binding* "]" label ::= mark | link mark ::= invocation "#" link ::= name "@" | name "!" | id "@!" SEMANTICS: REDUCTION AND BINDING R: expression, environment > expression -- Reduction B: expression, environment > environment -- Bindings R&B(E) denotes the pair R(E); B(E) [Unless explicitly given below, B(E) = E.] R(E) = R(E) op R(E) R(E) = literal R&B(E) = R&B(E) R&B(E) = R&B(E))>(E) R<"$" name>(E) = "$" name R(E) = apply(invocation, R(E), E) R&B<"(" term "|" item1* "|" item2* ")">(E) = if R(E) then R&B(E) else R&B(E) R&B<"{" item* "}">(E) = "{" R<"Sub" item*>([Null | "Outer" "=" E]) "}"; locVal("Outer", (B<"Sub" item*>([Null | "Outer" "=" E]))) R&B<"(" item* ")">(E) = "(" R(E) ")" ; B(E) R<>(E) = Nil R&B(E) = R(E) R(B(E)); B(B(E)) R&B(E) = Nil; bind(name, mode, R(E), E) = -- Syntactic sugar R<"'" item* "'">(E) = item* --Usable only in rhs of binding R<"[|" binding* "]">(E) = [B([Null | "Outer" "=" E]) | "Outer" "=" Null] R<"[" invocation "|" binding* "]">(E) = [B([R(E) | "Outer" "=" E]) | "Outer" "=" Null] R(E) = R(E) "#" R(E) = link -- Subsidiary definitions for R&T bindingOf(id, E) = locBinding(id, whereBound(id, E)) -- Gets innermost binding valOf(id, E) = locVal(id, whereBound(id, E)) -- Gets innermost value whereBound(id, E) = -- Finds innermost binding locBinding(id, E) ~= None => E locBinding("Outer", E) ~= None => whereBound(id, locVal("Outer", E)) True => Null apply(invocation, value*, E) = CASE R(E) OF "$equal" => value1 = value2 "$greater" => value1 > value2 . . . "$subscript" => value1[value2] -- value1: sequence, value2: int "$marks" => "(" M ")" "$links" => "(" L ")" "$sources" => "(" S ")" "$targets" => "(" T ")" "$contents" => "(" C ")" ELSE => R([[Null | "Outer" "=" E] | "Value" "=" value*]) inner("{" value* "}") = value* bind(id, mode, value, E) = bindingOf(id, E) = "=" => E -- Can't rebind constants mode = ":=" => assign(id, value, E) -- Assign at right level True => [E | id mode value] bind(id "." name, mode, value, E) = [E | id bindingOf(id, E) bind(name, mode, value, valOf(id, E))] assign(id, value, E) = locBinding(id, E) = ":" => [E | id ":" value] bindingOf(id, E) = ":" => bind("Outer." id, ":=", value, E) True => E -- Can only assign to vars NOTATION FOR ENVIRONMENTS Environments bind identifiers to expressions, in various modes ("=", ":", ":=", "_"): Null denotes the "empty" environment [E | id m e] means "E with id mode m bound to e" locBinding(id, E) denotes the binding mode of id in E locBinding(id, Null) = None locBinding(id, [E | id' m e]) = if id=id' then m else locBinding(id, E) locVal(id, E) denotes the value locally bound to id in E locVal(id, Null) = Nil = "" locVal(id, [E | id' m e]) = if id=id' then e else locVal(id, E) SEMANTICS OF MARKS, LINKS, CONTENTS 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 C: expression > expression -- Content of node [These functions all return the non-value, Nil (which does not lengthen a sequence), except as specified below.] M = name M<"(" item* ")"> = M M = M M L = id L<"(" item* ")"> = L L = L L S = prefixes(name) S<"(" item* ")"> = S S = S S T = name T<"(" item* ")"> = T T = T T C = value C

(E) then False else True R(E) = op = "." => R([R(E) | "Outer" = E]) op = "+" => R(E)+R(E) . . . R(E) = Nothing -- Empty list T(E) = bind(n, m, R(E), E) T(E) = bind(n, m, e, E) T(E) = bind(n, m, R(E), E) R<"{" labels e* "}">(E) = "{" labels R([Null | "Outer" = E]) "}" T<"{" labels e* "}">(E) = locVal("Outer", (T<"ENV("Sub e*")">(E))) R<"(" e* ")">(E) = R(E) R<"ENV(" e* ")">(E) = [T<"ENV(" e* ")">(E) | "Outer" = Null] T<"ENV(" e* ")">(E) = T([Null | "Outer" = E]) ------------------- Edited by Jim Horning 17 Aug. 1981 10:49 am PDT (Monday) R&T<> Nothing > "" Edited by Jim H. on 17 Aug. 1981 4:58 pm PDT (Monday) Remove side-effects from all expressions. Parentheses purely for grouping (don't hide environment transformations). #label > label ! labels within nodes Edited by Jim H. on 19 Aug. 1981 9:52 am PDT (Wednesday). Rewrite as syntactic sugar. structured labels re-introduce apply function in R&T correct syntax for "." % for opening an environment (also replaces ENV?) Edited by Jim H. on 19 Aug. 1981 6:55 pm PDT (Wednesday). Drop "%"; ENV() is now the only environment-constructing operator. Add SUB operator (first operand: sequence only, second: number only). Add atoms, as distinct from ids. Fix lhs op rhs syntax. Edited by Jim H. on 20 Aug. 1981 5:29 pm PDT (Thursday). resolve pending questions as per message of 20 Aug. 1981 12:29 pm PDT. distinguish syntactically between properties (marks) and labels. only the "main" id of a label is declarable. eliminate  as an id character. eliminate op ids from grammar. restructure the grammar for "functional" notation for operators. update semantic equations for new grammar, etc. fix treatment of unbound qualified names (now produce Nil). Edited by Jim H. on 21 Aug. 1981 6:58 pm PDT (Friday). restore $val. move quoting to rhs, allow quoted primaries without parentheses. allow an op to be the rhs of a definition. eliminate the functions operate, apply, eval by back substitution. change semantics of () to allow "record" construction without $env. Edited by Jim H. on 24 Aug. 1981 6:08 pm PDT (Monday). "It's OK to edit a node if you understand ALL of its (local) properties, and either don't remove any of them or also understand ALL properties of its parent." "Put in contents if: Put in environment if: ..." Add connection syntax to syntactically rule out a+_'b. Edited by Jim H. on 25 Aug. 1981 11:33 am PDT (Tuesday). Syntactically separate label references and name invocation. Put in distinct syntax in rhs for environment construction. Informal semantics of labels. ( ... ) > [ ... ] in applications; permitting ( ... ) as a primary. Edited by Jim H. on 25 Aug. 1981 4:08 pm PDT (Tuesday). Add sequence as a nonterminal to the syntax. State the formal semantics of labels and properties. Reorder presentation (hopefully to improve readability). Edited by Jim H. on 28 Aug. 1981 2:08 pm PDT (Friday). ' ... ' in rhs Restore infix operators, right to left. Modify syntax to rule out more nonsense, add semantically meaningful nonterminals. Introduce special syntax for selections. Eliminate side-effects for $subscript (actually, all applications). Add application of defined functions. Note that Value[ ... ] allows use of temporary (hidden) local definitions, Nil[ ... ] allows placement of hidden nodes. ( ... ) creates list/sequence values (without hiding bindings). Tidy up definition of assign, using bind("Outer." ...). Introduce value nonterminal into grammar (rule out more nonsense). rhs ::= ... | "[" [ lookup ] "|" binding* "]" . Change nonterminal lookup to invocation. Remove $ name from literal (to invocation). Add node operators: $properties -- All #'s $marks -- All !'s $references -- All @'s $contents -- The rest (fringe) Restrict $subscript just to sequences, not nodes.