The whole Enchilada

Let's make programming as simple as possible, but not too simple

Enchilada is a programming language that stands on the shoulders of Lisp, APL and Forth:

- The minimalistic approach and parenthesis were taken from Lisp.
- The arrays and mathematical purity from APL.
- And the postfix notation and typelessness was stolen from Forth.

Enchilada is not meant as a mainstream programming language but to spur some new thoughts on computer language design (and may be number theory).
Nonetheless, Enchilada is targeted to solve real world problems that are related to security, distributed systems and scaleability.

Expressions

We start off with the most important (and the least user-friendly) feature of Enchilada:

Enchilada expressions are written in postfix notation

This choice is made on purpose: with postfix notation we can manipulate expressions in ways that are incompatible with infix notation.
A few examples will point out those differences:

infix:

1 + 2 + 3 => 3 + 3 => 6  
2 * 4 + 5 => 8 + 5 => 13

postfix:

3 2 1 + + => 3 3 + => 6 
5 4 2 + * => 8 5 + => 13

infix functions:

f(a,b,c) == a + b + c
g(d,e) == d * e
h == g(f(a,b,c),e) == (a + b + c) * e

postfix ‘functions’:

f == + +
g == *
h == f g == + + *

As the slogan goes, Enchilada tries to make programming as simple as possible. In that respect, we can conclude that postfix is the clear winner.
Compared to infix, there is no need for complex constructs such as variable bindings or function application.

Theoretically speaking, the concatenation of postfix expressions is isomorphic to the composition of anonymous functions. Moreover, because of the absence of variables and functions, we can manipulate curried expressions just as easily.

There are two kinds of expressions that can be identified: dyadic expressions that need two operands to reduce, and monadic expressions that only need one.
By concatenating dyadic expressions to single operands, we get a monadic expressions in return. The other way around, turning a monadic into a dyadic expression, can also be done:

dyadic expressions (atomic):

+
*

monadic expressions (curried):

2 +
2 * 4 +

Now that we are free to mix operands, operators and curried expressions, we are ready to advance to the next Enchilada type: the list. But before we do that, let us consolidate on expressions first:

- Expressions are sequences of operators and operands.
- Operators are atomic expressions.
- Expressions can be reduced into other expressions via operators.
- Operators cannot reduce other operators, only operands.

Additionally, we want to syntactically distinguish one expression from another, plus the constraint that they do not nest:

- Expressions are synthetically enclosed by parentheses.
- Parenthesis are not allowed to nest.

legal expressions:

()
(1 2 +) => (3)
(5 6 + 5 *) => (11 5 *) => (55)
(+ 1 2 * *) => (+ 2 *)

illegal expressions:

(2 3 * (2))
(3 () +)
()(3)

But what if we still want to able to nest expressions? Following the previous definitions, we cannot come to another conclusion then to nest expressions in operands.

Lists

Lists are defined as containers for expressions, synthetically enclosed by square brackets. Lists can contain an unlimited amount of expressions, or they can be empty: they solely exist to be the operands for operators.

Combined with earlier definitions, the whole Enchilada framework can now be succinctly phrased in six statements:

- Lists are sequences of expressions (enclosed by brackets)
- Expressions are sequences of lists and operators (enclosed by parenthesis)
- Lists are manipulated by operators
- Operators are atomic expressions
- Expressions are written in postfix notation
- Expressions can be reduced into other expressions via operators.

Alternatively, lists can be interpreted as (fixed) computational spaces wherein multiple expressions can be reduced simultaneously. Moreover, the final state doesn't depend on the order of reductions whatsoever.

Lists enable the possibility of distributed computing because its contained expressions can be independendly reduced without opposing any ordering.

out of order:

[(1 2 +) (3 4 +)] => [(3) (3 4 +)] => [(3) (7)]
[(1 2 +) (3 4 +)] => [(1 2 +) (7)] => [(3) (7)]

simultaneously:

[(1 2 +) (3 4 *) (5 6 +)] => [(3) (12) (11)] 
[(2 3 + 4) (4 5 + +)] => [(5 + 4)(9 + +)]

De-solving

What if we were to combine all list expressions into one single expression? With the aid of the powerful de-solve operator (!) we can just do that. To see how de-solving works we go through it in two steps:

- First remove the round parenthesis for each expression in the target list.
- Then remove the square brackets around the target list.

simple:

([(1) (2)] !) => (1 2)
([(1 2) (+)] !) => (1 2 +) => (3)
(1 [(2)] ! +) => ( 1 2 +) => (3)

complex:

([([(2)])] !) => ([(2)])
([([(2)]) (!)] !) => ([(2)] !) => (2)

in any order:

