From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id A14E9BCA6 for ; Sun, 21 Oct 2007 12:25:48 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAAebGUfAXQImh2dsb2JhbACOVQEBAQgKKYEnkxA X-IronPort-AV: E=Sophos;i="4.21,303,1188770400"; d="scan'208";a="4881270" Received: from discorde.inria.fr ([192.93.2.38]) by mail3-smtp-sop.national.inria.fr with ESMTP; 20 Oct 2007 15:10:31 +0200 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l9KDAUVl008402 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sat, 20 Oct 2007 15:10:30 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAH6bGUeLEwECjGdsb2JhbACOVQEBAQgEBgkGGoEnkws X-IronPort-AV: E=Sophos;i="4.21,303,1188770400"; d="scan'208";a="3385706" Received: from ns2.mpi-inf.mpg.de (HELO francois.mpi-sb.mpg.de) ([139.19.1.2]) by mail1-smtp-roc.national.inria.fr with ESMTP; 20 Oct 2007 15:10:29 +0200 Received: from loopback.mpi-sb.mpg.de ([127.0.0.1]:35989 helo=localhost ident=amavis) by francois.mpi-sb.mpg.de (envelope-from ) with esmtp (Exim 4.50) id 1IjE61-0003sZ-6V for caml-list@inria.fr; Sat, 20 Oct 2007 15:10:29 +0200 Received: from francois.mpi-sb.mpg.de ([127.0.0.1]) by localhost (aspirin.mpi-sb.mpg.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 13856-01 for ; Sat, 20 Oct 2007 15:10:29 +0200 (CEST) Received: from mpiat0211.mpi-sb.mpg.de ([139.19.1.28]:37885 helo=zak.mpi-sb.mpg.de) by francois.mpi-sb.mpg.de (envelope-from ) with esmtp (Exim 4.50) id 1IjE60-0003s9-0y for caml-list@inria.fr; Sat, 20 Oct 2007 15:10:28 +0200 Received: from p54a59e8b.dip0.t-ipconnect.de ([84.165.158.139]:62610 helo=wiko) by zak.mpi-sb.mpg.de with esmtpsa (TLS-1.0:RSA_ARCFOUR_MD5:16) (Exim 4.50) id 1IjE5z-0002Lp-CE for caml-list@inria.fr; Sat, 20 Oct 2007 15:10:27 +0200 X-Notes-Item: NOT CHECKED; name=$DNSBLSite Message-ID: <004601c8131a$9a2e6b70$14b2a8c0@wiko> From: "Andreas Rossberg" To: References: <200710181457.58077.jon@ffconsultancy.com> <47176C28.1090509@janestcapital.com> <200710181818.31430.jon@ffconsultancy.com> <20071019152311.25cdf410.mle+ocaml@mega-nerd.com> <4718A220.4030708@univ-savoie.fr> <4718C3AA.9050503@fischerventure.com><4234F84D-BEC4-4850-B051-D38E8EA38918@mpi-sws.mpg.de> <471926F8.2010809@fischerventure.com> Subject: Re: [Caml-list] Re: Help me find this pdf Date: Sat, 20 Oct 2007 15:10:34 +0200 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=response Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.3138 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.3198 X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at mpi-sb.mpg.de X-Miltered: at discorde with ID 4719FE46.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; rossberg:01 rossberg:01 haskell:01 semantically:01 bug:01 bug:01 high-level:01 iirc:01 monads:01 semantics:01 deallocated:01 haskell:01 semantically:01 compiler:01 high-level:01 "Robert Fischer" wrote: > >> 1. Purity and evaluation regime are separate issues. You can very well >> have a pure language that is eager. > The way I understand it, the omnipresent laziness of Haskell is at least > partly justified because it is a way of encouraging being functionally > pure. Is that wrong? I guess you are alluding to SPJ's famous quote that "one advantage of laziness is that it keeps the language designer honest". But that wasn't its motivation, rather a tongue in cheek observation, made after more than a decade of language evolution. >> 6. Nevertheless, evaluation is fully deterministic, thus it certainly >> cannot cause Heisenbugs, neither semantically nor performance-wise. > If I put in a debug statement, it will like change the timing when > something gets forced, right? This, in turn, can change all kinds of > time/space performance characteristics, and potentially even the code that > is executed (through interrupting deforestation). So your debugging > statements might well change the very characteristic of the program that > you're defining as a bug. In an (otherwise pure) language, (even impure) debug output cannot hide a bug that is present without it. You are right that it can change the performance characteristics of a program by inducing additional strictness. But debug outputs are rather useless for performance tuning anyway, for which you would use more high-level tools. "Jon Harrop" wrote: > >> 1. Purity and evaluation regime are separate issues. You can very >> well have a pure language that is eager. > > IIRC, you then need the option of laziness to be able to implement all > programs with the same asymptotic complexity as impure/eager or pure/lazy. Even with laziness you cannot always achieve the same complexity in a pure language, unless you have something like built-in state monads giving you constant-time update in a pure fashion - which is independent from laziness. >> 2. However, in a pure language the details of evaluation order are >> largely immaterial to its semantics, which obviously is an advantage. > > I'm not sure that unknown evaluation order is an "obvious" advantage in > general. For example, when evaluating "f && g" where f is O(1) and g is > O(n!) you might want to know that "f" gets evaluated first. I didn't say it is an advantage if you don't know. It is an advantage if you don't *have to* know. >> 3. Lazy evaluation by itself is as precise an evaluation scheme as >> eager evaluation. There is no inherent vagueness. > > Does a thunk preventing a large data structure from being deallocated > count as "inherent vagueness"? I don't think so. At least in principle, you always know when something is evaluated. In practice that can be hard to determine, of course, but that doesn't make it "vague". The vagueness of garbage collection itself is a different issue that is not addressed in any major language I am aware of. >> 5. The problem with Haskell and laziness on the other hand is not >> semantic bugs, but the fact that it can make space complexity hard to >> predict sometimes. > > And time performance hard or impossible to achieve. Evaluating a given expression lazily can never take more steps than evaluating it eagerly. So in principle, achieving a certain time complexity is no harder than under eager evaluation (everything else being equal). But when you try to be smarter and actually exploit laziness you can certainly run into surprises. >> 6. Nevertheless, evaluation is fully deterministic, thus it certainly >> cannot cause Heisenbugs, neither semantically nor performance-wise. > > Perhaps I've missed something but surely evaluation order can alter > asymptotic complexity? If so, moving from one compiler to another can > change the asymptotic complexity of your program? Well, that is a slightly different issue. Of course, certain high-level optimizations can cut down the complexity of programs. If you move to a compiler that does not perform them you may see a complexity increase. However, the naive unoptimized semantics will always be the upper bound. On the other hand, this is simply an instance of a general problem you see with many languages: the more aggressive your compilers are the more careful you have to be with assumptions regarding performance that you rely on for coding. - Andreas