[Caml-list] Why NOT to compile OCaml via C

[Caml-list] Why NOT to compile OCaml via C

[oleg]

Pierre-Alexandre Voye wrote:

> Note that if Ocaml compiler would have a C backend, all these problems or
> architecture port would disappear...
> Ocaml would have more than 30 target[1]
> In my Opinion, trying to generate assembler is a bad idea because modern CPU
> require a lot of work to generate good assembler.

There are many good reasons to avoid C when compiling functional
languages, especially strict ones.

One often hears that ``C is a portable assembler''. That has never
been true. One of the reasons is that every assembler I know has the
"jmp" instruction, which, without affecting SP, transfers control
anywhere, out of a procedure or in the middle of a procedure, out of a
module or into a module. C is built around the stack discipline --
after all, C is a descendant of Algol 60. (Although C has labels, they
are limited, even in GCC). Although Algol-60 researchers quickly
recognized the value of tail recursion, all that knowledge was lost in
the Dark Ages.

In strict functional languages, tail-recursion is a big deal. 
There is *huge* amount of literature on emulating tail-recursion in
standard C or GCC. That alone should tell that there is no simple
solution.  When GHC (Glasgow Haskell Compiler) was emitting C, it was
targeting specifically GCC. Furthermore, it employed a Perl program,
aptly named `evil mangler', to post-process the assembly code
generated by GCC. One can only shudder when thinking about Simon
Marlow's maintaining it.

There are at least two other reasons ocamlopt emitting assembly. One
is garbage collection. OCaml GC is precise. Therefore, when sweeping
through the stack, GC has to know if 0x80aa4000 is an unboxed integer
or a heap pointer. So-called frame tables generated by the compiler
tell GC which stack slots contain OCaml values. GC ignores other slots
and hence expensive tests it had to do otherwise. One can build frame
tables only when one has full control of the generated code and the
frame layout. The third reason is exceptions. In OCaml, exceptions are
pervasive and should be fast. They are indeed well implemented, via
special exception frames and a dedicated exception frame `register'
(which is a real register on x64).

Re: [Caml-list] Why NOT to compile OCaml via C

[Stéphane Glondu]

