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