OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 5:36 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 118 posts ]  Go to page 1, 2, 3, 4, 5 ... 8  Next
Author Message
 Post subject: CompilerDev?
PostPosted: Fri Sep 20, 2013 5:46 pm 
Offline

Joined: Sat Aug 29, 2009 3:33 pm
Posts: 7
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.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 2:14 am 
Offline
Member
Member
User avatar

Joined: Fri Jul 03, 2009 6:21 am
Posts: 359
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.

_________________
Every universe of discourse has its logical structure --- S. K. Langer.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 3:09 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
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?

Quote:
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.

Quote:
Compiler writing is easy.


For me it is quite hard.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 5:34 am 
Offline
Member
Member

Joined: Wed Aug 01, 2012 10:53 am
Posts: 48
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.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 6:45 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
Zondartul wrote:
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.



Antti wrote:
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)

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 7:07 am 
Offline
Member
Member
User avatar

Joined: Fri Jul 03, 2009 6:21 am
Posts: 359
Antti wrote:
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?

_________________
Every universe of discourse has its logical structure --- S. K. Langer.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 7:43 am 
Offline
Member
Member
User avatar

Joined: Fri Jul 03, 2009 6:21 am
Posts: 359
Combuster wrote:
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.

_________________
Every universe of discourse has its logical structure --- S. K. Langer.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 9:16 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
bwat wrote:
Antti wrote:
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.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 9:36 am 
Offline
Member
Member

Joined: Wed Aug 01, 2012 10:53 am
Posts: 48
Antti wrote:
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.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 10:03 am 
Offline
Member
Member

Joined: Thu Jul 05, 2012 5:12 am
Posts: 923
Location: Finland
Congdm wrote:
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.

_________________
Undefined behavior since 2012


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Sat Sep 21, 2013 10:29 am 
Offline
Member
Member

Joined: Wed Aug 01, 2012 10:53 am
Posts: 48
Antti wrote:
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.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Tue Sep 24, 2013 8:02 am 
Offline
Member
Member
User avatar

Joined: Tue Mar 06, 2007 11:17 am
Posts: 1225
Zondartul wrote:
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).

_________________
Live PC 1: Image Live PC 2: Image

YouTube:
http://youtube.com/@AltComp126/streams
http://youtube.com/@proyectos/streams

http://master.dl.sourceforge.net/projec ... 7z?viasf=1


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Tue Sep 24, 2013 9:16 am 
Offline
Member
Member
User avatar

Joined: Thu Jul 12, 2012 7:29 am
Posts: 723
Location: Tallinn, Estonia
Maybe we should start a section on this forum about writing the helper tools, including the compilers, for use in OSDev.

_________________
Learn to read.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Wed Sep 25, 2013 6:49 am 
Offline
Member
Member
User avatar

Joined: Tue Mar 09, 2010 8:57 am
Posts: 255
Location: Moscow, Russia
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.

_________________
Yet Other Developer of Architecture.
OS Boot Tools.
Russian national OSDev forum.


Top
 Profile  
 
 Post subject: Re: CompilerDev?
PostPosted: Wed Sep 25, 2013 7:22 am 
Offline
Member
Member
User avatar

Joined: Fri Jul 03, 2009 6:21 am
Posts: 359
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:
%%% 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:
%%% 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:
%%% 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:
:- 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:
| ?- ['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.

_________________
Every universe of discourse has its logical structure --- S. K. Langer.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 118 posts ]  Go to page 1, 2, 3, 4, 5 ... 8  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 27 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group