Le 09/12/2011 07:57, oleg@okmij.org a écrit :
> There are at least two other reasons ocamlopt emitting assembly. One
> is garbage collection. OCaml GC is precise. Therefore, when sweeping
> through the stack, GC has to know if 0x80aa4000 is an unboxed integer
> or a heap pointer. So-called frame tables generated by the compiler
> tell GC which stack slots contain OCaml values. GC ignores other slots
> and hence expensive tests it had to do otherwise. One can build frame
> tables only when one has full control of the generated code and the
> frame layout. The third reason is exceptions. In OCaml, exceptions are
> pervasive and should be fast. They are indeed well implemented, via
> special exception frames and a dedicated exception frame `register'
> (which is a real register on x64).

C sure is not a good target language, but assembly is not either.
The assembly backends of ocamlopt (and GHC... there is no support at all
on some Debian ports) look like a maintenance burden that their authors
obviously cannot cope with. I find the idea of making ocamlopt a GCC (or
LLVM) frontend the most sensible and constructive one I've seen in these
discussions.

However, one barrier is the licensing: QPL is incompatible with almost
any license (even QT does no longer use it!). Has it ever been
considered to switch the "public" license to e.g. GPLv3 (which looks
constraining enough, and compatible with GCC)?


Cheers,

-- 
Stéphane

Re: [Caml-list] Why NOT to compile OCaml via C

[Gabriel Scherer]

> I find the idea of making ocamlopt a GCC (or
> LLVM) frontend the most sensible and constructive one I've seen in these
> discussions.

Note that, besides Oleg excellent description of some issues, the idea
has already been discussed a few times before, here and on llvm-dev:
- http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-November/011525.html
(discussion on llvm-dev)
- http://caml.inria.fr/pub/ml-archives/caml-list/2010/11/315de2fb3656166edba13bb657fa691f.fr.html
(Benedikt Meurer: why ocamljit2 isn't an LLVM backend)
- https://sympa-roc.inria.fr/wws/arc/caml-list/2011-08/msg00192.html
(Pierre-Alexandre Voyes: question about a C backend; further
discussion of the DDC case)
- https://sympa-roc.inria.fr/wws/arc/caml-list/2011-08/msg00003.html
(Wojciech Meyer: announcement of an ocaml compiler framework project
with goal and structure similar to LLVM)

I found back some of this links thanks to the excellent "OCaml Weekly
News" summary:
  http://alan.petitepomme.net/cwn/2011.08.02.html
(Where Benedikt announces that he has a student working on an LLVM backend.)

OCamlPro also published an internship offer for an LLVM backend.

Apparently, there was at the time no particular interest among the
existing OCaml compiler hackers to develop such a C, LLVM or what you
have backend. Lots of people are talking about it, but few actual work
is done, or at least publicly exposed. I guess everyone would be happy
to look at an good LLVM backend, *especially* it is complete, stable,
safe enough to be a potential candidate for integration (if the work
needed between the working prototype and an integration is huge and
nobody is interested in doing it, it will remain at a prototypical
stage) but I will believe it when I see it.

I'm confident both Benedikt and/or OcamlPro (or other parties that I
don't know) would have the expertise to do something very good in this
direction, and I hope they'll go forward with this. It's just that I
don't feed the need for another bunch of emails about how LLVM passes
are great, GC issues, JIT or not JIT, performances of the current
Javascript engines, how frustratring it is that emacs is as slow to
start today as it was ten years ago, and the good and bad of Python's
meaningful-indentation syntax.

> However, one barrier is the licensing: QPL is incompatible with almost
> any license (even QT does no longer use it!). Has it ever been
> considered to switch the "public" license to e.g. GPLv3 (which looks
> constraining enough, and compatible with GCC)?

Stéphane, I am surprised at how good your are at raising trollish topics !

I don't think now is a good time to discuss this; maybe we should wait
for dust to settle on the other trolls before restarting a
"discussion" (where everyone agrees, but BSD or GPL?) on this.

On Fri, Dec 9, 2011 at 8:52 AM, Stéphane Glondu <steph@glondu.net> wrote:
> Le 09/12/2011 07:57, oleg@okmij.org a écrit :
>> There are at least two other reasons ocamlopt emitting assembly. One
>> is garbage collection. OCaml GC is precise. Therefore, when sweeping
>> through the stack, GC has to know if 0x80aa4000 is an unboxed integer
>> or a heap pointer. So-called frame tables generated by the compiler
>> tell GC which stack slots contain OCaml values. GC ignores other slots
>> and hence expensive tests it had to do otherwise. One can build frame
>> tables only when one has full control of the generated code and the
>> frame layout. The third reason is exceptions. In OCaml, exceptions are
>> pervasive and should be fast. They are indeed well implemented, via
>> special exception frames and a dedicated exception frame `register'
>> (which is a real register on x64).
>
> C sure is not a good target language, but assembly is not either.
> The assembly backends of ocamlopt (and GHC... there is no support at all
> on some Debian ports) look like a maintenance burden that their authors
> obviously cannot cope with. I find the idea of making ocamlopt a GCC (or
> LLVM) frontend the most sensible and constructive one I've seen in these
> discussions.
>
> However, one barrier is the licensing: QPL is incompatible with almost
> any license (even QT does no longer use it!). Has it ever been
> considered to switch the "public" license to e.g. GPLv3 (which looks
> constraining enough, and compatible with GCC)?
>
>
> Cheers,
>
> --
> Stéphane
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-devel] [Caml-list] Why NOT to compile OCaml via C

[Jonathan Protzenko]

