Version 0.2


  1. Syntax
  2. Execution
  3. Function and Expression Semantics
    1. Symbols
    2. Lambda Abstractions
    3. Applications
  4. Implementation Notes
    1. Data Structures
    2. Examining Functions

1. Syntax

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 ' ', ',', '\'

2. Execution

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.

3. Function and Expression Semantics

3.1. Symbols

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.

3.2. Lambda Abstractions

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.

3.3. Applications

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:


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.)

4. Implementation Notes

4.1. Data Structures

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.

4.2. Examining Functions

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.