B construct a record type from a module C transform top type to exceptional input printing wrapper G transform top type to recombining grid thereof I transform top type to instance recognizer J transform top type to job thereof L transform top type to list thereof M transform top type to error messenger N transform top type to balanced tree thereof O make top type printed as opaque P transform top type to printing function Q transform top type to compressed version R qualify C or V with recursive attribute S transform top type to set thereof T transform top type to a tree thereof W transform top type to a pair Y transform top type to self-describing formatter Z replace top type with union with empty instance d duplicate the operand on the top of the stack h push recursive type or raise the top one k transform top type or function to identity function l replace the top operand on the stack with its left side m transform top type to list of assignments of strings thereto p transform top type to parsing function r replace the top operand on the stack with its right side u transform top constant to unit type type stack operators of arity 2

-?..?- cumulative conditional with default case last -..- cumulative functional composition -|..|- cumulative ||, short circuit functional disjunction -!..!- cumulative !|, logical valued functional disjunction -&..&- cumulative &&, short circuit functional conjunction [..] record delimiters <..> list delimiters {..} specifies sets as sorted lists with duplicates purged (..) tuple delimiters

The content of the diagnostic message is the only feature specific to the definition of retype as a type converter.

5.3 Remarks A quick summary of the aggregate operators described in this chapter is available interac- tively from the command

$ fun --help outfix whose output is shown in Listing 5.2. Some of these, especially the logical operators, are comparable to infix operators that perform similar operations, as the listing implies and as the next chapter documents.

If you truly believe in the system of law you administer in my country, you must inflict upon me the severest penalty possible. Ben Kingsley in Gandhi

With the previous chapter having exhausted what little there is to say about operators in general terms, this chapter details the semantics for each operator in the language on more of an individual basis. The operators are organized into groups roughly by related func- tionality, and ordered in some ways by increasing conceptual difficulty. An understanding of the conventions pertaining to arity and dyadic operators explained previously is a pre- requisite to this chapter.

6.1 Data transformers The six operators listed in Table 6.1 are used to express lists, assignments, sets, and trees, and some are already familiar from many previous examples. The set union operator, |, has only infix and solo arities, but the others have all four arities. These operators represent first order functions in their infix arities, and are dyadic in other arities (see Section 5.1.4). Hence, it is possible to write t[U+02C6]:u and t[U+02C6]: u interchangeably for a tree with root t and subtrees u.

6.2 Constant forms

The operators shown in Table 6.2 are normally used to express functions that may depend on hard coded constants. They have these algebraic properties. fflThe constant combinator can be used either as a solo or as a postfix operator, and satisfies ! x j x! for all x. fflThe binary to unary combinators can be used as solo or infix operators, and are dyadic.

6.2.1 Semantics The constant combinator and binary to unary combinators are well known features of 1 functional languages, although the notation may vary. The binary to unary combinators may also be familiar to C++ programmers as part of the standard template library.

Constant combinators The constant combinator takes a constant operand and constructs a function that maps any argument to that operand. Such functions occur frequently as the default case of a conditional or the base case of a recursively defined function. Binary to unary combinators

The binary to unary combinators / and \ take a function as their left operand and a constant as their right operand. The function is expected to be one whose argument is usually a pair of values. The combinator constructs a function that takes only a single value as an argument, and returns the result obtained by applying the original function to the pair made from that value along with the constant operand. For the / combinator, the constant becomes the left side of the argument to the function, and for the \ combinator, it becomes the right. Standard examples are functions that add 1 to a number, plus/1. or plus\1., and a function that subtracts 1 from a number, minus\1.. Normally the plus and minus functions perform addition or subtraction given a pair of numbers. In the latter case, the reverse binary to unary combinator is used specifically because subtraction is not commu- tative. Currying A frequent idiomatic usage of the binary to unary combinator is in the expres- sion ///, which is parsed as (/)/(/), and serves as a currying combinator. Any mem- ber f of a function space .u [U+0398] v/ ! w induces a function g in u ! .v ! w/ such that g D /// f. This effect is a consequence of the semantics of these operators and their algebraic properties whose proof is a routine exercise.

Example The currying combinator allows any function that takes a pair of values to be converted to one that allows so-called partial application. For example, a partially valuable addition function would be /// plus. It takes a number as an argument and returns a function that adds that number to anything. $ fun flo --m="((/// plus) 2.) 3." --c 5.000000e+00 The plus function is defined in the flo library distributed with the compiler. 1 Curried functional languages don’t need a binary to unary combinator, but the reverse binary to unary combinator could be a problem for them.

Mapped binary to unary combinators The operators /* and \* serve a similar purpose to the binary to unary combinators above, but are appropriate for operations on lists. The left operand is a function taking a pair of values and the right operand is a constant, as above, but the resulting function takes a list of values rather than a single value. The constant operand is paired with each item in the list and the function is evaluated for each pair. A list of the results of these evaluations is returned. This example uses the concatenation operator explained in the previous section to con- catenate each item in a list of strings with an x. $ fun --m="--\*x <'a',b,c>" --c <'ax',bx,cx>

6.2.2 Suffixes The binary to unary combinators / and \ allow suffixes consisting of any sequence of the characters $, |, ;, and . that doesn’t begin with *. The mapped binary to unary combinators / and \* allow suffixes consisting of any sequence of the characters $, =, and *. Each character alters the semantics of the function constructed by the operator in a particular way. To summarize their effects briefly, fflthe $ makes the function apply to both sides of a pair fflthe | makes the function triangulate over a list fflthe ; makes the function transform a list by deleting all items for which it is false

Some experimentation with these operator suffixes is a better investment of time than read- ing a more formal exposition would be. A few examples to get started are the following. fflThis example shows how negative numbers can be removed from a list. $ fun flo --m="fleq/;0. ←2.,-1.,0.,1.,2.>" --c %eL <0.000000e+00,1.000000e+00,2.000000e+00>

The last example works because f/|n <a,b,c,d> is equivalent to <a,f(n,b),f(n,f(n,c)),f(n,f(n,f(n,d)))> Often there are several ways of expressing the same thing, and the choice is a matter of programming style. The function product/|2 is equivalent to the pseudo-pointer ~&iNiCBK9 (see pages 76 and 87). In case of any uncertainty about the semantics of these operators, there is always re- course to decompilation. $ fun --m="--\*=$x" --decompile main = fan compose( reduce(cat,0), map compose(cat,couple(field &,constant x)))

6.3 Pointer operations

A small classification of operators shown in Table 6.3 pertains to pointers in one way or another. 6.3.1 The ampersand

The ampersand has been used extensively in previous examples variously as the identity pointer, the true boolean value, or a notation for the pair of empty pairs, which are all equivalent in their concrete representations, but at this stage, it is best to think of it is as an operator. 201

6.3.2 The tilde The tilde operator can be used either as a prefix or as a solo operator. It has the algebraic property that _{x j} x for all x. A distinction is made nevertheless between the solo and the prefix usage because the latter has higher precedence. The operand of the tilde operator can be any expression that evaluates to a pointer. A primitive form of such an expression would be a pointer specified by the ampersand operator, a field identifier from a record declaration, or a literal address from an a-tree or grid type. Tuples of these expressions are also meaningful as pointers, and the colon and dot operators can be used to build more pointer expressions from these. The tilde operator is defined partly as a source level transformation that lets it depend on the concrete syntax of its operand. Pseudo-pointer suffixes for the ampersand operator, while not normally meaningful in themselves, are acceptable when the ampersand forms part of the operand of a tilde operator. The tilde in this case effectively disregards the ampersand and makes direct use of the pseudo-pointer suffix. The result returned by the tilde operator is a either a virtual code program of the form field p for an pointer operand p, or a function of unrestricted form if its operand is a pseudo-pointer. The field combinator pertains to deconstructors, which are functions that return some part of their argument specified by a pointer. 6.3.3 Assignment

The assignment operator, :=, performs an inverse operation to deconstruction. It satisfies the equivalence _{a a:=f x j f x for any address a, function f, and data x. It is also dyadic in all arities. Intuitively this relationship means that whereas deconstruction retrieves the value from a field in a structure, assignment stores a value in it. Fields in the result that aren’t specifically assigned by this operation inherit their values from the argument x. If b were an address different from a, then} b a:=f x would be the same as ~b x. This condition defies a simple rigorous characterization, but the following examples should make it clear.

Usage The address in an expression a:=f x can refer to a single field or a tuple of fields in the 2 argument x. In the latter case, the function f should return a tuple of a compatible form. $ fun --m="&h:=c! <'a',b>" --c %sL <'c',b> $ fun --m="(&h,&th):=~&thPhX <'a',b>" --c %sL <'b',a> fflAs the second example above shows, multiple fields can be referenced or inter- changed by an assignment without interference, provided their destinations don’t overlap.

An optional pointer expression s may be supplied as a suffix, with the syntax :=s. The suffix can be a pointer or a pseudo-pointer, but it must be given by a literal pointer constant rather than a symbolic name. The suffix is distinct from the operands and may be used in any arity. However, when a suffix is used in the prefix or infix arities, as in :=sf or a:=sf, and the right operand f begins with alphabetic character, f must be parenthesized to distinguish it from a suffix. In fact, any right operand to an assignment with or without a suffix must be parenthesized if it begins with an alphabetic character. The purpose of the suffix is to specify a postprocessor. An expression a:=s f with a suffix s is equivalent to -_&s,a:=f- or &s+ a:=f. This feature is a matter of convenience because assignments are almost always composed with deconstructors or pseudo-pointers in practice, as a regular user of the language will discover. Non-mutability The idea of storage is non-mutable as always. If x represents a store, then a:=f is a function that returns a new store differing from x at location a. Evaluating this function has no effect on the interpretation of x itself, as this example shows.

$ fun --m="x=<1> y=(&h:=2! x) z=(x,y)" --c %nLW,z (<1>,<2>) 2 If you’re trying these examples, be sure to execute set +H first to suppress interpretation of the exclamation point by the bash command line interpreter. 203

The original value of x is retained in z despite the definition of y as x with a reassigned head. Growing a new field

In order for the above equivalence to hold without exception, assignment to a field that doesn’t exist in the argument causes it to grow one rather than causing an invalid decon- struction. For example, an attempt to retrieve the head of the tail of a list with only one item causes an invalid deconstruction, as expected, $ fun --m="_{&th <1>" --c %n fun:command-line: invalid deconstruction but retrieving that of a list in which it has been assigned doesn’t. $ fun --m="}&th &th:=2! <1>" --c %n 2 The assignment to the second position in the list either overwrites the item stored there if it exists (in a non-mutable sense) or creates a new one if it doesn’t. $ fun --m="&th:=2! <1>" --c %nL <1,2>

It could also happen that other fields need to be created in order to reach the one being assigned. In that case, the new fields are filled with empty values. $ fun --m="&tth:=2! <1>" --c %nL <1,0,2> It is the user’s responsibility to ensure that fields created in this way are semantically meaningful and well typed. $ fun --m="&tth:=2.! <1.>" --c %eL fun: writing core warning: can’t display as indicated type; core dumped An empty value is not well typed in a list of floating point numbers.

Manual override Assignment can be used to override the usual initialization function for a record and set the value of a field "by hand". (See Section 4.2.3 for more about initialization functions in records.) A simple illustration is a record r with two natural type fields u and w, wherein w is meant track the value of u and double it. r :: u %n w %n ~u.&NiC By default, this mechanism works as expected.

$ fun --m="r::u %n w %n _{u.&NiC x=_r%I u:=3! r[u: 1]" -c %b false For this reason, the updated record will not be cast to the type _r. $ fun --m="r::u %n w %n} u.&NiC x= u:=3! r[u: 1]" --c _r fun: writing core warning: can’t display as indicated type; core dumped The badly typed record was displayable in previous examples only by the _r%P function, which doesn’t check the validity of its argument.

6.3.4 The dot The dot operator has two unrelated meanings, one for relative addressing, making it topical for this section, and the other for lambda abstraction. The operator allows either an infix or a postfix arity. The infix usage pertains to relative addressing, and the postfix usage to lambda abstraction. Relative addressing

An expression of the form a.b with pointers a and b describes the address b relative to a. Semantically the dot operator is equivalent to the P pointer constructor (pages 63 and 79), but the latter appears only in literal pointer constants, whereas the dot operator accommodates arbitrary expressions involving literal or symbolic names. In many cases, the deconstruction of a value x by a relative address _{a.b could also be accomplished by first extracting the field a and then the field b from it, as in} b ~a x. In these cases, the dot notation serves only as a more concise and readable alternative, particularly for record field identifiers (see page 153 for an example).

Lambda abstraction An alternative to the use of combinators to specify functions is by lambda abstraction, so called because its traditional notation is [U+02D8]x: f.x/, where x is a dummy variable and f.x/ is an expression involving x. This idea has a well established body of theory and convention, to which the current language adheres for the most part. However, the [U+02D8] symbol itself is omitted, because the dot as a postfix operator is sufficiently unambiguous, and dummy variables are enclosed in double quotes to distinguish them from identifiers. Parsing The postfix arity of the dot operator is indicated when it is immediately preceded by an operand and followed by white space, which is then followed by another operand. This last condition is necessary because lambda abstraction is mainly a source level trans- formation. When it is used for lambda abstraction, the dot operator has a lower precedence than function application and any non-aggregate operator except declarations (= and ::). It is also right associative. These conditions imply the standard convention that the body of an abstraction extends to the end of the expression or to the next enclosing parenthesis, comma, or other aggregate operator.

Semantics The function defined by a lambda abstraction "x". f."x"/ is computed by substituting the argument to the function for all free occurrences of "x" in the expression f."x"/ and evaluating the expression. Free occurrences of a variable in the body of a lambda abstraction are usually all oc- currences except in contrived examples to the contrary. Technically a free occurrence of a variable "x" is one that doesn’t appear in any part of a nested lambda abstraction ex- pressed in terms of a variable with the same name (i.e., another "x"). An example of an occurrence that isn’t a free occurrence of "x" is in the expression "x". "x". "x". This expression nevertheless has a well defined meaning, which is 3 the constant function returning the identity function, ~&!. Nested lambda abstractions are ordinarily an elegant specification method for higher order functions that can be more easily readable than the equivalent combinatoric form. 3 With no opportunity for substitution, applying this expression to any argument yields "x"."x", which is the identity function because applying it to any argument yields the argument.

Pattern matching Lambda abstractions can also be expressed in terms of lists or tuples of dummy variables, in any combination and nested to any depth. The syntax for lists and tuples of dummy variables is the same as usual, namely a comma separated sequence enclosed by angle brackets or parentheses. The reason for using a pair of dummy variables would be to express a function that takes a pair of values as an argument and needs to refer to each value individually. When a pair of dummy variables is used, each component of the argument is identified with a distinct variable, and they can appear separately in the expression. For example, a function that concatenates a pair of lists in the reverse order could be expressed as ("x","y"). "y"--"x" When a function is defined as a lambda abstraction with a tuple of dummy variables, it should be applied only to arguments that are tuples with at least as many components, or else an exception may be raised due to an invalid deconstruction. Similarly, a list of dummy variables in the definition means that the function should be applied only to lists with at least one item for each dummy variable. For nested lists or tuples, each component of the argument should match the arity or length of the corresponding component in the nested list or tuple of dummy variables. See page 162 for a related discussion. Repeating a dummy variable within the same pattern, as in ("x","x"). "x", is 4 allowed but has no special significance. There is nothing to compel this function to be applied only to pairs of equal values. The component of the argument to which a repeated dummy variable refers in the body of the abstraction is unspecified. Note that this example differs from the case of a nested lambda abstraction, wherein repeated variables have a standard interpretation as discussed above.

6.4 Sequencing operations

Five operators pertain feeding the output from one function into another or feeding it back to the same one. They are listed in Table 6.4. There are two for iteration and three for composition. 4 An alternative semantics considered and rejected in the design of Ursala would allow a pattern with repetitions to express a partial function restricted to a domain matching the pattern. This semantics would be useful only in the context of a function defined by cases via multiple partial functions, which raises various practical and theoretical issues.

6.4.1 Algebraic properties These operators are designed with various algebraic properties to be as convenient as pos- sible in typical usage. fflThe iteration combinator → allows all four arities and is fully dyadic.

6.4.2 Semantics The semantics of these operators are as simple as they look, and require no lengthy dis- course. fflThe fixed point iterator, [U+02C6]=, applies a function to the original argument, then applies the function again to the result, and so on, until two consecutive results are equal. 5 The last result obtained is the one returned. Non-termination is a possibility. fflThe iteration combinator in a function p→f similarly applies the function f repeat- edly, but uses a different stopping criterion. The predicate p is applied to each result from f, and the first result for which p is false is returned. The result may also be the original argument if p isn’t satisfied by it, in which case f is never evaluated.

6.4.3 Suffixes All of the operators in Table 6.4 can be used with a suffix. The suffix can be used in any arity the operators allow. There are three different conventions followed be these operators regarding suffixes. fflThe iterations → and [U+02C6]= allow a literal pointer constant as a suffix. fflThe fixed point iterator [U+02C6]= also allows the = character in a suffix. fflThe composition operators + and ; can take a suffix consisting of any sequence of the characters *, =, ., and $.

Iteration postprocessors A pointer constant s serves as a postprocessor to the iteration operators, similarly to its use by the assignment operator. That is, p→sf is equivalent to _{&s+ p→f, and f[U+02C6]=s is equivalent to} &s+ f[U+02C6]=. The right operand to → in its infix or prefix arities must be parenthesized to distinguish it from a suffix if it begins with an alphabetic character. For the fixed point iterator [U+02C6]=, a suffix of = can be used, as in [U+02C6]==, either with or without a pointer constant. The effect of the = is to generalize the stopping criterion to compare each newly computed result with every previous result, rather than comparing it only to its immediate predecessor. This criterion makes the computation more costly both in time and memory usage, but will allow it to terminate in cases of oscillation, where the alternative wouldn’t.

Embellishments to composition The suffixes to the composition operators alter the semantics of the function they would normally construct in the following ways. fflThe * makes the function apply to all items of a list. fflThe = composes the function with a list flattening postprocessor. fflThe $ makes the function apply to both sides of a pair. fflThe . makes the function transform a list by deleting the items that falsify it.

These explanations may be supplemented by some examples. $ fun --m="_&h+*&t <'ab',cd,ef,gh>" --c bdfh $ fun --m="_&t+=&t <'ab',cd,ef,gh>" --c efgh $ fun --m="_&h+$&t (<'ab',cd>,<'ef',gh>)" --c (cd,gh) $ fun --m="_&t+.&t <'abc',de,fgh,ij>" --c <'abc',fgh> 209

6.5 Conditional forms

Several forms of non-strict evaluation of functions conditioned on a predicate are afforded by the operators listed in Table 6.5. These operators have only postfix and solo arities, and therefore are not dyadic, but they share the algebraic property (p?)(f,g) j (?)(p,f,g) where these expressions are fully parenthesized to emphasize the arity. More frequent idiomatic usages are p?/f g and ?(p,~&/f g), etcetera, with line breaks per stylistic convention.

6.5.1 Semantics These operators are defined in terms of the virtual machine’s conditional combinator, a second order function that takes a predicate p and two functions f and g to a function that evaluates to f or g depending on the predicate. [U+00E6] f(x) if p(x) is non-empty conditional(p,f,g) x D g(x) otherwise The non-strict semantics means the function not chosen is not evaluated and therefore un- able to raise an exception. This behavior is similar to the if:::then:::else statement found in most languages. fflThe ? operator in a function p?(f,g) directly corresponds to the conditional combinator with a predicate p and functions f and g.

6.5.2 Suffixes The conditional operators listed in Table 6.5 all allow pointer expressions as suffixes, and the [U+02C6]? additionally allows suffixes containing the characters =, $, and <. Equality and membership suffixes

The [U+02C6]? operator with a suffix = is a recursive form of the ?= operator. That is, the func- tion p[U+02C6]?=(f,g) is equivalent to refer p?=(f,g). Similarly, p[U+02C6]?<(f,g) is equiv- alent to the function refer p?<(f,g), and p[U+02C6]?$(f,g) is equivalent to the function refer p?$(f,g). The =, $ and < characters are mutually exclusive in a suffix. The effect of using more than one together is unspecified. Pointer suffixes The pointer expression s in a function p?s(f,g) serves as a preprocessor to the predicate p, making the function equivalent to (p+ _{&s)?(f,g). The expression s can be a pseudo-pointer but must be a literal constant. Note that only the predicate p is composed with} &s, not the functions f and g. For the ?= and ?< operators, the pointer expression is composed with the implied pred- icate. Hence, x?=s(f,g) is equivalent to (_&E/x+ &s)?(f,g) and x?<s(f,g) is equivalent to (_&w\x+ &s)?(f,g). (See page 78 for a reminder about the equality and membership pseudo-pointers E and w.)

Combined suffixes A pointer expression and one of < or = may be used together in the same suffix of the [U+02C6]? operator, as in p[U+02C6]?=s(f,g) or p[U+02C6]?<s(f,g), with the obvious interpretation as a recursive form of one of the above operators with a pointer suffix. 6 see page 78 for a discussion of equality

A selection of operators for constructing predicates useful for conditional forms among other things is shown in Table 6.6. There are operators for testing of equality and mem- bership in normal and negated forms, and for several kinds of functional conjunction and disjunction. 6.6.1 Boolean operators

The boolean operators in Table 6.6 are &&, ||, !|, [U+02C6]&, and [U+02C6]!. Algebraically, they allow all four arities and are fully dyadic. Semantically, they are second order functions that take functions rather than data values as their operands, and their results are functions. The functions they return have a non-strict semantics. There are currently no suffixes defined for these operators. Non-strictness The non-strict semantics means that in their infix usages, the right operand isn’t evaluated in cases where the logical value of the result is determined by the left. A prefix usage such as &&q represents a function that needs to be applied to a predicate p, and will then construct a predicate equivalent to the infix form p&&q. The resulting predicate therefore evaluates p first and then q only if necessary. Similar conventions apply to other arities.

Semantics The meanings of these operators can be summarized as follows. fflA function f&&g applies f to the argument, and returns an empty value iff the re- sult from f is empty, but otherwise returns the result obtained by applying g to the argument. fflA function f||g applies f to the argument, and returns the result from f if it is non-empty, but otherwise returns the result of applying g to the argument. Although

The refer combinator is used in recursively defined functions. An expression of the form (refer f) x evaluates to f _{&J(f,x). See pages 44 and 72 for further explanations. The aggregate operators -&f,g&-, -|f,g|-, and -!f,g!- have a similar seman- tics to the first three of these operators but allow arbitrarily many operands. See page 191 for more information. 6.6.2 Comparison and membership operators The operators ==,} =, -=, and ~< from Table 6.6 pertain respectively to equality, inequal- ity, membership, and non-membership. These operators have no suffixes. They allow all four arities but are dyadic only in their postfix arity. For their prefix arities, they share the algebraic property f; ==x j f==x but in their solo arities they are only first order functions taking pairs of data to boolean values.

Four operators shown in Table 6.7 are useful for access and control of library functions. Library functions can be those that are implemented in other languages and linked into the virtual machine such as the linear algebra and floating point math libraries, or they can be implemented in virtual code stored in .avm library files that are user defined or packaged with the compiler. The dash operator, -, is useful for the latter and the other operators are useful for the former. 6.7.1 The dash

This operator allows only an infix arity and has a higher precedence than most other oper- ators. The left operand should be of a type t%m for some type t, which is to say a list of assignments of strings to instances of t, and the right operand must be an identifier. Syntax The dash operator is implemented partly as a source level transformation that allows it to have an unusual syntax. The identifier that is its right operand need not be bound to a value by a declaration elsewhere in the source. Rather, it should be identical to some string associated with an item of the left operand. The value of an expression foo-bar is the value associated with the string bar in the list foo. Although bar is a string, it is not quoted when used as the right operand to a dash operator.

a more useful application is to have a symbolic name as the left operand representing a previously compiled library module. Any source text containing #library+ directives generates a library file with a suffix of .avm when compiled, that can be mentioned on the command line during a subsequent compilation. Doing so causes the name of the file (without the .avm suffix) to be avail- able as a predeclared identifier whose value is the list of assignments of strings to values declared in the library. A usage like lib-symbol allows an externally compiled symbol from a library named lib.avm to be used locally, provided that file name is mentioned on the command line during compilation. The #import directive serves a related purpose by causing all symbols defined in a library to be accessible as if they were locally declared. However, the dash operator is helpful when an external symbol has the same name as a locally declared symbol, because it provides a mechanism to distinguish them. Type expressions

Type expressions associated with record declarations in modules are handled specially by the dash operator. The compiler uses a compressed format for type expressions to save space when storing them in library files. The dash operator takes this format into account. When any identifier beginning with an underscore is used as the right operand to a dash operator, and its value is detected to be that of a compressed type expression, the value is uncompressed automatically. This effect is normally not noticeable unless the module containing a type expression is accessed by other means than the dash operator in an application that makes direct use of type expressions. Compressed libraries If a file containing #library+ directives is compiled with the --archive command line option, the file is written in a compressed format. This compression is optional and is orthogonal to that of type expressions mentioned above. The dash operator automatically detects whether its left operand is a compressed mod- ule and accesses it transparently. Operating on compressed modules otherwise requires un- compressing them explicitly, which can be performed by the function %QI. See page 132 for an example.

6.7.2 Library invocation operators The other kind of library functions are those that are written in C or Fortran and are invoked directly by the virtual machine. The virtual machine code for a call to this kind of library function is essentially a stub library(hlibrary namei,hfunction namei)

containing the name of the library and the function as character strings, which are looked up at run time by an interpreter. The available libraries and function names are site specific, 215

but can be viewed by executing the shell command $ fun --help library as shown in Listing 1.10 on page 46, and as documented in the avram reference manual. Aside from invoking a library function by the library combinator explicitly as shown above, there are three operators intended to make it more convenient as shown in Table 6.7, which are the .. (elipses), .!, and .| operators.

Syntax Algebraically the library name is the left operand and the function name is the suffix for each of these operators. The right operand, if any, can be any expression representing a function. All three operators allow solo and postfix usage. The .! and .| operators allow infix usage and are postfix dyadic. Syntactically the library name must be an identifier, which needn’t be declared any- where else because it is literally translated to a string by a source transformation, similarly to the right operand of a dash operator as explained above. Anything other than an identi- fier as the left operand to one of these operators causes a compile time exception. The function name in the suffix may contain digits, which are not normally valid in identifiers, as well as letters and underscores. Both the library and function names can be recognizably truncated or even omitted where there is no ambiguity (either because a function names is unique across libraries, or because a library has only one function). Semantics

The operators differ in their semantics, as explained below. The elipses The .. allows only a postfix or solo arity, with the solo arity corresponding to the case where the library name is omitted. It is translated directly to the library combinator mentioned above with an attempt to complete any truncated library or function names at compile time. fflIf there isn’t a unique match found for either the library or the function name in the postfix usage lib..func, it is taken literally (even if no such function or library exists on the compile time platform).

used in place of an unavailable library function. The determination of availability is made at compile time based on the virtual machine configuration on the compilation platform. fflAn expression of the form lib.!func f evaluates to f if no unique match to the library function is found, but it evaluates to lib..func otherwise. fflA solo usage of the form .!func f behaves analogously, but obviously may fail to find a unique match for the library function in some cases where the usage above would not. fflConsistently with the dyadic property and solo semantics, an expression .!func or lib.!func by itself evaluates either to the identity function or to a constant function returning lib..func, depending on whether a matching library function is found during compilation. fflIn any case, no compile time exception is raised, but run time errors are possible if a library function present on the compile time platform is absent from the target.

Run time replacement The .| operator provides a way for a replacement function to be used in place of an unavailable library function with the determination of availability made at run time. fflAn expression of the form lib.|func f represents a function that performs a run time check for the availability of a function named func in a library named lib. If such a function exists and is unique, it is applied to the argument, but otherwise the function f is applied to the argument. fflA solo usage of the form .|func f behaves analogously, but searches every virtual machine library for a function named func.

6.8 Recursion combinators Four operators shown in Table 6.8 are grouped together loosely on the basis that they abstract common patterns of recursion, particularly over lists and trees.

6.8.2 Recursion over trees The tree traversal operator, [U+02C6], is a generalization of the tree folding pseudo-pointer, o, introduced on page 70, that allows greater flexibility in the handling of empty subtrees, and accommodates arbitrary functional expressions as operands rather than literal pointer constants. It is useful for performing bottom-up calculations on trees. The operator allows all arities and is prefix dyadic. The solo usage *[U+02C6] f is equivalent to the postfix usage f[U+02C6]. A function of the form f*[U+02C6]k operates on a tree according to the following recurrence.

The remaining two operators in Table 6.8 construct functions operating on lists according to patterns of recursion sometimes known as folding or reduction. A typical application for these operators is summing over a list of numbers. 218

Folding The folding operator, ⇒ takes a function operating on pairs of values and an optional constant as a vacuous case result to a function that operates on a list of values by nested applications of the function. The operator can be used in any of four arities, with the infix form allowing a user defined vacuous case. It is prefix and solo dyadic, but the postfix form is without a vacuous case and consequently has a different semantics. There are currently no suffixes defined for it. A function expressed as f⇒k, which is equivalent to .⇒k/ f and .⇒/ .f;k/ by the dyadic properties, applies the following recurrence to a list. .f⇒k/ <> D k .f⇒k/ h:t D f.h;.f⇒k/ t/ If f were addition and k were 0, this function would compute a cumulative sum. Cumula- tive products might conventionally have a vacuous case of 1. A function expressed by the postfix form f⇒ is evaluated according to this recurrence.

The reduction operator, :-, performs a similar operation to folding, but the nesting of function applications follows a different pattern, and the vacuous case result doesn’t enter into the calculation unnecessarily. The difference is illustrated by these two examples, which fold and reduce the operation of concatenation followed by parenthesizing with an empty vacuous case. $ fun --m="-(--,--),---⇒'' _{&iNCS abcdefgh" --c (a(b(c(d(e(f(g(h)))))))) $ fun --m="-(--,--),---:-'} &iNCS 'abcdefgh" --c The original motivation for the reduction operator as opposed to folding was to avoid imposing unnecessary serialization on the computation. The current virtual machine im- plementation does not exploit this capability. Algebraically the reduction operator has all four arities, no suffixes, and is fully dyadic (i.e., the vacuous case must always be specified). Semantically it may be regarded either as folding with an unspecified order of evaluation, limiting it to associative operations, or can have a formal specification consistent with above example, as documented for the 219

6.9 List transformations induced by predicates

Some operators shown in Table 6.9 are designed to support frequently needed list calcula- tions such as sorting, searching, and partitioning. A common feature of these operators is that they specify a function by a predicate or a boolean valued binary relation. Except as noted, all of these operators apply equally well to lists and sets. 6.9.1 Searching and sorting

Searching a list for an extreme value can be done by either of two operators, $[U+02C6] and $-, while sorting a list can be done by the -< operator. Searching is semantically equivalent to sorting followed by extracting the head of the sorted list, but is more efficient, requir- ing only linear time. Each of these operators requires a binary relational predicate and optionally a pointer or pseudo-pointer identifying a field on which to base the comparison. A binary relational predicate p for these purposes is any function that takes a pair of values as an argument and returns a non-empty result if and only if the left value pre- cedes the right according to some transitive relation. That is, p.x;y/ is true if and only if x v y for a relation v. Examples of suitable relations are [U+02C7] on floating point numbers as computed by fleq from the flo library, and alphabetic precedence on character strings as computed by lleq from the standard library, std.avm. The example nleq used in Table 6.9 is the partial order relation on natural numbers. The pointer operand f can be any literal or symbolic expression evaluating to a pointer, including literals such as &thl or &hthPX, field identifiers such as foobar, or combi- nations of them such as foobar.(&h:&tt). Pseudo-pointers are also acceptable, such as &zl or foo.&iNC. 7 For a reduction combinator defined ab initio as a one-liner, see the file com.fun in the compiler source directory.

Semantics The maximizing and minimizing functions cause an exception when applied to empty lists, but sorting an empty list is acceptable. fflThe maximizing function p$[U+02C6]f applied to a list <x :::x > returns the item x for 0 n i which _{f x is the maximum with respect to the relation p. i fflThe minimizing function p$-f applied to a list <x :::x > returns the item x for 0 n i which} f x is the minimum with respect to the relation p. i fflThe sorting function p-<f applied to a list <x :::x > returns a permutation of 0 n the list in which ~f of each item precedes that of its successor with respect to the predicate p.

Algebraic properties None of these operators is dyadic, but they can be used in all four arities and have similar algebraic properties

Postfix usage The postfix form of any of these operators, such as p-<, p$-, or p$[U+02C6], is semantically equivalent to the infix form with a right operand of the identity pointer, p-<&, etcetera. That means the whole items of the argument list are compared to one another by p rather than a particular field f thereof. Solo usage The solo usages (-<) p, ($[U+02C6]) p, and ($-) p are equivalent to the respec- tive postfix usages p-<, p$[U+02C6], and p$-. That is, they imply an identity pointer in place of the right operand and base the comparison on whole items of the list.

Prefix usage The prefix form of the sorting operator, -<f is equivalent to lleq-<f, where lleq is the lexical total order relation on character strings, and also the relation used by the compiler to represent sets as ordered lists. The prefix forms of the maximizing and minimizing operators $[U+02C6]f and $-f are equiv- alent to leql$[U+02C6]f and leql$-f respectively, where leql is the relational predicate that tests whether one list is less or equal to another in length. The standard library defines leql as _{&alZ[U+02C6]!}&arPfabt2RB. Suffixes

Each of these operators allows a suffix, which can be any literal pointer or pseudo-pointer constant to be used as a postprocessor. That is, p-<sf with a pointer expression s is equivalent to ~&s+ p-<f. Consequently, if the right operand f to a sorting or searching operator begins with an alphabetic character, it must be parenthesized to distinguish it from a suffix.

6.9.2 Filtering The operation of filtering a list is that of transforming it to a sublist of itself wherein every item that falsifies a given predicate is deleted. Some operators previously introduced, such as composition and binary to unary combinators, can specify filtering functions by way of their suffixes, and filtering can also be done by the pseudo-pointers F, K16, and K17, but there are two operators intended specifically for filtering. fflThe filter operator * _{takes a predicate as an operand, and constructs a function that filters a list by deleting items that falsify the predicate (i.e., for which the predicate has an empty value). fflThe distributing filter operator} | takes a binary relational predicate p as an operand (not necessarily transitive) and constructs a function that takes a pair .a;<x :::x >/ 0 n to the sublist of the right argument containing only those x for which p.a;x / is i i non-empty. One way of thinking about these operators is that * _{is used when the filtering criterion can be hard coded and} | is used when it’s partly data dependent.

Usage These operators can be used as follows. fflThe _{| operator is usable in any arity, and *} can be infix, postfix, or solo. fflIn the prefix and infix usages, the right operand is a pointer expression. fflBoth operators allow a pointer constant as a suffix, which serves as a postprocessor. fflThe right operand, if any, must be parenthesized to distinguish it from a suffix if it begins with an alphabetic character. Algebraic properties Neither operator is dyadic, but the following algebraic properties hold, where p is a pred- icate and f is a pointer expression. fflThe prefix usage of distributing bipartition implies a predicate of equality. _{|f j (==)}|f

Semantics It is possible to supplement the informal descriptions above with rigorous definitions of these operators in various ways. The _{in postfix and solo forms without a suffix directly corresponds to the virtual machine’s filter combinator, as documented in the avram reference manual. Alternatively, we may define p}sf j _{&s+ = &&}&iNC p+ _{f p}|sf j _&s+ &rS+ p_{f+ -* using operators defined elsewhere in this chapter, where p is a predicate, f is a pointer expression and s is a literal pointer or pseudo-pointer constant. Definitions for other arities are implied by the algebraic properties. As indicated by these relationships, there is a minor point of difference between the usage of the pointer operand f with these operators and the sorting and searching operators described previously. In the present case,} f is applied to a pair of values, and its result is fed to p. In the previous case, ~f is applied only to items of a list individually, and the pairs of its results are fed to p. The latter is more appropriate when p is a relational predicate, as with sorting and searching, whereas the present alternative is more general.

6.9.3 Bipartitioning Bipartitioning is the operation of transforming a set S to a pair of subsets .L;R/ such that L"R is empty and L[R D S. It can also apply where S is a list, in which case the items of L and R preserve their order and multiplicity. The bipartition operator != shown in Table 6.9 takes a predicate p that is applicable to elements of a list or set S and constructs a function that bipartitions S into .L;R/ such that p is true of all elements of L and false for all elements of R. This operator is documented further below, along with several related operators *|, -_{, and} - also shown in Table 6.9. Pseudo-pointers with similar semantics are documented in Section 2.5.2.

Bipartition The != operator can be used in any of prefix, infix, postfix, and solo arities. The left operand, if any, is a predicate and the right operand, if any, is a pointer or pseudo-pointer expression. The operator may also have a literal pointer constant as a suffix. If there is a right operand beginning with an alphabetic character, it must be parenthesized to distinguish it from a suffix.

Algebraic properties The following algebraic properties hold, where p is a predicate and f is a pointer expression. fflThe postfix usage implies the identity as a pointer operand. p!= j p!=&

Semantics It is straightforward to give a formal semantics for the postfix arity (and the others by implication) in terms of the _{&j pseudo-pointer for set difference and the filter combinator. .p!=/ x D ..!=/ p/ x D (.p*}/ x,_{&j/x .p*}/ x) The optional suffix serves as a postprocessor in any arity. For a pointer constant s, any function of the form p!=sf, !=sf, p!=s, or !=s. is equivalent to _{&s+ g, where g is given by p!=f, !=f, p!=, or != respectively. Distributing bipartition The distributing bipartition operator | is used to bipartition a list according to a binary relation. A function p|f takes pair of (x,<y :::y >) as an argument, and it returns 0 n a pair of lists (<y :::>,<y :::>) collectively containing all of the items y through y . i j 0 n For all y in the left side of the result, p} f .x;y / has a non-empty value (using the i i same x in every case). For all y in the right side, p _{f .x;y / has an empty value. j j This operator has the same algebraic properties and arities as the bipartition operator discussed above, and makes similar use of an optional pointer expression as a suffix. Its semantics is given by p*|sf j} &s+ ~&brS+ p!=f+ -* where the suffix s is a literal pointer constant and f is any pointer expression, possibly parenthesized.

Ordered bipartition The two operators, - _and -, are used for bipartitioning a list S based on a predicate p into a pair of lists .L;R/ such that S is the concatenation of L and R. fflA function p- _{applied to S will construct .L;R/ with L as the maximal prefix of S whose items all satisfy p. fflA function p}- will make R the maximal suffix whose items all satisfy p. In operational terms, p- _{scans forward through a list from the head and stops at the first item for which p is false, whereas p}- scans backwards from the end. The results may or may not coincide with each other or with p!= depending on repetitions in S and the semantics of p. These operators allow solo usages, with .-_{/ p equivalent to p-}, and ._{-/ p equiv- alent to p}-, and they each allow a pointer suffix to specify a postprocessor.

6.9.4 Partitioning The partition operator, |=, shown in Table 6.9 can be used to identify equivalence classes of items in a list or a set according to any given equivalence relation, or by the transitive closure of any given relation. This operator is very expressive, for example by allowing a function locating clusters or connected components in a graph to be expressed simply in terms of a suitable distance metric or adjacency relation.

Usage The partition operator can be used in prefix, postfix, infix, and solo arities. In the prefix and infix arities, the right operand is a pointer expression. In the postfix and infix arities, the left operand is a binary relational predicate. There may also be a a suffix in any arity consisting of a sequence of the characters =, *, or a literal pointer constant. The right operand, if any, must be parenthesized to distinguish it from a suffix if it begins with an alphabetic character. Algebraic properties The operator is not dyadic, but has these properties, which also hold when it has a suffix.

The semantics for other arities follows from the algebraic properties above. The coupling operator, [U+02C6], is introduced subsequently in this chapter. The subexpression p_{||/h is parsed as ((p}|)|)/h to use a distributing filter within a distributing bipartition as the left operand of a binary to unary operator. fflIf there is a suffix that includes the = character (e.g. if the operator is of the form |==), the symmetric closure of the predicate p is implied, and the above recurrence holds with -!p,p+_&rlX!-| in place of p_{|. fflA function of the form p|=s, p|==s, p|=s, or p|==s, where s is a literal pointer or pseudo-pointer constant, is semantically equivalent to a function} &s+ g, where g is of the form p|=, p|==, p|=, or p|== respectively. fflIf there is not a suffix containing the *, the above recurrence accurately describes the semantics only if p is transitive (i.e., if p.x;y/ and p.y;z/ implies p.x;z/). If there is a suffix containing *, the recurrence holds regardless of transitivity. A more efficient algorithm is used for partitioning when the relation p is transitive, but unspecified results are obtained if this algorithm is used when p is not transitive. If p is not transitive, it is the user’s responsibility to specify the * in a suffix. An example of a relation that is not transitive is intersection between sets.

6.10 Concurrent forms Whatever the merits of functional programming for concurrent applications, the operators in Table 6.10 are variations on the theme of computations with obvious parallel evaluation

strategies. Although the virtual machine makes no use of parallelism in its present imple- mentation, these operators are convenient as programming constructs for their own sake. They fall broadly into the classifications of mapping operators and coupling operators, which are considered separately in this section.

6.10.1 Mapping operators The first four operators in Table 6.10 involve making a list of outputs from a function by applying the function to every item of an input list. They can be used either in solo arity, or as a postfix operator with a function as an operand, and they share the algebraic property f* j .*/ f. They also have suffixes usable in various ways. Map The simplest and most frequently used mapping operator, *, satisfies this recurrence when used without a suffix.