On Fri 09 Dec 2011 10:58:31 AM CET, Gabriel Scherer wrote:
>> I find the idea of making ocamlopt a GCC (or
>> LLVM) frontend the most sensible and constructive one I've seen in these
>> discussions.
>
> Note that, besides Oleg excellent description of some issues, the idea
> has already been discussed a few times before, here and on llvm-dev:
> - http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-November/011525.html
> (discussion on llvm-dev)
> - http://caml.inria.fr/pub/ml-archives/caml-list/2010/11/315de2fb3656166edba13bb657fa691f.fr.html
> (Benedikt Meurer: why ocamljit2 isn't an LLVM backend)
> - https://sympa-roc.inria.fr/wws/arc/caml-list/2011-08/msg00192.html
> (Pierre-Alexandre Voyes: question about a C backend; further
> discussion of the DDC case)
> - https://sympa-roc.inria.fr/wws/arc/caml-list/2011-08/msg00003.html
> (Wojciech Meyer: announcement of an ocaml compiler framework project
> with goal and structure similar to LLVM)
http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-October/043719.html is 
an interesting email thread on the same topic, discussing some very 
specific issues as to why llvm is not necessarily a good compiler 
backend.

jonathan

Re: [Caml-list] Why NOT to compile OCaml via C

[Mehdi Dogguy]

On 12/09/2011 10:58 AM, Gabriel Scherer wrote:
> On Fri, Dec 9, 2011 at 8:52 AM, Stéphane Glondu <steph@glondu.net> 
> wrote:
>> However, one barrier is the licensing: QPL is incompatible with 
>> almost any license (even QT does no longer use it!). Has it ever 
>> been considered to switch the "public" license to e.g. GPLv3
>> (which looks constraining enough, and compatible with GCC)?
> 
> Stéphane, I am surprised at how good your are at raising trollish 
> topics !
> 
> I don't think now is a good time to discuss this; maybe we should 
> wait for dust to settle on the other trolls before restarting a 
> "discussion" (where everyone agrees, but BSD or GPL?) on this.
> 

Gabriel, I'm really surprised at how good you are at stopping any
serious discussion !

I really doubt Stéphane wanted to start another trollish topic on the
list. In fact, he raised a very important point (IMHO). If one seriously
considers investigating some time to contribute such a backend, the
licensing issue will be the first stopper.

It is amazing how people easily turn controversial questions into "trolls" !

Regards,

-- 
Mehdi Dogguy مهدي الدڤي
http://dogguy.org/

Re: [Caml-list] Why NOT to compile OCaml via C

[Benedikt Meurer]

On Dec 9, 2011, at 10:58 , Gabriel Scherer wrote:

>> I find the idea of making ocamlopt a GCC (or
>> LLVM) frontend the most sensible and constructive one I've seen in these
>> discussions.
> 
> I found back some of this links thanks to the excellent "OCaml Weekly
> News" summary:
>  http://alan.petitepomme.net/cwn/2011.08.02.html
> (Where Benedikt announces that he has a student working on an LLVM backend.)

You can follow the progress here: https://github.com/colinbenner/ocamlllvm

It does work for some simple examples already, but it's still very early prototype quality and requires a patched LLVM. LLVM as such is not a bad idea for the compiler backend, but getting things to work with stuff compiled by the regular OCaml backends is the difficult part. We'll see how that turns out.

>> However, one barrier is the licensing: QPL is incompatible with almost
>> any license (even QT does no longer use it!). Has it ever been
>> considered to switch the "public" license to e.g. GPLv3 (which looks
>> constraining enough, and compatible with GCC)?
> 
> Stéphane, I am surprised at how good your are at raising trollish topics !

I don't think it's a trollish topic raised by Stéphane. The QPL is a serious problem and I fear many of us may already already be violating the terms of the QPL, it would be nice to get rid of that issue at some point. The exact license (GPL, LGPL, MIT, BSD, Apache, ...) doesn't matter all that much, almost every other open source license is better than the QPL (just my 2c).

Benedikt

Re: [Caml-list] Why NOT to compile OCaml via C

[Gabriel Scherer]

> You can follow the progress here: https://github.com/colinbenner/ocamlllvm

Excellent!

Just a few questions:

- there are two different repos, ocamlllvm and ocaml-llvm (which has a
commit history that make it looks like it is where the real
development happen); which one should one follow? A wild guess after
only a quick look is that the ocaml-llvm repo did not build upon your
ocamlnat changes, and ocamllvm is about merging the changes on top of
it; but I really have no idea.

- you mention a "patched" LLVM; where can the patches be fetched? Do
you plan to present changes in such a way that it can be submitted
upstream? I think it is natural that you have to make changes to LLVM,
the GHC people (which now have an experimental LLVM backend) also did,
and I was under the impression that the LLVM people where quite
welcoming of their changes, they are glad to see LLVM being used in a
non-Clang-centric project. I think your patches could bring value to
LLVM, independently of the success of the ambitious ocaml backend
attempt.

On Fri, Dec 9, 2011 at 1:08 PM, Benedikt Meurer
<benedikt.meurer@googlemail.com> wrote:
>
> On Dec 9, 2011, at 10:58 , Gabriel Scherer wrote:
>
>>> I find the idea of making ocamlopt a GCC (or
>>> LLVM) frontend the most sensible and constructive one I've seen in these
>>> discussions.
>>
>> I found back some of this links thanks to the excellent "OCaml Weekly
>> News" summary:
>>  http://alan.petitepomme.net/cwn/2011.08.02.html
>> (Where Benedikt announces that he has a student working on an LLVM backend.)
>
> You can follow the progress here: https://github.com/colinbenner/ocamlllvm
>
> It does work for some simple examples already, but it's still very early prototype quality and requires a patched LLVM. LLVM as such is not a bad idea for the compiler backend, but getting things to work with stuff compiled by the regular OCaml backends is the difficult part. We'll see how that turns out.
>
>>> However, one barrier is the licensing: QPL is incompatible with almost
>>> any license (even QT does no longer use it!). Has it ever been
>>> considered to switch the "public" license to e.g. GPLv3 (which looks
>>> constraining enough, and compatible with GCC)?
>>
>> Stéphane, I am surprised at how good your are at raising trollish topics !
>
> I don't think it's a trollish topic raised by Stéphane. The QPL is a serious problem and I fear many of us may already already be violating the terms of the QPL, it would be nice to get rid of that issue at some point. The exact license (GPL, LGPL, MIT, BSD, Apache, ...) doesn't matter all that much, almost every other open source license is better than the QPL (just my 2c).
>
> Benedikt

Re: [Caml-list] Why NOT to compile OCaml via C

[Benedikt Meurer]

On Dec 9, 2011, at 13:37 , Gabriel Scherer wrote:

>> You can follow the progress here: https://github.com/colinbenner/ocamlllvm
> 
> - there are two different repos, ocamlllvm and ocaml-llvm (which has a
> commit history that make it looks like it is where the real
> development happen); which one should one follow? A wild guess after
> only a quick look is that the ocaml-llvm repo did not build upon your
> ocamlnat changes, and ocamllvm is about merging the changes on top of
> it; but I really have no idea.

ocaml-llvm was the initial attempt, based on the upstream OCaml sources. But we decided to ditch the surrounding OCaml stuff, esp. the broken make-based build system in favor of something simple, based on oasis and ocamlbuild (just like I did with ocamlnat). So the one to follow is ocamlllvm.

> - you mention a "patched" LLVM; where can the patches be fetched?

Just drop Colin a mail and ask him for the current patch (should be for 2.7 or 2.8, IIRC).

> Do
> you plan to present changes in such a way that it can be submitted
> upstream?

Yes, the long time goal (maybe impossible to reach with just one bachelor thesis) is to have a simple set of patches for LLVM (mostly calling conventions, maybe some additional intrinsics for the weird OCaml exception model), which can be merged upstream.

> I think it is natural that you have to make changes to LLVM,
> the GHC people (which now have an experimental LLVM backend) also did,
> and I was under the impression that the LLVM people where quite
> welcoming of their changes, they are glad to see LLVM being used in a
> non-Clang-centric project. I think your patches could bring value to
> LLVM, independently of the success of the ambitious ocaml backend
> attempt.

Hm, I'm not sure. It's really easy to generate LLVM code for OCaml in general, the problem is getting things to interact with legacy OCaml code, with exception handling being one of the most important issue. The required stuff will be very platform specific and very specific to OCaml, and we don't even know if it's going to work.

Benedikt

Re: [Caml-list] Why NOT to compile OCaml via C

[Török Edwin]

On 12/09/2011 04:05 PM, Benedikt Meurer wrote:
> 
> On Dec 9, 2011, at 13:37 , Gabriel Scherer wrote:
> 
>>> You can follow the progress here: https://github.com/colinbenner/ocamlllvm
>>
>> - there are two different repos, ocamlllvm and ocaml-llvm (which has a
>> commit history that make it looks like it is where the real
>> development happen); which one should one follow? A wild guess after
>> only a quick look is that the ocaml-llvm repo did not build upon your
>> ocamlnat changes, and ocamllvm is about merging the changes on top of
>> it; but I really have no idea.
> 
> ocaml-llvm was the initial attempt, based on the upstream OCaml sources. But we decided to ditch the surrounding OCaml stuff, esp. the broken make-based build system in favor of something simple, based on oasis and ocamlbuild (just like I did with ocamlnat). So the one to follow is ocamlllvm.
> 
>> - you mention a "patched" LLVM; where can the patches be fetched?
> 
> Just drop Colin a mail and ask him for the current patch (should be for 2.7 or 2.8, IIRC).

FWIW 3.0 has some fixes in the OCaml bindings that may (or may not) be useful for you, like:
findlib support, string_of_lltype not dieing on recursive structs, bindings to ipo.h,
bindings to some additional C APIs that were missing from the OCaml ones,
support for creating landing pads.

3.0 changes how structs work fundamentally though (they are not merged based on structure anymore),
so it may not be an easy change to move from 2.8 to 3.0, and I see why you would want to stay with 2.8 for now.

> 
>> Do
>> you plan to present changes in such a way that it can be submitted
>> upstream?
> 
> Yes, the long time goal (maybe impossible to reach with just one bachelor thesis) is to have a simple set of patches for LLVM (mostly calling conventions, maybe some additional intrinsics for the weird OCaml exception model), which can be merged upstream.
> 
>> I think it is natural that you have to make changes to LLVM,
>> the GHC people (which now have an experimental LLVM backend) also did,
>> and I was under the impression that the LLVM people where quite
>> welcoming of their changes, they are glad to see LLVM being used in a
>> non-Clang-centric project. I think your patches could bring value to
>> LLVM, independently of the success of the ambitious ocaml backend
>> attempt.
> 
> Hm, I'm not sure. It's really easy to generate LLVM code for OCaml in general, the problem is getting things to interact with legacy OCaml code, with exception handling being one of the most important issue. The required stuff will be very platform specific and very specific to OCaml, and we don't even know if it's going to work.

Is binary compatibility with a specific version of ocamlopt necessary?
I think that ocaml-llvm could detect the mismatch and print an error, like you get for an ABI mismatch.

Sure it'd be nice to be able to try out ocaml-llvm without rebuilding all OCaml packages,
but such a rebuilt is required when new OCaml releases come out anyway, as they are usually not ABI compatible with each-other.

Best regards,
--Edwin

Re: [Caml-list] Why NOT to compile OCaml via C

[Benedikt Meurer]

On Dec 9, 2011, at 15:30 , Török Edwin wrote:

>> Just drop Colin a mail and ask him for the current patch (should be for 2.7 or 2.8, IIRC).
> 
> FWIW 3.0 has some fixes in the OCaml bindings that may (or may not) be useful for you, like:
> findlib support, string_of_lltype not dieing on recursive structs, bindings to ipo.h,
> bindings to some additional C APIs that were missing from the OCaml ones,
> support for creating landing pads.

The prototype should not use the C/OCaml API, but emit a textual representation instead (for various reasons). The work is based on an earlier prototype I did some time ago and that was based on LLVM 2.7. IIRC Colin ported that to 2.8, because 2.9 had some fundamental differences that caused trouble with the custom calling conventions. I haven't looked into this myself, but I'm sure we can port the final patch to 3.0 once things proved working.

>>> I think it is natural that you have to make changes to LLVM,
>>> the GHC people (which now have an experimental LLVM backend) also did,
>>> and I was under the impression that the LLVM people where quite
>>> welcoming of their changes, they are glad to see LLVM being used in a
>>> non-Clang-centric project. I think your patches could bring value to
>>> LLVM, independently of the success of the ambitious ocaml backend
>>> attempt.
>> 
>> Hm, I'm not sure. It's really easy to generate LLVM code for OCaml in general, the problem is getting things to interact with legacy OCaml code, with exception handling being one of the most important issue. The required stuff will be very platform specific and very specific to OCaml, and we don't even know if it's going to work.
> 
> Is binary compatibility with a specific version of ocamlopt necessary?

It's a "nice to have" thing.

> Best regards,
> --Edwin

Benedikt

Re: [Caml-list] Why NOT to compile OCaml via C

[oliver]

On Fri, Dec 09, 2011 at 04:30:33PM +0200, Török Edwin wrote:
[...]
> Is binary compatibility with a specific version of ocamlopt necessary?
> I think that ocaml-llvm could detect the mismatch and print an error, like you get for an ABI mismatch.
> 
> Sure it'd be nice to be able to try out ocaml-llvm without rebuilding all OCaml packages,
> but such a rebuilt is required when new OCaml releases come out anyway, as they are usually not ABI compatible with each-other.
[...]


If it produces the same output as OCaml does now,
why to investigate ocaml-llvm?

Maybe changing OCaml from non-optimizing to an optimizing compiler
would outperform any llvm attempts.

Mabye the core team alkready works on this... who knows? ;-)


