From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Chris Gray Newsgroups: gmane.emacs.devel Subject: tail-call elimination Date: Mon, 10 Dec 2012 18:57:05 -0800 Message-ID: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary=20cf3010e3154aaa5f04d08ad6c7 X-Trace: ger.gmane.org 1355194643 30986 80.91.229.3 (11 Dec 2012 02:57:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 11 Dec 2012 02:57:23 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Dec 11 03:57:37 2012 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TiG2F-0007GO-Pn for ged-emacs-devel@m.gmane.org; Tue, 11 Dec 2012 03:57:32 +0100 Original-Received: from localhost ([::1]:44137 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiG23-0003g1-CB for ged-emacs-devel@m.gmane.org; Mon, 10 Dec 2012 21:57:19 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:60296) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiG1y-0003ei-Rb for emacs-devel@gnu.org; Mon, 10 Dec 2012 21:57:16 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TiG1r-000192-Js for emacs-devel@gnu.org; Mon, 10 Dec 2012 21:57:14 -0500 Original-Received: from mail-yh0-f52.google.com ([209.85.213.52]:36653) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TiG1r-00018q-8Y for emacs-devel@gnu.org; Mon, 10 Dec 2012 21:57:07 -0500 Original-Received: by mail-yh0-f52.google.com with SMTP id o22so715300yho.39 for ; Mon, 10 Dec 2012 18:57:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=pW04i/qzMgbaLbWCdQUhvHyGVhZrlyuv6CO0sFcrxBA=; b=HTDmpi1aER3EZebgj/J/K4/lLWSDraBQwPu7ac+1YkIaYe2bFimDNT6Yv/i8wy4fh9 7D3nj3LwrbgJe/kkSGRf+tlNHomH6meNVy5gfKCub2iZSdMEfpmeR1WNNWXldnBy+/U2 Tog4dppGBHHIyqjEB8RN2rnxTRsReufpoUsu/ppSXSy2FxxKZpypYC6zF4rzdpr0zQVK jUMbvPtlZ6Xq/hjlnNE9uns0wWVNNIIwZ2m72RnpwD6VpFXCyopx39oFnjhFdBXcjnga 8cueOWi//GtEVgssA5zLiWf9Uznc8tOnYwRrE//w+8aDm05nPz5RnMZfQbbkWDr+wte2 qVyQ== Original-Received: by 10.236.92.6 with SMTP id i6mr25897361yhf.40.1355194626124; Mon, 10 Dec 2012 18:57:06 -0800 (PST) Original-Received: by 10.101.110.11 with HTTP; Mon, 10 Dec 2012 18:57:05 -0800 (PST) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.213.52 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:155443 Archived-At: --20cf3010e3154aaa5f04d08ad6c7 Content-Type: multipart/alternative; boundary=20cf3010e3154aaa5a04d08ad6c5 --20cf3010e3154aaa5a04d08ad6c5 Content-Type: text/plain; charset=ISO-8859-1 Hello, I have attached a patch that implements tail-call elimination for a subset of emacs lisp. This will be helpful in allowing coding styles which emphasize tail recursion, such as is usual in languages like Scheme. The subset of emacs lisp that is targeted is compiled and lexically bound. There are some downsides to tail-call elimination. The most obvious is that debugging will be more complicated. Since the memory usage is not allowed to grow because of a tail call, the debug stack will not show the function that was called in the tail call. I think the benefits outweigh this, but I'm obviously biased. :) I'm also not a regular contributor to emacs, so please let me know if there is anything I need to do to the patch to get it accepted. Cheers, Chris --20cf3010e3154aaa5a04d08ad6c5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hello,

I have attached a patch that implements tail-call elimination= for a subset of emacs lisp.=A0 This will be helpful in allowing coding sty= les which emphasize tail recursion, such as is usual in languages like Sche= me.=A0
The subset of emacs lisp that is targeted is compiled and lexically bound.= =A0

There are some downsides to tail-call elimination.=A0 The most = obvious is that debugging will be more complicated.=A0 Since the memory usa= ge is not allowed to grow because of a tail call, the debug stack will not = show the function that was called in the tail call.=A0 I think the benefits= outweigh this, but I'm obviously biased. :)

I'm also not a regular contributor to emacs, so please let me know = if there is anything I need to do to the patch to get it accepted.

C= heers,
Chris
--20cf3010e3154aaa5a04d08ad6c5-- --20cf3010e3154aaa5f04d08ad6c7 Content-Type: application/octet-stream; name="tco.diff" Content-Disposition: attachment; filename="tco.diff" Content-Transfer-Encoding: base64 X-Attachment-Id: f_hakf8urb0 Y29tbWl0IGExMTI3MjhlMDhiN2VjMTE0ZGM2MDEwN2RiOTk0YmQzZTI3Y2M0YzYgKEhFQUQsIHJl ZnMvaGVhZHMvdGNvLTIpCkF1dGhvcjogQ2hyaXMgR3JheSA8Y2hyaXNtZ3JheUBnbWFpbC5jb20+ CkRhdGU6ICAgTW9uIERlYyAxMCAxODozNzowOCAyMDEyIC0wODAwCgogICAgQ2hhbmdlIGJ5dGVj b2RlIGludGVycHJldGVyIHRvIGFsbG93IGZvciB0YWlsLWNhbGwgZWxpbWluYXRpb24gaW4gc29t ZSBjYXNlcwoKCU1vZGlmaWVkIHNyYy9ieXRlY29kZS5jCmRpZmYgLS1naXQgYS9zcmMvYnl0ZWNv ZGUuYyBiL3NyYy9ieXRlY29kZS5jCmluZGV4IDRjNWFjMTUuLjk1NDQwOTAgMTAwNjQ0Ci0tLSBh L3NyYy9ieXRlY29kZS5jCisrKyBiL3NyYy9ieXRlY29kZS5jCkBAIC00NSw2ICs0NSw4IEBAIGJ5 IEhhbGx2YXJkOgogI2luY2x1ZGUgInh0ZXJtLmgiCiAjZW5kaWYKIAorTGlzcF9PYmplY3QgRmZl dGNoX2J5dGVjb2RlIChMaXNwX09iamVjdCk7CisKIC8qCiAgKiBkZWZpbmUgQllURV9DT0RFX1NB RkUgdG8gZW5hYmxlIHNvbWUgbWlub3Igc2FuaXR5IGNoZWNraW5nICh1c2VmdWwgZm9yCiAgKiBk ZWJ1Z2dpbmcgdGhlIGJ5dGUgY29tcGlsZXIuLi4pCkBAIC00ODEsOCArNDgzLDggQEAgSWYgdGhl IHRoaXJkIGFyZ3VtZW50IGlzIGluY29ycmVjdCwgRW1hY3MgbWF5IGNyYXNoLiAgKi8pCiAgICBl eGVjdXRpbmcgQllURVNUUi4gICovCiAKIExpc3BfT2JqZWN0Ci1leGVjX2J5dGVfY29kZSAoTGlz cF9PYmplY3QgYnl0ZXN0ciwgTGlzcF9PYmplY3QgdmVjdG9yLCBMaXNwX09iamVjdCBtYXhkZXB0 aCwKLQkJTGlzcF9PYmplY3QgYXJnc190ZW1wbGF0ZSwgcHRyZGlmZl90IG5hcmdzLCBMaXNwX09i amVjdCAqYXJncykKK2V4ZWNfYnl0ZV9jb2RlICh2b2xhdGlsZSBMaXNwX09iamVjdCBieXRlc3Ry LCB2b2xhdGlsZSBMaXNwX09iamVjdCB2ZWN0b3IsIHZvbGF0aWxlIExpc3BfT2JqZWN0IG1heGRl cHRoLAorCQl2b2xhdGlsZSBMaXNwX09iamVjdCBhcmdzX3RlbXBsYXRlLCB2b2xhdGlsZSBwdHJk aWZmX3QgbmFyZ3MsIExpc3BfT2JqZWN0ICphcmdzKQogewogICBwdHJkaWZmX3QgY291bnQgPSBT UEVDUERMX0lOREVYICgpOwogI2lmZGVmIEJZVEVfQ09ERV9NRVRFUgpAQCAtNDk4LDggKzUwMCwx MSBAQCBleGVjX2J5dGVfY29kZSAoTGlzcF9PYmplY3QgYnl0ZXN0ciwgTGlzcF9PYmplY3QgdmVj dG9yLCBMaXNwX09iamVjdCBtYXhkZXB0aCwKICAgcHRyZGlmZl90IGJ5dGVzdHJfbGVuZ3RoOwog I2VuZGlmCiAgIHN0cnVjdCBieXRlX3N0YWNrIHN0YWNrOwotICBMaXNwX09iamVjdCAqdG9wOwor ICBMaXNwX09iamVjdCAqdG9wID0gTlVMTDsKKyAgTGlzcF9PYmplY3QgKmJvdHRvbSA9IE5VTEw7 CiAgIExpc3BfT2JqZWN0IHJlc3VsdDsKKyAgam1wX2J1ZiBlbnY7CisgIHZvbGF0aWxlIExpc3Bf T2JqZWN0ICpmdW5hcmdzOwogCiAjaWYgMCAvKiBDSEVDS19GUkFNRV9GT05UICovCiAgewpAQCAt NTExLDkgKzUxNiwyMyBAQCBleGVjX2J5dGVfY29kZSAoTGlzcF9PYmplY3QgYnl0ZXN0ciwgTGlz cF9PYmplY3QgdmVjdG9yLCBMaXNwX09iamVjdCBtYXhkZXB0aCwKICB9CiAjZW5kaWYKIAorIGZ1 bmFyZ3MgPSB4bWFsbG9jIChuYXJncyAqIHNpemVvZihMaXNwX09iamVjdCkpOworIGZ1bmFyZ3Mg PSAqKHZvbGF0aWxlIExpc3BfT2JqZWN0ICopICZmdW5hcmdzOworICB7CisgICAgaW50IGk7Cisg ICAgZm9yIChpID0gMDsgaSA8IG5hcmdzOyBpKyspCisgICAgICB7CisgICAgICAgIGZ1bmFyZ3Nb aV0gPSBhcmdzW2ldOworICAgICAgfQorICB9CisgIHN0YWNrLm5leHQgPSBieXRlX3N0YWNrX2xp c3Q7CisgIGJ5dGVfc3RhY2tfbGlzdCA9ICZzdGFjazsKKworICBzZXRqbXAoZW52KTsKICAgQ0hF Q0tfU1RSSU5HIChieXRlc3RyKTsKICAgQ0hFQ0tfVkVDVE9SICh2ZWN0b3IpOwogICBDSEVDS19O QVROVU0gKG1heGRlcHRoKTsKKyAgYXJncyA9IGZ1bmFyZ3M7CiAKICNpZmRlZiBCWVRFX0NPREVf U0FGRQogICBjb25zdF9sZW5ndGggPSBBU0laRSAodmVjdG9yKTsKQEAgLTUzOCwxMiArNTU3LDEx IEBAIGV4ZWNfYnl0ZV9jb2RlIChMaXNwX09iamVjdCBieXRlc3RyLCBMaXNwX09iamVjdCB2ZWN0 b3IsIExpc3BfT2JqZWN0IG1heGRlcHRoLAogICBpZiAoTUFYX0FMTE9DQSAvIHdvcmRfc2l6ZSA8 PSBYRkFTVElOVCAobWF4ZGVwdGgpKQogICAgIG1lbW9yeV9mdWxsIChTSVpFX01BWCk7CiAgIHRv cCA9IGFsbG9jYSAoKFhGQVNUSU5UIChtYXhkZXB0aCkgKyAxKSAqIHNpemVvZiAqdG9wKTsKKwog I2lmIEJZVEVfTUFJTlRBSU5fVE9QCiAgIHN0YWNrLmJvdHRvbSA9IHRvcCArIDE7CiAgIHN0YWNr LnRvcCA9IE5VTEw7CiAjZW5kaWYKLSAgc3RhY2submV4dCA9IGJ5dGVfc3RhY2tfbGlzdDsKLSAg Ynl0ZV9zdGFja19saXN0ID0gJnN0YWNrOwogCiAjaWZkZWYgQllURV9DT0RFX1NBRkUKICAgc3Rh Y2tlID0gc3RhY2suYm90dG9tIC0gMSArIFhGQVNUSU5UIChtYXhkZXB0aCk7CkBAIC01OTUsNiAr NjEzLDggQEAgZXhlY19ieXRlX2NvZGUgKExpc3BfT2JqZWN0IGJ5dGVzdHIsIExpc3BfT2JqZWN0 IHZlY3RvciwgTGlzcF9PYmplY3QgbWF4ZGVwdGgsCiAgICAgICBlcnJvciAoIlVua25vd24gYXJn cyB0ZW1wbGF0ZSEiKTsKICAgICB9CiAKKyAgeGZyZWUgKGZ1bmFyZ3MpOworCiAgIHdoaWxlICgx KQogICAgIHsKICNpZmRlZiBCWVRFX0NPREVfU0FGRQpAQCAtODk0LDYgKzkxNCw0MiBAQCBleGVj X2J5dGVfY29kZSAoTGlzcF9PYmplY3QgYnl0ZXN0ciwgTGlzcF9PYmplY3QgdmVjdG9yLCBMaXNw X09iamVjdCBtYXhkZXB0aCwKIAkJICB9CiAJICAgICAgfQogI2VuZGlmCisgICAgICAgICAgICAv KiBJZiB0aGUgbmV4dCBvcCBpcyByZXR1cm4sIG1heWJlIHdlIGNhbiBlbGltaW5hdGUgdGhlIHRh aWwgY2FsbCAqLworICAgICAgICAgICAgaWYgKCpzdGFjay5wYyA9PSBCcmV0dXJuKQorICAgICAg ICAgICAgICB7CisgICAgICAgICAgICAgICAgTGlzcF9PYmplY3QgZnVuLCBvcmlnaW5hbF9mdW4s IHN5bXNfbGVmdDsKKyAgICAgICAgICAgICAgICBmdW4gPSBvcmlnaW5hbF9mdW4gPSBUT1A7Cisg ICAgICAgICAgICAgICAgCisgICAgICAgICAgICAgICAgaWYgKFNZTUJPTFAgKGZ1bikgJiYgIUVR IChmdW4sIFF1bmJvdW5kKQorICAgICAgICAgICAgICAgICAgICAmJiAoZnVuID0gWFNZTUJPTCAo ZnVuKS0+ZnVuY3Rpb24sIFNZTUJPTFAgKGZ1bikpKQorICAgICAgICAgICAgICAgICAgZnVuID0g aW5kaXJlY3RfZnVuY3Rpb24gKGZ1bik7CisgICAgICAgICAgICAgICAgaWYgKENPTVBJTEVEUChm dW4pKQorICAgICAgICAgICAgICAgICAgeworICAgICAgICAgICAgICAgICAgICBzeW1zX2xlZnQg PSBBUkVGIChmdW4sIENPTVBJTEVEX0FSR0xJU1QpOworICAgICAgICAgICAgICAgICAgICBpZiAo SU5URUdFUlAgKHN5bXNfbGVmdCkpCisgICAgICAgICAgICAgICAgICAgICAgeworICAgICAgICAg ICAgICAgICAgICAgICAgaW50IGk7CisgICAgICAgICAgICAgICAgICAgICAgICB2b2xhdGlsZSBM aXNwX09iamVjdCAqZnVuYXJnczI7CisgICAgICAgICAgICAgICAgICAgICAgICBpZiAoQ09OU1Ag KEFSRUYgKGZ1biwgQ09NUElMRURfQllURUNPREUpKSkKKyAgICAgICAgICAgICAgICAgICAgICAg ICAgRmZldGNoX2J5dGVjb2RlIChmdW4pOworICAgICAgICAgICAgICAgICAgICAgICAgYnl0ZXN0 ciA9IEFSRUYgKGZ1biwgQ09NUElMRURfQllURUNPREUpOworICAgICAgICAgICAgICAgICAgICAg ICAgdmVjdG9yID0gQVJFRiAoZnVuLCBDT01QSUxFRF9DT05TVEFOVFMpOworICAgICAgICAgICAg ICAgICAgICAgICAgbWF4ZGVwdGggPSBBUkVGIChmdW4sIENPTVBJTEVEX1NUQUNLX0RFUFRIKTsK KyAgICAgICAgICAgICAgICAgICAgICAgIGFyZ3NfdGVtcGxhdGUgPSBzeW1zX2xlZnQ7CisgICAg ICAgICAgICAgICAgICAgICAgICBuYXJncyA9IG9wOworICAgICAgICAgICAgICAgICAgICAgICAg ZnVuYXJnczIgPSB4bWFsbG9jIChuYXJncyAqIHNpemVvZihMaXNwX09iamVjdCkpOworICAgICAg ICAgICAgICAgICAgICAgICAgZnVuYXJncyA9ICoodm9sYXRpbGUgTGlzcF9PYmplY3QgKikgJmZ1 bmFyZ3MyOworICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpID0gMDsgaSA8IG5hcmdzOyBp KyspIHsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgZnVuYXJnc1tpXSA9IHRvcFtpICsgMV07 CisgICAgICAgICAgICAgICAgICAgICAgICB9CisgICAgICAgICAgICAgICAgICAgICAgICAvKiB1 c2VzIHNldGptcC9sb25nam1wIHJhdGhlciB0aGFuIGdvdG8gc28gdGhhdCB0aGUgZW1hY3MtbGlz cCBzdGFjaworICAgICAgICAgICAgICAgICAgICAgICAgICAgY2FuIGJlIGFsbG9jYXRlZCBvbiB0 aGUgQ1BVIHN0YWNrLiAgVGhpcyBpcyB3aGF0IHRoZSBnYXJiYWdlIGNvbGxlY3RvcgorICAgICAg ICAgICAgICAgICAgICAgICAgICAgYXNzdW1lcywgc28gaXQgaXMgcHJlZmVyYWJsZSB0byBjaGFu Z2luZyB0aGUgZ2FyYmFnZSBjb2xsZWN0b3IuCisgICAgICAgICAgICAgICAgICAgICAgICAqLwor ICAgICAgICAgICAgICAgICAgICAgICAgbG9uZ2ptcChlbnYsIDEpOworICAgICAgICAgICAgICAg ICAgICAgIH0KKyAgICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgICAgfQogCSAgICBUT1Ag PSBGZnVuY2FsbCAob3AgKyAxLCAmVE9QKTsKIAkgICAgQUZURVJfUE9URU5USUFMX0dDICgpOwog CSAgICBORVhUOwoJTW9kaWZpZWQgc3JjL2xpc3AuaApkaWZmIC0tZ2l0IGEvc3JjL2xpc3AuaCBi L3NyYy9saXNwLmgKaW5kZXggNWFjYjM3Zi4uMmJiOGUzOSAxMDA2NDQKLS0tIGEvc3JjL2xpc3Au aAorKysgYi9zcmMvbGlzcC5oCkBAIC0zNDAxLDggKzM0MDEsOCBAQCBleHRlcm4gc3RydWN0IGJ5 dGVfc3RhY2sgKmJ5dGVfc3RhY2tfbGlzdDsKIGV4dGVybiB2b2lkIG1hcmtfYnl0ZV9zdGFjayAo dm9pZCk7CiAjZW5kaWYKIGV4dGVybiB2b2lkIHVubWFya19ieXRlX3N0YWNrICh2b2lkKTsKLWV4 dGVybiBMaXNwX09iamVjdCBleGVjX2J5dGVfY29kZSAoTGlzcF9PYmplY3QsIExpc3BfT2JqZWN0 LCBMaXNwX09iamVjdCwKLQkJCQkgICBMaXNwX09iamVjdCwgcHRyZGlmZl90LCBMaXNwX09iamVj dCAqKTsKK2V4dGVybiBMaXNwX09iamVjdCBleGVjX2J5dGVfY29kZSAodm9sYXRpbGUgTGlzcF9P YmplY3QsIHZvbGF0aWxlIExpc3BfT2JqZWN0LCB2b2xhdGlsZSBMaXNwX09iamVjdCwKKwkJCQkg ICB2b2xhdGlsZSBMaXNwX09iamVjdCwgdm9sYXRpbGUgcHRyZGlmZl90LCBMaXNwX09iamVjdCAq KTsKIAogLyogRGVmaW5lZCBpbiBtYWNyb3MuYy4gICovCiBleHRlcm4gTGlzcF9PYmplY3QgUWV4 ZWN1dGVfa2JkX21hY3JvOwoK --20cf3010e3154aaa5f04d08ad6c7--