----- Original Message -----
From: <iepos@...>
To: <concatenative@egroups.com>
Sent: Saturday, June 03, 2000 8:38 PM
Subject: [stack] joy combinator construction finder
>
> However, there are a few interesting constructions it has found,
> for instance:
>
> [dup] dip == [] cons cons dup call drop swap call
this was driving me nuts until i figured out that your 'drop' is
my 'pop'!
i'll bet your c function is faster than my brute force k routine,
but it's nice to know we get the same answers - ;-)
\l joy
Find:{[g;s;b]
s:I s
t:s E/I g
n:#b:I b
i:1
while[1
j:0
do[_ n^i
c:b(i#n)_vs j
if[t~*|.[E/;(s;c);:];:`0:O@|c]
j+:1]
\i+:1]
}
Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]
2
3
4
5
6
7
8
[] cons cons cons i pop swap i
--
best
sa
> > However, there are a few interesting constructions it has found,whoops. sorry :-)
> > for instance:
> >
> > [dup] dip == [] cons cons dup call drop swap call
>
> this was driving me nuts until i figured out that your 'drop' is
> my 'pop'!
> i'll bet your c function is faster than my brute force k routine,maybe... it took my 133Mhz pentium 20 seconds. the k one could not have
taken more than a couple hours, judging by how quickly you responded.
the k one certainly appears way more compact.
one trick used that significantly speeds things up is that the
program never explores expressions with redexes in them; that is,
you will never get a result involving something like "[foo] drop"
or "[foo] call" or "[foo] dup" (where enough parameters are statically
known that an reduction could occur), although admittedly you could get
something involving "dup drop" or "[] dip".
> but it's nice to know we get the same answers - ;-)out of curiousity, is that list on the right the list of bases?
>
> [k code which i do not understand :-)]
>
> Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]
why does "[]" need to be explicitly provided? does not the
finder automatically use all kinds of quotations. if not, it seems
like that would be a hole, as it then could not find constructions like
[swap] dip swap [swap] dip == swap [swap] dip swap
because these contain non-empty quotations...
but, speaking of holes, I discovered that my program has quite a
large one: generally, it will fail to find results if the goal
combinator has a cons'ing effect (like "cons" and "concat"). oops.
but it is quite a deep flaw and am a bit confused and not sure
what a good way is to fix it.
but the whole thing needs a redesign anyway. currently, it operates
by testing a possibility, and then incrementing it, and then testing
and then incrementing, and so forth. it would be way faster (i think)
if with each test, only the last word or so in the program usually
changed (instead of the first word or so, as it currently is),
and if the system did not do the whole test all over, but remembered
shared results from the program so far...
I'm guessing that a big speed increase could be gained that way.
Although I'm not really sure what use any of this is ... :-)
It could perhaps be of use when trying to make an optimizer that
eliminates redundant stack-juggling, I suppose.
> best- "iepos" (Brent Kerby)
>
> sa
----- Original Message -----
From: <iepos@...>
To: <concatenative@egroups.com>
Sent: Sunday, June 04, 2000 12:35 AM
Subject: Re: [stack] joy combinator construction finder
>
> > i'll bet your c function is faster than my brute force k routine,
>
> maybe... it took my 133Mhz pentium 20 seconds. the k one could not have
> taken more than a couple hours, judging by how quickly you responded.
> the k one certainly appears way more compact.
my 450 mhz machine took 39 seconds to test 392476 expressions -
how odd.
>
> one trick used that significantly speeds things up is that the
> program never explores expressions with redexes in them; that is,
> you will never get a result involving something like "[foo] drop"
> or "[foo] call" or "[foo] dup" (where enough parameters are statically
> known that an reduction could occur), although admittedly you could get
> something involving "dup drop" or "[] dip".
do you have any feel for how this strategy cuts down the
search space? is it worth it?
>
> > but it's nice to know we get the same answers - ;-)
> >
> > [k code which i do not understand :-)]
> >
> > Find["[dup]dip";"[1][2]";"[] cons dup i pop swap"]
>
> out of curiousity, is that list on the right the list of bases?
> why does "[]" need to be explicitly provided? does not the
> finder automatically use all kinds of quotations. if not, it seems
> like that would be a hole, as it then could not find constructions like
>
> [swap] dip swap [swap] dip == swap [swap] dip swap
>
> because these contain non-empty quotations...
oh yes, this is a big hole. it should consider all possible
constructions from the base.
>
> but, speaking of holes, I discovered that my program has quite a
> large one: generally, it will fail to find results if the goal
> combinator has a cons'ing effect (like "cons" and "concat"). oops.
> but it is quite a deep flaw and am a bit confused and not sure
> what a good way is to fix it.
>
> but the whole thing needs a redesign anyway. currently, it operates
> by testing a possibility, and then incrementing it, and then testing
> and then incrementing, and so forth. it would be way faster (i think)
> if with each test, only the last word or so in the program usually
> changed (instead of the first word or so, as it currently is),
> and if the system did not do the whole test all over, but remembered
> shared results from the program so far...
>
> I'm guessing that a big speed increase could be gained that way.
> Although I'm not really sure what use any of this is ... :-)
> It could perhaps be of use when trying to make an optimizer that
> eliminates redundant stack-juggling, I suppose.
there must be a theory lurking in all of this. i wonder what
it is?
>
> > best
> >
> > sa
>
> - "iepos" (Brent Kerby)
>
> ------------------------------------------------------------------------
> Porsche Boxter. You and a friend. Nine dream days from
> Napa Valley to Beverly Hills. Provided by CarsDirect.com.
> Click to enter.
> http://click.egroups.com/1/4882/6/_/_/_/960093345/
> ------------------------------------------------------------------------
>
> To unsubscribe from this group, send an email to:
> concatenative-unsubscribe@egroups.com
>
>
>
>
> > one trick used that significantly speeds things up is that thea very natural question to ask. Actually, before now I had never tried
> > program never explores expressions with redexes in them; that is,
> > you will never get a result involving something like "[foo] drop"
> > or "[foo] call" or "[foo] dup" (where enough parameters are statically
> > known that an reduction could occur), although admittedly you could get
> > something involving "dup drop" or "[] dip".
>
> do you have any feel for how this strategy cuts down the
> search space? is it worth it?
not using the trick. Now, here's what I get without the trick,
when we have 5 bases:
(size 1, total checked 0)
(size 2, total checked 6)
(size 3, total checked 48)
(size 4, total checked 378)
(size 5, total checked 3192)
(size 6, total checked 28614)
(size 7, total checked 268056)
(size 8, total checked 2594490)
* []ccwiksi
(size 9, total checked 25745520)
...
The number of expressions to search increases exponentially with size,
as we'd expect, at about a factor of 10. Now, here's what we get with
the trick:
(size 1, total checked 0)
(size 2, total checked 6)
(size 3, total checked 45)
(size 4, total checked 316)
(size 5, total checked 2303)
(size 6, total checked 17493)
(size 7, total checked 137404)
(size 8, total checked 1107784)
* []ccwiksi
(size 9, total checked 9115213)
A significant improvement, although actually not as much as I would have
expected. We are still exponential, but now at about a factor of 8.
The five bases used here were {i, dup, drop, swap, cons}; the important
thing is that 3 of the five are unary. The trick applies better the
more combinators are unary, since then it will never at all attempt to use
a quotation before a combinator (whereas with binary combinators,
one quotation before is okay, although two is not). For instance,
if we lie to the program and tell it that all five combinators are
unary, then we get:
(size 1, total checked 0)
(size 2, total checked 6)
(size 3, total checked 43)
(size 4, total checked 278)
(size 5, total checked 1817)
(size 6, total checked 12209)
(size 7, total checked 84476)
(size 8, total checked 600950)
(size 9, total checked 4384065)
...
A further improvement, except when you consider that it missed the
solution (because a quotation was needed before "cons") :-)
Anyway, I would definitely say that the trick is worth it. The
time it takes to do the check seems insignificant compared
to all the time wasted doing other things (i haven't done a exact time
check though; maybe I should, but I think really i'm just going
to start over and make a new version; so many cycles are thrown
away by using a basically bad algorithm that there is no point
trying to fine-tune it in this way, I think).
> there must be a theory lurking in all of this. i wonder what it is?The theory of Joy combinators is similar to the theory of
Combinatory Logic, pioneered in the 1930s by Haskell Curry and others.
The combinators studied then were a bit different in that they were
considered as functions that can be applied to each other using a
function-application construct, whereas in Joy we concatenate
combinators together and have quotations.
The combinators W, K, and C, however, are strikingly similar to the
"dup", "pop", and "swap" of Joy, respectively. For more information
on combinatory logic, I might recommend Curry's book, "Combinatory Logic",
and maybe Raymond Smullyan's "To Mock a Mockingbird". You might also find
useful some old pages that I've written, available online at:
http://tunes.org/~iepos
Also, you might find interesting a long discussion between Billy and I
on the TUNES list beginning January this year, under the subject
"Joy, Lambdas, Combinators, Procedures":
http://lists.tunes.org/list/tunes/0001/
In this, I was mainly advocating making a new, pure applicative system
based on combinators instead of named variables, while Billy was
emphasizing how much better the concatenative approach is.
Now I think I'm mostly won over to the Joy way of doing things,
because it is closer to the way things work on real machines.
However, the applicative approach is still quite curious; for one thing,
with applicative combinators one can get a complete base with just
two combinators (the so-called "S" and "K", with "I" usually added also,
although not strictly necessary). With Joy, the smallest complete base I
know of involves four combinators: "sip", "drop", "i", and "cons".
Since "sip" is not standard Joy, I suppose I should define it to avoid
being misunderstood again ... :
[x] [f] sip == [x] f [x]
It is similar to "dip" in that it saves a parameter, runs a program,
and restores the saved thing, except that "sip" also leaves a copy
of the parameter for the program.
- "iepos" (Brent Kerby)
From: iepos@... [mailto:iepos@...]
>On my machine it is currently tackling the "dip" problem mentionedSince you're allowing cons you must at least allow the unit list. I assume,
>earlier: is "dip" constructable from {call, drop, dup, swap, cons}?
of course, that you're using 'call' to mean 'i'.
enquote == [] cons;
concat == [] cons cons;
dip == enquote concat call.
We're removing the first and second item from the stack, and using them to
build a program which when executed will execute the second item, then will
place the first item back on the stack. We then execute the program.
Example:
7 [4 +] 3 enquote -> 7 [4 +] [3]
7 [4 +] [3] concat -> 7 [4 + 3]
7 [4 + 3] call -> 11 3
>- "iepos" (Brent Kerby)-Billy
From: iepos@... [mailto:iepos@...]
>> this was driving me nuts until i figured out that your 'drop' isI always use 'drop' for that myself -- to me, 'pop' implies not discarding,
>> my 'pop'!
>whoops. sorry :-)
but rather storing somewhere else (it's a word in common use in Forth). In
fact,
pop == dup first
As far as I'm concerned.
>- "iepos" (Brent Kerby)-Billy
> >On my machine it is currently tackling the "dip" problem mentionedYes, all kinds of quotations are allowed, with the unit list as
> >earlier: is "dip" constructable from {call, drop, dup, swap, cons}?
>
> Since you're allowing cons you must at least allow the unit list.
a special case. For instance, expressions like
[dup call] cons
would be considered permissible to use in the construction.
> I assume, of course, that you're using 'call' to mean 'i'.Right.
> enquote == [] cons;Yes. This is the combinator I've called "unit". It takes an item off
the stack and yields a quoted program that would push that item when run.
> concat == [] cons cons;This is incorrect, I believe. Say that you have the lists "[1 2]" and
"[3 4]" on the stack, this will just give you
[1 2] [3 4] [] cons cons
[1 2] [[3 4]] cons
[[1 2] [3 4]]
We have not concatenated the two lists, but only wrapped the two lists
unchanged into a new list. However, by modifying the technique a bit,
you could construct "concat" correctly as
concat == [[call] dip call] cons cons
With the example above we get
[1 2] [3 4] [[call] dip call] cons cons
[1 2] [[3 4] [call] dip call] cons (cons)
[[1 2] [3 4] [call] dip call] (cons)
[[1 2] call [3 4] call] (dip)
[1 2 [3 4] call] (call)
[1 2 3 4] (call)
> dip == enquote concat call.Yes, this is right ... except that the "dip" thus constructed takes the
>
> We're removing the first and second item from the stack, and using them to
> build a program which when executed will execute the second item, then will
> place the first item back on the stack. We then execute the program.
> Example:
>
> 7 [4 +] 3 enquote -> 7 [4 +] [3]
> 7 [4 +] [3] concat -> 7 [4 + 3]
> 7 [4 + 3] call -> 11 3
item to save first (i.e., it expects it as the top item on the stack),
and then the program to run, which is backwards from Joy's standard
"dip", which takes the program first. Just prepending a "swap" to the
construction could fix this, of course.
> >- "iepos" (Brent Kerby)- "iepos" (Brent Kerby)
>
> -Billy
From: iepos@... [mailto:iepos@...]
>> >On my machine it is currently tackling the "dip" problem mentionedObviously, this isn't sufficient -- we can't define dip in terms of itself.
>> >earlier: is "dip" constructable from {call, drop, dup, swap, cons}?
>> concat == [] cons cons;
>This is incorrect, I believe. Say that you have the lists "[1 2]" and
>"[3 4]" on the stack, this will just give you
> [1 2] [3 4] [] cons cons
> [1 2] [[3 4]] cons
> [[1 2] [3 4]]
>We have not concatenated the two lists, but only wrapped the two lists
>unchanged into a new list. However, by modifying the technique a bit,
>you could construct "concat" correctly as
> concat == [[call] dip call] cons cons
In general, a true concat is inappropriate, since it implies a list
unwrapping which cannot dequote. Joy is deficient in this respect, IMO; it
fails to correctly define the operation which 'first' actually performs on a
quotation.
Of course, I can make this work in spite of its illegality; I can't test it,
since I don't have a joy-capable platform, but try this:
sneakytrick == [call] first;
concat == sneakytrick swap cons cons;
dip == swap unit concat call.
My first solution can also be modified to work in a more legitimate way:
uncons == dup rest swap first;
join == [] cons cons;
dip == swap join uncons call first.
However, both of these explicitly require at least 'first'; in other words,
they have to be able to disassemble the lists they're allowed to create. In
a combinator spanning set one would probably want to include 'uncons' rather
than 'first' and 'rest'. By the way, you'll also want to remove 'swap' from
your so-called basis set; swap == [] cons cons call.
I believe that these will make the system complete by your terms. This is
an interesting kind of completeness, since it applies to runtime programs as
well as compile-time ones; you can pass quotations (such as ones generated
using loops) to functions using these, and they'll operate correctly on
them. The applicative completeness using only I and K can't handle runtime
actions, probably because one of the crucial components is the applicative
parser.
>- "iepos" (Brent Kerby)-Billy