While bored one night, I thought about how a lot of people only
know one thing about Lisp: that it uses lots of parens. If they've
taken a class in college that uses Lisp, they may also remember that
it's got "some weird funky lambda thing".
So I decided to implement a quine (I was reading GEB at the time)
using only parens and lambda, no other tokens:
((lambda (lambda) ((lambda lambda lambda) lambda lambda))
(lambda (lambda) ((lambda lambda lambda) lambda lambda)))
(I seem to recall a discussion here about "Buffalo buffalo buffalo
buffalo buffalo." It may have been related to this quine.)
Now, this is (I believe) correct for *some* definition of Lisp, but it
has some requirements on the Lisp:
1. Lambda forms must be acceptable without decoration such as #'.
2. Lambda forms must be acceptable as a function, that is, in the car
of a function call.
3. A lambda list that's a symbol instead of a list must be
acceptable (as with Scheme).
4. The symbol LAMBDA must allowable as a variable name.
5. It's nice-- but not necessary-- if lambda forms are self-quoting.
Otherwise, the above is not a quine, but it produces one-- but one
that probably doesn't have a readable representation. Instead,
it'll produce something like
(#<function 0xDEADBEEF> #<function 0xDEADBEEF>), which would indeed
be a quine, but not a very fun one.
Criterion 5 (which, like I said, is technically optional) nearly
effectively means that the Lisp is dynamically scoped, since making
lambdas self-quoting doesn't make much sense if you have closures.
(It would be reasonable, however, to consider a Lisp which generates
closures if there are free variables, and unadorned lambda expressions
otherwise. This could be an optimization to allow earlier GC's of
unused binding contexts. I don't know of any Lisp which does this. I
may modify LQLisp (below) to do so.)
No Lisp that I've tried this with meets all the criteria:
1 2 3 4 5
CLtL1 NIL T NIL T *
ANSI CL T T NIL T NIL
Scheme T T T NIL NIL
MacLisp NIL T ** T * <-- interpreted; not sure about compiled
Emacs T T NIL T T
*: It's an error to use an unadorned lambda as a form.
**: While it looks like MacLisp accepts a symbol as the lambda list,
it doesn't use the Scheme semantics: it binds the symbol to the number
of arguments, and provides the ARG function to get the argument
values.
Emacs and Scheme come closest, in my judgment. I was surprised that
every Lisp I tried supported #2, even the ones that didn't allow
unadorned lambdas elsewhere. I also had thought that CL supported #3,
based on a faulty memory of an example from CLtL2.
To test my quine, then, I wrote my own Lisp, called LQLisp (Lambda
Quine Lisp). It's a dynamically scoped, deep-binding lisp-1, pretty
much a classroom exercise. It's similar in appearance to the lambda
calculus, but doesn't allow for closures / currying. This is pretty
much the minimal Lisp that would run the lambda quine. It has one
special form (lambda) and one subr (quit). There's no (for instance)
eq, setq, defun/defvar, although the implementation allows for them
(the last by nconcing onto the end of *lq-global-env*).
If anybody knows of a way to make this quine work on an existing Lisp,
using only lambda and parens, I'd be interested in hearing about it.
On the other side, if anybody knows of a Lisp that works with my
quine, I'd be all ears then too.
Share and enjoy,
joelh
;;; -*- Mode: LISP; Syntax: ANSI-Common-Lisp; Package: CL-USER; Base: 10 -*-
;;; $Id$
;;; Public domain, 2004 by Joel Ray Holveck.
(in-package "CL-USER")
(defun lq-lambda (args env)
(declare (ignore env))
(cons 'lambda args))
(defun lq-quit (args env)
(declare (ignore args env))
(throw 'lq-quit nil))
(defparameter *lq-special-forms* '((lambda . lq-lambda)))
(defvar *lq-global-env* `((t . t)
(nil . nil)
(quit . ,#'lq-quit)))
(defun lq-apply (fn args environment)
(cond
((and (consp fn) (eq (car fn) 'lambda)) ;lambda expr
(let* ((lambda-list (cadr fn))
(environment
(etypecase lambda-list
;; Note that we don't support dotted lambda lists.
;; Some call it inconsistent. I call it lazy. Is
;; there something like MAPLIST that accepts atoms?
(list
(unless (= (length lambda-list) (length args))
(error "Wrong number of args: ~S <- ~S" lambda-list args))
(nconc (mapcar #'cons lambda-list args) environment))
(symbol
(acons lambda-list args environment)))))
(loop
for form in (cddr fn)
as result = (lq-eval form environment)
finally (return result))))
((functionp fn) ;subr
(funcall fn args environment))
(t
(error "Not a function: ~S" fn))))
(defun lq-eval (form environment)
(cond
((symbolp form) ;variable reference
(let ((binding (assoc form environment)))
(unless binding
(error "Unbound variable: ~S" form))
(cdr binding)))
((and (consp form) ;special form
(assoc (car form) *lq-special-forms*))
(funcall (cdr (assoc (car form) *lq-special-forms*))
(cdr form)
environment))
((consp form) ;function call
(lq-apply (lq-eval (car form) environment)
(mapcar #'(lambda (subform)
(lq-eval subform environment))
(cdr form))
environment))
(t
form)))
(defun lq-lisp ()
(catch 'lq-quit
(loop
(fresh-line)
(princ "> ")
(print (lq-eval (read) *lq-global-env*)))))
--
Joel Ray Holveck - ·····@piquan.org
Fourth law of programming:
Anything that can go wrong wi
sendmail: segmentation violation - core dumped
In article <··············@thor.piquan.org>,
Joel Ray Holveck <·····@piquan.org> wrote:
>4. The symbol LAMBDA must allowable as a variable name.
...
>Scheme T T T NIL NIL
Should be
Scheme T T T T NIL
at least with the R5RS macro system.
Brad
From: Joel Ray Holveck
Subject: Re: Lambda Quine (and the Lisp it rode in on)
Date:
Message-ID: <87sm90b3ua.fsf@thor.piquan.org>
>> 4. The symbol LAMBDA must allowable as a variable name.
> ...
>> Scheme T T T NIL NIL
> Should be
> Scheme T T T T NIL
> at least with the R5RS macro system.
Thanks, I don't know much about Scheme. My idea was based on a
misinterpretation of one part of R5RS. After more careful review, I
think I understand a little better.
Unfortunately, my lambda quine is still, from what I can tell, not
usable in Scheme. This is because it binds lambda around a form that
includes a lambda expression, so the lambda expression is taken as a
function call to whatever lambda is bound to at that time.
I guess should revise my #4:
4. The symbol LAMBDA must allowable as a variable name, but still
retain its lambda-ness.
This doesn't make much sense in a Lisp-1 without special forms, which
is how my LQLisp works, that is, it has special forms even though it's
a Lisp-1.
Thanks for the note!
Cheers,
joelh
--
Joel Ray Holveck - ·····@piquan.org
Fourth law of programming:
Anything that can go wrong wi
sendmail: segmentation violation - core dumped
Joel Ray Holveck <·····@piquan.org> wrote:
+---------------
| While bored one night, I thought about how a lot of people only
| know one thing about Lisp: that it uses lots of parens. If they've
| taken a class in college that uses Lisp, they may also remember that
| it's got "some weird funky lambda thing".
|
| So I decided to implement a quine (I was reading GEB at the time)
| using only parens and lambda, no other tokens:
|
| ((lambda (lambda) ((lambda lambda lambda) lambda lambda))
| (lambda (lambda) ((lambda lambda lambda) lambda lambda)))
|
| (I seem to recall a discussion here about "Buffalo buffalo buffalo
| buffalo buffalo." It may have been related to this quine.)
|
| Now, this is (I believe) correct for *some* definition of Lisp, but it
| has some requirements on the Lisp...
+---------------
Here's a REPL quine that Kent Pitman posted several years ago
[in <····················@world.std.com>] that works in ANSI CL:
(LET ((LET
'`(LET ((LET ',LET))
,LET)))
`(LET ((LET ',LET))
,LET))
By using the standard expansion of LET into LAMBDA:
(let ((var value)) ==> ((lambda (var) body)
body) value)
and possibly some local variable renaming (of quoted constant
symbol LETs into symbol LAMBDAs), you should be able to transform
the all LETs & quotes & backquotes version in a LAMBDAs & quotes &
backquotes version, but I'm not sure you can get rid of the
quotes & backquotes.
Here's my first cut at a conversion of the above LET-based quine
into LAMBDAs & quotes & backquotes. I may have made mistakes in
the conversion, but at least the result *is* a REPL quine in CL
[well, at least in both CMUCL & CLISP]:
((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
'`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sat, 09 Oct 2004 04:00:02 -0500, Rob Warnock wrote:
>
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
>
You can do something a little simpler:
((lambda (lambda) `(,lambda ',lambda))
'(lambda (lambda) `(,lambda ',lambda)))
Cheers,
Bill.
--
"If you give someone Fortran, he has Fortran. If you give someone Lisp,
he has any language he pleases." -- Guy Steele
From: Joel Ray Holveck
Subject: Re: Lambda Quine (and the Lisp it rode in on)
Date:
Message-ID: <87k6tlnnwa.fsf@thor.piquan.org>
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
Sure, but that's got backquotes. Remember, my goal was to make a
quine that used only parens and lambda.
Backquotes certainly make quining easier; indeed, if you were to
purpose-build a construct for writing quines, it'd be hard to find
something more suitable than the backquote. For instance, I couldn't
use CL for mine because it had ((lambda lambda lambda) ...), but
that's just LIST[1], and backquotes make LIST easy. In fact, the
lambda quine I posted came out of me trying to get rid of the
backquotes from this earlier version (which Bill posted already):
((lambda (lambda) `(,lambda ',lambda)) '(lambda (lambda) `(,lambda ',lambda)))
But as I say, I was going for something that only used parens and
lambda.
Thanks,
joelh
[1] Okay, LIST can't reuse its argument list. That's not the point here.
--
Joel Ray Holveck - ·····@piquan.org
Fourth law of programming:
Anything that can go wrong wi
sendmail: segmentation violation - core dumped