I'm having a hard time wrapping my mind around this. Can someone explain
just how the following form manages to reproduce itself when executed?
((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
'`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
"Robert Rotstein" <·········@verizon.net> writes:
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
Mushroom! Mushroom!
-dan
--
"please make sure that the person is your friend before you confirm"
Robert Rotstein wrote:
> I'm having a hard time wrapping my mind around this. Can someone explain
> just how the following form manages to reproduce itself when executed?
>
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
>
>
Well, how rudimentary of an explanation are you seeking?
1. Do you understand the use of lambda forms?
((lambda (x) (+ x 2)) 3) => 5
vs.
(funcall #'(lambda (x) (+ x 2)) 3) => 5
vs.
(defun f (x) (+ x 2))
(f 3) => 5
2. Do you understand backquote and comma?
`(a b ,(+ 1 2)) is basically the same as (list 'a 'b (+ 1 2)), i.e.,
replace the _value_ of expressions marked by comma inside a list of
otherwise unevaluated elements.
3. Do you understand quote?
'(a b c) == (quote (a b c))
So your example is basically the same as this:
(defun my-lambda (x)
(list (list (quote lambda) (list (quote lambda)) x)
(list (quote quote) x)))
or simply
(defun my-lambda (x)
`((lambda (lambda) ,x) ',x))
(my-lambda '`((lambda (lambda) ,lambda) ',lambda)) =>
((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
'`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
MY-LAMBDA applies a function to an expression that resembles the
syntactic structure of the function itself. The use of LAMBDA as a
parameter name merely ups the obfuscation factor.
This is an example of a Quine (named for WVO Quine)--a program whose
output replicates its source.
David Sletten
Robert Rotstein wrote:
> I'm having a hard time wrapping my mind around this. Can someone explain
> just how the following form manages to reproduce itself when executed?
>
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
I tend to think of composing Quines as analogous to composing magic squares
(without the use of deterministic algorithms that produce them) or anagrams
or such. Things I was never good at.
Chris Capel
Robert Rotstein wrote:
> I'm having a hard time wrapping my mind around this. Can someone explain
> just how the following form manages to reproduce itself when executed?
>
> ((LAMBDA (LAMBDA) `((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
> '`((LAMBDA (LAMBDA) ,LAMBDA) ',LAMBDA))
First of all, some of these instances of LAMBDA are only
formal parameters and we might as well replace them with,
say, X to reduce confusion.
((LAMBDA (X) `((LAMBDA (X) ,X) ',X))
'`((LAMBDA (X) ,X) ',X))
Now, consider the following subform:
`((LAMBDA (X) ,X) ',X)
Call it E. Note that X plays more than one role in E...
Now, our big scary form has the following structure.
((LAMBDA (X) E) 'E)
So, this defines an anonymous function -- (LAMBDA (X) E) --
and applies it to E itself. Let's take a look at that anonymous
function. E is being evaluated here, in a context where X is
bound (since it's a function argument). Call the thing X is
bound to "Y". Then evaluating E does the usual backquote
template-filling-in thing; each instance of ",X" turns into "Y".
Thus, evaluating E produces
((LAMBDA (X) Y) 'Y)
But ... the thing X is bound to, as a matter of fact, is E
itself. Thus, evaluating E in *this* context produces
((LAMBDA (X) E) 'E)
which, if you look back up a few lines, is exactly the same
thing as our big scary form. We're done.
--
Gareth McCaughan
.sig under construc