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