Lithium Language

				Henry Strickland
				<strick> in the domain <yak.net>

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