# Implementation of a C compiler in TeX ?

Seeing the many things already done with TeX, I wonder if anyone has implemented a C (or C++) compiler in TeX. This does not seem too far fetched as an experiment. I do not expect great performance.

I am also interested about experiments towards a Lisp interpreter or a Java compiler.

-
Binary output would be an issue: TeX is a text based system! – Joseph Wright Apr 22 '11 at 10:50
@Joseph: binary output per se is possible. See for instance answers to this question about writing the whole 0-255 range of characters. – Bruno Le Floch Apr 22 '11 at 12:04
@Bruno: Yes, I know that, but was making the point that writing a binary file is not really some TeX is particularly good at, so it's not exactly a obvious thing to do to write a compiler. – Joseph Wright Apr 22 '11 at 12:26
@Bruno: just curious to know if someone tried it and look at the result. Certainly not doing it myself. There are so many more interesting and productive things to do with TeX or together with TeX and LaTeX in its natural sphere which is typesetting. And if there is something I appreciate from a compiler (besides correctness), it is speed. – ogerard Apr 22 '11 at 13:37
@Sharpie: My reading of the question was that as TeX82 itself is Turing-complete the aim would be to use TeX82 only. – Joseph Wright Apr 22 '11 at 16:55

Andrew Greene wrote a Basic interpreter in TeX many years ago; take a look at the tugboat article.

-
Nice. I did not mention this language but it sounds a more natural fit than C or Java. – ogerard Apr 25 '11 at 11:10

This does not seem like a good idea at all. A compiler uses highly specific data structures (like an abstract syntax tree, dictionaries, control flow graphs, register transfer lists) that I cannot believe you will want to build and use in TeX. Yes, TeX is programmable but it is a domain specific language for typesetting, not a general purpose language.

I assume you mentioned C (and C++) as an example but I also believe you underestimate the complexity of these languages. But even if you wanted to implement a Pascal compiler I would like to discourage you. You might want to try an interpreter for the lambda calculus, a Turing machine, or a calculator first.

-
thanks for your concern. I believe I do not underestimate C's complexity as a compiler source. In fact I was a member of a team who programmed an ANSI 89 C compiler 17 years ago on RISC systems. I expect that someone has already done something like implementing a core subset of the language in TeX. I certainly do not plan to do it myself, just would like to look at the result if it exists, for fun. Also we both know that a compiler is just one part of a C devpt ecosystem. – ogerard Apr 22 '11 at 13:25
@ogerard Thanks for providing some background. You obviously know much more about compilers than most people who often believe that a C compiler in particular is easy to implement. My own compiler background comes from C-- and I didn't mean to sound patronizing - my apologies. – Christian Lindig Apr 22 '11 at 13:59

Another thing that may be of interest is Alan Jeffrey's lazylist package and the associated TUGboat article about performing lambda calculus in TeX:

What amazes me is that the implementation is only ~80 lines of TeX and should be very understandable to anyone who has played with a functional programming language. The result of the paper is an implementation of insertion sort with lazy evaluation.

-
That is very nice and very close to what I wanted to have a look at in fact. The article is clearly written and very clever but I am just a little disappointed because the pdf is typeset with several black boxes that could have been avoided by careful use of display and editing. – ogerard Apr 25 '11 at 11:22

It would be extremely hard to do, but not impossible in principle.

As Christian Lindig mentions, trees and dictionaries would be needed, and it is not possible to code those very efficiently in TeX. However, a naive implementation of dictionaries can be

\def\newdictionary#1{%
\expandafter\def\csname dict@#1\endcsname##1{%
\csname dict@#1@##1\endcsname}}
\def\putkeyvalue#1#2#3{%
\expandafter\def\csname dict@#1@#2\endcsname{#3}}


A better (more memory efficient) implementation can be found as property lists in the expl3 bundle. For trees, I guess that the easiest is to have each node represented as one control sequence containing the list of its children, and one containing the material.

It may be easier to run the programs without compiling them, though. I know that pgf has some support for object-oriented programming.

On a side note, I should mention that I once wrote in TeX a parser for integer expressions (essentially the same syntax as \numexpr), where the user could define new functions, and it is rather tricky to get right.

-
Thanks a lot for these several ideas (dictionary macro, expl3, pgf). Can you add a link to your integer expression parser ? – ogerard Apr 22 '11 at 13:26
You can find it here. The other files in that directory are an attempt to extend this to floating point numbers. I know how to do each part (parsing one number, parsing expressions, doing calculations (sin, cos, etc.), but it is very difficult to combine all, because I want to keep expandability. FYI, I am using the expl3 package, but not in any critical way, so eventually, I might convert to TeX primitives. – Bruno Le Floch Apr 22 '11 at 21:00
@ogerard I have extended the expression parser to floating point expressions, and this has become the LaTeX3 l3fp module in the expl3 bundle on CTAN. I still want to write an interpreter or compiler in TeX, but I haven't decided what language to implement. – Bruno Le Floch Aug 18 '12 at 21:17