Small executables from Scheme

14 views
Skip to first unread message

Pascal Costanza

unread,
Apr 22, 2008, 10:46:35 AM4/22/08
to
Hi,

I'm trying to figure with which implementations I can compile to C
source code, and from there generate very small executables. My target
platform has only 256 kByte RAM available and provides only a C compiler.

Bigloo, Chicken, Gambit, Schlep and Petit Larceny seem good candidates,
but before doing the preliminary tests all myself, can anyone already
give me hints which ones would allow me to considerably reduce the size
of executables and would therefore be good choices?


Thanks a lot in advance!


Pascal

--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/

My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/

William D Clinger

unread,
Apr 22, 2008, 6:09:43 PM4/22/08
to
Pascal Costanza wrote:

> I'm trying to figure with which implementations I can compile to C
> source code, and from there generate very small executables. My target
> platform has only 256 kByte RAM available and provides only a C compiler.

With only 256k bytes, I think you'd be better off
using a byte code interpreter than compiling to C.

> Bigloo, Chicken, Gambit, Schlep and Petit Larceny seem good candidates,
> but before doing the preliminary tests all myself, can anyone already
> give me hints which ones would allow me to considerably reduce the size
> of executables and would therefore be good choices?

In native Larceny, the R6RS-compatible get-datum
procedure compiles into a single chunk of machine
code that's over 300k bytes on x86-32 and over
400k bytes on the SPARC.

On Petit Larceny, get-datum compiles to a single
C function that takes gcc about an hour to compile
on our Linux box. I'm pretty sure the machine code
that gcc generates for that one C function is larger
than the machine code that native Larceny generates.
On a SPARC, that one .o file is over 700k bytes.

That's an extreme example, caused in part by the
complexity of R6RS lexical syntax, but it illustrates
the problem.

The standard interpreters for Bigloo, Chicken, Gambit,
and Petit Larceny all occupy several megabytes, all
by themselves. You could probably cross-compile and
execute smallish programs, but anything that pulls in
a substantial fraction of the usual libraries (small
as they are) is likely to exceed 256k bytes.

Will

phi5...@yahoo.ca

unread,
Apr 24, 2008, 12:53:24 AM4/24/08
to
On 22 abr, 11:46, Pascal Costanza <p...@p-cos.net> wrote:
> Hi,
>
> I'm trying to figure with which implementations I can compile to C
> source code, and from there generate very small executables. My target
> platform has only 256 kByte RAM available and provides only a C compiler.
>
> Bigloo, Chicken, Gambit, Schlep and Petit Larceny seem good candidates,
> but before doing the preliminary tests all myself, can anyone already
> give me hints which ones would allow me to considerably reduce the size
> of executables and would therefore be good choices?
>
> Thanks a lot in advance!
>
> Pascal
>
> --
> 1st European Lisp Symposium (ELS'08)http://prog.vub.ac.be/~pcostanza/els08/

>
> My website:http://p-cos.net
> Common Lisp Document Repository:http://cdr.eurolisp.org
> Closer to MOP & ContextL:http://common-lisp.net/project/closer/

Hi, try Stalin. I wrote a lot of code in Stalin, and it is stingy (and
fast too). Schlep generates very small exec too, but I am not sure
that one can call it a Scheme implementation. Anyway, it is quite easy
to combine Schlep with Siod, and get a working stand alone with most
of Scheme functionality. You need to modify schlep to generate code
that is compatible with Siod. Here is an example of program for the
modified Scheme:

(require "cinclude")


(declare-suffixes!
'((eed (array "unsigned char"))
(ate (array "unsigned char"))
(sta (array "unsigned char"))
(sra (array unsigned))
(argv (ptr (ptr "char")))
("pp" int)
("rgv" (array (array char)))
("ean" double)
(lfat "conscell")
("_" conscell)
("_s" conscell)
("iff" double)))

(define (fat n acc)
(if (< n 1) acc
(fat (- n 1) (* n acc))))

(define (fat_s x_)
(if (nflonump x_) (err "argumento errado" x_))
(flocons (toreal (fat (toint (flonm x_)) 1))))


(define (fib n)
(if (< n 2) 1
(+ (fib (- n 1)) (fib (- n 2)) )))

(define (fib_s n_)
(flocons (toreal (fib (toint (flonm n_)) )) ))

(define (main argc argv)
(let ((retval 0))
(print_welcome)
(process_cla argc argv 0)
(init_storage)
(init_subrs)
(init_subr_1 "fatori" fat_s)
(init_subr_1 "fibo" fib_s)
(set! retval (repl_driver 1 1 c_null))
(printf "EXIT\n")
(exit retval)
0)

)


Modified Schlep generates the following C code:

#include "cinclude.h"


/**/

int fat(n, acc)
int n;
int acc;
{
L_fat:
if ((n)<1)
return acc;
else {
int T_n = (n)-1;
acc = (n)*(acc);
n = T_n;
goto L_fat;
}
}


conscell fat_s(x_)
conscell x_;
{
if (nflonump(x_))
err("argumento errado", x_);
return flocons(toreal(fat(toint(flonm(x_)), 1)));
}

int fib(n)
int n;
{
if ((n)<2)
return 1;
else return (fib((n)-1))+(fib((n)-2));
}


conscell fib_s(n_)
conscell n_;
{
return flocons(toreal(fib(toint(flonm(n_)))));
}


int main(argc, argv)
int argc;
char **argv;
{
{
int retval = 0;
print_welcome();
process_cla(argc, argv, 0);
init_storage();
init_subrs();
init_subr_1("fatori", fat_s);
init_subr_1("fibo", fib_s);
retval = repl_driver(1, 1, c_null);
printf("EXIT\n");
exit(retval);
return 0;
}
}