Ciao,
   Oliver

Re: [Caml-list] Why NOT to compile OCaml via C

[Richard W.M. Jones]

On Fri, Dec 09, 2011 at 03:05:43PM +0100, Benedikt Meurer wrote:
> Hm, I'm not sure. It's really easy to generate LLVM code for OCaml
> in general, the problem is getting things to interact with legacy
> OCaml code, with exception handling being one of the most important
> issue.

As Edwin said, I don't think interaction with existing ocamlopt-
compiled code is that important.  Debian and Fedora routinely
"recompile the world".  What is more important is compatibility with C
extensions.  How difficult is just C extension compatibility?  Or
something that was mostly compatible but needed a few changes to C
extensions?

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Why NOT to compile OCaml via C

[Benedikt Meurer]

On Dec 9, 2011, at 22:22 , Richard W.M. Jones wrote:

> On Fri, Dec 09, 2011 at 03:05:43PM +0100, Benedikt Meurer wrote:
>> Hm, I'm not sure. It's really easy to generate LLVM code for OCaml
>> in general, the problem is getting things to interact with legacy
>> OCaml code, with exception handling being one of the most important
>> issue.
> 
> As Edwin said, I don't think interaction with existing ocamlopt-
> compiled code is that important.  Debian and Fedora routinely
> "recompile the world".  What is more important is compatibility with C
> extensions.  How difficult is just C extension compatibility?  Or
> something that was mostly compatible but needed a few changes to C
> extensions?

