From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Noah Lavine Newsgroups: gmane.lisp.guile.devel Subject: Re: Compiler Branch Date: Sat, 7 Jan 2012 19:42:14 -0500 Message-ID: References: <87wra0c0y5.fsf@pobox.com> <87mxa0iaxj.fsf@pobox.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1325983347 24105 80.91.229.12 (8 Jan 2012 00:42:27 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 8 Jan 2012 00:42:27 +0000 (UTC) Cc: guile-devel To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 08 01:42:23 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Rjgq6-0001Oz-TU for guile-devel@m.gmane.org; Sun, 08 Jan 2012 01:42:23 +0100 Original-Received: from localhost ([::1]:47504 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rjgq6-0003mb-2P for guile-devel@m.gmane.org; Sat, 07 Jan 2012 19:42:22 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:42125) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rjgq2-0003mK-Ra for guile-devel@gnu.org; Sat, 07 Jan 2012 19:42:20 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Rjgq1-0008MI-7e for guile-devel@gnu.org; Sat, 07 Jan 2012 19:42:18 -0500 Original-Received: from mail-pw0-f41.google.com ([209.85.160.41]:50516) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rjgq0-0008MD-Px for guile-devel@gnu.org; Sat, 07 Jan 2012 19:42:17 -0500 Original-Received: by pbdd2 with SMTP id d2so2339469pbd.0 for ; Sat, 07 Jan 2012 16:42:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=kxaVmXXiSTNfvX78Xra7QgVDvuveyt+XUcmB47w5ypY=; b=Bqo3wfEQcYFpWm98QBKWlg5yDoT8QUSf0qzyw745Xf5oxwqwUukfQTTchByNOyeZ1u jGdGGDh3FOqvku1OFfo0pg8nigDRbiGdR31gqblrmuZ8SlRmVPZe7UNj/qrnOOChpO9Q 5bN7VQdng8vLnLnrURTmaKgGV5ngg4SwxQs9A= Original-Received: by 10.68.122.227 with SMTP id lv3mr27765495pbb.79.1325983334097; Sat, 07 Jan 2012 16:42:14 -0800 (PST) Original-Received: by 10.142.143.16 with HTTP; Sat, 7 Jan 2012 16:42:14 -0800 (PST) In-Reply-To: <87mxa0iaxj.fsf@pobox.com> X-Google-Sender-Auth: 71Qd0GdUIXR-CBH4fzBL9wH12Vs X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 209.85.160.41 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:13431 Archived-At: Hello, I'm going to try to combine the two parallel compiler threads into one, by replying to two messages at once. I hope this makes things simpler rather than more confusing. :-) Message 1: > Here is my calculus regarding this work, FWIW: it is low risk, and low > cost, since it doesn't actually affect Tree-IL or any other part of the > compiler. =A0The only cost it imposes is a coupling with Tree-IL, which i= s > easy enough to deal with on that side. =A0So that makes me much less > uneasy :-) And on the positive side, it has the potential to prove > interesting things, so at this point I'm neutral about it. =A0If it does > something useful, IMO we should throw it in, when you're ready for that. > Other people's opinions are welcome as well, of course. Well, I would hope to have it merged eventually. It will be a while before it's ready to do that, though. > Can you describe what the branch does, currently? So far it doesn't do any interesting analysis - it just has bookkeeping code and a very rough interface to an analyzer. The function called 'go' runs everything. You give it a Scheme expression. It compiles that expression to tree-il, then converts it to annotated-tree-il. Then it scans the annotated-tree-il looking for instances of the special function 'verify'. The idea of 'verify' is that if the analyzer can't prove that things in a verify always evaluate to true, it will throw a warning. It's a simple way to mark up your code with your expectations. For instance, (verify #t) always passes verification, and (verify #f) never passes. (verify (some-big-expression)) might or might not pass, depending on the expression and depending on how well we could analyze the program. I imagine that it would primarily be used for things like this: (define (map proc list) (verify (list? list)) ...) If your program didn't pass the verify check, you could still run it, but you probably shouldn't. > What do you see it doing within three months or so? Verifying statements, but with some actual inference. > How long do you intend to work on it? At least a year, and probably more if that's what it takes to make it do what I want. I would really like to make it usable and useful. > What do you think about the tree-il differences in master relative to > stable-2.0? I don't know what the differences are, since I just base all of the work on master. > Do you see this work as an optional pass, or a core part of the > compiler? If the latter, what sort of algorithmic complexity are you > envisioning for this work? =A0(O(n) in size of program is ideal of > course.) My first idea was to implement something equivalent to 0-CFA, which unfortunately has complexity O(n^3). If there's something that's faster and still produces useful results, that could be a good first step. However, I also think we could get the average-case time far below n^3 by doing inference on demand instead of calculating the type of every binding, similar to the change that peval went through a couple months ago. I think the complexity really determines how it could be used in the compiler. Ideally it would be very fast, and it could work as an extension to peval. If it's slower, it could only be used if the user requested that the compiler do more work. Either way, I'd like to see it help generate native code, and ideally native binaries. Message 2: > This sounds cool. =A0I assume you're familiar with kCFA? =A0See > http://matt.might.net/articles/implementation-of-kcfa-and-0cfa/, for > example. No, I hadn't read about it before. Thank you very much for the pointer! I admit that I am new to writing real compilers, so pointers to papers are great. I have now read the first part of Matt Might's thesis, where he describes k-CFA. 0-CFA is equivalent to what I was planning to do, I think, but his implementation is more elegant than what I had thought of. k >=3D 1 seems to have performance too slow to be useful to us. I also think k >=3D 1 does some wasted work in many common cases. I have ideas on how to fix this, but I suspect they're equivalent to the abstract garbage collection he talks about. In any case, I think 0-CFA is a good first step, and later I hope to get some variant of 1-CFA that does less work than full 1-CFA. > It doesn't seem to me that static analysis is a prerequisite for AOT > compilation -- and indeed, the current .go compilation is an example of > naive AOT compilation. Yes, excellent point. I was blurring two ideas together. I would eventually like this work to lead to an optimizing native-code compiler, so I am planning ahead for that. As a side note, you'll see that the current code is quite ugly in many ways. I used to think that the best choice was to do the analysis in a form very similar to Tree-IL, to keep from disturbing the program structure too much. Now I suspect that it would be best to use something like continuation-passing style, to keep the analyzer simpler. So I hope that you'll see more elegant-looking code soon. Best, Noah