Home » forums » LtU Forum

The whole Enchilada

The concatenative language Enchilada only defines two types:

- Expressions that are sequences of operators and lists.
- Lists that are sequences of expressions

(operators are primitive expressions)

One interesting result is that there is no need for an additional integer type.
Another surprising result is that the Cartesian product turns out to be a very powerful operator!

I've recently started a blog to explain some of the details.

I'm pretty sure that I've hit something extra-ordinary but I leave it to Lambda the Ultimate to decide.

Feedback is much appreciated!

By Robbert van Dalen at 2006-08-26 21:15 | LtU Forum | previous forum topic | next forum topic | other blogs | 8375 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Something related?

On a cursory examination this seems related to the following work: http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-church.html.

By cdiggins at Sat, 2006-08-26 22:07 | login or register to post comments

Thanks for that

Thanks for that.

Yes, it does resemble Church numberals.

Of course, Enchilada borrows a lot from Joy and Cat ;-) but I think Enchilada is much more regular and clean then other concatenative languages (it was designed that way).

For example, Enchilada has one interesting feature: to allow the multiplication of expressions:

[(2) (4 5)] [(*) (+)] * => [(2 *) (2 +) (4 5 *) (4 5 +)] =>
[(2 *) (2 +) (45) (9)]

Implementing the map operator on top of multiplication is a no-brainer.
And while we are at it I find the map operator of Joy very irregular, plus I don't like the artificial difference between quotations and lists.
Although I love and respect Joy, I feel Enchilada solves some of its defects.

By Robbert van Dalen at Sun, 2006-08-27 05:41 | login or register to post comments

Syntax

Reading your blog your language changed a bit during those posts, and I think you don't need () around expressions anymore, just a separator inside lists. This would make your example above:

[2; 4 5] [*; +] * => [2 *; 2 +; 4 5 *; 4 5 +] => [2 *; 2 +; 45; 9]

I think this cleans things up a bit, but maybe that's just because I don't like excessive parenthesis.

Also, why don't you make lists into an operator. It sort of seems natural:

[(a) (b)] [(c) (d)] => [(a c) (a d) (b c) (b d)]

Anyway, I think cartesian products are very useful in programming, but they are rarely available in programming languages. Most list programming languages do the inner product when they distribute an operator over lists. Ie. they make [1, 2] + [10, 20] => [11, 22], but [11, 21, 12, 22] is much more useful in general programming. (If values in different lists group pairwise they shoulnd't have been in seperate lists to start with, unless you're doing vector math.)

By Sjoerd Visscher at Sun, 2006-08-27 09:55 | login or register to post comments

Two types of parenthesis

Thanks for the suggestion. I also don't like excessive parenthesis and thought about using a list separator too.
But then I would have to encode the empty expression with an additional symbol (.), then

[] == 0
[()] == 1
[() ()] == 2
Would become:
[] == 0
[.] == 1
[., .] == 2
and:
[., .] [5] * => [5, 5]

Although lesser parenthesis makes the syntax definitely more appealing, the reduction rules become littered with exceptions.
BTW: your example [1, 2] + [10, 20] can be written like this in Enchilada:

[(2) (1)] [(10) (20)] * [(+)] * => [(2 10 +) (2 20 +) (1 10 +) (1 20 +)]=>
[(12) (22) (11) (21)]

By Robbert van Dalen at Sun, 2006-08-27 13:33 | login or register to post comments

Hadn't thought of the empty

Hadn't thought of the empty expression.

Can you do the inner product as well? I think you need a zipper:

[(1) (2)] [(10) (20)] zip [(+)] * => [(1 10) (2 20)] [(+)] * => [(11) (22)]

For zip you probably need a way to split a list in a head and a tail, I'm not sure if you can do that in Enchilada.

By Sjoerd Visscher at Sun, 2006-08-27 16:37 | login or register to post comments

Concatenate

Wouldn't zip just be concatenate? Remember that + is concatenation in Enchilada:

[(1) (2)] [(10) (20)] + => [(1) (2) (10) (20)]

Just to make things a little bit more interesting:

enl == [] : +
4 enl == [4]

ita == swp [(dup 1 +)] * ! drp

3 2 ita => 2 3 [(dup 1 +)] * ! ==>
2 dup 1 + dup 1 + dup 1 + drp ==>
2 3 4

Then factorial can be written as:

fac == enl [(1 ita) ([(*)] *)] * !

3 fac => [(3 1 ita) (3 [(*)] *)] ! ==>
[(1 2 3) (* * *)] ! ==> 6

No stinking loops and no conditionals ;-)

By Robbert van Dalen at Sun, 2006-08-27 20:38 | login or register to post comments

Zip

Zip is certainly not concatenate. Note the order and where the parentheses are:

[(1) (2)] [(10) (20)] zip => [(1 10) (2 20)]

See f.e. http://www.zvon.org/other/haskell/Outputprelude/zip_f.html.

By Sjoerd Visscher at Sun, 2006-08-27 21:58 | login or register to post comments

Parenthesis blindness

That's what you get with excessive parenthesis ;-)

Yeah, I could consider to add zip as a primitive Of course, it can be build with other operators, but that would be considerably less efficient.

By Robbert van Dalen at Mon, 2006-08-28 05:21 | login or register to post comments

How to implement zip

Assuming the 2 lists are of the same length, I can imagine something like this:

a b zip = 
  a 1 ==          // if test (a list equals its size, right?)
  a b *           // then part
  a / b / zip2    // else part
  if

a1 a2 b1 b2 zip2 =
  a1 b1 zip a2 b2 zip +

Ignoring for a moment if Enchilada supports this style of function declaration, this leaves implementing if. Could you show me how to implement if with the other operators?

By Sjoerd Visscher at Mon, 2006-08-28 07:46 | login or register to post comments

If then else (ife)

You can implement if with the is-equal operator (?). For example:

if (c == d) then b else a

Would be this in Enchilada:

ife == ? [(swp)] * ! drp !
a == [(1 +)]
b == [(3 *)]
c == 2
d == 2

a b c d ife ==> a b 2 2 ? [(swp)] * ! drp ! ==>
a b 1 [(swp)] * ! drp ! ==>
a b swp drp ! ==>
b a drp ! ==>
b ! ==> 3 *

and for c == 1 and d == 2

a b c d ife ==> a b 1 2 ? [(swp)] * ! drp ! ==>
a b 0 [(swp)] * ! drp ! ==>
a b drp ! ==>
a ! ==> 1 +

So multiplying 1 with [(expr)] will give you [(expr)]. Multiplying 0 with [(expr)] gives you [].
You can manipulate expressions conditionally with the aid of ? and *.

By Robbert van Dalen at Mon, 2006-08-28 09:11 | login or register to post comments