# Enchilada design notes

## r_v_dalen — 2006-10-25 16:08:33

    This post discusses the choices I've made while designing the

    concatenative language Enchilada. That will hopefully explain why

    I've diverged from Joy.

    To make the discussion more enjoyable for concatenative list-members,

    I've rephased Enchilada's terminology to match Joy's wherever

    possible.

    DESIGN CONTEXT

    Enchilada's basic design evolved out of one theme:

    How far can we get with just concatenative semantics?

    Important research conducted by Manfred von Thun has given us the

    surprising result that, next to lists, programs can have

    concatenative properties too. This is expressed in Manfred's language

    Joy, wherein lists and programs are fused into quotations.

    But Joy also provides primitives such as booleans, integers, etc

    which do not posses the concatenative property. Enchilada's first

    challenge was to come up with a number system that is concatenative.

    UNARY NUMBERS

    The simplest number system of all number systems, the unary system,

    turned out to be the only candidate.

    We can simulate unary numbers by choosing an arbitrary symbol (say

    dot) as the tally symbol. Let's see how this would look like in Joy:

    [] == 0

    [.] == 1

    [..] == 2

    [...] == 3

    [..] [..] concat => [.]

    [..] [concat] concat => [..concat]

    [..concat] i => ..concat

    Notices that opening a quotation leaves dots on the stack, so that

    leaves us with the choice for the type of the tally-dot. Here are two

    obvious choices:

    1) The tally-dot is a list.

    2) The tally-dot is an operator.

    If we replace the tally-dot with the empty list we get the following:

    [] == 0

    [[]] == 1

    [[][]] == 2

    [[][][]] == 3

    0 i =>

    1 i => 0

    2 i => 0 0

    3 i => 0 0 0

    .

    Substituting the tally-dot with a no-operation gives another

    interesting option:

    [] == 0

    [nop] == 1

    [nop nop] == 2

    [nop nop nop] == 3

    .

    0 i =>

    1 i => nop =>

    2 i => nop nop => nop =>

    3 i => nop nop nop => nop nop => nop =>

    Other lists and operator combinations can be thought of, but for now

    we'll leave it to that.

    QUOTATIONS:

    Now lets take a closer look at Joys's quotations: what are they

    exactly?

    1) programs?

    2) lists?

    3) .or quotations, distinct from programs and lists?

    But if they were programs, we are not allowed to reduce them.

    Consider the following Joy program:

    [0] [1] [[2] [3] +] head + => [0] [1] [[2] [3]] + + => [0] [1 [2]

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

    Reducing quotations however, would get us:

    [0] [1] [[2] [3] +] head + => [0] [1] [[2 3]] head + + => [0] [1] [2

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

    ...giving a different unwanted result. So the top-level program is

    the only level where Joy can perform program reductions without being

    inconsistent.

    QUOTATIONS REDEFINED:

    If we redefine a quotation as *list* of Joy programs (instead of a

    list of atoms) we can get rid of the reduction level and order

    restriction. With this new definition, the previous examples work out

    like this:

    [0] [1] [[2] [3] concat] head concat => [0] [1] [2] [3] concat concat

    => [0] [1] [2 3] concat => [0] [1 2 3]

    or

    [0] [1] [[2] [3] concat] head concat => [0] [1] [[2 3]] hd concat =>

    [0] [1] [2 3] concat => [0] [1 2 3]

    Both reduction orders give the same result. Here some other examples

    (using ; as separator and + for concat)

    [1 2 +; 3 4 +] head => [3; 3 4 +] head => [3] 3 4 + => [3] 7

    [1 2 +; 3 4 +] head => [1 2 +; 7] head => [1 2 +] 7 => [3] 7

    [1 2 +; 3 4 +] head => [1 2 +] 3 4 + => [3] 3 4 + => [3] 7

    Again, any order will do. So every Joy program can be reduced at any

    (nested) level, independently and concurrently with other reductions.

    So what does new quotation definition give us?

    - Joy programs.

    - and lists that have Joy programs as elements.

    NEGATIVE NUMBERS

    Interestingly, the new quotation definition gives us also a third

    choice for our tally-symbol: the empty program (denoted by an empty

    space):

    . == 0

    [ ] == 1

    [ ; ] == 2

    [ ; ; ] == 3

    Note that,, because the zero or the empty list cannot be syntactially

    expressed given the new definitiin, I'll lazily define it as dot (.).

    Now what about signed numbers? For this we can steal the old APL

    notation for negative sign: we prefix every number and list with _

    _[ ; ; ] == _3

    _[ ; ] == _2

    _[ ] == _1

    . == 0

    [ ] == 1

    [ ; ] == 2

    [ ; ; ] == 3

    The concatenation of negative and positive numbers is easily

    explained:

    _5 2 + == _[ ; ; ; ; ] [ ; ] => _[ ; ; ] == _3

    2 _5 + == [ ; ] _[ ; ; ; ; ] => _[ ; ; ] == _3

    But if we replace the empty programs with Joy programs, the

    catenation of signed lists can be forced to 'behave' like the

    addition of annotated-one-dimensional 'vectors'. As a side-effect,

    lists that have negative sign are in reverse order:

    _[1;2;3;4;5] [6;7] => _[1;2;3]

    5;4;3;2;1

    <--------

    6;7

    --->         +

        <----

        3;2;1

    [1;2] _[3;4;5;6;7] => _[5;6;7]

          1;2

          -->

    7;6;5;4;3

    <--------  +

    7;6;5

    <----

    CONCLUSION

    By changing the definition of quotations (slightly?) we gain more

    consistency and flexibility (and flatness?). Moreover, as in the case

    with unmodified Joy, there is no difference between lists, quotations

    and programs.

    When we interpreted lists as unary numbers, we can further drop

    special types such as booleans and integers. Both approaches leaves

    us with only two concepts: catenable lists and catenable programs.

    or rephrased in Enchilada terms: lists and expressions.

    - Robbert

## William Tanksley, Jr — 2006-10-25 20:02:36

    r_v_dalen <r_v_dalen@...> wrote:

     > But if we replace the empty programs with Joy programs, the

    > catenation of signed lists can be forced to 'behave' like the

    > addition of annotated-one-dimensional 'vectors'. As a side-effect,

    > lists that have negative sign are in reverse order:

     Are the elements of such lists also reversed -- that is, would one

    take the inverse of each given program to determine its negation?

    -Billy

## Robbert van Dalen — 2006-10-26 06:13:44

    > > lists that have negative sign are in reverse

    > order:

    >

    > Are the elements of such lists also reversed -- that

    > is, would one

    > take the inverse of each given program to determine

    > its negation?

     Negative sign operates only on the surface of a list.

    In Enchilada speak:

    [1 2 +;3 4 +] - 1 + =>

    _[1 2 +; 3 4 +] 1 + =>

    _[1 2+] => _[3]

    de-solve:

    _[1;2;3;4] ! => 4 3 2 1

    _1 ^ _2 ^ + - ! => [_1] _2 ^ + - ! =>

    [_1] [_2] + - ! => [_1;_2] - ! => _[_1;_2] !=>

    _2 _1

    maximum:

    [1;2] _[3;4] | => [1 4; 2 3]

    So when you index a negative list you get the elements

    in reverse order.

    All Enchilada's operators can work on negative signed

    lists.

    The most difficult operator to get right was the mod

    (%) operator.

    Most languages get the modulus operator all wrong for

    negative values, so I've done my best to implement it

    correctly.

    I feel the 'vector' notation helps to understand how

    the concatenation

    of signed lists work. Did it help for you, or should I

    look for another vehicle to explain Enchilada's

    semantics?

    - Robbert

    __________________________________________________

    Do You Yahoo!?

    Tired of spam?  Yahoo! Mail has the best spam protection around

    http://mail.yahoo.com

## William Tanksley, Jr — 2006-10-31 17:23:31

    Robbert van Dalen <r_v_dalen@...> wrote:

     > I feel the 'vector' notation helps to understand how

    > the concatenation

    > of signed lists work. Did it help for you, or should I

    > look for another vehicle to explain Enchilada's

    > semantics?

     I believe it helps (I'll have to test myself by trying to make sense

    of your future postings; I'm reading your blog, of course).

    Your recent post about dual expressions in a list is interesting. I'd

    like to hear more about your motivations. I don't understand your

    example for what the new max operator does -- the example was just too

    complex, and the notation is unfamiliar.

    The first idea I had as a result was that list negation, in addition

    to reversing the order, could also reverse the direction of the

    mapping. It seems a natural change... But I'm not sure about the math

    of it. Perhaps the two should be kept separate: negation is list

    reversal, and reciprocal is map reversal. Again, I'm not sure about

    the math involved; I think a good idea would be to try to preserve

    some of the properties of numbers :-).

    I just read a facinating article on the properties of multisets that

    seems to me to be appropriate for Enchilada. Check out

    http://web.maths.unsw.edu.au/~norman/papers.htm (see the paper titled

    "A new look at multisets").

     > - Robbert

     -Billy

## Robbert van Dalen — 2006-10-31 19:11:43

    > I believe it helps (I'll have to test myself by

    > trying to make sense

    > of your future postings; I'm reading your blog, of

    > course).

     Feel free to comment (harshly if needed). If things

    don't make sense I should push harder or alter the

    notation, so that it *does* make sense. Anyway,

    Enchilada's syntax still needs a *lot* of work. But I

    get a lot of help from Stevan Apter and Sjoerd

    Visscher to improve on that.

     > Your recent post about dual expressions in a list is

    > interesting. I'd

    > like to hear more about your motivations.

     I like your terminology - dual expressions in a list.

    Can I copy that?

    My motivations, as always, aren't computer language

    related. What I'm after is scalable distributed data

    structures.

    Just to make you curious: dual lists can be used to

    implement an efficient diff algorithm. Just image that

    you can take a diff between two tera-byte documents

    (or databases) in O(log(a)+log(b))!

    See http://lambda-the-ultimate.org/node/953 for more

    motivations ;)

     > I don't

    > understand your

    > example for what the new max operator does -- the

    > example was just too

    > complex, and the notation is unfamiliar.

     Yes I know, I'm struggling with the notational part.

    And my weak educational powers aren't helping either.

     >

    > The first idea I had as a result was that list

    > negation, in addition

    > to reversing the order, could also reverse the

    > direction of the

    > mapping. It seems a natural change... But I'm not

    > sure about the math

    > of it.

     Your instincts are perfect. Sjoerd Visscher has

    suggested this also. And he also suggested a much more

    elegant syntax for dual lists.

     > Perhaps the two should be kept separate:

    > negation is list

    > reversal, and reciprocal is map reversal. Again, I'm

    > not sure about

    > the math involved; I think a good idea would be to

    > try to preserve

    > some of the properties of numbers :-).

     I'm also pondering on keeping the seperation between

    negation and turning. Or to merge turning into

    negation - I still have to decide.

    In any case, the number properties are left untouched.

    I certainly wouldn't want to break that in favor of

    dual lists.

     > I just read a facinating article on the properties

    > of multisets that

    > seems to me to be appropriate for Enchilada. Check

    > out

    > http://web.maths.unsw.edu.au/~norman/papers.htm (see

    > the paper titled

    > "A new look at multisets")

     .

    At a first glance I saw a lot of similarities, even in

    syntax!

    Thanks for pointing me to this.

    Take care,

    Robbert.

    ____________________________________________________________________________________

    We have the perfect Group for you. Check out the handy changes to Yahoo! Groups

    (http://groups.yahoo.com)