Concatenative macros?
Robbert van Dalen — 2006-12-21 19:53:54
The newest version (0.5) of the Enchilada language has macros onboard.
This is mainly thanks to Stevan. He pushed me to include Billy's
shuffle operator!
Exactly because of macros, I could drop the typical stack operators
such as duplicate, swap (and drop!).
Enchilada macros come in two flavours: eager and lazy.
Here is an example of a lazy macro that swaps two lists:
{a b=b a}
[1;2] [3;4] {a b=b a}
[1;2] {a=[3;4] a}
[3;4] [1;2]
Here is an example of a eager macro that compiles into an interesting
(but otherwise useless) other macro:
{a b c==[c] b * [a;1;] * & [c] + +}
8 5 {a b c==[c] b * [a;1;] * & [c] + +}
8 {a b==[5] b * [a;1;] * & [5] + +}
{a==[5;5;5;5;5;5;5;5;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;a;1;;5]}
Lazy macros are denoted with one equals(=) symbol while eager macros
have two equals(=) symbols.
Here are some other examples:
{a=[a]} (enlist)
{a} (drop)
(a=a a} (duplicate)
Although macros are very powerful I consider them to be more Lispy
then Joyish.
I wonder what the concatenative list think of macros?
If you are interested, my blog (
http://my.opera.com/rapido/blog/) has
the links to the lastest Enchilada documentation and implementation.
- Robbert
William Tanksley, Jr — 2006-12-21 22:34:02
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> The newest version (0.5) of the Enchilada language has macros onboard.
> This is mainly thanks to Stevan. He pushed me to include Billy's
> shuffle operator!
> Exactly because of macros, I could drop the typical stack operators
> such as duplicate, swap (and drop!).
That's something I like. Remembering the names of some of those is
frankly a pain.
> Enchilada macros come in two flavours: eager and lazy.
I don't know if I understand what that means.
> Although macros are very powerful I consider them to be more Lispy
> then Joyish.
Shuffle notation is entirely concatenative. It looks like your macros
are more like Lisp lambdas, not shuffle notation.
> I wonder what the concatenative list think of macros?
Nothing wrong with using a lambda when it helps. Just remember that
while you're doing it, you're not concatenative anymore.
I kind of like the idea of making lambdas (macros with functions
inside them) look different from shuffle notation. Shuffles can be
considered nothing more than a different way to name stack operators;
lambdas are not so simple.
But I understand the argument against this too: that macros are a
single simple concept, and users won't want to split that into two
parts, one that's "concatenatively pure" and one that's actually
useful ;-).
Your language; your call.
> - Robbert
-Billy
Robbert van Dalen — 2006-12-22 09:52:49
> > Enchilada macros come in two flavours: eager and lazy.
>
> I don't know if I understand what that means.
Here is another example:
1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)
1 2 {a b=[a] [b] [3] + +}
1 {a=[a] [2] [3] + +}
[1] [2] [3] + +
[1] [2;3] +
[1;2;3]
1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)
1 2 3 {a b c==[a;b;c]}
1 2 {a b==[a;b;3]}
1 {a==[a;2;3]}
[1;2;3]
> > Although macros are very powerful I consider them to be more Lispy
> > then Joyish.
>
> Shuffle notation is entirely concatenative. It looks like your macros
> are more like Lisp lambdas, not shuffle notation.
Is that because shuffle notation is considered to be a word?, so:
xyz-zyx
is considered to be uncuttable? Then with the same reasoning I claim a
macro also to be an uncuttable word :)
> > I wonder what the concatenative list think of macros?
>
> Nothing wrong with using a lambda when it helps. Just remember that
> while you're doing it, you're not concatenative anymore.
OK. I guess I have to let it go then - macros are just to good to be left out!
>
> I kind of like the idea of making lambdas (macros with functions
> inside them) look different from shuffle notation. Shuffles can be
> considered nothing more than a different way to name stack operators;
> lambdas are not so simple.
>
> But I understand the argument against this too: that macros are a
> single simple concept, and users won't want to split that into two
> parts, one that's "concatenatively pure" and one that's actually
> useful ;-).
>
> Your language; your call.
I guess with macros, Enchilada will eventually end up to be some kind
of postfix lisp :)
> -Billy
[Robbert]
William Tanksley, Jr — 2006-12-26 06:41:06
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> > > Enchilada macros come in two flavours: eager and lazy.
> > I don't know if I understand what that means.
> Here is another example:
> 1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)
> 1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)
In other words, lazy expansion is a normal inline lambda; eager
expansion is like a Lisp macro. Right?
> > > Although macros are very powerful I consider them to be more Lispy
> > > then Joyish.
> > Shuffle notation is entirely concatenative. It looks like your macros
> > are more like Lisp lambdas, not shuffle notation.
> Is that because shuffle notation is considered to be a word?, so:
> xyz-zyx
> is considered to be uncuttable? Then with the same reasoning I claim a
> macro also to be an uncuttable word :)
No, not because it's "considered" to be uncuttable (although it must
be considered uncuttable in order to be considered a word, of course),
but because it's form is easily lexable and its semantics are atomic.
Neither criterion applies to macro notation.
Macros come close to being lexable -- anything between { and } is
obviously a macro, assuming macros are not nestable. This still makes
knowing when you're splitting a lexeme difficult; in a flat grammar
the only thing you need to know is that if you find a space, you can
always split the word. If there are macros, you have to know about
spaces AND about {}.
Macros are definitely not atomic in semantics -- they can contain
calls to any word, so they can do anything.
> > > I wonder what the concatenative list think of macros?
> > Nothing wrong with using a lambda when it helps. Just remember that
> > while you're doing it, you're not concatenative anymore.
> OK. I guess I have to let it go then - macros are just to good to be left out!
I disagree; I think they're a positive danger. But that's because my
goals are different from yours. I don't think that they're "good" as
such; I think they're convenient, but there's a risk that people
learning the language will use them instead of learning the language
on its own terms.
For that reason, I would split them into two parts: one non-optional
part that does shuffling and nothing else (and is extremely easy to
language-analyze), and another part that handles full variable
substitution. Full variable substitution is undeniably useful, of
course.
But your language is not even close in purpose to mine. I accept your
design decisions :-).
> I guess with macros, Enchilada will eventually end up to be some kind
> of postfix lisp :)
You know, there have been a lot of reimplementations of Lisp. I hope
it sounds like a positive statement when I say that Enchilada doesn't
seem at all like a mere reimplementation of Lisp.
> [Robbert]
-Billy
Robbert van Dalen — 2006-12-27 11:47:19
> > Here is another example:
>
> > 1 2 3 {a b c=[a] [b] [c] + +} (lazy expansion)
> > 1 2 3 {a b c==[a] [b] [c] + +} (eager expansion)
>
> In other words, lazy expansion is a normal inline lambda; eager
> expansion is like a Lisp macro. Right?
Yes, more or less. But alas, the problem with eager expansion is that
we get all the hairy lambda stuff, such as alpha-conversion, etc. In
the lazy case everything is much, much easier.
> Macros come close to being lexable -- anything between { and } is
> obviously a macro, assuming macros are not nestable. This still makes
> knowing when you're splitting a lexeme difficult; in a flat grammar
> the only thing you need to know is that if you find a space, you can
> always split the word. If there are macros, you have to know about
> spaces AND about {}.
Macros may nest in Enchilada, just like lists.
> Macros are definitely not atomic in semantics -- they can contain
> calls to any word, so they can do anything.
Yes you are right. Shuffle words are atomic as opposed to macros.
> > OK. I guess I have to let it go then - macros are just to good to be left
> out!
>
> I disagree; I think they're a positive danger. But that's because my
> goals are different from yours. I don't think that they're "good" as
> such; I think they're convenient, but there's a risk that people
> learning the language will use them instead of learning the language
> on its own terms.
I guess I know what your goal is: to build a flat concatenative
language that's cuttable anywhere..... A fine goal indeed!.....
But I'm not so much concerned with Enchilada not being fully
concatenative but rather with Enchilada being immutable and useable
(while still being scalable).
Anyway, the shuffle notation you helped invent has led me to introduce
the macro construct. So you are partly to blame :-)
> > I guess with macros, Enchilada will eventually end up to be some kind
> > of postfix lisp :)
>
> You know, there have been a lot of reimplementations of Lisp. I hope
> it sounds like a positive statement when I say that Enchilada doesn't
> seem at all like a mere reimplementation of Lisp.
Enchilada is a little bit different from Lisp, yes ;). But the dark
(applicative) side is calling me.... :-)
> -Billy
Robbert
William Tanksley, Jr — 2006-12-27 17:03:36
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> > In other words, lazy expansion is a normal inline lambda; eager
> > expansion is like a Lisp macro. Right?
> Yes, more or less. But alas, the problem with eager expansion is that
> we get all the hairy lambda stuff, such as alpha-conversion, etc. In
> the lazy case everything is much, much easier.
I had to look alpha-conversion up :-). Now I remember. I would have
expected alpha conversion to appear even in the lazy case... Certainly
if you allow nested macros.
> > Macros come close to being lexable -- anything between { and } is
> > obviously a macro, assuming macros are not nestable. This still makes
> > knowing when you're splitting a lexeme difficult; in a flat grammar
> > the only thing you need to know is that if you find a space, you can
> > always split the word. If there are macros, you have to know about
> > spaces AND about {}.
> Macros may nest in Enchilada, just like lists.
Makes sense.
> > Macros are definitely not atomic in semantics -- they can contain
> > calls to any word, so they can do anything.
> Yes you are right. Shuffle words are atomic as opposed to macros.
> > > OK. I guess I have to let it go then - macros are just to good to be left
> > > out!
> > I disagree; I think they're a positive danger. But that's because my
> > goals are different from yours. I don't think that they're "good" as
> > such; I think they're convenient, but there's a risk that people
> > learning the language will use them instead of learning the language
> > on its own terms.
> I guess I know what your goal is: to build a flat concatenative
> language that's cuttable anywhere..... A fine goal indeed!.....
Grin.. That's not so much my primary goal as it is a curiosity of
mine. I'd love see such a thing, but it would surprise me if it were
useful, and I'm pretty big on usefulness (in spite of appearances!).
I'm really focussed on exploring concatenativity. Flatness appears to
be an interesting and useful adjunct; we haven't explained precisely
how it fits in, but it's definitely convenient and practical to have
some amount of flatness.
> But I'm not so much concerned with Enchilada not being fully
> concatenative but rather with Enchilada being immutable and useable
> (while still being scalable).
Yes, indeed. Fine goals; not at cross-purposes with mine at all, but
clearly we have different priorities. I definitely like what you're
doing, though. Fun.
> Anyway, the shuffle notation you helped invent has led me to introduce
> the macro construct. So you are partly to blame :-)
The story of my shame will outlive me. :-)
> > > I guess with macros, Enchilada will eventually end up to be some kind
> > > of postfix lisp :)
> > You know, there have been a lot of reimplementations of Lisp. I hope
> > it sounds like a positive statement when I say that Enchilada doesn't
> > seem at all like a mere reimplementation of Lisp.
> Enchilada is a little bit different from Lisp, yes ;). But the dark
> (applicative) side is calling me.... :-)
If once you start down the dark path, forever will it dominate your
destiny, consume you it will, as it did PL/1.
It's tempting to assume that the familiar (applicative notation with
named parameters) is easier and (in your word) "usable". We all know
it's not always true, but it's quick and convenient to assume that in
this case it might be.
Your job isn't to find out whether or not this is one of the cases
where the familiar solution is the best one. That's my job :-).
> Robbert
-Billy
Manfred Von Thun — 2007-01-02 09:08:04
I liked the original ideas and the discussions on this topic. Just a few
brief comments:
What you called ³eager² and ³lazy² macros seems to correspond pretty well to
³#define² macros in the C preprocessor and ordinary function definitions in
C. Am I right here? Clearly most languages could use a macro processor, and
in many it would be very useful. You might also call them ³compile-time² and
³run-time² operators (or something like that). I believe some languages even
have ³link-time² and ³load-time² macros, but these distinctions only make
sense in more complex systems. So, I would advise you to continue with the
two, but you do need some really convincingly useful examples of the eager
macros.
About the pattern matching operators, written in the ³before-and-after²
style, where (a b b a) implements swap, for example. I seem to remember a
few years back some discussion on how to extend this to handle list
manipulation. The pattern (a [b c D] -- b a [c a D] b [D]) would match a
stack whose top element is a list of at least two items, b and c, and which
also has a second element a. This operator would remove these two items from
the stack and then push the five items on the right of the ³--², which are:
b, the first element of the list, then a, the original second element,
then a list whose first two elements are c and a then the rest D of the
list, then b again, and finally, on top, the list which is just the rest D
of the list. Not a very useful example (contrary to my own advice), but
you get the idea. It would help if someone could remember when this
discussion occurred.
It looks a bit like Prolog, doesn¹t it? In fact all the stack-shufflers and
all list operators can be implemented in a Joy-in-Prolog using this style.
Sticking to the ³before/after² style, here are some familiar ones:
cons == (a [B] -- [a B])
uncons == ([a B] -- a [B])
first == ([a B] -- a)
rest == ([a B] -- [B])
Note that in the two examples all variables occurring to the right of
the ²--² were already bound on the left of the ³--². That need not be
so, but then we need some extra machinery. I will only give one
example. Suppose I have a list of at least 3 items on top of the stack,
and that third item is a number, and I wish to square it. In Joy I
would write
squarethird == uncons uncons unswons dup * swons cons cons
In a pattern matching Prolog-like Joy I would write
squarethird([x y z R] -- [x y w R])
w = z dup *
So the extra ³machinery² is precisely what in Prolog is the body of
a relation.
I cannot remember how far we went in our discussion some years back.
I have resisted the pattern matching mechanism for Joy mainly for
reasons of purity. But I am also aware how some of the pattern matching
languages allow very succinct code.
I hope what I wrote is of some use to the language smiths on this group.
- Manfred
[Non-text portions of this message have been removed]
Chris Double — 2007-01-02 13:02:08
On 1/2/07, Manfred Von Thun <
m.vonthun@...> wrote:
> The pattern (a [b c D] -- b a [c a D] b [D]) would match a
> stack whose top element is a list of at least two items, b and c, and which
> also has a second element a.
That's pretty nifty. I wrote some pattern matching routines for Factor
a while back and for fun implented a 'shuffle' word that used it to do
stack manipulation. I wrote about it here:
http://www.bluishcoder.co.nz/2006/12/factor-pattern-matching-additions.html
or if the URL wraps and doesn't work:
http://wee-url.com/NBE12
As an example, 2dup looks like: { ?a ?b } { ?a ?b ?a ?b } shuffle
Where ?a and ?b are pattern matching variables. I didn't think about
it at the time but implementing cons,etc works fine too:
: mycons { ?a { ?b } } { { ?a ?b } } shuffle ;
1 { 2 } mycons
=> { 1 2 }
I like the idea of being able to do calculations to insert in the
result - 'shuffle' unfortunately doesn't allow that.
Since writing the pattern matching stuff I use it a lot. Not for stack
shuffling though - it was just me playing around with the idea.
Although it could get addictive!
By the way, wee-url.com I linked above is implemented in Factor,
written by Doug Coleman, one of the keen Factor users.
Chris.
--
http://www.bluishcoder.co.nz
Christopher Diggins — 2007-01-04 17:07:36
It is perhaps interesting to mention the equivalence of stack shuffling
notation and lambda expressions (other languages) which was identified by
Brent Kerby
http://tunes.org/~iepos/joy.html
In other words a pattern such as:
[c] [b] [a] -> [[c] b] [c] a
Would be expressed in the lambda calculus as:
\abc.ac(bc)
Which rewritten with () around the arguments to a function looks like:
\abc.a(c)(b(c))
Notice this is simply the stack pattern written backwards. .
I am planning on creating a separate language for expressing stack
operations as shuffle operations. It is intended to operate on concatenative
languages without itself being concatenative. This would be basically an
implementation of the concatenative algebra. The tool would be useful for
optimizing and manipulating concatenative code. A similar approach is used
in the GHC haskell compiler.
I am also interested in a Joy program for automatically generating Joy
programs from lambda expressions. Does anyone have such a beast? The
algorithm is provided on Brent Kerby's page (
http://tunes.org/~iepos/joy.html ) I simply haven't yet had time to
implement it yet. Chris double's Factor program does it, but apparently
relies on a bit of Factor specific items to achieve the result.
Christopher Diggins
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-01-04 18:52:16
Christopher Diggins <
cdiggins@...> wrote:
> It is perhaps interesting to mention the equivalence of stack shuffling
> notation and lambda expressions (other languages) which was identified by
> Brent Kerby http://tunes.org/~iepos/joy.html
Yes, although there's nothing interesting about the fact that those
are equivalent to lambdas -- they are, prima facia, lambdas, since
they create a function that takes arguments which are expressed as
named parameters and returns a function of those parameters.
There are some minor things to notice about this notation.
First, it's not immediately obvious that it's not a mere stack
shuffle; it can also enlist and execute its parameters.
Second, it is never used in Kerby's paper to delist, because that
would require the language to officially know what is inside lists. In
other words, the pattern on the left-hand-side must NEVER contain
complex quoted expressions, just lists containing a single variable
each.
Third, it's more powerful than Kerby wants it to be. It's (allegedly)
possible to write expressions in it, called in his paper
"pseudo-combinators", that cannot be simplified so that their result
contains only quotations and input variables.
> In other words a pattern such as:
> [c] [b] [a] -> [[c] b] [c] a
> Would be expressed in the lambda calculus as:
> \abc.ac(bc)
> Which rewritten with () around the arguments to a function looks like:
> \abc.a(c)(b(c))
> Notice this is simply the stack pattern written backwards. .
It took me AGES to recognize this, and when I finally did, I saw it
was there in his paper all along.
It gets much harder with lambda expressions which include combinators.
I still haven't found an expression for any of the X combinators.
> I am planning on creating a separate language for expressing stack
> operations as shuffle operations. It is intended to operate on concatenative
> languages without itself being concatenative. This would be basically an
> implementation of the concatenative algebra. The tool would be useful for
> optimizing and manipulating concatenative code. A similar approach is used
> in the GHC haskell compiler.
That's an excellent idea. You might want to think about how much power
you want to put into that language, and for what purposes. Kerby's
notation, as I've mentioned, has more power than he wanted to use; my
notation for stack shuffles has deliberately too little power because
it can neither execute its parameters nor enlist them.
I wonder if a stack shuffle language which could execute, but not
enlist, its parameters would be "just right"? The power to execute
implies the power to enlist, after all, since you can always pass [[]
cons] to the shuffle. Such a language might be expressed as something
like:
{abc--abCc} =>
[a][b][c] == [a] [b] c [c]
I still wouldn't include such a pattern language in my ideal language,
but I certainly recognize that languages with other purposes would.
The lack of list operators implies that the notation is not
_primarily_ designed to manipulate lists, although it's possible to
make it do so; it's designed to rearrange the stack, execute
parameters, and allow the preservation of parameters.
I haven't bothered implementing one of the X combinators in this
notation (I only just invented the notation :-).
More later, if I remember. (I've been doing a lot of work on the X
combinator stuff.)
> Christopher Diggins
-Billy
Robbert van Dalen — 2007-01-05 09:55:50
>
> What you called ³eager² and ³lazy² macros seems to correspond
> pretty well to
> ³#define² macros in the C preprocessor and ordinary function
> definitions in
> C. Am I right here?
No, I would say they are more dynamic and very close to Lisp macros.
> So, I would advise you to continue with the
> two, but you do need some really convincingly useful examples of
> the eager
> macros.
Eager macros are very useful to efficiently generate or compile code.
Let's say you want to repeat an item with a constant.
Here is the lazy version:
3 5 {a b=[a] b * &}
3 {a=[a] 5 * &}
[3] 5 * &
[3;3;3;3;3] 5 &
[3;3;3;3;3]
Here is the eager version:
3 5 {a b==[a] b * |}
3 {a==[a;a;a;a;a]}
[3;3;3;3;3]
Now we could reuse the eager macro to multiply items in a list with a
constant:
[1;2;3;4] [3 {a b==[a] b * |}] ! * | !
[1;2;3;4] [{a==[a;a;a]}] * | !
[1;2;3;4] [{a==[a;a;a]};{a==[a;a;a]};{a==[a;a;a]};{a==[a;a;a]}] | !
[1 {a==[a;a;a]};2 {a==[a;a;a]};3 {a==[a;a;a]};4 {a==[a;a;a]}] !
[[1;1;1];[2;2;2];[3;3;3];[4;4;4]]
the lazy case would be less efficient:
[1;2;3;4] [3 {a b=[a] b * |}] ! * | ! ! !
[1;2;3;4] [{a=[a] 3 * |}] * | ! ! !
[1;2;3;4] [{a=[a] 3 * |};{a=[a] 3 * |};{a=[a] 3 * |};{a=[a] 3 * |}]
| ! ! !
[1 {a=[a] 3 * |};2 {a=[a] 3 * |};3 {a=[a] 3 * |};4 {a=[a] 3 * |}] ! ! !
[[1] 3 * |;[2] 3 * |;[3] 3 * |;[4] 3 * |] ! !
[[1;1;1] 3 |;[2;2;2] 3 |;[3;3;3] 3 |;[4;4;4] 3 |] !
[[1;1;1];[2;2;2];[3;3;3];[4;4;4]]
>
> About the pattern matching operators, written in the ³before-and-
> after²
> style, where (a b ‹ b a) implements swap, for example. I seem to
> remember a
> few years back some discussion on how to extend this to handle list
> manipulation.
I remember Stevan Apter has put some similar constructs in his XY
language.
>
> It looks a bit like Prolog, doesn¹t it? In fact all the stack-
> shufflers and
> all list operators can be implemented in a Joy-in-Prolog using this
> style.
> Sticking to the ³before/after² style, here are some familiar ones:
>
> cons == (a [B] -- [a B])
> uncons == ([a B] -- a [B])
> first == ([a B] -- a)
> rest == ([a B] -- [B])
Wasn't it you that implemented Joy in Prolog in the first place? :)
> I cannot remember how far we went in our discussion some years back.
> I have resisted the pattern matching mechanism for Joy mainly for
> reasons of purity. But I am also aware how some of the pattern
> matching
> languages allow very succinct code.
I think (Prolog) pattern matching has more power than Enchilada macros.
Enchilada macros are just lambdas (just variable substitution).
>
> I hope what I wrote is of some use to the language smiths on this
> group.
You certainly made me consider to include pattern matching in
Enchilada, so yes!
>
> - Manfred
Robbert.
stevan apter — 2007-01-05 15:02:54
i've implemented several versions of this, in XY, and then again in F
and G (http://www.nsl.com/k/f/f.htm)
in F/G:
A pattern is a list whose head is a scheme and whose tail is a template
A scheme is a name or a list of schemes. The case of the first letter
in a name is significant. If lower-case, the name matches a single element.
If upper-case, the name must occur as the final element in a list of schemes,
and will match zero or more elements, viz. the remainder of the list whose
initial elements are matched by schemes preceding the terminal name.
A template is a list. If s is a symbol in the template which also occurs in
the scheme, the value matched by s is substituted for s in the template.
in G, ` is the pattern operator. it takes a pattern, performs substitutions
from the stack below it, and replaces the pattern and the elements consumed
from the stack with the result.
G also supports the more limited case of shuffles. e.g. swap is the shuffle-
symbol ab-ba.
the G prelude defines some common words:
http://www/k/f/g/prelude.g
e.g. where ! is eval, dip is:
[[a b][b!a]]`!
in XY (http://www.nsl.com/k/xy/xy.htm) the result of pattern-evaluation
is placed on the queue, so evaluation happens automatically.
in F, four operators are defined which apply the pattern to either
the stack or the queue, and place the result on either the stack or
the queue. on reflection, i thought this might be overkill, so G
was defined to contain just the one pattern operator ` : stack->stack.
i still believe that a single notation which treats stack-shuffling
and list-construction/deconstruction in the same way is desirable,
but as billy points out, patterns and macros do much more than that.
although i haven't worked out the details, i think an extended form of
shuffle-symbol would be just adequate. e.g.
[aB]-ab uncons
ab-[aB] cons
[aA]-a car
[aA]-A cdr
this is more powerful than the notation billy described, but less
powerful than either XY patterns or enchilada macros.
----- Original Message -----
From: "Manfred Von Thun" <m.vonthun@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, January 02, 2007 4:08 AM
Subject: Re: [stack] Concatenative macros?
I liked the original ideas and the discussions on this topic. Just a few
brief comments:
What you called ³eager² and ³lazy² macros seems to correspond pretty well to
³#define² macros in the C preprocessor and ordinary function definitions in
C. Am I right here? Clearly most languages could use a macro processor, and
in many it would be very useful. You might also call them ³compile-time² and
³run-time² operators (or something like that). I believe some languages even
have ³link-time² and ³load-time² macros, but these distinctions only make
sense in more complex systems. So, I would advise you to continue with the
two, but you do need some really convincingly useful examples of the eager
macros.
About the pattern matching operators, written in the ³before-and-after²
style, where (a b < b a) implements swap, for example. I seem to remember a
few years back some discussion on how to extend this to handle list
manipulation. The pattern (a [b c D] -- b a [c a D] b [D]) would match a
stack whose top element is a list of at least two items, b and c, and which
also has a second element a. This operator would remove these two items from
the stack and then push the five items on the right of the ³--², which are:
b, the first element of the list, then a, the original second element,
then a list whose first two elements are c and a then the rest D of the
list, then b again, and finally, on top, the list which is just the rest D
of the list. Not a very useful example (contrary to my own advice), but
you get the idea. It would help if someone could remember when this
discussion occurred.
It looks a bit like Prolog, doesn¹t it? In fact all the stack-shufflers and
all list operators can be implemented in a Joy-in-Prolog using this style.
Sticking to the ³before/after² style, here are some familiar ones:
cons == (a [B] -- [a B])
uncons == ([a B] -- a [B])
first == ([a B] -- a)
rest == ([a B] -- [B])
Note that in the two examples all variables occurring to the right of
the ²--² were already bound on the left of the ³--². That need not be
so, but then we need some extra machinery. I will only give one
example. Suppose I have a list of at least 3 items on top of the stack,
and that third item is a number, and I wish to square it. In Joy I
would write
squarethird == uncons uncons unswons dup * swons cons cons
In a pattern matching Prolog-like Joy I would write
squarethird([x y z R] -- [x y w R])
w = z dup *
So the extra ³machinery² is precisely what in Prolog is the body of
a relation.
I cannot remember how far we went in our discussion some years back.
I have resisted the pattern matching mechanism for Joy mainly for
reasons of purity. But I am also aware how some of the pattern matching
languages allow very succinct code.
I hope what I wrote is of some use to the language smiths on this group.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-01-05 16:16:14
stevan apter <
sa@...> wrote:
> i still believe that a single notation which treats stack-shuffling
> and list-construction/deconstruction in the same way is desirable,
> but as billy points out, patterns and macros do much more than that.
> although i haven't worked out the details, i think an extended form of
> shuffle-symbol would be just adequate. e.g.
> [aB]-ab uncons
> ab-[aB] cons
> [aA]-a car
> [aA]-A cdr
I think you're probably right. I just did some work with the shuffle
notation I proposed in my last post, which provided for stack shuffle
and execution but not any support for lists. I didn't like the results
at all.
If you want a shuffle notation to be able to express all possible
combinators, you have to support lists, execution, and shuffling. I
don't see any way around that.
I would propose a slight modification of your system, though. Your
system doesn't allow for execution, and it has a little bit of
redundancy, since the last letter in a list is ALWAYS the tail of the
list, and therefore always has to be a list itself (unless you're
going to support Lisp's "improper lists"; I'll assume in my notation
that this isn't desired).
Here's an alternate form:
[ab]-ab uncons
ab-[ab] cons
[ab]-a car
[ab]-b cdr
This frees us up to use upper case to mean something else; I choose to
make it mean execution.
ab-A k combinator
a-A i
abc-[cB]cA s combinator
I'm not entirely satisfied with this. Consider the last combinator --
the s combinator might also be written as
abc-[[C]B][C]A s combinator
I'm just not entirely happy with the equivalence between lower case
and quoted upper case. I suppose the problem is inherent in our choice
to equate quotation and enlistment. On the other hand, this notation
does offer a nice shorthand; my first definition of the s combinator
is pleasantly short.
It's also worth noting that your notation (and this notation) has both
the ability to take apart input lists, AND manages to make it obvious
when lists are being taken apart.
There's a little problem. I can't figure out how to define Fokker's X
combinator. (The following work uses Kerby's notation.)
X = \f fS(\xyz x) =
\f f(S)(\xyz x) =
\f [\xyz x] [s] f =
[\xyz x] [s] rot i
Okay, now I'll use my shuffle notation...
[abc-A] [abc-[cB]cA] abc-bcA
The problem now is that I don't see how I can consolidate this into a
single shuffle, which cues me that something's wrong.
A doubt begins to stir in my mind. Is the Fokker X combinator actually
a pseudo-combinator? If so, is that a problem with the Fokker X
combinator, or is it a problem with Kerby's ideas about
pseudo-combinators? If not, have I simply overlooked the solution, or
is my shuffle notation a bit too weak?
> this is more powerful than the notation billy described, but less
> powerful than either XY patterns or enchilada macros.
Definitely so.
-Billy
stevan apter — 2007-01-05 20:20:40
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, January 05, 2007 11:16 AM
Subject: Re: [stack] Concatenative macros?
> stevan apter <sa@...> wrote:
> > i still believe that a single notation which treats stack-shuffling
> > and list-construction/deconstruction in the same way is desirable,
> > but as billy points out, patterns and macros do much more than that.
> > although i haven't worked out the details, i think an extended form of
> > shuffle-symbol would be just adequate. e.g.
>
> > [aB]-ab uncons
> > ab-[aB] cons
> > [aA]-a car
> > [aA]-A cdr
>
> I think you're probably right. I just did some work with the shuffle
> notation I proposed in my last post, which provided for stack shuffle
> and execution but not any support for lists. I didn't like the results
> at all.
>
> If you want a shuffle notation to be able to express all possible
> combinators, you have to support lists, execution, and shuffling. I
> don't see any way around that.
>
> I would propose a slight modification of your system, though. Your
> system doesn't allow for execution, and it has a little bit of
> redundancy, since the last letter in a list is ALWAYS the tail of the
> list, and therefore always has to be a list itself (unless you're
> going to support Lisp's "improper lists"; I'll assume in my notation
> that this isn't desired).
well, in my notation, [aB] and [ab] are different. [aB] matches
any list which contains at least one element. then a is the first
of that list and B is the rest. but [ab] only matches those lists
which contain exactly two elements.
i don't know what an "improper list" is, so i probably wasn't
intending to support them. :-)
>
> Here's an alternate form:
>
> [ab]-ab uncons
then you can't decompose a pair into its parts.
> ab-[ab] cons
or compose two things into a pair.
> [ab]-a car
> [ab]-b cdr
etc.
what am i missing?
btw, i've lost the reference for the X combinator you've been
discussing.
>
> This frees us up to use upper case to mean something else; I choose to
> make it mean execution.
>
> ab-A k combinator
> a-A i
> abc-[cB]cA s combinator
>
> I'm not entirely satisfied with this. Consider the last combinator --
> the s combinator might also be written as
>
> abc-[[C]B][C]A s combinator
>
> I'm just not entirely happy with the equivalence between lower case
> and quoted upper case. I suppose the problem is inherent in our choice
> to equate quotation and enlistment. On the other hand, this notation
> does offer a nice shorthand; my first definition of the s combinator
> is pleasantly short.
>
> It's also worth noting that your notation (and this notation) has both
> the ability to take apart input lists, AND manages to make it obvious
> when lists are being taken apart.
>
> There's a little problem. I can't figure out how to define Fokker's X
> combinator. (The following work uses Kerby's notation.)
>
> X = \f fS(\xyz x) =
> \f f(S)(\xyz x) =
> \f [\xyz x] [s] f =
> [\xyz x] [s] rot i
>
> Okay, now I'll use my shuffle notation...
>
> [abc-A] [abc-[cB]cA] abc-bcA
>
> The problem now is that I don't see how I can consolidate this into a
> single shuffle, which cues me that something's wrong.
>
> A doubt begins to stir in my mind. Is the Fokker X combinator actually
> a pseudo-combinator? If so, is that a problem with the Fokker X
> combinator, or is it a problem with Kerby's ideas about
> pseudo-combinators? If not, have I simply overlooked the solution, or
> is my shuffle notation a bit too weak?
>
> > this is more powerful than the notation billy described, but less
> > powerful than either XY patterns or enchilada macros.
>
> Definitely so.
>
> -Billy
>
John Cowan — 2007-01-05 20:52:16
stevan apter scripsit:
> i don't know what an "improper list" is, so i probably wasn't
> intending to support them. :-)
An improper list is one whose final cons does not have a car of nil.
--
He played King Lear as though John Cowan <
cowan@...>
someone had played the ace.
http://www.ccil.org/~cowan
--Eugene Field
stevan apter — 2007-01-05 22:25:12
----- Original Message -----
From: "John Cowan" <cowan@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, January 05, 2007 3:52 PM
Subject: Re: [stack] Concatenative macros?
> stevan apter scripsit:
>
> > i don't know what an "improper list" is, so i probably wasn't
> > intending to support them. :-)
>
> An improper list is one whose final cons does not have a car of nil.
you know, i've just never really internalized lisp lists. for
me, a list is just a sequence. everytime i have to understand
something like this i have to forget what i know. (never mind
that i've implemented lisp lists several times -- they're just
not intuitive (to me).)
>
> --
> He played King Lear as though John Cowan <cowan@...>
> someone had played the ace. http://www.ccil.org/~cowan
> --Eugene Field
>
William Tanksley, Jr — 2007-01-06 06:58:20
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > stevan apter <sa@...> wrote:
> > > i still believe that a single notation which treats stack-shuffling
> > > and list-construction/deconstruction in the same way is desirable,
> > > but as billy points out, patterns and macros do much more than that.
> > > although i haven't worked out the details, i think an extended form of
> > > shuffle-symbol would be just adequate. e.g.
> > I think you're probably right. I just did some work with the shuffle
> > notation I proposed in my last post, which provided for stack shuffle
> > and execution but not any support for lists. I didn't like the results
> > at all.
> > If you want a shuffle notation to be able to express all possible
> > combinators, you have to support lists, execution, and shuffling. I
> > don't see any way around that.
> > I would propose a slight modification of your system, though. Your
> > system doesn't allow for execution, and it has a little bit of
> > redundancy, since the last letter in a list is ALWAYS the tail of the
> > list, and therefore always has to be a list itself (unless you're
> > going to support Lisp's "improper lists"; I'll assume in my notation
> > that this isn't desired).
> well, in my notation, [aB] and [ab] are different. [aB] matches
> any list which contains at least one element. then a is the first
> of that list and B is the rest. but [ab] only matches those lists
> which contain exactly two elements.
My system tries not to specify the shape of lists -- I consider it a
bad habit. Even being able to take apart lists is mathematically
problematic within a system that allows execution (notice that Kerby's
notation never tries). The problem is that if you specify the shape of
a list, you've got a problem if someone passes to you a list that's
got the wrong shape, and your code doesn't explain what to do with
that problem.
> i don't know what an "improper list" is, so i probably wasn't
> intending to support them. :-)
It's a list whose cdr points to an object rather than another list --
in other words, a pair, since both the car and cdr are objects. But I
don't think they're worth supporting for our general purposes.
> > Here's an alternate form:
> > [ab]-ab uncons
> then you can't decompose a pair into its parts.
That's what uncons does, unless you meant a "pair" as in an improper
list -- but if so, that's only one special case, so there's no reason
why we couldn't support it, aside from not wanting to. (We still can't
create improper lists.)
> > ab-[ab] cons
> or compose two things into a pair.
Again, how is this not composing two things into a pair?
> > [ab]-a car
> > [ab]-b cdr
> etc.
> what am i missing?
I don't know -- am I missing something?
> btw, i've lost the reference for the X combinator you've been
> discussing.
After reading
http://ling.ucsd.edu/~barker/Iota/zot.html, I noticed a
reference to "Rosser" and "Fokker". Citeseer showed me
http://citeseer.ist.psu.edu/fokker97systematic.html, which lists quite
a few others (note that Iota, Jot, and Zot all use a different one).
I'm really working hard trying to figure out what the X combinator
DOES to a stack...
-Billy
stevan apter — 2007-01-06 12:10:32
between you and john, i now understand the point about "improper
lists".
i think the two notations can be made equivalent by adding a special
symbol to each.
mine yours
---- -----
pair-to-parts: [ab]-ab [ab.]-ab for you, . means nil
parts-to-pair: ab-[ab] ab-[ab.]
k-combinator: ab-a. ab-A for me, . means execute
for me, . can only occur on the right side of a shuffle. for you,
. can only occur on the left side.
on second thought, maybe you don't need the extra symbol. isn't
[ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
isn't the natural way for me think about these things.) if this
is the case, then i think i favor your notation.
on the question of list-deconstruction and "bad input", it seems
that you and robbert are in agreement. i'd like to better understand
the practical implications of this devil's bargain (freedom-from-
exceptions for reduced expressiveness.)
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, January 06, 2007 1:58 AM
Subject: Re: [stack] Concatenative macros?
> stevan apter <sa@...> wrote:
> > From: "William Tanksley, Jr" <wtanksleyjr@...>
> > > stevan apter <sa@...> wrote:
> > > > i still believe that a single notation which treats stack-shuffling
> > > > and list-construction/deconstruction in the same way is desirable,
> > > > but as billy points out, patterns and macros do much more than that.
> > > > although i haven't worked out the details, i think an extended form of
> > > > shuffle-symbol would be just adequate. e.g.
>
> > > I think you're probably right. I just did some work with the shuffle
> > > notation I proposed in my last post, which provided for stack shuffle
> > > and execution but not any support for lists. I didn't like the results
> > > at all.
>
> > > If you want a shuffle notation to be able to express all possible
> > > combinators, you have to support lists, execution, and shuffling. I
> > > don't see any way around that.
>
> > > I would propose a slight modification of your system, though. Your
> > > system doesn't allow for execution, and it has a little bit of
> > > redundancy, since the last letter in a list is ALWAYS the tail of the
> > > list, and therefore always has to be a list itself (unless you're
> > > going to support Lisp's "improper lists"; I'll assume in my notation
> > > that this isn't desired).
>
> > well, in my notation, [aB] and [ab] are different. [aB] matches
> > any list which contains at least one element. then a is the first
> > of that list and B is the rest. but [ab] only matches those lists
> > which contain exactly two elements.
>
> My system tries not to specify the shape of lists -- I consider it a
> bad habit. Even being able to take apart lists is mathematically
> problematic within a system that allows execution (notice that Kerby's
> notation never tries). The problem is that if you specify the shape of
> a list, you've got a problem if someone passes to you a list that's
> got the wrong shape, and your code doesn't explain what to do with
> that problem.
>
> > i don't know what an "improper list" is, so i probably wasn't
> > intending to support them. :-)
>
> It's a list whose cdr points to an object rather than another list --
> in other words, a pair, since both the car and cdr are objects. But I
> don't think they're worth supporting for our general purposes.
>
> > > Here's an alternate form:
> > > [ab]-ab uncons
> > then you can't decompose a pair into its parts.
>
> That's what uncons does, unless you meant a "pair" as in an improper
> list -- but if so, that's only one special case, so there's no reason
> why we couldn't support it, aside from not wanting to. (We still can't
> create improper lists.)
>
> > > ab-[ab] cons
> > or compose two things into a pair.
>
> Again, how is this not composing two things into a pair?
>
> > > [ab]-a car
> > > [ab]-b cdr
>
> > etc.
> > what am i missing?
>
> I don't know -- am I missing something?
>
> > btw, i've lost the reference for the X combinator you've been
> > discussing.
>
> After reading http://ling.ucsd.edu/~barker/Iota/zot.html, I noticed a
> reference to "Rosser" and "Fokker". Citeseer showed me
> http://citeseer.ist.psu.edu/fokker97systematic.html, which lists quite
> a few others (note that Iota, Jot, and Zot all use a different one).
>
> I'm really working hard trying to figure out what the X combinator
> DOES to a stack...
>
> -Billy
>
William Tanksley, Jr — 2007-01-07 01:56:05
stevan apter <
sa@...> wrote:
> between you and john, i now understand the point about "improper
> lists".
> i think the two notations can be made equivalent by adding a special
> symbol to each.
> mine yours
> ---- -----
> pair-to-parts: [ab]-ab [ab.]-ab for you, . means nil
> parts-to-pair: ab-[ab] ab-[ab.]
> k-combinator: ab-a. ab-A for me, . means execute
Yes, that would make them equivalent (although "." wouldn't mean 'nil'
for me; instead, it would be a code that meant that the previous item
was the end of the list).
> for me, . can only occur on the right side of a shuffle. for you,
> . can only occur on the left side.
> on second thought, maybe you don't need the extra symbol. isn't
> [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
> isn't the natural way for me think about these things.) if this
> is the case, then i think i favor your notation.
Well, actually, [ab[]] (either of our notations) is the same thing as
[aB] (in your notation) and [ab] in mine. I don't think [ab.] is a
"pair" in the sense of an improper list. Personally, if you asked me,
I don't think our notations need to support creating improper lists --
they are really a special case of linked list, not really something
languages should worry about in general.
I don't see why we should care about a "pair" when it's so easy to
deal with a "list". It's easy to create a list with two items; why
bother with a "pair"? The only thing specifying a pair as input can do
is force your shuffle to throw an error when the input is actually a
list. And specifying a pair as output is only useful if your language
includes words to process pairs specially.
So I still don't see the need for the "." code.
> on the question of list-deconstruction and "bad input", it seems
> that you and robbert are in agreement. i'd like to better understand
> the practical implications of this devil's bargain (freedom-from-
> exceptions for reduced expressiveness.)
It simply depends on your language, I think. A language without list
deconstruction is as powerful as a language with; but the language
with might express some things more tersely.
If the rest of your language doesn't use exceptions or runtime errors
(like Enchilada), it's a forgone conclusion that your shuffles
shouldn't support list deconstruction. If your language uses runtime
errors and/or exceptions regularly, it's probably better to include
support for list deconstructions. If your language is strongly
staticly typed with decent type inference, list deconstructions will
probably fit in nicely.
IMO.
-Billy
stevan apter — 2007-01-08 13:15:37
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Saturday, January 06, 2007 8:56 PM
Subject: Re: [stack] Concatenative macros?
> stevan apter <sa@...> wrote:
> > between you and john, i now understand the point about "improper
> > lists".
>
> > i think the two notations can be made equivalent by adding a special
> > symbol to each.
>
> > mine yours
> > ---- -----
> > pair-to-parts: [ab]-ab [ab.]-ab for you, . means nil
> > parts-to-pair: ab-[ab] ab-[ab.]
>
> > k-combinator: ab-a. ab-A for me, . means execute
>
> Yes, that would make them equivalent (although "." wouldn't mean 'nil'
> for me; instead, it would be a code that meant that the previous item
> was the end of the list).
i was relying on the fact that [1 2 3] = 1 . 2 . 3 . nil.
>
> > for me, . can only occur on the right side of a shuffle. for you,
> > . can only occur on the left side.
this directly contradicts the parts-to-pair expression above.
>
> > on second thought, maybe you don't need the extra symbol. isn't
> > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
> > isn't the natural way for me think about these things.) if this
> > is the case, then i think i favor your notation.
>
> Well, actually, [ab[]] (either of our notations) is the same thing as
> [aB] (in your notation) and [ab] in mine.
no, that isn't actually true. in my notation [ab[]] is a list of three
items: a, b, and []. [ab] in your notation is equivalent to [aB] in
mine.
> I don't think [ab.] is a
> "pair" in the sense of an improper list. Personally, if you asked me,
> I don't think our notations need to support creating improper lists --
> they are really a special case of linked list, not really something
> languages should worry about in general.
>
> I don't see why we should care about a "pair" when it's so easy to
> deal with a "list". It's easy to create a list with two items; why
> bother with a "pair"? The only thing specifying a pair as input can do
> is force your shuffle to throw an error when the input is actually a
> list. And specifying a pair as output is only useful if your language
> includes words to process pairs specially.
i think our miscommunication on this point is the rseult of terminological
confusion, which is probably my fault. for me, a pair is just a list with
two elements; thus: [1 2]. in the shuffle notation i've implemented in
various languages, [ab] matches a to 1 and b to 2, and [aB] matches a
to 1 and B the cdr of the list, viz. [2].
if my program expects a two-element list, and wants to operate on
those elements as named entities, then [ab] will pick them off and
make them available to the program. in your case, your program
will use [ab]-aB.
>
> So I still don't see the need for the "." code.
for you, [ab]-aB = [ab.]-ab, so i think you're right -- you don't need
it. for me, since on the left mean "rest of the list", . on the right
means execute, and unless i want to forego the ability to fold that
idea into the notation, i need it (or a third case beyond lower and
upper!)
>
> > on the question of list-deconstruction and "bad input", it seems
> > that you and robbert are in agreement. i'd like to better understand
> > the practical implications of this devil's bargain (freedom-from-
> > exceptions for reduced expressiveness.)
>
> It simply depends on your language, I think. A language without list
> deconstruction is as powerful as a language with; but the language
> with might express some things more tersely.
yes, i think i agree with that. that's really the whole of my point.
>
> If the rest of your language doesn't use exceptions or runtime errors
> (like Enchilada), it's a forgone conclusion that your shuffles
> shouldn't support list deconstruction. If your language uses runtime
> errors and/or exceptions regularly, it's probably better to include
> support for list deconstructions. If your language is strongly
> staticly typed with decent type inference, list deconstructions will
> probably fit in nicely.
>
> IMO.
>
> -Billy
>
William Tanksley, Jr — 2007-01-10 16:21:19
stevan apter <
sa@...> wrote:
> > stevan apter <sa@...> wrote:
> > > between you and john, i now understand the point about "improper
> > > lists".
> > > i think the two notations can be made equivalent by adding a special
> > > symbol to each.
From the rest of your message, it's clear that you didn't want support
for "improper lists"; what you wanted was the ability to get the last
item out of a list without having to execute anything. A fine
ambition. My notation (so far) doesn't support that, and I can see why
you'd want it. Furthermore, it's a natural feature within any notation
that allows list deconstruction, since such deconstruction naturally
carries the exact same risk of error (said error being that the list
doesn't have the desired structure).
> > > on second thought, maybe you don't need the extra symbol. isn't
> > > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
> > > isn't the natural way for me think about these things.) if this
> > > is the case, then i think i favor your notation.
> > Well, actually, [ab[]] (either of our notations) is the same thing as
> > [aB] (in your notation) and [ab] in mine.
> no, that isn't actually true. in my notation [ab[]] is a list of three
> items: a, b, and []. [ab] in your notation is equivalent to [aB] in
> mine.
No, you're right; my notation doesn't define an input meaning for
[ab[]], because I didn't consider what happens to nested lists. That's
because I didn't want to deal with list deconstruction, so I didn't
put any thought into it. Further instances of not putting thought into
things will be followed by further instances of putting my foot into
my mouth.
But this is worth thinking about.
I believe that the strengths of our two syntaxes can and should be
combined into a single semantics which would scale nicely, so that
languages with differing needs can pick the subset that matches their
needs and capabilities. Some languages require only shuffling; some
require execution; some require list construction; some require list
deconstruction into head and tail; and some require full list
deconstruction.
By the way, I admit grudgingly that some language designs do require
lambda forms. I persist in claiming that our mega-shuffle notation
need not support that; I would suggest that such languages should
borrow syntax from an applicative language, since that class of
languages has thoroughly researched the practice (a concatenative
language with locals is essentially the same as Haskell interpreting a
monad). Fitting lambda support into our notation would simply balloon
the notation.
Therefore, I choose to limit the features we need to support to
shuffling, enlistment, delistment, indexing, and execution. (Here I
choose to define "indexing" as accessing elements deeper in the list
than the first element, what I earlier called "full list
deconstruction".)
> if my program expects a two-element list, and wants to operate on
> those elements as named entities, then [ab] will pick them off and
> make them available to the program. in your case, your program
> will use [ab]-aB.
Unfortunately, my notation would make it impossible to execute a
combinator which happened to be the CDR of a list, since I can only
uppercase once. Strike one for my notation.
So let me go a bit closer to your notation on the input side, except
that 'a' and 'A' are no longer distinct variables. Case is used to
control how the input is fetched and how the output is generated.
I'm having some trouble defining (in my own head) the meaning of an
uppercase letter on the input side. Even in your notation it seems a
bit limited. The examples you gave are clear enough, but what happens
if an uppercase letter appears in some other place than the tail of a
list?
Anyhow, it would be a start to define a special meaning for uppercase
in the input: it's defined only as the last character in a list
pattern, and as in your notation, it means "the rest of the list". On
the output side, uppercase would indicate execution, as with my stack
shuffle notation.
I think that makes all your examples work, although "[aA]-a" doesn't
work (it has to be changed to "[aB]-a", since variable names have to
be unique regardless of case). Then the definition of cdr becomes
"[aB]-b".
I'm really not very happy with the fact that uppercase letters on the
input side are undefined except at the tail of a list. I've thought of
a few meanings, but none of them make me happy and fulfilled :-).
I'm considering making upper case in the input side mean "gather as
many values as will fit", which might be handy... What do you think?
Doing that would change the definition of CDR to "[aB]-[b]", and would
allow i to be defined as "[A]-A" (that means get the entire contents
of a list and execute each of the atoms in it, first to last). Of
course, an uppercase letter outside of a list would still be
undefined, so I haven't really completely solved the problem, but at
least I've opened a new door (I don't think either of our notations
could express the definition of "i" before).
-Billy
sa@dfa.com — 2007-01-10 20:29:28
i think i've formulated a version which captures your requirements.
since setting down the rules is more difficult than grasping the
notation by way of examples, let me do that first:
car [aB]-a
cdr [aB]-B
B is the rest of the list [a ...]. that is, B is [...].
cons aB-[aB]
B on the left matches a list. on the right [aB] is the list
with a as the first element, and B as the remaining elements.
on either side, a list may contain at most one upper-case letter:
[aBc]
a is the first, c is the last, [B] is [aBc] without a, c.
uncons [aB]-aB
i A-a
A matches a list, a is A i.
dip aB-ba
so then what do the following shuffles mean?
a-A
[aB]-[ab]
the first could be quotation; i.e. a-[a].
the second could be disquotation without execution:
[2 [3 +]] [aB]-[ab] -> [2 3 +]
i don't see any problem extending the notation to handle nested
lists on either side.
but this is just off the top of my head, and i might have
overlooked some lurking inconsistency.
concatenative@yahoogroups.com wrote on 01/10/2007 11:21:19 AM:
> stevan apter <sa@...> wrote:
> > > stevan apter <sa@...> wrote:
> > > > between you and john, i now understand the point about "improper
> > > > lists".
>
> > > > i think the two notations can be made equivalent by adding a
special
> > > > symbol to each.
>
> From the rest of your message, it's clear that you didn't want support
> for "improper lists"; what you wanted was the ability to get the last
> item out of a list without having to execute anything. A fine
> ambition. My notation (so far) doesn't support that, and I can see why
> you'd want it. Furthermore, it's a natural feature within any notation
> that allows list deconstruction, since such deconstruction naturally
> carries the exact same risk of error (said error being that the list
> doesn't have the desired structure).
>
> > > > on second thought, maybe you don't need the extra symbol. isn't
> > > > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
> > > > isn't the natural way for me think about these things.) if this
> > > > is the case, then i think i favor your notation.
>
> > > Well, actually, [ab[]] (either of our notations) is the same thing as
> > > [aB] (in your notation) and [ab] in mine.
>
> > no, that isn't actually true. in my notation [ab[]] is a list of three
> > items: a, b, and []. [ab] in your notation is equivalent to [aB] in
> > mine.
>
> No, you're right; my notation doesn't define an input meaning for
> [ab[]], because I didn't consider what happens to nested lists. That's
> because I didn't want to deal with list deconstruction, so I didn't
> put any thought into it. Further instances of not putting thought into
> things will be followed by further instances of putting my foot into
> my mouth.
>
> But this is worth thinking about.
>
> I believe that the strengths of our two syntaxes can and should be
> combined into a single semantics which would scale nicely, so that
> languages with differing needs can pick the subset that matches their
> needs and capabilities. Some languages require only shuffling; some
> require execution; some require list construction; some require list
> deconstruction into head and tail; and some require full list
> deconstruction.
>
> By the way, I admit grudgingly that some language designs do require
> lambda forms. I persist in claiming that our mega-shuffle notation
> need not support that; I would suggest that such languages should
> borrow syntax from an applicative language, since that class of
> languages has thoroughly researched the practice (a concatenative
> language with locals is essentially the same as Haskell interpreting a
> monad). Fitting lambda support into our notation would simply balloon
> the notation.
>
> Therefore, I choose to limit the features we need to support to
> shuffling, enlistment, delistment, indexing, and execution. (Here I
> choose to define "indexing" as accessing elements deeper in the list
> than the first element, what I earlier called "full list
> deconstruction".)
>
> > if my program expects a two-element list, and wants to operate on
> > those elements as named entities, then [ab] will pick them off and
> > make them available to the program. in your case, your program
> > will use [ab]-aB.
>
> Unfortunately, my notation would make it impossible to execute a
> combinator which happened to be the CDR of a list, since I can only
> uppercase once. Strike one for my notation.
>
> So let me go a bit closer to your notation on the input side, except
> that 'a' and 'A' are no longer distinct variables. Case is used to
> control how the input is fetched and how the output is generated.
>
> I'm having some trouble defining (in my own head) the meaning of an
> uppercase letter on the input side. Even in your notation it seems a
> bit limited. The examples you gave are clear enough, but what happens
> if an uppercase letter appears in some other place than the tail of a
> list?
>
> Anyhow, it would be a start to define a special meaning for uppercase
> in the input: it's defined only as the last character in a list
> pattern, and as in your notation, it means "the rest of the list". On
> the output side, uppercase would indicate execution, as with my stack
> shuffle notation.
>
> I think that makes all your examples work, although "[aA]-a" doesn't
> work (it has to be changed to "[aB]-a", since variable names have to
> be unique regardless of case). Then the definition of cdr becomes
> "[aB]-b".
>
> I'm really not very happy with the fact that uppercase letters on the
> input side are undefined except at the tail of a list. I've thought of
> a few meanings, but none of them make me happy and fulfilled :-).
>
> I'm considering making upper case in the input side mean "gather as
> many values as will fit", which might be handy... What do you think?
> Doing that would change the definition of CDR to "[aB]-[b]", and would
> allow i to be defined as "[A]-A" (that means get the entire contents
> of a list and execute each of the atoms in it, first to last). Of
> course, an uppercase letter outside of a list would still be
> undefined, so I haven't really completely solved the problem, but at
> least I've opened a new door (I don't think either of our notations
> could express the definition of "i" before).
>
> -Billy
>
stevan apter — 2007-01-10 22:19:09
----- Original Message -----
From: <sa@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, January 10, 2007 3:29 PM
Subject: Re: [stack] Concatenative macros?
>
>
> i think i've formulated a version which captures your requirements.
> since setting down the rules is more difficult than grasping the
> notation by way of examples, let me do that first:
>
> car [aB]-a
> cdr [aB]-B
>
> B is the rest of the list [a ...]. that is, B is [...].
>
> cons aB-[aB]
>
> B on the left matches a list. on the right [aB] is the list
> with a as the first element, and B as the remaining elements.
>
> on either side, a list may contain at most one upper-case letter:
>
> [aBc]
correction: a list may contain any number of non-contiguous upper-
case letter, e.g.
[aBcDe]
is fine, but
[aBCd]
is not.
>
> a is the first, c is the last, [B] is [aBc] without a, c.
>
> uncons [aB]-aB
>
> i A-a
>
> A matches a list, a is A i.
>
> dip aB-ba
>
> so then what do the following shuffles mean?
>
> a-A
> [aB]-[ab]
>
> the first could be quotation; i.e. a-[a].
>
> the second could be disquotation without execution:
>
> [2 [3 +]] [aB]-[ab] -> [2 3 +]
>
> i don't see any problem extending the notation to handle nested
> lists on either side.
>
> but this is just off the top of my head, and i might have
> overlooked some lurking inconsistency.
>
> concatenative@yahoogroups.com wrote on 01/10/2007 11:21:19 AM:
>
> > stevan apter <sa@...> wrote:
> > > > stevan apter <sa@...> wrote:
> > > > > between you and john, i now understand the point about "improper
> > > > > lists".
> >
> > > > > i think the two notations can be made equivalent by adding a
> special
> > > > > symbol to each.
> >
> > From the rest of your message, it's clear that you didn't want support
> > for "improper lists"; what you wanted was the ability to get the last
> > item out of a list without having to execute anything. A fine
> > ambition. My notation (so far) doesn't support that, and I can see why
> > you'd want it. Furthermore, it's a natural feature within any notation
> > that allows list deconstruction, since such deconstruction naturally
> > carries the exact same risk of error (said error being that the list
> > doesn't have the desired structure).
> >
> > > > > on second thought, maybe you don't need the extra symbol. isn't
> > > > > [ab[]] a pair? (as i said, the "car/cdr/cons" approach to lists
> > > > > isn't the natural way for me think about these things.) if this
> > > > > is the case, then i think i favor your notation.
> >
> > > > Well, actually, [ab[]] (either of our notations) is the same thing as
> > > > [aB] (in your notation) and [ab] in mine.
> >
> > > no, that isn't actually true. in my notation [ab[]] is a list of three
> > > items: a, b, and []. [ab] in your notation is equivalent to [aB] in
> > > mine.
> >
> > No, you're right; my notation doesn't define an input meaning for
> > [ab[]], because I didn't consider what happens to nested lists. That's
> > because I didn't want to deal with list deconstruction, so I didn't
> > put any thought into it. Further instances of not putting thought into
> > things will be followed by further instances of putting my foot into
> > my mouth.
> >
> > But this is worth thinking about.
> >
> > I believe that the strengths of our two syntaxes can and should be
> > combined into a single semantics which would scale nicely, so that
> > languages with differing needs can pick the subset that matches their
> > needs and capabilities. Some languages require only shuffling; some
> > require execution; some require list construction; some require list
> > deconstruction into head and tail; and some require full list
> > deconstruction.
> >
> > By the way, I admit grudgingly that some language designs do require
> > lambda forms. I persist in claiming that our mega-shuffle notation
> > need not support that; I would suggest that such languages should
> > borrow syntax from an applicative language, since that class of
> > languages has thoroughly researched the practice (a concatenative
> > language with locals is essentially the same as Haskell interpreting a
> > monad). Fitting lambda support into our notation would simply balloon
> > the notation.
> >
> > Therefore, I choose to limit the features we need to support to
> > shuffling, enlistment, delistment, indexing, and execution. (Here I
> > choose to define "indexing" as accessing elements deeper in the list
> > than the first element, what I earlier called "full list
> > deconstruction".)
> >
> > > if my program expects a two-element list, and wants to operate on
> > > those elements as named entities, then [ab] will pick them off and
> > > make them available to the program. in your case, your program
> > > will use [ab]-aB.
> >
> > Unfortunately, my notation would make it impossible to execute a
> > combinator which happened to be the CDR of a list, since I can only
> > uppercase once. Strike one for my notation.
> >
> > So let me go a bit closer to your notation on the input side, except
> > that 'a' and 'A' are no longer distinct variables. Case is used to
> > control how the input is fetched and how the output is generated.
> >
> > I'm having some trouble defining (in my own head) the meaning of an
> > uppercase letter on the input side. Even in your notation it seems a
> > bit limited. The examples you gave are clear enough, but what happens
> > if an uppercase letter appears in some other place than the tail of a
> > list?
> >
> > Anyhow, it would be a start to define a special meaning for uppercase
> > in the input: it's defined only as the last character in a list
> > pattern, and as in your notation, it means "the rest of the list". On
> > the output side, uppercase would indicate execution, as with my stack
> > shuffle notation.
> >
> > I think that makes all your examples work, although "[aA]-a" doesn't
> > work (it has to be changed to "[aB]-a", since variable names have to
> > be unique regardless of case). Then the definition of cdr becomes
> > "[aB]-b".
> >
> > I'm really not very happy with the fact that uppercase letters on the
> > input side are undefined except at the tail of a list. I've thought of
> > a few meanings, but none of them make me happy and fulfilled :-).
> >
> > I'm considering making upper case in the input side mean "gather as
> > many values as will fit", which might be handy... What do you think?
> > Doing that would change the definition of CDR to "[aB]-[b]", and would
> > allow i to be defined as "[A]-A" (that means get the entire contents
> > of a list and execute each of the atoms in it, first to last). Of
> > course, an uppercase letter outside of a list would still be
> > undefined, so I haven't really completely solved the problem, but at
> > least I've opened a new door (I don't think either of our notations
> > could express the definition of "i" before).
> >
> > -Billy
> >
>
>
William Tanksley, Jr — 2007-01-11 18:02:12
sa@... <
sa@...> wrote:
> i think i've formulated a version which captures your requirements.
I think I see some ambiguities.
> since setting down the rules is more difficult than grasping the
> notation by way of examples, let me do that first:
Agreed.
> car [aB]-a
> cdr [aB]-B
> B is the rest of the list [a ...]. that is, B is [...].
I do like your notation of uppercase meaning "the rest of the list".
> cons aB-[aB]
> B on the left matches a list.
But this is a contradiction. B on the left doesn't match a list; it
matches "the rest of the list". It's true that at the end of the list
"the rest of the list" happens to be a CDR, which is enclosed in a
list -- but our notation hides that fact, and we shouldn't expect the
user to know it.
Therefore I propose that uppercase on the left not match a list, but
rather match "the rest of the list" (and not be defined outside of a
list, nor if used twice inside a list).
> on the right [aB] is the list
> with a as the first element, and B as the remaining elements.
I propose that uppercase on the right side mean execution, always.
So your example
> cons aB-[aB]
becomes (I suggest):
cons a[B]-[ab]
> on either side, a list may contain at most one upper-case letter:
> [aBc]
I agree with this, because obviously "the rest of the list" doesn't
make sense when used more than once per list. Your followup message
contradicts this because I think you were believing that uppercase
meant "there is a list here", but that's not accurate. If you want to
match a list, you can make it explicit, like this:
[a[B][C]]-[c][b]
> uncons [aB]-aB
And in my proposed notation,
uncons [aB]-a[b]
It's an implementation detail that B is entirely contained within the
CDR list of the original list, so no new list needs to be formed.
> i A-a
> A matches a list, a is A i.
This isn't accurate, because 'i' must execute each item, not merely
unquote a list. It's also ambiguous what A means here -- you defined
it as "rest of the list", but you're using it here as "a list".
I propose:
i [A]-A
First, we see that the unquoting is explicit, but different from
execution. Second, we see that execution is expressed by uppercase
letter on the right side. This means that uppercase means something
different on the left and right side -- but this seems to me to be
reasonable, since the left side is a pattern, while the right side is
not.
> dip aB-ba
Again, I would express this as:
dip a[b]-Ba
> so then what do the following shuffles mean?
> a-A
> the first could be quotation; i.e. a-[a].
In my notation, this is the general form of 'i'; it executes anything,
list or non-list.
> [aB]-[ab]
> the second could be disquotation without execution:
> [2 [3 +]] [aB]-[ab] -> [2 3 +]
In my notation that would be identity.
If you want disquotation without execution, you'd write:
[a[B]]-[ab]
> i don't see any problem extending the notation to handle nested
> lists on either side.
Correct, unless we confuse our notation with CDR notation. In our
notation the tail of a list is not _written as_ a list -- it's a group
of items. It's an array style notation. If we adopt your style, every
list would have a CDR of [], so the two left-hand expressions [a[]]
and [a] would match the same lists. I think it gets worse, because it
would become difficult (ambiguous) to express lists that contain the
empty list.
-Billy
sa@dfa.com — 2007-01-11 19:16:55
i think i like this.
concatenative@yahoogroups.com wrote on 01/11/2007 01:02:12 PM:
> sa@... <sa@...> wrote:
> > i think i've formulated a version which captures your requirements.
>
> I think I see some ambiguities.
>
> > since setting down the rules is more difficult than grasping the
> > notation by way of examples, let me do that first:
>
> Agreed.
>
> > car [aB]-a
> > cdr [aB]-B
> > B is the rest of the list [a ...]. that is, B is [...].
>
> I do like your notation of uppercase meaning "the rest of the list".
>
> > cons aB-[aB]
> > B on the left matches a list.
>
> But this is a contradiction. B on the left doesn't match a list; it
> matches "the rest of the list". It's true that at the end of the list
> "the rest of the list" happens to be a CDR, which is enclosed in a
> list -- but our notation hides that fact, and we shouldn't expect the
> user to know it.
>
> Therefore I propose that uppercase on the left not match a list, but
> rather match "the rest of the list" (and not be defined outside of a
> list, nor if used twice inside a list).
>
> > on the right [aB] is the list
> > with a as the first element, and B as the remaining elements.
>
> I propose that uppercase on the right side mean execution, always.
>
> So your example
> > cons aB-[aB]
> becomes (I suggest):
> cons a[B]-[ab]
>
> > on either side, a list may contain at most one upper-case letter:
> > [aBc]
>
> I agree with this, because obviously "the rest of the list" doesn't
> make sense when used more than once per list. Your followup message
> contradicts this because I think you were believing that uppercase
> meant "there is a list here", but that's not accurate. If you want to
> match a list, you can make it explicit, like this:
>
> [a[B][C]]-[c][b]
>
> > uncons [aB]-aB
>
> And in my proposed notation,
>
> uncons [aB]-a[b]
>
> It's an implementation detail that B is entirely contained within the
> CDR list of the original list, so no new list needs to be formed.
>
> > i A-a
> > A matches a list, a is A i.
>
> This isn't accurate, because 'i' must execute each item, not merely
> unquote a list. It's also ambiguous what A means here -- you defined
> it as "rest of the list", but you're using it here as "a list".
>
> I propose:
>
> i [A]-A
>
> First, we see that the unquoting is explicit, but different from
> execution. Second, we see that execution is expressed by uppercase
> letter on the right side. This means that uppercase means something
> different on the left and right side -- but this seems to me to be
> reasonable, since the left side is a pattern, while the right side is
> not.
>
> > dip aB-ba
>
> Again, I would express this as:
>
> dip a[b]-Ba
>
> > so then what do the following shuffles mean?
>
> > a-A
> > the first could be quotation; i.e. a-[a].
>
> In my notation, this is the general form of 'i'; it executes anything,
> list or non-list.
>
> > [aB]-[ab]
> > the second could be disquotation without execution:
> > [2 [3 +]] [aB]-[ab] -> [2 3 +]
>
> In my notation that would be identity.
>
> If you want disquotation without execution, you'd write:
>
> [a[B]]-[ab]
>
> > i don't see any problem extending the notation to handle nested
> > lists on either side.
>
> Correct, unless we confuse our notation with CDR notation. In our
> notation the tail of a list is not _written as_ a list -- it's a group
> of items. It's an array style notation. If we adopt your style, every
> list would have a CDR of [], so the two left-hand expressions [a[]]
> and [a] would match the same lists. I think it gets worse, because it
> would become difficult (ambiguous) to express lists that contain the
> empty list.
>
> -Billy
>
William Tanksley, Jr — 2007-01-11 20:18:57
sa@... <
sa@...> wrote:
> i think i like this.
I just noticed a problem with my idea. Help me...
> Billy wrote on 01/11/2007 01:02:12 PM:
> > I propose:
> > i1 [A]-A
[...snip...]
> i2 a-A
> In my notation, this is the general form of 'i'; it executes anything,
> list or non-list.
I'm wrong about i2. It won't correctly execute a list, because if i1
works, the result of executing a list MUST be the list itself. (Try
passing a list containing a list, such as [[2]], to 'i'.)
So my notation can't express Joy's 'i', because my notation can only
execute lists, not atoms.
Unless, of course, we choose to allow me to define Joy's 'i' as:
i == [ atom? ] [ a-A ] [ [A]-A ] ifte.
That may be acceptable, since Joy's i wasn't originally intended to
work that way (it just happened, from what I recall).
What do you think?
-Billy
sa@dfa.com — 2007-01-11 20:49:27
i don't quite follow the reasoning here, but it has always
seemed to me that joy's 'i' (and other combinators as well)
was unduly restrictive in requiring a *quotation* to
execute. and in fact i've never built that restriction
into any of my languages.
the way i've always thought of 'i' was that it took its
operand x and: if x is a quotation push the contents of
x onto the queue, else push x onto the queue. so
[[2]] i
pushes [2] onto the queue, and it winds up on the stack.
3 i
pushes 3 onto the queue, and it winds up on the stack.
[+] i
pushes + onto the queue, and then it's executed.
so once again, why can't you interpret i1 and i2 in that
framework? in other words, what's wrong with your
redefinition of 'i'?
concatenative@yahoogroups.com wrote on 01/11/2007 03:18:57 PM:
> sa@... <sa@...> wrote:
> > i think i like this.
>
> I just noticed a problem with my idea. Help me...
>
> > Billy wrote on 01/11/2007 01:02:12 PM:
> > > I propose:
>
> > > i1 [A]-A
>
> [...snip...]
>
> > i2 a-A
> > In my notation, this is the general form of 'i'; it executes anything,
> > list or non-list.
>
> I'm wrong about i2. It won't correctly execute a list, because if i1
> works, the result of executing a list MUST be the list itself. (Try
> passing a list containing a list, such as [[2]], to 'i'.)
>
> So my notation can't express Joy's 'i', because my notation can only
> execute lists, not atoms.
>
> Unless, of course, we choose to allow me to define Joy's 'i' as:
>
> i == [ atom? ] [ a-A ] [ [A]-A ] ifte.
>
> That may be acceptable, since Joy's i wasn't originally intended to
> work that way (it just happened, from what I recall).
>
> What do you think?
>
> -Billy
>
William Tanksley, Jr — 2007-01-12 16:59:40
sa@... <
sa@...> wrote:
> i don't quite follow the reasoning here, but it has always
> seemed to me that joy's 'i' (and other combinators as well)
> was unduly restrictive in requiring a *quotation* to
> execute. and in fact i've never built that restriction
> into any of my languages.
I think that Joy's 'i' will work with a bare function (i.e., 2 2 [+]
car i == 4). Manfred mentioned that he'd never thought of that while
he was building it, and it was accidental (but nice) that it worked.
> the way i've always thought of 'i' was that it took its
> operand x and: if x is a quotation push the contents of
> x onto the queue, else push x onto the queue. so
> [[2]] i
> pushes [2] onto the queue, and it winds up on the stack.
> 3 i
> pushes 3 onto the queue, and it winds up on the stack.
> [+] i
> pushes + onto the queue, and then it's executed.
> so once again, why can't you interpret i1 and i2 in that
> framework? in other words, what's wrong with your
> redefinition of 'i'?
You're right. But it's still true that [A]-A and a-A are not *both*
definitions of 'i'. Using your semantics, the problem is that the
second one will execute the list (which will unquote it), but won't
execute any of the things inside the list (functions will be dumped
onto the stack).
Compare the results of [+ -] a-A to the results of [+ -] [A]-A.
So my definition didn't cover the cases well enough, and (at least)
one of my examples was bad. I think I'm going to claim that the
definition of i is a-A, and leave it at that; the meaning of [A]-A
will be to perform 'i' on every item in the list (which is not the
same as performing 'i' on the list).
In other words, uppercase on the left *means* that each item in the
uppercased variable gets 'i' applied to it.
Okay, I think I'm satisfied... This problem was only in my example,
not in my notation.
-Billy
sa@dfa.com — 2007-01-15 16:32:10
solve the 99 lisp (haskell/prolog/etc.) problems in enchilada.
:-)
Robbert van Dalen — 2007-01-16 19:27:20
I'd rather solve 99 lisp problems with the Game Of Live - now *thats*
a challenge!
but yes, it would be interesting to see how many symbols are needed
to solve crossword puzzles in Enchilada.
but seriously, such problems have to wait until Enchilada reaches
version 1.0.
On Jan 15, 2007, at 5:32 PM, sa@... wrote:
>
>
> solve the 99 lisp (haskell/prolog/etc.) problems in enchilada.
>
> :-)
>
iepos — 2007-01-16 22:22:51
Hi Billy & all,
It's been a while! Sorry this post is a little belated. I tried
sending it last week, but something was wrong with my account (my
concatenative membership had expired, apparently; or maybe the list
was unmoderated back when I used to use it). In any case, Yahoo ate
my post up, so I had to rewrite it ...
> A doubt begins to stir in my mind. Is the Fokker X combinator
actually
> a pseudo-combinator? If so, is that a problem with the Fokker X
> combinator, or is it a problem with Kerby's ideas about
> pseudo-combinators?
Yes. The Fokker X combinator would be a "pseudo-combinator". But
that was a bad choice of terminology on my part. Under the standard
definition, it is a combinator. The restricted objects I was calling
combinators are what Curry called "proper combinators". So we ought
to say that the Fokker X combinator is an improper combinator, but a
combinator nonetheless. To recap, here are the standard definitions
which I should have used:
Proper combinator: Any closed lambda-form in which all lambdas occur
at the head (i.e., at the far left).
Combinator: Any closed lambda-form whatsoever (or, equivalently: any
combination of proper combinators)
This applies to both applicative and concatenative systems (although
the interpretation of "lambda" and "combination" of course depends
on which system we're dealing with). Another way of putting it is
that proper combinators are ones that can be expressed by a rewrite
rule; i.e., in an applicative system, Z is a proper combinator if
you can state a rule
Zxyz == (some applicative combination of x, y, and z)
or the like, with as many variables as needed; the standard
combinators S, K, I, B, C, W, T, etc. are all proper, while the
Fokker X combinator and, for example, Y, the "paradoxical" or fixed-
point combinator, are not.
Likewise, in a concatenative system, Z is a proper combinator if you
can state a rule
[z] [y] [x] Z == (some concatenative combination of x, y, and z)
or the like, with as many variables as needed. The standard
combinators i, cons, dip, cat, swap, dup, zap, k, and cat are all
proper.
Now, since the Fokker X combinator is improper, the question
naturally arises: Is there a complete basis (in applicative
combinatory logic) consisting of a single _proper_ combinator? The
answer is no. The standard proof (due to William Craig) goes roughly
like this: Every basis of proper combinators must contain a
selector, i.e., a combinator like I or K, that takes some parameters
(in a curried fashion, of course) and returns a certain one of them
untouched, ignoring the rest. This is because selectors cannot be
constructed out of other proper combinators; this can been seen by
looking at the rewriting process: An expression Fxyz, for example,
where F is written as some combination of proper combinators A, B,
C, ..., none of which is a selector, can never reduce to just the
the single variable 'x' by applying rewrite rules, because the
rewrite rules for A, B, C, ... each have a right-hand-side
consisting of something more than just a single variable. There is a
combinator F (namely, the selector \xyz.x) for which Fxyz would
reduce to x; but it is impossible to construct this F, or likewise,
any selector, from a basis of non-selectors. Therefore, in a basis
consisting of a single proper combinator, this combinator must be a
selector. But selectors have no duplicative effect; therefore, it
would be impossible to construct "W" or "S", for example. So a
complete basis consisting of a single proper combinator does not
exist.
So in a complete basis of proper combinators, we need at least two.
And of course it turns out that two is enough, since {S, K} is a
complete basis. But if you allow improper combinators, then one is
enough, as the Fokker X combinator shows, for instance.
Now, what about in a concatenative system? Well, using an argument
similar to the one above, we can show that a basis consisting of a
single proper combinator is again impossible. This is because any
basis of proper combinators must contain what I'll call a "total
dequoter", i.e., a combinator whose right-hand-side contains no
quotations; total dequoters simply execute some of their parameters
(possibly multiple times, or none at all) in a certain order;
examples would be i, k, zap, 'cat i', and
X\ Y\ Z\ W\ Y X W X
A total dequoter is needed, because if every combinator in the basis
had a quotation on the right-hand-side, then it would never be
possible to get down to an empty stack, once a quotation was on it;
specifically, the expression [] F, where F is written as some
combination of proper combinators A, B, C, ..., none of which is a
total dequoter, could never reduce to the empty program, which shows
that 'i' could not be constructed, since 'i' would be an F that
works. Therefore, in a basis consisting of a single proper
combinator, this combinator must be a total dequoter. But from a
total dequoter alone, it is clearly impossible to construct cons, or
even swap, dup, dip, or cat. So a basis consisting of a single
proper combinator again does not exist.
So the best we could hope for would be a two-combinator basis of
proper combinators, or a one-combinator basis consisting of an
improper combinator. We know that a basis of two proper combinators
is possible; for example, {cake, k} works.
So what about a one-combinator basis? This is an interesting
question. It will not work to simply take the concatenative version
of the Fokker X combinator (or the Rosser, or any other applicative
one-combinator complete basis). This would be equivalent to the
basis {s, k}, which is _not_ complete in a concatenative system.
From {s, k}, we can construct all applicative combinators (i, b, c,
etc.) and even many others (swap, cons, dup, zap), but it would be
impossible to construct dip (or cat). You can see this by looking at
the rewrite rules for 's' and 'k':
[Z] [Y] [X] s == [[Z] Y] [Z] X
[Y] [X] k == X
Note that on the right-hand-side of both rules, there is nothing to
the right of the only dequoted term X. In reducing the
expression '[B] [A] F', where F is some (concatenative) combination
of 's' and 'k', every step of the reduction preserves the property
that no subexpression contains a (dequoted) A followed by anything
containing B; therefore, it could never reduce to 'A [B]'. So it is
impossible to construct dip from {s, k}.
But after some fiddling, I was able to find a one-combinator base
that does work. The idea is to make a combinator with 'cake' and 'k'
somehow embedded in it, built in such a way that, with a little
manipulation, we can extract them back out. Let
z == X\ zap [cake] [k] X
or, in other words,
z == [zap [cake] [k]] dip i
Then
[] [] z z
== [] zap [cake] [k] z
== [cake] [k] z
== [cake] zap [cake] [k] k
== [cake] [k] k
== k
So we can construct k. And
[] [] [zap k] z
== [] [] zap [cake] [k] zap k
== [] [cake] [k] zap k
== [] [cake] k
== cake
So we can construct cake. Explicitly, we can write them
k == [] [] z z
cake == [] [] [[] [] [] z z [] [] z z] z
So this {z} forms a complete basis. Incidentally, this construction
doesn't depend specifically on 'cake'; you could replace 'cake' with
any combinator that, along with 'k', forms a complete basis.
- Brent
William Tanksley, Jr — 2007-01-17 05:56:16
iepos <
bkerby@...> wrote:
> Hi Billy & all,
> It's been a while! Sorry this post is a little belated. I tried
> sending it last week, but something was wrong with my account (my
> concatenative membership had expired, apparently; or maybe the list
> was unmoderated back when I used to use it). In any case, Yahoo ate
> my post up, so I had to rewrite it ...
Thank you for putting the effort in. I have one more question.
> > A doubt begins to stir in my mind. Is the Fokker X combinator
> > actually
> > a pseudo-combinator? If so, is that a problem with the Fokker X
> > combinator, or is it a problem with Kerby's ideas about
> > pseudo-combinators?
> Yes. The Fokker X combinator would be a "pseudo-combinator". But
> that was a bad choice of terminology on my part. Under the standard
> definition, it is a combinator. The restricted objects I was calling
> combinators are what Curry called "proper combinators". So we ought
> to say that the Fokker X combinator is an improper combinator, but a
> combinator nonetheless. To recap, here are the standard definitions
> which I should have used:
Ah! A light dawns. Thank you again. Your definitions make sense.
> But after some fiddling, I was able to find a one-combinator base
> that does work. The idea is to make a combinator with 'cake' and 'k'
> somehow embedded in it, built in such a way that, with a little
> manipulation, we can extract them back out. Let
> z == [zap [cake] [k]] dip i
Nice. Now I'm going to have to try to understand Fokker's paper so I
can try to construct a simpler version. (I'll have to pick a
definition of "simpler".)
Before I fiddle with that, though, I'm going to work on the
two-combinator flat language... That's seriously interesting. To me.
> - Brent
-Billy
William Tanksley, Jr — 2007-01-19 16:52:13
Sorry; I said in my last post that I had one more question, and then I
forgot to ask it.
My question is: how does Okasaki's and Barker's work apply to this?
Okay, actually, what I want to know is how to design a flat,
two-combinator, concatenative language that's implemented using stacks
and lists (like Joy).
I've wanted to figure this out for a while, but my friend wants it in
order to design a genetic algorithm system that allows maximum
flexibility in cutting genomes.
iepos <
bkerby@...> wrote:
> So what about a one-combinator basis? This is an interesting
> question. It will not work to simply take the concatenative version
> of the Fokker X combinator (or the Rosser, or any other applicative
> one-combinator complete basis). This would be equivalent to the
> basis {s, k}, which is _not_ complete in a concatenative system.
Okasaki, in the postscript file linked to at
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03, builds a
concatenative system using different rules, under which the classical
combinators form the classical structures (and so {s,k} is complete,
hence the classical X combinators are complete). The difference
between his notation and yours is that his notation uses combinators
to build a list-structure which is then treated as a grammatical
structure in itself; your notation has its own grammatical structure.
His notation has two strengths: first, it harnesses directly the
classic combinators; and second, it is syntactically completely flat
(lists and quotation play no part in the grammar). I'm concerned that
it has weaknesses that I don't understand, however, because I can't
figure out how it actually works well enough to design an
implementation.
I also found Barker's work on Zot at
http://ling.ucsd.edu/~barker/Iota/zot.html to be compelling -- I
speculate that Zot (and probably Jot as well) qualify as
concatenative, although they don't explicitly specify a stack (that
could be another example of a non-stack-based concatenative language,
or it could just be that the stack is hidden by the way in which the
semantics of the language is described). Again, though, the notation
used is foreign to me, so further examination is hindered. The reason
I qualify Zot as probably concatenative is that the author describes
several properties of it in ways that make me think it might meet my
definitions as well. Interestingly, it's probably also applicative, if
I read its notation right (although it doesn't provide
variables/lambdas, so it's pure dataflow -- that certainly reduces the
differences between the concepts).
> But after some fiddling, I was able to find a one-combinator base
> that does work. The idea is to make a combinator with 'cake' and 'k'
> somehow embedded in it, built in such a way that, with a little
> manipulation, we can extract them back out. Let
> z == [zap [cake] [k]] dip i
Interesting. I came up with a similar combinator (i.e. one which
contained both cake and k) when I was attempting to build a system
that didn't use a list structure as part of its grammar back a while
ago. Unfortunately, my notes are lost, and since I wasn't trying for
completeness (indeed, I didn't understand it at all) I doubt I
achieved it.
Your combinator, unlike Barker's and Okasaki's, makes sense to me :-).
The problem is that I don't see whether it's possible to transform it
to a flat system.
My problem with non-flat systems isn't merely syntactic; my concern is
that they hide infinite semantic complexity in the ability to create
layers of quotations. It's hard to unambiguously measure the
K-complexity of a non-flat syntax; do you count the depth of nesting,
or do you count opening brackets, or ...? A flat syntax makes the
K-complexity of things implemented in it obvious.
> - Brent
-Billy
iepos — 2007-02-06 05:39:27
Billy and all,
Sorry for taking so long to respond to this. When I first read your
email, the server hosting Chris Okasaki's paper was apparently down.
And then for a couple weeks I forgot to come back and try it again. I
must say -- What he's accomplished is pretty cool.
> My question is: how does Okasaki's and Barker's work apply to this?
> Okay, actually, what I want to know is how to design a flat,
> two-combinator, concatenative language that's implemented using
stacks
> and lists (like Joy).
I want to respond to your second question first; hopefully this will
in turn shed some light on the relationship between flat
concatenative systems and Okasaki's and Barker's work.
When I wrote that flaky old program that searches for optimal Joy
constructions, I put in an option to search only for flat
constructions (activated by uncommenting the line "//#define
NOQUOTES" :-) ) but never really pursued the problem, although I
agree it is an interesting one.
Let's try this. We're looking for a finite set of combinators from
which we can construct any combinator by concatenation alone (no
quotations). We'll say that such a set of combinators forms complete
flat basis. To start, we observe that if "z" is any combinator
forming a complete (non-flat) basis (for example, z == X\ zap [cake]
[k] X, as we've seen), then {[], [z], unit, cat, i} forms a complete
flat basis. Any concatenative combination of "z" can be decomposed
into a flat one in terms of these combinators quite easily; For
example,
[z [z z] z]
== [z] [[z z] z] cat
== [z] [[z z]] [z] cat cat
== [z] [z z] unit [z] cat cat
== [z] [z] [z] cat unit [z] cat cat
If the expression had contained a dequoted 'z', then we would have
needed to use '[z] i' (or, if desired, we could have included 'z' in
the basis instead of i); and if the expression had contained a null
quotation, we would have had to use []. In this way, we can decompose
any concatenative combination of "z", and hence any combinator
whatsoever, into a flat expression in terms of {[], [z], unit, cat,
i}.
Now, we can do better than that. You really want a basis in terms of
just two combinators (not five). So let's think about what would have
to be true about such a basis:
1. One of the two combinators must be able to execute on an empty
stack; therefore it must do nothing but push a sequence of constant
quotations onto the stack (This will necessarily be an improper
combinator).
2. The other combinator must be a total dequoter, such as 'i' or 'k'
(otherwise, roughly speaking, it's impossible to get down to an empty
stack again once anything has been pushed onto it).
It might be possible to relax the first requirement if our system has
a "bottomless stack", i.e., if we can assume infinitely many stack
items are always available if needed, so that "[] dip" is considered
equivalent to the empty program (analagous to the beta-eta-theory of
classical combinatory logic, as opposed to the beta-theory). In any
case, this won't be necessary, because it turns out there is a
solution satisfying both requirements.
Also, intuitively, the empty quotation [] must be embedded somehow in
the first combinator. My first attempts at a two-combinator flat
basis were {[] [z], i}, {[z] [], i}, {[] [cake] [k], i}, {[cake] [k]
[], i}, and so forth, before realizing that these are all doomed
because it is impossible to construct "cat" from them. But I'll skip
over my failed attempts and cut straight to one that works. To do
this, first define a new combinator "q":
[B] [A] q == [[B]] [A B]
This combinator, along with k, forms a complete basis (in the
ordinary, non-flat sense). This is interesting in itself, since "q"
is a bit simpler than "cake" ({cake, k} formerly being the simplest
known basis of two proper combinators). But, as you've mentioned,
Billy, it's not exactly clear how to count the size of a combinator.
In my search program, I've counted it as the total number of atoms
plus the number of quotations (so "q" would be size 6, 3 atoms plus 3
quotations, while "cake" would be size 8, 4 atoms plus 4 quotations);
but other schemes may be equally valid.
Anyhow, here are the essential constructions from {q,k}:
zap == [] k
i == [] q k
unit == [] q zap
swat == q unit k (where swat == X\ Y\ [X Y] == swap cat)
dip == unit [unit] swat i swat i
dup == [] q unit swat i
I'll give the verification of "dip", the most interesting of these:
[Y] [X] unit [unit] swat i swat i
== [Y] [[X]] [unit] swat i swat i
== [Y] [unit [X]] i swat i
== [Y] unit [X] swat i
== [[Y]] [X] swat i
== [X [Y]] i
== X [Y]
It's worth noting that
swat i == X\ Y\ X Y == dip i
This combinator simply executes the top two programs on the stack. It
may be constructed simply as "q k". Using this makes the above
constructions of "dip" and "dup" much more efficient (In fact, a
computer search shows that they are then minimal, in terms of their
size as combinations of the original base combinators "q" and "k").
Also, notice that the constructions of unit and swat (as well as zap,
i, and dup) are flat in terms of [], q, and k. This will be useful to
us in a moment. But I want to emphasize that I'm not claiming that
{q, k} is a complete flat basis, because it certainly isn't. However,
{q, k} is complete in the ordinary sense, and will be useful in
building a flat basis:
All right, so for a two-combinator basis, define:
o == [] [q] [k]
Then {o,i} is a complete flat basis. To prove this, we just need to
show how to construct each combinator in {[], [q], [k], swat, unit},
because this set, along with "i", clearly forms a complete flat
basis, applying with minor adjustment the simple algorithm
illustrated above for {[], [z], cat, unit, i}, noticing that "swat"
will do just as well as "cat".
So here we go. First, as an auxiliary step, we find that
oi == q
and
ooooqiiiiii == [][k]
(We might as well dispense with unnecessary spaces). Here's the
verification:
oi
== [][q][k]i
== [][q]k
== q
ooooqiiiiii
== ooo[][q][k]qiiiiii
== ooo[][[q]][kq]iiiiii
== ooo[][[q]]kqiiiii
== ooo[q]qiiiii
== oo[][q][k][q]qiiiii
== oo[][q][[k]][qk]iiiii
== oo[][q][[k]]qkiiii
== oo[][[q]][[k]q]kiiii
== oo[][k]qiiii
== oo[[]][k[]]iiii
== oo[[]]k[]iiii
== oo[[]]kiii
== o[][q][k][[]]kiii
== o[][q][]iii
== o[][q]ii
== o[]qi
== [][q][k][]qi
== [][q][[k]][k]i
== [][q][[k]]k
== [][k]
From this we can get zap:
zap == [][k] i
The verification:
[A][][k]i
== [A][]k
==
Now we can construct []:
[] == [][k] zap
This was one of the five we wanted. So, one down, four to go.
Actually, we're done with most of the hard work. Next construct [k]:
[k] == [][k] [] q i
The verification:
[][k][]qi
== [][[k]][k]i
== [][[k]]k
== [k]
Now take advantage of our original flat constructions of "unit"
and "swat":
unit == [] q zap
swat == q unit k
Now it remains only to construct [q]. (Note we already
constructed "q" at the very beginning, but in a flat system, this is
not enough.):
[q] == o zap unit k
The verification:
o zap unit k
== [][q][k] zap unit k
== [] [q] unit k
== [] [[q]] k
== [q]
So there we have it! We can write all this explicitly as
[] == oooooiiiiiiioooooiiiiiiii
[k] == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii
unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii
swat ==
oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo
oiiiiiiiioiii
[q] ==
ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo
oiiiiiiioooooiiiiiiiioiii
Of course, these constructions could probably be improved; my poor
little Joy searcher (among other restrictions) only works on a basis
of proper combinators, which does not apply in this case. So I'm not
able to determine what the minimal constructions might be. Also, it
is certainly possible that a more clever choice of basis could lead
to smaller constructions.
- Brent
William Tanksley, Jr — 2007-02-06 19:19:27
iepos <
bkerby@...> wrote:
> Billy and all,
> Sorry for taking so long to respond to this. When I first read your
> email, the server hosting Chris Okasaki's paper was apparently down.
> And then for a couple weeks I forgot to come back and try it again. I
> must say -- What he's accomplished is pretty cool.
I agree -- and it was both instructive and reasonably fun to read.
> I want to respond to your second question first; hopefully this will
> in turn shed some light on the relationship between flat
> concatenative systems and Okasaki's and Barker's work.
Indeed it did! I especially appreciate you including your reasoning.
Not only do I know how to construct the language I wanted, I also
understand a bit more about how to think about that type of problem.
Thank you!
I'm also amused by your choice of 'o' and 'i' as combinators,
considering that I mentioned that I was going to use 0 and 1 bits to
represent them. Way back in my school career I took a typing class in
which we were taught that upper case 'i' and 'o' could be typed
instead of 1 and 0. (My community college was always a bit behind the
technology curve; I'm not actually that old. Yes, my Fortran class
taught me how to use punchcards, even though I've never set hands on a
punchcard reader and never will use one.)
The rest snipped for now... I'm going to try some constructions based
on your and Fokker's work (not his combinator, just the way in which
he derived it) to assure myself that I understand this.
Thank you!
> - Brent
-Billy
sa@dfa.com — 2007-02-06 19:54:22
concatenative@yahoogroups.com wrote on 02/06/2007 02:19:27 PM:
> I'm also amused by your choice of 'o' and 'i' as combinators,
> considering that I mentioned that I was going to use 0 and 1 bits to
> represent them.
i thought it might be subliminal tribute to o[kasak]i.
William Tanksley, Jr — 2007-02-08 00:01:18
My apologies to the many people (I hope) reading this list and hoping
for something useful. This stuff is a LONG way from usefulness. I hope
that it will sharpen our understanding of what it means to be
concatenative; I hope that after I understand this I'll be better
equipped to explain the potential benefits.
For now, just treat this as a puzzle: to be solved if it entertains,
and skipped otherwise.
iepos <
bkerby@...> wrote:
> Also, it
> is certainly possible that a more clever choice of basis could lead
> to smaller constructions.
I chose a different basis which results in shorter constructions for
the primitives we're producing. I think it's universally shorter; my
reason for suspecting that is that your 'o' and 'i' operations have
very asymmetric stack effects, so in general you have to execute a LOT
of 'i's for every 'o'. I also personally found it to be much simpler
to derive results for.
Let
0 = [] [q] [k]
1 = k
In this experiment, I didn't change the sequence of the 'o'
combinator. One interesting (to me) implication is that 'k' is very
exposed -- it's the last operation in both combinators. The other
simple choice would be to define 0 as [] [k] [q]; doing that seems to
result in slightly more complex forms for some primitives, but might
make others much simpler. (I need to work that out in full.) The other
permutations should be interesting as well, but now we're talking
computer work, not human work.
I originally chose 'k' so that the VM only needs to define 2
operations, q and k (rather than having to define q, k, and i). I also
suspect that it'll reduce faster, since there's less asymmetry between
'0' producing stack items and '1' consuming them.
Construct 'k':
1 =
k
Construct 'zap':
01 =
[] [q] [k] k =
[] k =
zap
(A simple 'zap' is very useful. It allows me to easily get at the
functions contained in '0'. It also promises a nice peephole
optimizer, since I have meanings for both "1" and "01"!)
Construct 'q':
0011 =
0 01 1 =
[] [q] [k] zap k =
[] [q] k =
q
Construct '[]':
00101 =
0 01 01 =
0 zap zap =
[] [q] [k] zap zap =
[]
Construct 'i':
00101 0011 1 =
[] q k =
i
Construct 'unit':
00101 0011 01 =
[] q zap =
unit
Construct 'nip':
00101001101 1 =
unit k =
nip
Construct 'swat':
0011 001010011011 =
q nip
> [] == oooooiiiiiiioooooiiiiiiii
[] = 00101
> [k] == oooooiiiiiiioooooiiiiiiioooooiiiiiiiioii
[k] = 0 nip nip ==
0 001010011011 001010011011
(That's 26 bits for the k system, versus 41 when using 'i'. This is
the closest thing to a tie.)
> unit == oooooiiiiiiioooooiiiiiiiioioooooiiiiiiii
unit == 00101001101
> swat ==
> oioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooooiiiiiiioooo
> oiiiiiiiioiii
swat == 0011001010011011
> [q] ==
> ooooooiiiiiiiioooooiiiiiiioooooiiiiiiiioioooooiiiiiiiioooooiiiiiiioooo
> oiiiiiiioooooiiiiiiiioiii
[q] = 0 zap nip ==
0 01 001010011011
Seems like I had a good intuition. Balance them combinators!
I still need to explore the effect of using cake instead of q. I also
need to (just as an exercise) express 'dip' and 'swap' in this system.
So far I haven't (I've tried...).
> - Brent
-Billy
iepos — 2007-02-08 03:34:57
> I chose a different basis which results in shorter constructions for
> the primitives we're producing.
Wow! That's much better. Nice work.
> I think it's universally shorter;
Well, what exactly do you mean by that? There's certainly one
combinator which is shorter in my {o,i}, namely "i". But there
probably aren't too many more :-) Perhaps only finitely many. That
would be an interesting question ...
> I still need to explore the effect of using cake instead of q.
Well, I can show you that {[] [cake] [k], k} is incomplete (and the
choice of total dequoter "k" is irrelevant to the following argument,
as is the order of the 3 quotations in 0). It is impossible to
construct cat. Why? Well, notice that in the right side of the
rewrite rule for "cat", there is a quotation containing two non-
quoted terms:
[B] [A] cat == [B A]
But if we start with the stack "[B] [A]" and execute only a sequence
of 0's and 1's (i.e., [] [cake] [k], or k), at each step the property
will be preserved that each quotation contains at most one non-quoted
term. This is because "cake" and "k" both preserve this property, as
we can see from their rewrite rules:
[B] [A] cake == [[B] A] [A [B]]
[B] [A] k == A
Assuming "A" and "B" each contain at most one non-quoted term (and
that, if they contain quotations or subquotations, these also contain
at most non-quoted term each), the same will hold for the right-hand-
side of both rewrite rules. So it is impossible to construct "cat".
Now, to be clear, I'm not claiming that "cat" is inconstructible in
every basis expressed in terms of "cake" and "k". For example, let
0 = [] [cake] [k k]
1 = k
Then {0,1} is a complete flat basis (albeit a much uglier one than
the one you've just given). Construct
zapk: 01 (i.e., zapk == zap k == x\ y\ z\ y )
== [] [cake] [k k] k
== [] k k
== zap k
cake: 001
== 0 01
== 0 zap k
== [] [cake] [k k] zap k
== [] [cake] k
== cake
zap: 000 cake zapk k zapk
== 00 [] [cake] [k k] cake zap k k zap k
== 00 [] [[cake] k k] [k k [cake]] zap k k zap k
== 00 [] [[cake] k k] k k zap k
== 00 [cake] k k k zap k
== 0 [] [cake] [k k] [cake] k k k zap k
== 0 [] [cake] cake k k zap k
== 0 [[] cake] k k zap k
== [] [cake] [k k] [[] cake] k k zap k
== [] [cake] [] cake k zap k
== [] [[cake]] [[cake]] k zap k
== [] [cake] zap k
== [] k
== zap
[]: 0 zap zap
== [] [cake] [k k] zap zap
== [] [cake] zap
== []
unit: [] cake zap
[A] [] cake zap
== [[A]] [[A]] zap
== [[A]]
nip: unit k (as in your construction)
[cake]: 0 zap nip
== [] [cake] [k k] zap nip
== [] [cake] nip
== [cake]
cons: cake zap
[B] [A] cake zap
== [[B] A] [A [B]] zap
== [[B] A]
dip: cake k
[B] [A] cake k
== [[B] A] [A [B]] k
== A [B]
swap: unit dip
[B] [A] unit dip
== [B] [[A]] dip
== [A] [B]
i: [] swap k
[A] [] swap k
== [] [A] k
== A
take: cake nip
[B] [A] cake nip
== [[B] A] [A [B]] nip
== [A [B]]
swat: [] swap take take [] swap 0 nip nip cons cons
[B] [A] [] swap take take [] swap 0 nip nip cons cons
== [B] [] [A] take take [] swap 0 nip nip cons cons
== [B] [A []] take [] swap 0 nip nip cons cons
== [A [] [B]] [] swap 0 nip nip cons cons
== [] [A [] [B]] 0 nip nip cons cons
== [] [A [] [B]] [] [cake] [k k] nip nip cons cons
== [] [A [] [B]] [] [k k] nip cons cons
== [] [A [] [B]] [k k] cons cons
== [] [[A [] [B]] k k] cons
== [[] [A [] [B]] k k]
== [A [] [B] k]
== [A B]
[k]: 0 nip cons [] swap cons
== [] [cake] [k k] nip cons [] swap cons
== [] [k k] cons [] swap cons
== [[] k k] [] swap cons
== [] [[] k k] cons
== [[] [] k k]
== [k]
We've constructed [], [cake], [k], "swat", "unit", and "i", so that
implies completeness. (But note that we had to assume transparent
quotation in the last two constructions). The reason the above
argument does not apply here is that [k k], in the basis combinator
0, is a quotation containing more than one non-quoted term; so the
initial assumption of the argument is not satisfied.
> I also need to (just as an exercise) express 'dip' and 'swap' in
this system.
If you still want the exercise, close this message now. I also wanted
the exercise, so I'm going to spoil it below :-)
(lines intentionally left blank)
(lines intentionally left blank)
(lines intentionally left blank)
(lines intentionally left blank)
So, the (non-flat) construction for dip is
dip == unit [unit] swat i swat i
Putting things in terms of {q,k} (recalling that "swat i" == "q k")
and flattening, we get:
dip == [] q zap [[] q zap] q k q k
== [] q zap [[] q [] k] q k q k
== [] q zap [k] [[] q []] swat q k q k
== [] q zap [k] [[]] [[] q] swat swat q k q k
== [] q zap [k] [[]] [q] [[]] swat swat swat q k q k
== [] q zap [k] [] unit [q] [] unit swat swat swat q k q k
== 00101 0011 01 0001010011011001010011011 00101 00101001101
001001010011011 00101 00101001101 0011001010011011 0011001010011011
0011001010011011 0011 1 0011 1
==
0010100110100010100110110010100110110010100101001101001001010011011001
0100101001101001100101001101100110010100110110011001010011011001110011
1 (141 bits)
Then, the easiest way to get swap is via the construction
swap == unit dip
Of course, if you could construct swap first some other way, then you
could use the construction
dip == swap unit cat i
== swap unit swap swat i
== swap unit swap q k
to get dip; but I doubt that this is helpful, because "swap" is
probably more complicated to construct than "dip". At least, in the
non-flat case, the minimal construction of "swap" in terms of {q,k},
according to a computer search (at least, according to my memory -- I
seem to have accidentally overwritten the log file, and this one took
quite a while to run), is
[] q [] k [] q [] k [[] q [] k] q k q k
which is just the minimal construction of "unit" concatenated with
the minimal construction of "dip", so that "unit dip" really is the
minimal way to construct swap in this situation. Of course, it's
certainly possible that this could change when we switch to the flat
basis {0,1}.
By the way, I said "the minimal", but there were actually some other
solutions of equal size; I didn't take the time to look at them all,
but they mostly seemed to be trivial varients based on the equivalence
[A] k == [] k A
(which, in fact, could be useful to help flatten out expressions over
{q,k} without introducing as many "swat"'s).
> > - Brent
>
> -Billy
>
- Brent
stevan apter — 2007-02-08 23:01:42
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
>
> Construct 'i':
> 00101 0011 1 =
> [] q k =
> i
>
i think this should be
00101 0011 1 1 =
[] q k k
i've posted an interpreter for 01 at:
http://www.nsl.com/k/01.k
William Tanksley, Jr — 2007-02-09 04:54:14
stevan apter <
sa@...> wrote:
> > Construct 'i':
> > 00101 0011 1 =
> > [] q k =
> > i
> i think this should be
> 00101 0011 1 1 =
> [] q k k
[A] [] q k k =
[[A]] [A] k k =
A k
Too many k's.
What might be messing things up is how you treat the [A B] term in the
result of 'q'. In this quotation, [A] is [], which means that A must
be nothing. It's kind of (severely) wierd, but that's how it works.
Does your interpreter act that way?
> i've posted an interpreter for 01 at:
> http://www.nsl.com/k/01.k
You are amazing. :-)
-Billy
iepos — 2007-02-09 08:28:15
Billy & all,
I hacked at my old Joy searcher for a while and was at last able to
persuade it to deal with improper combinators; so I've been able to
determine some minimal constructions for the basis we're looking at,
i.e., {o,k} where
o == [] [q] [k]
and
[B] [A] q == [[B]] [A B]
[B] [A] k == A
So, it turns out most of the constructions you gave are minimal. An
improvement was possible only for [q] (from 15 to 8 bits) and [k]
(from 25 to 18 bits). Here are all minimal constructions for q, [],
i, unit, nip, swat, [q], and [k]:
q == ookk ( == o zap k, same as your construction)
[] == ookok ( == o zap zap, same as your construction)
i == ookokookkk ( == [] q k, same as your construction)
== ookoookkkk
unit== ookokookkok ( == [] q zap, same as your construction)
== ookoookkkok
nip == ookokookkokk ( == unit k, same as your construction)
== ookoookkkokk
swat== ookkookokookkokk (== q nip, same as your construction)
== ookkookoookkkokk
[q] == oookkokk ( == o q zap k)
[k] == oookokookkookkokkk ( == o [] q q zap k k)
== oookoookkkookkokkk
The varients are all due to the equivalence
okookk == oookkk == zap q
The improvements on [q] and [k] are actually interesting. The
original construction for [q] was
[q] == o zap nip
== o zap unit k
== o zap [] q zap k
Notice that in the construction
unit == [] q zap
the empty program is only used as a junk element; any other element
works just as well:
[A] [junk] q zap
== [[A]] [junk A] zap
== [[A]]
So, in the construction for [q], we might as well leave [k] alone
and use it as our junk element, rather than zapping it and pushing
[]. Therefore, we can delete "zap []" from the construction. Compare:
o zap [] q zap k
== [] [q] [k] zap [] q zap k
== [] [q] [] q zap k
== [] [[q]] [q] zap k
== [] [[q]] k
== [q]
o q zap k
== [] [q] [k] q zap k
== [] [[q]] [k q] zap k
== [] [[q]] k
== [q]
Now let's look at [k]. The original construction was
[k] == o nip nip
== o unit k unit k
Notice that "unit unit k k" also works as an implementation of "nip
nip":
[C] [B] [A] unit unit k k
== [C] [B] [[A]] unit k k
== [C] [B] [[[A]]] k k
== [C] [[A]] k
== [A]
So we have
[k] == o unit unit k k
== o [] q zap [] q zap k
And once again we can delete the unneeded "zap []" (for the same
reason as with [q]) to get
[k] == o [] q q zap k
which is the minimal construction.
I've tried searching for minimal constructions of "dip" and "swap"
but without success; I can say that "dip" has size at least 33
and "swap" has size at least 35. But I would guess that the minimal
constructions are much larger than this, so it's probably useless to
continue searching in a brute-force manner (although technically
it's not quite brute-force; I did implement a sort of backtracking
algorithm for flat constructions, which helps speed things up a bit).
I also did some experimenting with different bases. Remarkably, all
five other bases obtained from {o,k} by changing the order of the
three quotations in "o" are flat complete. Here are the
constructions (for the sake of conciseness, I'll just choose one
representative when there are multiple minimal constructions):
o := [] [k] [q]
[] == oookkokkk
[q] == ookokokkokkkk
[k] == ookkokokk
i == okk
unit== okoookkokkkk
swat== ookokkkokookkokokkk
o := [q] [] [k]
[] == oookkoookkokkk
[q] == ooookkookkokkk
[k] == ooookkokkookkk
i == oookkokkk
unit== ookoookkookkkk
swat== ookkoookokookkkk
o := [k] [] [q]
[] == ooookokookkkkkokk
[q] == ooookokkkkokk
[k] == ooookokookkkkkk
== ooookokkokkokkk
i == oookkokkk
unit== oookokkkk
swat== oookokkokokkkk
o := [q] [k] []
[] == ooookkookkkokkk
[q] == ok
[k] == ooookkkoookkkkk
i == oookkkoookkkokkkk
unit== oookkoookokkokkookkkkk
swat== okokkookkookoookkkkkk
o := [k] [q] []
[] == ooookkkookkokkk
[q] == oookkokk
[k] == ok
i == oookkkoookkookkkkkk
unit== okooookkkookkkk
swat== ookkoookkkokk
Also, it turns out that my original base {o,i} isn't as bad as it
first appeared; here are the minimal constructions over it:
[] == oooiiioooiiiiii
[q] == ooioooiioiioiiii
[k] == oooiioiii
unit== ooiioooiiiii
swat== oiooiioooiioiioiiii
And the basis {[k] [q] [],i} also turns out to be complete and has
fairly simple constructions:
o := [k] [q] []
[] == ooiiioiii
[q] == ooioiiiiiiii
[k] == ooiiii
unit== oiiooiiioiiioiiii
swat== oooiioiiioiiooiioiii
The other four bases obtained from {o, i} by changing the order of
the quotations in "o" appear to be incomplete, although I'm not
certain except in the case {[q] [] [k], i}, which is definitely
incomplete since "oi" is the empty program.
A couple other interesting bases arise from a new combinator, call
it "h", defined
[B] [A] h == [[A B]] [B]
which forms a complete (non-flat) basis with "k", as evidenced by
the constructions
i == [] h k
unit == [] h [] k
swat == h h k
dup == [] h unit swat i
Then {[] [h] [k], k} and {[] [k] [h], k} are complete flat bases:
o := [] [h] [k]
[] == ookok
[h] == ookookkookkk
[k] == ooookkkokoookkkokkk
i == oookkkk
unit == oookkkok
swat == ookkookkk
o := [] [k] [h]
[] == ookkokokkk
[h] == ookookokkkokookokkkkk
[k] == ookkokkokk
i == okk
unit == okookokkk
swat == ookookokkkkkookokkkokk
In the end, from what I can see, none of these alternative bases
offer significant improvement over your {o,k}, which is one of the
best in terms of yielding small constructions of the combinators
we're looking at. It looks like your intuition served you well
indeed!
- Brent
stevan apter — 2007-02-09 12:54:42
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Thursday, February 08, 2007 11:54 PM
Subject: Re: [stack] Re: Concatenative macros?
> stevan apter <sa@...> wrote:
> > > Construct 'i':
> > > 00101 0011 1 =
> > > [] q k =
> > > i
>
> > i think this should be
> > 00101 0011 1 1 =
> > [] q k k
>
> [A] [] q k k =
> [[A]] [A] k k =
> A k
>
> Too many k's.
>
> What might be messing things up is how you treat the [A B] term in the
> result of 'q'. In this quotation, [A] is [], which means that A must
> be nothing. It's kind of (severely) wierd, but that's how it works.
> Does your interpreter act that way?
it does now. that wasn't at all clear (to me) from the description of 'q'.
[B] [A] q == [[B]] [A B]
shouldn't that be
[B] [A] q == [[B]] [A B] if A is not []
[[B]] B if A is []
?
did i read right past that in brent's original explanation?
O["";"[1][0]q"]
[[1]][[0][1]]
O["";"[1][]q"]
[[1]][1]
O["";"[][0]q"]
[[]][[0][]]
do i have this right, or should B = [] produce analogous
behavior?
in any case, kudos to both you and brent. this is fascinating.
>
> > i've posted an interpreter for 01 at:
> > http://www.nsl.com/k/01.k
>
> You are amazing. :-)
>
> -Billy
>
William Tanksley, Jr — 2007-02-09 15:25:56
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > What might be messing things up is how you treat the [A B] term in the
> > result of 'q'. In this quotation, [A] is [], which means that A must
> > be nothing. It's kind of (severely) wierd, but that's how it works.
> > Does your interpreter act that way?
> it does now. that wasn't at all clear (to me) from the description of 'q'.
> [B] [A] q == [[B]] [A B]
> shouldn't that be
> [B] [A] q == [[B]] [A B] if A is not []
> [[B]] B if A is []
> ?
This is one of the things that confuses me about this notation -- but
it's something you have to learn. The reason it's confusing to us is
that it's a purely functional notation, and we're used to thinking
procedurally. You're especially in danger of that, since you're using
a concrete implementation in order to learn about it.
In this case, we think procedurally when we use the word "dequote" to
mean "execute now". What it actually means is "insert the semantics
that are quoted inside this list directly into this context."
I'm taking a long time to get to the point. Let me take a break to
give an example.
> [B] [A] q == [[B]] [A B] if A is not []
> [[B]] B if A is []
Well, first, the second part is a typo -- you probably meant to type
"[[B]] [B]". Second, though, and this is the important part, in this
notation the term "A" doesn't mean "the top item on the stack". It
means "the semantics which are quoted inside the top item on the
stack."
> did i read right past that in brent's original explanation?
> O["";"[1][0]q"]
> [[1]][[0][1]]
> O["";"[1][]q"]
> [[1]][1]
> O["";"[][0]q"]
> [[]][[0][]]
I can't read this notation; sorry.
> do i have this right, or should B = [] produce analogous
> behavior?
Precisely so -- "B" means "the semantics quoted inside the second item
on the stack". If [B] == [], that means there are no semantics quoted
inside the second item on the stack.
So these things are not a special case; they're normal behavior.
> in any case, kudos to both you and brent. this is fascinating.
Thank you -- and a HUGE thank you to Brent, who's at last made this
all make sense to me. This is exciting to me, since I've been puzzled
by it for so long.
I've decided (tentatively) that my next goal is to build a basis in
which swap is easier to express. I don't think that'll be the last
basis I construct :-), but I'm just not happy with the extreme
imbalance between how easy it is to nip and how hard it is to swap.
I know there will always be tradeoffs; but I want to learn how to make
them wisely. I have a very strong sense that some of these bases are
FAR easier to work with than others, so I'm confident that there's
much room for improvement.
> > > i've posted an interpreter for 01 at:
> > > http://www.nsl.com/k/01.k
I wrote a Python interpreter, although I didn't even try to run it, so
it's probably severely broken. (My purpose was to explain this to a
fellow programmer who doesn't know anything about concatenativity or
flatness or mathematics; I succeeded, since he wrote back with a bunch
of derivations.) Does anyone want to see it? It's not that many lines
long.
-Billy
sa@dfa.com — 2007-02-09 16:37:57
concatenative@yahoogroups.com wrote on 02/09/2007 10:25:56 AM:
> stevan apter <sa@...> wrote:
[:]
>
> > [B] [A] q == [[B]] [A B]
>
> > shouldn't that be
> > [B] [A] q == [[B]] [A B] if A is not []
> > [[B]] B if A is []
> > ?
>
> This is one of the things that confuses me about this notation -- but
> it's something you have to learn. The reason it's confusing to us is
> that it's a purely functional notation, and we're used to thinking
> procedurally. You're especially in danger of that, since you're using
> a concrete implementation in order to learn about it.
>
> In this case, we think procedurally when we use the word "dequote" to
> mean "execute now". What it actually means is "insert the semantics
> that are quoted inside this list directly into this context."
>
> I'm taking a long time to get to the point. Let me take a break to
> give an example.
[:]
>
> Precisely so -- "B" means "the semantics quoted inside the second item
> on the stack". If [B] == [], that means there are no semantics quoted
> inside the second item on the stack.
>
> So these things are not a special case; they're normal behavior.
my confusion was purely notational: i didn't realize that "A B"
meant (what i would write as) "A^B", although the left-hand-side of
the rule should have clued me in.
i notice that robbert also favors a rewrite-rule style for his
exposition of enchilada. and he too is always correcting me on
this matter!
>
> > in any case, kudos to both you and brent. this is fascinating.
>
> Thank you -- and a HUGE thank you to Brent, who's at last made this
> all make sense to me. This is exciting to me, since I've been puzzled
> by it for so long.
yes, i find his contributions uniquely valuable, indispensable to
understanding this terrain. thank you brent.
>
> I've decided (tentatively) that my next goal is to build a basis in
> which swap is easier to express. I don't think that'll be the last
> basis I construct :-), but I'm just not happy with the extreme
> imbalance between how easy it is to nip and how hard it is to swap.
>
> I know there will always be tradeoffs; but I want to learn how to make
> them wisely. I have a very strong sense that some of these bases are
> FAR easier to work with than others, so I'm confident that there's
> much room for improvement.
onward. i'll be with the baggage, in the rear.
>
> > > > i've posted an interpreter for 01 at:
> > > > http://www.nsl.com/k/01.k
>
> I wrote a Python interpreter, although I didn't even try to run it, so
> it's probably severely broken. (My purpose was to explain this to a
> fellow programmer who doesn't know anything about concatenativity or
> flatness or mathematics; I succeeded, since he wrote back with a bunch
> of derivations.) Does anyone want to see it? It's not that many lines
> long.
yes, by all means.
as i mentioned to you privately a few days ago, i wrote the interpreter
as a preliminary step to experimenting with a genetic algorithm (to find
programs.) as you pointed out at the beginning of this discussion,
programs constructed in a flat, two-element language seem tailor-made
for recombination operations.
01.k contains inner and outer interpreters. the inner interpreter
evaluates and produces binary sequences. the outer interpreter takes
strings using a vocabulary (e.g. zap, i, unit, &c.), deconstructs them
into binary sequences, invokes the inner interpreter, then constructs
strings in the vocabulary from the result.
>
> -Billy
>
William Tanksley, Jr — 2007-02-09 18:47:13
iepos <
bkerby@...> wrote:
> > I chose a different basis which results in shorter constructions for
> > the primitives we're producing.
> Wow! That's much better. Nice work.
Thanks, but obviously it builds on your work -- you actually know what
you're doing, and you get all the credit for making it make sense.
I suspect that this language is more easily explained than any of the
unlambda-ish competitors. In theory, it might be nice that each
element of the language stands alone, and any substring of any program
can be understood in isolation, and it means exactly the same thing in
context, no matter what the context is.
(In practice, a real language would have to define a data convention,
so there would be a difference between data and code.)
I sent a Python implementation (of your first version of the language)
to a friend who knows Forth but no math (a pure electronic engineer
type), and he responded with a series of derivations (although he
wasn't really interested in the language and in fact some of his
derivations were incorrect, he definitely proved that he understood
it).
> > I think it's universally shorter;
> Well, what exactly do you mean by that? There's certainly one
> combinator which is shorter in my {o,i}, namely "i". But there
> probably aren't too many more :-) Perhaps only finitely many. That
> would be an interesting question ...
That's what I meant, yes. I don't know a precise way of asking the
question; I've seen that type of assertion made in math, but I don't
remember how it was expressed. It's also possible that in that
particular case there's no way to express what I meant (but you know
what I mean).
Anyhow, I found my {01} basis to be far easier to derive things for
than your {oi} basis. I suspect there's a reason for that. I also
found my basis to be very hard to express stack reorderings in, and I
suspect I know a reason for that. I want to see how *good* of a basis
I can possibly construct.
> > I still need to explore the effect of using cake instead of q.
> Well, I can show you that {[] [cake] [k], k} is incomplete (and the
> choice of total dequoter "k" is irrelevant to the following argument,
Very nice. You just saved me a lot of time. And, to boot, gave me a
good example of reasoning. Well, more accurately, you caused me to
spent my time looking at good reasoning instead of trying to create my
own bad reasoning.
> > I also need to (just as an exercise) express 'dip' and 'swap' in
> > this system.
> If you still want the exercise, close this message now. I also wanted
> the exercise, so I'm going to spoil it below :-)
I tried, I failed. Your path to a solution is more prudent than mine.
> to get dip; but I doubt that this is helpful, because "swap" is
> probably more complicated to construct than "dip". At least, in the
That was my conclusion as well.
I'm still exploring basises (bases? basi?). I know there's no
perfection, only tradeoffs, but I also suspect that some are much
worse than others, and I have no theoretical basis for believing that
I've found the "best".
> - Brent
-Billy
William Tanksley, Jr — 2007-02-09 19:10:00
sa@... <
sa@...> wrote:
> concatenative@yahoogroups.com wrote on 02/09/2007 10:25:56 AM:
> > I wrote a Python interpreter, although I didn't even try to run it, so
> > it's probably severely broken. (My purpose was to explain this to a
> yes, by all means.
Included at the end of this post.
> as i mentioned to you privately a few days ago, i wrote the interpreter
> as a preliminary step to experimenting with a genetic algorithm (to find
> programs.) as you pointed out at the beginning of this discussion,
> programs constructed in a flat, two-element language seem tailor-made
> for recombination operations.
Indeed.
Although I'm also interested in genetic systems, my main interest is
in understanding languages for use by humans. I'm not certain
(although I can sometimes hope) that perfectly flat languages will
ever be usable by humans (we and the people who write in Unlambda are
NOT humans, sorry), but I'm certain that I'm increasing my
understanding of languages :-).
> 01.k contains inner and outer interpreters. the inner interpreter
> evaluates and produces binary sequences. the outer interpreter takes
> strings using a vocabulary (e.g. zap, i, unit, &c.), deconstructs them
> into binary sequences, invokes the inner interpreter, then constructs
> strings in the vocabulary from the result.
Of course, the "outer interpreter" could also be implemented as a
"compiler" and "decompiler". I think this is a useful result of
flatness: any string always means the same thing, regardless of
context. (Of course, this also means that decompilations are not
unique.)
-Billy
-------- the "ok" 01 interpreter (untested):
def q(stack):
a = stack.pop()
b = stack.pop()
stack.push( [[b]] )
stack.push( [a, b] )
return stack
def one(stack): # K combinator
a = stack.pop()
b = stack.pop() # throw away
return Execute(a, stack)
def zero(stack):
stack.push( list() )
stack.push( list(q) )
stack.push( list(one) )
# It's impossible to Execute anything that's not a list.
def Execute(fn, stack):
for elem in fn:
if elem instanceof list: stack.push(elem)
else elem(stack)
# The heart of the system:
bits = raw_input("Input a string of 0s and 1s: ")
stack = []
for bit in bits:
if bit == '0': zero(stack)
else: one(stack)
print stack
William Tanksley, Jr — 2007-02-09 19:12:38
iepos <
bkerby@...> wrote:
> I hacked at my old Joy searcher for a while and was at last able to
> persuade it to deal with improper combinators; so I've been able to
> determine some minimal constructions for the basis we're looking at,
> i.e., {o,k} where
Okay; and then you posted it where? :-)
Let me get my credit card.
-Billy
stevan apter — 2007-02-09 22:02:30
i would be extremely interested in reading a description
of the algorithm.
(my dog ate my credit card)
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, February 09, 2007 2:12 PM
Subject: Re: [stack] Re: Flat concatenative basis (was: Concatenative macros?)
> iepos <bkerby@...> wrote:
> > I hacked at my old Joy searcher for a while and was at last able to
> > persuade it to deal with improper combinators; so I've been able to
> > determine some minimal constructions for the basis we're looking at,
> > i.e., {o,k} where
>
> Okay; and then you posted it where? :-)
>
> Let me get my credit card.
>
> -Billy
>
Brent L Kerby — 2007-02-09 22:56:20
> Okay; and then you posted it where? :-)
Oh, yeah, I forgot to mention that. It's at
http://www.tunes.org/~iepos/joys.zip (it's linked from the article "Theory of Concatenative Combinators"); I overwrote the old version with the new version. The C source code is included, although it's very unreadable (sorry about that). I meant to include an updated README, but it looks like I've misplaced the file. The basic difference is that if you want to search only for flat constructions, place an underscore ("_") on a line by itself anywhere in the "goal" file. And, to support the use of improper combinators in the basis, you may declare auxiliary combinators (which will not be included in the basis) at the beginning of the "goal" file and separate them from the others by putting a "." on a line by itself. The goal combinator is marked by an asterisk ("*") and may be placed anywhere in the file (whereas the older version always required the goal to be the first line); but it must occur after any combinators it references (so, if you're searching for "[q]", it should come after the definition of "q"); it's fine to always put it at the end.
For example, to search for constructions of "swat" over the basis {o, k} where o == [] [q] [k], use this for the "goal" file:
_
2q [[1]][01]
.
2k 0
0o [][q][k]
2* [01]
Oh, by the way, the searcher assumes opaque quotation because this was the easiest to implement; years ago I partially implemented transparent quotation (activated by uncommenting the line "#define LIVEQUOTES") but the code for it is broken, so I don't recommend using it.
Enjoy!
> -Billy
- Brent
Brent L Kerby — 2007-02-10 03:31:16
> i would be extremely interested in reading a description
> of the algorithm.
It basically works by trying all programs of size 0 (There aren't too many of these :-) ), then all programs of size 1, and so forth, testing each program by executing it to see if it generates the desired effect. There's a limit (the constant "TOOLONG" in my implementation) as to how many steps it spends on any one program; this is necessary to prevent it from freezing when it encounters a non-terminating program (of which, by the way, in {o,k}, there are none of size 34 or less; I have yet to find the smallest one). Of course, in theory, this could cause the searcher to miss possible solutions, since in general there is no way to tell whether an apparently non-terminating program really is non-terminating (the Halting Problem, the canonical problem which a Turing machine cannot solve), or whether it might not eventually yield the desired construction after a very long time. My searcher makes an announcement the first time it first finds an apparently non-terminating program, so that you know that there could be omitted solutions. For practical purposes, we're probably not really interested in constructions that have extremely long run times anyway.
In the case of flat constructions, I implemented a (partial) backtracking algorithm so that if a program generates an error (i.e., a stack underflow) at a certain point, then that whole branch of the search space will be skipped. So, for example, when we search for a construction of "i" over the basis {o,k}, at some point the program "koooo" will be tested which will generate a stack underflow in the very first instruction (since only 1 stack item is available and "k" needs 2), so that the subsequent programs "koook", "kooko", "kookk", ..., "kkkkk" will be entirely skipped.
I say that it's only a partial implementation of backtracking because each program still gets tested from scratch. My implementation does not use recursion or dynamic memory allocation; instead, there is both a data stack and a code "stack" (the data stack grows up while the code stack grows down), each implemented as a simple array of fixed maximum size. I'm pretty sure this is not the best way to do it. Each quotation requires a memcpy() (of size equal to the length of the quotation) from the code stack to the data stack, while execution (i.e., dequoting) likewise requires a memcpy() from the data stack to the code stack. If I were doing it again, I would allocate quotations dynamically and reference them by pointers to eliminate the need for this deep copying, especially considering that fully implementing backtracking would otherwise require making a copy of the stack at each level of the recursion. So we should implement stacks/quotations using lists, or better yet, trees, which generally we will never modify, only newly create. Trees are preferable to lists, so that, for example, we can implement q == A\ B\ [[B]] [A B], in constant time; with lists, a copy, albeit a shallow copy, is needed to form the concatenation "A B", and this is potentially problematic, as I'll show below.
There's no reason why "dup" (or "q") actually needs to duplicate anything more than a pointer. In a real implementation of the system, this would necessitate garbage collection, but in a searcher this is unnecessary, since individual programs do not run long enough to generate a significant amount of garbage (and since we want to be able to backtrack, even the "garbage" isn't garbage to us). In a recursive implementation of the searcher, everything new that is created should be freed on the way out of the recursion, so that special garbage collection, i.e., reference counting, mark&sweep, etc., is unnecessary.
Now, there are "busy beaver" programs which can generate an obscenely large amount of data in only a very small amount of code (the maximum amount generated grows so fast as a function of code length that it is incomputable; that means that in the end, it grows faster than any function you can describe, worse than exponential or even Ackermann functions); and of course, non-terminating programs could potentially generate an unbounded amount of data. For instance,
[] [[dup cons] dip dup i] dup i
is a non-terminating program that takes up stack space exponential to the amount of time you let it run. In general,
[[P] dip dup i] dup i
is an infinite loop that runs "P" over and over again unconditionally:
[[P] dip dup i] dup i
== [[P] dip dup i] [[P] dip dup i] i
== [[P] dip dup i] [P] dip dup i
== P [[P] dip dup i] dup i
== P P P P P P ...
So then
[] [[dup cons] dip dup i] dup i
== [] dup cons dup cons dup cons dup cons ...
== [] [] cons dup cons dup cons dup cons ...
== [[]] dup cons dup cons dup cons dup cons ...
== [[]] [[]] cons dup cons dup cons dup cons ...
== [[[]][]] dup cons dup cons dup cons ...
== [[[]][]] [[[]][]] cons dup cons dup cons ...
== [[[[]][]]][[]][]] dup cons dup cons ...
== [[[[]][]]][[]][]] [[[[]][]]][[]][]] cons dup cons ...
== [[[[[]][]]][[]][]][[[]][]]][[]][]] dup cons ...
== ...
My Joy searcher would likely crash if it encounters such a program. That's not a good thing. But an efficient Joy searcher would implement "dup" by copying references, not by a deep copy, so that then the amount of space a program uses is bounded linearly by the length of time it is allowed it to run, which makes space requirements trivial. Another example that is even worse than the one above is
== [[]] [[dup cat] dip dup i] dup i
== [[]] dup cat dup cat dup cat dup cat ...
== [[]] [[]] cat dup cat dup cat dup cat ...
== [[] []] dup cat dup cat dup cat ...
== [[] []] [[] []] cat dup cat dup cat ...
== [[] [] [] []] dup cat dup cat ...
== [[] [] [] []] [[] [] [] []] cat dup cat ...
== [[] [] [] [] [] [] [] []] dup cat ...
== [[] [] [] [] [] [] [] []] [[] [] [] [] [] [] [] []] cat ...
This one is worse because it will thwart a system that assumes that shallow copies are cheap; that's why I'd suggest using trees. Using balanced trees might be helpful, but it is probably unnecessary, since the maximum depth of any tree is no larger than the number of steps we allow the program to run (which should be fairly small), times a small constant (normally 1 or 2) which depends on the choice of basis.
Okay, so thus far this has been more of a description of how I should have written the searcher, and not how I actually did :-) But I'll explain one thing that I think I did right that could be a bit subtle. Prior to testing each program, the stack is arranged with a number of quotations of distinct special objects which I'll call indeterminates. For example, if you're searching for "dip", the goal line will look like
2* 0[1]
and two indeterminates (referred to as "0" and "1", "0" the top one) will be pushed prior to each test. When one of these indeterminates is executed, it is stored (in dequoted form) on the "data stack" just like quotations. Thus, you may think of the "data stack" as more of a history than of a stack in the literal sense. In one sense, a dequoted indeterminate is a brick wall in the history, in that attempting to look past one will generate a stack underflow, regardless of whether there are quotations beyond it.
Anyhow, back to optimization strategies ... Currently, the only condition which causes the searcher to backtrack is a stack underflow. But there are other conditions which should also trigger this:
1. Whenever a program appears to be non-terminating.
2. Whenever an indeterminate is executed and the history/"data stack" does not precisely match the first part of the goal combinator.
3. Whenever last copy of an indeterminate that is still needed is destroyed. (This is potentially more expensive to check; perhaps the set of referenced indeterminates could be built into the data structure for quotations/stack).
Another optimization would be to build an exhaustive table of small constructions and find out which ones are equivalent. Then from each equivalence class, choose one representative and prohibit all others in the construction (Backtrack if one occurs). For example, in {o,k} we found that
okookk == oookkk == zap q
Therefore, to speed things up, we should choose "okookk" and prohibit "oookkk", or vice versa. Under certain bases and sufficiently large table size, it is possible that in building the table we may encounter some (apparently) non-terminating programs; if this happens, we should prohibit them entirely.
- Brent
stevan apter — 2007-02-11 00:02:29
thanks brent
as usual, work that you consider throw-away contains more insights than can fit in a standard
published article, much less the margins of one.
----- Original Message -----
From: "Brent L Kerby" <bkerby@...>
To: <concatenative@yahoogroups.com>
Sent: Friday, February 09, 2007 10:31 PM
Subject: Re: Re: [stack] Re: Flat concatenative basis (was: Concatenative macros?)
> i would be extremely interested in reading a description
> of the algorithm.
It basically works by trying all programs of size 0 (There aren't too many of these :-) ), then all programs of size 1, and so
forth, testing each program by executing it to see if it generates the desired effect. There's a limit (the constant "TOOLONG" in my
implementation) as to how many steps it spends on any one program; this is necessary to prevent it from freezing when it encounters
a non-terminating program (of which, by the way, in {o,k}, there are none of size 34 or less; I have yet to find the smallest one).
Of course, in theory, this could cause the searcher to miss possible solutions, since in general there is no way to tell whether an
apparently non-terminating program really is non-terminating (the Halting Problem, the canonical problem which a Turing machine
cannot solve), or whether it might not eventually yield the desired construction after a very long time. My searcher makes an
announcement the first time it first finds an apparently non-terminating program, so that you know that there could be omitted
solutions. For practical purposes, we're probably not really interested in constructions that have extremely long run times anyway.
In the case of flat constructions, I implemented a (partial) backtracking algorithm so that if a program generates an error (i.e., a
stack underflow) at a certain point, then that whole branch of the search space will be skipped. So, for example, when we search for
a construction of "i" over the basis {o,k}, at some point the program "koooo" will be tested which will generate a stack underflow
in the very first instruction (since only 1 stack item is available and "k" needs 2), so that the subsequent programs "koook",
"kooko", "kookk", ..., "kkkkk" will be entirely skipped.
I say that it's only a partial implementation of backtracking because each program still gets tested from scratch. My implementation
does not use recursion or dynamic memory allocation; instead, there is both a data stack and a code "stack" (the data stack grows up
while the code stack grows down), each implemented as a simple array of fixed maximum size. I'm pretty sure this is not the best way
to do it. Each quotation requires a memcpy() (of size equal to the length of the quotation) from the code stack to the data stack,
while execution (i.e., dequoting) likewise requires a memcpy() from the data stack to the code stack. If I were doing it again, I
would allocate quotations dynamically and reference them by pointers to eliminate the need for this deep copying, especially
considering that fully implementing backtracking would otherwise require making a copy of the stack at each level of the recursion.
So we should implement stacks/quotations using lists, or better yet, trees, which generally we will never modify, only newly create.
Trees are preferable to lists, so that, for example, we can implement q == A\ B\ [[B]] [A B], in constant time; with lists, a copy,
albeit a shallow copy, is needed to form the concatenation "A B", and this is potentially problematic, as I'll show below.
There's no reason why "dup" (or "q") actually needs to duplicate anything more than a pointer. In a real implementation of the
system, this would necessitate garbage collection, but in a searcher this is unnecessary, since individual programs do not run long
enough to generate a significant amount of garbage (and since we want to be able to backtrack, even the "garbage" isn't garbage to
us). In a recursive implementation of the searcher, everything new that is created should be freed on the way out of the recursion,
so that special garbage collection, i.e., reference counting, mark&sweep, etc., is unnecessary.
Now, there are "busy beaver" programs which can generate an obscenely large amount of data in only a very small amount of code (the
maximum amount generated grows so fast as a function of code length that it is incomputable; that means that in the end, it grows
faster than any function you can describe, worse than exponential or even Ackermann functions); and of course, non-terminating
programs could potentially generate an unbounded amount of data. For instance,
[] [[dup cons] dip dup i] dup i
is a non-terminating program that takes up stack space exponential to the amount of time you let it run. In general,
[[P] dip dup i] dup i
is an infinite loop that runs "P" over and over again unconditionally:
[[P] dip dup i] dup i
== [[P] dip dup i] [[P] dip dup i] i
== [[P] dip dup i] [P] dip dup i
== P [[P] dip dup i] dup i
== P P P P P P ...
So then
[] [[dup cons] dip dup i] dup i
== [] dup cons dup cons dup cons dup cons ...
== [] [] cons dup cons dup cons dup cons ...
== [[]] dup cons dup cons dup cons dup cons ...
== [[]] [[]] cons dup cons dup cons dup cons ...
== [[[]][]] dup cons dup cons dup cons ...
== [[[]][]] [[[]][]] cons dup cons dup cons ...
== [[[[]][]]][[]][]] dup cons dup cons ...
== [[[[]][]]][[]][]] [[[[]][]]][[]][]] cons dup cons ...
== [[[[[]][]]][[]][]][[[]][]]][[]][]] dup cons ...
== ...
My Joy searcher would likely crash if it encounters such a program. That's not a good thing. But an efficient Joy searcher would
implement "dup" by copying references, not by a deep copy, so that then the amount of space a program uses is bounded linearly by
the length of time it is allowed it to run, which makes space requirements trivial. Another example that is even worse than the one
above is
== [[]] [[dup cat] dip dup i] dup i
== [[]] dup cat dup cat dup cat dup cat ...
== [[]] [[]] cat dup cat dup cat dup cat ...
== [[] []] dup cat dup cat dup cat ...
== [[] []] [[] []] cat dup cat dup cat ...
== [[] [] [] []] dup cat dup cat ...
== [[] [] [] []] [[] [] [] []] cat dup cat ...
== [[] [] [] [] [] [] [] []] dup cat ...
== [[] [] [] [] [] [] [] []] [[] [] [] [] [] [] [] []] cat ...
This one is worse because it will thwart a system that assumes that shallow copies are cheap; that's why I'd suggest using trees.
Using balanced trees might be helpful, but it is probably unnecessary, since the maximum depth of any tree is no larger than the
number of steps we allow the program to run (which should be fairly small), times a small constant (normally 1 or 2) which depends
on the choice of basis.
Okay, so thus far this has been more of a description of how I should have written the searcher, and not how I actually did :-) But
I'll explain one thing that I think I did right that could be a bit subtle. Prior to testing each program, the stack is arranged
with a number of quotations of distinct special objects which I'll call indeterminates. For example, if you're searching for "dip",
the goal line will look like
2* 0[1]
and two indeterminates (referred to as "0" and "1", "0" the top one) will be pushed prior to each test. When one of these
indeterminates is executed, it is stored (in dequoted form) on the "data stack" just like quotations. Thus, you may think of the
"data stack" as more of a history than of a stack in the literal sense. In one sense, a dequoted indeterminate is a brick wall in
the history, in that attempting to look past one will generate a stack underflow, regardless of whether there are quotations beyond
it.
Anyhow, back to optimization strategies ... Currently, the only condition which causes the searcher to backtrack is a stack
underflow. But there are other conditions which should also trigger this:
1. Whenever a program appears to be non-terminating.
2. Whenever an indeterminate is executed and the history/"data stack" does not precisely match the first part of the goal
combinator.
3. Whenever last copy of an indeterminate that is still needed is destroyed. (This is potentially more expensive to check; perhaps
the set of referenced indeterminates could be built into the data structure for quotations/stack).
Another optimization would be to build an exhaustive table of small constructions and find out which ones are equivalent. Then from
each equivalence class, choose one representative and prohibit all others in the construction (Backtrack if one occurs). For
example, in {o,k} we found that
okookk == oookkk == zap q
Therefore, to speed things up, we should choose "okookk" and prohibit "oookkk", or vice versa. Under certain bases and sufficiently
large table size, it is possible that in building the table we may encounter some (apparently) non-terminating programs; if this
happens, we should prohibit them entirely.
- Brent
William Tanksley, Jr — 2007-02-11 00:27:58
stevan apter <
sa@...> wrote:
> as usual, work that you consider throw-away contains more insights than can fit in a standard
> published article, much less the margins of one.
I'm looking forward to your genetic system -- one would expect that it
would be useful for the same purpose. Perhaps you should tailor a
version of it to accept the same input as Kerby's, so we cant directly
compare them.
Also, Enchilada's tree data structure might be extremely useful for this.
> - Brent
-Billy
Robbert van Dalen — 2007-02-11 11:27:34
Great stuff!
Still, I don't see the need for a flat binary base (except for
extreme simplicity and fun).
Why not allow 4 flat primitives that follow the 4 bases (ACGT) of
DNA? :)
I'm not sure but that may lead to smaller programs.
I also wonder how one can do arithmetics on top of {o,k} without
resorting to Church numerals.
On Feb 11, 2007, at 1:27 AM, William Tanksley, Jr wrote:
> stevan apter <sa@...> wrote:
> > as usual, work that you consider throw-away contains more
> insights than can fit in a standard
> > published article, much less the margins of one.
>
> I'm looking forward to your genetic system -- one would expect that it
> would be useful for the same purpose. Perhaps you should tailor a
> version of it to accept the same input as Kerby's, so we cant directly
> compare them.
>
> Also, Enchilada's tree data structure might be extremely useful for
> this.
If the flat base {o,k} settles to a definite version I would be very
happy to implement it on top of Enchilada's tree structure.
(or provide you guys with the algorithms).
>
> -Billy
>
>
Robbert.
>
William Tanksley, Jr — 2007-02-11 18:45:29
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> Great stuff!
> Still, I don't see the need for a flat binary base (except for
> extreme simplicity and fun).
That's a great reason :-). I'm using it to better understand perfect
flatness, in hopes that I can see whether flatness has any desirable
properties. It's also accidentally making it possible for me to
understand combinators, which I now see that I didn't fully "get".
> Why not allow 4 flat primitives that follow the 4 bases (ACGT) of
> DNA? :)
> I'm not sure but that may lead to smaller programs.
It certainly would; but it would be just that much less flat (you
could only 'cut' programs at every other bit address). Long-term, I'm
likely going to make a 256-base code, and claim that it's flat at the
8-bit byte level. But before I think about that I have to understand
this much simpler system -- 256 bases is a lot to have to choose when
one doesn't know why 2 bases are efficient.
> I also wonder how one can do arithmetics on top of {o,k} without
> resorting to Church numerals.
That's essentially correct, although actually there are other
conventions that will work as well as Church numbers do. As you know,
Enchilada uses one of them (although of course E can see into its
quotations). I haven't bothered choosing one, because I've got so much
else to do.
> > Also, Enchilada's tree data structure might be extremely useful for
> > this.
> If the flat base {o,k} settles to a definite version I would be very
> happy to implement it on top of Enchilada's tree structure.
> (or provide you guys with the algorithms).
Thank you!
> Robbert.
-Billy
William Tanksley, Jr — 2007-02-26 00:12:40
Robbert van Dalen <
robbert.van.dalen@...> wrote:
> Why not allow 4 flat primitives that follow the 4 bases (ACGT) of
> DNA? :)
> I'm not sure but that may lead to smaller programs.
I played with this -- it definitely does make things simpler, since
you don't need to have a "do everything" 'o' combinator; the other
combinators can help supply the needed operators.
Of course, I wasn't imitating ACGT, but was just using 4 bases.
> I also wonder how one can do arithmetics on top of {o,k} without
> resorting to Church numerals.
I haven't bothered trying to find out yet. But another possibility
would be to include a new set of bases especially for handling
numbers. You could even use a separate stack for numbers.
-Billy