Map to both The _{* operator works like the * operator except that it constructs a function that applies to a pair of lists rather than a single list. The exact relationship is .f*}/ .x;y/ j ..f*/ x;.f*/ y/ where f is a function and x and y are lists. This operator also allows a pointer suffix, that serves as a preprocessor That is,

Flattening map The = operator behaves like the * with a list flattening postprocessor. The function f in an expression f= should return a list. After making a list of the results, which will be a list of lists, the flattening map operation forms their cumulative concatenation. Formally, the relationship is f*= j _{&L+ f* in terms of the list flattening pseudo-pointer} &L explained on page 65, which could also be defined as --:-<> with operators introduced in this chapter. The flattening map operator allows arbitrarily many more * and = characters to be appended as suffixes. fflEach * character in a suffix indicates a nested map. That is, f*=* is equivalent to .f*=/, where the latter * is parsed as the map operator, f=* is equivalent to ..f=//, and so on.

6.10.2 Coupling operators Whereas the mapping operators are concerned with applying the same function to multiple arguments, most of the remaining operators in Table 6.10 involve concurrently applying multiple functions to the same argument.

Apply to both The _{~ operator allows postfix and solo arities with no suffixes. In the postfix arity, its operand is a function, and the solo arity satisfies .}~/ f j f_{~. This operator corresponds to what is called the fan combinator in the avram reference manual. Given a function f, it constructs a function that applies to a pair of values and returns a pair of values. Each side of the output pair is computed by applying f to the corresponding side of the input pair. .f}~/ .x;y/ j .f x;f y/ Normally a function of the form f_{~ will raise an exception with a diagnostic mes- sage of "invalid deconstruction" when applied to an empty argument, but if the function f is of the form} &p and p is a pointer, certain code optimizations might apply. $ fun --main="_&~" --decompile main = field & $ fun --m="_&rlX~" --d main = field((((0,&),(&,0)),0),(0,0 The optimization in the first example is a refinement rather than an equivalent semantics, whereby the function will map an empty input to an empty output rather than raising an exception. The optimization in the second example uses a single pointer instead of the fan combinator. This operator also allows a pointer suffix, that serves as a preprocessor That is,

The most frequently used coupling combinator is [U+02C6], which allows infix, postfix, and solo arities, and a pointer suffix as a postprocessor. fflIn the solo arity, [U+02C6] is a function that takes a pair of functions as an argument and returns a function as a result. fflIn the infix arity, the [U+02C6] operator takes a function as its left operand and a pair of functions as its right operand, with the algebraic property f[U+02C6].g;h/ j f+ .[U+02C6]/.g;h/. fflThe operator is postfix dyadic, so the postfix usage is implied by the infix.

The semantics for the solo arity, which implies the other two, is given by ..[U+02C6]/ .f;g// x j .f x;g x/ where f and g are functions. That is, a function [U+02C6].f;g/ returns a pair whose left side is computed by applying f to the argument, and whose right side is computed by applying g to the argument. This operation corresponds to the virtual machine’s couple combinator. The interpretation of a pointer suffix s varies depending on the arity. fflIn the solo arity, the suffix acts as a postprocessor to the function that is constructed. [U+02C6]s.f;g/ j ~&s+ [U+02C6].f;g/

One to each A further variation on the couple operator is [U+02C6]|. The semantics in the infix arity with a pointer suffix s is .f[U+02C6]|s.g;h// .x;y/ j f _{&s .g x;h y/ where f, g, and h are functions. The solo arity satisfies ..[U+02C6]|s/ .g;h// .x;y/ j} &s .g x;h y/ and the operator is postfix dyadic. If a function of the form f[U+02C6]|s.g;h/ is applied to an empty value instead of a pair .x;y/, an exception will be raised with "invalid deconstruction" reported as a diagnostic. Otherwise, one function is applied to each side of the pair, as the above equivalence indicates. In addition to a pointer suffix s, this operator may be used with any combination of suffixes , =, and _{. The simplest way of understanding and remembering their effects is by these identities, f[U+02C6]|*s.g;h/ j .f}/[U+02C6]|s.g;h/ f[U+02C6]|s.g;h/ j .f_{~/[U+02C6]|s.g;h/ f[U+02C6]|=s.g;h/ j .f=/[U+02C6]|s.g;h/ which is to say that they can be envisioned as making the left function mapped, fanned, or flat mapped. These suffixes may also be used in the solo form, wherein they act on the implied identity function instead of a left operand. The flattening suffix, =, can be used by itself, and will have the effect of composing the list flattening function} &L with the left operand. Arbitrarily long sequences of these suffixes are also allowed, and are applied in order, as in this example.

Usage A function of the form f$ with a record mnemonic f is analogous to a function g[U+02C6] for a function g operating on a pair of values. Whereas the latter is meaningful when applied to a pair of functions (as explained in connection with the [U+02C6] operator), the former applies to a record of functions. Hence, the typical usage is in an expression of the form hrecord mnemonici$[ hfield identifieri: hfunctioni, : : : hfield identifieri: hfunctioni] which is parsed as .hrecord mnemonici$/[:::]. The record mnemonic and field iden- tifiers should match those of a record type previously declared with the :: operator, as explained in Section 4.2. fflThe fields in a record valued function can be specified in any order or omitted, but at least one must be included. fflThe effect of repeating a field in the same expression is unspecified, but in the current implementation one or another will take precedence. fflThe technique of associating a tuple of values with a tuple of fields is not valid for record valued functions, even though it ordinarily can be used to express record in- stances. For example, the subexpression [a: fa,b: fb] should not be abbrevi- ated to [(a,b): (fa,fb)] in a record valued function.

Semantics The $ operator can be understood by this equivalence. ..f$/[a : g , ::: a : g ]/ x j f[a : g .x/, ::: a : g .x/] 0 0 n n 0 0 n n That is, .f$/[a : g , ::: a : g ] represents a function that can be applied to an ar- 0 0 n n gument x to return a record of the type indicated by f. To compute this function, each g i is applied to the argument, and its result is stored in the field with address a in the manner i portrayed in Figure 5.3 (page 188). The record of function results is then initialized by the record initializing function f. At this stage, any user defined verification or initializa- tion specified in the record declaration is automatically performed, even if it overrules the function results.

Suffixes Not every field defined when the record is declared has to be specified in a record valued function. This feature reduces clutter and allows easier code maintenance if more 8 fields are added to a record in the course of an upgrade. The handling of omitted fields depends on the optional pointer suffix to the $ operator. With no suffix, the default behavior of the $ is to assign an empty value to an omitted field, but for a typed or smart record, the empty fields are automatically initialized by the record initializing function f. If there is a pointer or pseudo-pointer suffix s appended to the $ operator, then any omitted field a is assigned a value of ~s.a x, where x is the argument to the function. i i Intuitively that means that the unspecified fields in a result can be copied or inherited automatically from a record in the argument. This value may still be subject to change by the record initializing function. By way of an example, a function taking a record of type _foo to a modified record of the same type with most of the fields other than bar unchanged could be expressed as foo$i[bar: g]. This function is almost equivalent to bar:=g using the assign- ment operator (page 202) except that it provides for the record to be reinitialized after the change. Other common usages are $l and $r, for functions that take a pair of a record and something else to a new record by copying mostly from the input record.

6.11 Pattern matching A set of operators relevant to the general theme of pattern matching or transformation is shown in Table 6.11. They are classified in this section as random variate generators, type expression constructors, finite maps, and string handling operators.

6.11.1 Random variate generators An operator in a class by itself is %_{, which is useful for constructing programs with non-deterministic outputs. It can be used in postfix or solo arities, and has the property n%} j .%~/ n. Its operand n is either a natural or a floating point number. 8 If the declaration and use of a record are in separate modules, both may require recompilation even if no source level changes are made to the latter.

6.11.2 Type expression constructors Two operators concerned with type expressions are topical for this section because type instance recognizers are an effective pattern recognition mechanism. Type expressions are a significant topic in themselves, being thoroughly documented in Chapters 3 and 4, but the operators %- and % are included here for completeness and because they have some previously unexplained features.

The % operator The type operator % allows postfix and solo arities, with different meanings depending mainly on the suffix. fflIf there is a suffix containing alphabetic characters, the operator represents a type expression or type induced function in either arity as documented in Chapters 3 and 4. fflIf there is a suffix containing only numeric characters, then the operator represents an exception handler in the solo arity but is undefined in the postfix arity. fflIf there is no suffix, it represents an exception generator in either arity, and has the property f% j .%/ f. The latter two alternatives require further explanation.

Exception handlers An expression of the form %n, where n is a sequence of digits, is a higher order function meant to be applied to a function f. It will return a function g that behaves identically to f unless g is applied to an argument that would cause f to raise an exception. In that case, g will also raise an exception, but the content of the diagnostic message will differ from that which would be reported by f, in that the number n will be appended to it. A simple illustration is given by the following examples. $ fun --m="_{&h <>" --c fun:command-line: invalid deconstruction $ fun --m="(%52} &h) <>" --c fun:command-line: invalid deconstruction 52 $ fun --m="_{&h <'x'>" --c x $ fun --m="(%52} &h) <'x'>" --c x This usage of the operator is intended mainly for debugging applications that are termi- nating ungracefully, by helping to locate the problem. See Section 4.1.2 and particularly page 142 for background and motivation about exception handling.

Exception generators Although exceptions are usually associated with ungraceful termi- nation, there could also be reasons for raising them deliberately in production code. The default case in a -?:::?- cumulative conditional expression wherein the other cases are thought to be exhaustive is one example (page 190). Failure of an assertion is another. An expression of the form % f or f%, where f is a function, represents a function that unconditionally raises an exception. The function f is applied to the argument, execution is either immediately terminated or dropped into an enclosing exception handler, and the result from f is reported in a diagnostic message. Because diagnostic messages are written to the standard error console by the virtual machine, they should normally be lists of character strings (type %sL). fflIf the function f returns something other than a list of character strings and the excep- tion is raised during compilation, the compiler will substitute a diagnostic message of "undiagnosed error". fflIf a badly typed diagnostic is reported in a free standing executable application, the virtual machine may report a diagnostic of "invalid text format" or attempt to display unprintable characters. fflUsers who think it’s worth the effort can throw diagnostics of arbitrary types and catch them using the virtual machine’s guard combinator, provided the latter con- verts them to lists of character strings. This combinator is documented in the avram reference manual. A frequently used idiom is an exception generator made from a function f returning a constant list of a single character string, as in <'game over'>!%. A more helpful alternative if possible is an exception handler that gives some indication of the input that caused the exception, such as % :/bad input was+ %xP, preferably with a more specific printing function than %xP. Confusing effects can occur if the function f in an expression f% raises an exception it- self either because of a programming error or because of a nested % operator. The reported diagnostic will then refer to the exception generator itself rather than the program contain- ing it. Moreover, interaction between the exception generator and exception handlers or guard combinators will be affected because exceptions form a hierarchy of segregated levels. See the avram reference manual for more information.

The %- operator This operator is unusual insofar as it allows only a solo arity, but may have a literal type expression as a suffix. It has the property %-t x j x%t where t is a literal type expression constant or type induced function. It exists to pro- vide a convenient means for general purpose functions to construct type expressions. For example, a user preferring a more verbose programming style might define list_of = %-L

Listing 6.1 decompilation of optimal code generated by <0,1,2,3,4,5,6,7>-$01234567 digitize = # takes a number 0..7 to the corresponding digit conditional( field &, conditional( field(&,0), conditional( field(0,&), conditional( field(0,(&,0)), conditional(field(0,(0,&)),constant '7,constant '3), constant '5), constant '1), conditional( field(0,(&,0)), conditional(field(0,(0,&)),constant '6,constant '2), constant '4)), constant '0)

and thereafter write list_of(my_type) instead of my_type%L. A more practical example is the enum function, which the standard library defines as enum = ~&ddvDlrdPErvPrNCQSL2Vo+ %-U:-0+ %-u* taking any non-empty set to an enumerated type thereof. The pseudo-pointer postproces- sor is a low level optimization to the type expression’s concrete representation, and not presently relevant. See page 172 for motivation.

6.11.3 Reification A finite map is a function whose inputs are expected only to be members of a fixed finite set, usually something small enough to enumerate exhaustively like a set of mnemonics or numerical instruction codes. In some applications, a finite map turns out to be a "hot spot" that can improve performance if optimized. There are three operators provided in support of finite maps. They generate code that 9 is optimal in the sense of requiring minimally many interrogations on an amortized basis. This effect is achieved by detecting differences between the concrete representations of the possible input values without regard for their types. For example, the quickest function to convert natural numbers in the range 0 through 7 to the corresponding characters '0 through '7 would be the the one shown in Listing 6.1. In the worst case, five conditionals testing individual bits of the argument are evaluated, 10 but in the best case, only one. In any case, it would be irritating to develop or maintain 9 I.e., the quick ones make up for the slow ones, but they’re all pretty quick. 10 Recall from page 115 that natural numbers are represented as arbitrary length lists of booleans lsb first, so both the length and the content must be established.

this code by hand, which is the motivation for reification operators. Algebraic properties

The three reification operators are -:, -$, and =:, for zipped finite maps, unzipped finite maps, and address maps. fflThe -$ operator can be used in any arity and is fully dyadic. fflThe -: operator can also be used in any arity. It is prefix and postfix dyadic, but has the solo semantics described below. fflThe =: operator can be used in postfix or solo arities, and satisfies m=: j .=:/ m. There are no suffixes for the =: operator, but suffixes for the other two as described below allow some control over the tradeoff among code size, speed of execution, and compilation time.

Semantics These operators have related meanings. The semantics for the arities not mentioned below follows from the algebraic properties above. fflAn expression of the form <x :::x >-$<y :::y > with the left and right operand 0 n 0 n being lists of equal length, evaluates to a function f such that f.x / D y for all 0 [U+02C7] i i i [U+02C7] n. The effect of applying f to other arguments than those listed is unspecified and can cause an exception. fflAn expression of the form <(x ,y ):::(x ,y )>-:d, where d is a function, eval- 0 0 n n uates to a function f such that f.x / D y for all 0 [U+02C7] i [U+02C7] n, and f.z/ D d.z/ for all i i z not in fx :::x g. 0 n fflAn expression of the form -: <(x ,y ):::(x ,y )> evaluates to a function f 0 0 n n such that f.x / D y for all 0 [U+02C7] i [U+02C7] n, and f.z/ is undefined for all z not in i i fx :::x g. 0 n fflAn expression of the form <(x ,y ):::(x ,y )>=: (with no right operand) evalu- 0 0 n n ates to a function f such that f.x / D y for all 0 [U+02C7] i [U+02C7] n but otherwise is undefined, i i provided that x is an address (of type %a) for all i, and all x have the same weight. i i The address map operator =: generates faster code than the others where applicable by exploiting the concrete representation of pointers, provided that the pointers are distinct and non-overlapping. All of these operators require mutually distinct x values or the results are undefined. However, the y values need not be mutually distinct. If there are many cases of multi- ple x values mapping to the same y, the code may be optimized automatically to avoid containing redundant copies of y values if doing so results in a net improvement.

Listing 6.2 nested conditional equivalent to Listing 6.1 digitize = conditional( compose(compare,couple(constant 0,field &)), constant '0, conditional( compose(compare,couple(constant 1,field &)), constant '1, conditional( compose(compare,couple(constant 2,field &)), constant '2, conditional( compose(compare,couple(constant 3,field &)), constant '3, conditional( compose(compare,couple(constant 4,field &)), constant '4, conditional( compose(compare,couple(constant 5,field &)), constant '5, conditional( compose(compare,couple(constant 6,field &)), constant '6, constant '7)))))))

Tradeoffs Reifications of large data sets can be time consuming to construct. The time to construct them might outweigh the time saved over a less efficient equivalent. For example, building a cumulative conditional on the fly can be very easily done by a function like this one,

