Lithium Language
Henry Strickland
in the domain
IMPORTANT:
To give a FUNNY_SELF operator '_', define FUZZY_SELF
in your enviroment:
FUZZY_SELF=1 tclsh run.....
This is left out, by default, so that lithium programs
will be deterministic.
Nodes:
Nodes are the only value type in Lithium.
All variables are untyped, and may be any node.
Three kinds of nodes are
-- Atoms,
-- Pairs, and
-- PartialFunctions.
Atoms:
There are 256 atoms. Each has
-- a character
-- an integer value 0..255
-- a meaning as an expression
-- a meaning as a function
Each atom is written as a single character.
The "integer value" does NOT correspond to the "character" exactly
as in C; rather, there is an offset of -48 (modulo 256), so that
the characters '0' thru '9' have integer values 0 thru 9, although
their ASCII values are 48 thru 57.
e.g. '!', ASCII character 33, has
integer value 241, because ((33-48)mod256) is 241.
Pairs:
Pairs have a CAR (left-hand node) and a CDR (right-hand node)
as in Lisp.
PartialFunctions:
Some function applications can return a PartialFunction node,
which represents the need for more arguments before the function
can finish. PartialFunctions are special opaque values; the only
thing they are good for is applying to their next argument.
Totally Monadic:
Every function in Lithium takes exactly one operator.
Currying:
Functions that need more than one argument must curry.
The partial evaluation is represented by a PartialFunction object,
which can be stored and used later.
Syntax:
Lithium atoms are written as a single character (unless they are
not in the Printable ASCII range 32 to 127-- what then?).
Lithium pairs are written as two nodes (the CAR and the CDR)
after an open parenthesis. Since each open parenthesis is followed
by exactly two things (atoms or pairs), closing parentheses are not
needed and not used.
Examples:
3 -- an atom
B -- an atom
& -- an atom
(24 -- a pair ( think "(24)" )
((x3(y5 -- a pair of pairs ( think "((x3)(y5))" )
((+34 -- how to curry the expression meaning "3+4"
Compared to Unlambda:
If you are familiar with Unlambda, the "(" of Lithium acts
like the "apply" mark "`" in Unlambda, which is always followed
by two things. The way function application works is exactly like
in Unlambda, but the functions themselves are more like LISP.
Compared to LISP LIST syntax:
There is no special syntax for a LIST structure like in LISP,
in which the CAR holds the list elements and the CDR points to
the next pair or to NIL. You can build them in Lithium, but
the list written in LISP as "(A B C D E)" would be written in
Lithium as "(A(B(C(D(E0". Notice the atom character "0" is
conventionally used in Lithium in the role of the NIL atom of LISP.
Expression:
Any node can be evaluated as an expression.
There are several kinds of Atoms:
-- digits '0' thru '9', representing Numbers 0 thru 9
-- letters 'a' thru 'm', representing Global Variables
-- letters 'n' thru 'z', representing Local Variables
-- all others, some of which represent Builtin Functions
Numbers '0' thru '9' evaluate to themselves.
Global Variables a-m and Local Variables n-z dereference to the
value of the variable.
All other atoms evaluate to themselves (as if they were quoted).
All PartialFunctions evaluate to themselves.
Pairs are evaluated as Applications, by considering the CAR
to be the function and the CDR to be the argument.
Whether the CAR and/or the CDR are evaluated as expressions
depends on details below.
PairApplication:
Applying a function to an arguments is done by evaluating
a Pair, with the function in the CAR and the argument in
the CDR.
The unevaluated CAR determines how application proceeds:
If CAR is digit Atom, it's a NumberConditional.
If CAR is a GlobalVariable a-m, it's a GlobalAssignment.
If CAR is a LocalVariable n-z, it's a LambdaExpression.
If the CAR is some other CharacterAtom, it is a BuiltinFunction.
If CAR is a PartialFunction, it is applied to the CDR.
If CAR is a pair, use the result of PairApplication on it,
and revisit the above rules.
Suppressed CDR Evaluation:
Usually the CDR is evaluated to determine the argument to
the function. However some CARs suppress this evaluation
in some or all cases:
Quote:
The BuiltinFunction "'" returns its argument unevaluated.
LambdaExpression:
Letters n-z use the CDR unevaluated as the expression
to evaluate when the lambda expression is applied.
Increment:
The increment operator ';' does not evaluate its
argument if it is a Global or Local Variable.
In other cases it does.
Conditionals and While:
While '@' and the NumberConditionals take unevaluated
arguments.
U and V:
Some combinators defined to not evaluate certain arguments.
NumberConditional:
for any N in '0' .. '9',
and for any nodes X and Y,
((NX)Y) means "if X is a Character and is less than or equal
to N, evaluate to Y; otherwise, evaluate to X"
NOTE: NumberConditional will probably be removed, in favor
of a more typical "if" operator (((?C)T)E) meaning
"if (C) then {T} else {E}".
GlobalVariable Assignment:
for any G in 'a' .. 'm',
(GX) means evaluate X and assign the result to GlobalVariable G.
LambdaExpression:
for any V in 'n' .. 'z',
and for any nodes X and Y,
((VX)Y) means "evaluate (quoted) X with local variable V bound to
the evaluation of Y"
That is, X is not evaluated until it is applied to Y.
While it is evaluated, V will be set to the evaluation of Y.
Primitive:
(CX)
Other characters C may have builtin functions associated with them.
If no primitive is associated, it returns the evaluation of X.
That is, characters default to behaving like the the identity function I.
WARNING:
It is not yet fixed which ones are actually defined; these tend to change
as we experiment. So this section should not be considered final.
These primitives are defined:
For any nodes X, Y and Z;
('X) Quote X -- do NOT evaluate X, just return it verbatim.
((+X)Y) X + Y
(-X) - X
((*X)Y) X * Y
((&X)Y) X and Y
((|X)Y) X or Y
((@)C)B) while (C) { B }
((M)F)X) (MAPCAR X `F)
These may be wrong:
((0)X)Y) (X is a character && X==0) ? Y : X
((1)X)Y) (X is a character && X<=1) ? Y : X
((2)X)Y) (X is a character && X<=2) ? Y : X
((3)X)Y) (X is a character && X<=3) ? Y : X
((4)X)Y) (X is a character && X<=4) ? Y : X
((5)X)Y) (X is a character && X<=5) ? Y : X
((6)X)Y) (X is a character && X<=6) ? Y : X
((7)X)Y) (X is a character && X<=7) ? Y : X
((8)X)Y) (X is a character && X<=8) ? Y : X
((9)X)Y) (X is a character && X<=9) ? Y : X
This is not defined yet, but should be:
(((?)C)T)E) (C) ? T : E
Combinators:
(IX) X
((KX)Y) X
((JX)Y) Y
((VX)Y) X -- Y is *never* evaluated
((UX)Y) Y -- X is *never* evaluated
Lispy operators that might be disabled:
(AX) if X evaluates to a Pair, its CAR; else '0'
(DX) if X evaluates to a Pair, its CDR; else '0'
((CX)Y) CONS X Y
((RX)Y) CONS Y X
These might be disabled:
(((SX)Y)Z) ((XZ)(YZ))
More to doc:
Self, Answer, PutChar, PutTree
APPENDIX -- Historical Goals
This is a historical document. It's mostly still true.
It's been marked up in [square brackets] to show what's changed.
I wrote a Lisp interpreter over the weekend, called "lithium", designed
for the scenario of genetic programming, as I think it should be done.
Design Goals & Summary:
-- implemented in C++, so fast, & easy to use as a library
-- pure functional lisp-like core lang
[ not any more ]
-- can be extended with side-effect commands
(e.g. to do, or simulate, HTTP GET and HTTP POST)
-- only 'lambda' binds immutable local variables; no globals.
[ not any more -- also Global Variables now ]
-- every function takes exactly one parameter (or curries for more)
-- easy to mutate, cross genomes, randomize, etc.
-- lisp trees (programs and data) stringify and destringify efficiently
(one string character per lisp atom,
one "(" to start a cons node; ")" optional)
[ ")" is no longer allowed ]
-- API to program execution is a string in (the program), and
a string out (the result)
[ or it can use a builtin putchar function to write the result ]
-- program executions are relatively short-lived, with limits on
time and space. This also means no garbage collection -- we
just toss the entire NODE table after each "program" runs.
-- I think it's quite fast (and could be optimized more)
-- It's designed for the ROBOTS to read & understand, not so much
for humans, although (if you can remember the single-char atom codes)
it is rather "normal" lisp functions and combinators