# Re: [stack] Re: God's Own Algorithms.

## Billy and Melissa — 2002-04-05 00:31:27

    From: "e1_t" <e1_t@...>

     > He simply made a decision to use stack instead of registers. Doing

    > that doesn't cripple C compilers or any other compilers - it does

    > make Forth interpreters shine though (note that I said interpreters -

    > a Forth compiler is really no different to any other compiler - it

    > can be made equally efficient on any platform).

     That's mostly true, but actually all code is tuned in some way for the type

    of machine the author expects it to be running on.  Forth for Chuck's

    machines can be perfectly valid Forth, yet still be tuned just for his

    machines.  That's his big claim about them.

    -Billy

## Brent Kerby — 2002-04-07 01:56:33

    > Now wouldn't it be nice to have a brute force search for the most powerful

    > base.

    >

    > John Carter

     Yes ... I was thinking about your idea here, and I think it is quite

    interesting.

    With a bit of programming work, I bet you could actually formalize the idea

    of the "power" of a base, in a Joy combinator context, in such a way that

    the power of particular bases could even be (approximately) computed by some

    brute force.

    To me, the most simple way that comes to mind to test the power of a base is

    this: given a base, construct every possible combinator up to a certain

    size, using the smallest possible construction, and then find the average

    length of the constructions (the length of a construction should take into

    account that in a larger base each term will take slightly more bits to

    represent). This average would tell how powerful the base was, a smaller

    number indicating a more powerful base.

    This approach could be modified by just doing a random sampling of

    combinators to construct (rather than trying every single one), which could

    allow the computation to finish much quicker, and thus allow you to go up to

    a higher size of combinators to check.

    The automation could be carried one step further, and you could have the

    program automatically move on from base to base, checking every possible

    base, in search of the best one; however, I'm guessing the computations here

    are going to be expensive enough that it would only be wise to check bases

    which seem like reasonable candidates to be powerful (if this automation was

    used, I think it would be a practical neccessity to include some preliminary

    tests to weed out worthless bases before wasting long times doing the

    in-depth check; perhaps a preliminary test could be the same as the

    full-fledged check, though, except up to a much smaller size of combinator)

    One subtle question to ask in considering how to carry on this search is

    this: how exactly are the goal combinators to be expressed? Put another way,

    what exactly is meant by "construct every possible combinator up to a

    certain _size_"? How do we rate the size of a combinator except by reference

    to some base?

    To answer that question ... at first, I was thinking that in the search, the

    goal combinators would be expressed in lambda form. However, it would also

    be possible to represent the goal combinators in terms of some other base

    (for example, {i, cons, dip, dup, zap}), and that would give the resulting

    "power" a bit of a different meaning, since it would be relative to the base

    that the goal combinators were expressed in.

    But, anyway, assuming the search uses the lambda approach, the first few

    goal combinators that we'd be trying to construct would look something like

    this (the number one the left, before each colon, represents the arity of a

    given goal combinator; i.e., how many parameters it takes ... the numbers on

    the right symbolize the results that will happen, "0" symbolizing an

    execution (i.e., unquoting) of the first parameter, "1" symbolizing an

    execution of the second parameter, etc.):

    (size 1:)

    1:       (search for the program that takes 1 parameter and leaves nothing;

    i.e., "zap")

    (size 2:)

    1: 0     (search for a program that takes 1 parameter and executes it; i.e.,

    "i")

    2:       (search for a program that takes 2 parameters and leaves nothing)

    (size 3:)

    1: 00    (search for a program that takes 1 parameter and executes it twice,

    i.e., "rep2")

    1: [0]   (search for a program that does nothing, except check for one item;

    i.e., "[] dip")

    2: 0     (search for "k")

    2: 1     (search for "swap k", aka "zap i")

    3:       (drop three parameters)

    (size 4:)

    1: 000   ("rep3")

    1: 0[0]

    1: [0]0

    1: [00]

    2: 00

    2: 01

    2: 10

    (...)

    There is some flexibility as to how exactly this is defined. For example, a

    quotation could reasonably be defined to be of either size 1 or size 2 (2

    because it may implemented as a start "[" and terminator "]", or 1 because

    it may be implemented with just a single-byte prefix telling the length).

    Also, above I did not include combinators containing "[]"'s in them, even

    though they could be considered true combinators (after some thought about

    what Louis has said, I think I realize there is some significance to a

    formalism excluding empty quotations, also).

    Anyway, if someone feels up to programming something like this, that'd be

    really cool (maybe in a while I'd be up to it, but not right now anyway, at

    least until after I've written that article Manfred suggested). I might give

    just one hint, from the experience of writing two brute-force Joy searchers

    that really stink, efficiency-wise: in your brute-force search of the

    construction, incrementally try your construction, starting from the

    beginning, and adding one term at a time, and backtracking when either an

    error occurs or when the maximum size is reached. In this way, huge masses

    of search space are cut out, by backtracking on errors (by error, I'm

    talking about the basic "empty stack error", but also about cases where

    executions of the candidate program do not match up with the goal; e.g., if

    your goal is "0[2][1]" (dip2), and your candidate program begins by

    executing parameter "1" or "2", then you know it is safe to backtrack,

    because nothing that happens after an execution of "1" or "2" can ever make

    the combinator match the goal). I did not use that incremental approach, by

    the way, which is why my searchers are so slow.

    An extension to that approach, which would also help a ton, is to postpone

    filling in quotations until after their context is clear. In other words,

    actually have the body of quotations stored at the end of the expression.

    The reason for this is that, when you're about to push a quotation, any

    quotation seems valid, and so there's a huge search space; but, if you wait

    until later when the quotation is executed, you'll be able to cut back

    big-time on the search space using the backtracking technique.

    Well, this sounds fun ... any takers?

    - Brent

## Dan Andersson — 2002-05-01 01:30:46

    Before you begin a more serious undertaking you might gain a lot of headway by

    looking into the works of G. J. Chaitin and A. N. Kolmogorov. The link

    http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ieee74.html

    might be a start. And for a more practical and hands on approach on something

    approaching the problem domain. The record busting 'Busy Beaver' program by

    Heiner Marxen. The problem is literally leading you neck deep into the dirtiest pool

    of the mathematical swamplands.

    MvH Dan Andersson