[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: address@hidden*Subject*: Re: in defense of types*From*: Lauri Alanko <address@hidden>*Date*: Sun, 2 Jun 2002 11:19:08 +0300*In-reply-to*: <200205300555.g4U5t5q13913@orchestra.cs.caltech.edu>*References*: <20020529172958.1945.qmail@mail.archub.org> <200205292327.g4TNRaL11580@orchestra.cs.caltech.edu> <6616qo7s.fsf@kldp.org> <200205300555.g4U5t5q13913@orchestra.cs.caltech.edu>*Sender*: address@hidden*User-agent*: Mutt/1.3.25i

On Wed, May 29, 2002 at 10:55:05PM -0700, Michael Vanier wrote: > BTW I'm not sure what you mean when you say that Y is not usable in eager > languages. You can define Y in scheme, which is eager. Do you mean in > eager statically-typed languages? You can _define_ Y, but it's not usable: (define y (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))) You can see why: (y f) -> ((lambda (x) (f (x x))) (lambda (x) (f (x x)))) -> (f ((lambda (x) (f (x x))) (lambda (x) (f (x x))))) -> (f (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))) -> ... Eager reduction requires that the argument in a function application is reduced to a value before beta reduction, and here the argument keeps on expanding. In Haskell, which uses lazy evaluation, you can use the trick with recursive types without resorting to eta expansion: newtype I a = I (I a -> a) y = \f -> (\(I x) -> (f (x (I x)))) (I (\(I x) -> (f (x (I x))))) And this works with _all_ values, not just functions: Y> :t y y :: (a -> a) -> a Y> y (\x -> 1 : x) [1,1,1,1,1,1,1,.... This would be a bit like saying (letrec ((l (cons 1 l))) l) in scheme. Ocaml, btw, has a fairly new extension, which allows just this, as long as the recursive expression is a constructor invocation: # let rec l = 1 :: l in l;; - : int list = [1; 1; 1; 1; 1; 1; 1; .... This is nice, but not very useful, since recursive data structures typically need more complicated initialization, and then you can't use the letrec structure and have to resort to mutable data. Lauri Alanko la@iki.fi

**Follow-Ups**:**RE: in defense of types***From:*matthias@ccs.neu.edu

**References**:**Re: in defense of types***From:*Paul Graham <pg@archub.org>

**Re: in defense of types***From:*Michael Vanier <mvanier@cs.caltech.edu>

**Re: in defense of types***From:*Jaeyoun Chung <jay@kldp.org>

**Re: in defense of types***From:*Michael Vanier <mvanier@cs.caltech.edu>

- Prev by Date:
**Re: Generalizing Types as Provable Invariants** - Next by Date:
**RE: in defense of types** - Previous by thread:
**Re: in defense of types** - Next by thread:
**RE: in defense of types** - Index(es):