I was recently asked the following question on a homework assignment:
What is the shortest self-reproducing non-atomic LISP form? A self-
reproducing form is one that evaluates to itself. t would be an
example, as it always evaluates to t. But t is atomic, and we seek
a non-atomic solution. It is considered cheating if your solution
involves any permanent side-effects. For example, we could
trivially solve the problem by defining a function f, say, that
returns (f) as its value. But we disqualify this solution because
defining a function counts as a permanent side effect.
As you might expect, the solution involves the use of lambda.
The professor's solution was as follows:
((lambda (x) (list x (list 'quote x)))
'(lambda (x) (list x (list 'quote x))))
My solution, which was shorter, was:
((lambda (x) `(,x ',x) '(lambda (x) `(,x ',x)))
My question is: can anyone come up with an even shorter self-
evaluating non-atomic LISP form?
Don't worry: I'm not cheating: the assignment is already handed in.
-- Ben Horowitz
········@cs.umass.edu
On Mon, 9 Oct 1995 13:04:44 GMT,
····@aplcenmp.apl.jhu.edu (Marty Hall) said:
Marty> A few "cheating" answers that are shorter:
Marty> (A) Use the '-' variable. Infinite short solutions with it. Eg
Marty> - ; Certainly the shortest possible solution :-)
Marty> (first (list -))
Marty> (append - nil)
Marty> etc
Marty> (B) Type (print (read)) twice. You get back (print (read)) twice.
Marty> Definitely not self-evaluating, but kinda looks like it.
Marty> (C) If the professor foolishly says that the solution must be a list
Marty> instead of saying it is non-atomic, then NIL is a solution.
Another "cheating" answer is to define a function "d":
(defun d () '(d))
then:
(d) => (d)
Some people might argue that the "defun" should be included in the
picture but what about the definitions for built-ins like "list" in the
canonical example?
--
+------------------------------------------------------------------+
| Jerry R. Jackson EMAIL: ···@rmtc.Central.Sun.COM |
| SunSoft Inc. SOUND: (719)528-3620 |
+------------------------------------------------------------------+
| It does me no injury for my neighbor to say there are twenty |
| gods or no god. It neither picks my pocket nor breaks my leg. |
| |
| -- Thomas Jefferson |
+------------------------------------------------------------------+
In article <··········@caleddon.dircon.co.uk>, Simon Brooke
<·····@rheged.dircon.co.uk> wrote:
> ········@kerits.cs.umass.edu (Benjamin Horowitz) wrote:
> >I was recently asked the following question on a homework assignment:
> >
> >What is the shortest self-reproducing non-atomic LISP form? A self-
> >reproducing form is one that evaluates to itself.
>
> ()
Bzzt. (ATOM ()) --> T
Dave
--
CPU Cycles: Use them now or lose them forever...
http://www.teleport.com/~dlamkins/
In article <··········@caleddon.dircon.co.uk> Simon Brooke <·····@rheged.dircon.co.uk> writes:
> From: Simon Brooke <·····@rheged.dircon.co.uk>
> Newsgroups: comp.lang.lisp
> Date: 8 Oct 1995 20:42:28 GMT
> Organization: Carlinscraig
> X-URL: ···············@kernighan.cs.umass.edu
>
> ········@kerits.cs.umass.edu (Benjamin Horowitz) wrote:
> >I was recently asked the following question on a homework assignment:
> >
> >What is the shortest self-reproducing non-atomic LISP form? A self-
> >reproducing form is one that evaluates to itself.
>
> ()
>
No, nil is an atom!
Certainly the 'Goedel constructions' of the
origenal posting are the most charming ones,
but shorter is:
#1=(quote #1#)
i.e. the form you get after evaluating
(let ((answer '(quote)))
(setf (cdr answer) answer)
)
Oh, set *print-circle* to T first!
Hmm I have to reset my system now,
because I tried the same thing
with "cdr" instead of "quote"... :-)
Geert-Jan
--
Geert-Jan van Opdorp
AI-Engineering
Amsterdam, The Netherlands
·····@aie.nl
In article <···················@sparc.aie.nl> ·····@sparc.aie.nl
(Geert-Jan van Opdorp) writes:
[Self-evaluating non-atomic Lisp form]
>Certainly the 'Goedel constructions' of the
>origenal posting are the most charming ones,
>but shorter is:
>
>#1=(quote #1#)
>
>i.e. the form you get after evaluating
>(let ((answer '(quote)))
> (setf (cdr answer) answer)
> )
Hmm, it seems to me that if you were allowed to rely on earlier side
effects, then defining the function foo such that (foo) returns (foo)
is easier and shorter. But IMHO "a Lisp form that evaluates to xxxx"
means one that evaluates to xxxx in any legal Lisp environment, so you
can't count on side effects having already happened. :-)
- Marty
(proclaim '(inline skates))
It is useful to distinguish between self-evaluating (the output is
equal to the input) and self-reproducing (the printed output looks
like the input). In ANSI CL, lambda is a macro, so the following is
self-reproducing in a CL that prints functions as their source code:
((lambda (x) (list x x))
(lambda (x) (list x x)))
My favorite example is only seven characters:
#1='#1#
This is self-evaluating, but only self-reproducing when *print-circle*
is true. So you can do:
#1=(setq *print-circle* '#1#)
Marty Hall pointed out that the variable - can be used, but he missed
a twelve character solution:
(identity -)
--
Peter Norvig | Phone: 415-833-4022 FAX: 415-833-4111
Harlequin Inc. | Email: ······@harlequin.com
1010 El Camino Real, #310 | http://www.harlequin.com
Menlo Park CA 94025 | http://www.cs.berkeley.edu/~russell/norvig.html
In article <····················@meteor.menlo.harlequin.com>
Peter Norvig writes:
>Marty Hall pointed out that the variable - can be used, but he missed
>a twelve character solution:
>
>(identity -)
I pointed out that if you allow the '-' variable then you have a one
character solution. So it wasn't too interesting finding other
solutions. But if you throw down the gauntlet like that :-), how about
(print -), with 9 characters, or (setq x -) with 10?
I didn't know about the #1= business. I'll be careful to exclude it
next time I assign the problem :-).
Hey, this is fun! Cheers-
- Marty
(proclaim '(inline skates))
Cyber Surfer <············@wildcard.demon.co.uk> wrote:
>In article <··········@caleddon.dircon.co.uk>
> ·····@rheged.dircon.co.uk "Simon Brooke" writes:
>
>> >What is the shortest self-reproducing non-atomic LISP form? A self-
>> >reproducing form is one that evaluates to itself.
>>
>> ()
>
>Um, I get the following, by using CLISP:
>
>> ()
>NIL
>
>I know. This is a technicality. ;-)
It was posted as a joke, but too many people took it seriously. At some level,
an empty list is an empty list and therefore not an atom; the name of the empty
list is nil which is an atom. But it's an implementation hack so lost in the
mists of antiquity to treat nil as being strictly equal to the empty list that
many good LISP people have forgotten that there ever was or might have been a
distinction; to the point that I'm prepared to bet that someone will post a
followup to this post giving a sound, mathematical rationalisation for the
assertion that the assertion that () is an atom is not a hack. And if you can
read a sentence like that you will appreciate how useful brackets can be.
--
------- ·····@rheged.dircon.co.uk (Simon Brooke)
'Victories are not solutions.'
;; John Hume, Northern Irish politician, on Radio Scotland 1/2/95
In article <··········@caleddon.dircon.co.uk>
Simon Brooke <·····@rheged.dircon.co.uk> writes:
>But it's an implementation hack so lost in the
>mists of antiquity to treat nil as being strictly equal to the empty list that
>many good LISP people have forgotten that there ever was or might have been a
>distinction; to the point that I'm prepared to bet that someone will post a
>followup to this post giving a sound, mathematical rationalisation for the
>assertion that the assertion that () is an atom is not a hack.
I agree that overloading the myriad uses of NIL is a hack. The Scheme
way is cleaner. However, here is an amusing dissenting opinion I found
on the Net once pointing out that it is a *convenient* hack.
- Marty
===========================================================================
A SHORT BALLAD DEDICATED TO THE GROWTH OF PROGRAMS
==================================================
by
Ashwin Ram
This is a tale of a sorry quest
To master pure code at the T guru's behest
I enrolled in a class that appealing did seem
For it promised to teach fine things like T3 and Scheme
The first day went fine; we learned of cells
And symbols and lists and functions as well
Lisp I had mastered and excited was I
For to master T3 my hackstincts did cry
I sailed through the first week with no problems at all
And I even said "closure" instead of "function call"
Then said the master that ready were we
To start real hacking instead of simple theory
Will you, said he, write me a function please
That in lists would associate values with keys
I went home and turned on my trusty Apollo
And wrote a function whose definition follows:
(cdr (assq key a-list))
A one-liner I thought, fool that I was
Just two simple calls without a COND clause
But when I tried this function to run
CDR didn't think that NIL was much fun
So I tried again like the good King of yore
And of code I easily generated some more:
(cond ((assq key a-list) => cdr))
It got longer but purer, and it wasn't too bad
But then COND ran out and that was quite sad
Well, that isn't hard to fix, I was told
Just write some more code, my son, be bold
Being young, not even a moment did I pause
I stifled my instincts and added a clause
(cond ((assq key a-list) => cdr)
(else nil))
Sometimes this worked and sometimes it broke
I debugged and prayed and even had a stroke
Many a guru tried valiantly to help
But undefined datums their efforts did squelch.
I returneth once more to the great sage of T
For no way out of the dilemma I could see
He said it was easy -- more lines must I fill
with code, for FALSE was no longer NIL.
(let ((val (assq key a-list)))
(cond (val (cdr val))
(else nil)))
You'd think by now I might be nearing the end
Of my ballad which seems bad things to portend
You'd think that we could all go home scot-free
But COND eschewed VAL; it wanted #T
So I went back to the master and appealed once again
I said, pardon me, but now I'm really insane
He said, no you're not really going out of your head
Instead of just VAL, you must use NOT NULL instead
(let ((val (assq key a-list)))
(cond ((not (null? val)) (cdr val))
(else nil)))
My song is over and I'm going home to bed
With this ineffable feeling that I've been misled
And just in case my point you have missed
Somehow I preferred (CDR (ASSQ KEY A-LIST))
:-)