CompilerDev?

[Zondartul]

Hey all. They often say that the second hardest thing to writing an OS is writing a compiler, and I happen to be interested in both. The only problem is, we have OsDev.org, which is both a wiki and a forum and altogether a great resource and community portal on OS development, but there doesn't seem to be an equivalent for compiler development.

I tried googling and the only relevant answer I found was here: http://stackoverflow.com/questions/7054 ... ent-forums and apparently other than usenet.comp.compilers (what's a usenet?) and a bunch of github projects, there do not appear to be much reasources.

Is that really all there is to the global compiler development community? Reading the Dragon book and searching Wikipedia for occasional deep topic is fine, but I'd feel much better if I found something more like what we have here.

Sorry if this is a bad question.

[bwat]

Compiler writing is easy. Getting a run-time system working and documented is what takes time and effort.

With my most recent language implementation, the total is round 35,000 lines of code with around 3,000 of those implementing the compiler. I still have more library routines to add so the proportion of the system which is the compiler will shrink in time. This is probably quite typical for mature languages with an ISO/ANSI standard. I should also add that the user manual is about 220 pages with at least another 100 left to write, possible more. As you can see the compiler is just a little part of a bigger picture.

You are right that there does not seem to be a compiler forum for language implementation. There is Lambda the Ultimate for language research (sadly mainly a strongly-typed functional language bias) but no well known forum for people who need to know how to implement, test, and report the accuracy of a their logarithm function. You're on your own. So get out the books and learn learn learn. All the information you need is out there and many of the books are easily downloadable from the net.

[Antti]

This is an interesting topic. I am quite sure that many OS developers are also interested in compilers (count me in). If there are enough users, perhaps we could start discussing the topic here?

the second hardest thing to writing an OS is writing a compiler

It depends on features and implementation details. An OS can be quite simple and still be an OS. This same applies to compilers also. I think both can be equally hard. However, when comparing typical hobby OSs and compilers, I think the latter might be a little bit harder.

Compiler writing is easy.

For me it is quite hard.

[Congdm]

Hi,

To write a "unoptimized" compiler for a straight-forward, simple language is quite a simple task. I am writing an Oberon compiler right now and it just takes me a few weeks to nearly complete the compiler (although without Professor Wirth's "Compiler Construction" book, I couldn't learn to write a compiler that fast). As bwat said, getting a run-time system working is way more harder than writing a compiler.

[Combuster]

there doesn't seem to be an equivalent for compiler development.

Compiler development differs from OS development in a few things. The vast majority of our wiki is dedicated to hardware, and relatively little about various bits of theory. For compiler development, the situation is the reverse: The specifications you need are to be counted on one hand, well documented and known in advance. And since you're writing the thing yourself, implementation errors and errata are not the kind of concern you will find in this world.

Project scope and complexity are otherwise the same, and especially something like a c++ compiler is much more technically challenging than the average hobby OS standard.

The challenge is just less troubled with randomness and archaics, and as such the kind of need is different - if you're good in the basics then the Dragon book (I don't have it) is probably going to be sufficient whereas there won't ever be a book that covers OS development in its fullest.

I am quite sure that many OS developers are also interested in compilers

I actually have a sort of compiler in my OS source tree that gets built and then builds parts of my OS (same with a runtime linker, of which I have two now)

[bwat]

For me it is quite hard.

Is there anything in particular that you're having trouble with?
Edit: Is there a certain language you want to compile?

[bwat]

I actually have a sort of compiler in my OS source tree that gets built and then builds parts of my OS (same with a runtime linker, of which I have two now)

This is an example of the application of compiling techniques that what I would call good design. We should always be on the lookout for ways to raise the level of abstraction so we can describe our systems in terms of declarative formalisms - most of the time it just makes sense. Another good example of this in the OS arena is the POSIX regcomp and regexec functions.

[Antti]

For me it is quite hard.

Is there anything in particular that you're having trouble with?

I have been reading the Dragon Book and made some experiments but I am not an expert. Even though I can get some simple C-like syntax (expressions, "if", "while", etc.) compiled to three address code, it is still very far from any practical use. All the experiments I made are implementations of well-thought-out theory. "By the book" they say. Of course it is relatively easy to follow that but there are not much innovations "left" to students.

When I started low-level programming and learned how to get "bootable applications", so called OSs, run, it felt like I was free to do anything. I immediately had much ideas of how I wanted to implement OS features. Now that I play with compilers, I do not have any ideas at all. Everything is "by the book" so far. That is why compiler programming feels quite hard for me.

