quines

Relational interpreter in miniKanren that can generate quines

It's quine time! -- Daniel P. Friedman

Update -- 29 Sept 2012

We have taken the liberty to veer ever so slightly from the transcript (please work from talk.scm instead), since we now have a side-effect free version of the implementation. This means that we have replaced

(define no-closureo (not-in 'closure))

and

(no-closureo x)

by a single goal

(noo 'closure x).

This also allows the noo expression to appear anywhere a goal can appear, provided the first argument to noo is a symbol and the second argument is any term. This is the only change and today we saw a generation of four thrines, which you can see in q.scm.

Requirements

Chez Scheme or its free version Petite Chez Scheme are required to run the quines code and its supporting libraries.

Petite Chez Scheme quick start

The Petite Chez Scheme distributions are located at the Cadence Research Systems website. The installation instructions are clear and concise. A quit rundown of relevant commands are as follows:

• To launch Petite Chez Scheme, simple run petite at your system command prompt

• If a computation enters an infinite loop, then you can hit CTRL-C to abort the computation and enter a debugging prompt.

  • Type ? to view the available debugging commands

• To load a source file, type (load "<filepath>") where <filepath> is the path to a Scheme source file.

• Type (exit) to quit from Petite Chez Scheme

Visit the official Petite Chez Scheme documentation for more information.

Getting the source code

Clone the quines repository using Git with the following command:

git clone git://github.com/webyrd/quines.git

You can also download the source repository directly at https://github.com/webyrd/quines/downloads and extract its contents into your directory of choice.

Generating quines

Navigate to the location where the quines source code was placed and launch your Chez Scheme or Petite Chez Scheme REPL.

From the REPL enter the following to load the quine system:

(load "q.scm")

Finally, enter the following Scheme expression to exercise the quine system and verify that all seems in order:

(run 1 (q) (eval-expo q '() q))

You should see the following (formatted for readability):

((((lambda (_.0)
     (list _.0 (list 'quote _.0)))
   '(lambda (_.0)
      (list _.0 (list 'quote _.0))))
  (=/= ((_.0 . list))
       ((_.0 . closure))
       ((_.0 . quote)))
  (sym _.0)))

To prove that the system generated a quine, enter the following in the REPL:

((lambda (_.0)
   (list _.0 (list 'quote _.0)))
  '(lambda (_.0)
     (list _.0 (list 'quote _.0))))

The resulting value should be the same as the executed form itself!

View the talk.scm file for more usage examples.

Enjoy!