In LOLA, every token is a single character. Whitespace is significant.
A LOLA program comprises one or more functions. Of these, exactly one must be the main function. Any function other than the main function begins its definition with a symbol that is the function's name. No two functions may have the same name.
program ::= line program ::= program newline-char line line ::= functional-line line ::= functional-line comment functional-line ::= functional-line ::= function functional-line ::= main-function function ::= symbol expression main-function ::= expression newline-char ::= CR newline-char ::= LF comment ::= ' ' comment ::= HT comment ::= comment comment-char comment-char ::= any ASCII printable character comment-char ::= HT expression ::= abstraction expression ::= application-expression abstraction ::= '\' expression application-expression ::= application application-expression ::= symbol application ::= application-expression expression ',' symbol ::= any ASCII printable character except ' ', ',', '\'
The state of the program at any time is determined by the "current expression", which is initialised to the main function when the program begins.
LOLA relies heavily on Church integers for input and output. A Church integer is a function which, for a given non-negative integer n, takes two arguments one after the other and applies the first argument n times to the second.
The following table gives the first few Church integers. The notation will be explained in section 3.
| Number | As a Church integer (c) |
cfx,, is equivalent to |
|---|---|---|
| 0 | \\a |
x |
| 1 | \a (i.e. the identity function) |
fx, |
| 2 | \\bba,, |
ffx,, |
| 3 | \\bbba,,, |
fffx,,, |
The current expression is lazily evaluated until it is a lambda
abstraction (technically speaking, until it is in weak head normal
form). It is then applied to the lambda abstraction \\a,
i.e. the Church integer 0, and the action taken depends on the result of this
application.
Current expression applied to \\a |
Action |
|---|---|
| A Church integer | Outputs the character in the implementation character set
corresponding to the value of the Church integer. The
current expression applied to \a becomes the new
current expression. |
\\b (the K combinator of SKI calculus) |
Terminates the program. The current expression applied
to \a must evaluate to a Church integer, which
becomes the program's exit code. |
\\\b |
Retrieves a character from the standard input. The
current expression applied to \a, and then applied to
the Church integer having the value of the retrieved character in
the implementation character set (or \\b if end of file has been reached), becomes the new current expression. |
| Anything else | A runtime error. |
This process is repeated until the program exits.
Usually, any symbol occurring within the body of a function is taken to mean the function that has that symbol as its name.
The context of a lambda abstraction overrides certain symbols, as described in the next section.
The \ operator represents the lambda of lambda-calculus.
The expression beginning with it is a lambda abstraction.
The parameter of the lambda abstraction is not named. Instead, a
notation based on de Bruijn indexes is used. Lowercase letters of the basic
Latin alphabet represent these parameters, with a representing
the parameter of the innermost lambda abstraction of which it is a part,
b representing the next lambda abstraction outwards, and so
on.
Any named functions are overridden by the semantics of lowercase letters as parameters in lambda abstractions. Therefore, a named function cannot be accessed from within a lambda abstraction if the function name conflicts with a letter that denotes a parameter of the abstraction within the abstraction nesting depth.
The , operator represents the application of one function to
another. It operates on the two functions preceding it in RPN
fashion. The left operand is the function to apply, and the right
operand is what to apply it to. For example:
f\a\ba,,
f\\ab,,
applies \a\ba,, to \\ab,, giving
(\\ab,)\(\\ab,)a,,, which in turn evaluates to
\\a\(\\ab,)a,,. (LOLA doesn't support brackets; they are
just used here to illustrate what is going on.)
The current expression is the only program state information that an implementation needs to store. Typically, expressions within expressions would be held by reference, and a function call would be internally a simple reference to the function's definition.
As with almost any functional programming language, garbage collection is a necessity. Because expressions can be recursive, a reference-counting garbage collector is not suitable for implementing LOLA; the garbage collector must traverse the expression structure from the current expression in order to determine what is still in use and what isn't.
Necessary to the functioning of LOLA is the ability to identify the possible function forms to which an expression can legally be reduced. The same function may be represented by a number of different expressions both in code and internally; an implementation must behave identically regardless of which form is being used.
The simplest means of testing functions is to use internal objects to
"unchurch" integers, by applying the Church integer to objects representing
increment and the number 0. This technique can also be used to detect
the lambda abstraction \\b, and a further application can be used
to detect \\\b.