From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA00025; Fri, 31 Jan 2003 20:18:57 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA00169 for ; Fri, 31 Jan 2003 20:18:55 +0100 (MET) Received: from juvenileinstructor.com (woodboy.ne.client2.attbi.com [66.30.30.177]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h0VJIsf12938 for ; Fri, 31 Jan 2003 20:18:54 +0100 (MET) Received: by juvenileinstructor.com (Postfix, from userid 512) id 932F649A65; Fri, 31 Jan 2003 14:18:06 -0500 (EST) Date: Fri, 31 Jan 2003 14:18:06 -0500 From: Russ Ross To: caml-list@inria.fr Subject: Re: [Caml-list] @, List.append, and tail recursion Message-ID: <20030131191806.GA28910@juvenileinstructor.com> Mail-Followup-To: caml-list@inria.fr References: <11707E79-34C2-11D7-9ECD-000393BA7EBA@wetware.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.28i Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk I'd just like to agree with Brian on this. We seem to have a split in this thread and the two branches should be addressed separately: 1. Help with the specific case being mentioned. I think this has been addressed nicely with several helpful suggestions. 2. Discussions about solving this class of problems. Practical workarounds are an essential part of writing software, but eliminating the need for them is where the computer science comes into play. I was reading Paul Graham's "On Lisp" the other day and came across an example that made me cringe. He pointed to a simple Lisp code fragment and then rewrote it for performance, proudly pointing to the result as an example of what efficient Common Lisp looks like and claiming that the result is competitive with C for speed. That's great that the capability is there, but whenever there is a significant difference between the clean, simple way to do something and the efficient way to do it (where the primary different is language or compiler related, not a fundamental algorithm or data structure change) it indicates an opportunity to improve the language or compiler design. If a systematic rewrite can transform inefficient code into efficient code, why doesn't the language and/or compiler just do it for you or prevent the problem in the first place? (the answers "because it is hard to do" and "I don't see you doing it" are both equally valid, but let's consider the question rhetorical for now) In Graham's example (if I recall correctly) the solution involved annotating variable types (Lisp is dynamically typed) and transforming a recursive function to use an accumulator to allow tail recursion. Lisp is full of this pattern and it does make a big different in performance. ML is statically typed so one could argue that it fixes the first problem already (annotating the types effectively removes dynamic typing from the Lisp function) but the second is still there. Tail recursion is a powerful and efficient construct, but it still requires care on the part of the programmer to make sure that the calls are proper tail calls. I think there are many recursive functions which cannot be transformed easily into tail calls, but there is a large class of functions that can be mechanically transformed using techniques discussed here and elsewhere. I would be interested personally if anyone could point to papers or other resources about this topic. Right now I think there is some low-hanging fruit to be plucked--recognizing and transforming a few simple patterns (code that looks like List.map) would make a big difference in a lot of code. Handling more complex cases is undoubtedly harder, but I think the potential benefits are considerable. I appreciate everyone's input on this subject so far. I was attracted to Caml in the first place because it seemed to be one of the best examples of a language where writing code that is clean and natural coincides with writing code that is efficient. I hope that discussions like this can bridge the gap even more. - Russ p.s. I don't mean to sound critical of Paul Graham here--in the context of Common Lisp his examples were very valuable--he just nicely illustrated my point for me so I picked on him. On Fri, Jan 31, 2003 at 11:13:26AM -0600, Brian Hurt wrote: > I did get it the first time. I'm just using List.append to illustrate a > problem I'm having. > > The problem is *constructing* lists. If you can construct your list > backwards, fine- but if you can't, you end up either not being tail > recursive (and blowing up for long lists) or allocating the list twice. > Now minor uglification becomes major uglification. It'd be nicer just to > be able to be able to construct lists forwards instead of backwards. > > List.append is just an obvious example to be talking about, but the > problem is signifigantly more general. > > Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners