[PRL] Type question...

[Felix S Klock II]

On Oct 3, 2007, at 11:33 PM, Riccardo Pucella wrote:

>>> (let ((fact (lambda (num)
>>>                 ((lambda (f n) (f f n))
>>>                  (lambda (g m)
>>>                    (if (< m 2) 1
>>>                        (* m (g g (- m 1))))) num))))
>>>    (fact 5))
>
>> I believe it's the (f f n) and (g g (- m 1)) that shoot you down.
>> There's no simple type for a function that accepts itself as an
>> argument.
>
> Right; as Carl says, just look at (lambda (f n) (f f n))
>
> The best type you could give it is the recursive type:
>    (\mu Z.( Z x a -> b)) x a -> b

Or a (sufficiently large) intersection type could also type the term,  
I believe.

But who wants to go down that road. . .

-Felix