[Congdm]

When I started low-level programming and learned how to get "bootable applications", so called OSs, run, it felt like I was free to do anything. I immediately had much ideas of how I wanted to implement OS features. Now that I play with compilers, I do not have any ideas at all. Everything is "by the book" so far. That is why compiler programming feels quite hard for me.

I don't think compiler programming is less free than OS programming, you can invent a new language if you want. I think the correct term would be "specific". Compiler writing is more specific than OS writing, because you only need to deal with 1 language when writing a compiler, but an OS need to run on many types of hardware.

[Antti]

I don't think compiler programming is less free than OS programming, you can invent a new language if you want.

Yes, this makes sense. However, I think it is possible to innovate something that "might turn out to be quite OK" when designing an OS without any books. Designing a compiler without any books (research done by compiler experts) will end up being a disaster. Unless you are very smart.

[Congdm]

However, I think it is possible to innovate something that "might turn out to be quite OK" when designing an OS without any books. Designing a compiler without any books (research done by compiler experts) will end up being a disaster. Unless you are very smart.

How can you write an OS without books ? Our holy books for OS developing are datasheets and manuals. "You have not enough datasheets"

But it is true that compiler require more theoretical studying than OS. Any hacker can write a "bootable program" but I doubt any hacker can write a compiler.

[~]

Hey all. They often say that the second hardest thing to writing an OS is writing a compiler, and I happen to be interested in both. The only problem is, we have OsDev.org, which is both a wiki and a forum and altogether a great resource and community portal on OS development, but there doesn't seem to be an equivalent for compiler development.

I tried googling and the only relevant answer I found was here: http://stackoverflow.com/questions/7054 ... ent-forums and apparently other than usenet.comp.compilers (what's a usenet?) and a bunch of github projects, there do not appear to be much reasources.

Is that really all there is to the global compiler development community? Reading the Dragon book and searching Wikipedia for occasional deep topic is fine, but I'd feel much better if I found something more like what we have here.

Sorry if this is a bad question.

I have been trying to learn about these topics, and I see that after trying to write a kernel by reading the generic information around, the next thing I had to try was trying to write a compiler for trying to implement a language that was easier than Assembly and easier than C.

If you want to read about all of the basics for writing a compiler, you can see the documentation and demonstration of my project here:

RealC Compiler and Language Project

I learned what I did with the Jack Crenshaw's compiler tutorial series, here:

Let's Build a Compiler

So you should first define the language and architecture you want to target from your compiler. If you want to create your own language you will have to define it along with the compiler, but it is a good exercise to understand some more system-level internals.
_________________________________

After trying to write a compiler, you will probably try again to implement the most simple kernel possible that you can use to run commands as a first milestone, and then you might try to implement an emulator for your target machine (usually an x86 PC).

But all of these things will be achieved slowly and/or poorly, unless you can have a study/development regime based on very good information, and that you can understand it; obviously the proof that you will be doing things right is that you will do many things that you hadn't done or understood before.

If you at any point feel that you aren't doing things well or that everything is becoming tedious, it means that you will need to find a radically different approach and way of advancing your knowledge and projects (and this is where I am currently at).

Maybe I could suggest that you start by calming down and then let ideas flow. After this you could try to find topics that can advance your skills and that you can integrate as soon as possible with the real world, so that they can be beneficial in the theory or the practice side (but at first I bet you that you will need to understand theory and create test projects before even hoping to build highly capable programs, which lack bugs or deficiencies at a professional level; we even talking about years here).

[dozniak]

Maybe we should start a section on this forum about writing the helper tools, including the compilers, for use in OSDev.

[Yoda]

I'm now starting the compiler project and think that this topic is very interesting. The developers should have the community to discuss various aspects of compilers. Yes, straightforward implementation of a simple language is not very difficult task, the COOL language compiler for MIPS machine may be built in a two months of a not very hard work and is an assignment in a Compilers course of Prof. Alex Aiken @Coursera. But there are lots of optimizations and improvements to do for real compiler which may need a discussion. Also if a new language created, a varius aspects of language design should also be discussed.
I like an idea to create a special section in OSDev forum and Wiki for languages and compilers and I think that this is the good place because compilers and OS are closely related tasks.

[bwat]

Last night I realised that my bottom-up parser generator was broken. I fixed it quite quickly this morning --- a name was misspelled --- and wrote a little compiler to test it. I'll show it here as an example of the absolute bare minimum compiler written in a very high level language.

