Self hosting OS/Compiler from scratch

[bwat]

A silly example, the usage of higher order programming languages, compared to the use of assembly or even hex, is by the use of programming tools, rather than by the use of software engineering tools, however I'm pretty convinced that writing in a higher order programming language, allows one to deal with several magnitudes of complexity compared to when writing in hex.

Programming language tools is not *the* solution, it is *part* of the solution for complexity.

If you agree, that the use of a complexer higher order programming language (compared to assembly for instance), helps reduce the overall complexity of large systems, then the same argument can be applied to generics.

I just want to point out that, if you mean languages with higher order functions when you use the term "higher order programming", then these languages aren't any more complex. Actually, it seems they aren't even higher order.

[skeen]

In Java, you can use actual generic syntax, which means you get the errors for the implementation on the exact line you wrote them, and the errors for the invocation where you actually call the generic. And because you explicitly used an generic, the compiler can split error reporting at the boundary between call and implementation, and gives the user an explicit error that it is mixing types when it does so, instead of having to pass that type all the way through the macro to see if it works the way you think it does - where the macro in question might have expanded to something that looks acceptable to the compiler when it isn't. And also a feature in Java, a generic costs space exactly once, not for each type you throw at it.

The main issue I see with Java generics, is that while it only generates a single version, this is really because all type information is dropped in byte code, such that what you really get is just a version which accepts Object, and a lot of automatic casts (which are sound, but still nothing but casts). This is in general fine, expect that in Java, you lose the ability to do static duck typing.

Say I have a generic procedure called Dijkstra, which accepts a graph 'g' and a source 's', now in the implementation of this I'd like to do something like; 'g.getNodes()', however because 'g' is really just an object, this will fail. The solution in Java would be to define an interface, named Graph, which has a method named getNodes(), however then you're leaving the generic programming paradigm for the object oriented programming paradigm.

Duck typing, is an essential technique in generic programming, whether dynamic or static.

[bwat]

So let's try to keep using languages that most people understand or can at least relate to, because in truth Ada is a bit alien to me as well, as it took me a while to understand the example, which is a shame, as it ruins the argument and makes it harder to discuss on a common ground.

Ross-Ashby's law of requisite variety says we can't always do this. Here are some paraphrased quotes that spring to mind:

Don't simplify the problem to suit your frame of reference. Widen your frame of reference to suit the problem.

We can't use yesterday's language to discuss today's problems

We shape our tools, then our tools shape us.

[skeen]

