Sat Apr 15 00:08:03 CEST 2006

quines in pf

I swear i started an entry already.. Can't find it. Anyways. Trying to
find a way to make quines in pf. Instead of an incremental brute force
approach, let's think about it first. What is a quine? A fixed point
of some function. Which function depends on the rules of the game.
Usually this is compile followed by run.

In pf, compile followed by run is generally equivalent to interpret.
Wether the game is trivial depends on what we see as compile and run,
and what we see as input or output.

For example, we could look for fixed points of the function
'interpret'. This prodices a lot of trivial quines: all non-symbols,
and symbols evaluating to themselves. This is considered
cheating. There has to be at least some operation of
unquoting/interpretation of the source code.

The next thing to look at is fixed points of 'interpret-list'. There
are no trivial quines here, since it involves unquoting. So that's the
first place to look for interesting quines.

In 'interpret-list' the containing list structure is removed, so there
has to be at least one operator which generates a new list from
non-list atoms. This could be 'pack'. This operation needs an integer
argument, so '<n> pack' should be part of the deal.

Maybe it's easier to write a reproducing program first. 
I'll use the shortcuts

     : i interpret-list ;
     : p pack ;

Playing with (1 p) i and dup gives

     ((1 p)) i     -> (1 p)
             dup i -> ((1 p))

So we see 

     ((1 p)) is a fixed point of { i dup i } 


     (1 p) is a fixed point of { dup i i }

What about this: you need a quoted payload that when executed will
duplicate the top of stack and pack it:

     dup 2 pack

Found this one

     ((dup 2 p) dup 2 p)  ->  ((dup 2 p) (dup 2 p))

Which evenually lead to the first quine:

     ((dup 2 pack split +) dup 2 pack split +)

Which reads as:
  * copy quoted code            dup
  * combine in one package      2 pack
  * unqote one half, recombine  split +

Analyzing that one gives a shorter one

     ((dup unsplit) dup unsplit)

Which reads as:
  * copy list of code
  * combine by inserting one list as a data
    argument into the other

This is very similar to the Y combinator, where you pass a function to
itself as a parameter to implement recursion. However, in that case
the reproduction eventually stops.

In CAT/PITH this quine is ((dup cons) dup cons). Both elements of the
first pair in this list point to (dup cons). The car one is quoted
because it is not a symbol, and the cdr one is interpreted because
it's cars are symbols.