Dear Friends of Lisp,
Cons-ing a quote with a symbol (x) to get ('x).
i am reading Gregory Chaitin's "The Unknowable" on Goedels and Turings
proofs of unprovability. (Free download) inwhich he uses "his" lisp to
help prove and teach us these ideas. In chapter 3 beginning he tries to
defun a fixed point using the syntax in the subject above (cons ' (cons
'(x) nil)).
i can't get clisp to accept this syntax of cons-ing the quote character
to a symbol ( variable x)
He want to get to (f f) becomes (('f) ('f)) where f is a function which
evaluates to itself. SO (f x) becomes (('x) ('x)).
CAn anyone tell me how to do this in clisp or any other lisp please??
Many thanks. i am fairly new to lisp and while i have done the
preliminary recursive functions of set manipulation i can't figure out
how to do this fixed point - to make a function that evaluates to
itself. Chaitin says it is the clue (trick) to understanding Goedels
theory/proof.
I just looked at this interesting text. You're going to be slightly
confused by his notation, but if you simply wrote out his quotes ['] as
QUOTE his code (mostly) works.
Example:
He writes:
(car (' (a b c)))
This won't work in normal lisp, but this will:
(car (quote (a b c)))
He's using the quote ['] to mean: The function QUOTE (actually, it's a
special form, not a function, but don't worry about that.)
This form:
(quote (a b c))
returns: (a b c)
The "normal", "modern" way to write what he's doing is:
(car '(a b c))
So, he does:
(cons (' a) (' (b c)))
You do:
(cons (quote a) (quote (b c)))
or better:
(cons ' a '(b c))
[Also, I hope you'll be able to completely ignore his M-expression
form, which is going to totally confuse you!]
I hope this helps!
ps to my note:
I wrote:
> So, he does:
>
> (cons (' a) (' (b c)))
>
> You do:
>
> (cons (quote a) (quote (b c)))
>
> or better:
>
> (cons ' a '(b c))
Although functionally identical, the space after the first quote in
this last form is extraneous. It should read:
(cons 'a '(b c))
It will work either way, but you'll be less confused if you remember to
put the quotes right next to what they are quoting.
So, to summarize:
He writes: (' anything)
He means: (quote anything)
You write: 'anything
and all will be well.
Actually, I totally take it back. Although what I said above is
correct, his scheme won't work for a different reason: He wants to use
a quoted lambda in function position, which you can't do in Common
Lisp. That is, he wants to do:
(eval '('(lambda (x) (reverse x)) '(a s d f)))
That won't work, but *this* will:
(eval '((lambda (x) (reverse x)) '(a s d f)))
[Note the missing ['] before the (lambda...)]
If you know what you're doing, you can rewrite his examples for
commonlisp, but you have to be careful, and know what you're doing.
Many many thanks to for your replies. they are most helpful and it is
so nice to get guidance and direction so fast. Wow! I hope JShrager
that you enjoy the Chaitin article. i am sure i will have more
questions and would like to hear your comments on the article. I
rewrote my function as below and it seems to work:
(defun f (x)
(let((y (cons (cons 'quote (cons x nil)) nil)))
(cons y (cons y nil))) )
producing from (f 'x) -> (('x) ('x))
Yes i snagged on the lambda syntax earlier but found the solution you
did.
but i can't do (f f) the second f error is 'the variable F is not
defined' I had to quote the x i used above in (f 'x)
so here is the next problem: he writes
[Now let's construct the fixed point.]
define (f x) let y [be] cons "' cons x nil [ y is ('x) ]
[return] cons y cons y nil [ return (('x)('x)) ]
OK TO HERE BUT WHAT IS THE NEXT define f value with all the
lambdas??? do i need to make this a function somehow?? I can't get (f
f) because of the ndefined variable f. i am missing a step. If you can
push me in the right direction i will be very appreciative.
define f
value (lambda (x) ((' (lambda (y) (cons y (cons y nil)))
) (cons ' (cons x nil))))
[Here we try f:]
(f x)
expression (f x)
value ((' x) (' x))
[Here we use f to calculate the fixed point:]
(f f)
expression (f f)
value ((' (lambda (x) ((' (lambda (y) (cons y (cons y ni
l)))) (cons ' (cons x nil))))) (' (lambda (x) (('
(lambda (y) (cons y (cons y nil)))) (cons ' (cons
x nil))))))
> If you know what you're doing, you can rewrite his examples for
> commonlisp, but you have to be careful, and know what you're doing.
Do you know what Lisp he is using? Scheme?? he does have a C code
download for a lisp interpreter for this excersize but i wanted to do
it in commonlisp if possible.
Thanks again, I'm off to sleep.
markandeya wrote:
>
> [Here we use f to calculate the fixed point:]
> (f f)
> expression (f f)
> value ((' (lambda (x) ((' (lambda (y) (cons y (cons y ni
> l)))) (cons ' (cons x nil))))) (' (lambda (x) (('
> (lambda (y) (cons y (cons y nil)))) (cons ' (cons
> x nil))))))
>
> > If you know what you're doing, you can rewrite his examples for
> > commonlisp, but you have to be careful, and know what you're doing.
> Do you know what Lisp he is using? Scheme?? he does have a C code
> download for a lisp interpreter for this excersize but i wanted to do
> it in commonlisp if possible.
> Thanks again, I'm off to sleep.
Using DEFINE and the expression (F F) are indicative of a Lisp-1
like Scheme, but if you're willing to fudge a little:
CL> (defparameter f (lambda (x) (list 'funcall x x)))
F
CL> (defmacro f (x) `(funcall f ,x))
F
CL> (f f)
(FUNCALL #'(LAMBDA (X) (LIST (QUOTE FUNCALL) X X))
#'(LAMBDA (X) (LIST (QUOTE FUNCALL) X X)))
CL> (eval (f f))
(FUNCALL #'(LAMBDA (X) (LIST (QUOTE FUNCALL) X X))
#'(LAMBDA (X) (LIST (QUOTE FUNCALL) X X)))
-----
Geoff
·········@gmail.com" <········@gmail.com> writes:
> Actually, I totally take it back. Although what I said above is
> correct, his scheme won't work for a different reason: He wants to use
> a quoted lambda in function position, which you can't do in Common
> Lisp. That is, he wants to do:
>
> (eval '('(lambda (x) (reverse x)) '(a s d f)))
>
> That won't work, but *this* will:
>
> (eval '((lambda (x) (reverse x)) '(a s d f)))
>
> [Note the missing ['] before the (lambda...)]
>
> If you know what you're doing, you can rewrite his examples for
> commonlisp, but you have to be careful, and know what you're doing.
The second form works as is in Common Lisp:
[27]> (eval '((lambda (x) (reverse x)) '(a s d f)))
(F D S A)
Note that Chaitin's code certainly did work on some old pre-Common Lisp LISP.
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
Pascal Bourguignon wrote:
> ·········@gmail.com" <········@gmail.com> writes:
> > ...
> > That won't work, but *this* will:
> >
> > (eval '((lambda (x) (reverse x)) '(a s d f)))
> > ...
>
> The second form works as is in Common Lisp:
>
> [27]> (eval '((lambda (x) (reverse x)) '(a s d f)))
> (F D S A)
Didn't I just say that? (That's what "...*this* will [work]:" means.)
·········@gmail.com" <········@gmail.com> writes:
> Pascal Bourguignon wrote:
>> ·········@gmail.com" <········@gmail.com> writes:
>> > ...
>> > That won't work, but *this* will:
>> >
>> > (eval '((lambda (x) (reverse x)) '(a s d f)))
>> > ...
>>
>> The second form works as is in Common Lisp:
>>
>> [27]> (eval '((lambda (x) (reverse x)) '(a s d f)))
>> (F D S A)
>
> Didn't I just say that? (That's what "...*this* will [work]:" means.)
Sorry. Hunger made me read it wrong. <*^.^*>
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?�
comme l'a formul� si adroitement notre ami Pascal, mais plut�t:
�Comment vais-je m'en tirer?� -- Jean Yanne
In article <························@m7g2000cwm.googlegroups.com>,
"markandeya" <·········@sriaurobindoashram.com> wrote:
> Dear Friends of Lisp,
> Cons-ing a quote with a symbol (x) to get ('x).
>
> i am reading Gregory Chaitin's "The Unknowable" on Goedels and Turings
> proofs of unprovability. (Free download) inwhich he uses "his" lisp to
> help prove and teach us these ideas. In chapter 3 beginning he tries to
> defun a fixed point using the syntax in the subject above (cons ' (cons
> '(x) nil)).
> i can't get clisp to accept this syntax of cons-ing the quote character
> to a symbol ( variable x)
' is not an object by itself, it's a reader macro that causes
'<something> to be read as (quote <something>). So I suspect that what
he intends is something like
(cons 'quote (cons '(x) nil))
> He want to get to (f f) becomes (('f) ('f)) where f is a function which
> evaluates to itself. SO (f x) becomes (('x) ('x)).
You can't do that with a Lisp function. The reason is that function
arguments are always evaluated, and the function receives the value of
the argument expression, not the literal expression. So f never sees f
or x, it just sees the value of the variables f or x.
> CAn anyone tell me how to do this in clisp or any other lisp please??
> Many thanks. i am fairly new to lisp and while i have done the
> preliminary recursive functions of set manipulation i can't figure out
> how to do this fixed point - to make a function that evaluates to
> itself. Chaitin says it is the clue (trick) to understanding Goedels
> theory/proof.
You need to use a macro, not a function:
(defmacro f (thing)
`(list '(',thing) '(',thing)))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***