Path: utzoo!attcan!uunet!aplcen!samsung!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!sics.se!sics!bjornl
From: bjornl@tds.kth.se (Bj|rn Lisper)
Newsgroups: comp.lang.functional
Subject: Re: Purity and Laziness
Message-ID: <BJORNL.90Jul26211631@tarpon.tds.kth.se>
Date: 26 Jul 90 19:16:31 GMT
References: <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <4170@castle.ed.ac.uk> <7044@ganymede.inmos.co.uk>
Sender: news@sics.se
Organization: The Royal Inst. of Technology (KTH), Stockholm, Sweden.
Lines: 30
In-Reply-To: geoffb@butcombe.inmos.co.uk's message of 25 May 90 09:56:09 GMT

In article <7044@ganymede.inmos.co.uk> geoffb@butcombe.inmos.co.uk (Geoff
Barrett) writes:
%I believe there is an Oxford DPhil thesis by a man called David Turner
%which pointed out that strict languages are not referentially
%transparent because of the fact that conditionals are not strict, so
%that the equality symbol in the definition

%	fun iiff (b,x,y) = if b then x else y

%is not equality.  Lazy evaluation languages are referentially
%transparent.  I think this is what the original poster meant by
%"purer".

Hmmm. How would a lazy language treat a call

if(b,x,x)

where the evaluation of b is non-terminating but the evaluation of x
terminates? If "naive" left-to-right evaluation order is assumed, the
computation will not terminate. On the other hand, it is reasonable to
define the semantics of the if-function so that such a call returns the
value of x. (After all, the value of x will be the answer regardless of what
b evaluates to). What about "referential transparency" here?

This problem is akin to left-to-right evaluation sensitivity of goals in
Prolog; the order of goals that are ANDed together in a Horn clause can
affect termination even though AND, considered as a "mathematical" binary
operation, is commutative.

Bjorn Lisper