Re: [stack] a minor change to cons

John Nowak <[email protected]> wrote:
> I've commented before that the map fusion rule for Haskell:
>   map f . map g  ==  map (f . g)
> ... has no nice analog in Joy. I now think this may not be because Joy is stack-based, but rather because it's not stack-based enough!

Very interesting! I need to explore this, and ask you for practical
and demonstrative examples. You tend to get a little theoretical, so I
need to bring you down to earth so that I can implement your ideas in
my HIGHLY practical zeroone language (cue the laugh track, ha ha ha).

> Because I need to for this to work, I separate quotations ("[]"), lists ("{}"), and stacks ("()"; these are just first class stacks similar to lists but heterogeneous) into separate data types. I believe this is a good idea regardless; see previous posts.

I think you're implying that lists contain multiple elements of the
same data type, right? So a "list" contains an unknown number of
elements all of the same type, while a "stack" contains an unknown
number of elements of any data type. (In Joy, of course, the two would
be the same type.) It would be quite possible to make a runtime-typed
language (like Joy) that enforced the distinction you're hinting at.

> Currently, 'cons' and 'uncons' have the following semantics (where "'a" denotes a single element of any type and "X" denotes zero or more elements):
>      'a {X} cons  ==  {'a X}
>    {'a X} uncons  == 'a {X}
> I'm proposing a small change; the idea is that 'cons' can only add a stack to a list; it is an error to attempt to add anything else (e.g. "1 {} cons"):
>     (Y) {X} cons  ==  {(Y) X}
>   {(Y) X} uncons  ==  (Y) {X}

Iiiiinteresting. We probably shouldn't start talking about
multidimensional arrays now, and what happens when we expand this to
allow adding lists to lists (instead of only stacks to lists).

One thing that's REALLY interesting about this is that Manfred's
notation for [cons] is that he uses quotation syntax, that is [square
brackets], to indicate something that's pushed on the stack (whereas
you and I prefer a single-item quotation mark like \ or '). Amusingly,
under your proposal, Manfred's notation would remain literally valid
(i.e. you could type it into an interpreter and have it work), while
ours wouldn't.

> Because all lists now are composed of zero or more stacks, we can write a nice version of 'map' that uses the 'infra' combinator:
>   (X) [F] infra  ==  (X F)
>          infrad  ==  [infra] dip
>   map = [swap null?]
>         [drop]
>         [[uncons] dip  [infrad] keep  map cons]
>         ifte

Ok, here I have to ask for examples. I really want to know what this
looks like in a live context -- that is, with someone using the
results as part of an algorithm... But that's a lot to ask (and I
didn't ask for it with the banana notation or the 'cleave'
combinators). So let me just ask for some simple examples, because I
really don't get the depth of this change just by looking at your
definitions.

I'm glad you mention the cases where this change makes reasoning about
programs simpler, so that I could start to get enthusiastic about it
:-). I think I need a little more explanation, though. Sorry, I'm
slow.

> This version of 'map' enjoys the following property:
>   [G] map [F] map  ==  [G F] map

That's a really nice property, concatenatively speaking.

> It's also strictly more useful. For example, we can now map a function across a list that returns more than one value (such as 'dup' to give a trivial example).

Okay, I can see that... But, just for the sake of discussion, could
you please expand on this? It seems that the setup and takedown from a
map could be quite messy, since you have to 'enstack' and 'destack'
all of the items. Do you have an algorithm in mind that would be made
simpler by this approach?

> This "stack on the stack" approach can be used to clean up the semantics for the cleave and spread combinators as well. For example, if we redefine Factor's 'bi', 'bi@', and 'bi*' as such:
> This approach also eliminates the need for '2bi', '3bi', et cetera; the programmer can simply elect to push more values into the stack on top of the stack.

I really like hearing that. Numbered combinators annoy me. (The fact
that this is actually a doubly-numbered combinator just takes it to
new extremes... '2bi'???)

> - jn

-Wm