From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 4AB83BC37 for ; Wed, 16 Dec 2009 07:26:12 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtoCAL8MKEs+BBB0gmdsb2JhbACBS5l9AQELCwgHFQO5L4IsgX8E X-IronPort-AV: E=Sophos;i="4.47,404,1257116400"; d="scan'208";a="42102081" Received: from smtp-116-tuesday.nerim.net (HELO maiev.nerim.net) ([62.4.16.116]) by mail1-smtp-roc.national.inria.fr with ESMTP; 16 Dec 2009 07:26:12 +0100 Received: from hector.lesours (ours.starynkevitch.net [213.41.244.95]) by maiev.nerim.net (Postfix) with ESMTP id 80C45B8460; Wed, 16 Dec 2009 07:26:11 +0100 (CET) Received: from glinka.lesours ([192.168.0.1]) by hector.lesours with esmtp (Exim 4.69) (envelope-from ) id 1NKnL5-0000mN-Io; Wed, 16 Dec 2009 07:26:23 +0100 Message-ID: <4B287D84.201@starynkevitch.net> Date: Wed, 16 Dec 2009 07:26:12 +0100 From: Basile STARYNKEVITCH User-Agent: Mozilla-Thunderbird 2.0.0.22 (X11/20091109) MIME-Version: 1.0 To: David Allsopp Cc: 'Eray Ozkural' , caml-list@inria.fr Subject: Re: [Caml-list] How to write a CUDA kernel in ocaml? References: <320e992a0912150737t483a5946x9cad351fc344691f@mail.gmail.com> <4B27B442.9030300@starynkevitch.net> <320e992a0912150820l4d36e4e0s24dc7cc084c9fc29@mail.gmail.com> <4B27B981.80700@starynkevitch.net> <017101ca7ddc$fb936b20$f2ba4160$@allsopp@metastack.com> In-Reply-To: <017101ca7ddc$fb936b20$f2ba4160$@allsopp@metastack.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; basile:01 basile:01 ocaml:01 eray:01 ozkural:01 ocaml:01 recursive:01 recursion:01 recursive:01 recursion:01 translating:01 ocamlopt:01 rax:01 rax:01 translated:01 David Allsopp wrote: > Basile Starynkevitch wrote: >> Eray Ozkural wrote: >> >> Compiling Ocaml to efficient C is not easy and probably impossible (or >> extremely difficult) in the general case. In >> particular, tail recursive calls are essential in Ocaml, and are not >> available in C in most compilers. > > What's this based on (out of interest)? Most C compilers don't necessarily > identify tail recursion in *C* code but if you're emitting C as an OCaml > backend then there's no reason not to convert tail recursive *OCaml* > functions to C code based on goto or similar looping constructs (yes, you'd > almost-always-virtually-never use goto in a hand-crafted C program without > apologising profusely at Dijkstra's grave but if you're using C as an > intermediate language then that's a different matter). If I recall correctly > from an old post on this list, this is how Felix handles tail recursion when > translating Felix to C++ I am not sure this can work when tail-calling an unknown function. How would you translate to C let rec f g x = if x < 0 then g x (*tail recursive call to an unknown function*) else f g (x - 1) ;; ocamlopt -S gives (I am keeping only the crucial code) camlEsstr__f_58: .L101: movq %rax, %rsi cmpq $1, %rbx jge .L100 movq (%rsi), %rdi movq %rbx, %rax movq %rsi, %rbx jmp *%rdi ;;;; tail rec call to g .align 4 .L100: addq $-2, %rbx movq %rsi, %rax jmp .L101 As you can see, the tail recursive call is translated to an undirect jmp. Please explain how you would translate the above example to portable & efficient C. Regards. -- Basile STARYNKEVITCH http://starynkevitch.net/Basile/ email: basilestarynkevitchnet mobile: +33 6 8501 2359 8, rue de la Faiencerie, 92340 Bourg La Reine, France *** opinions {are only mines, sont seulement les miennes} ***