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: The wonders of partial evaluation Date: Thu, 8 Sep 2011 18:59:09 -0400 Message-ID: References: <87fwk6zmvq.fsf@gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1315522760 3538 80.91.229.12 (8 Sep 2011 22:59:20 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 8 Sep 2011 22:59:20 +0000 (UTC) Cc: guile-devel@gnu.org To: =?ISO-8859-1?Q?Ludovic_Court=E8s?= Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Sep 09 00:59:16 2011 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 1R1nYy-0005yT-99 for guile-devel@m.gmane.org; Fri, 09 Sep 2011 00:59:16 +0200 Original-Received: from localhost ([::1]:45065 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1nYx-0007O1-SU for guile-devel@m.gmane.org; Thu, 08 Sep 2011 18:59:15 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:43867) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1nYu-0007Nr-0f for guile-devel@gnu.org; Thu, 08 Sep 2011 18:59:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R1nYs-0004Wx-J8 for guile-devel@gnu.org; Thu, 08 Sep 2011 18:59:11 -0400 Original-Received: from mail-yi0-f41.google.com ([209.85.218.41]:41398) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1nYs-0004Wq-Gi; Thu, 08 Sep 2011 18:59:10 -0400 Original-Received: by yic24 with SMTP id 24so404958yic.0 for ; Thu, 08 Sep 2011 15:59:09 -0700 (PDT) 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=yE0y5Iu6FI8NhV+dSNNfiInIf3ni5U0f+JLEKZIL/Ik=; b=mAdEOpEAG2xW7GExVSIMu7JjAg0zp/b44+CQN5QUU2JFj8PS0ugZ+47tD6Ji973jL5 WM0uIsi3luzI4H5nRy+ozCU/4uxAklO3ljRt9msddZJty5YlUEDZss5ojzGuCXdYXzpw PUbclfrrHt9YvhNt0OHivYYvPTTVInNic36no= Original-Received: by 10.42.132.200 with SMTP id e8mr508217ict.518.1315522749222; Thu, 08 Sep 2011 15:59:09 -0700 (PDT) Original-Received: by 10.43.131.6 with HTTP; Thu, 8 Sep 2011 15:59:09 -0700 (PDT) In-Reply-To: <87fwk6zmvq.fsf@gnu.org> X-Google-Sender-Auth: 0bvO7-BvOPHlYjhSylpFKPUIE7w X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 209.85.218.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:12748 Archived-At: This is excellent! Congratulations! An interesting note from my current project: a partial evaluator means you don't have to use macros to define the PEG parser (while keeping exactly the same efficiency as now): instead of having (define-peg pattern) be a macro that analyzes pattern and outputs code, you have, (interpret-peg pattern string) be a program that parses string with peg. Then to generate code, you just partially apply interpret-peg to pattern, leaving string undetermined. (I'm not sure if the partial evaluator currently does this, but it would be an interesting approach.) Noah On Thu, Sep 8, 2011 at 6:32 PM, Ludovic Court=E8s wrote: > Hello! > > Three days ago I had the chance to attend William Cook=92s excellent > tutorial on partial evaluation at DSL 2011, called =93Build your own > partial evaluator in 90 minutes=94 [0]. > > A few times 90 minutes later, I am pleased to announce a new partial > evaluator for Tree-IL: > > =A0http://git.sv.gnu.org/cgit/guile.git/commit/?h=3Dstable-2.0&id=3D11671= bbacbdd52039c77978bfe7f24a3316f6019 > > Partial evaluation is =93the mother of all optimizations=94, and in > particular that of constant propagation and inlining. =A0So that=92s what > the partial evaluator is here for. =A0A few examples, showing code before > and after partial evaluation: > > =A0(let ((x 1) (y 2)) (+ x y)) > =A0=3D> (const 3) > > =A0(letrec ((even? (lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(or (=3D 0 x) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(odd? (- x 1))))) > =A0 =A0 =A0 =A0 =A0 (odd? =A0(lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(not (even? (- x 1)))))) > =A0 =A0(and (even? 4) (odd? 7))) > =A0=3D> (const #t) > > =A0(letrec ((fibo (lambda (n) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (if (<=3D n 1) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 n > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (+ (fibo (- n 1)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(fibo (- n 2))))))) > =A0 =A0(fibo 7)) > =A0=3D> (const 13) > > Here all the values are known at compile-time, so the partial evaluator > does basically the same job as =91eval=92. > > =A0(let ((f (lambda (x y) (if (> x 0) y x)))) > =A0 =A0(+ (f -1 x) (f 2 y) (f z y))) > =A0=3D> (let (f) (_) > =A0 =A0 =A0 =A0 =A0((lambda (_) > =A0 =A0 =A0 =A0 =A0 =A0 (lambda-case > =A0 =A0 =A0 =A0 =A0 =A0 =A0(((x y) #f #f #f () (_ _)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 (if (apply (primitive >) (lexical x _) (const= 0)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lexical y _) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lexical x _)))))) > =A0 =A0 =A0 =A0 =A0(apply (primitive +) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (const -1) =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0; (f -1 x) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (toplevel y) =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0; (f 2 y) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (apply (lexical f _) =A0 =A0 =A0 =A0 =A0 = =A0 =A0; (f z y) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(toplevel z) (toplevel y))= )) > > Here calls to =91f=92 have been inlined 3 times and specialized twice. > > Isn=92t it great? =A0:-) > > Note that currently this only works with lexical bindings, not across > top-level bindings=96i.e., a top-level binding never gets inlined. > > Of course the main difficulty is to make sure it behaves correctly in > the presence of effects. =A0Please let me know if you suspect a > compilation problem (partial evaluation can be turned off, see > =91optimize.scm=92.) > > Feedback welcome! > > Ludo=92. > > [0] http://www.cs.utexas.edu/~wcook/tutorial/ > > >