((1 2 +) (3 4 +)] !) => (1 2 + 3 4 +) => (3 3 4 +) => (3 7)
([(1 2 +) (3 4 +)] !) => ([(3) (3 4 +)] !) => (3 3 4 +) => (3 7)

Note how expressions and lists recursively alternate at each level. This recursion reveals another purpose of (!) in that it can reduce the level of recursion by two.

Following the examples, de-solving may look like parenthesis voodoo coming from Mars. But if we were to follow the pre-defined steps, there is nothing difficult about it.

Lucky numbers

Until now we have been using numbers in various examples. But we haven't specified where they come from and how they are exactly constructed. The challenge is that we have to build them out of lists and expressions alone!
Luckily, this challenge can be easily met: we can use the empty expression () to encode all natural numbers in base 1:

0 == []
1 == [()]
2 == [() ()]
3 == [() () ()]
4 == [() () () ()]
5 == [() () () () ()]
....

(commutative) addition:

(0 2 +) == ([] [() ()] +) => ([() ()]) == (2)
(2 0 +) == ([() ()] [] +) => ([() ()]) == (2)
(1 2 +) == ([()] [() ()] +) => ([() () ()]) == (3)
(2 1 +) == ([() ()] [()] +) => ([() () ()]) == (3)

(commutative) multiplication:

(0 2 *) == ([] [() ()]) => ([]) == (0)
(2 0 *) == ([() ()] []) => ([]) == (0)
(2 1 *) == ([() ()] [()] *) => ([() ()]) == (2)
(1 2 *) == ([()] [() ()] *) => ([(() ()]) == (2)

Strictly speaking, the (+) operator doesn't do addition but rather concatenation. Similarly, multiplication also looks a bit off. Nevertheless, both (+) and (*) possess the necessary commutative property to correctly implement the rules of arithmetics.

But what happens if we extend the empty expressions with not-empty expressions? Does multiplication and concatenation still work in that case? Magically so, it does:

([(1) (2)] [(3) (4)] +) => ([(1) (2) (3) (4)])
([(1) (2)] [(3) (4)] *) => ([(1 3) (2 3) (1 4) (2 4)])
[4 [(3)] *) => [(3) (3) (3) (3)]
([(3 4) (5)] [(*)] *) => ([(3 4 *) (5 *)]) => ([(12) (5 *)])

The previous examples show that Enchilada defines multiplication as the Cartesian product of two lists: each new expression is the concatenation of two expressions taken from the first- and second list.

Three more operators

To turn Enchilada into full-blown programming language, we need something more then just addition, multiplication or de-solving.

What's lacking for instance, is the possibility to make runtime decisions. The enlist operation (inverse to !) is also missing from our repertoire, together with the swap operator that allows the re-ordering of operands.

Let's start with the is-equal operator (?) to implement decision semantics. This operator reduces two operands into 1 if they are equal, or 0 if they are not:

(1 2 ?) => 0
(2 2 ?) => 1
([(1)] [(1 +)] ?) => 0
([(1 2 +)] [(3)] ?) => 1

Swap and enlist are merged into a single swap-and-enlist operator (:). One reason for this is that they are often used in conjuction, for instance, to pack two operands into one. Another reason is to keep the number of operators to an absolute minimum:

(1 2 :) => (2 [(1)])
(1 2 : !) => (2 [1] !) => (2 1)
(2 [] : +) => ([] [2] +) => ([2]) 
(1 2 : : +) => (2 [(1)] : +) => ([(1)][(2)] +) => ([(1) (2)])
(2 3 : * !) => (3 [(2)] * !) => ([(2) (2) (2)] !) => (2 2 2)

Two operators down, one last operator to go!

The cut (\) operator inverts the concatenation of two identical lists. It can also interpreted as division by two, thus providing a generic division operator (because there is no such thing as a Cartesian division):

([(1) (2)] \) => ([(1)] [(2)])
(4 4 + \) => (8 \) => (4 4)
(4 3 + \) => (7 \) => (4 3)
(3 4 + \) => (7 \) => (4 3)

Re-usable expressions

Programmers don't like to write the same program twice, so let's define some re-usable expressions:
(swp) == (: !) -- swap
(drp) == ([] *) -- drop
(els) == ([] : +) -- enlist
(dup) == (els 2 * !) -- duplicate

An interesting re-usable expression is the is-a-number expression, reducing to 1 if the operand is a number (and otherwise 0)

(isa) == (els [(!)] * 1 ?) -- is-a-number
Are we confident enough to define the factorial function in the Enchilada way?

(a b fac) =:= (a 1 + a b *)
Then factorial(3) is:


1 1 [(fac)] 3 * ! => 1 1 fac fac fac => 6
We'll leave the definition of fac to the next post ;-)