From www@deja.com Mon Feb 14 20:09:18 2000 Message-ID: <889nnl$1se$1@nnrp1.deja.com> From: oleg@pobox.com Subject: Self-referential values and expressiveness of strict vs. non-strict languages Date: Mon, 14 Feb 2000 20:14:49 GMT Reply-To: oleg@pobox.com Keywords: self-reference, cyclic structure, lazy computation, expressiveness, Haskell, Scheme Newsgroups: comp.lang.scheme,comp.lang.functional Summary: of pure functional languages, only non-strict ones can express self-referential values X-Article-Creation-Date: Mon Feb 14 20:14:49 2000 GMT X-Comment: updated based on follow-ups Status: OR Certain types can be fully specified by their constructors -- generating functions. That is certainly true of algebraic types in ML or Haskell with one data constructor, immutable types of many languages; and of some types in Scheme. For example, every possible string can be generated by applying a function 'string' to appropriate arguments. The case of vectors and lists is more complex. Consider the following value: (define (make-vc) (let ((v (vector 0 1))) (vector-set! v 0 v) v)) (define vc (make-vc)) (vector? vc) ==> #t (vector-ref (vector-ref (vector-ref vc 0) 0) 1) ==> 1 vc is a vector (which is better left unprinted). It is obvious that no application of function 'vector' can produce 'vc'. Indeed, Scheme is a strict language. The value yielded by a function is computed strictly after all argument expressions have been evaluated. Therefore, an argument expression cannot refer to the value of a function it is an argument of. A lazy computation helps, however. Consider an implementation of Scheme where primitives that require a value implicitly 'force' their arguments. This behavior is specifically allowed in R5RS. We can write then: (define (make-lvc) (vector (delay (make-lvc)) 1)) (define lvc (make-lvc)) (vector? lvc) ==> #t (vector-ref (vector-ref (vector-ref lvc 0) 0) 1) ==> 1 Vector 'lvc' is a true vector, which is functionally equivalent to 'vc' above. Note that lvc is produced by a single application of a vector constructor. Therefore, the function 'vector' is now capable of constructing every possible vector value, even a self-referential one. The body of make-lvc is a purely functional expression. P.S. There is the other way to lazily construct a self-referential vector. Rather than delay an argument expression, we can delay the construction. (define lvc1 (delay (vector lvc1 1))) (vector-ref (vector-ref (vector-ref lvc1 0) 0) 1) ==> 1 The equivalent Haskell code is: data SRPair a = SRpair (SRPair a) a srl = SRpair srl 1 pfst :: SRPair a -> SRPair a pfst (SRpair x _) = x psnd :: SRPair a -> a psnd (SRpair _ y) = y psnd (pfst (pfst srl)) ==> 1