From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: Compiler Branch Date: Sun, 08 Jan 2012 15:53:05 +0100 Message-ID: <877h12dz5a.fsf@pobox.com> References: <87wra0c0y5.fsf@pobox.com> <87mxa0iaxj.fsf@pobox.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1326034402 27457 80.91.229.12 (8 Jan 2012 14:53:22 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 8 Jan 2012 14:53:22 +0000 (UTC) Cc: guile-devel To: Noah Lavine Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 08 15:53:17 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 1Rju7Y-0000fY-9v for guile-devel@m.gmane.org; Sun, 08 Jan 2012 15:53:16 +0100 Original-Received: from localhost ([::1]:58812 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rju7X-0004sd-Sg for guile-devel@m.gmane.org; Sun, 08 Jan 2012 09:53:15 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:47680) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rju7U-0004sN-8F for guile-devel@gnu.org; Sun, 08 Jan 2012 09:53:13 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Rju7S-0003xL-P2 for guile-devel@gnu.org; Sun, 08 Jan 2012 09:53:12 -0500 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:45981 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rju7S-0003xH-KV for guile-devel@gnu.org; Sun, 08 Jan 2012 09:53:10 -0500 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id CCC0F729A; Sun, 8 Jan 2012 09:53:09 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=sasl; bh=Gzku0wDTq6We XKxa5CSp3EcKW7U=; b=WsMNZgRV+MEyp+RLv4pNVVhAFWIm6Htd/AQy6jHdz47f NXEgWbyjlp+SayNvqqhD8AkeeL/mJgscpebEqAJToBREOVLBC0SzBeN1hpJKPV/8 09VMEykKpAQXApdxku3TMv9+1JxClW9lQSKtRL9rHKr2yJVMHF9ZLYytVXzrTiI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=sasl; b=XkUnrK FM9frTKe7FZUO0/nbWaBLf1QYRqYwPXybiyUQAVl7Kr2EniXsG6N0f6R4qTKY/lc W7s071MGKol+YdrEqrt7ReSlBzEq16kAuXyYpFolFuA2Sbk13SgPAV9LcG9qLUpu n/tas3l6xDAQe8FBu6w59IzWpEWRnpf3dp2aY= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id C612B7299; Sun, 8 Jan 2012 09:53:09 -0500 (EST) Original-Received: from badger (unknown [90.164.198.39]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 0666A7298; Sun, 8 Jan 2012 09:53:08 -0500 (EST) In-Reply-To: (Noah Lavine's message of "Sat, 7 Jan 2012 19:42:14 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-Pobox-Relay-ID: 7AC61C6E-3A08-11E1-A30D-65B1DE995924-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 74.115.168.62 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:13439 Archived-At: Hi Noah :) On Sun 08 Jan 2012 01:42, Noah Lavine writes: > 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, Interesting. `verify' seems to be a form of contracts: http://ftp.ccs.northeastern.edu/scheme/pubs/icfp2002-ff.pdf Does `verify' have runtime semantics? Under what situations, if any, would the compiler insert runtime checks? As that paper indicates, two issues you will have to deal with are higher-order functions and blame. Your interest in static analysis naturally raises the question of types. You might like this paper: http://www.ccs.neu.edu/racket/pubs/dls06-tf.pdf I'm glad to hear of your interest in the problem, it's a good one. >> 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. Ah, I was just curious. I made some small changes relative to stable-2.0 (primcall and seq), and wondered if they were a good idea or not. I was also considering a move to a CPS-based intermediate language. Some links are here: http://wingolog.org/archives/2011/07/12/static-single-assignment-for-func= tional-programmers >> 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? =C2=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. Yes, this is my thought as well. Note also that peval is described by waddell and dybvig as being a kind of special-purpose sub-0CFA. > 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. Yes, that would be great. > Message 2: > >> This sounds cool. =C2=A0I assume you're familiar with kCFA? =C2=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'm still new to them too, so consider it a joint learning process :-) Note that the kCFA algorithms, though proven, are not the last word; see for example CFA2, http://arxiv.org/pdf/1102.3676. Dimitris Vardoulakis applied CFA2 to JavaScript last summer, in work at Mozilla. >> 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. Great. Happy hacking, Andy --=20 http://wingolog.org/