quines

sa@dfa.com — 2001-08-07 19:40:22

manfred's joy quine



    [[dup cons] dup cons]



is really quite beautiful.  on my drive into work this

morning i was so entranced by it that i pulled away from

the gas station with the pump still attached to my car!



anyway, i thought it might be fun to find the smallest k

implementation of concatenative semantics which would run

this successfully.



represent the stack by a list.



atoms are symbols of functions and programs are lists.



an evaluator E is a function of two arguments:



    E:{:[@y;y x;(,y),x]}



x is a stack and y is an item to evaluate.  if y is an

atom, then apply it to the stack, else enlist prepend it

to the stack.



define three functions.  each one takes a stack and

returns a stack:



    dup:{x[,0],x}                / duplicate first

    cons:{(x[,0],x 1),2_ x}      / cons first two

    i:{(1_ x)E/*x}               / evaluate first over rest



i is a loop over each of the first of the stack.  e.g. if

the stack x is [a b c] d e then i x is:



    E[E[E[d e;a];b];c],



the quine is:



    quine:(`dup`cons;`dup;`cons)



to run, apply i to a stack whose first element is quine:



    i[,quine]

(`dup `cons

 `dup

 `cons)



or equivalently:



    E[,quine;`i]

(`dup `cons

 `dup

 `cons)