Listing 6.3 a space-optimized reification semantically equivalent to Listings 6.1 and 6.2. $ fun --m="-:=@p (<0,1,2,3,4,5,6,7>,01234567)" --decompile main = couple( couple( constant 0, conditional( field &, conditional( field(0,&), conditional( field(0,(&,0)), couple( conditional(field(0,(0,&)),constant 'Q,constant -1), field(&,0)), couple( constant -1, conditional(field(&,0),constant 1,constant <0,0>))), constant(1,0)), constant(1,-1)))

Suffixes The default behavior of the -: and -$ operators without a suffix is to generate the code as quickly as possible, by limiting the results to functions that can be constructed from conditional, field, and constant virtual machine combinators. Alternative be- haviors can be specified using suffixes of - and =. The suffixes are mutually exclusive, and have these interpretations. ffl- requests code that may have better run time performance (in real time rather than number of virtual machine reductions) by factoring out common compositions where possible

The last three operators listed in Table 6.11 are useful for string manipulation, but they also generalize to lists of any type. The %= operator is suitable for string substitution, and the =] and [= operators are for detecting prefixes of strings, which is relevant to parsing and file handling applications. 240

String substitution The %= operator can be used in all four arities and is fully dyadic. An expression of the form s%=t, where s and t are strings (or lists of any type) denotes a function that searches its argument for occurrences of s as a substring and returns a modified copy of the argument in which the occurrences of s have been replaced by t.

Suffixes This operator allows a suffix consisting of any sequence of the characters , =, and -. The effects of these characters in a suffix can be specified in terms of other operators described in this chapter. When a suffix contains more than one of them, they apply cumulatively in the order they’re written. fflThe * used as a suffix makes the result apply to all items of a list. s%=*t j (s%=t)

Prefix recognition The two remaining operators are [= and =], called "prefix" and "startswith", respectively (despite other uses of the word "prefix" in this manual). Both of these operators can be used in any arity, and are postfix dyadic. The left operand, if any, is a function, and the right operand, if any, is a string or a list. They share the algebraic property [=x j ~&[=x which is to say that the prefix arity is equivalent to the infix arity with an implied left operand of the identity function. Their algebraic properties differ with regard to the solo arity, in that .=]/ x j =]x whereas .[=/ .x;y/ j .[=y/ x. Neither operator has any suffixes. Their semantics can be summarized as follows.

6.12 Remarks The best way to proceed after a first reading of this chapter is to select a subset of the operators such as the one shown in Table 6.12 for use in your initial coding efforts. As the work progresses, you might gradually add to your repertoire when a new challenge can be met most effectively by deploying a new operator. Despite the importance of this material, attempting to commit it to memory is not rec- 12 ommended. Subtle lapses about semantics or algebraic properties will invariably occur that become persistent habits and code maintenance problems. The recommended way of staying on top of this material is to make full use of the interactive help facilities of the compiler. Brief reminders of the information in this chapter are at your fingertips during development by way of various interactive commands. For example, to see a complete list of all infix operators with a short reminder about how they work, execute the command $ fun --help infix

Similar commands can be used for prefix, postfix, and solo operators. To get help for an individual operator, use a command like this. $ fun --help infix,"→"

→ p→f iterates f while p is true If an operator contains the = character, it may be necessary to invoke the command with this syntax to avoid misleading the command line option parser in the virtual machine. $ fun --help=prefix,"-=" Finally, summary information about operator suffixes can be retrieved interactively by the command

$ fun --help suffixes This command can also be used for specific operators in the manner described above.

Let’s get this freak show on the road. Sheriff Wydell in The Devil’s Rejects

A sequential reading of this manual imparts a knowledge of the language from the bottom up, starting with the major components of pointers, types, and operators. Some features remain to be discussed at this point with a view to assembling them into complete appli- cations. This chapter gives a systematic account of the large scale organization of a source text, and is concerned mainly with the use of compiler directives.

7.1 Source file organization A file containing source code suitable for compilation, usually named with a suffix .fun, follows a pattern of sequences of declarations nested within matched pairs of compiler directives. A partial EBNF (Extended Backus-Nauer form) syntactic specification may be useful as a road map. hsource filei ::D hdirectivei.+ j hexpressioni/ [hdeclarationi j hsource filei] [U+039B] hdirectivei[U+0393] hdirectivei ::D #hidentifieri hdeclarationi ::D hhandlei = hexpressioni j hrecord declarationi hexpressioni ::D hidentifieri j [hexpressioni] hoperatori [hexpressioni] j hleft aggregatori[hexpressioni[,hexpressioni][U+039B]]hright aggregatori In keeping with EBNF conventions, most of the punctuation above is metasyntax. Square brackets contain optional content, vertical bars indicate choice, the [U+039B] indicates zero or more repetitions, and ::D defines a rewrite rule. Only the characters set in typewriter font

are meant to be taken literally, namely the comma, plus, minus, =, and hash characters above. fflExpressions consist of operators and operands as documented in Chapter 6. fflAggregators are things like parentheses and braces as documented in Chapter 5. fflHandles appearing on the left of a declaration are a restricted form of expression to be explained shortly.

7.1.1 Comments Comments can be interspersed with this file format. There are five kinds of comments. New users need to learn only the first one. fflThe delimiters (# and #) may be used in matched pairs to indicate a comment any- where in a source file (other than within a quoted string or other atomic lexeme, of course), and may be nested.

$ fun --main="<1,2,3>" --cast %nL <1,2,3> $ fun --m="<1,2,## 3>" --c <1,2> 245

Table 7.1: compiler directives by task classification; non-parameterized directives are shown with a + sign

When smart comments are used in a large expression, there is no need to fish for the other end of it to insert the matching comment delimiter, or to be too concerned about whether the commas and the right number of nesting aggregate operators are inside or outside the comment. 7.1.2 Directives

Compiler directives give instructions to the compiler about what should be done with the code it generates from the declarations. Directives can be nested in matched pairs like parentheses, and their effect is confined to the declarations appearing between them. Every source text needs at least some directives in order for its compilation to have any useful effect, but sometimes the directives are implicit or are stipulated by command line options. Syntactically, a directive begins with a hash character, followed by an identifier. The opening directive of a matched pair is followed either by a plus sign (with no interven- ing space) or an expression. The closing directive in a pair contains the same identifier terminated by a minus sign. An expression is supplied only for so called parameterized directives. Some examples of directives noted previously in passing are the #library+ directive for creating a library file, and the #executable directive for creating an executable file. The latter is a parameterized directive and the former isn’t. These and the other directives shown in Table 7.1 are documented more specifically in this chapter.

7.1.3 Declarations Other than compiler directives and comments, the main things occupying a source file are declarations. There are two kinds of declarations, one for records and the other for general data or functions using the = operator. Record declarations are documented com- prehensively in Section 4.2 and need not be revisited here. The = operator is used in many previous examples but may benefit from further explanation below.

Motivation The purpose of declarations is to effect compile-time bindings of values to identifiers, thereby associating a symbolic name with the value. When a declaration of the form hnamei=hvaluei appears in a source text, the name on the left may be used in place of the value on the right in any expression with the same effect (subject to rules of scope to be explained presently). There are several reasons declarations are important. fflDescriptive names are universally lauded as good programming practice. Compli- cated code is made more meaningful to a human reader when a large expression is encapsulated by a well chosen name. fflCode maintenance is easier and more reliable when a value used throughout the source text needs to be revised and only its declaration is affected. fflThe expression on the right of a declaration is evaluated only once during a compila- tion, regardless of how many times the name is used. Declaring it thereby improves efficiency if it is used in several places. fflSometimes the names given to values are needed by output generating directives, for example as file names or as names of symbols in a library.

Declaration Syntax The right side of the = operator in a declaration of the form hhandlei = hexpressioni

is an expression composed of operators and operands as documented in Chapters 5 and 6. Usually the left side is a single identifier, but in general it may follow this syntax, hhandlei ::D hidentifieri j (hhandlei) j hhandlei hparamsi hparamsi ::D hvariablei j (hparamsi[,hparamsi][U+039B]) j <hparamsi[,hparamsi][U+039B]> where a variable is a double quoted string like "x" or "y". That is, the identifier may appear with arbitrarily many dummy variable parameters in lists or tuples nested to any depth. This syntax is the same as the part of a record declaration to the left of the :: operator. (See Section 4.2.4, page 160.) Note that no terminators or separators other than white space are required between declarations.

Interpretation of dummy variables If dummy variables appear in the handle, the declaration is that of a function and the variables are part of a syntactically sugared form of lambda abstraction (pages 24 and 206). The declaration .f x/ = y is transformed to f = x. y. More generally, a declaration of the form .:::.f x /:::x / = y 0 n is transformed to .:::.f x /:::x / = x . y 0 n[U+0393]1 n (and so on). Free occurrences of the variables may appear in the expression y.

Identifier syntax Identifiers abide by the following syntactic rules. fflAn identifier may consist of upper and lower case letters and underscores, but not digits. This convention allows functions and numerical arguments to be juxtaposed without spaces or parentheses, with an expression like h1 being parsed as h(1). fflThe letters in an identifier are case sensitive, so foobar is a different identifier from FooBar. fflIdentifiers beginning with underscores may not be declared, because they are reserved either for record type expression identifiers or for a very few predeclared identifiers. fflIdentifiers for compiler directives and standard library functions are not reserved, making it acceptable to redefine words like library and conditional.

Predeclared identifiers Predeclared identifiers begin with two underscores, and there are currently only a small number of them. They are provided as predeclared identifiers rather than library functions for obvious reasons demanded by their semantics. fflswitches evaluates to a list of strings given by the command line parameters to the --switches option when the compiler is invoked. fflursala_version evaluates to a character string giving the version number of the compiler.

7.2 Scope Rules of scope are rarely a matter of concern for a user of this language, because the conventions are intuitive. Normally an identifier declared in a source file can be used anywhere else in the same file, before or after the declaration. Multiple declarations of the same identifier are an error and will cause compile time exception. Identifiers declared in separately compiled files are stored in libraries that may be imported. Applications for which these arrangements are insufficient are probably over designed. Nevertheless, there are ways of deliberately controlling the scope and visibility of dec- larations using the first three compiler directives listed in Table 7.1, which are documented in this section.

7.2.1 The #import directive Almost every source file contains #import directives in order to make use of standard or user defined libraries. fflThe #import directive is parameterized by an expression whose value is a list of assignments of strings to values, that may optionally be compressed (i.e., type %om or %omQ in terms of type expressions documented in Chapter 3). fflThe effect of the #import directive on an expression <'foo': bar, :::> is similar to inserting the sequence of declarations foo = bar::: at the point in the file where the directive is invoked. fflA matching #import- directive may appear subsequently in the file, but has no effect.

Usage Many previous examples have featured the directives

#import std #import nat for importing the standard library and natural number library. This practice is effective because external libraries are stored in binary files as instances of %om or %omQ, and any binary file name mentioned on the command line during compilation is accessible as an identifier in the source. However, nothing prevents arbitrary user defined expressions of these types from being "imported". (The std and nat libraries don’t have to be named on the command line because they are automatically supplied by the shell script that invokes the compiler.)

Semantics The effect of an #import directive is similar but not identical to inserting declarations. Although it is normally an error to have multiple declarations of the same identifier, it is acceptable to have a locally declared identifier with the same name as one that is imported. In this case, the local declaration takes precedence, but the precedence can be overridden by the dash operator. It is also acceptable to import multiple libraries with some identifiers in common. In this case, it is best to use fully qualified names with the dash operator (Section 6.7.1, page 214). For example, if two libraries foo and bar both need to be imported and both include an identifier x, then uses of x in the source should be qualified as foo-x or bar-x as the case may be. Name clashes Although relying on it would be asking for maintenance problems, there is a rule for name clash resolution when multiple libraries containing the same symbol name are imported.

7.2.2 The #export+ directive The main use for this directive is in a situation where dependences exist in both directions between declarations in separate source files. This situation makes it impossible to compile one of them first into a library and then import it by the other.

Motivation This situation is avoidable. Assuming no dependence cycles exist between declarations, the problem could be solved by merging or reorganizing the files. (For coping with cyclic dependences, see the #fix directive later in this chapter.) However, if design preferences are otherwise, the user can also arrange to compile both source files simultaneously with- out merging them just by naming both on the command line when invoking the compiler. Simultaneous compilation does not fully resolve the issue in itself. When multiple files are compiled simultaneously, the declarations in one file are not normally visible in another. (I.e., an attempt to use an identifier declared in another file will cause a compile- time exception with an "unrecognized identifier" diagnostic message.) How- ever, the #export+ directive can make declarations visible outside the file where they are written. Usage The usage of the #export directives is very simple. To make all declarations in a source file visible, place #export+ near the beginning of the file before any declarations. To make declarations visible only selectively, insert #export+ and #export- anywhere between declarations in the file. Only the declarations that are more recently preceded by #export+ than #export- will then be visible.

Semantics A couple of points of semantics should be noted. fflThe effect of #export+ is orthogonal to directives that generate output files, such as #binary+ or #library+, which can cause declarations to be written to files whether they are visible or not. fflThe #export directive can be overridden by the #hide directive, and vice versa, as explained in the next section. fflName clashes are possible when multiple files compiled simultaneously export sym- bols with the same names.  — Local declarations take precedence over external declarations.  — Further rules of name clash priority are given in the next section.  — An expression like filename-symbol can be used similarly to the dash op- erator to qualify a symbol unambiguously, unless not even the file names are unique.

The last point pertains to an idiom of the language rather than a legitimate use of the dash operator, because the file name is not meaningful as an operand in itself.

7.2.3 The #hide+ directive Even further removed from common use is the #hide+ directive, which can create sep- arate local name spaces within a single source file. Although it is unlikely to be needed by a real user, this directive is used internally by the compiler, making it a feature of the language calling for documentation. In particular, the name clash priority rules for si- multaneously compiled files are implied by its specification, with a matched pair of these directives implicitly bracketing each source file and another bracketing their ensemble. Usage The #hide+ and #hide- directives can be used as follows. Readers who find these matters perfectly lucid probably have been thinking about programming languages too long.

Name clashes To complete the picture, a name clash resolution policy is needed when multiple declara- tions of the same identifier are visible. For this purpose, we can regard name spaces as forming a tree, with nested spaces as the descendents of those enclosing them. The least common ancestor of any two nodes is the smallest subtree containing them.

7.3 Binary file output

There are four directives that are relevant to the output of binary files. Library files, exe- cutable files, and binary data files are each written by way of a separate directive, and the remaining directive inserts comments into any of these file types. 7.3.1 Binary data files Any data of any type generated in the course of a compilation can be saved in a file for future use by the #binary+ directive. The file format is standardized by the compiler and the virtual machine so that no printing or parsing needs to be specified by the user. Although they are called binary files in this manual, they actually contain only printable characters as a matter of convenience. The use of printable characters does not restrict the types of their contents.

Usage The usual way to generate binary data files is by having a #binary+ directive preceding any number of declarations, optionally followed by a #binary- directive. #binary+ hidentifieri = hexpressioni 1 1 : : : hidentifieri = hexpressioni n n #binary- Compilation of this code will cause n binary files to be written to the current directory, with file names given by the identifiers and contents given by the expressions. If the #binary- directive is omitted, then all declarations up to the end of the file or the next #hide- directive are involved. Other forms of declarations can also be used to generate binary files, such as records, lambda abstractions, and imported libraries.

Example A short example shows how a numerical value can be written to a binary file and then used in a subsequent compilation. $ fun --m="#binary+ x=1" fun: writing x $ fun x --m=x --c 1 The value in a binary file is used by passing the file name as a command line parameter to the compiler, and using the name of the file as an identifier in the source text.

7.3.2 Library files The #library+ and #library- directives may be used to bracket any sequence of declarations in a source text to store them in a library file, as shown below. #library+ hidentifieri = hexpressioni 1 1 : : : hidentifieri = hexpressioni n n #library-

If the #library- directive is omitted, the scope of the #library+ directives extends to the end of the file or current name space. The declarations can also be for imported modules or records. Usage The binary file written in the case of the #library+ directive is named after the source file in which it appears, with a suffix of .avm. At most one library file is written for each

Listing 7.1 a library source file #library+ rec :: x y foo = 'a bar = 'b baz = 'c

Listing 7.2 excerpt of the binary file from Listing 7.1 # rec (9) # - x # - y # bar (6) # baz (7) # foo (5) # {w{yZKk'{AsMU{r[yU[sx\Mz[MAnkczDqmAac\AlZ[_[ra<MeUxKbKYop[U+02C6]D’Et[?JxPQ… Sh{[U+02C6]'wKtuzD]ZozD]Z\=XJ[[U+02C6]DS_ctcd<S?cv<Ar][U+02C6]Z\=XEt=VBEz]d=VB<L\@[U+02C6]<

source file. If multiple pairs of #library+ and #library- directives appear in a file, all of the declarations between each pair are collected together into the same file. The normal way to use a library file is by the #import directive, which will cause the symbols stored in the library to be declared in the current name space, as explained in Section 7.2.1. A library file can also be used directly as a list of assignments of strings to values (type %om) or as a compressed list of assignments of strings to values (type %omQ). A library will be compressed if the command line option --archive is used when it is compiled. Example An example of a library file is shown in Listing 7.1, and part of the binary file is shown in Listing 7.2.

File formats The binary file for a library contains an automatically generated preamble listing the symbols alphabetically and their sizes measured in two bit units (quits). If any records are declared in the library, they are listed first with the field identifiers as shown. This format makes it easy to find the file containing a known symbol in a directory of library files by a command such as the following. $ grep foo *.avm libdem.avm:# foo (5)

Compilation The library source file is compiled by the command $ fun libdem.fun fun: writing libdem.avm It can be tested as follows. $ fun libdem --main="<foo,bar,baz>" --cast abc

The suffix .avm on the file name may be omitted when the file name is given as a command line parameter. When library symbols are referenced in a --main expres- sion, no #import directive is necessary, but if the library were used in a source file, the #import libdem directive would be needed in the file. 7.3.3 Executable files An executable file is one that can be invoked as a shell command to perform a computa- tion. The compiler can be used to generate executable files from specifications in Ursala, which are implemented as wrapper scripts that launch the virtual machine (avram) loaded with the necessary code. These scripts appear to execute natively to the end user, but are portable to any platform on which the virtual machine is installed.

Usage The #executable directive is used to generate executable files. It is normally appears in a source text as shown. #executable (hoptionsi,hconfiguration filesi) hidentifieri = hexpressioni 1 1 : : : hidentifieri = hexpressioni n n #executable-

The options and configuration files are lists of strings, which may be empty. fflThe idiomatic usage #executable& pertains to an executable with no options and no configuration files. fflEach enclosed declaration should represent a function that is meaningful to invoke as a free standing application. fflIf the #executable- directive is omitted, all declarations up to the end of the current name space are included. fflA separate executable file is written for each declaration, named after the identifier.

Execution models The run time behavior of an executable file is specified partly by the function it contains and partly by the way the virtual machine is invoked. The latter is determined by the options given in the left side of the parameter to the #executable directive, which are supplied automatically to the virtual machine as command line options. A complete list of command line options for the virtual machine with brief explanations can be viewed by executing the command $ avram --help All options are documented extensively in the avram reference manual. Some of them are less frequently used because they are applicable only in special circumstances, such as infinite stream processing, but the two that suffice for most applications are the following. fflA directive of the form

Listing 7.3 data structures used by parameterized executable files command_line :: files _file%L options _option%L file :: stamp %sbU path %sL preamble %sL contents %sLxU option :: position %n longform %b keyword %s parameters %sL invocation :: command _command_line environs %sm

Listing 7.4 a utility to display the command line record #import std #comment -[ Invoked with any combination of parameters or options, this program pretty prints a representation of the command line record to standard output.]-

#executable (parameterized,<>) #optimize+ crec = _{&iNC+ file$[contents: --<''>+ _command_line%P+} command]

Invocation records There are two fields in an invocation record, one for the environ- ment variables, and the other for the command line parameters and options. fflThe environment variables are represented in the environs field as a list of assign- ments of environment variable identifiers to strings, such as <'DISPLAY': :0.0,VISUAL: xemacs :::>

Command line records The data structures used to represent files and command line options are designed to allow convenient access with mnemonic field identifiers. As an example, a short text file $ cat mary.txt Mary had a little lamb.

passed as a command line argument to the application shown in Listing 7.4 with some other parameters will have the output below. $ crec mary.txt --foo --bar=baz command_line[ files: < file[ stamp: Sun Apr 29 13:48:48 2007, path: <'mary.txt'>, contents: <'Mary had a little lamb.,'>]>, options: < option[position: 1,longform: true,keyword: foo], option[ position: 2, longform: true, keyword: bar, parameters: <'baz'>]>] The application in Listing 7.4 is distributed with the compiler under the contrib subdi- rectory. fflThe files field in a command line record contains the list of files separately from the options field in the order the files are named on the command line. fflIf any configuration file names are supplied to the #executable directive when the application is compiled, their files will appear at the beginning of the list without the end user having to specify them. fflThe application aborts if any file parameters or configuration files don’t exist or aren’t readable.

File records The records in the list of files stored in the command line record passed to an application are organized with four fields. fflThe stamp field contains the modification time of an input file expressed as a string, if available. fflThe path field is a list of strings whose first item is the file name. Following strings, if any, are parent directory names in ascending order. If the last string in the list is empty, the path is absolute, but otherwise it is relative to the current directory. An empty path refers to the standard input stream. fflThe preamble is a list of character strings that is empty for text files an non- empty for binary files. Any comments or other front matter stored in a binary file are recorded here. fflThe contents field is a list of character strings for text files and any type for binary files.

Option records The other field in a command line record contains a list of records rep- resenting the command line options. This field is initialized by the virtual machine to contain the command line options passed to the application when it is invoked. Although command line options are parsed automatically by the virtual machine, it is the application developer’s responsibility to validate them. An option record contains four fields and their interpretations are straightforward. fflThe position field is a natural number whose value implies the relative ordering of the options and file parameters. This information is useful only to applications whose options have position dependent semantics. Positions are numbered from the left starting at zero. Non-consecutive position numbers between consecutive options indicate intervening file parameters. fflThe longform field is true if the option is specified with two dashes, and false otherwise. fflThe keyword field contains the literal name of the option as given on the command line in a character string.

Listing 7.5 An application to perform interactive user input #import std #import cli #executable (<'par'>,<>) grab =

_{&iNC+ file$[ stamp: &!, path: <'transcript'>!, contents: --<'>+} &zm+ ask(bash)/<>+ <'zenity --entry>!]

languages are notoriously awkward at user interaction despite long years of effort by the community to put the best face on it. With this disclaimer, one small example of an interactive application is shown in List- ing 7.5. This application opens a dialog window in which the user can type some text. When the user clicks on the "ok" button, the window closes, and the application writes the text to the a file named transcript in the current directory. The application can be compiled and run as shown below. Although the dialog window isn’t shown, that’s where the text was entered. $ fun cli grab.fun fun: writing grab $ grab grab: writing transcript $ cat transcript this text was entered The real work is done by the zenity utility, which needs to be installed on the host system. It is invoked in a shell spawned by the ask function defined in the cli library, as documented in Part III of this manual.

7.3.4 Comments The #comment directive adds user supplied front matter to binary data files, libraries, and executable files without altering their semantics. It requires a parameter that is either a character string or a list of character strings. The text of the comment can be anything at all, and is normally something to doc- ument the file for the benefit of an end user. Instructions for an executable or calling conventions for a library file are appropriate. Comments are also good places to include version information obtained by the pre-declared identifiers source_time_stamp or ursala_version (page 248). A pair of comment directives must bracket the directives that generate the files in which comments are desired. The closing #comment- directive may be omitted, in which

case the effect extends to the end of the enclosing name space (normally the end of the source file unless #hide directives are in use). A general outline of a source file using #comment directives would be the following. #comment htexti

7.4 Text file output

There are four directives pertaining to the output of text files, as shown in Table 7.1. The #cast and #output are parameterized, whereas #show+ and #text+ directives are not. All of them may be used in matched pairs to bracket a sequence of declarations, and will apply only to those they enclose. If the matching member of the pair is omitted, their scope extends to the end of the file or current name space. The specific features of each directive are documented in the remainder of this section.

7.4.1 The #cast directive The #cast directive requires a type expression as a parameter, and applies to declarations of values that are instances of the type. It ignores all but the last declaration within the sequence it brackets, and causes the value of the last one to be displayed on standard output. The display follows the concrete syntax implied by the type expression. This directive therefore performs the same operation as the --cast command line option used in many previous examples, except that it occurs within the file instead of on the command line, and the type expression is not optional.

7.4.2 The #show+ directive The #show+ directive performs a similar operation to the #cast, explained above, ex- cept that no type expression or any other parameter is required. It ignores all but the last declaration in the sequence it brackets, and causes the last one to be written to standard output. The type of the value that is written must be a list of character strings, or else an exception is raised. No formatting of the data is performed. The #show+ directive performs the same operation as the --show command line option, except that it occurs within the source text instead of on the command line.

7.4.3 The #text+ directive This directive causes a text file to be written for each declaration within its scope. The text file is named after the identifier on the left side of the declaration, with a suffix of .txt appended. The value of the expression on the right is required to be a list of character strings, but if the value is of a different type, the declaration is silently ignored and no exception is raised. A short example using this directive is the following. $ fun --m="#text+ foo = <'bar','>" fun: writing 'foo.txt $ cat foo.txt bar 7.4.4 The #output directive

This directive allows more control over the names and contents of output files than is possible with other directives. It is parameterized by a function whose input is a list of assignments of character strings to values, and whose output is a list of file records as documented on page 259. Interface The input to the function parameterizing the #output directive contains the values and identifiers of the declarations in its scope, as this example demonstrates.

$ fun --m="#output %nmM foo=1 bar=2" fun:command-line: <'foo': 1,bar: 2> The error messenger %nmM reports its argument in a diagnostic message when control passes to it, as documented on page 144. The argument of <'foo': 1,bar: 2> is derived from the declarations following the directive. The output from the function may make any use at all of the input or ignore it entirely 1 when generating the list of files to be written, as the next example shows. $ fun --m="#output <file[contents: <'done',''>]>! foo=1" done

Alternative interface It is often more convenient to use the #output directive with the function dot, which the standard library defines as follows. "s". "f". * file$[ stamp: &!, path: _{&iNC+ --(:/'. "s")+} &n, contents: "f"+ ~&m] The dot function is used in a directive of the form #output dothsuffixi hfunctioni

which causes a separate file to be written for each declaration within the scope of the directive. The file is named after the identifier in the declaration with the suffix appended, and the contents of the file are computed by applying the function to the value of the declaration. The function is required to return a list of character strings.

7.5 Code generation Several directives modify the code generated by the compiler with regard to optimization, profiling, and handling of cyclic dependences. The last requires some discussion at length, but the others are easily understood. 1 The shell command set +H may be needed in advance to suppress interpretation of the exclamation point.

7.5.1 Profiling The virtual machine provides the means to profile an application by making a record of its run time statistics. For any profiled function, the number of times it is evaluated is tabulated, along with the total and average number of virtual machine instructions (a.k.a. reductions) required to evaluate it, and their percentage of the total. This information may be useful for a developer to identify performance bottlenecks and potential areas for performance tuning. Profiling a function does not alter its semantics or behavior in any way. The run time statistics are recorded in a file named profile.txt in the current directory, without affecting any other file operations. One way of profiling a function f is to substitute the function profile(f,s) for it, where s is a character string used to identify f in the table of profile statistics, and profile is a function provided by the standard library. However, it may sometimes be more convenient to use the #profile+ directive.

Usage When a sequence of declarations is enclosed within a pair of #profile directives, pro- filing is enabled for all of them. A simple example demonstrates the effect. $ fun --m="#profile+ f=~& #profile- x = f* abc" --c abc $ cat profile.txt invocations reductions average percentage

Hazards The #profile directives are simple to use, but care must be taken to apply them se- lectively only to functions and not to general data declarations, which they might alter in unpredictable ways. In the above example, profiling is specifically switched off so as not to affect the declaration of x, which is not a function. Otherwise we would have this anomalous result.

$ fun --m="#profile+ f=~& g=f* abc" --c (&,&,0,<(abc,g)>) As one might imagine, overlooking this requirement can lead to mysterious bugs. Another hazard of the #profile directives is their use in combination with higher order functions. Although it is not incorrect to profile a higher order function, it might not be very informative. In this code fragment, #profile+ (h "n") "x" = … #profile- t = h1 x u = h2 x only the function h is profiled, which is a higher order function taking a natural number to one of a family of functions. However, the statistics of interest are likely to be those of h1 and h2, which are not profiled. Extending the scope of the #profile directives would not address the issue and in fact may cause further problems as described above. This situation calls for using the profile function mentioned previously for more specific control than the #profile directives.

7.5.2 Optimization directives A tradeoff exists between the speed of code generation and the quality of the code based on its size and efficiency. For production code, the quality is more important than the time needed to generate it. For code that exists only during the development cycle, the speed of generating the code is advantageous. By default, a middle ground between these alternatives is taken, but it is possible to direct the compiler to make the code more optimal than usual, or to make it less optimal but more quickly generated.

Examples The directive to improve the quality of the code is #optimize+, and the directive to improve the speed of generating it is #pessimize+. The first can be demonstrated as follows. $ fun --m="f=%bP" --decompile f = compose( couple( conditional( field(0,&), constant true, constant false), constant 0), couple(constant 0,field &))

The above code is compiled without optimization, but an improved version is obtained when optimization is requested. $ fun --m="#optimize+ f=%bP" --decompile f = couple( conditional(field &,constant true,constant false), constant 0) Some understanding of the virtual machine semantics may be needed to recognize that these two programs are equivalent, but it should be clear that the latter is smaller and faster. The #pessimize+ directive is demonstrated on a different example. $ fun --m="f = _&x+&y" --decompile f = compose(field(0,&),reverse) $ fun --m="#pessimize+ f = _&x+&y" --decompile f = compose( reverse, compose(reverse,compose(field(0,&),reverse))) Although there is no reason to use the #pessimize directives in cases like the one above, it often occurs during the development cycle that a short test program takes several minutes to compile because a large library function used in the program is being optimized every time. These delays can be mitigated considerably by the #pessimize directives.

Hazards The same care is needed with the #optimize directives as with the #profile direc- tives to avoid using them on declarations other than functions, for the reasons discussed above. It is sometimes possible to detect a non-function during optimization, and in such cases a warning is issued, but the detection is not completely reliable. Pessimization can safely be applied to anything with no anomalous effects. However, it is probably never a good idea to have pessimized code in a library function or exe- cutable, so a warning is issued when the #library or #executable directives detect a #pessimize directive within their scope. 7.5.3 Fixed point combinators

The #fix directive is an unusual feature of the language making it possible to solve systems of recurrences over any semantic domain to any order. It is necessary only for the user to nominate a fixed point combinator specific to the domain of interest, or a hierarchy of fixed point combinators if solutions to systems in higher orders are desired. Systems of recurrences involving multiple semantic domains are also manageable. First order recurrences Recurrences involving functions are the most familiar example, because in most languages there is no alternative for expressing recursively defined functions. Listing 7.6 shows an

Listing 7.6 a naive first order functional fixed point combinator #import std #fix "h". refer [U+02C6]H("h"+ refer+ _&f,&a) rev = _&?\& [U+02C6]lrNCT~&h rev+ ~&t

example of a recursively defined list reversal function expressed in this style. To see that it really works, we can save it in a file named fffx.fun and test it as follows. $ fun fffx.fun --m="rev abc" --c cba Normally a declaration of a function rev defined in terms of rev would be circular and compilation would fail, but the fixed point combinator "h". refer [U+02C6]H("h"+ refer+ _&f,&a) tells the compiler how to resolve the dependence.

Calling conventions The calling convention for a first order fixed point combinator (i.e., the function supplied by the user as a parameter to the #fix directive) is that given a function h, it must return an argument x such that x D h.x/. Intuitively, h can be envisioned as a function that plugs something into an expression to arrive at the right hand side of a declaration. In this example, the function h would be h.x/ D _&?\& [U+02C6]lrNCT~&h x+ ~&t In particular, h.rev/ would yield exactly the right hand side of the declaration in List- ing 7.6. Since the right hand side is equal to rev by definition, the value of rev satisfying rev D h.rev/ is the solution, if it can be found. The job of the fixed point combinator is to find it, hence the calling convention above.

Semantic note The rich and beautiful theory of this subject is beyond the scope of this manual, but it should be noted that the most natural definition of a fixed point for most functions h of interest generally turns out to be an infinite structure in some form. In practice, a finitely describable approximation to it must be found. It is this requirement that calls on the developer’s ingenuity. The fixed point combinator in the above example works by creating self modifying code that unrolls as far as necessary at run time, but this method is only the most naive approach. The construction of fixed point combinators varies widely with the application domain, thereby precluding any standard recipe. For example, these techniques have been used successfully for solving recurrences over asynchronous process networks in an electronic circuit CAD system, where the fixed point combinator takes a considerably different form. Specific applications are not discussed further here. 268

Listing 7.7 a better first order functional fixed point combinator #import std #import sol #fix function_fixer rev = _&?\& [U+02C6]lrNCT~&h rev+ ~&t

Practical functional recurrences There are of course better ways of expressing list rever- sal and recursively defined functions in general. Even for recurrences in this style, the fixed point combinator in Listing 7.6 should never be used in practice because it gen- erates bloated code, albeit semantically correct. Users who are nevertheless partial to this style, perhaps due to prior experience with other languages, are advised to use the function_fixer as a fixed point combinator, as shown in Listing 7.7, from the sol library distributed with the compiler. $ fun sol bffx.fun --decompile rev = refer conditional( field(0,&), compose( cat, couple( recur&, couple(field(0,(&,0)),constant 0))), field(0,&)) The results are seen to be comparable in quality to hand written code, although not as good as using the virtual machine’s built in reverse function or ~&x pseudo-pointer.

Higher order recurrences The recurrences considered up to this point are of the form t D h.t/, but there may also be a need to solve higher order recurrences in these forms, t D "x0". h.t;"x0"/ t D "x0". "x1". h.t;"x0";"x1"/ t D "x0". "x1". "x2". h.t;"x0";"x1";"x2"/ : : : and their equivalents, t."x0"/ D h.t;"x0"/, or variable-free forms t D h/t, and so on. In these recurrences, t has a higher order functional semantics regardless of the domain. The order is at least the number of nested lambda abstractions, but could be greater if the expressions are written in a variable-free style. It can be defined as the number n in the

Listing 7.8 different fixed point combinators for different orders of recurrences #import std #import nat #import sol #import tag #fix general_type_fixer 0

ntre = ntre%WZnwAZ # a zero order recurrence #fix general_type_fixer 1 xtre "s" = ("s",xtre "s")%drWZwlwAZ # first order #fix fix_lifter1 general_type_fixer 0

stre "s" = ("s",stre)%drWZwlwAZ # zero order lifted by 1

minimum expression .:::.t x /:::x / whereby the solution t yields an element of the 1 n semantic domain of interest. All of these recurrences can be accommodated by the #fix directive, but an appropri- ate fixed point combinator must be supplied by the user, which depends in general on the order.

Calling conventions For an n-th order recurrence of the form t D "x1". ::: "xn". h.t;"x1"; ::: ;"xn"/ or of the equivalent form

Type expression recurrences Although a distinct fixed point combinator is required for ev- ery order, it may be possible to construct an ensemble of them from a single definition parameterized by a natural number, as a developer exploring these facilities will discover. Two ready made examples of semantic domains with complete hierarchies of fixed point combinators are functions and type expressions. For the sake of variety, the latter is illus- trated in Listing 7.8. 270

Because xtre is a function requiring a type expression as an argument, it is applied to the dummy variable in the recurrence. A similar function is implemented by stre. $ fun sol tag nxs.fun --m="1: (2: (),3: ())" --c "stre %tL" <&>: (<0,&>: (),<&,&>: ()) This recurrence is solved without recourse to higher order fixed point combinators, as explained below.

Lifting the order If a function p returning elements of a semantic domain P having a family of fixed point combinators F is the solution to a first order recurrence of the form n p D "v". h.p "v";"v"/ then one way to get it would be by evaluating p D F "f". "v". h."f" "v";"v"/ 1 but another way would be

Heterogeneous recurrences Although this section begins with small contrived examples of functions and type expres- sions that could be expressed easily without recurrences, the difficulty of a manual solu- tion quickly escalates in realistic situations involving mutual dependences among multiple declarations. It is compounded when the system involves multiple semantic domains and various orders of recurrences, to the point where a methodical approach may be needed. In the most general case, each of m declarations can be associated with a separate fixed point combinator F for i ranging from 1 to m, in a source text organized as shown below. i #fix F 1 x D v . ::: v . h .x :::x ;v :::v / 1 11 1n 1 1 m 11 1n : : : #fix F m x D v . ::: v . h .x :::x ;v :::v / m m1 mn m 1 m m1 mn Although the declarations are shown here as lambda abstractions, any semantically equiv- alent form is acceptable, as noted previously. fflEach declared identifier x is defined by an expression h .:::/ that may depend on i i itself and any or all of the other x’s. fflDummy variables v , if any, are not shared among declarations, and their names need ij not be unique across them. fflThere is no requirement for any solutions x to belong to the same semantic domain i as any others, only that the corresponding fixed point combinator F is consistent i with its type and the order of its declaration. fflA single #fix directive can apply to multiple declarations following it up to the next one. In other respects, solving a system of recurrences automatically is no more difficult from the developer’s point of view than solving a single one as in previous examples. In particular, there is no need for the developer to give any special consideration to hetero- geneous or mutual recurrences when designing the fixed point combinator hierarchy for a particular semantic domain. It can be designed as if it were going to be used only to solve simple individual recurrences. Similar use may also be made of lifted fixed point combinators using the fix_lifter function.

7.6 Reflection Most of the remaining compiler directives in Table 7.1 are hooks that can be made to per- form any user defined operations not covered by the others. They come under the heading of reflection because they can access and inform the compiler’s run-time data structures describing the application being compiled. Because this access permits unrestricted mod- ifications, there is a possibility of disruption to the compiler’s correct operation. Fortu- nately, safety is ensured by the user’s capable judgment and intentions. There is also a directive to interface with external development tools (e.g., "make" file generators and similar utilities) by providing a standardized access to user specified metadata.

7.6.1 The #depend directive This directive takes any syntactically correct expression as a parameter, or at least an ex- pression that can be parsed without causing an exception. The expression is never eval- uated and is ignored during normal use. However, if the compiler is invoked with the --depend command line option, then the expression is written to standard output along with the source file name, and the rest of the file is ignored. The reason this directive might be useful is that it allows any user defined metadata embedded in the source file to be extracted automatically by a shell script or other devel- opment tool without it having to lex the file. For example, the directive can be used to list the names of the files on which a source file depends, so that a "make" utility can determine when it requires recompilation. #import foo #import bar

#depend foo bar … If a file baz.fun containing the above code fragment is compiled with the --depend command line option, the effect will be as follows. $ fun baz.fun --depend baz.fun: foo bar The script or development tool will need to parse this output, but that’s easier than scanning the source file for #import directives. It’s also more reliable if the directive is properly used because a file may depend on other files without importing them.

7.6.2 The #preprocess directive This directive takes a function as a parameter that performs a parse tree transformation. The parse tree contains the declarations within the scope of the directive. When the tree is 273

passed to the function during compilation, the function is required to return a tree of the same type. The parse trees used by the compiler are of type _token%T, where the token record is defined in the lag library. For example, compilation of a file named foobar.fun containing the code fragment #preprocess lag-_token%TM x=y would result in diagnostic message similar to the following. fun:foobar.fun:1:1: [U+02C6]: ( token[ lexeme: #preprocess, filename: foobar.fun, filenumber: 3, location: (1,1), preprocessor: 399394%fOi&, semantics: 33568%fOi&], < [U+02C6]: ( token[ lexeme: =, filename: foobar.fun, filenumber: 3, location: (3,2), preprocessor: 4677323%fOi&, semantics: 13%fOi&], < [U+02C6]:<> token[ lexeme: x, filename: foobar.fun, filenumber: 3, location: (3,1), semantics: 12%fOi&], [U+02C6]:<> token[ lexeme: y, filename: foobar.fun, filenumber: 3, location: (3,3)]>)>) Of course, in practice the function parameter to the #preprocess directive should do something more useful than dumping the parse tree as a diagnostic message. Effective use of this directive requires a knowledge of compiler internals as documented in Part IV of this manual. Possibly an even less useful example would be the following, #preprocess *[U+02C6]0 &d.semantics:= ~&d.semantics|| 0!!!

which implements something like the infamous Fortran-style implicit declaration by giving every undeclared identifier used in any expression a default value of 0 rather than letting it cause a compile-time exception.

7.6.3 The #postprocess directive This directive gives the user one last shot at any files generated by directives in its scope before they are written to external storage by the virtual machine. It is parameterized by a function that takes a list of files as input, and returns a list of files as a result. The files are represented as records in the form documented on page 259. The following simple example will cause all output files in its scope to be written to the /tmp directory instead of being written relative to the current working directory or at absolute paths. #postprocess * path:= _path; &i&& :\<'tmp',''>+ ~&h This directive can be used intelligently without any further knowledge of compiler inter- nals beyond the file record format documented in this chapter (unless of course it is used to modify the content of libraries or executable files significantly).

7.7 Command line options An alternative way to use most of the directives documented in this chapter is by naming them on the command line when the compiler is invoked rather than by including them in the source text. fflAn unparameterized directive like #binary+ is expressed on the command line as --binary or -binary. fflA parameterized directive like #cast is written as --cast "t" on the command line for a parameter t, with quotes and escapes as required by the shell.

A directive given on the command line applies by default to every declaration in every source file as if it were inserted at the beginning of each. Unlike a directive in a file, there isn’t the capability of switching it off selectively from the command line, even if applying it to every declaration is inappropriate, with two exceptions. fflAny directive selected on the command line can be made to apply to just one dec- laration by supplying an optional parameter stating the identifier of the declaration to which it applies. For example, --cast foo,bar specifies that the value of the identifier bar should be cast to the type foo and displayed as such. fflSome directives, such as #cast and #show, apply only to the last declaration within their scope in any case, so applying them to a whole file is the same as applying them only to the last declaration.

There are two other general differences between directives on the command line and di- rectives in a file. fflCommand line options other than --trace can be recognizably truncated, whereas directives in files must be spelled out in full. fflCommand line options can also be ambiguously truncated if the ambiguity can be resolved by giving precedence to the options --optimize, --show, --cast, --help, --archive, --parse, and --decompile. There are also some differences pertaining to specific directives.

7.7.1 Documentation The two command line options --version and --warranty have the conventional effects of displaying short messages containing the compiler version number and non- warranty information. The --help option provides a variety of brief documentation interactively, and is intended as the first point of reference for real users. The --help option by itself shows some general usage information and a list of all options with an indication of their parameters. It can also show more specific information when used with one of the following parameters. These parameters can be recognizably truncated. fflThe options parameter shows a listing similar to table 7.2 that also includes the compiler directives accessible by the command line. fflThe directives parameter shows a list of all compiler directives with short ex- planations. fflThe types parameter shows a list of the mnemonics of all primitive types and type constructors with explanations (see Listing 4.9, page 174).

7.7.2 Verbosity Several command line options can control the amount of diagnostic information reported by the compiler.

Warnings and core dumps The --no-warnings and --no-core-dumps options have the obvious interpreta- tions of suppressing warning messages and core dump files. $ fun --main=0 --c %c fun: writing core warning: can’t display as indicated type; core dumped $ fun --main=0 --c %c --no-core-dumps $ fun --main=0 --c %c --no-warnings fun: writing core

Aliases The --alias option changes the name of the application reported in diagnostic messages from fun to something else. $ fun --m="_{&h 0" fun:command-line: invalid deconstruction $ fun --alias serious --m="}&h 0" serious:command-line: invalid deconstruction This option is provided for the benefit of developers of application specific languages who 2 want to use the compiler as a starting point and customize it. The alias option would be hard coded into the shell script that invokes the compiler, so that end users need never suspect that they’re using a functional programming language, even when something goes wrong. This effect can also be achieved simply by renaming the script.

Troubleshooting the compiler The --phase option is of interest only to compiler developers. It takes a parameter of 0, 1, 2, or 3, and writes a binary file with the name phase0 through phase3, respectively. The file contains a data structure of a self describing type (%y), expressing the program state at a particular phase of the operation. Normal compilation is not performed when this option is selected, but this operation may be time consuming due to the compression required for large data structures. A useful technique to avoid including the std and nat libraries in the binary output file, thereby saving time and space, is to invoke the compiler by $ avram --par hfull pathi/fun hcommand linei --phase n

assuming the troublesome code in the source files in the command line has been narrowed down enough not to depend on the standard libraries. 2 or simplify it for a user base they consider less clever than themselves

Debugging client/server interactions The --trace option is passed through to the virtual machine, requesting all characters exchanged between an application using the interact combinator and an external com- mand line interpreter to be displayed on the console along with some verbose diagnostic information. Unlike most command line options, --trace must be written out in full and may not be truncated. This option is useful mainly for debugging. See the avram reference manual for further information. Here is an example using a function from the cli library. $ fun cli --m=now0 --c --trace opening bash waiting for 36 32 : : : → $ 36 → 32 matched ← e 101 ← x 120 ← i 105 ← t 116 ← 10 waiting for nothing matched closing bash Tue, 19 Jun 2007 23:44:30 +0100

7.7.3 Data display A small selection of command line options can be used to display information specific to a given program source text or expression. The --cast command line option, seen in many previous examples, is derived from the #cast directive documented in Section 7.4.1, hence not repeated here. The same goes for the --show option, which is also frequently used (Section 7.4.2). The others are summarized below. fflThe --decompile option shows the virtual machine code for the last expression compiled, assuming it is a function. The expression can come from either the source text or from a --main option. The code is expressed using the mnemonics from the cor library, (Listing 3.1, page 113) and documented extensively in the avram reference manual. This option is similar to --cast %f, except that it displays the full declaration. fflThe --depend option displays the expression used as a parameter to any #depend directives in the source texts on standard output, prefaced by the name of the source file. See Section 7.6.1 for more information and motivation.

7.7.4 File handling The remaining command line options in Table 7.2 pertain to the handling of input and output files. Output files

The --archive and --gpl options are specific to library files and executables (i.e., those generated by the #library or #executable directives). Each takes an optional numerical parameter. --archive This option causes a library file to be compressed, or an executable code file to be stored in a compressed self-extracting form. The optional parameter is the granularity of compression, which has the same interpretation as the granularity of compressed types explained on page 168. The default behavior without a parameter is maximum compres- sion, which is usually the best choice. Compression is usually a matter of necessity for any non-trivial application, without which the file size explodes, and the memory requirements even more so. fflCompressed libraries are indistinguishable from uncompressed libraries when im- ported by the #import directive or dereferenced with the dash operator.

Input files When the compiler is invoked with multiple input files, the default behavior is to treat the binary files as data and to compile the text files as source code. For this purpose, binary files are those that conform to the format used in files generated by the directives #library, #binary, and #executable, and text files are any other files, even if they contain unprintable characters. No explicit i/o operations are required in the source files to access the contents of the data files. Instead, the contents of the data files are accessible in the source files as the values of pre-declared identifiers derived from the file names. fflIf a data file name contains only alphabetic characters, the identifier associated with it is the file name.

--data This option can be used to override the default behavior for text files by causing them to be treated as data files instead of being compiled. The value of the identifier associated with a text file will be a list of character strings storing the contents of the file. The --data option is unusual in that its placement on the command line is significant. It must immediately precede the name of the file that is to be treated as data. It pertains only to that file and not to any files given subsequently on the command line. If there are multiple text files to be treated as data files, each one must be preceded by a separate --data option.

--implicit-imports When this option is selected, all files with suffixes of .avm on the command line are detected. These files are required to be valid library files generated by the #library directive during a previous compilation. An #import directive is constructed with the name of each library file, and this sequence of #import directives is inserted at the beginning of each source file. The resulting effect is that the code in the source files may refer to symbols within the library files as if they were locally declared, without having to import them. --switches This option takes a comma separated sequences of parameters, and causes the predeclared identifier __switches to evaluate to them in any source text being com- piled, as this example shows.

$ fun --m=switches --switches=foo,bar,baz --c <'foo',bar,baz> The type of the predeclared identifier switches is always a list of character strings. See page 248 for more information and motivation. --main This option is used in many previous examples. Its purpose is to allow for easy interactive compilation of short expressions directly from the command line without re- quiring them to be stored in a file. fflThe parameter to the --main option contains the text be compiled, which can be either a single expression or a sequence of one or more declarations.

7.8 Remarks

This chapter concludes Part II of this manual on Language Elements. These specifications are expected to remain fairly stable for the forseeable future, with most new development work concentrating on the standard libraries documented in Part III. Readers with a good grasp of this material are well posed to begin developing practical applications with Ursala. Please use your powers wisely and only for the benefit of all mankind.

I require the exclusive use of this room, as well as that drafty sewer you call the library. Sheridan Whiteside, The man who came to dinner

Most applications in this language as in others are not developed ab initio but from a reusable code base of tried and tested components. A growing collection of library mod- ules packaged and maintained along with the compiler provides a variety of helpful utilities in the way of functions, combining forms, and data structure specifications.

8.1 Overview of packaged libraries There are three subdirectories in the main distribution package populated with .avm vir- tual code library files, these being the src/, lib/, and contrib/ directories.

8.1.2 Documentation conventions Each library is documented in a separate chapter, even though some chapters may be very short. The style is that of a reference manual, often with little more than a catalog of descriptions of the library functions and data structures. The emphasis is more on accuracy and completeness than motivation or literary merit, and this style is most conducive to maintaining current information about an evolving code base. These chapters need not be read sequentially, but they take a working knowledge of the material in Part II for granted. The std and nat libraries are under the src/ directory in the packaged distribution because they are necessary for bootstrapping the compiler, but they are also suitable for more general use so they are documented in Part III. The remainder of this chapter documents the std library. Unlike most other libraries, this one can be imported into any source text without being given as a command line parameter to the compiler, because it is automatically supplied by the shell script that invokes the compiler.

8.2 Constants The standard library defines three constants that are useful for input parsing and validation.

8.3 Enumeration Two functions tangentially related to the idea of enumeration are the following.

This function is useful for exhaustively testing code that operates on small data structures or pointers. However, it should be used with caution because the number of results in- P n creases exponentially with the size n, being given by f.i/, where f.0/ D 1 and iD0 i[U+0393]1 X f.i/ D f.j/f.i [U+0393]j/ jD0 for i [U+00BF] 0. enum This function takes a set of data and returns a type expression for the type whose instances are the data. See page 172 for an example.

8.4 File Handling Executable applications that have a command line interface or that generate output files are expressed as functions that observe consistent calling conventions. The standard li- brary provides a small set of data structure declarations and functions in support of these conventions.

8.4.1 Data Structures The following four identifiers are record mnemonics. Their usage is explained with exam- ples starting on page 257, but they are briefly recounted here for reference.

8.4.2 Functions Two further functions are intended to facilitate generating output files or other possible uses. gpl This function takes a version number as a character string (usually 2 or 3), and returns a list of character strings containing the standard General Public License notification for the corresponding version, "This program is free software :::". If an empty string is supplied as an argument, the version number defaults to 3.

8.5 Control Structures A small group of control structures comparable to those in other languages is specified by the combining forms documented in this section. These are not built into the language but defined as library functions.

8.5.1 Conditional An idea originated by Tony Hoare, case statements are useful as a structured form of nested conditionals whose predicates test the argument against a constant. (This construct is more restrictive than the cumulative conditional combinator, which allows general predicates as explained on page 190.) In typical usage, a function H of the form H D (case f) ( < k : g , 0 0 : : : k : g >, n n h)

applied to an argument x first computes the value k D f.x/, and then tests k against each possible k in sequence. For the first matching k , the corresponding function g .x/ is i i i evaluated and its result is returned. If no match is found, h.x/ is returned. Note that g i or h is applied to the original argument, x, not to k, which is only an intermediate result that is not returned. Evaluation is non-strict insofar as only the g for the matching k is i i evaluated, if any, and h is not evaluated unless no match is found. Two forms of case statement defined in the standard library differ in the nature of the test, and the third generalizes both of these. case This function takes a function f as an argument and returns a function that maps a pair (<k : g , ::: k : g >,h) to a function H as above. In terms of the foregoing 0 0 n n notation, a match between k and k occurs precisely when they are equal in the sense i described on page 78.

classifier = cases~&'unrecognized'! < aeiouAEIOU: vowel!, letters: consonant!, digits: digit!> Note that because the order in which the cases are listed is significant, the patterns may overlap without ambiguity. If the patterns are mutually disjoint, use of braces is preferable to angle brackets as a matter of style and clarity. The concept of a case statement generalizes to arbitrary matching criteria beyond equal- ity and membership.

8.5.2 Unconditional Most of the basic functional combining forms in the language are provided by the operators documented in Chapter 6, but several are expressible as follows.

A simple example of this function would be $ fun --m="associate_left~& abcdef" --c ((((('a,'b),'c),'d),'e),'f)

8.5.3 Iterative A couple of functions useful mainly for debugging can be used to iterate a function a fixed number of times. rep This function takes a natural number n as an argument, and returns a function that maps a given function f to the composition of f with itself n times (or equivalent). If n D 0, the result of .rep n/ f is the identity function.

The following example demonstrates the rep function by inserting a zero at the head of a list five times. $ fun --m="rep5~&NiC <1>" --c %nL <0,0,0,0,0,1>

8.5.4 Random Three functions are defined in the standard library for generating pseudo-random data according to some specified distribution. The underlying random number generator is the Mersenne Twistor algorithm provided by the virtual machine’s mtwist library, as documented in the avram reference manual. arc This function, mnemonic for "arbitrary constant", takes any set as an argument, and constructs a program that ignores its input but returns a pseudo-randomly chosen member of the set. The value returned by the program may be different for each execution, with all members of the set being equally probable.

An example of the arc function is given by the following expression. $ fun --m="arc<0,1,2>* --------" --c <0,2,1,1,0,1,2,1>

$ fun --m="stochasm{0.3: ~&iNC,0.7: '!}*= letters" --c 'dehilnosDFLMNOSVY

8.6 List rearrangement A collection of functions defined in the standard library for operating on lists supplements the operators and pseudo-pointers in the core language.

8.6.1 Binary functions These functions take a pair of lists to a list. zip Given a pair of list .hx :::x i;hy :::y i/ of the same length, this function returns 0 n 0 n the list of pairs h.x ;y /:::.x ;y /i. If the lists are of unequal lengths, the function 0 0 n n raises an exception with the diagnostic message "bad zip".

The zip function is equivalent to the ~&p pseudo-pointer (page 75). zipt This function performs a truncating zip operation. It follows a similar calling conven- tion to the zip function, above, but does not require the lists to be of equal length. If the lengths are unequal, the shorter list is zipped to a prefix of the longer one. The zipt function is equivalent to the one used in an example on Page 73.

8.6.2 Numerical The function in this section perform operations on lists that are parameterized by natural numbers. iol Given any list, this function returns a list of consecutive natural numbers starting with zero that has the same length as its argument.

This function is exemplified in the following expression. $ fun --m="iol catabolic" --c <0,1,2,3,4,5,6,7,8>

The function name is mnemonic for "sliding window". An example of the swin function is the following. $ fun --m="swin3 abcdef" --c %sL <'abc',bcd,cde,def>

8.6.3 General Some further list editing operations parameterized by functions or constants are docu- mented in this section. These include functions for padded zips, variations on flattening and unflattening, sorting, and conditional truncation. zipp This function takes a constant k to a function that zips two lists together of arbitrary length by padding the shorter one with copies of k if necessary. It satisfies the follow- ing recurrences. .zipp k/ .<>;<>/ D <> .zipp k/ .a : x;<>/ D .a;k/ : ..zipp k/ .x;<>// .zipp k/ .<>;b : y/ D .k;b/ : ..zipp k/ .<>;y// .zipp k/ .a : x;b : y/ D .a;b/ : ..zipp k/ .x;y//

This example shows the zipp function zipping two lists of natural numbers by padding the shorter one with zeros. $ fun --m="zipp0/<1,2,3> <4,5,6,7,8>" --c %nWL <(1,4),(2,5),(3,6),(0,7),(0,8)> pad This function takes a constant k to a function that takes a list of lists of differing lengths to a list of lists of the same length by appending copies of k to those that are shorter than the maximum. It is defined as follows. pad "k" = _&i&& &rSS+ zipp"k"[U+02C6]*D\~& leql$[U+02C6]

This example shows how a list of lists of lengths 2, 1, and 3 is transformed to a list of three lists of length three by padding the shorter lists. $ fun --m="pad1 1>" --c %nLL 1 mat This function takes a constant k of type t to a function that flattens a list of type t%LL to a list of type t%L after inserting a copy of <k> between consecutive items. It can be defined as :-0+ [U+02C6]|T/~&+ //:, among other ways.

The following example shows how a ten is inserted after every three numbers in the list of natural numbers from 0 to 9. $ fun --m="mat10 block3 <0,1,2,3,4,5,6,7,8,9>" --c %nL <0,1,2,10,3,4,5,10,6,7,8,10,9>

An example of the rlc function that collects runs of identical list items is the following. 297

$ fun --m="rlc_{&E <0,0,1,0,1,1,1,0,1,0,0>" --c %nLL 0> This function could be carried a step further to compute the conventional run length encod- ing of a sequence by [U+02C6](length,}&h)*+ rlc~&E, which would return a list of pairs with the length of each run on the left and its content on the right.

$ fun --m="skipwhile_{&h <1,3,5,2,4,7,9>" --c %nL <2,4,7,9> Recall that} &h tests the least significant bit of the binary representation of a natural num- ber. 8.6.4 Combinatorics

Various functions relevant to combinatorial problems are defined in the standard library. These include functions for computing transitive closures and cross products, permuta- tions, combinations, and powersets. closure Given a relation represented as a set of pairs, this function computes the transitive closure of the relation. The transitive closure of a relation R is defined as the min- imum relation containing R for which membership of any .x;y/ and .y;z/ implies membership of .x;z/. A simple example of the closure function is the following. $ fun --m="closure{(x,y),(y,z)}" --c %sWS {(x,y),(x,z),(y,z)}

This example shows all possible subdivisions of a nine item lists into three consecutive parts. $ fun --m="cuts(abcdefghi,2)" --c %sLL < <'a',b,cdefghi>, <'a',bc,defghi>, <'a',bcd,efghi>, <'a',bcde,fghi>, <'a',bcdef,ghi>, <'a',bcdefg,hi>, <'a',bcdefgh,i>, <'ab',c,defghi>, <'ab',cd,efghi>, <'ab',cde,fghi>, <'ab',cdef,ghi>, <'ab',cdefg,hi>, <'ab',cdefgh,i>, <'abc',d,efghi>, <'abc',de,fghi>, <'abc',def,ghi>, <'abc',defg,hi>, <'abc',defgh,i>, <'abcd',e,fghi>, <'abcd',ef,ghi>, <'abcd',efg,hi>, <'abcd',efgh,i>, <'abcde',f,ghi>, <'abcde',fg,hi>, <'abcde',fgh,i>, <'abcdef',g,hi>, <'abcdef',gh,i>, <'abcdefg',h,i>> The result is ordered by length of the first sublists with different lengths.

is an example usage. $ fun --m="words5 01" --c < 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111>

8.7 Predicates Various primitive functions and combinators are defined in the standard library to assist in applications needing to compute truth values or decision procedures.

8.7.1 Primitive A number of predicates that are mostly binary relations are provided by the definitions documented in this section. fflAs a matter of convention, predicates may return any non-empty value when said to hold or to be true, and will return the empty value () when false. fflThese predicates are false in all cases where the descriptions do not stipulate that they are true. fflEquality is in the sense described on page 78. fflRead "if" as "if and only if".

8.7.2 Boolean combinators The boolean operations are most conveniently obtained by combinators taking predicates to predicates rather than by first order functions. Predicates used as arguments to the functions in this section could be any of those documented in the previous section, as well as any user defined predicates. Each of these predicate combinators is unary in the sense that it takes a single predicate as an argument and returns a single predicate as a result. However, the predicate it returns may operate on a pair of values. In that case, evaluation is non-strict in that only the left value is considered where it suffices to determine the result. Similar conventions to those of the previous section regarding truth values apply here as well.

8.7.3 Predicates on lists These combinators take an arbitrary predicate as an argument and return a predicate that operates on a list.

8.8 Generalized set operations The combinators documented in this section generalize the concepts of intersection, dif- ference, and membership for lists and sets by parameterizing them with an arbitrary binary relational predicate.

A short example using this function is the following. $ fun --m="gldif~&E/aaabbbcccaaa aaccccd" --c %s abbbaaa glint This function performs an analogous operation to the generalized list difference com- binator gldif, but pertains to intersection rather than difference.

The generalized set operations above are related to the K10 through K13 pseudo-pointers, whereas the remaining one is similar to the w pseudo-pointer or -= operator. lsm Given a set s, this function, mnemonic for "large set membership", constructs a pred- icate that is true for all members of s and false otherwise.

Although it would be trivial to implement lsm as \/-=, the implementation in the stan- dard library attempts to construct the optimal decision procedure for a large set, which may be more efficient than the default set membership algorithm of sequential search. The crossover point between the speed of the two algorithms for membership testing occurs around a cardinality of 8, not including the time required by lsm to construct the predicate. Best performance is achieved when the set members have most dissimilar representations.

I’m your number one fan. Kathy Bates in Misery

The natural numbers 0;1;2:::, are a primitive type in the language, with the type expres- sion mnemonic %n, as explained in Chapter 3. Any application involving natural numbers may elect to manipulate them directly on the bit level. Alternatively, the nat module presents an interface to them as an abstract type. Similarly to the std library documented in the previous chapter, the nat library is automatically loaded by the compiler’s wrapper script, and need not be specified on the command line. This chapter documents its functions.

9.1 Predicates A couple of functions take natural numbers as input and return a truth value.

9.2 Unary The following functions take a natural number as an argument and return a natural number as a result.

The double function is a partial inverse to half, because half+ double is equivalent to the identity function. The function double+ half is equivalent to rounding down to the nearest even number. predecessor Given a number n, this function returns n [U+0393] 1 if n [U+00BF] 0, and raises an exception if n D 0. The diagnostic message in the latter case is "natural out of range".

9.3 Binary All of the functions documented in this section take a pair of natural numbers as input. The division function returns a pair of natural numbers as a result, and the rest return a single natural number.

$ fun --m="quotient* <(21,3),(100,8)>" --c %nL <7,12> remainder This function takes a pair .n;m/ and returns their residual, customarily denoted n mod m. This number is the remainder left over when n is divided by m, i.e., ..n=m/[U+0393] bn=mc/[U+0398]m.

The standard relationships between truncated quotients and residuals holds exactly. [U+02C6]~&r sum[U+02C6]/remainder product[U+02C6]/~&r quotient This expression is equivalent to the identity function for a pair of natural numbers .n;m/ provided m 6D 0.

$ fun --m="power/2 56" --c 310

72057594037927936 However, powers of two are more efficiently obtained by bit shifting.

9.4 Lists A couple of other functions in the nat library are useful for converting between numbers and lists.

The following equivalence holds for any natural number n. n D length iota n Because natural numbers are represented as lists of booleans, they also have a length. Although there is no logarithm function defined in the nat library, a tight upper bound on the logarithm of a natural number to the base 2 can be found by taking its length. $ fun --m="length factorial 52" --c %n 226 This result is confirmed by a more precise calculation using floating point arithmetic. $ fun --m="..log2 ..nat2mp factorial 52" --c %E 2.255810E+02

He is you, your opposite, your negative, the result of the equation trying to balance itself out. The Oracle in The Matrix Revolutions

10.1 Notes on usage Many functions in this chapter have the same names as similar functions in the nat library documented in the previous chapter. Using both in the same source text is possible by methods described in Section 7.2 to control the scope and visibility of imported symbols. For example, a file containing the directives

#import nat #import int in that order preceding any declarations will use integer functions by default, reverting to natural functions such as iota only when there is no integer equivalent, or when it is specifically requested using the dash operator, as in nat-successor. The opposite order will cause natural functions to be used by default unless otherwise indicated. Al- ternatively, integer operations can be used exclusively by using only the #import int directive and omitting #import nat from the source text.

10.2 Predicates This section is for functions that return a boolean value when operating on integers. 312

10.3 Unary Operations The functions documented in this section take a single integer argument to an integer result. abs This function returns the absolute value of its argument. If the argument is non- negative, the result is the same as the argument. Otherwise, the result is its additive inverse. Hence, the result is always non-negative.

Unlike the nat-predecessor function, this one is defined for all integers.

10.4 Binary Operations

The functions documented in this section take a pair of integers as an argument and return an integer as a result.

Unlike the nat-difference function, this one is defined for all integers. product Given a pair .n;m/ this function returns their product, nm.

10.5 Multivalued Function documented in this section return something other than a boolean or integer value.

zrange Given a pair of integers .n;m/, this function returns the list of jn [U+0393] m C 1j integers beginning with n, ending with m and differing by 1 between consecutive items. If n [U+00BF] m, the numbers are listed in descending order.

For him, it’s as if there were thousands of bars and behind the thousands of bars no world. Robin Williams in Awakenings

The type %v represents integers sequences of decimal digits, along with a boolean sign, as described on page 119, which may be more efficient than the usual binary representation in applications needing to manipulate and display numbers with thousands of digits or more. Literal numerical constants in this representation are written as sequences of decimal digits with a trailing underscore, and an optional leading negative sign. A small set of functions for operating on numbers in this representation with a similar API to the int library described in the previous chapter is provided by the bcd library documented in this chapter. Because many of the functions are similarly named, the dis- cussion of name clash resolution in Section 10.1 is relevant here as well.

11.1 Predicates A partial order relational predicate on BCD integers is provided as follows.

11.2 Unary Operations The functions documented in this section take a single BCD argument to an BCD result. abs This function returns the absolute value of its argument. If the argument is non- negative, the result is the same as the argument. Otherwise, the result is its additive inverse. Hence, the result is always non-negative.

Here are some examples. $ fun bcd --m="[U+02C6]A(~&,sgn)* :/0_ 50%vi* 7" --c %vvAL < 0_: 0_, -3741541087_: -1_, 306278996_: 1_, -12120849714_: -1_>

11.3 Binary Operations The functions documented in this section take a pair of BCD integers as an argument and return a BCD integer as a result. sum Given a pair .n;m/ this function returns their sum, nCm.

The quotient rounding convention has been chosen to satisfy this identity. abs.quotient.n;m// j quotient.abs.n/;abs.m//

11.4 Multivalued

Function documented in this section return something other than a boolean or BCD value. division This function maps a pair .n;m/ of integers with m 6D 0 to the pair of integers .quotient.n;m/;remainder.n;m//. The same relationship among the division, quotient, and remainder functions holds for BCD integers as for binary integers and natural numbers. If both the quotient and remainder are required, it is more efficient to compute them using the division function than individually.

11.5 Conversions

A couple of functions are defined provided for converting between BCD integers and other types. toint Given a BCD integer n, this function returns the corresponding integer in the binary representation (i.e., type %z, or if non-negative, type %n).

Don’t knock rationalizations. Jeff Goldblum in The Big Chill

The primitive type %q represents rational numbers in unlimited precision. They can be used to perform exact numerical calculations with the functions defined in the rat library and documented in this chapter. Simultaneously their greatest strength and their greatest weakness, their exactitude renders them prohibitively inefficient for routine work, but they may be useful in special circumstances such as proof checking or conjecture.

12.1 Unary The functions documented in this section take a single rational number as an argument to a rational result. inverse This function takes a number x to 1=x. This example shows inverses of two numbers. $ fun rat --m="inverse* <5/2,-3/8>" --c %qL <2/5,-8/3>

12.2 Binary The functions documented in this section take a pair of rational numbers and return a rational number, except for rleq, which returns a boolean value.

12.3 Formatting

The functions documented in this section convert rational numbers to a character string representation compatible with the syntax of floating point numbers. In some cases, the string representation may require rounding. Each function takes a natural number as an ar- gument specifying the number of decimal places, and returns a function that takes rational numbers to lists of strings. fixed This function takes a natural number n to a function that converts a rational number to a list of strings in fixed decimal format with n places after the decimal point.

Logsine, clogsine, thingamabob, some bubblegum will do the job. The Nowhere Man in Yellow Submarine

Ursala places substantial resources at the developer’s disposal in the way of floating point number operations. A small library, flo, containing some of the more frequently used functions and constants is documented in this chapter. Other libraries pertaining to more specialized areas are documented in subsequent chapters, and these are further augmented by the virtual machine’s interface to third party numerical libraries as documented in the avram reference manual. All functions described in this chapter involve floating point numbers in standard IEEE double precision format, corresponding to the primitive type %e in the language. Users interested in arbitrary precision numbers (type %E) are referred to the documentation of the mpfr library in the avram reference manual, whose functions are directly accessible by the library combinators (Section 6.7.2, page 215).

13.1 Constants The declarations documented in this section pertain to numerical constants. These are usable as numbers in expressions, and require not much further explanation.

13.2 General General unary and binary operations on floating point numbers are documented in this section. Most of them are simple wrappers for the corresponding virtual machine math.. library functions, defined as a matter of convenience.

13.2.1 Unary The following functions take a single floating point number as an argument and return a floating point number as a result. abs The absolute value function, customarily denoted jxj for an argument x, returns x if x is positive or zero, and [U+0393]x otherwise.

13.2.2 Binary The usual binary operations on floating point numbers are provided by the functions docu- mented in this section. Each of them takes a pair of numbers as input and returns a number as a result. Correct handling of indeterminate (nan) and infinite arguments is automatic. Overflowing results are mapped to infinity.

The last two functions are often more convenient than the conventional forms of sub- traction and division. For example, to subtract the baseline from a list of floating point numbers, it is slightly quicker and less cluttered to write bus[U+02C6]*D~& fleq$- than the alternative sub[U+02C6]*DrlXS\~& fleq$-

13.3 Relational The following functions involve tests or comparisons on floating point numbers.

13.4 Trigonometric Wrappers for circular functions provided by the virtual machine’s math.. library are defined for convenience as shown below. Each of these functions takes a floating point argument to a floating point result. The inverse functions may return a nan value for arguments outside their domains.

Definitions of sine and cosine functions are given by the standard construction involving the unit circle. tan This function returns the tangent of a given number x, which can be defined as sin.x/=cos.x/.

13.5 Exponential A short selection of functions pertaining to exponents and logarithms is provided as de- scribed below. Each of these functions takes a single floating point argument to a floating point result.

13.6 Calculus Several higher order functions supporting elementary operations from integral and differ- ential calculus are provided as documented in this section.

< (0.000000e+00,0.000000e+00), (1.000000e-01,2.000000e-01), (2.000000e-01,4.000000e-01), (3.000000e-01,6.000000e-01), (4.000000e-01,8.000000e-01), (5.000000e-01,1.000000e-00), (6.000000e-01,1.200000e+00), (7.000000e-01,1.400000e+00), (8.000000e-01,1.600000e+00), (9.000000e-01,1.800000e+00), (1.000000e+00,2.000000e+00)> For each value of x, the derivative of f.x/ is 2x, as expected. nth deriv This function takes a natural number n to a function that returns the n-th derivative of a given function f.

The function nth_deriv1 is equivalent to the derivative function. Ideally the func- tion nth_deriv2 would be equivalent to derivative+ derivative, and so on, but in practice there are problems with numerical stability when taking higher derivatives. The nth_deriv function attempts to obtain better results than the naive approach by us- ing an ensemble of progressively larger tolerances for the higher derivatives when invoking the underlying GSL differentiation routine. integral Given a function f taking a real value to a real result, this function returns a function F taking a pair of real values to a real result, such that Z b F.a;b/ D f.x/ dx xDa The following examples demonstrate the integral function. $ fun flo --m="integral(sqr)/0. 3." --c %e 9.000000e+00 $ fun flo --m="integral(sin)/0. pi" --c %e 2.000000e+00 The integral function is based on the GNU Scientific Library integration routines, using the adaptive algorithm iterated over a range of tolerances if necessary. This function will give best results in most cases, but users requiring more specific control (e.g., to specify tolerances or discontinuities explicitly) are referred to the avram reference manual for information on how to access these features.

13.7 Series

The functions documented in this section are useful for operating on vectors or time series represented as lists of floating point numbers. 13.7.1 Accumulation

These three functions perform cumulative operations, each taking a list of numbers as input to a list of numbers as output. Differences are inverses of cumulative sums. cu prod Given a list hx :::x i this function returns the list hy :::y i for which 0 n 0 n i Y y D x i j jD0 . Here is a simple example of a cumulative product. $ fun flo --m="cu_prod <1.,2.,3.,4.,5.>" --c < 1.000000e+00, 2.000000e+00, 6.000000e+00, 2.400000e+01, 1.200000e+02>

$ fun flo --m="nth_diff1 <2.,8.,7.,1.>" --c <6.000000e+00,-1.000000e+00,-6.000000e+00> $ fun flo --m="nth_diff2 <2.,8.,7.,1.>" --c ←7.000000e+00,-5.000000e+00> $ fun flo --m="nth_diff3 <2.,8.,7.,1.>" --c <2.000000e+00> 13.7.2 Binary vector operations

These two functions compute the standard metrics on pairs of vectors. 332

13.7.3 Progressions These two functions allow arithmetic or geometric progressions to be constructed without explicit iteration required.

This example shows a list of four numbers from 25 to 40. $ fun flo --m="ari4/25. 40." --c < 2.500000e+01, 3.000000e+01, 3.500000e+01, 4.000000e+01> geo Given a natural number n this function returns a function that takes a pair of posi- tive floating point numbers .a;b/ to a list of n floating point numbers hx :::x i in 1 n geometric progression from a to b. That is, ` [U+00B4] i [U+0393] 1 b x D a exp ln i n[U+0393] 1 a The following example shows a geometric progression from 10 to 1000. $ fun flo --m="geo5/10. 1000." --c < 1.000000e+01, 3.162278e+01, 1.000000e+02, 3.162278e+02, 1.000000e+03>

13.7.4 Extrapolation These two functions can be used to extapolate a convergent series and thereby estimate the limit more efficiently than by direct computation. levin limit Given a list of floating point numbers hx :::x i, this function returns an estimate of 0 n the limit of x as n approaches infinity, based on the Levin-u transform from the GNU n Scientific library.

This example shows the limit of a geometric series of numbers approaching 1. $ fun flo --m="levin_limit <0.5,.75,.875,.9375>" --c 1.000000e-00 levin sum

13.8 Statistical A selection of functions pertaining to statistics is documented in this section. These in- clude descriptive statistics on populations, random number generators, and probability distributions.

13.8.1 Descriptive The following functions compute standard moments and related parameters for data stored in lists of floating point numbers. mean Given a list of n numbers hx :::x i, this function returns the population mean, de- 1 n fined as n X 1 xND x i n iD1

If the available data hx :::x i are a sample of the population rather than the whole popu- 1 n lation, a more statistically efficient estimator of the true mean has n[U+0393]1 in the denominator rather than n. Users working with sample data may wish to define a different version of this function accordingly. variance For a list of numbers hx :::x i, this function returns the variance, which is defined 1 n as n X 1 2 .x [U+0393]xN/ i n iD1 where xNis the mean as defined as above.

13.8.2 Generative A couple of functions are defined for pseudo-random number generation. Strictly speaking they are not really functions because they may map the same argument to different results on different occasions. rand This function returns a pseudo-random number uniformly distributed between zero and one.

The following example shows five uniformly distributed pseudo-random numbers. $ fun flo --m="rand* iota5" --c < 2.066991e-02, 9.812020e-01, 1.900977e-01, 5.668466e-01, 6.280061e-01> The results are derived from the virtual machine’s implementation of the Mersenne Twistor algorithm, as documented in the avram reference manual.

This function depends on the virtual machine’s interface to the R math library, which must be installed on host system in order for it to work. 13.8.3 Distributions The functions described in this section provide cumulative and inverse cumulative prob- ability densities. Currently only the standard normal distribution is supported, as defined above.

13.9 Conversion Three functions allow conversions between floating point numbers and other types.

Although natural numbers and positive integers have the same representation, the floatz function is necessary for coping with negative integers correctly. A negative argument to the float function will have an unspecified result. strtod This function takes a character string as input and returns a floating point number representation obtained by the strtod function from the host system’s C library. The same syntax for floating point numbers as in C is acceptable. If the syntax is not valid, a value of floating point 0 is returned. Here is an example of the strtod function. $ fun flo --m="strtod 6.023e23" --c 6.023000e+23

$ fun flo --m="printf/%0.5f pi" --c %s 3.14159

The higher I go, the crookeder it becomes. Al Pacino in The Godfather, Part III

A selection of functions in support of curve fitting or interpolation is provided in the fit library. These include piecewise polynomial and sinusoidal interpolation methods, avail- able in both IEEE standard floating point and arbitrary precision arithmetic by way of the virtual machine’s interface to the mpfr library. There are also functions for differentiation and higher dimensional interpolation. The functions in this chapter are suitable for finding exact fits for data sets associating a unique output with each possible input. Readers requiring least squares regression or generalizations thereof may find the lapack library helpful, particularly the functions dgelsd and dggglm, which are conveniently accessible by way of the virtual machine’s lapack interface as documented in the avram reference manual.

14.1 Interpolating function generators The functions in this section take a set of points as an argment and return a function fitting through the points as a result. plin Given a set of pairs of floating point numbers f.x ;y /:::.x ;y /g, this function re- 0 0 n n turns a function f such that f.x / D y for any .x ;y / in the data set, and f.x/ is the i i i i linearly interpolated y value for any intermediate x.

Piecewise linear interpolation is an expedient method based on approximating the given function with connected linear functions. An illustration is given in Figure 14.1. Note that there is no requirement for the points to be equally spaced. The following example shows how the plin function can be used.

$ fun flo fit --m="plin<(1.,2.),(3.,4.)>* ari5/1. 3." --c < 2.000000e+00, 2.500000e+00, 3.000000e+00, 3.500000e+00, 4.000000e+00> sinusoid Given a set of pairs of floating point numbers f.x ;y /:::.x ;y /g, this function re- 0 0 n n turns a function f such that f.x / D y for any .x ;y / in the data set, and f.x/ is the i i i i sinusoidally interpolated y value for any intermediate x.

For the latter function, The precision of numbers used in the calculations is determined by the precision of the numbers in the input data set. As the names imply, these functions use a sinusoidal interpolation method. For equally spaced values of x , the function that they construct is evaluated by i n X sin.!.x [U+0393]x // i f.x/ D y i x [U+0393]x iD0 i

for values of x other than x , with a suitable choice of !. i fflA function of this form has the property of being continuous and non-vanishing in all derivatives, and is also the minimum bandwidth solution. fflIf the numbers x are not equally spaced, the spacing is adjusted by a cubic spline i transformation to make this form applicable. fflLarge variations in spacing may induce spurious high frequency oscillations or dis- continuities in higher derivatives.

14.2 Higher order interpolating function generators The functions documented in this section allow for the construction of families of interpo- lating functions parameterized by various means. There is a piecewise polynomial inter- polation method with selectable order similar to the conventional cubic spline method, a higher dimensional interpolation function, and a function for differentiation of polynomi- als obtained by interpolation.

0.75

0.50

0.25

0.00 0.00 0.20 0.40 0.60 0.80 1.00

0.75

0.50

0.25

0.00 0.00 0.20 0.40 0.60 0.80 1.00 polynomial

1.00

0.75

0.50

0.25

0.00 0.00 0.20 0.40 0.60 0.80 1.00

The poly_dif function is specific to polynomial interpolating functions because it de- compiles them based on the assumption that they have a certain form. The derivative function from the flo library can be used for differentiation in more general cases. How- ever, differentiation by the poly_dif function is more accurate and efficient where pos- sible. Figure 14.3 shows plots of the first derivatives of the polynomial functions in Fig- ure 14.2 as obtained by the poly_dif function. Figure 14.4 shows the same functions differentiated by the derivative function for comparison, as well as the first derivative of the sinusoidal interpolation. fflIt can be noted from these figures that the piecewise interpolation is continuous but not smooth in the first derivative, and hence discontinuous in higher derivatives. 344

-4.47 -6.82 0.00 0.20 0.40 0.60 0.80 1.00

-1.52

-3.54 -5.57 0.00 0.20 0.40 0.60 0.80 1.00

-0.10 -5.55

-11.00

-16.46 -21.91 0.00 0.20 0.40 0.60 0.80 1.00

As you are undoubtedly gathering, the anomaly is systemic, creating fluctuations in even the most simplistic equations. The Architect in The Matrix Reloaded

Several functions meant to expedite the task of mapping infinite continua to finite or semi- infinite subsets of themselves are provided by the cop library. Aside from general math- ematical modelling applications, the main motivation for these functions is to adapt an unconstrained non-linear optimization solver such as minpak to constrained optimiza- tion problems by a change of variables. The non-linear optimizers currently supported by virtual machine interfaces, minpack and kinsol, also allow a Jacobian matrix to be supplied by the user in either of two forms, which can be evaluated numerically by functions in this library.

15.1 Changes of variables The functions documented in this section pertain to continuous maps of infinite intervals to finite or semi-infinite intervals.

4.00

3.00

2.00

1.00

0.00 -5 -4 -3 -2 -1 0 1 2 3 4 5 x

0.278 0.277

0.276

0.275 0.274

0.273 0.272 3.00 3.40 3.80 4.20 4.60 5.00 x

15.2 Partial differentiation The functions documented in this section are suitable for obtaining partial derivatives of real valued functions of several variables.

Listing 15.1 example of Jacobian function usage #import std #import nat #import flo #import cop f = <.plus:-0.,sin+_&th,times+&hthPX> d = %eLLP (jacobian(3,2) f) <1.4,2.7>

A more complicated example of the jacobian function is shown in Listing 1.6 on page 33. jacobian row Given a natural number n, this function constructs a function that takes a function n m n n f : R ! R as an input, and returns a function J : .f0:::m[U+0393]1g[U+0398]R / ! R as an output. fflThe input to f is represented as a list of floating point numbers hx :::x i. 1 n

Can you learn stuff that you haven’t been programmed with, so you can be, you know, more human, and not such a dork all the time? John Connor in Terminator 2 — Judgment Day

The lin library contains functions and data structures in support of linear programming problems. These features attempt to present a convenient, high level interface to the virtual machine’s linear programming facilities, which are provided currently by the free third party libraries glpk and lpsolve. Enhancements to the basic interface include symbolic names for variables, positive and negative solutions, and costs proportional to magnitudes. A few standard matrix operations are also included in this library as wrappers for the more frequently used virtual machine library functions, such as solutions of sparse systems and solutions in arbitrary precision arithmetic using the mpfr library. Replacement functions implemented in virtual code are automatically invoked on plat- forms lacking interfaces to some of these libraries (lapack, umf, and lpsolve or glpk). These allow a nominal form of cross platform compatibility, but are not com- petitive in performance with native code implementations.

16.1 Matrix operations The mathematical concept of an n[U+0398]m matrix has a concrete representation as a list of lists of numbers, with one list for each row of the matrix as this diagram depicts. 0 1 < a ::: a 11 1m <a :::a >, : : 11 1m @ : A : : : : , : : : : : a ::: a n1 nm <a :::a >> n1 nm This representation is assumed by the matrix operations documented in this section except as otherwise noted, and by the virtual machine model in general.

16.2 Continuous linear programming There are two linear programming solvers in this library, with one closely following the calling convention of the virtual machine interfaces to glpk and lpsolve, and the other allowing a higher level, symbolic specification of the problem. The latter employs a record data structure as documented below.

16.2.1 Data structures The linear programming problem in standard form is that of finding an n [U+0398] 1 matrix X to minimize a cost CX for a known 1 [U+0398] n matrix C, subject to the constraints that AX D B for given matrices A and B, and all X [U+02D8] 0. i1 P n Letting x D X , b D B , c D C , and z D c x the constraint AX D B is i i1 i i1 i 1i i i iD1 equivalent to a system of linear equations. n X A x D b ij j i jD1 In practice, most A values are zero. A more user-friendly formulation of this problem ij than the standard form would admit the following features. fflconstraints on the variables x having arbitrary upper and lower bounds i

16.2.2 Functions The following functions are used in solving linear programming problems.

The replacement function is implemented purely in virtual code without calling lpsolve or glpk and can serve as a correct reference implementation of a linear programming solver for testing purposes, but it is too slow for production use, mainly because it exhaus- tively samples every vertex of the convex hull.

16.3 Integer programming Integer programming problems are an additionally constrained form of linear program- ming problems in which the solutions x are required to take integer values. If some but not i all x are required to be integers, then the problem is called a mixed integer programming i problem. Current versions of the virtual machine can be configured with an interface to the lpsolve library providing for the solution of integer and mixed integer programming

I don’t set a fancy table, but my kitchen’s awful homey. Anthony Perkins in Psycho

This chapter documents a small selection of functions intended to facilitate the construc- tion of tables of numerical data with publication quality typesetting. These functions are particularly useful for tables with hierarchical headings that might be more difficult to typeset manually, and for tables whose contents come from the output of an application developed in Ursala. A The tables are generated as LT X code fragments meant to be included in a document or E A presentation. They require the document that includes them to use the LT X booktabs E package. The functions are defined in the tbl library.

17.1 Short tables A table is viewed as having two parts, which are the headings and the body. fflThe body is a list of columns, wherein each column is either a list of character strings or a list of floating point numbers. fflThe headings are a list of trees of lists of strings (type %sLTL).  — Each non-terminal node in a tree is a collective heading for the subheadings below it.  — Each terminal node is a heading for an individual column.  — The total number of terminal nodes in the list of trees is equal to the number of columns. A The character strings in the table headings or columns can contain any valid LT X code. E Its validity is the user’s responsibility.

atable = (headings,body) with further variations possible. In any case, the table may then be incorporated into a document by a code fragment such as the following. … \caption{the tables are turning} This code fragment is based on the assumption that the user intends to have the table centered in a floating table environment, with a caption and label, but these choices are all at the user’s option. Only the actual tabular environment is stored in the file. Also note that the file name is the same as the identifier used in the source with the .tex suffix A appended, but the suffix is implicit in the LT X code. See Section 7.4.4 on page 263 for E more information about the #output directive. The result from Listing 17.1 is shown in Table 17.1. As the example shows, headings with multiple strings are typeset on multiple lines, all headings are vertically centered, and all columns are right justified. A more complicated example of table heading specifications is shown on page 49 and the result displayed in Table 1.1. These headings are generated algorithmically by the user application in Listing 1.11.

Listing 17.1 simple example of the table function usage #import std #import nat #import tbl

headings = # a list of trees of lists of strings < <'name'>[U+02C6]: <>, # table heading <'foo'>[U+02C6]: < <'bar',baz>[U+02C6]: <>, # subheadings <'rank'>[U+02C6]: <>>>

body = # list of lists of either strings or numbers < <'x',y,z>, # each list is a column <1.,2.,3.>, <4.,5.,6.>>

#output dot’tex' ~& atable = table3(headings,body)

Listing 17.2 usage of the sectionedtable function #import std #import nat #import tbl headings = # a list of trees of lists of strings < <'name'>[U+02C6]: <>, <'foo'>[U+02C6]: <<'bar',baz>[U+02C6]: <>,<'rank'>[U+02C6]: <>>>

body = # a list of lists of columns < <<'u',v,w>,<7.,8.,9.>,<0.,1.,2.>>, <<'x',y,z>,<1.,2.,3.>,<4.,5.,6.>>> #output dot’tex' ~&

setab = sectioned_table3(headings,body)

17.2 Long tables A couple of functions documented in this section are useful for constructing tables that are A too long to fit on a page. These require the document that includes them to use the LT X E longtable package. The general approach is to construct tables normally by one of the functions described previously (table or sectioned_table), and then to transform the result to a long

table format by way of a post processing operation. The longtable environment com- bines aspects of the ordinary table and tabular environments, precluding postpone- ment of the choice of a caption and label as in previous examples, and hence requiring calling conventions such as the following. elongation A Given a character string containing LT X code specifying a title, this function returns E a function that transforms a given tabular environment in a list of strings to the corresponding longtable environment having that title. A typical usage of this function would be in an expression of the form elongationhtitlei .[sectioned_]table n/ .hheadingsi;hbodyi/

A typical usage of this function would be in an expression of the form labelhnamei elongationhtitlei .[sectioned_]table n/ .hheadingsi;hbodyi/ A The table thus obtained can be cross referenced in the document by the usual LT X label E

17.3 Utilities A further couple of functions described in this section may be helpful in preparing the contents of a table.

Listing 17.3 some uses of the vwrap function #import std #import nat #import tbl #output dot’tex' table0

chab = # ISO codes for upper and lower case letters vwrap5( _{&iNCNVS <'letter',code>, <.}&rNCS,_{&hS+ %nP*+} &lS> ~&riK10\letters num characters) pows = # first seven powers of numbers 1 to 7

vwrap7( _{&iNCNVS <'$n$,$m$,$n[U+02C6]m$'>,} &hSS %nP** <._&lS,&rS,power*> ~&ttK0 iota 8)

This function can be demonstrated as follows. $ fun tbl --m="scientific_notation 6.022e+23" --c %s 23 The result appears as 6.022[U+0398]10 in a typeset document. The scientific_notation function need not be invoked explicitly to get this effect in a table, because it applies automatically to any column whose entries are char- acter strings in exponential format. Floating point numbers can be converted to strings in exponential format by the printf function as explained in Section 13.9.

The core network of the grid must be accessed. The Keymaker in The Matrix Reloaded

Data of type t%G, using the grid type constructor explained in Chapter 3, are supported by a variety of operations defined in the lat library and documented in this chapter. These include basic construction and deconstruction functions, iterators analogous to some of the usual operations on lists, and higher order functions implementing the induction patterns that are the main reason for using lattices.

18.1 Constructors The first thing necessary for using a lattice is to construct one, which can be done easily by the grid function.

The grid function allows the input list of adjacency relations to be truncated if subsequent relations are the same as the last one in the list. A few small examples of lattices constructed by this function should clarify the de- scription. In these examples, the verticies are the characters a, 'b, 'c and 'd, expressed in strings rather than lists for brevity. The first example shows a fully connected lattice, 1 which is obtained by using a (truncated) list of adjacency relations that are always true. $ fun lat --m="grid/<'a,ab,abc,abcd> <&!>" --c %cG < [0:0: 'a[U+02C6]: <1:0,1:1>], [ 1:1: 'b[U+02C6]: <2:0,2:1,2:2>, 1:0: 'a[U+02C6]: <2:0,2:1,2:2>], [ 2:2: 'c[U+02C6]: <2:0,2:1,2:2,2:3>, 2:1: 'b[U+02C6]: <2:0,2:1,2:2,2:3>, 2:0: 'a[U+02C6]: <2:0,2:1,2:2,2:3>], [ 2:3: 'd[U+02C6]: <>, 2:2: 'c[U+02C6]: <>, 2:1: 'b[U+02C6]: <>, 2:0: 'a[U+02C6]: <>]> This example shows a lattice with each letter connected only to those that don’t precede it in the alphabet.

$ fun lat --m="grid/<'a',ab,abc,abcd> <lleq>" --c %cG < [0:0: 'a[U+02C6]: <1:0,1:1>], [ 1:1: 'b[U+02C6]: <2:1,2:2>, 1:0: 'a[U+02C6]: <2:0,2:1,2:2>], [ 2:2: 'c[U+02C6]: <2:2,2:3>, 2:1: 'b[U+02C6]: <2:1,2:2,2:3>, 2:0: 'a[U+02C6]: <2:0,2:1,2:2,2:3>], [ 2:3: 'd[U+02C6]: <>, 2:2: 'c[U+02C6]: <>, 2:1: 'b[U+02C6]: <>, 2:0: 'a[U+02C6]: <>]> The next example shows the degenerate case of a lattice obtained by using equality as the adjacency relation, resulting in most letters being unreacheable and therefore omitted. 1 Remember to execute set +H before trying this example to suppress interpretation of the exclamation point by the shell. 370

$ fun lat --m="grid/<'a',ab,abc,abcd> ⇐⇒" --c %cG < [0:0: a[U+02C6]: <0:0>], [0:0: 'a[U+02C6]: <0:0>], [0:0: 'a[U+02C6]: <0:0>], [0:0: 'a[U+02C6]: <>]> Finally, we have an example of a lattice generated with a branching pattern chosen at random. Each vertex has a 50% probability of being connected to each vertex in the next level. $ fun lat --m="grid/<'a,ab,abc,abcd> <50%~>" --c %cG < [0:0: 'a[U+02C6]: <1:0,1:1>], [1:1: 'b[U+02C6]: <1:0,1:1>,1:0: 'a[U+02C6]: <1:0>], [1:1: 'c[U+02C6]: <2:1,2:2>,1:0: 'a[U+02C6]: <2:0>], [2:2: 'd[U+02C6]: <>,2:1: 'c[U+02C6]: <>,2:0: 'b[U+02C6]: <>]> Along with constructing a lattice goes the need to deconstruct one in order to access its components. Several functions for this purpose follow.

This function may be useful in user-defined ad hoc lattice deconstruction functions. Here is an example. $ fun lat --m="edges grid/<'a',ab,abc> <&!>" --c %aLL <1:0

$ fun lat --m="sever grid/<'a',ab,abc> <&!>" --c %cGG < [ 0:0: [U+02C6]:<1:0,1:1> < [0:0: 'a[U+02C6]: <1:0,1:1>], [ 1:1: 'b[U+02C6]: <2:0,2:1,2:2>, 1:0: 'a[U+02C6]: <2:0,2:1,2:2>], [2:2: 'c[U+02C6]: <>,2:1: 'b[U+02C6]: <>,2:0: 'a[U+02C6]: <>]>], [ 1:1: [U+02C6]:<2:0,2:1,2:2> < [0:0: 'b[U+02C6]: <2:0,2:1,2:2>], [2:2: 'c[U+02C6]: <>,2:1: 'b[U+02C6]: <>,2:0: 'a[U+02C6]: <>]>, 1:0: [U+02C6]:<2:0,2:1,2:2> < [0:0: 'a[U+02C6]: <2:0,2:1,2:2>], [2:2: 'c[U+02C6]: <>,2:1: 'b[U+02C6]: <>,2:0: 'a[U+02C6]: <>]>], [ 2:2: (<[0:0: 'c[U+02C6]: <>]>)[U+02C6]: <>, 2:1: (<[0:0: 'b[U+02C6]: <>]>)[U+02C6]: <>, 2:0: (<[0:0: 'a[U+02C6]: <>]>)[U+02C6]: <>]>

18.2 Combinators The functions documented in this section are analogues to functions and combinators nor- mally associated with lists, such as maps, folds, zips, and distributions. All of them require lattices with a unique root vertex. ldis Given a pair .x;g/ where g is a lattice, this function returns a lattice derived from g by substituting each vertex v in g with the pair .x;v/.

This function is analogous to distribution on lists, and can be demonstrated as follows. $ fun lat -m="ldis/1 grid/<'a',ab,abc> <&!>" -c %ncXG < [0:0: (1,'a)[U+02C6]: <1:0,1:1>], [ 1:1: (1,'b)[U+02C6]: <2:0,2:1,2:2>, 1:0: (1,'a)[U+02C6]: <2:0,2:1,2:2>], [ 2:2: (1,'c)[U+02C6]: <>, 2:1: (1,'b)[U+02C6]: <>, 2:0: (1,'a)[U+02C6]: <>]>

The lmap combinator on lattices is analogous to the map combinator on lists. This exam- ple shows the lmap of a function that duplicates its argument. $ fun lat --m="(lmap ~&iiX) grid/<'a',ab> <&!>" --c %cWG < [0:0: ('a,'a)[U+02C6]: <1:0,1:1>], [1:1: ('b,'b)[U+02C6]: <>,1:0: ('a,'a)[U+02C6]: <>]>

This function is comparable the the zip function on lists. The following example shows a lattice zipped to a copy of itself. $ fun lat --m="lzip (_{&iiX grid/<'a',ab> <&!>)" --c %cWG < [0:0: ('a,'a)[U+02C6]: <1:0,1:1>], [1:1: ('b,'b)[U+02C6]: <>,1:0: ('a,'a)[U+02C6]: <>]> This operation has the same effect as the previous example, because lmap} &iiX is equivalent to lzip+ ~&iiX.

18.3 Induction patterns The benefit of working with a lattice is in effecting a computation by way of one or more of the transformations documented in this section. These allow an efficient, systematic pattern of traversal through a lattice, visiting a user defined function on each vertex, and allowing it to depend on the results obtained from neighboring vertices. Directions of traversal can be forward, backward, sideways, or a combination. These operations are also composable because the inputs and outputs are lattices in all cases. Many of the algorithms concerning lattices have analogous tree traversal algorithms. As the previous example demonstrates, a lattice of type t%G can be converted to a tree of type t%T without any loss of information, and operating on the tree would be more convenient if it were not exponentially more expensive, because the tree is a simpler and more abstract representation. The combinators documented in this section therefore attempt to present

Listing 18.1 lattice transformation examples #import std #import nat #import lat x = grid/<'a',bc,def,ghij> <&!> xpress = bwi :[U+02C6]/_&l &rdS; _{&i&& :/(+ --)+ mat, paths = fwi [U+02C6]rlrDlShiX2lNXQ\}&rv _&l?\&rdNCNC _{&rdPlLPDrlNCTS roll = swi [U+02C6]H\}&r -$+ ~&lizyCX

neighbors = fswi [U+02C6]~&rdvDlS :[U+02C6]/_{&ll [U+02C6]T(} &lrNCC+ _{&rilK16rSPirK16lSPXNNXQ+} &rdPlrytp2X, ~&rvdSNC)

an interface to the user application whereby the lattice appears as a tree as far as possible. In particular, it is never necessary for the application to be concerned explicitly with the address fields in a lattice.

which is designed to operate on an argument of the form .v;hz :::z i/, for a character 0 n 375

v and a list of trees of strings z . It returns a single character string by flattening and i parenthesizing the roots of the trees and inserting the character v at the head. The subtrees of z are ignored. With Listing 18.1 stored in a file named lax.fun, this function can be i demonstrated as follows. $ fun lat lax -m="xpress grid/<'a',bc,def> <&!>" -c %sG < [0:0: a(b(d,e,f),c(d,e,f))[U+02C6]: <1:0,1:1>], [ 1:1: c(d,e,f)[U+02C6]: <2:0,2:1,2:2>, 1:0: b(d,e,f)[U+02C6]: <2:0,2:1,2:2>], [2:2: f[U+02C6]: <>,2:1: e[U+02C6]: <>,2:0: d[U+02C6]: <>]>

The example of forward induction in Listing 18.1 demonstrates the general form of an algorithm to compute all possible paths from the root to each vertex in a lattice. This type of problem might occur in practice for valuing path dependent financial derivatives. The argument to the fwi combinator [U+02C6]rlrDlShiX2lNXQ~&rv _&l?\&rdNCNC _{&rdPlLPDrlNCTS takes an argument .i;z/ in which z is tree of characters derived from the input lattice, and i is a list of lists of paths, each being inherited from a different ancestor. If i is empty, the list of the singleton list of the root of z is constructed by} &rdNCNC, but otherwise, i is flattened to a list of paths and the root of z is appended to each path by

~&rdPlLPDrlNCTS. The pair returned by this function .w;b/ has a copy of this result as w, and a list of copies of it in b, with one for each descendent of z. The paths function using this forward induction algorithm in Listing 18.1 can be demonstrated as follows. $ fun lat lax --m="paths x" --c %sLG < [0:0: <'a'>[U+02C6]: <1:0,1:1>], [ 1:1: <'ac'>[U+02C6]: <2:0,2:1,2:2>, 1:0: <'ab'>[U+02C6]: <2:0,2:1,2:2>], [ 2:2: <'abf',acf>[U+02C6]: <2:0,2:1,2:2,2:3>, 2:1: <'abe',ace>[U+02C6]: <2:0,2:1,2:2,2:3>, 2:0: <'abd',acd>[U+02C6]: <2:0,2:1,2:2,2:3>], [ 2:3: <'abdj',acdj,abej,acej,abfj,acfj>[U+02C6]: <>, 2:2: <'abdi',acdi,abei,acei,abfi,acfi>[U+02C6]: <>, 2:1: <'abdh',acdh,abeh,aceh,abfh,acfh>[U+02C6]: <>, 2:0: <'abdg',acdg,abeg,aceg,abfg,acfg>[U+02C6]: <>]> As this example suggests, some pruning may be required in practice to limit the inevitable combinatorial explosion inherent in computing all possible paths within a larger lattice.

But then if we do not ever take time, how can we ever have time? The Merovingian in The Matrix Reloaded

A small library of functions, stt, exists for the purpose of converting calendar times between character strings and natural number representations.

I wish you could see what I see. Neo in The Matrix Revolutions

A library named plo for plotting graphs of real valued functions along the lines of Fig- ures 15.1 and 15.2 is documented in this chapter. Features include linear, logarithmic and non-numeric scales, variable line colors and styles, arbitrary rotation of axis labels, in- A clusion of LT X code fragments as annotations, scatter plots, and piecewise linear plots. E More sophisticated curve fitting can be achieved by using this library in combination with the fit library documented in Chapter 14. The main advantages of this library are that it allows data visualization to be readily integrated with with numerical applications developed in Ursala, and the results generated A in LT X code will match the fonts of the document or presentation in which they are E included. The intention is to achieve publication quality typesetting.

20.1 Functions A plot is normally specified in its entirety by a record data structure which is then translated A as a unit to LT X code by the following functions. E plot A Given a record of type visualization, this function returns a LT X code frag- E ment as a list of character strings that will generate the specified plot. A In order for a plot generated by this function to be typeset in a LT X document, the E document preamble must contain at least these lines.

Listing 20.1 a nearly minimal example of a plot #import std #import plo #output dot’tex' plot

f = visualization[ curves: <curve[points: <(0.,0.),(1.,1.),(2.,-1.),(3.,0.)>]>]

It is also recommended to include the command \psset.5pt,arrowinset=0,arrowscale=1.1 An example demonstrating the plot function is shown in Listing 20.1, and the result- ing plot in Figure 20.1. In practice, the points in the plot are more likely to be algorith- mically generated than enumerated as shown, but it is often appropriate to use the plot A function as a formatting function in an #output directive. Doing so allows the LT X file E to be generated as follows. $ fun plo plex.fun fun: writing f.tex where plex.fun is the name of the file containing Listing 20.1. The plot stored in A E visualization record structure used in this example is explained in the next section.

20.2 Data structures A basic vocabulary of useful concepts for describing a plot is as follows. fflA planar cartesian coordinate system denominated in points, where 1 inch D 72 points, fixes any location with respect to the plot

However, if a value for the placer field is specified by the user, it is employed in the coordinate transformation. The axis record has several other automatic initialization features. fflZero values are inferred for unspecified rotation and alias.

fflIf the intercept is unspecified, the plot function positions an axis on the view- port boundary. fflIf the hats field is unspecified, it is determined from the hatches field.  — Symbolic hatches (i.e., character strings) are copied verbatim to the hats field.  — Numeric hatches are translated to character strings either in fixed or scientific notation, depending on the dynamic range. fflIf the hatches field is not specified but the hats field is a list of strings in fixed or exponential notation, the hatches field is read from it using the math..strtod library function. When the axis forms part of a visualization record, further initialization of the hatches field is performed automatically, because its values are implied by the curves.

curve This function is the mnemonic for a record data structure representing a curve to be plotted, of which there are a list in the curves field of a visualization record. The curve record has the following fields. fflpoints — a list of pairs h.x ;y /:::.x ;y /i representing the data to be plotted, 0 0 n n where x and y can be character strings or floating point numbers i i fflpeg — a value that’s constant along the curve if it’s a function of two variables fflattributes — a list of assignments of attributes to keywords recognized by A the LT X pstricks package to describe line colors and styles E ffldecorations — a list of triples h..x ;y /;s /:::..x ;y /;s /i where x and 0 0 0 n n n i y are coordinates consistent with the points field indicating the placement of i A a LT X code fragment s on the plot, where s is a list of character strings E i i fflscattered — a boolean value causing the points not to be connected when plotted if true ffldiscrete — a boolean value causing points to be disconnected and also causing each point to be plotted atop a vertical line if true

Listing 20.2 demonstration of decorations, attributes, and axes #import std #import plo #import flo #output dot’tex' plot

plop = visualization[ picture_frame: 400., abscissa: axis[ hats: printf/*%0.2f ari13/0. 3., variable: time ($\mu s$)], ordinates: < axis[variable: feelgood factor (erg$/$lightyear$[U+02C6]2$)]>, curves: < curve[points: <(0.,0.),(1.,1.),(2.,-1.),(3.,0.)>], curve[ decorations: ~&iNC/(0.35,-0.6) -[ \pssetblack \psline{-}(0,0)(10,0) \pssetlightgray \psline{-}(0,20)(10,20) \put(-10,-15){dashbox(75,50){}} attributes: <'linecolor': lightgray>, points: <(0.,0.),(3.,1.5)>]>]

20.3 Examples

A possible way of using this library without reading all of the preceding documentation is to copy one of the examples from this section and modify it to suit, referring to the

1.00

0.50

0.00

-1.00 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 time ([U+00AF]s)

Listing 20.3 symbolic axes, rotation, margins, discrete curves, generated data, and interpolation #import std #import nat #import plo #import flo #import fit data = ~&p(ari7/0. 1.,rand* iota 7)

#output dot’tex' plot slam = visualization[ margin: 35., picture_frame: 400., abscissa: axis[ rotation: -60., hats: < impulse, light speed, ludicrous speed, ridiculous speed>, variable: velocity ($v$)], ordinates: _{&iNC axis[ hatches: ari11/0. 1., variable: tunneling probability ($\rho$)], curves: < curve[discrete: true,points: data], curve[ points: [U+02C6](}&,sinusoid data)* ari200/0. 1., attributes: <'linecolor': lightgray>]>]

documentation only as needed. Most of the features are exemplified at one point or another. Listing 20.2 demonstrates multiple curves with different attributes, and user-written A LT X code decorations inserted "inline". Note that the coordinates of the decorations are E in terms of those of the curve, rather than being absolute point locations, so they will scale automatically if the bounding box size is changed. The results are shown in Figure 20.2. Listing 20.3 and the results shown in Figure 20.3 demonstrate an axis with symbolic rather than numeric hatches. In this case, the data are numeric and the axis labels are chosen arbitrarily, but data that are themselves symbolic can also be used. Further features of this example: fflthe discrete plotting style, wherein the points are separated from one another but connected to the horizontal axis by vertical lines. ffla smooth curve generated using the sinusoid interpolation function from the fit

0.70 0.60 0.50 0.40 0.30

0.20 0.10 0.00 impulse light speed ludicrous speed ridiculous speed velocity (v)

Listing 20.4 aliases, intercepts, margins, and selective hats #import std #import nat #import plo #import flo #output dot’tex' plot

para = visualization[ margin: 25., picture_frame: 400., abscissa: axis[ hats: printf/%0.2f ari9/-1. 1., alias: (205.,27.), variable: $x$], ordinates: _{&iNC axis[ alias: (8.,0.), intercept: <0.>, hats:} &NtC printf/%0.2f ari5/0. 1., variable: $y$], curves: <curve[points: [U+02C6](~&,sqr)* ari200/-1. 1.]>]

The scattered plot style is similar to the discrete style but omits the vertical lines. Listing 20.4 and the results in Figure 20.4 demonstrate some possibilities for position- ing axes and labels. The vertical axis is displayed in the center by way of the intercept, and the label x of the horizontal axis is displayed to the right rather than below. The zero on the vertical axis is suppressed in the hats field of the ordinate so as not to clash with the horizontal axis. Some manual adjustment to the margins and bounding box are made based on visual inspection of the bounding box in draft versions. The last example in Listing 20.5 and Figure 20.5 shows how multiple functions can be plotted on different vertical scales with the same horizontal axis. With two ordinates and two curves, each refers to its own. A logarithmic scale is automatically inferred for the right ordinate because the hatches are given as a geometric progression. A decoration for each curve reduces ambiguity by identifying the function it represents and hence the corresponding vertical axis.

Listing 20.5 logarithmic scales, decorations, and multiple ordinates #import std #import nat #import plo #import flo #output dot’tex' plot

gam = visualization[ picture_frame: 400., margin: 50., abscissa: axis[variable: $x$,hats: _{&hS %nP*} &tt iota 7], ordinates: < axis[variable: $\Gamma'(x)$,hats: printf/%0.1f' ari6/0. 2.], axis[variable: $\Gamma(x)$,hatches: geo6/1. 120.]>, curves: < curve[ ordinate: &h, decorations: <((2.8,1.0),-[$\Gamma'$]-)>, points: [U+02C6](_{&,rmath..digamma)} ari200/2. 6.], curve[ ordinate: &th, decorations: <((4.8,10.),-[$\Gamma$]-)>, points: [U+02C6](&,rmath..gammafn)* ari200/2. 6.]>]

Figure 20.5: gamma and digamma function plots with different vertical scales from Listing 20.5

It’s a way of looking at that wave and saying "Hey Bud, let’s party". Sean Penn in Fast Times at Ridgemont High

Following on from the previous chapter, a library called ren uses the same data structures to depict functions of two variables graphically as surfaces. The rendering algorithm fea- tures correct perspective and physically realistic shading of surface elements based on a A choice of simulated semi-diffuse light sources. The renderings are generated as LT X code E depending on the pstricks package, so that hidden surface removal is accomplished by the back end Postscript rendering engine. The user has complete control over the choice of a focal point, and scaling of the image both in the image plane and in 3-space.

21.1 Concepts To depict a function of two variables as a surface, a specification needs to be given not only of the function, but of certain other characteristics of the image. These include its focal point relative to a hypothetical three dimensional space, which can be understood as the position of an observer or a simulated camera viewing the surface, and the position of a simulated light source. Regardless of its relevance to the data, shading consistent with a light source is necessary for visual perception. There are also the same requirements for specifying the axis labels and hatches as in a two dimensional plot. The conventions whereby this information is specified are documented in this section.

21.1.1 Eccentricity 2 A function f : R ! R defined on a region [a ;a ] [U+0398] [b ;b ] is depicted as a surface 0 1 0 1 3 confined to the cube with corners f0;1g in a right handed cartesian coordinate system. Each input .x;y/ in the region is associated with a point in the unit square on the horizontal plane, and the value of f.x;y/ is indicated by the height of the surface above that point.

y [U+00BF] 1

y D 1

y [U+00A1] 1

The surface is always rendered from the point of view of an observer looking directly at the center of the prism described above, regardless of its eccentricity, but the position of the observer is a tunable parameter with three degrees of freedom. The position can be specified in principle by its cartesian coordinates, but it is convenient to encode frequently used families of coordinates as shown in Table 21.2. A specification of observer coordinates for one of these standard positions is a string of

the form [ijo] [ljmjh] [ejnjwjs] [+j-] fflThe first field, mnemonic for "in" or "out" determines the zoom, which is the distance of the observer from the center of the cube. The image is scaled to the same size regardless of the distance, but the inner position results in more pronounced apparent convergence of parallel lines due to perspective. fflThe second field, mnemonic for "low", "medium" or "high", refers to the angle of el- evation. The angle is formed by the vector from the center of the cube to the observer ffi ffi ffi with the horizontal plane. These angles are defined as 20 , 35 , and 50 , respectively. fflThe third field, mnemonic for "east", "north", "west" or "south", indicates the ap- proximate lateral angular displacement of the observer, with e referring to the posi- tive x direction, and n referring to the positive y direction. fflBecause it is less visually informative to sight orthogonally to the axes, the last field of - or + indicates a clockwise or counterclockwise displacement, respectively, of ffi 35 from the direction indicated by the preceding field.

The cartesian coordinates shown in Table 21.2 apply only to the case of neutral eccen- tricity. For oblong boxes, the positions are scaled accordingly to maintain these angular displacements. The effects of zooms, elevations, and lateral angular displacements are demonstrated in Tables 21.3 and 21.4, with Table 21.4 showing various views of the same quadratic surface. 21.1.3 Illumination The library provides three alternatives for light source positions in a rendering, which are left, right, and back lighting. The most appropriate choice depends on the shape of the surface being rendered and the location of the observer. fflleft lighting postulates a light source above and behind the focal point to the left

medium

quadrant + -

e+ = n-

n+ = w-

w+ = s-

s+ = e-

light source visual effect

21.2 Interface Use of the library is fairly simple when the concepts explained in the previous section are understood.

Listing 21.1 short example of a rendering #import std #import nat #import plo #import ren

#output dot’tex' left_lit_rendering/(ilw+,()) surf =

visualization[ picture_frame: 280., margin: 65., headroom: 35., viewport: (210.,210.), abscissa: axis[variable: $x$,hats: <'0',1,2,3>], pegaxis: axis[variable: $y$,hatches: <1.,5.,9.>], ordinates: <axis[variable: $z$]>, curves: < curve[peg: 1.,points: <(0.,2.),(1.,3.),(2.,4.),(3.,5.)>], curve[peg: 5.,points: <(0.,1.),(1.,2.),(2.,3.),(3.,4.)>], curve[peg: 9.,points: <(0.,0.),(1.,1.),(2.,2.),(3.,3.)>]>]

You talkin' to me? Robert De Niro in Taxi Driver

An unusual and powerful feature of Ursala is its interoperability with command line inter- preters such as shells and computer algebra systems. Ready made interfaces are provided for the numerical and statistical packages Octave, R, and scilab, the computer alge- bra systems axiom, maxima, and pari-gp, and the number theory package gap. These interfaces make any interactive function from these packages callable within the language, even if the function is user defined and not included in the package’s development library. There are also interfaces to the standard shells bash and psh (the perl shell), and to privileged shells opened by the su command. Orthogonal to the choice of an application package or shell is the option to access it locally or on a remote host via ssh. The above mentioned packages incorporate an extraordinary wealth of mathematical expertise, and with their extensible designs and scripting languages, each is a capable programming platform by itself. However, for a developer choosing to work primarily in Ursala, the value added by the interfaces documented in this chapter is the flexibility to leverage the best features of all of these packages from a single application with a minimum of glue code.

22.1 Theory of operation The application packages or shells are required to be installed on the local host or the remote host in order to be callable from the language. In the latter case, the remote host needs an ssh server and the user needs a shell account in it, but the compiler and virtual machine need only be installed locally. Installation of these applications is a separate issue beyond the scope of this manual, but it is fairly painless at least for Debian and Ubuntu users who are familiar with the apt-get utility.

22.1.1 Virtual machine interface These shells are spawned and controlled at run time by the virtual machine through pipes to their standard input and output streams, as implemented by the expect library. Hence, no dynamic loading takes place in the conventional sense. Furthermore, any console output they perform is not actually displayed on the user’s console, but recorded by the virtual machine. However, any side effects of executing them persist on the host.

22.1.2 Source level interface Although a very general class of interaction protocols can be specified in principle, full use demands an understanding of the calling conventions followed by the virtual machine’s interact combinator as documented in the avram reference manual. As an alternative, the functions defined cli library documented in this chapter insulate a developer from some of these details for a restricted but useful class of interactions, namely those involving a sequence of commands to be executed unconditionally. Several options exist for users requiring repetitive or conditional execution of external shell commands. In order of increasing difficulty, they include fflmultiple shell invocations with intervening control decisions at the source level ffla user defined command in the application’s native scripting language, if any ffla hand coded client/server interaction protocol

22.1.3 Referential transparency A more complex issue of interaction with external applications is the possible loss of 1 referential transparency. Although the code generated by the cli library functions can be invoked and treated in most respects as functions, it is incumbent on the user to recognize and to anticipate the possibility of different outputs being obtained for identical inputs on different occasions. The compiler for its part will detect the interact combinator on the virtual code level and refrain from performing any code optimizations depending on the assumption of referential transparency.

22.2 Control of command line interpreters Several functions concerned with sending commands to a shell and sensing its responses are documented in this section. These are higher order functions parameterized by a data structure of type _shell that isolates the application specific aspects of each shell (e.g., syntactic differences between computer algebra systems). The data structure is docu- mented subsequently in this chapter for users wishing to implement interfaces to other applications than those already provided, but may be regarded as an opaque type for the present discussion. 1 the property of pure functional languages guaranteeing run-time invariance of the semantics of any expression, even those including function calls

22.2.1 Quick start To invoke and interrogate one of the supported shells on the local host with any sequence of non-interactive commands, the function described below is the only one needed.

22.2.2 Remote invocation The next simplest scenario to the one above is that of a shell or application installed on a remote host. Assuming the host is accessible by ssh (the industry standard secure shell protocol), and that the user is an authorized account holder, the following functions allow convenient remote invocation.

22.3 Defined interfaces

As indicated in the previous section, ask and related functions are parameterized by a data structure of type _shell, which specifies how the client should interact with the ap- plication. It also determines the types of objects that may be declared in the application’s environment or workspace, and generates the necessary initialization commands and set- tings. Although a compatible specification for any shell can be defined by the user, some of 407

the most useful ones are defined in the library as a matter of convenience, and documented in this section.

22.3.1 General purpose shells It is possible for an application in Ursala to execute arbitrary system commands by inter- acting with a general purpose login shell. When such a shell s is used in an expression of the form (ask s)(<n : m :::>,c), each m value can be either a character string or a 0 0 i list of character strings. fflIf m is a character string, then an environment variable is implicitly defined by i export n =m . i i fflIf m is a list of character strings, then a text file is temporarily created in the current i working directory with a name of n and contents m using the standard line editor, i i ed. The text file is deleted when the shell terminates. There are certain limitations on the commands that may appear in the list c. fflInteractive commands that wait for user input should be avoided because they will cause the client to deadlock. fflCommands using input redirection (for example, "cat - > file") also won’t work.

$ fun cli -m="(ask su/0 Z10N0101)/<> <'whoami'>" -c %sLm <'whoami': <'root'>> If an application is already executing as root, it should not attempt to use a shell generated by the su function, because such a shell relies on the assumption that it will be prompted for a password. However, any application running as root can achieve the same effect just by executing su husernamei as an ordinary shell command.

22.3.2 Numerical applications The numerical applications whose interfaces are described in this section include linear algebra functions involving vectors and matrices of numbers. Facilities are provided for automatic initialization of these types of variables in the application’s workspace. fflWhen a shell s interfacing to a numerical application is used in an expression of the form (ask s)(<n : m :::>,c), each m value can be a number, a list of 0 0 i numbers, or a lists of lists of numbers, and will cause a variable to be initialized in the application’s workspace that is respectively a scalar, a vector, or a matrix. fflDifferent numeric types are supported depending on the application, including natu- ral, rational, floating point, and arbitrary precision numbers in the mpfr (%E) repre- sentation. The type is detected automatically. fflIf the application supports them, vectors and matrices of character strings are simi- larly recognized, and may be initialized either as quoted strings or symbolic names depending on the application. fflIf an application supports vectors of strings, an attempt is made to distinguish be- tween lists of character strings representing vectors and those representing functions defined in the application’s scripting language based on syntactic patterns as docu- mented below. In the latter case, the list of strings is interpreted as the definition of a function and initialized accordingly.

$ fun cli --m="ask®/<'x': 1.> <'x+1'>" --c %sLm <'x+1': <'[1] 2'>>

$ fun cli --m="(ask scilab)/<> <'1+1'>" --c %sLm <'1+1': <' 2. '>> 410

22.3.3 Computer algebra packages The interfaces documented in this section pertain to computer algebra packages, which are used primarily for symbolic computations.

22.4 Functions based on shells A small selection of functions using some of the standard shells is included in the cli library for illustrative purposes and possible practical use.

22.4.1 Front ends The following functions use bash, octave, or R as back ends to compute mathematical results or perform system calls.

Here is an example of now. $ fun cli --m=now0 --c %s Sat, 07 Jul 2007 07:07:07 +0100 eigen This function takes a real symmetric matrix of type %eLL to the list of pairs <(<x :::>,[U+02D8]/:::> representing its eigenvectors and eigenvalues in order of decreas- ing magnitude.

Here is an example of the above function. $ fun cli --m="eigen1.>" --c %eLeXL < (<7.071068e-01,7.071068e-01>,3.000000e+00), ( ←7.071068e-01,7.071068e-01>, 1.000000e+00)> 412

A similar result can be obtained with less overhead by the function dsyevr among others available through the virtual machine’s lapack library interface if it is appropriately configured. choleski This function takes a positive definite matrix of type %eLL and returns its lower tri- angular Choleski factor. If the argument is not positive definite, an exception is raised with a diagnostic message to that effect.

Here are some examples of Choleski decompositions. $ fun cli --m="choleski2.>" --c %eLL < <2.000000e+00,0.000000e+00>, <1.000000e+00,2.645751e+00>> $ fun cli --m="choleski2.>" --c %eLL fun:command-line: error: chol: matrix not positive definite The latter example demonstrates the technique of passing through a diagnostic message from the back end octave application. Note that if the virtual machine is configured with a lapack interface, a quicker and more versatile way to get Choleski factors is by the dpptrf and zpptrf functions. stdmvnorm This function takes a triple .<a :::a >,<b :::b >,oe/ to the probability that a ran- 0 n 0 n dom draw <x :::x > from a multivariate normally distributed population with means 0 n 0 and covariance matrix oe has a [U+02C7] x [U+02C7] b for all 0 [U+02C7] i [U+02C7] n. i i i

22.4.2 Format converters A couple of functions are usable for transforming the output of a shell. In the case of Axiom, the default output format is somewhat difficult to parse. $ fun cli --m="ask(axiom)/<> <'(x+1)[U+02C6]2'>" --c %sLm

< (x+1)[U+02C6]2: < ' 2', ' (1) x + 2x + 1', ' Type: Polynomial Integer'>> Although suitable for interactive use, this format makes for awkward input to any other program. However, the following technique can at least transform it to a lisp expression. $ fun cli --m="ask(axiom)/0 <'((x+1)[U+02C6]2)::INFORM'>" --c %sLm < ((x+1)[U+02C6]2)::INFORM: < ' (1) (+ (+ (* x 2) ( 2 x)) 1), ' Type: InputForm>> This format can be made convenient for further processing (e.g., with tree traversal com- binators) by the following function. axparse Given a lisp expression displayed by Axiom with an INFORM type cast, this func- tion parses it to a tree of character strings.

The following example demonstrates this effect. $ fun cli --c %sT \ > --m="axparse ~&hm ask(axiom)/<> <'((x+1)[U+02C6]2)::INFORM'>" [U+02C6]: < [U+02C6]: < *[U+02C6]: <'x'[U+02C6]: <>,2[U+02C6]: <>>, [U+02C6]: <'2'[U+02C6]: <>,x[U+02C6]: <>>>, 1[U+02C6]: <>> octhex This function is used to convert hexadecimal character strings displayed by Octave to their floating point representations.

The octhex function is used internally by the octave interface but may be of use for customizing or hacking it. $ octave -q octave:1> format hex octave:2> 1.234567 ans = 3ff3c0c9539b8887 octave:3> quit $ fun cli --m="octhex 3ff3c0c9539b8887" --c %e 1.234567e+00 414

22.5 Defining new interfaces The remainder of the chapter needs to be read only by developers wishing to modify or extend the set of existing shell interfaces. To this end, the basic building blocks are what will be called protocols and clients.

22.5.1 Protocols A protocol is represented as a non-empty list <.c ;p /; :::.c ;p /> of pairs of lists of 0 0 n n strings wherein each c is a sequence of commands sent by the client to the server, and the i corresponding p is the text containing the prompt that the server is expected to transmit i in reply. fflLine breaks are not explicitly encoded, but are implied if either list contains multiple strings. fflIf and when all transactions in the list are completed, the connection is closed by the client and the session is terminated. Certain patterns have particular meanings in protocol specifications. These interpreta- tions are a consequence of the virtual machine’s interact combinator semantics. fflIf any prompt p is a list of one string containing only the end of file character (ISO i code 4), the client waits for all output until the server closes the connection and then the session is terminated. fflIf a prompt p is <''>, the list of the empty string, the client waits for no output at i all from the server and proceeds immediately to send the next list commands c , if iC1 any.

22.5.2 Clients A client in this context is a function f expressed in virtual machine code that is said to execute a protocol <.c ;p /; :::.c ;p /> if it meets the condition 0 0 n n 8<x :::x >: 9<q :::q >: f./ D .q ;c ;p / 0 n 0 n 0 0 0 [U+02C6] 8i 2 f0:::n[U+0393] 1g: f.q ;-[-[x ]--[p ]-]-/ D .q ;c ;p / i i i iC1 iC1 iC1 where each x is a list of character strings and the dash bracket notation has the semantics i explained on page 118, in this case concatenating a pair of lists of strings by concatenating the last string in x with the first one in p , if any. The q values are constants of unrestricted i i i type. A client f in itself is only an alternative representation of a protocol in an intensional form, but when a program interact f is applied to any argument, the virtual machine carries out the specified interactions to return the transcript <c ;-[-[x ]--[p ]-]-;:::c ;-[-[x ]--[p ]-]→ 0 0 0 n n n with the x values emitted by a server.

Clients from clients seq This function takes a prompt p to a function that takes a list of clients to their se- quential composition in a shell with prompt p. The sequential composition is a client that begins by behaving like the first client in the list, then the second when that one terminates, and so on, expecting the prompt p in between.

For a list of commands x and a prompt p, the following equivalence holds, expect handshake/p x j (seq p) exec* x but the form on the left is more efficient. Some command line interpreters, such as those of Axiom and Maxima, use numbered prompts. In these cases, the following function or something similar is useful as a wrapper.

Execution of clients

22.5.3 Shell interfaces The purpose of a shell data structure is to encapsulate as much useful information as possible about invoking a shell or command line interpreter. When a shell is properly constructed, it can be used as a parameter to the ask function and allow easy access to the application it describes. Working with this data structure is explained in this section.

Data structures As noted below, some of the fields in a shell are character strings, but to be adequately expressive, others are protocols, clients, or functions that generate clients, as these terms are understood based on the explanations in the previous sections. shell This function is the mnemonic for a record with the following fields.

The functions sh and ssh follow similar calling conventions to ask and sask, respec- tively, but return only a client without executing it. Further levels of remote invocation are possible by using the hop function explicitly in conjunction with these. Aside from using the client constructed by one of these functions to specify a field in a shell, the only useful thing to do with it is to run it by the watch function. $ fun cli --m="watch (sh R)/<'x': 1.> <'x+1'>" --c < <'R -q'>, <'> >, <'x=1.00000000000000000000e+00,'>, <'x=1.00000000000000000000e+00,> '>, <'x+1,'>, <'x+1,[1] 2,> '>, <'q(),'>, <'q()>>

22.5.4 Interface example The programming language yorick is suitable for numerical applications and scientific data visualization (see http://yorick.sourceforge.net), and it is designed to be accessed by a command line interpreter. Although there is no interface to the yorick interpreter defined in the cli library, a user could easily create one by gleaning the fol- lowing facts from the documentation. 421

Listing 22.1 example of a user-defined shell interface with a test driver #import std #import nat #import cli #import flo

yorick = shell[ opener: yorick, prompt: > ', declarer: %eI?m( ("n","m"). exec "n"-- = --(printf/%0.20e' "m")--;, %sLI?m( expect+ completing+ handshake/cont> '+ ~&miF, <'unknown yorick type>!%)), closers: <'quit'>] alas =

%sLmP (ask yorick)( < x: 1., double: -[ func double(x) { return x+x; }]→, <'double(x)+1'>)

← i 105 ← t 116 ← 10 waiting for 13 10 → q 113 → u 117 → i 105 → t 116 → 13 → 10 matched closing yorick <'double(x)+1': <'3'>>

Yeah well, new rules. Tom Cruise in Rain Man

Many features of Ursala normally considered invariant, such as the operator semantics, can be changed by the command line options listed in Table 23.1. These changes are made without rebuilding or modifying the compiler. Instead, the compiler supplements its internal tables by reading from a binary file whose name is given as a command line parameter. This chapter is concerned with preparing the binary files associated with these options, which entails a knowledge of the compiler’s data structures. The kinds of things that can be done by means explained in this chapter are adding a new operator or directive, changing the operator precedence rules, defining new type constructors and pointers, or even defining new command line options. It is generally assumed that the reader has a reason for wanting to add features to the language, and that the desired enhancements can’t be obtained by simpler means (e.g., defining a library function or using programmable directives). The possible modifications described in this chapter affect only an individual compila- tion when the relevant command line option is selected, but they can be made the default behavior by editing the compiler’s wrapper script. There is likely to be some noticeable overhead incurred when the compiler is launched, which could be avoided if the changes were hard coded. Further documentation to that end is given in the next chapter, but this chapter is worth reading regardless, because the same data structures are involved.

23.1 Pointers The pointer constructors documented in Chapter 2 are specified in a table called pnodes of type _pnode%m defined in the file src/psp.fun. Each record in the table has the following fields. fflmnemonic — either a string of length 1 or a natural number as a unique identifier

Listing 23.1 source file defining a new pseudo-pointer #import std #import nat #import psp #binary+

pfi = ~&iNC pnode[ mnemonic: u, fval: ("f","g"). subset[U+02C6]("f","g"), arity: 2, help: binary subset combinator]

23.1.1 Pointers with alphabetic mnemonics An example of a file specifying a new pointer constructor is shown in Listing 23.1. The file contains a list of pnode records to be written in binary form to a file named pfi. The list contains a single pointer constructor specification with a mnemonic of u. This constructor is a pseudo-pointer that requires two pointers or pseudo-pointers as subexpressions in the pointer expression where it occurs. If the expression is of the form _{&fgu x, then the result will be subset(}&f x,~&g x). As a demonstration, the text in Listing 23.1 can be saved in a file named pfi.fun and compiled as shown. $ fun psp pfi.fun fun: writing pfi Using this file in conjunction with the --pointers command line option shows the new pointer is automatically integrated into the interactive help. $ fun --pointers ./pfi --help pointers,2

$ fun --main="_{&x" --decompile main = reverse $ fun --pointers only ./pfi --main="}&x" --decompile fun:command-line: unrecognized identifier: x A simple test of the new pointer is the following. $ fun --pointers ./pfi --m="_{&u/ab abc" --c %b true A more reassuring demonstration may be to inspect the code generated for the expression} &u, to confirm that it computes the subset predicate.

$ fun --pointers ./pfi --m="~&u" --d main = compose( refer conditional( field(0,&), conditional( compose(member,field(0,, recur&, constant 0), constant &), compose(distribute,field0 23.1.2 Pointers accessed by escape codes A drawback of defining a new pointer in the manner described above is that the mnemonic u is already used for something else. Although it is easy to change the meaning of an existing pointer, doing so breaks backward compatibility and makes the compiler unable to bootstrap itself. The issue is not avoided by using a different mnemonic because every upper and lower case letter of the alphabet is used, digits have special meanings, and non- alphanumeric characters are not valid in pointer mnemonics. However, it is possible to define new pointer operators by using numerical escape codes as described in this section. The escaping field in a pnode record may contain a function that takes a natural number as an argument and returns a pnode record as a result. The argument to the function is derived from the digits that follow the occurrence of the escaping pointer in an expression. The result returned by the escaping field is substituted for the original and the escape code to evaluate the expression. There is only one pointer in the pnodes table that has a non-empty escaping field, which is the K pointer, but only one is needed because it can take an unlimited number of escape codes. The way of adding a new pointer as an escape code is to redefine the K pointer similarly to the previous section, but with the escaping field amended to include the new pointer. A simple way of proceeding is to use the definitions of the K pointer and the escapes list from the psp module, as shown in Listing 23.2. The escapes list is a list of type

Listing 23.2 adding a new pointer without breaking backward compatibility #import std #import nat #import psp

pfi = ~&iNC pnode[ mnemonic: length psp-escapes, fval: ("f","g"). subset[U+02C6]("f","g"), arity: 2, help: binary subset combinator]

escapes = --([U+02C6]A(_mnemonic,&)* pfi) psp-escapes #binary+

kde = _{&iNC pnode[ mnemonic: K, fval: <'escape code missing after K'>!%, help: escape to numerically coded operators, escaping: %nI?(} &ihrPB+ [U+02C6]E(_&l,&r.mnemonic)*₊ &D\(~&mS escapes), <'numeric escape code missing after K'>!%), arity: 1]

_pnode%m whose i-th item (starting from 0) has a mnemonic equal to the natural number i. It is used in the definition of the escaping field of the K pointer specification. The K record is cut and pasted from psp.fun, without any source code changes, but the list of escapes is locally redefined to have an additional record appended. Appending it rather than inserting it at the beginning is necessary to avoid changing any of the existing escape codes. The appended record, for the sake of a demonstration, is similar to the one defined in the previous section. The code in Listing 23.2 is compiled as shown. $ fun psp kde.fun fun: writing kde The new pointer shows up as an escape code as required in the interactive help, $ fun --pointers ./kde --help pointers,2

: : : * K18 binary subset combinator : : : and it has the specified semantics. $ fun --pointers ./kde --m="~&K18" --d main = compose( refer conditional( field(0,&), conditional( compose(member,field(0,, recur&, constant 0), constant &), compose(distribute,field0

23.2 Precedence rules The --precedence command line option allows the operator precedence rules docu- mented in Section 5.1.3 to be changed. The option requires the name of a binary file to be given as a parameter, that contains a pair of pairs of lists of pairs of strings

Listing 23.3 a revised set of precedence rules to make infix composition right associative #binary+ npr = <>

mnemonic, either from Table 5.2 or user defined. The presence of a pair of strings in a component of the tuple indicates that the left operator is related to the right under the precedence relation.

23.2.1 Adding a rule Listing 23.3 provides a short example of a change in the precedence rules. Normally infix composition is left associative, but this specification makes the + operator related to itself when used in the infix arity, and therefore right associative. Given this code in a file named npr.fun, we have $ fun --main="f+g+h" --parse main = (f+g)h $ fun npr.fun fun: writing npr $ fun --precedence ./npr --main="f+g+h" --parse main = f(g+h) In the case of functional composition, both interpretations are of course semantically equivalent.

23.2.2 Removing a rule Additional precedence relationships are easy to add in this way, but removing one is slightly less so. In this case, a set of precedence rules derived from the default prece- dence rules from the module src/pru.avm has to be constructed as shown below, with the undesired rules removed. npr = (&rr:= _&j\<(;,/)>+ &rr) pru-default_rules The rules would then be imposed using the only parameter to the --precedence op- tion, as in $ fun --precedence only ./npr foobar.fun

23.2.3 Maintaining compatibility Changing the precedence rules can almost be guaranteed break backward compatibility and make the compiler unable to bootstrap itself. If customized precedence rules are im- plemented after a project is underway, it may be helpful to identify the points of incom- patibility by a test such as the following.

$ fun *.fun --parse all > old.txt $ fun --precedence ./npr *.fun --parse all > new.txt $ diff old.txt new.txt Assuming the files of interest are in the current directory and named *.fun, this test will identify all the expressions that are parsed differently under the new rules and therefore in need of manual editing.

23.3 Type constructors Type expressions are represented as trees of records whose declaration can be found in the file src/tag.fun. The main table of type constructor records is declared in the file src/tco.fun. It has a type of _type_constructor%m. A type_constructor record has the following fields, first outlined briefly below and then explained in more detail.

23.3.1 Type constructor usage Supplementary material on the type_constructor field interpretations is provided in this section for readers wishing to extend or modify the system of types in the language. As noted above, every field in the record except for the help and arity fields is a function. Most of these functions are not useful by themselves, but are intended to be combined in the course of a traversal of a tree of type constructors representing an aggregate type or type related function. This design style allows arbitrarily complex types to be specified in terms of interchangeable parts, but it requires the functions to follow well defined calling conventions.

Printer and recognizer calling conventions The printing function for a type d[U+02C6]: v, where d is a type_constructor record, is computed according to the equivalence .%-P d[U+02C6]: v/ x j .~printer d/ .[U+00A1] d[U+02C6]: v>,x/ at the root level. Note that the function is applied to an argument containing itself and the type expression in which it occurs, which is convenient in certain situations, in addition to the data x to be printed.

Primitive and aggregate type printers For primitive types, the printer field often may take the form f+ _{&r, because the type expressions on the left are disregarded. For example, the printer for boolean types is as follows. $ fun tag --m="}&d.printer %b" --d main = couple( conditional( field(0,&), constant true, constant false), constant 0) For aggregate types, the printer in the root constructor normally needs to invoke the printers from the subexpressions at some point. When a printer for a subexpression is called, convention requires it to be passed an argument of the form 0 .<t;d[U+02C6]: v>,x /

where d[U+02C6]: v is the original type expression, now appearing second in the list, while t is the subexpression type. In this way, the subexpression printer may access not just its own type expression but its parents. Although most printers do not depend on the parents of the expression where they occur, the exception is the h type constructor for recursive types (and indirectly for recursively defined records).

List printer example To make this description more precise, we can consider the printer for the list type constructor, L. The representation for a list type expression is always something similar to the following, $ fun tag --m="%bL" --c _type_constructor%T [U+02C6]: ( type_constructor[ mnemonic: L, printer: 674%fOi&, recognizer: 274%fOi&, precognizer: 100%fOi&, initializer: 32%fOi&, generator: 1605%fOi&], < [U+02C6]:<> type_constructor[ mnemonic: b, printer: 80%fOi&, recognizer: 16%fOi&, initializer: 11%fOi&, generator: 110%fOi&]>) where the subexpression may vary. The source code for the printer function in the list type constructor takes the form

The second phase, (* [U+02C6]H/_&lhd.printer &), uses the printer of the subexpres- sion t to print each item x through x . Many printers for unary type constructors have 0 n a similar first phase of pushing the subexpression onto the stack, but this second phase is more specific to lists. Recognizers The calling conventions for recognizer and precognizer functions follow immediately from the one for printers. Rather than returning a list of strings, these functions return boolean values. The root printer function of a type expression may need to invoke the recognizer functions of its subexpressions, which is done for example in the case of free unions.

The function in the microcode field is invoked when a type expression is evaluated as described in Section 4.3.1. To evaluate an expression such as s%t t :::t , the list of type 0 1 n constructors <T :::T > associated with each of the mnemonics t through t is combined 0 n 0 n with the initial stack <s>, and the microcode field of T is applied to .<s>;<T :::T >/. 0 0 n Certain conventions are followed by microde functions although they are not enforced in any way. fflIf T is the type constructor for a primitive type, the microcode should return a result 0 of .<T [U+02C6]:<>;s>;<T :::T >/, which has the unit tree of the constructor T shifted 0 1 n 0 to the stack. fflIf T is a unary type constructor, its microcode should map the result returned by 1 the microcode of T to .<T [U+02C6]:<T [U+02C6]:<>>;s>;<T :::T >/, which shifts a type ex- 0 1 0 2 n pression onto the stack having T as the root and the previous top of the stack as the 1 subexpression. fflIf T is a binary type constructor, its microcode should map the result returned by 1 the microcode of T to .<T [U+02C6]:<s;T [U+02C6]:<>>>;<T :::T >/, and s best be a type 0 1 0 2 n expression. This result has a type expression on top of the stack with T as the root 1 and the two previous top items as the subexpressions. fflIf any T represents a functional combinator rather than a type constructor (for ex- i ample, like the P and I constructors), the microcode should return a result of the form (<d[U+02C6]:<>>,<>), with the resulting function stored in the target field of d. fflThe microcode for the remaining constructors such as l and r transforms the stack in arbitrary ad hoc ways, as shown in Figure 4.1 on page 166.

Initializers The initializer field in each type constructor is responsible for assigning the default value of an instance of a type when it is used as a field in a record. It takes an argument of the form (<f :::f >,<t :::>) because the initializer of an aggregate type is normally 0 n defined in terms of the initializers of its component types, although the initializer of a primitive type is constant. For example, the boolean (%b) initializer is ! ~&i&& &!, the constant function returning the function that maps any non-empty value to the true

boolean value (&). The initializer of the list construtor (L) is _&l; &ihB&& _{&h; *, the function that applies the initializer f , in the above expression, to every item of a list. 0 For aggregate types, most initializers are of the form} &l; h, because they depend only on the initializers of the subtypes, but the exception is the U type constructor, whose initializer needs to invoke the precognizer functions of its subtypes and hence requires the stack of ancestor types in case any of them is recursively defined. Generators

A random instance generator for a type t is a function that takes either a natural number as an argument or the constant &. If it is given a natural number n as an argument, its job is to return an instance of t having a weight as close as possible to n, measured in quits. If it is given & as an argument, it is expected to return a boolean value which is true if there exists an upper bound on the size of the instances of t, and false otherwise. Examples of the former types are boolean, character, standard floating point types, and tuples thereof. The generator field in each type constructor is responsible for constructing a ran- dom instance generator of the type. For aggregate types, it is normally defined in terms of the generators of the component types, but for primitive types it is invariant. For example, the generator field of the e type constructor is defined as ! math..sub\10.0+ mtwist..u_cont+ 20.0! whereas the generator of the U type constructor is &?=[U+02C6]\choice !+ _&g+ &iNNXH+ gang

based on the assumption that it will be applied to the list of the generators of the com- ponent types, <g :::g >. Note that _&g &iNNXH gang<g :::g > is equivalent to 0 n 0 n ~&g <.g :::g > &, which is non-empty if and only if g & is non-empty for all i. 0 n i Various functions defined in the tag module may be helpful for constructing random instance generators, but there are no plans to maintain a documented stable API for this purpose. 23.3.2 User defined primitive type example Interval arithmetic is a technique for coping with uncertainty in numerical data by identi- fying an approximate real number with its known upper and lower bounds. By treating the pair of bounds as a unit, sums, differences, and products of intervals can all be defined in the obvious ways.

Interval representation A library of interval arithmetic operations is beyond the scope of this example, but the specification of a primitive type for intervals is shown in Listing 23.4. According to this specification, intervals are represented as pairs .a;b/ with a [U+00A1] b, where a and b are

Listing 23.4 a new primitive type for interval arithmetic #import std #import nat #import tag #import flo

#binary+ H =

_{&iNC type_constructor[ mnemonic: H, microcode:} &rhPNVlCrtPX, printer: _&r; &iNC+ math..isinfinite?l( math..isinfinite?r(0+-inf!,---inf+ _{&h+ %eP+} &r), math..isinfinite?r( --inf _{&h+ %eP+} &l, [U+02C6]|T(_{&,---) (}&h+ %eP+ div\2.)_{/plus bus)), reader:} &L; -? (==0+-inf): (ninf,inf)!, substring/-: - math..strtod_~; &rllXG; [U+02C6]|/bus plus, (,-)[U+02C6]?=ahthPX/_&Natt2X &ahPfatPRXlrlPCrrPX-, suffix/-inf: _{&/ninf+ math..strtod+} &xttttx, suffix/inf: _&\inf math..strtod+ &xttttx, <'bad interval'>!%?-, recognizer: ! _{&i&& &&fleq both %eI, precognizer: !} &i&& both %eI, initializer: ! _{&?\(ninf,inf)!} &l?( _&r?/(fleq?/& _&rlX) &\inf+ _&l, &/ninf!+ _{&r), help: push primitive interval type, generator: ! &?=/&! fleq?(}&,~&rlX)+ 0%eWi]

floating point numbers representing the endpoints. This representation is implied by the recognizer function, which is satisfied only by a pair of floating point numbers with the left less than the right. Interval type features

The mnemonic for the interval type is v, so it may be used in type expressions like %H or %HL, etcetera. This mnemonic is chosen so as not to clash with any already defined, thereby maintaining backward compatibility. A small number of unused type mnemonics is available, which can be listed as shown. $ fun tco --m="_&j/letters &nSL type_constructors" --c FHK Other fields in the type constructor are defined to make working with intervals conve- nient. The initializer function will take a partially initialized interval and define the rest of it. If either endpoint is missing, infinity is inferred, and if the endpoints are out of order, they are interchanged. The default value of an interval is the entire real line. This function would be invoked whenever a field in a record is declared as type %H. The precognizer field differs from the recognizer by admitting either order of the endpoints. This difference is in keeping with its intended meaning as the recognizer of data in a non-canonical form, where this concept applies. The concrete syntax for a primitive type needn’t follow the representation exactly. The printer and reader fields accommodate a concrete syntax like 1.269215e+00+-9.170847e-01 for finite intervals, which is meant to resemble the standard notation x [U+03A3] d with x at the center of the interval and d as half of its width. Semi-infinite intervals are expressed as x+inf or x-inf as the case may be, with the finite endpoint displayed. The generator function simply generates an ordered pair of floating point numbers. The size (in quits) of a pair of floating point numbers is not adjustable, so the generator returns & when applied to a value of &, following the convention.

Interval type demonstration To test this example, we first store Listing 23.4 in a file named ty.fun and compile it as follows. $ fun tag flo ty.fun fun: writing H Random instances can now be generated as shown.

$ fun --types ./H --m="0%Hi&" --c %H -7.577923e+00+-3.819156e-01

Note that if the file name H doesn’t contain a period, it should be indicated as shown on the command line to distinguish it from an optional parameter. Data can also be cast to this type and displayed, $ fun --types ./v --m="(1.6,1.7)" --c %H 1.650000e+00+-5.000000e-02 and data using the concrete syntax chosen above can be read by the interval parser %Hp. $ fun --types ./H --m="%Hp -[2.5+-.001]-" --c %H 2.500000e+00+-1.000000e-03 However, defining a concrete syntax for constants of a new primitive type does not auto- matically enable the compiler to parse them. $ fun --types ./H --m="2.5+-.001" --c %H fun:command-line: unbalanced +- This kind of modification to the language would require hand written adjustments to the lexical analyzer, as outlined in the next chapter.

23.4 Directives

The compiler directives, as documented in Chapter 7, are defined in terms of transforma- tions on the compiler’s run-time data structures. They can be used either to generate output files or to make arbitrary source level changes during compilation, and in either case may be parameterized or not. The directive specifications are stored in a table named default_directives de- fined in the file src/dir.fun. This table can be modified dynamically when the com- piler is invoked with the --directives command line option. This option requires a binary file containing a list of directive specifications that will be incorporated into the table. A directive specification is given by a record with the following fields, which are explained in detail in the remainder of this section. fflmnemonic — the identifier used for the directive in the source code fflparameterized — character string briefly documenting the parameter if one is required fflparameter — default parameter value; empty means there is none fflnestable — boolean value implying the directive is required to appear in matched + and - pairs (currently true of only the hide directive) fflblockable — boolean value implying the scope of the directive doesn’t automati- cally extend inside nestable directives (currently true only of the export directive) fflcommentable — boolean value indicationg that output files generated by the direc- tive can have comments included by the comment directive

23.4.1 Directive settings The settings for fields in a directive record tend follow certain conventions that are summarized below, and should be taken into account when defining a new directive.

Flags fflThe nestable and blockable fields should normally be false in a directive spec- ification, unless the directive is intended as a replacement for the hide or export directives, respectively. fflThe commentable field should normally be true for output generating directives that generate binary files, but probably not for other kinds of files. fflEither setting of the mergeable field could be reasonable depending on the nature of the directive. Currently it is true only of the library directive. Command line settings Any new directive that is defined will automatically cause a command line option of the same name to be defined that performs the same function, unless there is already a command line option by that name, or the directive is defined with a true value for the nestable field. fflA non-zero value for the favorite may be chosen if the directive is likely to be more frequently used from the command line than existing command line options starting with the same letter. Several directives currently use low numbers like 1, 2, etcetera (page 276). Higher numbers indicate higher name clash resolution priority.

23.4.2 Output generating functions The remaining fields in a directive record describe the operations that the directive performs as functions. The more straightforward case is that of the compilation field, which is used only in output generating directives.

Calling conventions The compilation field takes an argument of the form (<s : x :::s : x >,<f :::f >) 0 0 n n 0 m where s is a string, x is a value of any type, and f is a file specification of type _file, i i j as defined in the standard library. These values come from the declarations that appear within the scope of the directive being defined. For example, a user defined directive by the name of foobar used in a source file such as the following #foobar+

s = 1.2 t = (3,4.0E5) #foobar- can be expected to have a value of (<'s': 1.2,t: (3,4.0E5)>,<>) passed to the function in its compilation field. Note that the right hand sides of the declarations are already evaluated at that stage. The list of files on the right hand side is empty in this case, but for the code fragment below it would contain a file.

#foobar+ s = 1.2 t = (3,4.0E5) #binary+

u = game over #binary-

#foobar- The files in the right hand side of the argument to the compilation function are those that are generated by any output generating directives within its scope. These files can either be ignored by the function, or new files derived from them can be returned.

Listing 23.5 simple example of an output generating directive directive[ mnemonic: binary, commentable: &, compilation: _{&l; * file$[ stamp: &!, path:} &nNC, preamble: &!, contents: ~&m], help: dump each symbol in the current scope to a binary file]

Example The resulting list of files returned by the compilation function can depend on these pa- rameters in arbitrary ways. Listing 23.5 shows the complete specification for the binary directive, whose compilation field makes a binary file for each item of the list of dec- larations.

23.4.3 Source transformation functions The direction field in a directive specification can perform an arbitrary source level transformation on the parse trees that are created during compilation. Unlike the compilation field, this function is invoked at an earlier stage when the expressions might not be fully evaluated.

Parse trees Parse trees are represented as trees of token records, which are declared in the file src/lag.fun. Functions stored in these records allow parse trees to be self-organizing. A bit of a digression is needed at this point to explain them in adequate detail, but this ma- terial is also relevant to user defined operators documented subsequently in this chapter. A token record contains the following fields. ffllexeme — a character string identifying the token as it appears in a source file fflfilename — a character string containing the name of the file in which the token appears

Parse tree semantics Almost any desired effect can be achieved by a directive through suit- able adjustment to the preprocessor, postprocessors, and semantics fields of the parse tree nodes, so it is worth understanding their exact calling conventions. The preprocessor field is invoked essentially as follows. [U+02C6]= _{&a[U+02C6]& [U+02C6]aadPfavPMVB/}&f [U+02C6]H~&a ||_&! &ad.preprocessor

Hence, its argument is the tree in whose root it resides, and it is expected to return the whole tree after transformation. The semantics field is invoked as if the following code were executed during parse tree evaluation. _{&a[U+02C6]& [U+02C6]H( ||}&! _{&ad.postprocessors.&ihB, [U+02C6]H\}&favPM _&H+ &ad.(semantics,lag-suffix)) The argument of the semantics function is the suffix of the node in which it resides. It is expected to return a function that will map the list of values of the subtrees to a value for the whole tree, which is passed to the head of the postprocessors, if any, to obtain the final value.

Transformation calling conventions When a user defined directive has a non-empty direction field, this field should contain a function that takes a tree of token records as described above and return one that is transformed as desired. The tree represents the source code encompassing the scope of the directive (i.e., everything following it up to the end of the enclosing name space or the point where it is switched off). The direction function benefits from a reflective interface in that the root of the tree passed to it is a token whose lexeme is the directive’s mnemonic and whose preprocessor and semantics are automatically derived from the direction and compilation functions of the directive. For parameterized directives, the parameter is accessed as the first subexpression of the parse tree, _{&vh. If the action of the directive depends on the value of the parameter, as it typically would, then the parameter needs to be evaluated first. The direction function can wait until the parameter is evaluated before proceeding if it is specified in the following form, (*[U+02C6]0 -&}&,_{&d.semantics,}&vig&-)?vh\~& f

where f is the function that is applied after the parameter has been evaluated. This code simply traverses the first subexpression tree to establish that all semantics fields are initialized. If this condition is not met, it means there are symbolic names in the expression that have not yet been resolved, but will be on a subsequent iteration, as explained above in the discussion of control flow. In this case, the identity function ~& leaves the tree unaltered. A general point to note about direction functions is that some provision usually needs to made to ensure termination when they are iterated. The simplest approach for the directive to delete itself from the tree by replacing the root with a placeholder such as the separation token defined in the apt library. Where this is not appropriate, it also suffices to delete the preprocessor field of the root token. Refer to the file src/dir.fun for examples.

Listing 23.6 an example of a directive performing a parse tree transformation #import std #import nat #import lag #import dir #import apt #binary+

al = _{&iNC directive[ mnemonic: alphabet, direction: _token%TMk+} &v?( _{&V/separation+ [U+02C6]T\}&vt -+ * _{&ar[U+02C6]& [U+02C6]V\}&falrvPDPM :=ard ( &ard.(filename,filenumber,location), _{&al.(filename,filenumber,location)), [U+02C6]D/}&d _{&vh; -+ * -+} &V/token[lexeme: =,semantics: _&hthPA!], &iNViiNCC+ token$-, *[U+02C6]0 [U+02C6]T\&vL _{&d.lexeme; &&}&iNC subset\letters-+-, <'misused #alphabet directive'>!%), help: bulk declare a list of identifiers as strings, parameterized: list-of-identifiers]

23.4.4 User defined directive example One reason for customizing the directives might be to implement syntactic sugar for some sort of domain specific language. In a language concerned primarily with modelling or simulation of automata, for example, it might be convenient to declare a system’s input or output alphabet in an abstract style such as the following. #alphabet <a,b,ack,nack,foo,bar>

system = box_of(a,b,ack,nack) The intent is to allow the symbols a, b, etcetera to be used as symbolic names with no further declarations required.

Specification Listing 23.6 shows a possible specification for a directive to accomplish this effect, which works by declaring each symbol as a string containing its identifier, (e.g., a = a) but this representation need not be transparent to the user. This example could also serve as a

Listing 23.7 test driver for the directive defined in Listing 23.6 #alphabet foo bar baz x = <foo,bar,baz>

prototype for more sophisticated alternatives. Several points of interest about this example are the following.

Demonstration To demonstrate this example, we can store it in a file named al.fun and compile it as follows. $ fun lag dir apt al.fun fun: writing al It can then be tested in a file such as the one shown in Listing 23.7, named altoid.fun. $ fun --directives ./al altoid.fun --c <'foo',bar,baz>

This output is what should be expected if the identifiers were declared as strings. We can also verify that the directive is accessible directly from the command line. $ fun --dir ./al --m=foo --alphabet foo --c foo 446

23.5 Operators The operators documented in Chapters 5 and 6 are specified by a table of records of type _operator. The record declaration is in the file src/ogl.fun. The main opera- tor table is defined in the file ops.fun, the declaration operators are defined in the file eto.fun, and the invisible operators for function application, separation, and juxtaposi- tion are defined in the file apt.fun. Adding a new operator to the language or changing the semantics of an existing one is a matter of putting a new record in the table. It can be done dynamically by the --operators command line option, which takes a binary file containing a list of oper- ators in the form of operator record specifications.

23.5.1 Specifications Most operators admit more than one arity but have common or similar features that are independent of the arity. The operator record therefore contains several fields of type _mode. A mode record is used as a generic container having a named field for each arity. The field identifiers are prefix, postfix, infix, solo, and aggregate. This record type is declared in the file ogl.fun. Here is a summary of the fields in an operator record. fflmnemonic — a string of one or two characters containing the symbol used for the operator in source code fflmatch — for aggregate operators, a character string containing the right matching member of the pair (e.g. a closing parenthesis or brace) fflmeanings — a mode of functions containing semantic specifications

23.5.2 Usage Information contained in an operator specification is used automatically in various ways during lexical analysis, parsing, and evaluation. The parse tree for an expression containing operators is a tree of token records as documented in Section 23.4.3, with a token record corresponding to each operator in the expression. These token records are derived from the operator specification with appropriate preprocessor and semantic fields as explained below. Precedence

The last three fields in an operator record, loose, tight, and peer, affect the oper- ator precedence, which affects the way parse trees are built. Any time one of these fields is changed as a result of the --operators command line option for any operator, the rules are updated automatically. fflUse of the peer field is the recommended way of establishing the precedence of a new operator rather than changing the precedence rules directly as in Section 23.2, because it is conducive to more consistent rules and is less likely to cause backward incompatibility. fflThe loose field should have a true value only for declaration operators such as :: and =. However, some hand coded modifications to the compiler would also be re- quired in order to introduce new kinds of declarations, making this field inappropriate for use in conjunction with the --operators command line option. fflThe tight field is false for all operators except the very high precedence operators tilde (~), dash (-), library (..), and function application when expressed without a space, as in f(x). Otherwise, it is appropriate for infix operators whose left operand is rarely more than a single identifier. Optimization

The list of functions in the optimizers field maps directly to the postprocessors field in a token record derived from an operator. An optimizer function can perform an arbitrary transformation on the result computed by the operator, but the convention is to restrict it to things that are in some sense "semantics preserving". In this way, the operator can be evaluated with or without the optimizer as appropriate for the situation. 448

Because there is potentially a different semantics for each arity, the preprocessor in a token corresponding to an operator is automatically generated to detect the number and positions of the subtrees and to assign the semantics accordingly. Having done that, it will also apply the relevant function from the preprocessors field of the operator specification, if any. The preprocessors in an operator specification are not required and should be used sparingly when defining new operators, because top-down transformations on the parse tree can potentially frustrate attempts to formulate a compositional semantics for the language, making it less amenable to formal verification. However, there are two reasons to use them somewhat more frequently. One reason is to insert a so called "spacer" token into the parse tree using a function such as the following for a postfix preprocessor. _{lexeme==(spacer)?vhd/}& &vh:= _{&v; //}&V token[ lexeme: (spacer), semantics: _{&h!] The spacer should be inserted into the parse tree below any operator token that evaluates to a function but takes an operand that is not necessarily a function. such as the ! and ⇒ operators. Normally if all nodes in a parse tree have the same postprocessors, they are deleted from all but the root to avoid redundant optimization. The spacer token performs no operation when the parse tree is evaluated other than to return the value of its subex- pression, but its presence allows the subexpression to be optimized by its optimizer functions if applicable because they will not be deleted when the spacer is present. The other reason to use preprocessors in an operator specification is in certain aggregate operators that reduce to the identity function if there is just one operand, such as cumulative conjunction, which can benefit from a preprocessor like this. ||}& -&_{&d.lag-suffix.&Z,}&v,_&vtZ,&vh&-

Algebraic properties The dyadic field stores the information in Table 5.7 for each operator. For example, if an operator with a specification o is postfix dyadic, then ~dyadic.postfix o will be true. This information is not mandatory when defining an operator but may improve the quality of the generated code if it is indicated where appropriate. The field is referenced by the preprocessor of the function application operator defined in the file apt.fun.

Options The options field in an operator record is of the same type as the suffix field in a token derived from it, but the options fields contains the set of all possible suffix elements for the operator, and the suffix field contains only those appearing in the source text for a given usage. The options are a list of the form <s : x :::s : x >, where each s is a char- 0 0 n n i acter string containing exactly one character, and the x values can be of any type. For i example, some operators allowing pointer suffixes have the list of pnodes as their op- tions (see Section 23.1), and other operators that allow type expressions as suffixes have the type_constructors as their options, the main table of type_constructor records defined in the file tco.fun. Still others such as the /* operator have a short list of functional options defined as follows, <'*: *,=: ~&L+,$': fan> and other operators such as |= have combinations of these. However, no options should be specified for aggregate operators (e.g., parentheses and brackets) because they have a consistent style of using periods for suffixes as documented in Section 5.2.3, which is handled automatically. The use made of the options by the operator depends on their type and the operator se- mantics, as explained further below. For example, a list of pnodes can be assembled into a pointer or pseudo-pointer by the percolation function defined in the file psp.fun, and a list of type constructors is transformed to a type expression or type induced function by the execution function defined in tag.fun. A list of functional combinators such as those above might only need to be composed with the operator semantic function. Whatever options an operator may have, they should be documented in a few lines of text stored in the opthelp field, so that users are not forced to read the source code or search for a reference manual that might not exist or be out of date. The contents of this field are displayed when the compiler is invoked with the command line option --help suffixes, with the text automatically wrapped to fit into eighty columns on a terminal.

Semantics The functions in the meanings field follow a variety of calling conventions depending on the arity and depending on whether the options field is empty.

Lexical analysis The mnemonic and excluder fields in an operator specification map directly to the lexeme and exclusions fields in the token derived from it.

Mnemonics A new operator mnemonic can break backward compatibility even if it is not previously used, by coinciding with a frequently occurring character combination. For example, $[ would be a bad choice for an operator because this character combination occurs frequently in the expression of record valued functions. If this combination started to be lexed as an operator, many existing applications would need to be edited. Exclusions The excluder field can be used in operators with suffixes to suppress inter- pretation of a suffix. This function is consulted by the lexical analyzer when the operator lexeme is detected, and passed the string of characters following the lexeme up to the end of the line. If the function returns a true value, then the operator is considered not to have a suffix. One example is the assignment operator, :=, whose excluder detects the condi- tion ~&ihB-=0123456789. This condition allows expressions such as f:=0! to be interpreted in the more useful sense, rather than having 0 as a pointer suffix.

Listing 23.8 a user defined tree mapping operator #import std #import nat #import psp #import ogl #binary+

tm = _{&iNC operator[ mnemonic: [U+02C6]-, peer: *[U+02C6], dyadic: mode[solo: &], options: pnodes, opthelp: <'a pointer expression serves as a postprocessor'>, help: mode[ infix: f[U+02C6]-g maps f to internal nodes and g to leaves in a tree, prefix: [U+02C6]-g maps g only to terminal nodes in a tree, postfix: f[U+02C6]- maps f only to non-terminal nodes in a tree, solo: [U+02C6]- (f,g) maps f to internal nodes and g to leaves], meanings:} &H\-_{&lNlXBrY,percolation,}&mS- mode$[ infix: //+ "h". "h" *[U+02C6]0+ [U+02C6]V~&v+ _&v?+ &d;_{~, prefix: //+ "h". "h"} *[U+02C6]0+ [U+02C6]V\&v+ _&v?/&d+ _{&d;, postfix: //+ "h". "h" *[U+02C6]0+ [U+02C6]V\}&v+ _&v?\&d+ _{&d;, solo: //+ "h". "h"} *[U+02C6]0+ [U+02C6]V\&v+ _&v?+ &d;~~]]

23.5.3 User defined operator example The best designed operators are not necessarily the most complex, but the most easily learned and remembered. For a seasoned user, use of the operator becomes second na- ture, and for an inexperienced user, the time spent consulting the documentation is well compensated by the programming effort it saves. Most operators should be polymorphic, designed to support classes of types rather than specific types. Specification

A first attempt at an operator aspiring to these attributes is shown in Listing 23.8. This operator operates on trees or dual type trees. It is analogous to the map combinator on lists, in that it determines a structure preserving transformation wherein a single function is applied to multiple nodes. The operator, expressed by the symbol [U+02C6]-, is chosen to have the same precedence as the [U+02C6] operator, and allows four arities. In the infix form it satisfies these recurrences, .f[U+02C6]-g/ d[U+02C6]: <> D .g d/[U+02C6]: <> .f[U+02C6]-g/ d[U+02C6]: .h:t/ D .f d/[U+02C6]: .f[U+02C6]-g) .h:t/

which is to say that the user may elect to apply a different function to the terminal nodes than to the non-terminal nodes. Its other arities have these algebraic properties, [U+02C6]-g j ._{&/[U+02C6]-g f[U+02C6]- j f[U+02C6]-.}&/ .[U+02C6]-/ .f;g/ j f[U+02C6]-g the last being the solo dyadic property. Furthermore, the operator allows a pointer expres- sion as a suffix, which can perform any postprocessing operations. The question of whether these algebraic properties are most convenient would be re- solved only by experience, so this specification allows design changes to be made easily and transparently. A postfix dyadic semantics, for example, would be achieved by substi- tuting

Demonstration The code shown in Listing 23.8, stored in a file named tm.fun, is compiled as follows. $ fun psp ogl tm.fun fun: writing tm To demonstrate the operator, we use a function _{&ixT[U+02C6]-, in which the operand is a func- tion that generates a palindrome by concatenating any list with its reversal. This expression is applied to a randomly generated tree of character strings. $ fun --operators ./tm --m="}&ixT[U+02C6]- 500%sTi&" --c %sT zDOgcmHp}<eQQe<}pHmcgODz[U+02C6]: < -n.ss.n-[U+02C6]: < A%WYSD-'-DSYW%A[U+02C6]: <'p[U+02C6]: <>>, PzT$&&$TzP[U+02C6]: < GV+qswwsq+VG[U+02C6]: < '[U+02C6]: <'[U+02C6]: <>,Q[U+02C6]: <>,'[U+02C6]: <>,'[U+02C6]: <>>, [U+02C6]: ( }AL|yTm[[mTy|LA}, <'P'[U+02C6]: <>,~&V(),P[U+02C6]: <>,'[U+02C6]: <>>), '[U+02C6]: <>>, z/e4L[U+02C6]: <>, zg[U+02C6]: <>>, W[U+02C6]: <>>, 22O[U+02C6]: <>> This result shows that all of the non-terminal nodes in the tree are palindromes.

23.6 Command line options Most command line options to the compiler are not hard coded but based on executable 1 specifications stored in a table. The table can be dynamically modified by way of the --formulators command line option so as to define further command line options. In fact, all other command line options described in this chapter could be defined if they were not built in, and can be altered in any case.

23.6.1 Option specifications Each command line option is specified by a record of type _formulator as defined in the file src/for.fun. This record contains the semantic function of the option, among other things, which works by transforming a record of type _formulation as defined in the file mul.fun. The latter contains dynamically created copies of all tables mentioned in previous sections of this chapter, as well as entries for user supplied functions that can be invoked during various phases of the compilation. To be precise, the formulator record contains the following fields. fflmnemonic — a character string giving the full name of the option as it appears on the command line

23.6.2 Global compiler specifications The formulation data structure specifies a compiler by way of the following fields. Changing this data structure changes the behavior of the compiler. fflcommand_name — a character string containing the command whereby the compiler is invoked and diagnostics are reported fflsource_filter — a function taking a list of input files (type _file%L) to a list of input files, invoked prior to the initial lexical analysis phase ffltoken_filter — a function taking the initial a list of lists of lists of tokens (type _token%LLL) to a result of the same type, invoked after lexical analysis but before parsing fflpreformer — a function taking a list of parse trees before preprocessing to a list of parse trees fflpostformer — a function taking a parse tree for the whole compilation after pre- processing stabilizes to a parse tree suitable for evaluation ffltarget_filter — a function taking a list of output files to a list of output files, invoked after all parsing and evaluation fflimport_filter — a function for internal use by the compiler (refer to the source code documentation in src/mul.fun)

where the remainder of the expression takes a pair .p;f/ of a list of parameters p and possibly a configuration file f to a function that is applied to the token stream. Token streams The token stream is represented as a list of type _token%LLL because there is one list for each source file. Each list pertaining to a source file is a list of lists of tokens. Each list within one of these lists represents a contiguous sequence of tokens without intervening white space. Where white space or comments appear in the source file, the token preceding it is at the end of one list and the token following it is at the beginning of the next. Hence, a source code fragment like (f1, g2), would have the first four tokens together in a list, and the next three in the subsequent list.

Parse trees Parse trees follow certain conventions to express distinctions between operator arities, which must be understood to manipulate them correctly. If a user supplied function is installed as the preformer in the formulation record, its argument will be a list of parse trees as they are constructed prior to any self-modifying transformations deter- mined by the preprocessor field in the token records. Prior to preprocessing, every operator token initially has two subtrees. fflFor infix operators, the left operand is first in the list of subtrees and the right operand is second. fflFor prefix operators, the first subtree is empty and the second subtree is that of the operand.

Listing 23.9 parse tree for a prefix operator %=s, showing an empty first subexpression [U+02C6]: ( token[ lexeme: %=, location: (2,7), preprocessor: 983811%fOi&], < ~&V(), [U+02C6]:<> token[ lexeme: s, location: (2,9)]>)

Listing 23.10 parse tree for a postfix operator s%=, showing an empty second subexpression

[U+02C6]: ( token[ lexeme: %=, location: (2,8), preprocessor: 983811%fOi&], < [U+02C6]:<> token[ lexeme: s, location: (2,7)], ~&V()>)

Listing 23.11 parse tree for an infix operator s%=t, with two non-empty subexpressions [U+02C6]: ( token[ lexeme: %=, filename: command-line, location: (2,8), preprocessor: 983811%fOi&], < [U+02C6]:<> token[ lexeme: s, location: (2,7)], [U+02C6]:<> token[ lexeme: t, location: (2,10)]>)

23.6.3 User defined command line option example We conclude the discussion of command line options with the brief example of a user de- fined command line option shown in Listing 23.14. The code shown in the listing provides the compiler with a new option, --log, which causes an extra annotation to be written to the preamble of every generated binary or executable file stating the names of all source files given on the command line. This information could be useful for a "make" utility to construct the dependence graph of modules in a large project. Theory of operation There could be several ways of accomplishing this effect, but the basic approach in this case is to alter the postformer field of the compiler’s specification. The function in this field takes the main parse tree after preprocessing but before evaluation. At this stage the parse tree will consist only of directives and declarations (i.e., = operator tokens) whose subexpressions have been reduced to single leaf nodes by evaluation. The first step is to form the set of file names by collecting the filename fields from all tokens in the parse tree, formatted into a string prefaced by the word "dependences:". Next, the function is constructed that will insert this string into the preamble of each file in a list of files. Executable files require slightly different treatment than other binary files, because the last line of the preamble in an executable file must contain the shell command to launch the virtual machine, so the annotation is inserted prior to the last line.

Listing 23.12 the parse tree for fa,b,cg, showing commas and aggregate operators [U+02C6]: ( token[ lexeme: {, location: (2,7), preprocessor: 154623%fOi&], < _{&V(), [U+02C6]: ( token[ lexeme: }, location: (2,13), preprocessor: 152%fOi&, semantics: 5%fOi&], < [U+02C6]: ( token[ lexeme: ,, location: (2,9), semantics: 177%fOi&], < [U+02C6]:<> token[ lexeme: a, location: (2,8)], [U+02C6]: ( token[ lexeme: ,, location: (2,11), semantics: 177%fOi&], < [U+02C6]:<> token[ lexeme: b, location: (2,10)], [U+02C6]:<> token[ lexeme: c, location: (2,12)]>)>),} &V()>)>)

Listing 23.13 the parse tree from Listing 23.12 after preprocessing [U+02C6]: ( token[ lexeme: {, location: (2,7), preprocessor: 852%fOi&, postprocessors: <0%fOi&>, semantics: 480%fOi&], < [U+02C6]:<> token[ lexeme: a, location: (2,8)], [U+02C6]:<> token[ lexeme: b, location: (2,10)], [U+02C6]:<> token[ lexeme: c, location: (2,12)]>)

Listing 23.14 command line option to add source dependence information to output files

#import std #import lag #import for #import mul #binary+

log = _{&iNC formulator[ mnemonic: log, formula: &r.postformer:=r [U+02C6]\-|}&r.postformer,! _{&|- ! -} &ar[U+02C6]& _{lexeme.&ihB==#?ard( &ard.postprocessors:=ar} &iNC+ [U+02C6]|/_&+ &al, _{&ard2falrvPDPMV), _token%TfOwXMk+ [U+02C6]\}& -+ _{&iNC; "d". *} preamble?~& preamble:= _{preamble; ?( -&}&h=]!/bin/sh',_{&z=]exec avram,}&yzx=]\&-, [U+02C6]T/_{&yyNNCT ((* :/' ) "d")--+} &yzPzNCC, --<'>+ --((* :/ ) "d")+ _{&iNNCT), dependences: '--+ mat +} &s+ *[U+02C6]0 :[U+02C6]~&vL ~&d.filename+-+-, help: list source file dependences in executables and libraries]

The binary file containing the new command line option is easily prepared as shown. $ fun lag for mul log.fun fun: writing log One might then test it on itself. $ fun --formulators ./log lag for mul log.fun --log fun: writing log $ cat log # # # dependences: for lag log.fun mul nat std # syCs{auXn[eWGCvbVB@wDt…

23.7 Help topics The --help-topics command line option requires a binary file as a paramter contain- ing a list of assignments of strings to functions (type %fm). For each item s: f of the list, the function f takes an argument of the form (<hparameteri:::>,hformulationi) to a list of character strings to be displayed when the compiler is invoked with the option --help s. That is, the string s is a possible parameter to the --help command line option. The parameters in the argument to f are any further parameters that may appear after s in a comma separated sequence on the command line. The default help topics are automatically updated when any change is made to the oper- ators, directives, or formulators (and by extension, to the types or pointer constructors), as

Listing 23.15 a user defined help topic #import std #import nat #import for #import mul #binary+ pri =

_{&iNC priority:} &r.formulators; -+ [U+02C6]plrTS( (--' + _&rS+zipp )[U+02C6]*D(leql$[U+02C6],&)+ <'option',------>--+ _{&lS, <'priority',-------->--+} &rS; * _{&h+ %nP),} &rF+ * [U+02C6]/_mnemonic favorite+-

shown in previous examples. This option is needed therefore only if a whole new classifi- cation of interactive help is intended, such as might arise if the language were extensively customized in other respects. Listing 23.15 shows a small example of how a user defined help topic can be speci- fied. Recall that certain command line options have a higher disambiguation priority than others (page 276), but that this information is accessible only by consulting the written documentation, which may be unavailable or obsolete. To correct this situation, the help topic defined in Listing 23.15 equips the compiler with an option --help priority, which will display the priorities of any command line options with priorities greater than zero. The operation of the code is very simple. It accesses the formulators field in the main formulation record that will be passed to it as its right argument, filters those with positive favorite fields, and displays a table showing the mnemonics and the priorities of the results. This code can be tested as follows. $ fun for mul pri.fun fun: writing pri $ fun --help-topics ./pri --help priority

option priority ------ -------- help 1 parse 1 decompile 1 archive 1 optimize 1 show 1 cast 1

Where are you going with this, Ikea boy? Brad Pitt in Fight Club

This chapter gives a general overview of the compiler source organization for the benefit of developers wishing to take it further. The compiler consists of a terse 6305 lines of source code at last count, written entirely in Ursala, divided among 25 library files and a very short main driver shipped under the src directory of the distribution tarball. These statistics do not include the standard libraries documented in Part III, except for std.fun and nat.fun. Library files are employed as a matter of programming style, not because the project is conceived as a compiler developer’s tool kit. Most library functions are geared to specific tasks without much scope for alternative applications. Nor is there any carefully planned set of abstractions meant to be sustained behind a stable API. Nevertheless, this material may be of interest either to developers inclined to make small enhancements to the lan- guage not covered by features discussed in the previous chapter, or to those concerned with scavenging parts of the code base for a new project. Comprehensive developer level documentation of the compiler will probably never ex- ist, because it would double the length of this manual, and because not much of the code is amenable to natural language descriptions in any case. Moreover, many parts of the com- piler perform quite ordinary tasks that a competent developer could implement in various ways more easily than consulting a reference. Furthermore, to the extent that any such documentation is useful, it necessarily renders itself obsolete. We therefore limit the scope of this chapter to a brief summary of each library module in relation to the others. Table 24.1 lists the compiler modules in the src directory with brief explanations of their purposes. Generally modules in the table depend only on modules appearing above them in the table, although there are cyclic dependences between std and nat, between tag and tco, and between for and mul. The intermodular dependences are documented in the executable shell script named bootstrap, also distributed under the src directory. Execution of this script will re-

module comment cor virtual machine combinator mnemonics std standard library nat natural number library com virtual machine combinator emulation ext data compression functions pag parser generator opt code optimization functions sol fixed point combinators tag type expression supporting functions tco table of type constructors psp table of pointer operators lag lexical analyzer generator ogl operator infrastructure ops main table of operators lam parse tree transformers for lambda abstraction apt specifications of invisible operators eto specification of declaration operators xfm symbol name resolution and substitution functions dir table of compiler directives fen parser and lexical analysis drivers and glue code pru precedence rule specifications for supporting functions for command line options mul compiler formulation data structure declaration def main table of command line options con command line parsing and glue code fun executable driver

build the compiler from source, but depends on the fun executable. The script has a com- mand line option to generate a compiler with extra profiling features, also documented within. A full build is an over night job, subject to performance variations, of course. Most of the CPU time for a build is spent on code optimization, and the next largest fraction on file compression. Any production version of the compiler will bootstrap an exact copy of itself, unless the time stamp on for.fun has changed. Some modifications to the source code may require multiple iterations of bootstrapping in order for the compiler to recover itself. The cor, std, and nat modules are previously documented in Listing 3.1 and Chap- ters 8 and 9. The remainder of this chapter expands on Table 24.1 with some more detailed comments on the other modules.

24.1 com One way to simplify the job of implementing an emulator for the virtual machine is to code the smallest subset of combinators necessary for universality, and arrange for the re- mainder to be translated dynamically into these. The com module contains a selection of virtual machine code transformaters relevant to this task. For example, a program of the form iterate(p,f) using the virtual machine’s iterate combinator can be trans- formed into one using only recursion. The rewrite function automatically detects the root combinator of a given program and transforms it if possible. This function is written to an external file as a C language character constant when this library is compiled, which is used by avram as a sort of virtual "firmware" in the main evaluation loop. The other use of this module is in the opt code optimization module (Section 24.4), where it is used for abstract interpretation when optimizing higher order functions.

24.2 ext This module contains the data compression functions used with compressed types (t%Q), archived libraries, and self-extracting executables. Compression is a bottleneck in large compilations that would reward a faster implementation of these functions with noticably better performance. 0 The compression algorithm transforms a given tree t to a tuple ..p;s/;t / if doing so 0 will result in a smaller size, or to ../;t/ otherwise. The tree t is like t with all occurrences of its maximum shared subtree deleted. The subtree s is that which is deleted, and p is 0 another tree identifying the paths from the root to the deleted subtrees in t , similarly to a 0 pointer constant. The tuple ..p;s/;t / itself usually can be compressed further in the same way, so the algorithm iterates until a fixed point is reached or until the size of the largest shared subtree falls below a user defined threshold.

24.3 pag This module contains a generic parser generator based on an ad hoc theory, taking a data structure of type _syntax describing the grammar of the language as input. Traditional parser generator tools are inadequate for the idiosyncrasies of Ursala with regard to op- erator arity and overloading, but a hand coded parser would be too difficult to maintain, especially with user defined operators. The parsers generated by this method are much like traditional bottom-up operator precedence parsers using a stack, but are generalized to accommodate operator arity dis- ambiguation on the fly and a choice of precedence relations depending on the arities of both operators being compared. Rather than taking a list of tokens as input, the parser takes a list of lists of tokens, with white space implied between the lists, but juxtaposition of the tokens within each list (see page 456). Each token is first annotated with a list of four boolean values to indicate its possible arities prior to disambiguation. This information is derived partly from the operator specifications encoded by the syntax record parameterizing the parser, and partly by contextual information (for example, that the last token in a list can’t be a prefix operator unless it has no other arity). A token is ready to be shifted or reduced only when all but one of its flags are cleared. Otherwise a third alternative, namely a disambiguation step, is performed to eliminated at least one flag by contextual information that may at this stage depend on the stack contents. An exception to the conventional operator precedence parsing rules is made when a pre- fix operator is followed by a postfix operator and both are mutually related in precedence. In this case, they are simulataneously reduced, so that expressions like <> or {} can be

parsed as required. This test also applies to prefix and postfix operators with an expression between them, wherein the reduction results in a parse tree like that of Listing 23.12. Although the syntax data structure doesn’t explicitly represent any distinction be- tween aggregate operators and ordinary prefix or postfix operators, aggregate operators are indicated by being mutually related with respect to prefix-postfix precedence. There is never a need for this condition to hold with other prefix or postfix operators, because the relation is meaningful only in one direction.

24.4 opt Code optimization functions are stored in the opt library module. The optimizations are concerned with transforming virtual machine code to simpler or more efficient forms while preserving semantic equivalence. Optimizations include things like constant folding, boolean and first order logic sim- plifications, factoring of common subexpressions, some forms of dead code removal, and other ad hoc transformations pertaining to list combinators and recursion. The results are not provably optimal, which would be an undecidable problem, but are believed to be semantically correct and generally useful. A more rigorous investigation of code optimiza- tion for this virtual machine model awaits the attention of a suitably qualified algebraist. An intermediate representation of the virtual machine code is used during optimization, which is a tree of combinators (type %sfOZXT) as explained on pages 86 and 140. The left of each node is a mnemonic from the cor library, and the right is a function that will transform this representation to virtual code given the virtual code for each subtree. There are further possibilities for optimization of higher order functions. A second order function in this tree representation can be evaluated with a symbolic argument by abstract interpretation. Several functions concerned with abstract interpretation are de- fined in the library. The result, if it is computable, will be the representation of a first order function in which some of the nodes contain an unspecifed semantic function. Op- timization in this form followed by conversion back to second order often will be very effective. This technique generalizes to higher orders, but the drawback is that it is not possible to infer the order of a function by its virtual code alone, and mistakenly assuming a higher order than intended will generally incur a loss of semantic equivalence. In certain cases the order can be detected from source level clues, such as functions defined by lambda abstraction or functions using operators implying a higher order. The #order+ compiler directive, which is currently unused, could serve as a pragma for the programmer to pass this information to the optimizer. Code optimization is an interesting area for further work on the compiler, but should not be pursued indiscriminately. Optimizations that are unlikely to be needed in practice will serve only to slow down the compiler. Introduction of new optimizations that conflict with existing ones (i.e., by implying incompatible notions as to what constitutes optimality) can cause non-termination of the optimizer. Of course, semantically incorrect "optimizations" can have disastrous consequences. Any changes to the optimization routines should be

validated at a minimum by establishing that the compiler exactly reproduces itself with sufficiently many iterations of bootstrapping.

24.5 sol The main purpose of this library module is to implement the algorithm for general solution of systems of recurrences. The #fix compiler directive documented in Section 7.5.3 is one source level interface to this facility, and the use of mutually dependent record declarations is the other (page 156). The general_solution function takes a list of equations and user defined fixed point combinators to its solution following a calling convention with detailed documentation in the source, including a worked example. The general solution algorithm consists mainly of term rewriting iterations necessary to separate a system of mutually dependent equations to equations in one variable. Following that, obtaining the solutions is a straightforward application of each equation’s respective fixed point combinator. Thorough exposition of the algorithm is a subject for a separate article. However, being only sixteen lines of code and embedding many typed breakpoints of the style described starting on page 144, its inner workings are easily open to inspection. This module also includes the function_fixer and fix_lifter functions ex- plained in Section 7.5.3.

24.6 tag This module contains some functions relevant to type expressions, and also contains the declaration of the type_constructor record. Many of the functions defined in this module underlie the instance generators of primi- tive types and type constructors, along with their statistical distributions. These properties are adjustable only by hard coded changes to the compiler source through this module. Miscellaneous functions used in the definitions of various type constructors are also present, as is the execution function, which builds a type expression from a list of constructors by executing their microcode (see page 435). This function is needed to define the semantics of operators allowing type expressions as suffixes (e.g., the % and %- operators, Section 6.11.2). The fixed point combinators general_type_fixer and lifted_type_fixer are also defined in this module. These are used internally by the compiler for solving sys- tems of mutually dependent record declarations, but may also be of some use to developers wishing to construct mutually recursive types explicitly.

24.7 tco

This library module contains the main table of type constructors. Adding a user defined type constructor to this table and rebuilding the compiler can be done as an alternative to

loading one dynamically from binary a file as described in Section 23.3. The effect will be that the user defined type constructor becomes a permanent feature of the language.

24.8 psp This module contains the main table of pointer constructors, the declaration of the pnode record type specifying pointer constructors, and the percolation function used to translate a list of pointer constructors to its pointer or pseudo-pointer functional seman- tics. The percolation function is used in the definition of any operator that allows a pointer expression as a suffix. Adding a user defined pointer constructor to this table can be done as an alternative to loading it from a binary file as described in Section 23.1. The effect will be to make it a permanent feature of the language. As discussed previously, there are no unused pointer mnemonics remaining, and changing an existing one will break backward compatibility. However, an unlimited number of escape codes can be added, which would be done by appending more pnode records to the escapes table in the source.

24.9 lag

Functions pertaining to lexical analysis are stored in the lag library. This library also includes the declaration of the token record type, and a few operations on parse trees. Lexical analysis is less automted than parsing (Section 24.3), requiring essentially a hand coded scanner for each lexical class (e.g., numbers, strings, etcetera) although some of these functions are parameterized by lists of operators or directives derived automati- cally from tables defined elsewhere. The scanner for each lexical class consists of a triple .n;p;f/ called a "plugin", where n is a natural number describing the priority of the scanner, p is a predicate to detect the class, and f is a function to lex it. The functions p and f take an argument of type %nWsLLXJ of the form _{&J(h,(l,c),<s :::>), where refer(h) is the lexical ana- lyzer meant to be called recursively, l and c are the line and column numbers of the current character in the input stream, and s is the current line of the input stream beginning with the current character. The function p is supposed to return a boolean value that is true if s begins with an instance of the lexical class in question, and false otherwise. The function f is applied only when p is true, and should return list of token records beginning with the one corresponding to the current position in the input stream, and followed by those obtained from a recursive call to h. That implies that a new argument 0 0 0 of the form} &J(h,(l ,c ),<s :::>) must be constructed and passed in a recursive invocation of h, (usually of the form [U+02C6]R/~&f:::) with the line and column numbers adjusted accordingly, and the input stream advanced to the character past the end of the current token. Alternatively, if an error is detected, f can raise an exception, but should include the successors of the line and column numbers as part of the message.

24.10 ogl This library module contains the operator record type declaration (Section 23.5.1) and various functions in support of operator definitions. One useful entry point is the token_forms function, which takes a list of operator records to a list of token records suitable for parameterizing the built_ins plugin of the lag module described in the previous section. Another is the propagation function, for operators allowing pseudo-pointers as operands, whose usage is best understood by looking at a few examples in the ops module.

24.11 ops

This module contains the main table of operators. Adding a new operator to this table and rebuilding the compiler is a more persistent alternative to loading a user defined operator from a binary file as described in Section 23.5. Note that unlike operator specifications loaded from a file, these tables are fed through a function in the default_operators declaration that initializes the optimizers fields to copies of the optimization function defined in the opt module if they are non-empty. This feature is not necessarily appropriate if new operators are to be defined over non-functional semantic domains, and would require some minor reorganization. 24.12 lam

This module contains the code that allows functions to be specified by lambda abstraction. Lambda abstraction is a top-down source transformation implemented by a fairly simple algorithm. An expression of the form ("x","y"). f(g "x","y"), for example, is transformed to f[U+02C6](g+ _&l,&r), with deconstructors replacing the variables, compo- sition replacing application, and the couple operator used in application of functions of pairs. Subexpressions without bound variables are mapped to constant functions by the algorithm. The algorithm requires no modification if new operators are defined in the lan- guage, because their semantic functions are obtained from the semantics fields in the parse tree regardless. Being a source transformation, the lambda abstraction code forms part of the prepro- cessor for the . operator, but because this operator is overloaded, the preprocessor is not defined until the arity is determined to be either postfix or infix. The postfix usage is initially parsed as a function application (e.g., ("x".) e) with the implied application

token at the root of the parse tree, so it becomes the responsibility the application token’s preprocessor to reorganize the tree appropriately. The virtual code generated by a naive implementation of the above algorithm tends to be suboptimal, so this library also includes several postprocessing transformations designed to improve the quality. These are semantically correct but do not always improve the code, and therefore can be disabled by the #pessimize directive.

24.13 apt This module contains specifications for the tokens representing white space in a source file. There are three kinds of white space, which are the space between consecutive dec- larations, the space betwen a functional expression and its argument, and the space where there is insufficient information to distinguish between the two other cases. These are designated as separation, application, and juxtaposition respectively. Only application has a meaningful semantics, while the other two are expected to be transformed out in the course of preprocessing and will raise an exception if they are ever evaluated. The preprocessor of the application token is responsible for performing all al- gebraic transformations associated with dyadic operators. For this reason, the token is defined by way of a function that takes the main operator table as input, including any run time additions. Several minor source level optimizations are also performed by the preprocessor of the application token, such as recognition of lambda abstraction as mentioned in the previous section, and elimination of binary to unary combinators in some cases. These transformations depend on some of the operators having the mnemonics they have, inde- pendently of the table of operators.

24.14 eto

This module defines the tokens associated with the declaration operators, = and ::. These operators do not appear in the main table of operators but are defined instead in this mod- ule, mainly because their definitions are parameterized by the rest of the operators for various reasons. The :: operator has no semantics at all but only a preprocessor that transforms itself to a sequence of ordinary declarations in terms of the = operator, and also inserts #fix directives with appropriate fixed point combinators for types and functions in the event of self-referential declarations. It includes features to detect when a lifted fixed point combinator can be used in preference to an ordinary one to achieve the equivalent order, and uses it if possible (see Section 7.5.3 for theoretical background). The = operator semantics follows a required convention of evaluating an expression to an assignment s : x, with s being the identifier and x being the value of the body

of the expression. The preprocessor of this operator is complicated by the need to in- teract correctly with the #pessimize directive, and by the need to transform declara- tions like f("x") = y in conventional mathematical notation to the lambda abstraction f = "x". y. Although this library is short, the code in it is more difficult than most and will yield only to a meticulous reading.

24.15 xfm This library is concerned primarily with establishing the rules of scope described in Sec- tion 7.2 and with resolution of symbolic names as needed for evaluation of expressions. There are also functions concerned with dead code removal, and with invoking the general solution algorithm defined in the sol module (Section 24.5) when cyclic dependences are detected. The latter are applied globally to the parse tree of a given compilation in the con module (Section 24.22), whereas the former constitute the bulk of the preprocessor for the #hide directive defined in the dir library (Section 24.16).

24.16 dir The directive record declaration describing compiler directives is declared in this module, as is the main table of compiler directives. Adding a user defined compiler direc- tive specification to this table and rebuilding the compiler has a similar effect to loading a directive specification from a binary file as described in Section 23.4, except that in this case the directive will become a permanent feature of the language. This library also declares a function called token_forms. Similarly to a function of the same name in ogl (Section 24.10), this function transforms a list of directive speci- fications to a list of tokens. The main purpose of this function is to construct the list of tokens used to parameterize the directives plugin in the lexical analyizer generator (Section 24.9), but it also has applications in various other contexts where there is a need to construct a parse tree containing directives.

24.17 fen

This module instantiates the parser and lexical analyzer generators of the pag and lag modules with the operators, directives, and precedence rules from ops, eto, apt, dir, and pru. Certain other details are also addressed in this module, such as the precedence rules for such non-operators as white space, commas, smart comments (page 245), and dash bracket delimiters (page 118). The lexical analyzer produced by the lexer function in this module includes a hand written scanner that inserts separation tokens between consecutive declarations so that the automatically generated parser can apply to a whole file. The relaxation of the requirement that all compiler directives appear in matched 472

opening and closing pairs is also a feature of this lexical analyzer, which inserts matching directives using a hand written algorithm.

24.18 pru This module contains the main tables of precedence rules depicted in Tables 5.3 through 5.6, and also contains a function for pretty printing a parse tree, which is used by the --parse command line option. A function to compute the operator precedence equiva- lence classes shown in Table 5.2 is also included, but the underlying equivalence relation is determined by the peer fields of the operators defined in the ops module. Redefining the operator precedence rules in this module followed by rebuilding the compiler can be done as an alternative to temporarily loading the rules from a file as ex- plained in Section 23.2. The effect will be a permanent change in the operator precedence rules of the language. As noted previously, changes in precedence rules are likely to break backward compatibility.

24.19 for

This module contains the declaration of the formulator record used to describe com- mand line options as explained in Section 23.6.1, and a couple of functions that are help- ful for constructing records of this type. There are also some important constants de- clared in this module, such as the email address of the Ursala project maintainer, and the main compiler version number, which is displayed when the compiler is invoked with the --version option. The version number may also be supplemented with a time stamp, which is derived from the time stamp of this source file. One function in this module, directive_based_formulators, takes a list of compiler directive specifications as input, and returns a list of formulator records. This function is the means whereby any compiler directive automatically induces a corre- sponding command line option. Another function, help_formulator, takes a table of help topics as described in Section 23.7 and returns the formulator for the --help command line option parameter- ized by those topics. 24.20 mul

This very short module contains the declaration for the formulator record, which em- bodies a complete specification for the compiler by including all tables previously men- tioned, as explained in Section 23.6.2. A couple of functions define default values for some of the formulation fields, and the default_formulation function takes a table of formulator records to a formulation using them.

24.21 def The main tables of formulator records and help topics are stored in this module. These tables can be modified and the compiler rebuilt as an alternative to loading help topics or command line option specifications from a binary file as explained in Sections 23.6 and 23.7. In this case, the modifications will become permanent features of the compiler.

24.22 con

This module contains functions responsible for managing the main flow of control during a compilation. The customized function performs the initial interpretation of com- mand line options and parameters to arrive at the formulation record that will be used subsequently. Thereafter, compilation is divided into three main phases, corresponding to the results that can be inspected by the --phase command line option. The first covers lexical analysis and parsing. The second covers preprocessing, dependence analysis, and some local evaluation of expressions. The third phase includes all remaining evaluation and execution of compiler directives, and the construction of the list of output files. Each of these phases is specified by one of the functions in the list of phases. These are higher order functions parameterized by a formulation record, which return func- tions operating on parse trees and files. The composition of these functions, achieved by the compiler function, constitutes the bulk of the compiler.

24.23 fun This file contains the executable driver for the functions defined in the con module. The additional features implemented in this file are detection and handling of the --phase command line option, displaying the default help messages when no files or options are given, supporting the command-name feature of the formulation by incorporating it into diagnostic messages, displaying a warning when output generating directives are omitted, and trapping non-printing characters in diagnostic messages.

While it remains a burden assiduously avoided, it is not un- expected and thus not beyond a measure of control. The Architect in The Matrix Reloaded

A problem with software documentation perhaps first observed by Gerald Weinberg is that if it’s too polished, it gets out of sync with the software because it becomes intimidating for some people to update it. This appendix is reserved for contributions by maintainers, site administrators, or any- one redistributing the software who is disinclined to alter the main text. Any commentary, errata, or documentation of new features recorded here should be deemed to take prece- dence.

processors for output purposes only. The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work’s title, preceding the beginning of the body of the text. A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition. The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License. 2. VERBATIM COPYING

A ask, 406 assignment pointer constructor, 61 assignment operator, 198, 202 assignment type constructor, 122 associate left, 291 a atan, 328 address type, 108, 128 atanh, 329 job argument deconstructor, 61, 72 avram, 34, 120 abs combinators, 68, 112 floating point, 325 copyright, 54 rational, 321 download, 51 abs internals, 465 BCD, 317 libraries, 45 integer, 313 axiom acos, 328 computer algebra system, 404, 418 address enumeration pseudo-pointer, 82 url, 411 address map pseudo-pointer, 90 axis, 384 --alias option, 279 axparse, 414 all, 304 all same pseudo-pointer, 84 B all same, 304 conjunction pseudo-pointer, 77, 78 record type constructor, 167 alternate list items pseudo-pointers, 83 ampersand operator, 201 b anonymous recursion, 44 boolean type, 110 any, 305 back lit rendering, 401 application specific languages, 279 backward induction, 32 bad tag diagnostic, 101 apply-to-both operator, 229 apt library, 471 bandwidth, 341 apt-get utility, 404 bash, 203 arbitrage, 27 bash, 52, 143, 192, 280, 404, 406, 420 arbitrary precision, 51, 111, 117, 195 program control, 408 between, 353 matrices, 357 arbitrary precision arithmetic, 356 --binary option, 275 arc, 293 #binary compiler directive, 17, 251, 253 --archive option, 32, 215, 255, 281 #binary directive, 282 ari, 334 binary files, 264 binary to unary combinators, 198, 199 ari, 329 arrays, 128 mapped, 200 asin, 328 suffixes, 200

binary type constructors, 121 choose, 310 binomial lattice, 27, 29 mp chord fit, 341 bipartitioning operators, 223 chov, 353 bipartitioning pseudo-pointer, 89 circuits bisection, 331 AC, 35 bleq, 316 digital, 13, 268 block, 295 cli library, 404 A booktabs LT X package, 362, 363 data structures, 419 E vertical rules, 365 closing, 416 boolean operators, 212, 303 closure, 298 boolean representation, 69, 77, 110, 123 com library, 465 bootstrap shell script, 463 combinations, 310 both, 304 command line data structures, 257, 289 brainf*** language, 105 command line options brange, 319 customization, 454 bus, 327 comment delimiters, 139 bwi backward induction, 375 comments, 245 BWI alerts directive, 261 boss with idea, 141, 173 comparison operators, 213 compiler directives C customization, 439 crash type operator, 142 syntax, 246 list pointer constructor, 61 table, 246 c completing, 416 intersection pseudo-pointer, 302 complex library, 114 c complex numbers character type, 110, 117 precision, 43 intersection pseudo-pointer, 77 composition, 19, 20, 189, 194 C language, 1, 12, 110 optimization, 190 C++ language, 199 compression, 32, 281 capacitors, 37 granularity, 168 cardinality, 311 internals, 465 cartesian product, 299 of libraries, 215 cartesian product pseudo-pointer, 91 of phase dumps, 279 case, 290 compression function, 132 cases, 290 computer algebra, 404 --cast option, 275, 280 con library, 474 #cast directive, 263 concatenation, 74 character constants, 110, 131 operator, 198 characters, 287 conditional combinator, 68, 71, 210 characters, 110 conditional operators, 210 choice, 293 suffixes, 211 choices, 299 configuration files, 259 choleski, 413 485

conjunction, 77 decompilation, 114, 140, 201, 280 constant combinator, 198, 199 deconstructors, 57 constrained optimization, 351, 354 compound, 59 contingent claims, 27 lists, 59 continuous maps, 351 nested, 58 contrib subdirectory, 259, 286 relative, 59 cop library, 35, 351 table, 60 copyright information, 53 def library, 474 cor library, 112, 280, 287 defensive programming, 145 correlation, 336 --depend option, 273, 280 cos, 328 #depend directive, 273 cosmology, 191 derivative, 329 coupling operators, 229 derivatives covariance, 336 financial, 27 cross, 299 mathematical, 34, 35, 329, 354 crypttab, 68 partial, 35, 354 cumulative conditionals, 190, 195, 290 DES key space, 310 exceptions, 236 dgelsd, 339 cu prod, 331 difference current, 35 natural, 309 current division, 37, 42 rational, 322 currying, 179, 199 difference curve, 386 BCD, 318 cu sum, 332 integer, 314 cuts, 299 differentiation, 35 Cygnus tools, 52 digits, 287 dir library, 472 D --directives option, 439, 446 distribution pseudo-pointer, 75 disassembly, 114, 140 dual type tree constructor, 122 disjunction, 77 d distributing bipartition by comparison, 93 type stack dup, 165, 166 distributing bipartition operator, 224 dagglm, 339 distributing bipartition pseudo-pointer, 88 dash bracket notation, 118, 189, 193 distributing filter by comparison, 93 dash operator, 214, 250, 252, 281 distributing filter operator, 222 --data option, 283 distributing filter pseudo-pointer, 88 Debian, 51, 52, 404 distribution operator, 198 debugging tips, 142, 144, 245, 255, 266 div, 326 customization, 431 division type errors, 145 natural, 310 with --phase, 279 division with --trace, 280, 422 integer, 314, 319 declarations, 247 dollar sign internals, 471

forward induction, 376 glint, 305 forward sideways induction, 378 glpk library, 356 Free Software Foundation, 53 GNU Scientific Library, 12, 35, 329, 330, free unions, 122, 127, 133 354 fromint, 319 series extrapolation, 334 fswi, 378 gp, 410 function application, 19 gpl function, 289 function application internals, 471 --gpl option, 281 functional composition, 19, 20, 189 graph plotting, 381 lifted, 194 data structures, 383 operator, 208 default settings, 384 optimization, 190 discrete points, 389 suffixes, 209 inline code, 389 with pointers, 208 interpolation, 389 functional programming, 12 positioning axes, 391 impurity, 82, 169, 405 symbolic axes, 389 function fixer, 269, 468 three dimensional, 394 fun version identifier, 248, 261 data structures, 402 fused, 292 eccentricity, 394 fwi, 376 elevation, 397 focal point, 394, 396 G light sources, 397 glomming pointer constructor, 63 observer coordinates, 396 grid type constructor, 123, 369 zoom, 397 g with multiple axes, 391 general primitive type, 114, 120 Graphviz, 97 list conjunction pseudo-pointer, 70 greatest common divisor, 310 gang, 291 Greeks, 34 gap, 411 grid, 369 number theory package, 404 grow, 112 gcase, 291 guard combinator, 236 gcd, 310 gcp, 294 H gdif, 305 function application pointer, 79 General Public License, 53 h generalized difference by comparison, 93 head deconstructor, 59 generalized difference pseudo-pointer, 87 recursive type operator, 170 generalized intersection by comparison, 92 hackers, 12, 112, 114 generalized intersection pseudo-pointer, 87 half, 308 generalized set operations, 305 half list pseudo-pointers, 83 general type fixer, 271 half line, 351 geo, 334 handshake, 416 gint, 305 hashing operators, 238 gldif, 305 --help option, 276

help customization, 461 inverse, 320 --help-topics option, 461 iol, 294 hexadecimal, 116 iota, 311 #hide compiler directive, 252, 262 iprod, 333 #hide directive, 276 ISO code, 110, 118, 131, 169 Hoare, Tony, 290 iteration operator, 208 hop, 406, 421 J I job pointer constructor, 61, 72, 140 pairwise relative pointer, 64 job type constructor, 127 type instance recognizer, 139 j i primitive complex type, 114 identity pointer, 60 set difference pseudo-pointer, 77 instance generator, 130, 168 jacobian, 35, 354 identifier syntax, 248 jacobian row, 355 from file names, 282 Java, 12 impedance, 37, 43 k imperative programming, 125 --implicit-imports option, 283 comment type operator, 138 #import compiler directive, 19, 136, 215, list disjunction pseudo-pointer, 70 254, 255 Kinsol library, 12, 351, 354 semantics, 249 #import directive, 281, 283 L indexable, 303 list flattening pseudo-pointer, 65 list type constructor, 127 inductors, 37 l inf, 324 left deconstructor, 58 infinite streams, 257 installation instructions, 52, 286 type stack deconstructor, 165, 166 int library, 312 label, 366 integer programming, 360 lag library, 469 integers, 312 lam library, 470 integral, 330 lambda abstraction, 24, 194, 254 in recurrences, 269, 272 interact combinator, 280, 415 internals, 470 interaction protocols, 415 interactive applications, 260 operator, 206 interpolation, 25 semantics, 206 comparison of methods, 342 lapack, 12, 128, 339, 356, 413 multivariate, 346 lat library, 125, 126, 369 A LT X polynomial, 341 E sinusoidal, 341 graphics, 21, 25 spline, 341 labels, 366 intersecting, 302 tables, 45, 362 interval arithmetic, 436 latex document, 382 interview questions, 242 lattices, 369

mpfr library, 51, 111, 117, 195, 324 not, 303 matrices, 356 now, 412 mp one piece polynomial, 341 --no-warnings option, 279 mp sinusoid, 340 range, 311 mp solve, 357 nth deriv, 330 mp sparso, 357 nth diff, 332 msolve, 357 num, 295 mtwist library, 293 numerical differentiation, 35, 329, 342, 354 mul library, 473 numerical integration, 330 multihop, 407 multivariate, 346 O mvnorm, 413 composition pseudo-pointer, 79 opaque type constructor, 114, 130 N o a-tree type constructor, 128 opaque type, 116, 146 cumulative normal probability, 337 tree folding pseudo-pointer, 70 empty constant pseudo-pointer, 65 obfuscation, 67, 120 n object orientation, 24, 120, 150 assignment name deconstructor, 61 Octave, 12, 404 natural number type, 115 octave, 410 name clashes, 250, 251 octhex, 414 resolution, 252, 254 odd, 307 NaN (not a number), 135 odd nan, 325 BCD, 317 nat library, 116, 286, 307 ogl library, 470 natural numbers, 307 one-to-each operator, 231 representation, 76 one piece polynomial, 341 negation one time, 379 pseudo-pointer, 70 only command line parameter, 427 negation open, 421 BCD, 317 operators, 175 integer, 313 aggregate, 186, 192, 194 rational, 320 ambiguity, 178 negation pseudo-pointer, 89 arity, 177 negative, 325 associativity, 179 neither, 304 customization, 447, 470 next, 292 declaration, 185 ninf, 325 dyadic, 182 nleq, 19, 307 equivalence classes, 179 --no-core-dumps option, 279 precedence, 178, 448 non-determinacy, 293 customization, 430, 473 non-linear optimization, 351 suffixes, 176, 192 non-mutability, 203 syntax, 176 non-strictness, 210, 212, 303 --operators option, 447

oprod, 333 #pessimize directive, 266 ops library, 470 --phase option, 474 opt library, 467 --phase option, 279 #optimize directive, 266 physics, 333 options pi, 325 command line, 260, 275, 277 plo library, 381 customization, 454, 473 plot, 381 financial, 27 plotting in operators, 450 data structures, 383 ordered, 304 plus, 326 ordered bipartition operators, 224 pointer constructors, 19, 56, 61 outer product, 333 customization, 425, 469 #output directive escape codes, 80, 81, 428 dot function interface, 289 examples, 62 #output directive, 262, 263 table, 60 dot function interface, 264 --pointers option, 427 A with LT X files, 363 poly dif, 342 E with plots, 382 polymorphism, 149, 161 over, 353 polynomial interpolation, 341 #postprocess directive, 275 P Postscript, 21, 394 pointer constructor, 63, 71, 79 pow, 326 printing type operator, 140 power p natural, 310 parsing type operator, 139 rational, 322 zip pseudo-pointer, 75, 294 power package, 51 BCD, 318 pad, 296 powerset, 299 pag library, 466 --precedence option, 430 palindromes, 453 precedence rules, 178, 430 parallel combination, 36 predecessor, 143 parameterized option, 257 BCD, 317 pari-gp math package, 404 integer, 313 parsable primitive types, 139 predeclared identifiers, 248 --parse command line option, 178, 281 predicates, 212, 301 parse trees, 273 on lists, 304 spacers, 449 prefix predicate pseudo-pointer, 92 specifications, 442, 456 prefix recognition operator, 241 parser internals, 466 #preprocess directive, 273 partial reification pseudo-pointer, 90 primitive types, 107 partition by comparison pseudo-pointer, 84 printf, 338 partitioning operator, 225 probability density, 21 PDF, 21 product permutations, 299 492

reduction pseudo-pointer, 89 sep, 297 refer combinator, 68, 71, 145, 211, 213 seq, 417 referential transparency, 405 series combination, 35 reification operators, 238 series extrapolation, 35 relative addressing operator, 205 series operations, 331 remainder extrapolation, 334 natural, 309 set shell command, 264 remainder set shell command, 258 BCD, 318 set union operator, 198 integer, 314 sets, 65, 76, 134 remote shells, 406 delimiters, 187 ren library, 394 sever, 372 rendering, 401 sgn rep, 292 floating point, 326 replacement functions, 356, 360 sgn compile time, 216 BCD, 317 run time, 217 integer, 313 replacement lp solver, 360 sh, 420 residual, 309 shell, 419 resistors, 36 --show option, 140, 280 reverse composition operator, 208 #show directive, 263 right lit rendering, 401 showtabs example program, 66 rlc, 297 shrink, 112 rleq, 321 sideways induction, 377 root, 310 simplified, 321 root finder, 330 sin, 328 run length code, 297 singly branched, 303 sinusoid, 339, 340 S sinusoid, 389 mapping pseudo-pointer, 70 skip, 295 set type constructor, 133 skipwhile, 298 s smart comments, 245 list-to-set pointer, 65, 77, 84, 134 sol library, 269, 272, 468 string type, 117 sopen, 421 sask, 407, 421 sorting operator, 220 scientific, 322 source code, 463 scientific notation, 368 source time stamp, 248, 261 scilab, 410 sparse matrices, 356 math package, 404 sparso, 357 scope rules, 249 sqr, 325 searching operators, 220 sqrt, 326 sectioned table, 363 src/ subdirectory, 463 segmentation fault, 141 ssh, 420 self extracting files, 281 494