Scheme to C translator

Question

I tried to generate C code starting from a scheme function and I do not manage to find any translator from scheme to C. I tried to convert this function to C.

(define f
  (lambda(n)
     (if (= n 0) 1
         (* n (f (- n 1))))))

(display (f 10))
(newline)

I tried to use gambit (gsc) and it generates a C file that looks merely like a file to load in some interpreter, not a file containing a main function that can be executed.

Is there some application that generates C code that can be directly executed? The functions from standard scheme library like display should be linked with some object file.

EDIT:

My purpose is to understand the algorithms used by professional translators.

`f` looks like an implementation of the factorial function. It should be easy to implement a C version manually, implemented either recursively or iteratively. But unless you are only dealing with small numbers whose factorials fit in 64 bits, you might need to use a _bignum_ library such as GNU MP. — Ian Abbott, Jan 31 '20 at 12:38
@IanAbbott This is not what I am interested about :). I need a good converter for some more complex functions. This is the function I used to see what happens when I use gambit. — alinsoar, Jan 31 '20 at 12:56
@Flux hmmm. It seems that this is what I am looking for :), however I am not sure. — alinsoar, Jan 31 '20 at 13:44
@Flux Can you provide a link to a functional tutorial about how to generate a C executable for my function ? — alinsoar, Jan 31 '20 at 14:17
[stalin](https://en.wikipedia.org/wiki/Stalin_(Scheme_implementation)) generates executables which only depend on the standard libs and the Boehm C garbage collector. — , Jan 31 '20 at 15:34
assuming that your file is `foo.scm`, `stalin -On foo.scm` will create a `foo` executable, and `stalin -c -On foo.scm` a `foo.c` file (which you better don't look into ;-)). — , Jan 31 '20 at 15:38
by "good" converter do you mean one that produces a human-readable C? or even such that is able to convert `f` into an equivalent loop-based code? would an RTS be enough with Lisp translated into some C representation but essentially being interpreted by said RTS? It would still be C, technically. not that I have any of those, just wanted it clarified. — Will Ness, Jan 31 '20 at 16:47
@WillNess by "good" I mean, first of all, correct. because, looking on some forums, I saw that exist some that does not generate generate correct code, for example , for tail recursion. Ideally, I want to understand the algorithm used to convert, to be well documented about how it implements the tail recursion in C, and other more advanced issues. — alinsoar, Jan 31 '20 at 17:01
@WillNess so, not "human readable" , but correct , and well documented. — alinsoar, Jan 31 '20 at 17:03
perhaps you're familiar with such terms as "trampoline" ; "defunctionalization" ; "CPS / single assignment form" ; ... . or course writing it yourself is quite an undertaking. — Will Ness, Jan 31 '20 at 17:18
@WillNess I am familiar with trampoline, ssa, and CPS concepts, however it is not easy to understand the code from mit scheme, which uses both. — alinsoar, Jan 31 '20 at 17:21
@WillNess on the other hand, I have never implemented defunctionalization. — alinsoar, Jan 31 '20 at 17:25
@alinsoar it's trivial to implement tail call recursion in C -- with `goto`. — , Jan 31 '20 at 17:30
@mosvy I want to understand the methods used by professional interpreters. I doubt it is trivial, as it must be combined with gc and continuations. as a whole, it is not. a good start would be to understand how the professional translators from scheme to c work. — alinsoar, Jan 31 '20 at 17:32
@mosvy it is trivial if you implement it metacircularly, as in sicp. from scratch it is difficult. — alinsoar, Jan 31 '20 at 17:36
Read Queinnec's book *Lisp in Small Pieces* https://christian.queinnec.org/ ; several hundred pages to explain what you ask — Basile Starynkevitch, Jan 31 '20 at 18:29
@BasileStarynkevitch thank you, we are already talking here about queinnec's book. Do you know other resources as good as this one? — alinsoar, Jan 31 '20 at 18:52
No, but [Programming Language Pragmatics](https://www.cs.rochester.edu/~scott/pragmatics/) and the [Dragon book](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools) are worth reading too. Then, a book about [Denotational Semantics](https://en.wikipedia.org/wiki/Denotational_semantics) and of course [R5RS](https://schemers.org/Documents/Standards/R5RS/) — Basile Starynkevitch, Jan 31 '20 at 19:17
I love translator questions: a good source of exotic material to dive into and procrastinate on every important chore of the day :) — chqrlie, Apr 12 '22 at 08:54

score 4 · Accepted Answer · 2020-01-31T18:24:58.560

4

There are many such translators, dating back at least to the 1980s I think CHICKEN is a good current one.

If you want to use that:

get CHICKEN;
build & install it with the appropriate make incantation (this was painless for me on OSX, it should be very painless indeed on Linux therefore, although it may be harder on Windows);
stash your code in a file I'll call f.scm.
if you want to see the C code, compile with chicken f.scm which will produce a few hundred lines of incomprehensible C;
if you want just the executable, use csc to create it.

There is an extensive manual which you will need to read if you want to do anything nontrivial, such as linking in C libraries or talking to Scheme code from C.

Without knowing what you are after, this smells as if it may be an XY problem. In particular:

if you want a Scheme system which will allow you talk to code written in C, then you probably want a system with an FFI, not one that compiles to C;
if you want a Scheme system which will create native executables, then you probably want, well, a Scheme system which will create native executables, not one which compiles to C.

There are many examples of each of these. Some of these systems may also compile to, or via, C, but one does not depend on the other.

Finally, if you want to understand how Scheme compilers which target C work (or how Scheme compilers which target any language, including assembler), then the traditional approach probably still works best: find a well-written one for which source is available, and read & tinker with its source code.

edited Jan 31 '20 at 18:24

answered Jan 31 '20 at 15:31

thank you. Can you provide some links to the internals of chicken, to understand the algorithms used to make the conversion? I wish I would read some artictles that teaches me how to implement myself the algorithms of conversion. – alinsoar Jan 31 '20 at 17:42
@alinsoar: not really. It will be as hairy as any other compiler I suspect: it just happens to target C. C is famously spoken of as a 'portable assembler': Scheme compilers which target C are an example of just that. – Jan 31 '20 at 18:04
the internals of these interpreters and compilers is described in the book of Christian Queinnec, however it is interesting to follow that book looking in the same time at some concrete implementations. – alinsoar Jan 31 '20 at 18:07
@alinsoar: no: *some particular example techniques for compiling and intepreting Scheme* are described in that book: there is absolutely *no reason at all* why compilers need to follow those examples. It is perfectly legitimate to compile or interpret Scheme programs by invoking a djinn, for instance. That's certainly how I always do it. – Jan 31 '20 at 18:14
I have a French edition and it is published in 2007. this is why I suspect that it contains the chicken's algorithms; I suspect that it teaches the most modern algorithms. – alinsoar Jan 31 '20 at 18:24
@alinsoar: there *are no* 'most modern' algorithms: there is no temporal order on algorithms for compiling Scheme, or any other language, in which older techniques are necessarily superseded by newer ones. Some older techniques may die out for sure, but at any point there's just an enormous range of different techniques. Even if there was a temporal order, well, 2007 is 13 years ago. – Jan 31 '20 at 18:34
general relativity is 100 years ago, and it is still of actuality. The same with sicp. – alinsoar Jan 31 '20 at 18:36
1

@alinsoar: GR is a good example: some techniques from the early history of the theory may still be useful (I'm not sure though), but the techniques people use today to do calculations in GR are both widely varied and hugely developed from anything Einstein knew. Anyway, I'm done here. – Jan 31 '20 at 18:48
Yes, I believe , to be able to use more modern methods, it is better to have understood the most important of the classical methods. – alinsoar Jan 31 '20 at 18:54
https://wiki.c2.com/?LispInSmallPieces gives 1996 as the date. ISBN-13: 978-0521562478 says it's from June 28, 1996. And it was / is a translation from French so the first edition (in French) must have been even earlier. I was sure it must have had a Wikipedia page, but no. EOPL and PLAI have their pages; LiSP is at least as important. – Will Ness Feb 01 '20 at 08:58

score 3 · Answer 2 · answered Feb 01 '20 at 00:25

Basically no scheme to C translators will do what you want. They create hideous code not meant to be read and they rely on the underlying C compiler to do much of the optimization. Chicken and Gambit make use of header files while I have Stalin, which does not but it is based on R4RS instead of R5RS and later.

You are probably better off reading Abdulaziz Ghuloum's paper An Incremental Approach to Compiler Construction (PDF) or perhaps Matt Mights articles on parsing, continuations and compilations. Longer down he actually has a Scheme to C and Scheme to Java with different approaches to closure conventions. In the end nothing beats doing it yourself so have a go!

Scheme to C translator

2 Answers2