News for hackers. Stuff that matters.
Re:λ Calculus [pdf] by tromp on Friday August 18, 2023 @08:32AM (#37174765)
The number representation proposed by the author is one I've never seen before:

    |0|   = λx. x
    |n+1| = λ_. |n|
In other words, 0 is identity, and successor is the const function. This makes the predecessor function easy to define. Just apply Succ n to anything to get n back. The article fails to answer the most crucial question about these numerals though:

Can we write a function that tests if a numeral represents 0? I.e. a function f such that

    f |0| = True
    f |n+1| = False
If one cannot, then these numerals don't seem to be useful in any way, and don't deserve to be called a number representation.
Re:λ Calculus [pdf] by librexpr on Friday August 18, 2023 @09:49AM (#37175581)
I'm pretty sure it's impossible to write a function that tests for zero for these numerals. Necessarily, any such function f(|n|) would have to expand at some point into a toplevel |n|(args...) with some number of args. This call must be toplevel, not as an argument to another function, because otherwise it is lazy and not executed. The number of args also cannot be infinite, since that would require an infinitely large program.

The expansion into |n|(args...) must happen before we know what n is, because in the lambda calculus we can't know anything about a function without calling it. Since it happens before we know what n is, then the number of args will necessarily be the same for all n. When n > numargs, |n|(args...) ignores all its arguments and halts, and therefore f cannot be a useful test for zero.

Re:λ Calculus [pdf] by tromp on Friday August 18, 2023 @10:00AM (#37175719)
Thanks; you confirmed my suspicion. This is not a useful number representation.

> When n > numargs, |n|(args...) ignores all its arguments and halts

I would say it reduces to a term of the form \_. \_. M that is definitely different from both False and True.

Re:λ Calculus [pdf] by tromp on Sunday August 20, 2023 @05:17AM (#37197471)
> Necessarily, any such function f(|n|) would have to expand at some point into a toplevel |n|(args...)

Actually, this is not true. f |n| could expand into \x. \y. (|n| args...) instead, where the args contain x and y. But the rest of your argument still applies to the application of |n|.

Re:λ Calculus [pdf] by librexpr on Sunday August 20, 2023 @06:55AM (#37197943)
You're right, that was imprecise of me. But if F = (\x. \y. (|n| args...)) is equivalent to True or False, then it is also equivalent to (F True False), which brings us back to a toplevel (|n| args...).

Another slight correction/expansion is that (|n| args...) = n - numargs when n >= numargs. This happens to coincide with False when n = numargs + 1, so it would have been better if I had said "when n > numargs + 1".

[dead]
Re:λ Calculus [pdf] by tromp on Sunday August 20, 2023 @05:33AM (#37197562)
I sent an email to the professor that taught the course in 2011 asking for clarification...