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: Sun, 8 Jan 2012 16:15:47 -0500 Message-ID: References: <87wra0c0y5.fsf@pobox.com> <87mxa0iaxj.fsf@pobox.com> <877h12dz5a.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 1326057364 10301 80.91.229.12 (8 Jan 2012 21:16:04 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 8 Jan 2012 21:16:04 +0000 (UTC) Cc: guile-devel To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 08 22:15:58 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 1Rk05t-0007ov-O9 for guile-devel@m.gmane.org; Sun, 08 Jan 2012 22:15:58 +0100 Original-Received: from localhost ([::1]:35215 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rk05t-0006Jr-69 for guile-devel@m.gmane.org; Sun, 08 Jan 2012 16:15:57 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:44672) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rk05p-0006JV-RH for guile-devel@gnu.org; Sun, 08 Jan 2012 16:15:55 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Rk05k-0007tj-9v for guile-devel@gnu.org; Sun, 08 Jan 2012 16:15:53 -0500 Original-Received: from mail-iy0-f169.google.com ([209.85.210.169]:56034) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Rk05k-0007tV-4N for guile-devel@gnu.org; Sun, 08 Jan 2012 16:15:48 -0500 Original-Received: by iacb35 with SMTP id b35so6705644iac.0 for ; Sun, 08 Jan 2012 13:15:47 -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=YdyeSTFmnr7dhmatG5w640zgNuzF9JLZ7X2jEM+Yy+I=; b=HWQeVdcteO5KNVmrdXsIjb7b0ktEPQDKxWX9smCbQrEDRMlQ14/lht2uUbcEWOTLqN PdC0gk4z2EWD72VtBvxtvOAYlzLy/X7ftM4x/5Y0Hmsfd4ZIr+/vagogEvv3PtRWcP6k xm53JDB8rRGjBrNMZ208QT6q/59b2Ts8bp5OM= Original-Received: by 10.42.243.198 with SMTP id ln6mr10014493icb.29.1326057347165; Sun, 08 Jan 2012 13:15:47 -0800 (PST) Original-Received: by 10.43.51.132 with HTTP; Sun, 8 Jan 2012 13:15:47 -0800 (PST) In-Reply-To: <877h12dz5a.fsf@pobox.com> X-Google-Sender-Auth: XBte-xa0wJEXe2dnFx8JRetR6UA X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 209.85.210.169 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:13449 Archived-At: Hello, > Interesting. =A0`verify' seems to be a form of contracts: > > =A0http://ftp.ccs.northeastern.edu/scheme/pubs/icfp2002-ff.pdf > > Does `verify' have runtime semantics? =A0Under what situations, if any, > would the compiler insert runtime checks? It has no runtime semantics right now. I considered making it like 'assert', but I'm not sure that's right. I will look at that paper. > 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: > > =A0http://www.ccs.neu.edu/racket/pubs/dls06-tf.pdf I will look at that too; thank you. > Ah, I was just curious. =A0I 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: > > =A0http://wingolog.org/archives/2011/07/12/static-single-assignment-for-f= unctional-programmers Oh, this is interesting. I was just wondering if I needed a CPS-type representation to write the analyzer reasonably elegantly. If you think the main compiler also needs it, then perhaps I should work on that first, and then come back to the analyzer question. I do think there's a problem with plain CPS, though - it forces you to pick an order for the evaluation of function arguments. I would like to use CPS with some sort of parallel-call operator, so we can leave the order undefined (maybe at some point an optimizer will want to adjust the order). What do you think? I also noticed that at the end of that blog post you said you were considering ANF versus CPS for Guile (I assume you'd already decided that you didn't like Tree-IL). Does this mean you decided on CPS? >> 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. =A0Note also that peval is described by > waddell and dybvig as being a kind of special-purpose sub-0CFA. That makes sense. What I'd *really* like to do is make the analyzer use the same on-demand-calculation infrastructure as peval, but it might be really tricky to make them fit together. I am planning to leave that project for much later. Noah