"Cristian Baboi" wrote:

It appears as if lambda calculus is defined by lambda calculus.

Yes. id (lambda calculus) = lambda calculus. You might try to point back to yourself when being asked who you are to see the advantage of this technique. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

"Cristian Baboi" wrote:

On Sat, 29 Dec 2007 16:01:51 +0200, Achim Schneider wrote:

...

"Cristian Baboi" wrote:

...

It appears as if lambda calculus is defined by lambda calculus.

...

Yes. id (lambda calculus) = lambda calculus. You might try to point back to yourself when being asked who you are to see the advantage of this technique.

The next question is if id is well defined. There is such a function ? How many of them ?

None at all. A thing is nothing but itself and won't ever be anything else, identity is implied by existence. I used id = (\x -> x) just as an arbitrary fixed point you can also recurse around to point back to lambda calculus, instead of eval. After all, id(eval) = eval, even if the first one is a compiler, the second one is an interpreter and the third one is your mind. you can also say (define (id x) (unquote (quote x))) or, in the esoteric domain, where -1 people can be in an elevator, (define (id x) (quote (unquote x))). If you dare, you can also write (define (id x) (car (cons x '())) It really doesn't matter, if you don't use map or fold or write or whatever you can just write x, and if you don't write an interpreter or something that needs to interpret on runtime, you can just write your code instead of eval. http://mitpress.mit.edu/sicp/full-text/sicp/book/node77.html In a moonlit night, turn your back to the screen and meditate about the funny annotated taichi pictured on top of the page. It pictures the unity in transcendence not the equivalence of opposites, by the way. You might also say that any expression of any axiomatic system revolves around the system in the void. Hell breaks loose here: http://en.wikipedia.org/wiki/Image:Lambda.svg Sorry, I got a significant part of my logic from a philosophy lexicon. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

On 29 Dec 2007, at 6:39 AM, Cristian Baboi wrote:

On Sat, 29 Dec 2007 13:30:03 +0200, Luke Palmer wrote:

...

On Dec 29, 2007 11:14 AM, Cristian Baboi wrote:

...

In The Implementation of Functional Programming Languages by S.P. Jones, section 2.5.3, page 32 it is written:

Eval [[*]] a b = a x b Eval [[*]] _|_ b = _|_ Eval [[*]] a _|_ = _|_

but in section 2.5.2 it is said that _|_ is an element of the value domain. What business does it have on the left side of the '=' ?

...

I don't know the book you're talking about, but I suspect that this is not a definition of a function in a language, but rather the denotational semantics for a function.

Yes. Eval is the thing that do that.

...

Just as mathematics is allowed to categorize all turing machines into two categories (those that halt and those that do not), even though to actually do this is impossible, so too can mathematics talk about what a function returns when given _|_, even though it is impossible in general to know when you actually do have _|_ or you're just waiting for a value.

What confused me is the Eval seems to be defined by recursion, but maybe it is not. It would have been clear if it was written

Eval [[*]] env = x where x is extended to handle _|_ The "recursivity" I was talking about is:

Eval([[\x.E]], env) a = Eval([[E]], env[x=a]) Eval([[E1 E2]],env) = Eval([[E1]],env) (Eval([[E2]],env))

It appears as if lambda calculus is defined by lambda calculus.

These are equations that Eval must satisfy, but the text call '=' 'define'

Right. There's a convention in CS that any object may be defined by giving a list of conditions, to which is implicitly added the understanding that the object in question is in some sense the `least' object satisfying those conditions. So Eval is `defined' by those equations in the sense that its graph is the least relation closed under the equations given. jcc