So, here is the prolog source code for a lambda calculus reducer and compiler.

The input language is the basic lambda calculus described here in a grammar that is used to generate a bottom-up parser. This grammar is left-recursive so top down parsers would have trouble with it.

Code: Select all

%%% slask/parser.bup
parse(E) ::= exp(E), ['.'].
 
exp(variable(V)) ::= variable(V).
exp(abstraction(V, E)) ::= [lambda], variable(V), exp(E).
exp(application(E1, E2)) ::= exp(E1), exp(E2).
exp(E) ::= ['('], exp(E), [')'].

variable(V) ::= [V], {atom(V), V \== '(', V \== ')', V \== lambda}.

The compiler takes the output from the parser and generates terms for a reduction machine. In this case Krivine's machine.

Code: Select all

%%% slask/compiler.pl

:- ensure_loaded('slask/parser').

rho_lookup(VariableName, Rho, Result) :-
	rho_lookup(VariableName, Rho, 0, Result).

rho_lookup(VariableName, [], _, _) :- throw(semantic_error(undefined_variable(VariableName))).
rho_lookup(VariableName, [VariableName|_], Result, Result) :- !.
rho_lookup(VariableName, [_|Rest], Counter, Result) :-
	NewCounter is Counter + 1,
	rho_lookup(VariableName, Rest, NewCounter, Result).

extend_rho(Var, Rho, [Var|Rho]).

compile_lambda_exp(variable(Var), Rho, #Dbn) :- 
	rho_lookup(Var, Rho, Dbn).
compile_lambda_exp(abstraction(Var, Body), Rho, abstraction(BodyCode)) :- 
	extend_rho(Var, Rho, ExtendedRho), 
	compile_lambda_exp(Body, ExtendedRho, BodyCode).
compile_lambda_exp(application(Operator, Operand), Rho, application(OperatorCode, OperandCode)) :-
	compile_lambda_exp(Operator, Rho, OperatorCode),
	compile_lambda_exp(Operand, Rho, OperandCode).


compile_lambda(Input, Output) :-
	goal(parse, [Expression], Input, []),
	compile_lambda_exp(Expression, [], Output).

This is Krivine's reduction machine. It is probably the simplest abstract machine you could get for this purpose.

Code: Select all

%%% slask/krivine.pl
krivine([suspension(Env, Exp)|_], #0, Stack, Result) :-
	!,
	krivine(Env, Exp, Stack, Result).
krivine([_|Rest], #N, Stack, Result) :-
	!,
	M is N-1,
	krivine(Rest, #M, Stack, Result).
krivine(Env, application(Operator, Operand), Stack, Result) :-
	krivine(Env, Operator, [suspension(Env, Operand)|Stack], Result).
krivine(Env, abstraction(Exp), [Top|Tail], Result) :-
	!,
	krivine([Top|Env], Exp, Tail, Result).
krivine([], T, [], T).

Here is the code that ties it all together. Note the use of read_in/1 to tokenise input. No need for a tokeniser here!

Code: Select all

:- op(200, fx, #).

:- ensure_loaded('slask/compiler').
:- ensure_loaded('slask/krivine').
:- ensure_loaded(runtime(readin)).


main_loop :-
	read_in(Input),
	compile_lambda(Input, Code), 
	krivine([], Code, [], Result),
	format('~p~n', [Result]),
	main_loop.

Just to show that it works, we see that when we apply the identity function to an argument, we get the argument back. The output abstraction(abstraction(#1)) is equivalent to (lambda y (lambda z y)), basically a function which takes an argument then returns a function which takes a second argument then discards it and returns the first argument. The #1 says go up the call stack by one argument and return that value.

Code: Select all

| ?- ['slask/main'].
% yes
| ?- main_loop.
|: (lambda x x) (lambda y (lambda z y)).
abstraction(abstraction(#1))
|: 

Doesn't look like much and it is very inefficient, but it is an implementation of a simple lazy functional language which has covered argument passing and functions as first-class values. All that is needed now is typed data (integers, chars, lists), delta reductions (primitive functions, e.g., +, *, /, print, read). It would also be pretty easy to introduce syntactic sugar, e.g., "let V=N in E" translated into "(lambda V E) N". Once it was working they way you wanted it to, you could start thinking about changing the abstract machine into something that would give you much better performance. Then, finally, bootstrap the compiler and runtime system into the language defined.

For more info, see Abstract Machines, A Lambda Calculus Perspective, Werner Kluge.