It should work in general.

> Rich.

Benedikt

RE: [Caml-list] Why NOT to compile OCaml via C

[Jon Harrop]

Stéphane Glondu wrote:
> C sure is not a good target language, but assembly is not either.
> The assembly backends of ocamlopt (and GHC... there is no support at all on
> some Debian ports) look like a maintenance burden that their authors obviously
> cannot cope with. I find the idea of making ocamlopt a GCC (or
> LLVM) frontend the most sensible and constructive one I've seen in these
> discussions.

Perhaps because OCaml already has an efficient cross-platform bytecode interpreter.

> However, one barrier is the licensing: QPL is incompatible with almost any
> license (even QT does no longer use it!). Has it ever been considered to switch
> the "public" license to e.g. GPLv3 (which looks constraining enough, and
> compatible with GCC)?

Don't forget the CAML Consortium are selling OCaml under less restrictive licences.

Cheers,
Jon.

Re: [Caml-list] Why NOT to compile OCaml via C

[oliver]

On Fri, Dec 09, 2011 at 06:57:58AM -0000, oleg@okmij.org wrote:
> 
> Pierre-Alexandre Voye wrote:
> 
> > Note that if Ocaml compiler would have a C backend, all these problems or
> > architecture port would disappear...
> > Ocaml would have more than 30 target[1]
> > In my Opinion, trying to generate assembler is a bad idea because modern CPU
> > require a lot of work to generate good assembler.
> 
> There are many good reasons to avoid C when compiling functional
> languages, especially strict ones.
> 
> One often hears that ``C is a portable assembler''. That has never
> been true. One of the reasons is that every assembler I know has the
> "jmp" instruction, which, without affecting SP, transfers control
> anywhere, out of a procedure or in the middle of a procedure, out of a
> module or into a module. C is built around the stack discipline --
> after all, C is a descendant of Algol 60. (Although C has labels, they
> are limited, even in GCC). Although Algol-60 researchers quickly
> recognized the value of tail recursion, all that knowledge was lost in
> the Dark Ages.
[...]

