From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: ludo@gnu.org (Ludovic =?iso-8859-1?Q?Court=E8s?=) Newsgroups: gmane.lisp.guile.devel Subject: The wonders of partial evaluation Date: Fri, 09 Sep 2011 00:32:09 +0200 Message-ID: <87fwk6zmvq.fsf@gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1315521165 26568 80.91.229.12 (8 Sep 2011 22:32:45 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 8 Sep 2011 22:32:45 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Sep 09 00:32:41 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 1R1n9F-0002RK-42 for guile-devel@m.gmane.org; Fri, 09 Sep 2011 00:32:41 +0200 Original-Received: from localhost ([::1]:42176 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1n9B-0004JV-KY for guile-devel@m.gmane.org; Thu, 08 Sep 2011 18:32:37 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:44676) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1n97-0004JQ-Si for guile-devel@gnu.org; Thu, 08 Sep 2011 18:32:34 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R1n95-00009R-P2 for guile-devel@gnu.org; Thu, 08 Sep 2011 18:32:33 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:57546) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R1n95-00009L-8w for guile-devel@gnu.org; Thu, 08 Sep 2011 18:32:31 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1R1n93-0002Lj-Bs for guile-devel@gnu.org; Fri, 09 Sep 2011 00:32:29 +0200 Original-Received: from reverse-83.fdn.fr ([80.67.176.83]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 09 Sep 2011 00:32:28 +0200 Original-Received: from ludo by reverse-83.fdn.fr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 09 Sep 2011 00:32:28 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 70 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: reverse-83.fdn.fr X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 23 Fructidor an 219 de la =?iso-8859-1?Q?R=E9volutio?= =?iso-8859-1?Q?n?= X-PGP-Key-ID: 0xEA52ECF4 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 83C4 F8E5 10A3 3B4C 5BEA D15D 77DD 95E2 EA52 ECF4 X-OS: x86_64-unknown-linux-gnu User-Agent: Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:Kqe0LNoBXLf5R+m6aqVzpCWri0o= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 80.91.229.12 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:12747 Archived-At: Hello! Three days ago I had the chance to attend William Cook’s excellent tutorial on partial evaluation at DSL 2011, called “Build your own partial evaluator in 90 minutes” [0]. A few times 90 minutes later, I am pleased to announce a new partial evaluator for Tree-IL: http://git.sv.gnu.org/cgit/guile.git/commit/?h=stable-2.0&id=11671bbacbdd52039c77978bfe7f24a3316f6019 Partial evaluation is “the mother of all optimizations”, and in particular that of constant propagation and inlining. So that’s what the partial evaluator is here for. A few examples, showing code before and after partial evaluation: (let ((x 1) (y 2)) (+ x y)) => (const 3) (letrec ((even? (lambda (x) (or (= 0 x) (odd? (- x 1))))) (odd? (lambda (x) (not (even? (- x 1)))))) (and (even? 4) (odd? 7))) => (const #t) (letrec ((fibo (lambda (n) (if (<= n 1) n (+ (fibo (- n 1)) (fibo (- n 2))))))) (fibo 7)) => (const 13) Here all the values are known at compile-time, so the partial evaluator does basically the same job as ‘eval’. (let ((f (lambda (x y) (if (> x 0) y x)))) (+ (f -1 x) (f 2 y) (f z y))) => (let (f) (_) ((lambda (_) (lambda-case (((x y) #f #f #f () (_ _)) (if (apply (primitive >) (lexical x _) (const 0)) (lexical y _) (lexical x _)))))) (apply (primitive +) (const -1) ; (f -1 x) (toplevel y) ; (f 2 y) (apply (lexical f _) ; (f z y) (toplevel z) (toplevel y)))) Here calls to ‘f’ have been inlined 3 times and specialized twice. Isn’t it great? :-) Note that currently this only works with lexical bindings, not across top-level bindings–i.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. Please let me know if you suspect a compilation problem (partial evaluation can be turned off, see ‘optimize.scm’.) Feedback welcome! Ludo’. [0] http://www.cs.utexas.edu/~wcook/tutorial/