Funny thing is, I could implement an assembly optimized version in C++ too (Modulo the lack of a standard inline assembly construct, so we will deal with GCC's for now):

Can you have 6 different versions in assembly language (e.g. one for 32-bit 80x86 without SSE, one for 32-bit 80x86 with SSE, a few for 64-bit 80x86, some for ARM, etc); and have all of them grouped next with the high level code so that it's obvious what the intended functionality is? Will the compiler be able to compile the high level version and one or more assembly versions and make sure they both function the same?

There is ongoing research in this; Intel's C++ compiler actually compiles various versions of the same code, whenever it sees an opportunity for auto-vectorization; i.e. alike what you suggest, one for each configuration, which version to use, is then determined at runtime, using for instance the 'cpuid' instruction and a switch.

So one can imagine this being implemented alike;

Code: Select all

void matrix_mul(...)
{
    int sse = cpuid(...);
    switch(sse)
    {
         // different implementations, for different cpus
    }
}

The issue with this, is the constant rechecking of the non-changing state of cpuid, and the fact that this check may actually stall the SSE pipeline. So what could one do instead? - We could simply generate the check at a higher point in the executable, and simply set some function pointer to the correct implementation at runtime.

The issue is now, that we added an unexpected (and possibly unwanted) level of indirection, in this function pointer. The solution to this, is to simply use the indirection we've already got. Such that the check for cpuid, and the choosing the right implementation is actually done in places where we've already got this indirection, for C++ this usually means in virtual function dispatching.

Using this technique, one can support multiple CPU's only at the cost of a little more memory for the .text section. If the dynamic loader was to help out, it could actually eliminate this, by doing the cpuid instruction, and then loading the best version.

And how long did it take you to learn C++, write any/all libraries you've used, write your C++ compiler twice from scratch, and implement the optimizer that did the vectorization?

I don't think the discussion should focus on C++, because no-one here is going to write all a conformant standard library, and a fully conformant C++ compiler which does auto vectorization, just to use with their OS. Mainly because I doubt most people be able to do so within a single lifespan. The discussion should be above language specifics.

[skeen]

I might be stupid but how are you suppose to check that each parameter to each function is within the desired value range? Each function makes a compare for each parameter before continuing with its body?

What you usually do, is static analysis, namely based upon argument domain analysis (i.e. you try to figure, within which range a given argument may be, and validate that code works for that range).

In Brendan's no overflow approach, this could be something alike a function named double_arg(n), where 'n' must be in the range of 0..(MAX_VALUE_OF_N/2), static analysis then has to check that you never pass something which is larger than '(MAX_VALUE_OF_N/2)' to the function, this is impossible (due to something like rand() or user input (which is really the same)), and hence you may have to attach runtime checks as well, but by using your static argument domain analysis, the compiler can actually insert these checks quite early (like immediately after getting the output of rand()).

[Brendan]

Hi,

Whenever I have to solve a specific task (say implement a code generation phase) in some programming language, my approach is usually (simplified);

My approach is roughly similar. The main difference is that I try to find better ways of doing things than existing ways. If users are involved, this means making it easier for real people (not "academics"), and if users aren't involved this means making it faster, more scalable, etc. If something is written in a book, then it's just a starting point that needs to be improved on.

The other thing I do is separate design from implementation. Often I'll have the ideas rolling around my head for a week or more, write pages of notes, then finally (if appropriate) write down "formal" documentation or specifications. Then I'll try to forget it for another week or more and go back to the notes/docs/specs and try to find holes in the ideas and improve them more.

I don't start implementation until after design is done. Implementation is mostly a mechanical thing - converting a design into something the computer can execute. Because all the design is done beforehand I can concentrate on implementing efficient code. I mostly only use library functions as a way to access the kernel API (e.g. file IO, threads, etc). If I'm able to use generic things from a library (e.g. sorting, searching, lists, etc) then that mean my code is bad (I've failed to do things efficiently enough to avoid needing to sort, search, etc).

For a simple example, how many people here use "strlen()"? To me, that's a sure sign that the code isn't good enough (I failed to keep track of the string's length in previous code).

My point with this, is that I have a somewhat rigid approach to problems, and I want my tools to help me out along the way.
For the programming language tool, what I expect is;

I'd ask what tools you use for designing software, but I already know the answer because everyone's answer is the same (including mine). It's like there's a very important tool that should exist, but doesn't. By the time you get to implementation, you should be focusing on very small details, not the larger picture, but existing tools suck so...

In most language, sorting just requires me to lookup the right name, e.g. 'qsort' or 'std::sort', however for these two, I have to spend time understand the arguments, which is unfortunate.

Sorting is like "strlen()" - if you need to sort something that already exists, then you've failed to do your job properly and sort it while it was being created.

That being said, generics usually help me out, in terms of avoiding the reimplementation of standard algorithms, as I can simply use them with whatever type I like, with little hassle (i.e. implementing a comparator for instance).

I can't think of any standard algorithm I wouldn't "reimplement". Linked lists (and FIFO/FILO queues) and vectors are too trivial to bother with libraries. Hash tables I like to tune (get a good compromise between hash size and hash collisions for the data I'm expecting). Sorting I've already mentioned.

Now as for performance, that is really rarely an issue for me, when doing a new implementation, as I'd rather have the code working first, before I start optimizing it, also having the code running first, helps me profile the bottlenecks of the code.

I never really end up profiling. In theory I should, but I've never been disappointed by my code's performance enough to bother.


Cheers,

Brendan

[skeen]

Except the main cost is normalising the strings, which only happens once per string regardless of how often you compare.

Even if you assume that the string aren't normalised yet, I highly doubt that normalisation dominates when you have O(n²) string comparisons.

Have you ever looked into how much work it takes to normalise unicode strings? It's a table driven cache thrasher and if you're smart you convert the unicode strings into a set of "arrays of weights" and compare those.

Of course you are ignoring the point (the ability to optimise general purpose code to suit a specific case) and focusing on irrelevant details (a silly example).

What matters in terms of complexity is not how much work it takes, but how much work it takes asymptotically. Say one is able to normalize a unicode string in linear time in the number of characters, then then complexity of actually sorting the strings would outweigh the normalization of string.

That being said, I really think you miss the point of generics in terms of optimization, mainly because you should be able to hook into your generics in all places where the generic approach is just not good enough.

[skeen]

For the programming language tool, what I expect is;

# Being able to concisely specify my intent;

Somebody gets it. The talk of C++ and all that comes with it is OK when we're in the domain of low-level OS development but for programming in general there's a world of languages that'll bring you closer to the realm of specification. The Turing/von Nuemann architecture is an arbitrary design that we shouldn't have to take into consideration when writing software. Of course the world isn't perfect and we do not find ourselves in a declarative nirvana (*) but all this talk of C++ is a bit like arguing over the arrangement of the deck chairs on the Titanic when you should really spend your energy trying to find a way off the boat. Avoid the problem by choosing better tools. It's 2013 and you've got more choices than ever before.

*) We still end up thinking about control issues, e.g. machine dependent scheduling, order of evaluation etc.

Indeed there are better languages than C++, for concisely specifying intent, however when you also add the requirement of being able to deal directly with hardware, the set of candidates shrink quite a bit.

I truly believe in choosing the right tool for the job, and sadly it seems my usual tool won't cut it in OS development, and hence I had to pick up another tool. The one I've choose to stick with this far, has been C++ for several reasons, mainly that it supports a lot of 'stuff', some of which is quite nasty, but I'm just trying to navigate around the icebergs.

[skeen]

A silly example, the usage of higher order programming languages, compared to the use of assembly or even hex, is by the use of programming tools, rather than by the use of software engineering tools, however I'm pretty convinced that writing in a higher order programming language, allows one to deal with several magnitudes of complexity compared to when writing in hex.

Programming language tools is not *the* solution, it is *part* of the solution for complexity.

If you agree, that the use of a complexer higher order programming language (compared to assembly for instance), helps reduce the overall complexity of large systems, then the same argument can be applied to generics.

I just want to point out that, if you mean languages with higher order functions when you use the term "higher order programming", then these languages aren't any more complex. Actually, it seems they aren't even higher order.

My point was mainly that languages like C/C++/... helps one to deal with complexity compared to assembly, for instance when it comes down to being able to actually pass code as arguments to other pieces of code, as is usually the case when writing generic code, in the form of predicates or comparators.

I did meapn higher order functions as in passing code as arguments to functions, whether this is in the form of lambdas, virtual dispatching, or function pointers, doesn't matter, as the concept is the same, in functional programming as in object oriented or procedural.

[Brendan]

Hi,

Imagine a triangle like this:

Code: Select all

                  |\
                  |_\
                  |  \
  Skill/knowledge |   \
                  |    \
                  |     \
                  |      \
                  |_______\
                   Number of people

Stupid people like Bjarne Stroustrup and Simon Peyton Jones try their hardest to destroy programming for 95% of the people on earth; and amazing people like Alan Kay are trying their hardest to bring programming to 100% of the people on earth.

Okay, so while I like the idea of having programming be a common skill, alike mathematics, then there's something that I'd like to note;

If somebody is to build a piece of medical equipment, which my life depends on, then I'd like them to be at the top of the triangle, this goes for programmers, as well as other engineers. Because programming correctly in a multi-threaded environment using languages alike C/C++ actually require knowledge, as proven by Therac. - And I'll agree that this is partly because of the languages.

For medical equipment, I agree, but most software isn't as critical.

For programming correctly in multi-threaded environments, I don't think it's the language's fault. The problems are that the "procedural programming" model is bad ( causes the need for locks, etc); and a lot of programmers simply didn't have the knowledge/experience to deal with concurrency properly.

Also I'd like to argue, that programming is not simple, simply because of the immense required complexity of large software systems (i.e. not language complexity, even though that may be contributing), and because of the rather complex mathematical foundation, also Stroustrup is not trying to destroy programming for the 95%, he's trying to make it more accessible! - Which is quite a task with C++ indeed!

I'd argue that designing complex systems is hard (including breaking large things into sufficiently small things that can be implemented easily); while programming should be simple (laborious rather than complex). Like I said in my previous post, the tools for software design either don't exist or suck a lot, so nobody uses them, so design problems end up being implementation problems.

Alan Kay, on the other hand, is indeed doing some fantastic work! Compared to Stroustrup however, he's got the easier approach, as he's not bound by billions of lines of code, which cannot be broken, and an entire C++ committee with various interests and intents for the languages. He's able to focus on one intent, that is bringing programming to the 100%, that being said, Etoys is actually a domain specific programming language in that sense (even though it may be general purpose).

Just for fun, do a google search for "designed by committee"...

To deal with the inherent complexity of large projects, you need software engineering tools and not programming tools. These are things like UML diagrams, and breaking large/complex systems into smaller/simpler things when the system is being designed (before anything is implemented at all). People that think things like generics are going to help with the "inherent complexity of large projects" problem are trying to solve the wrong problems in the wrong tools - these things do not help at all, they only make the "complexity of programming languages" problem worse.

I partly agree, to deal with the complexity of large systems, you definitely need software engineering tools, however if programming tools are able to help you out with the same task, why not make sure of that as well?

Because it's the wrong tool for the job. It's like using belt-sander to cut wood - it's technically possible, and you could improve the belt-sander to make it cut wood better, but you're doing something very very wrong.

Programming language tools is not *the* solution, it is *part* of the solution for complexity.

If you did improve a belt-sander to make it cut wood better, it's very likely that you'd just end up with a tool that isn't as good at sanding wood. Programming languages are tools to help with implementing the design, one small piece at a time, until the entire design is implemented. They aren't a part of the solution for design complexity, just like a belt-sander isn't part of the solution to cutting wood.


Cheers,

Brendan

[skeen]

So let's try to keep using languages that most people understand or can at least relate to, because in truth Ada is a bit alien to me as well, as it took me a while to understand the example, which is a shame, as it ruins the argument and makes it harder to discuss on a common ground.

Ross-Ashby's law of requisite variety says we can't always do this. Here are some paraphrased quotes that spring to mind:

Don't simplify the problem to suit your frame of reference. Widen your frame of reference to suit the problem.

We can't use yesterday's language to discuss today's problems

We shape our tools, then our tools shape us.

I agree, that we can't always do this, but in the current context, the usage of Ada merely provided another syntax, which was 'alien' to some (most?) or us. Bear in my mind, that generics in C++ was actually influenced by Ada.

And while I'd love to use other languages to communicate my ideas, I'd still like to reach the audience. This applies to spoken language as well as programming language, however I doubt most people here would like to spend the time it takes to learn Danish, just for me to express myself in a more native way. I don't want people to learn some language, just to get my point, if I'm able to somewhat loselessly translate it into another language. This also applies to programming languages.

We can't use today's language, to discuss today's problems, if no-one (or only a small subset) speaks the languages of today.

[Brendan]

Hi,

I think you'd go looking for a "sort" thing, find something that's excellent for short lists and bad for your long list (or excellent for long lists and bad for your short lists, or whatever), use it without thinking or caring, never think about what the code is actually doing, never find out that it was bad (because when all your code is bad nothing rises to the top of the profiler's data), and never realise that you could've/should've sorted the list when it was being created rather than doing it after; all because that's the easy thing to do and the thing that generics/templates encourages.

What I don't get is: Why do you think that people are smart enough to choose and even implement the right data structure in a way that it performs really well, but at the same time you think they are too stupid to choose the right existing implementation? That doesn't make any sense. Just by additionally implementing your choice, you don't magically make a better choice (in fact, many people will probably make a worse one, because implementing the right choice is complicated and they don't have the time right now).

We've discussed this already. The first few times they'll get it wrong, learn from their mistakes, and eventually get it right. In contrast, by using an existing implementation they never learn, and there is no existing implementation that is "right" for every specific case.

Yes, with specialisations some code is reused, but then you've got a pieces spread all over the place turning something that should've been easy to read into an annoying "find the shrapnel" maintenance headache.

Right, you get the library and its users separated. That's a good thing.

If you can't find your code any more when more than one file is involved, get better tools.

Code: Select all

Do you                                     honestly think
it's easier                                  to read code
with different                                  pieces in
different                                         places?

You exist in some fantasy land populated by "let's over-engineer a solution to a problem nobody ever had" people. Contact with "real world code" developed by more people like you won't help and will only make you worse.

Funny to get accused of this by you of all people.

I'm the first to admit I've tried very hard to design an OS and language that's better than existing things. It's my projects main goal to find out how things could be if things weren't restricted by historical/compatibility baggage. If you think this means I've been corrupted by academic wankery, I think you're very mistaken .


Cheers,

Brendan

[Brendan]

Hi,

I agree, that we can't always do this, but in the current context, the usage of Ada merely provided another syntax, which was 'alien' to some (most?) or us. Bear in my mind, that generics in C++ was actually influenced by Ada.

And while I'd love to use other languages to communicate my ideas, I'd still like to reach the audience. This applies to spoken language as well as programming language, however I doubt most people here would like to spend the time it takes to learn Danish, just for me to express myself in a more native way. I don't want people to learn some language, just to get my point, if I'm able to somewhat loselessly translate it into another language. This also applies to programming languages.

We can't use today's language, to discuss today's problems, if no-one (or only a small subset) speaks the languages of today.

Excellent! Now look back at my "triangle of knowledge", and assume you're trying to reach the huge audience in the middle of the triangle rather than the negligible minority at the top...


Cheers,

Brendan

[Kevin]

And really I think the discussion of generics, is above language specific details, C++ is merely the vessel for examples, rather than what we are, and should be discussing. Because if we are to actually discuss languages in specific, then I'd like to abandon C++ before someone starts attacking that directly, rather than the concepts we use it to explain, since C++ is indeed a hacky language.

This is actually the reason why I didn't use C++ (besides the other one, that my C++ is really weak). Brendan started with the assumption that generics = C++ templates, and while I can understand that someone finds too C++ templates too powerful because you can do really complex things with them, I wanted to point out that this isn't a problem of the concept of generics in general, but of the specific way that C++ implements them.

Java would have been a reasonable choice as well, but it's a bit less different, so it wouldn't have shown as much things that you can do differently and still have generics (like the explicit instantiation, or explicitly declared required operations, both of which I find really interesting features).

[skeen]

Whenever I have to solve a specific task (say implement a code generation phase) in some programming language, my approach is usually (simplified);

My approach is roughly similar. The main difference is that I try to find better ways of doing things than existing ways. If users are involved, this means making it easier for real people (not "academics"), and if users aren't involved this means making it faster, more scalable, etc. If something is written in a book, then it's just a starting point that needs to be improved on.

What I sketched out was the typical process, that is, when I'm not doing anything research related, but rather doing the somewhat mechanical process of solving a specific task.

When I'm working on my hobby OS or compiler; I do indeed try to find better ways to do things. I try to get rid of the old (and in with the new), because tying yourself to the standard way, limits your creativity, and originality.

The other thing I do is separate design from implementation. Often I'll have the ideas rolling around my head for a week or more, write pages of notes, then finally (if appropriate) write down "formal" documentation or specifications. Then I'll try to forget it for another week or more and go back to the notes/docs/specs and try to find holes in the ideas and improve them more.

I don't start implementation until after design is done. Implementation is mostly a mechanical thing - converting a design into something the computer can execute. Because all the design is done beforehand I can concentrate on implementing efficient code. I mostly only use library functions as a way to access the kernel API (e.g. file IO, threads, etc). If I'm able to use generic things from a library (e.g. sorting, searching, lists, etc) then that mean my code is bad (I've failed to do things efficiently enough to avoid needing to sort, search, etc).

I actually use my implementation as a part of the design process, as it let's me experiment with more than the conceptual idea, this will sometimes help me notice serious flaws in the design, before I'm converting it to industrial strength, the main thing to notice in my list, is that the implementation I get, before refactoring it, is usually quite rubbish, as it's mostly hacked together, to make it work, and test the design.

I used to do the entire design up front, however I've come to find, that quite a lot of issues doesn't show up, until I start implementing, that may just be because of faulty design, but that's my way of weeding out bad designs. Also I'm affected by the entire scrum / agile development movement because of my choice of education.

However, the way I implement, it is not really a mechanical process, but rather a part of the design process. The act of converting the initial implementation, to an industrial strength one, is on the other hand, quite mechanical. As for using generic libraries; I usually just use whatever, when I'm in progress of writing my initial implementation. If I need a container, I'll just use a dynamic array, and change it later, if it turns out some other data structure would be better fit. (i.e. if it turns out i'm doing mostly inserts and deletes, and few lookups).

For a simple example, how many people here use "strlen()"? To me, that's a sure sign that the code isn't good enough (I failed to keep track of the string's length in previous code).

I agree that 'strlen()' is an example of bad design, given that you can just keep track of the length of a string, or even have the compiler do it for you.

My point with this, is that I have a somewhat rigid approach to problems, and I want my tools to help me out along the way.
For the programming language tool, what I expect is;

I'd ask what tools you use for designing software, but I already know the answer because everyone's answer is the same (including mine). It's like there's a very important tool that should exist, but doesn't. By the time you get to implementation, you should be focusing on very small details, not the larger picture, but existing tools suck so...

While most people use the same tools, I must once again, recommend the clang toolkit, it has helped me out immensely in debugging hard to find errors. Also;

For understanding assembly, syntax highlighting is nice (but entirely optional). There is nothing else that I'm aware of (e.g. no complex IDE with all sorts of features) because nobody ever really needed anything else. How many people would work on a large project written in C++ with nothing more than syntax highlighting?

I'm one of those people, that doesn't use a massive IDE, but rather command line tools, my trusted editor and scripts.

In most language, sorting just requires me to lookup the right name, e.g. 'qsort' or 'std::sort', however for these two, I have to spend time understand the arguments, which is unfortunate.

Sorting is like "strlen()" - if you need to sort something that already exists, then you've failed to do your job properly and sort it while it was being created.

If I wanted something to be sorted while creating it, then I'd use a data structure, which had the invariant that the data was always sorted. Then I wouldn't have to sort my data, however data structures with this invariant, comes at a cost, and as such it may or may not be what you need in the given context.

That being said, generics usually help me out, in terms of avoiding the reimplementation of standard algorithms, as I can simply use them with whatever type I like, with little hassle (i.e. implementing a comparator for instance).

I can't think of any standard algorithm I wouldn't "reimplement". Linked lists (and FIFO/FILO queues) and vectors are too trivial to bother with libraries. Hash tables I like to tune (get a good compromise between hash size and hash collisions for the data I'm expecting). Sorting I've already mentioned.

You state that linked lists, and vectors are too trivial to bother with, but in my case. I actually like not having to implement these, while I'm in the middle of implementing something else, and hence I prefer just being able to write vector<int>, rather than have to implement one.

Now as for performance, that is really rarely an issue for me, when doing a new implementation, as I'd rather have the code working first, before I start optimizing it, also having the code running first, helps me profile the bottlenecks of the code.

I never really end up profiling. In theory I should, but I've never been disappointed by my code's performance enough to bother.

I usually never get to profiling either, because it's almost never an issue with the performance when using standard containers, and algorithms.