This somehow is a good example on "OCaml maintenance status..:" thread
and "Some comments on recent discussions" thread...


If this thread comes to a conclusion, the conclusion maybe can be sent to the OCaml core team...
... if it has new insights.

But my guess is, that we end at a point, where OCaml already is,
because I think these kind of dicsussions were already made,
when the design was chosen.

If something new evolves it could be sent to the core team.
But I just doubt, that this will happen here ;)

Ciao,
   Oliver

Re: [Caml-list] Why NOT to compile OCaml via C

[Goswin von Brederlow]

oleg@okmij.org writes:

> Pierre-Alexandre Voye wrote:
>
>> Note that if Ocaml compiler would have a C backend, all these problems or
>> architecture port would disappear...
>> Ocaml would have more than 30 target[1]
>> In my Opinion, trying to generate assembler is a bad idea because modern CPU
>> require a lot of work to generate good assembler.
>
> There are many good reasons to avoid C when compiling functional
> languages, especially strict ones.
>
> One often hears that ``C is a portable assembler''. That has never
> been true. One of the reasons is that every assembler I know has the
> "jmp" instruction, which, without affecting SP, transfers control
> anywhere, out of a procedure or in the middle of a procedure, out of a
> module or into a module. C is built around the stack discipline --
> after all, C is a descendant of Algol 60. (Although C has labels, they
> are limited, even in GCC). Although Algol-60 researchers quickly
> recognized the value of tail recursion, all that knowledge was lost in
> the Dark Ages.

