From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p07JHdcD007550 for ; Fri, 7 Jan 2011 20:17:39 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvYEALf1Jk1XaqLJgWdsb2JhbACkKxUBARYiJLs5hUwEjic X-IronPort-AV: E=Sophos;i="4.60,290,1291590000"; d="scan'208";a="94794448" Received: from ka.mail.enyo.de ([87.106.162.201]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/AES256-SHA; 07 Jan 2011 20:17:34 +0100 Received: from [172.17.135.4] (helo=deneb.enyo.de) by ka.mail.enyo.de with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) id 1PbHoa-0002qm-Bz; Fri, 07 Jan 2011 20:17:32 +0100 Received: from fw by deneb.enyo.de with local (Exim 4.72) (envelope-from ) id 1PbHoa-0000uy-5A; Fri, 07 Jan 2011 20:17:32 +0100 From: Florian Weimer To: Dario Teixeira Cc: caml-list@inria.fr References: <699537.6718.qm@web111509.mail.gq1.yahoo.com> Date: Fri, 07 Jan 2011 20:17:32 +0100 In-Reply-To: <699537.6718.qm@web111509.mail.gq1.yahoo.com> (Dario Teixeira's message of "Fri, 7 Jan 2011 07:35:44 -0800 (PST)") Message-ID: <87vd20plpv.fsf@mid.deneb.enyo.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Subject: Re: [Caml-list] Purity and lazyness * Dario Teixeira: > So, my question is whether there is something I'm missing and in fact "purity > <=> lazyness", or I am reading too much from those Haskeller presentations, > because they never meant to say anything beyond "lazyness => purity", and > freely mixing the two was just a casual oversight. As specified, Haskell is not a pure language because every pattern match can have side effects. The Haskell community is split between those who think that this is a good thing, and those that consider it problematic. (Obviously, there is a large pure subset, much more useful than Erlang's pure subset and covering almost the whole language; you just avoid lazy I/O and use unsafePerformIO only for correcting the type of functions imported through FFI.) In my very limited experience, there are two kinds of laziness: essential laziness and laziness for presentation purposes. Essential laziness occurs when you construct values which would not otherwise be possible to construct in a pure language. For instance, if you have got some sort of compiler, at one point, you might want to perform name resolution. At that point, you want to translate names (references) to the program entities they denote (referents). In general, these references do not form a tree (for instance, a function body can refer to another function by name, which refers to the original function). With laziness, you can compute a map from names to entities, and the entities use this maps to resolve the names they use as references. Name lookup is only performed once per name. Without laziness, you have to perform name lookup each time you follow a reference because the self-referential nature of the data structure cannot be reflected in the program. The other type of laziness occurs when you write programs which work on large (perhaps even infinite) data structures, and carefully look only at the parts you need. This can lead to notationally elegant programs, but you have to be extremely careful not to keep references to parts you no longer need, otherwise your program will require too much memory (the live set might even be unbounded). Space retention behavior is quite implementation-dependent, too. It bothers me a bit that you cannot tell the first form from second just by looking at the types. You just don't know if the data structure is bounded or not.