The stand alone has only 59 K.

Pascal Costanza

unread,
Apr 26, 2008, 11:16:38 AM4/26/08
to
phi5...@yahoo.ca wrote:
> On 22 abr, 11:46, Pascal Costanza <p...@p-cos.net> wrote:
>> Hi,
>>
>> I'm trying to figure with which implementations I can compile to C
>> source code, and from there generate very small executables. My target
>> platform has only 256 kByte RAM available and provides only a C compiler.
>>
>> Bigloo, Chicken, Gambit, Schlep and Petit Larceny seem good candidates,
>> but before doing the preliminary tests all myself, can anyone already
>> give me hints which ones would allow me to considerably reduce the size
>> of executables and would therefore be good choices?
>>
>> Thanks a lot in advance!
>>
>> Pascal
>>
>> --
>> 1st European Lisp Symposium (ELS'08)http://prog.vub.ac.be/~pcostanza/els08/
>>
>> My website:http://p-cos.net
>> Common Lisp Document Repository:http://cdr.eurolisp.org
>> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
>
> Hi, try Stalin. I wrote a lot of code in Stalin, and it is stingy (and
> fast too). Schlep generates very small exec too, but I am not sure
> that one can call it a Scheme implementation. Anyway, it is quite easy
> to combine Schlep with Siod, and get a working stand alone with most
> of Scheme functionality. You need to modify schlep to generate code
> that is compatible with Siod.

Thanks a lot for your response, these look like very promising
alternatives. Your feedback is appreciated.

Pascal Costanza

unread,
Apr 26, 2008, 11:18:12 AM4/26/08
to
William D Clinger wrote:
> Pascal Costanza wrote:
>
>> I'm trying to figure with which implementations I can compile to C
>> source code, and from there generate very small executables. My target
>> platform has only 256 kByte RAM available and provides only a C compiler.
>
> With only 256k bytes, I think you'd be better off
> using a byte code interpreter than compiling to C.

Yes, that's a possibility, although not the best one for our case. But
thanks for your comments anyway.


Pascal

P.S.: Hm, wasn't Scheme supposed to be a minimal language? ;-)

Tzvetan Mikov

unread,
Apr 26, 2008, 11:51:16 AM4/26/08
to
On Apr 26, 8:18 am, Pascal Costanza <p...@p-cos.net> wrote:
> William D Clinger wrote:
> > Pascal Costanza wrote:
>
> >> I'm trying to figure with which implementations I can compile to C
> >> source code, and from there generate very small executables. My target
> >> platform has only 256 kByte RAM available and provides only a C compiler.
>
> > With only 256k bytes, I think you'd be better off
> > using a byte code interpreter than compiling to C.
>
> Yes, that's a possibility, although not the best one for our case. But
> thanks for your comments anyway.
>
> Pascal
>
> P.S.: Hm, wasn't Scheme supposed to be a minimal language? ;-)

You may want to try Pre-Scheme. It is very minimal, but still quite
powerful.

regards,
Tzvetan

Pascal Costanza

unread,
Apr 26, 2008, 8:26:56 PM4/26/08
to

OK, could be an option. But is there any documentation available?


Pascal

Tzvetan Mikov

unread,
Apr 27, 2008, 4:13:24 PM4/27/08
to
On Apr 26, 5:26 pm, Pascal Costanza <p...@p-cos.net> wrote:
> > You may want to try Pre-Scheme. It is very minimal, but still quite
> > powerful.
>
> OK, could be an option. But is there any documentation available?

Unfortunately I haven't been able to find any except
http://mumble.net/~kelsey/papers/prescheme.ps.gz (which isn't very
useful for as a PreScheme user) and the source itself, but hopefully
that shouldn't be a big problem for an embedded project - presumably
you don't need libraries.

BTW, In theory I disagree with the assessment that a Scheme
applications needs a byte-code interpreter to be able to run inside
256KB. It barely needs any runtime system at all except a GC. Bigints,
rationals, etc, are clearly optional.

The fact that some implementations of get-datum (which itself is not
needed in an embedded implementation) compile to hundreds of kilobytes
really means nothing except that these implementations aren't
concerned with code size (nobody programming on a PC is anymore).
Turbo Pascal 3 was significantly more complex than get-datum and was
smaller than 64 KB.

That said, I think that in practice, given the current state of
affairs, you are probably out of luck.

regards,
Tzvetan

Michael Sperber

unread,
Apr 28, 2008, 3:31:28 AM4/28/08
to

Pascal Costanza <p...@p-cos.net> writes:

> OK, could be an option. But is there any documentation available?

You should still be able to find Taylor Campbell's manual on the
Internet archives: The PreScheme compiler hasn't changed (except for bug
fixes) since it was written. There are several active PreScheme
projects going on, though, and we generally try to help on the Scheme 48
mailing list.

--
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla

Pascal Costanza

unread,
May 16, 2008, 3:18:45 AM5/16/08
to
Michael Sperber wrote:
> Pascal Costanza <p...@p-cos.net> writes:
>
>> OK, could be an option. But is there any documentation available?
>
> You should still be able to find Taylor Campbell's manual on the
> Internet archives: The PreScheme compiler hasn't changed (except for bug
> fixes) since it was written. There are several active PreScheme
> projects going on, though, and we generally try to help on the Scheme 48
> mailing list.

Thanks a lot!

Reply all
Reply to author
Forward
0 new messages