The whole Enchilada

For the past two months I have been very fortunate to get a lot of good suggestions/remarks from Stevan Apter regarding Enchilada.

One of Stevan's suggestions was to simplify Enchilada's syntax to be more like Joy (and to steal K's list separator).

First I was reluctant to do so but after some experimentation with JavaCC I'm now convinced that the new syntax is A GOOD THING.

The new release contains a new Vanilla parser that is implemented in JavaCC - a very handy tool that can help you write parsers with not much effort (it took me 2 days).

JavaCC can generate a BNF from the parser definition file. This is what jjdoc produced:

Input ::= Expression ( <EOF> | "\n" )

Expression ::= ( Term )*

Term ::= Operator | Literal | NegLiteral

Literal ::= Number | List

NegLiteral ::= "_" Literal

Operator ::= Monadic | Dyadic

Monadic ::= "-" | "^" | "\"" | "~" | "!" | "\\" | "<" | "#"

Dyadic ::= "+" | "*" | "/" | "%" | ">" | "@" | ":" | "?" | "|"

List ::= "[" Expression ( Separator Expression )* "]"

Separator ::= ";" | "\n"

Number ::= <NUM>

Notice the separator: it can be either ";" or "\n" like in K. Here are some examples to get a feel of the new syntax:

1 2 [3 4 +; 5 6 +] ! + + +

0: 1 2 [3 4 + ; 5 6 +] ! + + +

1: 1 2 3 4 + 5 6 + + + +

2: 1 2 3 4 + 11 + + +

3: 1 2 7 11 + + +

4: 1 2 18 + +

5: 1 20 +

6: 21

Here are some newlines to seperate expressions in lists:

1 [1

2

3] 4 : !

0: 1 [1 ; 2 ; 3] 4 : !

1: 1 4 [1 ; 2 ; 3] !

2: 1 4 1 2 3

So there is no need for parenthesis anymore - only the square brackets remain. Actually, the Enchilada's syntax is now very close to Joý's syntax (except for the list seperator). But semantically, Enchilada is very different from Joy.

You can download the newest version here.

Then run the following command for the vanilla parser:

java -cp enchilada_v0_3_2.jar org.enchilada.v0_3.impl.Test2

But you can always return (but who would want that?) to the canonical parser with:

java -cp enchilada_v0_3_2.jar org.enchilada.v0_3.impl.Test

Just released a minor version: v0_3_1. This version includes:

The iterator (@) operator.

The push (>) operator.

The pop (<) operator.

The push and pop operators are convenience operators to aid the re-shuffling of three or more operands.

Note that Enchilada is still very much in development but is pretty stable in terms of its functionality. Since version 0_2, only convenience operators have been added.

What's left to do?

Syntax simplifications (alternative vanilla syntax)

More documentation / examples.

Discussion about implementation details.

Regression testing framework.

Killer application.

Here's the newest version: http://www.javaforge.com/displayDocument/enchilada_v0_3_1.jar?doc_id=20954

Then run:

java -cp enchilada_v0_3_1.jar org.enchilada.v0_3.impl.Test

Enchilada provides a novel way to loop a program N times: just multiply the list (containing the expression to be iterated) by N and de-solve it.

But what if you don't know the number of iterations in advance? I've been trying to think of a binary operator to do iteration (@) and I've come up with the following semantics:

(0 [(B)] @) => (B [(B)] @)

(A [(B)] @) => () iff (A 0 ?) = (0)

Let's see how iota can be defined with the aid of @:

(3 0 [(" _1 + " 0 ?)] @) =>

(3 " _1 + " 0 ? [(" _1 + " 0 ?)] @) ==>

(3 2 0 [(" _1 + " 0 ?)] @) ==>

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

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

(3 2 1 0)

Now the challenge is that I want to define @ in terms of the already defined operators. Then @ would just be another short-cut like duplicate (") and drop (~).

After some googling I found Manfred von Thun's paper: 'Survey of reproducing programs' http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-survrep.html .

I feel that his paper can provide the answer I'm looking for.

Enchilada now has big numbers. This means that lists and numbers can be of any size (modulo memory size).

Here are some examples to show off how Enchilada handles BIG lists without any sweat.

0: ([(1) (2) (3) (4) (5)] 89312048067982364907692631 * ~ 3489023471 %)

1: ([(1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) ... {446560240339911824538463155} ... (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5)] 446560240339911824538463155 ~ 3489023471 %)

2: ([(1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) ... {446560240339911824538463155} ... (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5)] 3489023471 %)

3: ([(1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) ... {3489023471} ... (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1) (2) (3) (4) (5) (1)] 1513214361)

But if you really want to see how fast it is you should try it out yourself.

Download the latest greatest at http://www.javaforge.com/displayDocument/enchilada_v0_3.jar?doc_id=20297

Then run: java -cp enchilada_v0_3.jar org.enchilada.impl.v0_3.Test

Great news (for me anyway): I’ve completed the reference implementation of Enchilada.

Although the implementation is an interpreter of Enchilada expressions, it is otherwise pretty efficient on all list operations. Say that you want to concatenate n lists of length n into one big list (n*n). With Enchilada you can do this in O(n*log(n)*log(n)) rather then O(n^3).

During coding it became clear that the negation semantics were the hardest to implement. Especially the mod (%) operator turned out to be very difficult to get right. I’ve also made the interpreter reduce only the top-level expression – it only does one reduction at a time.

Note however that the Enchilada ‘spec’ doesn’t say anything about reduction order or depth – so any other implementation could do it completely different.

For people that like to experiment with Enchilada, go to: http://www.javaforge.com/displayDocument/enchilada_v0_2_4.jar?doc_id=20142

Then run:

java –cp enchilada_v0_2_4.jar org.enchilada.v0_2.impl.Test

Here are some Enchilada expressions to get a taste of how different Enchilada actually is:

Cartesian product:

0: ([(1) (2) (3) (4)] - [(6) (7) (8)] * |)

1: (_[(1) (2) (3) (4)] [(6) (7) (8)] * |)

2: (_[(1) (2) (3) (4) (1) (2) (3) (4) (1) (2) (3) (4)] [(6) (6) (6) (6) (7) (7) (7) (7) (8) (8) (8) (8)] |)

3: ([(4 6) (3 6) (2 6) (1 6) (4 7) (3 7) (2 7) (1 7) (4 8) (3 8) (2 8) (1 8)])

Division:

0: ([(+) (*) () (!) (#) (:) (") (?) (!) (~)] - [(1) (2) (3) (4)] /)

1: (_[(+) (*) () (!) (#) (:) (") (?) (!) (~)] [(1) (2) (3) (4)] /)

2: (_[(+) (*) () (!) (#)] [(1) (3)])

Modulus:

0: ([(1) (2) (3) (4) (5)] [(5) (6)] - %)

1: ([(1) (2) (3) (4) (5)] _[(5) (6)] %)

2: ([(4) (5)] _[(5)])

Factorial (n+1)

0: (4 1 : [(" 1 +) (* ~)] * : ~ !)

1: (1 4 [(" 1 +) (* ~)] * : ~ !)

2: (1 8 [(" 1 +) (" 1 +) (" 1 +) (" 1 +) (* ~) (* ~) (* ~) (* ~)] : ~ !)

3: (1 [(" 1 +) (" 1 +) (" 1 +) (" 1 +) (* ~) (* ~) (* ~) (* ~)] 8 ~ !)

4: (1 [(" 1 +) (" 1 +) (" 1 +) (" 1 +) (* ~) (* ~) (* ~) (* ~)] !)

5: (1 " 1 + " 1 + " 1 + " 1 + * ~ * ~ * ~ * ~)

6: (1 1 1 + " 1 + " 1 + " 1 + * ~ * ~ * ~ * ~)

7: (1 2 " 1 + " 1 + " 1 + * ~ * ~ * ~ * ~)

8: (1 2 2 1 + " 1 + " 1 + * ~ * ~ * ~ * ~)

9: (1 2 3 " 1 + " 1 + * ~ * ~ * ~ * ~)

10: (1 2 3 3 1 + " 1 + * ~ * ~ * ~ * ~)

11: (1 2 3 4 " 1 + * ~ * ~ * ~ * ~)

12: (1 2 3 4 4 1 + * ~ * ~ * ~ * ~)

13: (1 2 3 4 5 * ~ * ~ * ~ * ~)

14: (1 2 3 20 20 ~ * ~ * ~ * ~)

15: (1 2 3 20 * ~ * ~ * ~)

16: (1 2 60 60 ~ * ~ * ~)

17: (1 2 60 * ~ * ~)

18: (1 120 120 ~ * ~)

19: (1 120 * ~)

20: (120 120 ~)

21: (120)

If the above doesn’t make sense, but you are interested in how this all works, you should read all the previous blog entries ;-). Otherwise you have to wait for the manual.