functional

Functional languages rely on first-class functions, anonymous functions and immutability.

A programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements.

Fizzbuzz, in Heol Lisp.

(define print-ln
	(lambda (s)
		(and (print s) (print '\n))))

(define fizzbuzz
	(lambda (n f b)
		(if (< n 101)
			(if (and (eq? f 3) (eq? b 5))
				(and (print-ln 'FizzBuzz) (fizzbuzz (+ n 1) 1 1))
				(if (eq? f 3)
					(and (print-ln 'Fizz) (fizzbuzz (+ n 1) 1 (+ b 1)))
					(if (eq? b 5)
						(and (print-ln 'Buzz) (fizzbuzz (+ n 1) (+ f 1) 1))
						(and (print-ln n) (fizzbuzz (+ n 1) (+ f 1) (+ b 1))))))
			())))

(fizzbuzz 1 1 1)

Fizzbuzz, in LISP 1.5.

(LETREC main
	(main λ (INPUT)
		(loop (QUOTE 1) (QUOTE 100)))
	(loop λ (x y v)
		(IF (LEQ x y)
			(loop (+ x (QUOTE 1)) y (fizzbuzz x))
			(QUOTE Completed)))
	(fizzbuzz λ (n)
		(IF (EQ (% n (QUOTE 15)) (QUOTE 0))
			(WRITE (QUOTE FizzBuzz))
			(IF (EQ (% n (QUOTE 3)) (QUOTE 0))
				(WRITE (QUOTE Fizz))
				(IF (EQ (% n (QUOTE 5)) (QUOTE 0))
					(WRITE (QUOTE Buzz))
					(WRITE n))))))

An abstract machine intended as a target for functional programming language compilers.

The SECD is a stack-based runtime with a core of 10 opcodes defined with a set of transitions between its four components. Functions take their arguments from the stack. The arguments to built-in instructions are encoded immediately after them in the instruction stream. If C and D are both empty, overall evaluation has completed with the result on S.

Stack S register points to a list of intermediate results.
Environment E register points to the current environment.
Control C register points a location in the program.
Dump D register points to a list of triples. Each triple contains snapshots of the stack, environment, and control registers.

The .secd representation of a program encodes the various parts of a functional programming language into the abstract machine code, where each opcode is represented as a number. For example, if we compile the Pure Lisp program below:

Pure Lisp: (LAMBDA (X) (ADD (QUOTE 1) X))
SECD(opcodes): ( 3 ( 2 1 1 ( 0 . 0 ) 15 5 ) 4 21 )
SECD(mnemonics): ( LDF ( LDC 1 LD ( 0 . X ) ADD RTN ) AP BRK )

Basic Instructions
0	NIL	Creates an empty list on the top of the stack register.
0	NIL	A nil is compiled to ( NIL ).
1	LD	Pushes the value of a variable onto the stack. The variable is indicated by the argument, a pair.
1	LD	An identifier is compiled to ( LD ( i . j ) ). where ( i . j ) is an index the jth element of the ith sublist in the Environment stack.
2	LDC	Loads a constant on the stack.
2	LDC	A number, or a constant, x is compiled to ( LDC x ).

Here are a few compilation examples:

(QUOTE A) ; (LDC A AP STOP)
(LAMBDA (X) X) ; (LDF (LD (0.0) RTN) AP STOP)

Stack Instructions
3	LDF	Takes one list argument representing a function. It constructs a closure (a pair containing the function and the current environment) and pushes that onto the stack.
4	AP	Pops a closure and a list of parameter values from the stack. The closure is applied to the parameters by installing its environment as the current one, pushing the parameter list in front of that, clearing the stack, and setting C to the closure's function pointer. The previous values of S, E, and the next value of C are saved on the dump.
5	RTN	Pops one return value from the stack, restores S, E, and C from the dump, and pushes the return value onto the now-current stack.

((lambda (x y) (+ x y)) 2 3) ; (NIL LDC 3 CONS LDC 2 CONS LDF (LD (1.2) LD (1.1) + RTN) AP)

Recursive function instructions
7	RAP	Works like a p ap, only that it replaces an occurrence of a dummy environment with the current one, thus making recursive functions possible
6	DUM	Pushes a "dummy", an empty list, in front of the environment list.
Branching instructions
8	SEL	Expects two list arguments, and pops a value from the stack. The first list is executed if the popped value was non-nil, the second list otherwise. Before one of these list pointers is made the new C, a pointer to the instruction following s e l sel is saved on the dump.
9	JOIN	Pops a list reference from the dump and makes this the new value of C. This instruction occurs at the end of both alternatives of a sel.

(if (atom 5) 9 7) ; (LDC 5 ATOM SEL (LDC 9 JOIN) (LDC 7 JOIN))
(lambda (x y) (+ x y)) ; (LDF (LD (1.2) LD (1.1) + RTN))

Builtin Extensions
10	CAR(HEAD)	Returns a pair's first value.
11	CDR(TAIL)	Returns a pair's second value.
12	ATOM	Returns T if its value is atomic.
13	CONS	Returns a value pair consisting of two expressions.
Builtin Arithmetic
14	EQ	Returns T if two expressions are equal.
15	ADD	Returns the sum of two numeric values.
16	SUB	Returns the difference of two numeric values.
17	MUL	Returns the product of two numeric values.
18	DIV	Returns the quotient of two numeric values.
19	REM	Returns the remainder of two numeric values.
20	LEQ	Returns T if the first value is less or equal to the second.
Lispkit Extensions
21	STOP	End execution.
25	READ	Assign expression to a device event.
26	WRITE	Sends expression to a device.
27	IMPLODE	Transform a list into a symbol.
28	EXPLODE	Transform a symbol into a list of numbers which are the ASCII code for each character.

The compilation notation for builtins is reverse polish notation. To perform an operation is to pop up the front element(s) from s, perform the operation, and put the result back to s.

(ADD (QUOTE 123) (QUOTE 456)) ; ( LDC 123 LDC 456 ADD AP STOP )
(MUL (ADD (QUOTE 12) (QUOTE 34)) (QUOTE 56)) ; ( LDC 12 LDC 34 ADD LDC 56 MUL AP STOP )

Summary

Like all internal data-structures, the stack is a list, with the S register pointing at the list's head. Due to the list structure, the stack need not be a continuous block of memory, so stack space is available as long as there is a single free memory cell. Even when all cells have been used, garbage collection may yield additional free memory.

The current variable environment is managed by the E register, which points at a list of lists. Each individual list represents one environment level: the parameters of the current function are in the head of the list, variables that are free in the current function, but bound by a surrounding function, are in other elements of E.

The C register points at the head of the instruction list that will be evaluated. Once the instruction there has been executed, the pointer is pointed at the next instruction in the list. It is similar to an instruction pointer (or program counter) in conventional machines, except that subsequent instructions are always specified during execution and are not by default contained in subsequent memory locations, as is the case with the conventional machines.

The D register, at whose head the register points, is used as temporary storage for values of the other registers, for example during function calls. It can be likened to the return stack of other machines.

Pure Lisp, SECD virtual machine in ANSI C.

A common trait of all dialects of Lisp is the S-expression.

In Lisp, a pair of parentheses indicates one step of calculation in which the operation is written with the prefix notation.

Programs in Lisp are made of symbols that are nested into trees using cons cells. A number is a signed integer represented by a sequence of decimal digits, optionally preceded by a sign.

45
+137
-27

A symbol is word represented by a sequence of characters, it cannot begin with a number or a sign, although these may appear later in a symbol.

Hello
Hello-world
x32

A cons cell is an allocation of memory made of two parts, a value(car) and a pointer(cdr), the cdr can point to another cell.

(123)
(hello 45)
(foo (bar baz))

A Lisp through the Looking Glass

Gödel's bag, Gödel's bag,
Gödel's bag.

Bägel is a programming language where data is encoded as multisets(unordered bags of things) and compose by multiplication. Think Fractran, without the rule-searching of rewriting, or a strange Lisp in which cons cells are unordered lists.

In this mirror world, order does not matter, only presence and reduction.

Basics

Parentheses denotes an unordered bag of things, which may contain items, fractions or other bags. An item is either a non-numeric symbol assigned an unused prime number or a whole number. The order of things inside a bag does not matter. The caret notation is a shorthand that the represents the number of instances of an item in a bag.

; This is a comment

()            ; Empty(1), identity
(x^3)         ; -> (x x x)
(2 (y))	      ; -> (2 y)
(3 (2 5/2) 7) ; -> (3 5 7)

Evaluation consists of applying fractions on whole numbers, locally until exhaustion, starting at the deepest nesting level outward until the bag stabilizes.

(3/2 2)	      ; -> 3
(5/3 2 3 3)   ; -> (5/3 2 3 3) -> (5/3 2 3 5) -> (2 5 5)
(1/5 (5/7 7)) ; -> (1/5 5) -> ()

If a bag contains multiple fractions, the fractions are composed before application.

(2/3 2/5 3 5) ; -> (4/15 3 5) -> (2 2)
(1/5 1/7 5)   ; -> (1/35 5) -> 5

A fraction is applied if the bag in which it is being applied includes the denominator. If a fraction inside a bag cannot be applied, it is discarded during the reduction. A fractions does not fall through to the outer bag if application fails.

((3/4 2) 2) ; -> (2 2)
(1/4 3)	    ; -> 3

A fraction may also output other fractions or other bags.

(2/3/5 3 5)   ; -> (2/3 3) -> 2
((5/3 3)/7 7) ; -> (5/3 3) -> 5
(3/2/2/2 2^4) ; -> (3/2/2 2^3) -> (3/2 2^2) -> 6

Logic

Bägel can handle negation, or the lack of something, but it requires an explicit token to ground the computation. For example here is a NOT logic gate, notice the a resource.

(false/a (true/(x a) x a))
(false/a true)
true

(false/a (true/(x a) a))
(false/a a)
false

Building on this idea, we can make a OR gate.

(false/a (true/(x a) (true/(y a) (true/(x y a) x a))))
(false/a (true/(x a) (true/(y a) x a)))
(false/a (true/(x a) x a))
(false/a true)
true

(false/a (true/(x a) (true/(y a) (true/(x y a) a))))
(false/a (true/(x a) (true/(y a) a)))
(false/a (true/(x a) a))
(false/a a)
false

Notice how the AND gate doesn't need to the a symbol to check for the abscence of things.

(false/x (false/y (true/(x y) x y)))
(false/x (false/y true))
(false/x true)
true

(false/x (false/y (true/(x y) y)))
(false/x (false/y y))
(false/x false)
false

Arithmetic

The fraction y/x drains x into y, effectively finding the sum by resource transfer.

(y/x x^3 y^2) ; 3 + 2
(y/x x^2 y^3)
(y/x x y^4)
(y/x y^5)
y^5

The fraction 1/(x y) finds the difference between two symbols, but the program must handle positive and negative results:

(neg/y (pos/x (1/(x y) x^4 y^2))) ; 4 - 2
(neg/y (pos/x (1/(x y) x^3 y)))
(neg/y (pos/x (1/(x y) x^2)))
(neg/y (pos/x x^2))               ; drain x into pos
(neg/y (pos/x x pos))
(neg/y (pos/x pos^2))
(neg/y pos^2)
pos^2

(neg/y (pos/x (1/(x y) x^2 y^4))) ; 2 - 4
(neg/y (pos/x (1/(x y) x y^3)))
(neg/y (pos/x (1/(x y) y^2)))
(neg/y (pos/x y^2))               ; drain y into neg
(neg/y y^2)
(neg/y y neg)
(neg/y neg^2)
neg^2

Complex Fractions

Specific items can be injected inside fractions during recursion to create a mechanism similar to function arguments. In the following example, during replacement, the fraction will pull the items %f and %b from the location where the fraction is applied, and put them inside where they are needed.

((fizz/f^3 
	(buzz/b^5 
		(fizzbuzz/(f^3 b^5) %f %b))) f b)/i

while(i--) {
	f++, b++;
	if(f >= 3 && b >= 5)
		fizzbuzz++, f -= 3, b -= 5;
	else if(f >= 3) 
		fizz++, f -= 3;
	else if(b >= 5) 
		buzz++, b -= 5;
}

Implementation and details will be added soon, I wrote all this, as if in a fever, on the night of Halloween and expanded on it over the winter.

Multiset Languages: Rejoice, Fractran.

incoming: concatenative