C to Forth compiler?
Wayne Morellini
Guy in Motorola (I left the article I just copied in the Library). Can
anybody advise me where I can obtain such a beast?
Wayne Morellini
way...@cq-pan.cqu.edu.au
--
larry kollar
>I have found one, mentioned in an article from December 93 ACME Forth, by a
>Guy in Motorola (I left the article I just copied in the Library). Can
>anybody advise me where I can obtain such a beast?
I've gotten the impression that a C-to-Forth translator is much like
Bigfoot... lots of people claim to have seen it, but nobody has a good
photograph. :-)
It just occurred to me that a portable C compiler (perhaps GCC)
could be made to spit out Forth primitives in lieu of assembly code.
Someone else has certainly thought of this before.
The output would undoubtedly be ugly Forth, but (to me) the main pur-
pose of such a compiler would be to get something done quick and dirty
with some of the huge pile of C code floating around. Prettying up the
output could be dealt with later, or not at all, depending on the need.
I suspect that we haven't seen this particular Bigfoot simply because
it would be more of a "neat hack" than anything, and most of the "neat
hack" people use C and are happy with that. The Forth people with the
skill to do the translator are busy writing their own code for their
own use/living. (Plus, many Forth purists would be offended at the ugly
output. :-)
Just my two cents.
--
Larry Kollar, Dawsonville GA | *** Hatred is murder *** (1 Jn 3:15)
leko...@nyx.net | http://www.nyx.net/~lekollar/
"His third dimension done been re-VOKED!"
W.Baden
but the result would not be satisfactory. A better job, such as one
based on Tom Almy's ForthCmp or Xan Gregg's peephole optimization
would be much better, but still not satisfactory.
I think I could do it in a weekend, working hard. But I would hate
the result.
The no-brainer would put off EVALUATE, as this will require
writing a complete interpreter. "['] foo" would become just
"foo". EXECUTE would become something like "(((void)(void))*S--)();".
I don't do enough of this sort of stuff to get it right the first
time. (Help, please.)
This is what my first try would look like.
Given the following example, which a troll (I hope it's a troll) has
proclaimed to be a work of art.
: DIGIT DUP 9 > 7 AND + 48 + ;
the no-brainer would yield something like:
void DIGIT(void) {
top = *S, *++S = top; *++S = 9; greater();
*++S = 7; AND(); plus(); *S += 48;
}
Taking The First Algorithm as an example:
: GCD BEGIN ?DUP WHILE TUCK MOD REPEAT ;
would become:
void GCD(void) {
L10001: if (*S) top = *S, *++S = top;
if (*S-- == 0) goto L10002;
top = *S, *++S = top, S[-1] = S[-2], S[-2]=top; MOD();
goto L10001;
L10002:
}
With a good optimizer, this would be:
void GCD(void)
while (*S) {
top = *S, *S %= S[-1], S[-1] = top;
}
S--;
}
"+LOOP" should be hand-compiled, as what Standard Forth does here
is a laughing stock -- a Monty Python way of doing something simple.
Of course, if the Forth is readable, you will be able to
translate to good C as you read.
--
Procedamus in pace. Wil Baden Costa Mesa, California
Jos'h Fuller
: Thus spake Wayne Morellini:
: >I have found one, mentioned in an article from December 93 ACME Forth, by a
: It just occurred to me that a portable C compiler (perhaps GCC)
: could be made to spit out Forth primitives in lieu of assembly code.
: Someone else has certainly thought of this before.
the novix processor and the stack machines by phil koopman were
reputed to have a c compiler available that transformed the
c into the forth 'machine code' of the stack processor.
might check with silicon composers (advertise in forth dimensions)
about the novix and its brethren.
jos'h fuller
Paul E. Bennett
leko...@nyx10.cs.du.edu "larry kollar" writes:
> Thus spake Wayne Morellini:
> >I have found one, mentioned in an article from December 93 ACME Forth, by a
> >Guy in Motorola (I left the article I just copied in the Library). Can
> >anybody advise me where I can obtain such a beast?
>
> I've gotten the impression that a C-to-Forth translator is much like
> Bigfoot... lots of people claim to have seen it, but nobody has a good
> photograph. :-)
It lives in Estonia I think.
>
> It just occurred to me that a portable C compiler (perhaps GCC)
> could be made to spit out Forth primitives in lieu of assembly code.
> Someone else has certainly thought of this before.
Yes they have. Mati Tombak, Viljo Soo and Jaanus Poial of Tartu University in
Estonia presented such a beast at the 1990 EuroForml. I beleive they had what
were termed "Compiler Compilers" for many other languages that produced
Forth-83 as an intermediate stage before it hit the machine.
> The output would undoubtedly be ugly Forth, but (to me) the main pur-
> pose of such a compiler would be to get something done quick and dirty
> with some of the huge pile of C code floating around. Prettying up the
> output could be dealt with later, or not at all, depending on the need.
Some of it probably was, but the guys at Tartu Uiniversity were doing some
splendid work to automate finding the worst constructs (that usually broke
"Stack Balancing" rules.
> I suspect that we haven't seen this particular Bigfoot simply because
> it would be more of a "neat hack" than anything, and most of the "neat
> hack" people use C and are happy with that. The Forth people with the
> skill to do the translator are busy writing their own code for their
> own use/living. (Plus, many Forth purists would be offended at the ugly
> output. :-)
Depends on what it really looked like after you did what you could
automatically. The main problem that I would see with this is the fact that the
comments written by the C programmer would not necessarily fit with the
resultant Forth. This may leave you with the dis-advantage that you would then
have to try and understand what the C programme was supposed to have acheived
and by the time you did you may have seen a much better way of doing it in
Forth yourself. :-).
--
Paul E. Bennett
p...@transcontech.co.uk
Going Forth Safely
Jim Schneider
>Thus spake Wayne Morellini:
>>I have found one, mentioned in an article from December 93 ACME Forth, by a
>>Guy in Motorola (I left the article I just copied in the Library). Can
>>anybody advise me where I can obtain such a beast?
>
>I've gotten the impression that a C-to-Forth translator is much like
>Bigfoot... lots of people claim to have seen it, but nobody has a good
>photograph. :-)
>
>
>could be made to spit out Forth primitives in lieu of assembly code.
>Someone else has certainly thought of this before.
>
the GCC intermediate code, called "Register Transfer Language", assumes
that several independantly addressable registers exist on the target
machine. There was no support for stack-based virtual machines.
>The output would undoubtedly be ugly Forth, but (to me) the main pur-
>pose of such a compiler would be to get something done quick and dirty
>with some of the huge pile of C code floating around. Prettying up the
>output could be dealt with later, or not at all, depending on the need.
>
I wrote most of a parser that would chew up C and spit out FORTH.
I didn't finish it because it became more than I could handle.
Actually, the FORTH that resulted (while certainly not idomatic) was only
slightly less readable than the corresponding C.
>I suspect that we haven't seen this particular Bigfoot simply because
>it would be more of a "neat hack" than anything, and most of the "neat
>hack" people use C and are happy with that. The Forth people with the
>skill to do the translator are busy writing their own code for their
>own use/living. (Plus, many Forth purists would be offended at the ugly
>output. :-)
>
I would be willing to finish the compiler/translator, but the pressures of
making a living have to take precedence.
W.Baden
large-size-but-few-page book of about ten years ago, had as its
principal project a Simple C compiler that could be easily
subverted into generating Forth. I started but didn't complete because
I felt the result would never be more than a toy.
It did give me insight to the relationship of Forth code to profane languages.
The usual Forth primitives are not well-suited for targets
of this one-pass C compiler. Some primitives that would help
are: !@ STICK STICK+
where
: !@ OVER SWAP ! ;
STICK is the inverse of PICK
and STICK+ is to STICK as +! is to !. (UNDER+ is 1 STICK+)
Also something better than DROP 2DROP and NIP to clean up the stack.
Perhaps something like the following:
KEEP ( xn . . . xm . . . x1 m n -- xm . . . x1 )
Also Forth's data stack corresponds most closely to C's
registers, and Forth's data space corresponds to C's
stack (and heap).
Also DUP OVER DROP NIP are assignment statements, assigning
values to a variable.
With these primitives it would be straightforward to
translate much C into Forth as you read.
Pinhole optimization could tidy the output.
int gcd(int x, int y) {
while (y) {
int t = y; y = x % y; x = t;
}
return x;
}
: GCD ( x y -- x )
BEGIN DUP WHILE ( x y)
DUP ( x y y)
2 PICK 2 PICK MOD ( x y y x%y)
2 4 KEEP ( y x%y)
REPEAT ( x y)
1 PICK ( x y x)
1 3 KEEP
;
Compare this to natural Forth.
: GCD ( x y -- x )
BEGIN ?DUP WHILE ( x y)
TUCK MOD
REPEAT ( x)
;
The elegance of the natural Forth is surely a factor
of why Forth is loved so by those within the temple.
Phil Koopman
>larry kollar (leko...@nyx10.cs.du.edu) wrote:
>: It just occurred to me that a portable C compiler (perhaps GCC)
>: could be made to spit out Forth primitives in lieu of assembly code.
>: Someone else has certainly thought of this before.
>
>reputed to have a c compiler available that transformed the
>c into the forth 'machine code' of the stack processor.
There was a C compiler for the RTX-2000 by CESYS (I think) that
generated pretty mediocre code. The code generation was done by
people who didn't really "get" Forth. I wrote a post-pass optimizer
that sucked in their Forth output, did some peepholing,
branch-to-branch optimization and a couple other things that got, if
memory serves, another 10%-15% speed improvement. They also did a
prototype compiler for the RTX-4000/Binar, but it wasn't finished.
Harris might well still sell the C compiler if they're still selling
RTX's, but I think that would be only to the Rad-hard market.
I did take a crack at grafting on a back-end to GNU C. It turned out
that it was easier to grab a dump of the RTL debug output just before
register allocation than it was to mess with the back end generator.
You can read about the stack optimization results at:
http://www.cs.cmu.edu/~koopman/stckcomp/
which show that stack code can be optimized pretty well with some
relatively simple heuristics.
Phil Koopman -- koo...@cs.cmu.edu -- http://www.cs.cmu.edu/~koopman
larry kollar
Whoops, looks like I managed to say something worth responding to. :-)
Thanks for all the helpful responses. Wrapped up and presented below:
My first comment was:
LK>> I've gotten the impression that a C-to-Forth translator is much like
LK>> Bigfoot... lots of people claim to have seen it, but nobody has a good
LK>> photograph. :-)
Paul E. Bennett writes:
>It lives in Estonia I think.
>
>[...] Mati Tombak, Viljo Soo and Jaanus Poial of Tartu University in
>Estonia presented such a beast at the 1990 EuroForml. I beleive they had what
>were termed "Compiler Compilers" for many other languages that produced
>Forth-83 as an intermediate stage before it hit the machine.
>
>[...] the guys at Tartu Uiniversity were doing some
>splendid work to automate finding the worst constructs (that usually broke
>"Stack Balancing" rules.
Is the Estonian compiler available on the net? If not, I presume there would
be a listing (or at least a detailed description) in the EuroForml proceedings.
H. Peter Anvin chimes in:
>Well, it shouldn't be hard to write one. Virtual stack machines are
>traditionally used for P-code since they are so easy to generate code
>for.
>
>Start by writing a parser using yacc, or a similar tool. There are so
>few statement types in C that the code-generation for functions will
>be very easy. The hard part would probably be handling of variables
>and structures; most C runtimes uses a "stack frame" which assume it
>is easy to obtain a word at a specified offset on the stack.
I think that if you assume a version of Forth that supports local vari-
ables (as does Mops on the Mac and JForth on the Amiga), handling C
variables and structs would be much easier. (Make 'em into objects for
that matter.)
Moving on to my second comment:
LK>>It just occurred to me that a portable C compiler (perhaps GCC)
LK>>could be made to spit out Forth primitives in lieu of assembly code.
LK>>Someone else has certainly thought of this before.
Jim Schneider writes:
>Actually, I tried this a while back, but it didn't work.
>[...] There was no support for stack-based virtual machines.
>I wrote most of a parser that would chew up C and spit out FORTH. [...]
>I would be willing to finish the compiler/translator, but the pressures of
>making a living have to take precedence.
I hear that! I'm growing an increasing backlog of things I want to hack on,
but my moonlight job just kicked in again.
Wil Baden suggests:
>_Compiler Construction Using LEX and YACC_, [...] had as its
>principal project a Simple C compiler that could be easily
>subverted into generating Forth. I started but didn't complete because
>I felt the result would never be more than a toy.
[good example snipped for space]
I'll have to see if the local library can track that one down for me.
Thanks for the comments!
Anton Ertl
|> It just occurred to me that a portable C compiler (perhaps GCC)
I would recommend lcc, for this purpose, not GCC. GCC is an optimizing
compiler for register machines, so it is not very appropriate for
stack machines. lcc is a simple compiler with a well-documented
code-generation interface. There already exists a code generator for a
stack-based virtual machine interpreter:
@InProceedings{proebsting95,
author = "Todd A. Proebsting",
title = "Optimizing an ANSI C Interpreter with Superoperators",
crossref = "popl95",
pages = "322--332"
}
@Proceedings{popl95,
booktitle = "Principles of Programming Languages (POPL '95)",
title = "Principles of Programming Languages (POPL '95)",
year = "1995",
key = "POPL '95"
}
|> I suspect that we haven't seen this particular Bigfoot simply because
|> it would be more of a "neat hack" than anything, and most of the "neat
|> hack" people use C and are happy with that.
Ok with me, if you replace "neat" with "ugly":-)
- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
Wayne Morellini
Thanks everybody for there conmtributions, I guess that such a thing doesn't
really exist (correct me if one is available). I was hopping to use such a
thing to translate some large standard C code for some standards, on some
forth processors (and do any forth versions later).
Wayne Morellini
Paul E. Bennett (p...@transcontech.co.uk) wrote:
: In article <4e8vlr$m...@nyx10.cs.du.edu>
: leko...@nyx10.cs.du.edu "larry kollar" writes:
: > Thus spake Wayne Morellini:
: > >I have found one, mentioned in an article from December 93 ACME Forth, by a
: > >Guy in Motorola (I left the article I just copied in the Library). Can
: > >anybody advise me where I can obtain such a beast?
: >
: > I've gotten the impression that a C-to-Forth translator is much like
: > Bigfoot... lots of people claim to have seen it, but nobody has a good
: > photograph. :-)
: It lives in Estonia I think.
:
: >
: > It just occurred to me that a portable C compiler (perhaps GCC)
: > could be made to spit out Forth primitives in lieu of assembly code.
: > Someone else has certainly thought of this before.
: Yes they have. Mati Tombak, Viljo Soo and Jaanus Poial of Tartu University in
: Estonia presented such a beast at the 1990 EuroForml. I beleive they had what
: were termed "Compiler Compilers" for many other languages that produced
: Forth-83 as an intermediate stage before it hit the machine.
:
: > The output would undoubtedly be ugly Forth, but (to me) the main pur-
: > pose of such a compiler would be to get something done quick and dirty
: > with some of the huge pile of C code floating around. Prettying up the
: > output could be dealt with later, or not at all, depending on the need.
: Some of it probably was, but the guys at Tartu Uiniversity were doing some
: splendid work to automate finding the worst constructs (that usually broke
: "Stack Balancing" rules.
: > I suspect that we haven't seen this particular Bigfoot simply because
: > it would be more of a "neat hack" than anything, and most of the "neat
: > hack" people use C and are happy with that. The Forth people with the
: > skill to do the translator are busy writing their own code for their
: > own use/living. (Plus, many Forth purists would be offended at the ugly
: > output. :-)
: Depends on what it really looked like after you did what you could
: automatically. The main problem that I would see with this is the fact that the
: comments written by the C programmer would not necessarily fit with the
: resultant Forth. This may leave you with the dis-advantage that you would then
: have to try and understand what the C programme was supposed to have acheived
: and by the time you did you may have seen a much better way of doing it in
: Forth yourself. :-).
: --
: Paul E. Bennett
: p...@transcontech.co.uk
: Going Forth Safely
--
Bruce Eisenhard
over 10 years ago, that also was ported to Novix boxes. The code it
output was not what I'd call readable (but is an .obj file from any C
compiler). The "C" was a true subset of Ansi-C at the time, with no
runtime checking for stack overflow or other wierd conditions.
I later expanded that compiler to include structures (which if you
eliminate bit-fields becomes relatively easy to implement as they are
simply offsets from some pointer). However at present the compiler is
somewhat defunct and I really couldn't support it.
As to why I was poking my head in here today, was that I was looking for
a Forth written for AMD's 29K.
Paul E. Bennett
leko...@nyx10.cs.du.edu "larry kollar" writes:
> Paul E. Bennett writes:
>
> >It lives in Estonia I think.
> >
> >[...] Mati Tombak, Viljo Soo and Jaanus Poial of Tartu University in
> >Estonia presented such a beast at the 1990 EuroForml. I beleive they had what
> >were termed "Compiler Compilers" for many other languages that produced
> >Forth-83 as an intermediate stage before it hit the machine.
> >
From the archives:
Jaanus Poial
Tartu University
Department of Computer Science
2 J Liivi Strasse
Tartu
Estonia 202400
Sorry no phone number.
The paper is short and only gives some fragments of code, but they did have a
version running on PC/XT/AT systems under their own Forth 83 (32 bit). The
languages they had conversion implementations for in 1990 was Fortran IV and
Modula-2 and some other special languages for different machines. I suppose C
would not have been too much trouble from there.
> >[...] the guys at Tartu Uiniversity were doing some
> >splendid work to automate finding the worst constructs (that usually broke
> >"Stack Balancing" rules.
>
> Is the Estonian compiler available on the net? If not, I presume there would
> be a listing (or at least a detailed description) in the EuroForml
> proceedings.
I don't think so. Perhaps the easiest thing to do is to try and find the phone
number from either directory enquiries (International) or perhaps asking
Stephen Pelc of MPE as they were in touch with them re: the EuroFORML event.
Stephen Pelc
leko...@nyx10.cs.du.edu "larry kollar" writes:
> Thus spake Wayne Morellini:
> >I have found one, mentioned in an article from December 93 ACME Forth, by a
> >Guy in Motorola (I left the article I just copied in the Library). Can
> >anybody advise me where I can obtain such a beast?
>
> I've gotten the impression that a C-to-Forth translator is much like
> Bigfoot... lots of people claim to have seen it, but nobody has a good
> photograph. :-)
and every enquiry we have had to date is for a system which will require
some porting and hence money. But the beasts are in *use*, but by rather
shy companies.
Regards, Stephen
--
Stephen Pelc, s...@mpeltd.demon.co.uk
MicroProcessor Engineering - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 1703 631441, fax: +44 1703 339691
Anton Ertl
(W.Baden) misses the original subject:
|> A quick-and-dirty Forth to C translator would almost be a no-brainer,
|> but the result would not be satisfactory. A better job, such as one
|> based on Tom Almy's ForthCmp or Xan Gregg's peephole optimization
|> would be much better, but still not satisfactory.
If you want to know how to do a relatively simple Forth-to-C
translator that cooperates well with todays optimizing C compilers to
produce fast assembly code, read
@InProceedings{ertl&maierhofer95,
author = {M. Anton Ertl and Martin Maierhofer},
title = {Translating Forth to Efficient C},
crossref = {euroforth95},
url = {http://www.complang.tuwien.ac.at/papers/ertl&maierhofer95.ps.gz},
abstract = {An automatic translator can translate Forth into C
code which the current generation of optimizing C
compilers compiles to efficient machine code. I.e.,
the resulting code keeps stack items in registers
and rarely updates the stack pointer. This paper
presents a simple translation method that produces
efficient C code, describes an implementation of the
method and presents results achieved with this
implementation: The translated code is 4.5--7.5
times faster than Gforth (the fastest measured
interpretive system), 1.3--3 times faster than
BigForth 386 (a native code compiler), and smaller
than Gforth's threaded code.}
}
@Proceedings{euroforth95,
title = "EuroForth~'95 Conference Proceedings",
booktitle = "EuroForth~'95 Conference Proceedings",
year = "1995",
key = "EuroForth '95",
address = "Schloss Dagstuhl, Germany",
}
As an example, I have thrown the two examples Wil made to the
prototype translator
(http://www.complang.tuwien.ac.at/forth/forth2c.tar.gz), then to
"gcc-2.6.3 -O3 -fomit-frame-pointer -S" to generate 486 code.
|> : DIGIT DUP 9 > 7 AND + 48 + ;
The generated C code
Cell digit(Cell p0)
{
Cell _c_result;
Cell x0;
Cell x1;
{ /* dup */
Cell n;
n = p0;
p0 = n;
x0 = n;
}
{ /* Literal */
x1 = 9;
}
{ /* greater-than */
Cell n1, n2, n;
n1 = x1;
n2 = x0;
n = FLAG(n2 > n1);
x0 = n;
}
{ /* Literal */
x1 = 7;
}
{ /* and */
Cell n1, n2, n;
n1 = x1;
n2 = x0;
n = n2 & n1;
x0 = n;
}
{ /* plus */
Cell n1, n2, n;
n1 = x0;
n2 = p0;
n = n2 + n1;
p0 = n;
}
{ /* Literal */
x0 = 48;
}
{ /* plus */
Cell n1, n2, n;
n1 = x0;
n2 = p0;
n = n2 + n1;
p0 = n;
}
{ /* exit */
_c_result = p0;
return (_c_result);
}
}
The generated assembly code (AT&T syntax):
_digit:
movl 4(%esp),%eax
cmpl $9,%eax
setg %dl
andl $255,%edx
negl %edx
andl $7,%edx
leal 48(%edx,%eax),%eax
ret
|> : GCD BEGIN ?DUP WHILE TUCK MOD REPEAT ;
The prototype translator cannot grok ?DUP, so I changed this to
: GCD begin dup while tuck mod repeat drop ;
I also find that more aesthetically pleasing; IMO ?DUP is useful in
some cases in front of IFs to avoid an ELSE clause, but should not be
used elsewhere.
The C code produced from that is:
Cell gcd(Cell p0, Cell p1)
{
Cell _c_result;
Cell x0;
label0:
{ /* dup */
Cell n;
n = p0;
p0 = n;
x0 = n;
}
if (!x0) goto label1;
{ /* tuck */
Cell c1, c2;
c2 = p0;
c1 = p1;
p1 = c2;
p0 = c1;
x0 = c2;
}
{ /* mod */
Cell n1, n2, n;
n1 = x0;
n2 = p0;
n = n2 % n1;
p0 = n;
}
goto label0;
label1:
{ /* drop */
}
{ /* exit */
_c_result = p1;
return (_c_result);
}
}
and the assembly code is
_gcd:
pushl %ebx
movl 8(%esp),%edx
movl 12(%esp),%ebx
L28:
testl %edx,%edx
je L30
movl %ebx,%ecx
movl %edx,%ebx
movl %ecx,%eax
cltd
idivl %ebx
jmp L28
.align 4,0x90
L30:
movl %ebx,%eax
popl %ebx
ret
W.Baden
: In article <wilbadenD...@netcom.com>, wilb...@netcom.com
: (W.Baden) misses the original subject:
Yes, I did miss the subject, as I realized just after I "sent".
My expansions were based on the kind of results that I would have
gotten if I had followed through on the book project.
The results that you get after the optimizing C compiler has done
its stuff are impressive.
Perhaps Forth is not the black hole I've lately been thinking it is.
--
Let us go forth in peace. Wil Baden Costa Mesa, California