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: Adding Identities to Peval Date: Sat, 18 Feb 2012 11:20:01 -0500 Message-ID: References: <87mx8jjf0s.fsf@pobox.com> <87hayqkecl.fsf@pobox.com> <87zkchop17.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary=20cf30363ae7e7e6ab04b93f6e7e X-Trace: dough.gmane.org 1329582013 17359 80.91.229.3 (18 Feb 2012 16:20:13 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 18 Feb 2012 16:20:13 +0000 (UTC) Cc: guile-devel To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Feb 18 17:20:12 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Ryn19-0000PY-IK for guile-devel@m.gmane.org; Sat, 18 Feb 2012 17:20:11 +0100 Original-Received: from localhost ([::1]:56696 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ryn18-0002dH-UU for guile-devel@m.gmane.org; Sat, 18 Feb 2012 11:20:10 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:49821) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ryn15-0002aw-7g for guile-devel@gnu.org; Sat, 18 Feb 2012 11:20:08 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ryn13-0002V0-FI for guile-devel@gnu.org; Sat, 18 Feb 2012 11:20:07 -0500 Original-Received: from mail-iy0-f169.google.com ([209.85.210.169]:46182) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ryn13-0002TC-02 for guile-devel@gnu.org; Sat, 18 Feb 2012 11:20:05 -0500 Original-Received: by iagz16 with SMTP id z16so7260698iag.0 for ; Sat, 18 Feb 2012 08:20:02 -0800 (PST) Received-SPF: pass (google.com: domain of noah549@gmail.com designates 10.42.96.69 as permitted sender) client-ip=10.42.96.69; Authentication-Results: mr.google.com; spf=pass (google.com: domain of noah549@gmail.com designates 10.42.96.69 as permitted sender) smtp.mail=noah549@gmail.com; dkim=pass header.i=noah549@gmail.com Original-Received: from mr.google.com ([10.42.96.69]) by 10.42.96.69 with SMTP id i5mr2112728icn.48.1329582002612 (num_hops = 1); Sat, 18 Feb 2012 08:20:02 -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; bh=XS2e4YQzwaEEUyuW6TmIMZniLLDXddSSVL+sJ6ZXvks=; b=qlo+9QfQn0HppLNGvDuCPC9GOJrv47pMG5j55PKIz6QclqPTARj/R4EBwL//dViKUk mAgfyqET56bM+7awPAvyod4uweilEq8aEFD9jYYss/nMTbf1c8esQrazHuXvUOzA8Det fnNUCr6oFYo3+8IMY1kAy4oHW2vSp/BgkAWyw= Original-Received: by 10.42.96.69 with SMTP id i5mr1701569icn.48.1329582001612; Sat, 18 Feb 2012 08:20:01 -0800 (PST) Original-Received: by 10.42.142.7 with HTTP; Sat, 18 Feb 2012 08:20:01 -0800 (PST) In-Reply-To: <87zkchop17.fsf@pobox.com> X-Google-Sender-Auth: x3bqwyH2pHAmtZe_v7KWPyBXpLo X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. 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:13889 Archived-At: --20cf30363ae7e7e6ab04b93f6e7e Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Here is another patch that fixes the first of my examples. (let* ((x (random)) (y x)) (eq? x y)) now folds to (begin (random) #t). It turned out to be much smaller than the previous approach. Is it all right if I push this? I'm not sure how to make the other one work yet, but I will think about it. I will send a separate email about the CPS stuff. Noah On Fri, Feb 17, 2012 at 3:13 AM, Andy Wingo wrote: > Hi Noah, > > On Fri 17 Feb 2012 03:22, Noah Lavine writes: > >>>> (let* ((x (random)) >>>> =A0 =A0 =A0 =A0(y (list x)) >>>> =A0 =A0 =A0 =A0(z (car y)) >>>> =A0 (eq? x z)) >>> >> To make sure I understand, in the x-y-z example, psyntax would produce >> different gensyms for x and z, but peval could merge them later on, >> right? > > When processing `z' for value, it should reduce to `x'. =A0The strategy i= s > to do computation at compile time -- if at compile time, `z' can reduce > to `x', peval will do it. =A0But there is no global "give me all the > things that are equal to x" procedure. > >> In that case, peval would maintain the invariant "if two values must >> always be the same, they have the same gensym". Correct? > > More like the other way around! =A0If one identifier partially evaluates > to another, then they will have the same gensym, and therefore are the > same identifier. > >>> This is related to range analysis. =A0But, it's also something that's >>> easier to do with an explicit notion of control flow (i.e. a CPS IR). >> >> Yes, I think you're right. I would be very interested in working on a >> CPS IR, but I remember you had a blog post a couple months ago where >> you said you weren't sure if CPS or ANF was better for Guile. What do >> you think about intermediate representations now? > > I have no idea :-) I am a little hesitant to move to either one right > now, because our stack machine penalizes named temporaries, and with CPS > (or ANF -- which is closer to what we have, but without the advantage of > treating control flow on a first-class level) you would get a lot more > named temporaries. =A0But my uncertainty is also because I don't know wha= t > it would make the compiler look like. =A0Would it simplify things or woul= d > it add complication? =A0I don't know. > > But, writing a pass to turn tree-il into some CPS language would be a > really interesting step in any case. =A0If you wanted to work on that, I'= m > sure it would be instructive to us all. > > My humble thoughts :) > > Cheers, > > Andy > -- > http://wingolog.org/ --20cf30363ae7e7e6ab04b93f6e7e Content-Type: application/octet-stream; name="0001-Optimize-Equality-Primitives.patch" Content-Disposition: attachment; filename="0001-Optimize-Equality-Primitives.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_gysu1f1j0 RnJvbSAwN2UzYzRkNmY2NmJlNTM2OGZlNmQ3MGEyZGFjZWExMTM2YjUyMzY1IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb2FoIExhdmluZSA8bm9haC5iLmxhdmluZUBnbWFpbC5jb20+ CkRhdGU6IFNhdCwgMTggRmViIDIwMTIgMTA6NTU6NDkgLTA1MDAKU3ViamVjdDogW1BBVENIXSBP cHRpbWl6ZSBFcXVhbGl0eSBQcmltaXRpdmVzCgoqIG1vZHVsZS9sYW5ndWFnZS90cmVlLWlsL3By aW1pdGl2ZXMuc2NtOiBhZGQgZXF1YWxpdHktcHJpbWl0aXZlPywKICB3aGljaCBpcyB0cnVlIGZv ciBlcT8sIGVxdj8sIGFuZCBlcXVhbD8KKiBtb2R1bGUvbGFuZ3VhZ2UvdHJlZS1pbC9wZXZhbC5z Y206IGlmIGFuIGVxdWFsaXR5IHByaW1pdGl2ZSBpcwogIGFwcGxpZWQgdG8gdGhlIHNhbWUgdmFy aWFibGUgdHdpY2UsIGZvbGQgaXQgdG8gI3QKLS0tCiBtb2R1bGUvbGFuZ3VhZ2UvdHJlZS1pbC9w ZXZhbC5zY20gICAgICB8ICAgMTEgKysrKysrKysrKysKIG1vZHVsZS9sYW5ndWFnZS90cmVlLWls L3ByaW1pdGl2ZXMuc2NtIHwgICAxMSArKysrKysrKysrLQogMiBmaWxlcyBjaGFuZ2VkLCAyMSBp bnNlcnRpb25zKCspLCAxIGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL21vZHVsZS9sYW5ndWFn ZS90cmVlLWlsL3BldmFsLnNjbSBiL21vZHVsZS9sYW5ndWFnZS90cmVlLWlsL3BldmFsLnNjbQpp bmRleCA5YWFjMjRjLi5hNTg4YjY4IDEwMDY0NAotLS0gYS9tb2R1bGUvbGFuZ3VhZ2UvdHJlZS1p bC9wZXZhbC5zY20KKysrIGIvbW9kdWxlL2xhbmd1YWdlL3RyZWUtaWwvcGV2YWwuc2NtCkBAIC0x MTAzLDYgKzExMDMsMTcgQEAgdG9wLWxldmVsIGJpbmRpbmdzIGZyb20gRU5WIGFuZCByZXR1cm4g dGhlIHJlc3VsdGluZyBleHByZXNzaW9uLiIKICAgICAgICAgICgobmFtZSAuIGFyZ3MpCiAgICAg ICAgICAgKGZvbGQtY29uc3RhbnRzIHNyYyBuYW1lIGFyZ3MgY3R4KSkpKQogCisgICAgICAoKCQg PHByaW1jYWxsPiBzcmMgKD8gZXF1YWxpdHktcHJpbWl0aXZlPyBuYW1lKSAoYSBiKSkKKyAgICAg ICAobGV0ICgodmFsLWEgKGZvci12YWx1ZSBhKSkKKyAgICAgICAgICAgICAodmFsLWIgKGZvci12 YWx1ZSBiKSkpCisgICAgICAgICAobG9nICdlcXVhbGl0eS1wcmltaXRpdmUgbmFtZSB2YWwtYSB2 YWwtYikKKyAgICAgICAgIChjb25kICgoYW5kIChsZXhpY2FsLXJlZj8gdmFsLWEpIChsZXhpY2Fs LXJlZj8gdmFsLWIpCisgICAgICAgICAgICAgICAgICAgICAoZXE/IChsZXhpY2FsLXJlZi1nZW5z eW0gdmFsLWEpCisgICAgICAgICAgICAgICAgICAgICAgICAgIChsZXhpY2FsLXJlZi1nZW5zeW0g dmFsLWIpKSkKKyAgICAgICAgICAgICAgICAoZm9yLXRhaWwgKG1ha2UtY29uc3QgI2YgI3QpKSkK KyAgICAgICAgICAgICAgIChlbHNlCisgICAgICAgICAgICAgICAgKGZvbGQtY29uc3RhbnRzIHNy YyBuYW1lIChsaXN0IHZhbC1hIHZhbC1iKSBjdHgpKSkpKQorICAgICAgCiAgICAgICAoKCQgPHBy aW1jYWxsPiBzcmMgKD8gZWZmZWN0LWZyZWUtcHJpbWl0aXZlPyBuYW1lKSBhcmdzKQogICAgICAg IChmb2xkLWNvbnN0YW50cyBzcmMgbmFtZSAobWFwIGZvci12YWx1ZSBhcmdzKSBjdHgpKQogCmRp ZmYgLS1naXQgYS9tb2R1bGUvbGFuZ3VhZ2UvdHJlZS1pbC9wcmltaXRpdmVzLnNjbSBiL21vZHVs ZS9sYW5ndWFnZS90cmVlLWlsL3ByaW1pdGl2ZXMuc2NtCmluZGV4IGYxOTJjNGYuLjE1N2FhYTEg MTAwNjQ0Ci0tLSBhL21vZHVsZS9sYW5ndWFnZS90cmVlLWlsL3ByaW1pdGl2ZXMuc2NtCisrKyBi L21vZHVsZS9sYW5ndWFnZS90cmVlLWlsL3ByaW1pdGl2ZXMuc2NtCkBAIC0yOSw3ICsyOSw3IEBA CiAgICAgICAgICAgICBleHBhbmQtcHJpbWl0aXZlcyEKICAgICAgICAgICAgIGVmZmVjdC1mcmVl LXByaW1pdGl2ZT8gZWZmZWN0K2V4Y2VwdGlvbi1mcmVlLXByaW1pdGl2ZT8KICAgICAgICAgICAg IGNvbnN0cnVjdG9yLXByaW1pdGl2ZT8gYWNjZXNzb3ItcHJpbWl0aXZlPwotICAgICAgICAgICAg c2luZ2x5LXZhbHVlZC1wcmltaXRpdmU/KSkKKyAgICAgICAgICAgIHNpbmdseS12YWx1ZWQtcHJp bWl0aXZlPyBlcXVhbGl0eS1wcmltaXRpdmU/KSkKIAogKGRlZmluZSAqaW50ZXJlc3RpbmctcHJp bWl0aXZlLW5hbWVzKiAKICAgJyhhcHBseSBAYXBwbHkKQEAgLTIwNiw5ICsyMDYsMTMgQEAKICAg ICBieXRldmVjdG9yLWllZWUtZG91YmxlLW5hdGl2ZS1yZWYgYnl0ZXZlY3Rvci1pZWVlLWRvdWJs ZS1uYXRpdmUtc2V0IQogICAgIGYzMnZlY3Rvci1yZWYgZjMydmVjdG9yLXNldCEgZjY0dmVjdG9y LXJlZiBmNjR2ZWN0b3Itc2V0ISkpCiAKKyhkZWZpbmUgKmVxdWFsaXR5LXByaW1pdGl2ZXMqCisg ICcoZXE/IGVxdj8gZXF1YWw/KSkKKwogKGRlZmluZSAqZWZmZWN0LWZyZWUtcHJpbWl0aXZlLXRh YmxlKiAobWFrZS1oYXNoLXRhYmxlKSkKIChkZWZpbmUgKmVmZmVjdCtleGNlcHRpb25zLWZyZWUt cHJpbWl0aXZlLXRhYmxlKiAobWFrZS1oYXNoLXRhYmxlKSkKIChkZWZpbmUgKnNpbmdseS12YWx1 ZWQtcHJpbWl0aXZlLXRhYmxlKiAobWFrZS1oYXNoLXRhYmxlKSkKKyhkZWZpbmUgKmVxdWFsaXR5 LXByaW1pdGl2ZS10YWJsZSogKG1ha2UtaGFzaC10YWJsZSkpCiAKIChmb3ItZWFjaCAobGFtYmRh ICh4KQogICAgICAgICAgICAgKGhhc2hxLXNldCEgKmVmZmVjdC1mcmVlLXByaW1pdGl2ZS10YWJs ZSogeCAjdCkpCkBAIC0yMTksNiArMjIzLDkgQEAKIChmb3ItZWFjaCAobGFtYmRhICh4KSAKICAg ICAgICAgICAgIChoYXNocS1zZXQhICpzaW5nbHktdmFsdWVkLXByaW1pdGl2ZS10YWJsZSogeCAj dCkpCiAgICAgICAgICAgKnNpbmdseS12YWx1ZWQtcHJpbWl0aXZlcyopCisoZm9yLWVhY2ggKGxh bWJkYSAoeCkKKyAgICAgICAgICAgIChoYXNocS1zZXQhICplcXVhbGl0eS1wcmltaXRpdmUtdGFi bGUqIHggI3QpKQorICAgICAgICAgICplcXVhbGl0eS1wcmltaXRpdmVzKikKIAogKGRlZmluZSAo Y29uc3RydWN0b3ItcHJpbWl0aXZlPyBwcmltKQogICAobWVtcSBwcmltICpwcmltaXRpdmUtY29u c3RydWN0b3JzKikpCkBAIC0yMzAsNiArMjM3LDggQEAKICAgKGhhc2hxLXJlZiAqZWZmZWN0K2V4 Y2VwdGlvbnMtZnJlZS1wcmltaXRpdmUtdGFibGUqIHByaW0pKQogKGRlZmluZSAoc2luZ2x5LXZh bHVlZC1wcmltaXRpdmU/IHByaW0pCiAgIChoYXNocS1yZWYgKnNpbmdseS12YWx1ZWQtcHJpbWl0 aXZlLXRhYmxlKiBwcmltKSkKKyhkZWZpbmUgKGVxdWFsaXR5LXByaW1pdGl2ZT8gcHJpbSkKKyAg KGhhc2hxLXJlZiAqZXF1YWxpdHktcHJpbWl0aXZlLXRhYmxlKiBwcmltKSkKIAogKGRlZmluZSAo cmVzb2x2ZS1wcmltaXRpdmVzISB4IG1vZCkKICAgKGRlZmluZSBsb2NhbC1kZWZpbml0aW9ucwot LSAKMS43LjYKCg== --20cf30363ae7e7e6ab04b93f6e7e--