Path: utzoo!attcan!uunet!mcsun!ukc!edcastle!newshost!alti From: alti@staffa.ed.ac.uk (Thorsten Altenkirch) Newsgroups: comp.lang.functional Subject: Re: Laziness and Back-to-front Lists Message-ID: Date: 30 May 90 19:34:09 GMT References: <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <4170@castle.ed.ac.uk> <3738@moondance.cs.uq.oz.au> <4289@castle.ed.ac.uk> Organization: Laboratory for Foundations of Computer Science. Lines: 32 In-reply-to: bjornl@tds.kth.se's message of 29 May 90 14:58:42 GMT Bjorn's article reminds me on the following problem : In a lazy language we can define OR in two possible ways, s.t. it has the following behaviours : (_|_ = bottom) OR1 True _|_ = True OR2 True _|_ = _|_ OR1 _|_ True = _|_ OR2 _|_ True = True ... ... but there is no way to get the 'intended' behaviour : OR True _|_ = True OR _|_ True = True ... It is fairly obvious, that we need some sort of parallel evaluation to get the desired result. But even given that, it's not obvious what programming language construct would enable us to write 'symmetric' programs like OR. Candidates are the 'fair bottom avoiding merge' or more fundamently McCarthy's ambiguity operator [which applied to two arguments return's a value, if the evaluation of at least one of them terminates]. But both obviously destroy the Church-Rosser-Property ! Thorsten -- Thorsten Altenkirch JCMB Room 1404 JANET: alti@uk.ac.ed.lfcs LFCS, Dept. of Computer Science UUCP: ..!mcvax!ukc!lfcs!alti University of Edinburgh ARPA: alti%lfcs.ed.ac.uk@nsfnet-relay.ac.uk Edinburgh EH9 3JZ, UK. Tel: 031-667-1081 / 031 229 24 88 (p)