views:

62

answers:

3

OK, for those who have never encountered the term, a quine is a "self-replicating" computer program. To be more specific, one which - upon execution - produces a copy of its own source code as its only output.

The quines can, of course, be developed in many programming languages (but not all); but some languages are obviously more suited to producing quines than others (to clearly understand the somewhat subjective-sounding "more suited", look at a Haskell example vs. C example in the Wiki page - and I provide my more-objective definition below).

The question I have is, from programming language perspective, what language features (either theoretical design ones or syntax sugar) make the language more suitable/helpful for writing quines?

My definition of "more suitable" is "quines are easier to write" and "are shorter/more readable/less obfuscated". But you're welcome to add more criteria that are at least somewhat objective.

Please note that this question explicitly excludes degenerate cases, like a language which is designed to contain "print_a_quine" primitive.

+3  A: 

Languages like the Io Programming Language and others allow the treating of code as data. In tree walking systems, this typically allows the language implementer to expose the abstract syntax tree as a first class citizen. In the case of Io, this is what it does. Being object oriented, the AST is modelled around Message objects, and a special sentinel is created to represent the currently executing message; this sentinel is called thisMessage. thisMessage is a full Message like any other, and responds to the print message, which prints it to the screen. As a result, the shortest quine I've ever been able to produce in any language, has come from Io and looks like this:

thisMessage print

Anyway, I just couldn't help but sharing this with you on this subject. The above certainly makes writing quines easy, but not doing it this way certainly doesn't preclude easily creating a quine.

jer
+2  A: 

I'm not sure if this is useful answer from a practical point of view, but there is some useful theory in computability theory. In particular fixed points and Kleene's recursion theorem can be used for writing quines. Apparently, the theory can be used for writing quine in LISP (as the wikipedia page shows).

Tomas Petricek
+2  A: 

I am not entirely sure, so correct me if anyone of you knows better. I agree with both other answers, going further by explaining, that a quine is this:

Y g

where Y is a Y fixed-point combinator (or any other fixed-point combinator), which means in lambda calculus:

Y g = g(Y g)

now, it is quite apparent, that we need the code to be data and g be a function which will print its arguments.

So to summarize we need for constructing such a quines functions, printing function, fixed-point combinator and call-by-name evaluation strategy.

The smallest language that satisfies this conditions is AFAIK Zot from the Iota and Jot family.

Gabriel Ščerbák