© Jørgen Steensgaard-Madsen, Copenhagen, 2006
General properties                                                  

Howard languages share a general approach to syntax and semantics of structured expressions, be it statements or object instantiation, for instance. It means that they use the same scanner/parser and type system. This page provides a brief explanation and is fairly abstract in the sense that no examples are given. Readers are assumed to be familiar with formal grammars expressed in the notation EBNF.
Formal notation is condensed to the essential parts of the language. Some variations over the general theme are described by ad-hoc rules. They are reflected in the actual syntax used in the implementation (using bison) but they tend to make the formal presentation too complex.
Syntactic details for specific constructs is expressed by signatures which can be compared to descriptions of subroutines in various programming languages. Terms like prototypes and procedure headings are used for similar descriptions in other languages. A signature tells about number of subconstructs and type requirements that relate to application of a specific construct, e.g.
if OF T (Condition:int) [TrueBranch:T] [FalseBranch:T]
describes an if-construct that returns a value of some application specific type T (which may be void).
Most of the power of Howard languages is related to the possible complexity of signatures combined with the rules of application syntax.

Expression syntax

An incomplete EBNF grammar for expressions reads as follows:
Expression  =   { [ Operator ] Term } [ Operator ]
Term        =   "(" Expression ")" | Application | Constant
Application =   Operation { [ Label ] Clauselist }
Operation   =   [ Identifier "." ] Identifier
Clauselist  =   "(" Expression { "," Expression } ")" 
              | "{" Expression { ";" Expression } "}"
Label       =   Identifier [ ":" ]

Operators and Identifiers are distinguishable tokens mostly sequences of elements from different subsets of characters. The length of an Clauselist is one for the embraced kind and the number of expression between the parentheses otherwise. The sum of length of Clauselists in an Application is called the apparent number of clauses.
A label is an identifier that appears in a Label. Sometimes it appears just for readability, sometimes it appears before the period in an Operation as a qualifier for the following identifier, and it may even appear as an operation itself - in the latter case as a shorthand as a qualifier for the special operation name __.

Signature syntax

An incomplete EBNF grammar for signatures (our term for prototypes) reads
Signature      =   Identifier Typeoperators CDList [ ":" Type ]
                 | Operator "(" Type "," Type ")" ":" Type
Typeoperators  =   [ "OF" Typeop { "," Typeop } ]
Typeop         =   [ Number ] Identifier
CDList         =   [ "(" Signature { "," Signature } ")" ]
                   { "[" Signature "]" }
Type           =   { Type } Identifier

This is a simplified version, not reflecting the restrictions that signatures in a parenthesis must not contain bracketed signatures and must end with a type.
An operation name is an identifier that appears first in a Signature. A type operator is an identifier that appears in Typeop. A preceding number is the arity of the type operator: it must be positive and integral. A missing number corresponds to zero arity. The number of Types preceding a type operator in a Type must be equal to its arity. The number of (non-nested) Signatures in a CDList is the arity of the operation name.

Ad hoc rules

These are the most important syntax rules. Some supplementary rules of syntax are better described in natural language: Note that the first four rules require that something being defined by a contribution. The definitions state simple symbolic transformations.

Syntax of special constructs

A few operations are implemented directly in the core language. This includes means to define new operations in terms of predefined ones as well as recursive activation of the interpreter with a context as the one that express the activation.
Simple comments follow the usual script convention: text between a # character and an end of line is a comment.
Text (with balanced braces) beween ${ and } is a comment.
Expression = ... | "DEF" Signature Clauselist
where the clause list must have length 2, but do not forget that the tail coup may be used. The first clause defines the semantics of the signature's identifier. Recursive definitions are allowed. The second clause is the scope of the defined operation, which may be applied using the general syntax rules, of course.
Record types
Expression = ... | REC Identifier Bindings { ";" Expression }
Bindings = "(" Identifier ":" Type "," Identifier ":" Type ")"
The first identifier serves as a function to create a value of the record's type and the identifiers of the bindings serve as projections from the record's type to the corresponding type of the bindings.
REC N(n1:t1,n2:t2,...,np:tp);
with (N(e1,e2,...,ep) x;
x == N(n1(x),n2(x),...,np)
The list of expressions forms the scope of these functions.
Expression = ... | "ANY"
indicates that a result, e.g. in a DEFined computation, cannot be given. Sometimes it is meaningless to provide a result, as for instance when a divisor is zero. The contributed division handles this gracefully, and ANY exists to allow user defined operations to react likewise.
An undefined result prevents computations that depend directly on the the result. Computation will be resumed at a point where such a dependency is discarded, typically where a sequential computation goes on to a next step.
No action
Expression = ... | "skip"
might as well be discarded, but an explicit use can be useful for readability.
Context restriction
The operation name NEW_CONTEXT prevents embedded interpretation in any of its clauses (as defined for the purpose) from access to operations that are external to the clause. Note that external operations may be applied directly, only the `invisible' applications that might be given as commands dynamically are prevented. Consequently it is possible to define local operations in terms of external ones.


·Demo language
Implementation tool

·General properties

File translated from TEX by TTH, version 3.33.
On 18 Oct 2006, 16:47.
SourceForge.net Logo