Well, write the code as ONE function and do use lables. Sure, the C
source will be huge for larger projects but then again you get the
single source optimization bonus from gcc.

Note: gcc does know something about tail recusion. So it is not
completly lost there.

Personly I would like to have a ocaml -> C compiler. Not to replace the
one we have but for fun or as alternative on architectures that don't
have a native compiler (yet). It doesn't have to be hype efficient. If
it is somwhere between the bytecode and native speed that would be
totally fine.

MfG
        Goswin

Re: [Caml-list] Why NOT to compile OCaml via C

[Till Varoquaux]

You can use the bytecode compiler and interpreter on those
architectures. If you feel adventurous you can compile ocaml to java
or javascript and run wherever those languages run.

The hypothetical ocaml->c compiler would have to interact with the
garbage collector or use a different garbage collector; to be useful
it would also need to present a compatible FFI to pre-existing stubs.
You might also want to respect the limitations imposed by the current
framework (exceptions for stack-overflows; 31/63 bits ints...).
Writing portable C that low level is hard; generating it would be a
lot of work. I very much doubt that anyone who understands what's at
stake enough to be able to take a stab at it would consider this a
productive use of their time.

Till

On Fri, Dec 9, 2011 at 6:18 PM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> oleg@okmij.org writes:
>
>> Pierre-Alexandre Voye wrote:
>>
>>> Note that if Ocaml compiler would have a C backend, all these problems or
>>> architecture port would disappear...
>>> Ocaml would have more than 30 target[1]
>>> In my Opinion, trying to generate assembler is a bad idea because modern CPU
>>> require a lot of work to generate good assembler.
>>
>> There are many good reasons to avoid C when compiling functional
>> languages, especially strict ones.
>>
>> One often hears that ``C is a portable assembler''. That has never
>> been true. One of the reasons is that every assembler I know has the
>> "jmp" instruction, which, without affecting SP, transfers control
>> anywhere, out of a procedure or in the middle of a procedure, out of a
>> module or into a module. C is built around the stack discipline --
>> after all, C is a descendant of Algol 60. (Although C has labels, they
>> are limited, even in GCC). Although Algol-60 researchers quickly
>> recognized the value of tail recursion, all that knowledge was lost in
>> the Dark Ages.
>
> Well, write the code as ONE function and do use lables. Sure, the C
> source will be huge for larger projects but then again you get the
> single source optimization bonus from gcc.
>
> Note: gcc does know something about tail recusion. So it is not
> completly lost there.
>
> Personly I would like to have a ocaml -> C compiler. Not to replace the
> one we have but for fun or as alternative on architectures that don't
> have a native compiler (yet). It doesn't have to be hype efficient. If
> it is somwhere between the bytecode and native speed that would be
> totally fine.
>
> MfG
>        Goswin
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Why NOT to compile OCaml via C

[oleg]

> Well, write the code as ONE function and do use lables. Sure, the C
> source will be huge for larger projects but then again you get the
> single source optimization bonus from gcc.

A realistic version of this approach indeed has been used, for
example, in Gambit-C Scheme and Stalin Scheme compilers. The approach as
suggested above has several drawbacks. First of all, it prevents
separate compilation. If we do need separate compilation, we have to
be content with several C functions (one per each separately compiled
unit), and have to arrange for tail-recursive calls among them. So, we
need a fall-back solution. Gambit-C uses trampolining. 

