From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.2 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id E5263BBAF for ; Tue, 27 May 2008 09:57:11 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AusCAMFbO0jAXQIniGdsb2JhbACCM5AHAQEBDyCVAIUm X-IronPort-AV: E=Sophos;i="4.27,547,1204498800"; d="scan'208";a="12761476" Received: from concorde.inria.fr ([192.93.2.39]) by mail1-smtp-roc.national.inria.fr with ESMTP; 27 May 2008 09:57:11 +0200 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m4R7v8fB008749 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Tue, 27 May 2008 09:57:11 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: An8OADJbO0jRVcipaWdsb2JhbACCM5AHDQQDBAkPBZR5hSc X-IronPort-AV: E=Sophos;i="4.27,547,1204498800"; d="scan'208";a="13081863" Received: from wf-out-1314.google.com ([209.85.200.169]) by mail3-smtp-sop.national.inria.fr with ESMTP; 27 May 2008 09:57:10 +0200 Received: by wf-out-1314.google.com with SMTP id 25so2289904wfa.0 for ; Tue, 27 May 2008 00:57:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; bh=mNkT1ExtdSJ7JVOSDZs0CvJoJ+W+ImsWX+Rsu1eTstk=; b=bTyfg64dKCgNhfLwCRwfrBmhBwQJVHkVI9+68A4Di9I2Gqxjwa+mhJRP14OhZ5fd5b5ukfpU53/jO2MPrfekq7O6YtrpWzOnqJMVfJ5eTVD46vWhdUurFYPtwi2OAQD7U17CScmb+pD1/tvRU+WuuXK65aCBiUcW3/TTDddvfIs= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=BcYfxlkxy//qTNPwmGF8/NFidxPD2PXNnzJnpB1jERyNzxxPDLiqeTmKitDRx+gLeH9SEC4TY6osBdDsTCFOccgZnGiQagrnnR05lsRNgaKikBZBfeS71oP7BCtsH0i3XLfv6UWTGdpPnTWLSmH3uBRagCxlvVovq+hEi0EsIFg= Received: by 10.142.191.2 with SMTP id o2mr376697wff.209.1211875028990; Tue, 27 May 2008 00:57:08 -0700 (PDT) Received: by 10.142.72.20 with HTTP; Tue, 27 May 2008 00:57:08 -0700 (PDT) Message-ID: <9d3ec8300805270057n46b5ea9fp4c3172e9d7f5efcd@mail.gmail.com> Date: Tue, 27 May 2008 08:57:08 +0100 From: "Till Varoquaux" To: "Jon Harrop" Subject: Re: [Caml-list] [ANN] OCaml-Java project: 1.0 release Cc: caml-list In-Reply-To: <200805270801.39081.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <764D4B4A-FA1E-4672-BA9D-4195193E1C48@x9c.fr> <200805270706.20939.jon@ffconsultancy.com> <9d3ec8300805262337o6cb390f0ma986212e065132d6@mail.gmail.com> <200805270801.39081.jon@ffconsultancy.com> X-Miltered: at concorde with ID 483BBED4.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursion:01 1.0:98 frog:98 wrote:01 wrote:01 stack:01 compile:01 caml-list:01 tail:01 tail:01 implemented:02 implemented:02 cps:02 therefor:03 overflow:03 On Tue, May 27, 2008 at 8:01 AM, Jon Harrop wrote: > On Tuesday 27 May 2008 07:37:40 Till Varoquaux wrote: >> On Tue, May 27, 2008 at 7:06 AM, Jon Harrop wrote: >> > 4. Are tail calls fully implemented and, if not, when exactly do they >> > work? >> >> One cannot fully implement tail calls on the JVM: there's no such >> thing as a goto or a tail call instruction. >> Tail recursion can usually be done for cheap. The general requires >> some expensive machinery (usually trampolines) > > What characteristics of tail calls cannot be implemented using trampolines? > Speed. I am sure you are aware of this but trampolining is very expensive [1]. A common trick to avoid using to much trampolining is to compile the whole program in cps form (therefor all calls are tail calls) and unwind the whole stack when we are about to overflow [2] Till [1] Tail call elimination on the Java Virtual Machine [2] CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. > -- > Dr Jon D Harrop, Flying Frog Consultancy Ltd. > http://www.ffconsultancy.com/products/?e > Tail call elimination on the Java Virtual Machine -- http://till-varoquaux.blogspot.com/