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)

Enchilada design notes

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

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

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

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

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