Second, you probably do not appreciate how huge the produced C
functions might become. Past a certain threshold, gcc or other C
compilers slow down, almost to a halt. Subjectively, it seems that the
quality of optimizations deteriorates past a threshold (although I
haven't investigated that). Past another threshold, gcc just
bombs. Therefore, Gambit for example had to take measures limiting the
size of the generated C functions.

> Note: gcc does know something about tail recusion. So it is not
> completly lost there.

One must really draw the distinction between an optional optimization
and a required behavior. GCC indeed _may_ optimize a tail call -- in
simple circumstances and when the stars are well-aligned. BTW,
implementing tail-recursion is much more complex than it may
appear. Consider, for example
	let rec f x y = if y = 0 then x else f (x+y) (x-y)

Here, we can't _just_ jump on the recursive call. We have to mutate
the arguments in the current frame, possibly using stack for scratch
storage. GCC won't do tail-call optimization in this (and many much
simpler) cases.

As I said earlier, there really is huge literature on implementing
functional languages by compiling into C. Lots of approaches have been
suggested and tried -- it is very hard to say anything new here. The
fact that we are still having this discussion tells that no solution
has been truly satisfactory.

BTW, Gambit avoids other pitfalls of C compilation and so does manages
precise GC and very efficient call/cc, exceptions and dynamic
binding. The reason is that the generated C code is essentially a
Gambit Virtual machine interpreter specialized to the source code.  It
does not share its stack with the C stack. Perhaps Gambit is the
first example of the First Futamura Projection that I have seen. It
works out quite well in the end.

Re: [Caml-list] Why NOT to compile OCaml via C

[Basile Starynkevitch]

On Sat, 10 Dec 2011 00:18:25 +0100
Goswin von Brederlow <goswin-v-b@web.de> wrote:
> 
> Well, write the code as ONE function and do use lables. Sure, the C
> source will be huge for larger projects but then again you get the
> single source optimization bonus from gcc.


This won't work very well in practice, because practically speaking, a GCC recent
(4.4, 4.5, or 4.6) compiler with -O1 optimization has a compile time which is quadratic
with respect to the function size.

Compiling a single 100 0000 C statements function with GCC take a lot of time & memory.

(You might use http://starynkevitch.net/Basile/manydl.c to measure that)
 
Cheers.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: [Caml-list] Why NOT to compile OCaml via C

[Peter Hawkins]

Hi...

There are some cool but quite dirty tricks based on computed gotos
between functions to avoid problems with function size; see Section
5.2 of:
Compiling logic programs to C using GNU C as a portable assembler
Fergus Henderson, Zoltan Somogyi and Thomas Conway.
Proceedings of the ILPS '95 Postconference Workshop on Sequential
Implementation Technologies for Logic Programming Languages. Portland,
Oregon, December 1995.

Cheers,
Peter

On Sat, Dec 10, 2011 at 7:40 AM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> On Sat, 10 Dec 2011 00:18:25 +0100
> Goswin von Brederlow <goswin-v-b@web.de> wrote:
>>
>> Well, write the code as ONE function and do use lables. Sure, the C
>> source will be huge for larger projects but then again you get the
>> single source optimization bonus from gcc.
>
>
> This won't work very well in practice, because practically speaking, a GCC recent
> (4.4, 4.5, or 4.6) compiler with -O1 optimization has a compile time which is quadratic
> with respect to the function size.
>
> Compiling a single 100 0000 C statements function with GCC take a lot of time & memory.
>
> (You might use http://starynkevitch.net/Basile/manydl.c to measure that)
>
> Cheers.
>
> --
> Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
> email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
> 8, rue de la Faiencerie, 92340 Bourg La Reine, France
> *** opinions {are only mine, sont seulement les miennes} ***
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Why NOT to compile OCaml via C

[Basile Starynkevitch]

On Sat, 10 Dec 2011 15:56:39 -0800
Peter Hawkins <hawkinsp@cs.stanford.edu> wrote:

> Hi...
> 
> There are some cool but quite dirty tricks based on computed gotos
> between functions to avoid problems with function size; see Section
> 5.2 of:
> Compiling logic programs to C using GNU C as a portable assembler
> Fergus Henderson, Zoltan Somogyi and Thomas Conway.
> Proceedings of the ILPS '95 Postconference Workshop on Sequential
> Implementation Technologies for Logic Programming Languages. Portland,
> Oregon, December 1995.


Yes, but these tricks are really dirty. They might not work when upgrading your compiler
(e.g. from GCC 4.5 to GCC 4.6).



-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***