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 JAA17897; Mon, 3 May 2004 09:54:55 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA17882 for ; Mon, 3 May 2004 09:54:54 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i437spEV013585 for ; Mon, 3 May 2004 09:54:52 +0200 Received: from [192.168.1.200] (ppp116-155.lns1.syd2.internode.on.net [150.101.116.155]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id i437sjk2003399; Mon, 3 May 2004 17:24:47 +0930 (CST) Subject: Re: [Caml-list] [ANN] The Missing Library From: skaller Reply-To: skaller@users.sourceforge.net To: "Marcin 'Qrczak' Kowalczyk" Cc: caml-list In-Reply-To: <1083542538.9152.65.camel@qrnik> References: <200404280613.19547.jdh30@cam.ac.uk> <1083141467.9537.845.camel@pelican.wigram> <200404281018.14913.jdh30@cam.ac.uk> <1083151482.9537.904.camel@pelican.wigram> <93ADD9EA-9936-11D8-BD03-000A958FF2FE@wetware.com> <1083173516.9537.1162.camel@pelican.wigram> <1083542538.9152.65.camel@qrnik> Content-Type: text/plain; charset=UTF-8 Message-Id: <1083570883.20722.536.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 03 May 2004 17:54:44 +1000 Content-Transfer-Encoding: 8bit X-Miltered: at nez-perce with ID 4095FACB.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sourceforge:01 2004:99 marcin:01 'qrczak':01 kowalczyk:01 glue:01 reuse:01 glue:01 unification:01 recursively:01 recursion:01 fixpoint:01 closures:01 pointers:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 2004-05-03 at 10:02, Marcin 'Qrczak' Kowalczyk wrote: > W liście z czw, 29-04-2004, godz. 03:31 +1000, skaller napisał: > > > I have quite a lot of 'multi-pass' phases in my Felix compiler > > where i build temporary data structures in between. > > > > I'd love to glue some of these together to eliminate building > > whole data structures. > > I'm not sure it's worth the trouble. Neither am I, even given an easy way to do it. > There are two issues of compiler > phases: organization and efficiency. > > Concerning the organization, my opinion is that we do want to separate > it into several small phases, so each pass becomes easier to manage. How small though? > Trying to do too much at once sometimes requires to recompute the same > thing several times, because there is no convenient intermediate form > to store it for reuse, Oh, this is a perfect description of my horrible lookup algorithm! Originally, it was decoupled, but it didn't work. I've had to glue the whole thing together in a single operation because everything is so mutually recursive. For example: typing a function return value requires binding all the return statement expressions, which requires lookup, which requires binding all the function names in the expression, which requires overloading which requires binding the signatures of all the candidate functions.. one of which could be the original function you're trying to find the type of, and if it's that one you need to find its return types .. woops! That was the original problem :) i would like to augment the system so calls of the form: f x y z allow overloading on all arguments: at present you can only overload on the first one. Seems easy .. just extended application of the unification algorithm. Only it requires determining the return type of f, and not just the parameter type. The parameter type must be specified .. the return type does not. So I'd have to recursively calculate the return type. which is already problematic (see above) .. which might create yet another cycle if doing that called the overload resolution routine again with the same arguments .. I'm scared to even try it [There are 4 distinct entry points to the algorithm, and 4 distinct 'exclusion' lists marking them to prevent infinite recursion .. its never clear to me which list to reset and which one to push a new fixpoint onto, nor is it clear what to do when a cycle is detected.. > Also, lazy structures with some smart inversion of > control flow typically introduce an overhead of creating many closures > and calling many functions through pointers. At one stage I rewrote the 'token filter' part of Vyper using Ocaml streams. About 3 times slower I think. > | C coder which splits functions into > | fragments between calls (needed > | because of tail calls), Interested in how you handle tail calls in C. In theory this is easy, using goto. Unfortunately it requires generating a single massive function, and gcc is too much of a toy compiler to really trust with that. > The slowest part is currently the pretty printer. The slowest part of Felix is the lookup algorithm because of the really heavy (exponential time) recursion and lack of proper memoisation. -- John Skaller, mailto:skaller@users.sf.net voice: 061-2-9660-0850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net ------------------- 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