Self hosting OS/Compiler from scratch

[Brendan]

Hi,

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?

Yes, you can have a version for each (its' somewhat convoluted, but that's what happens when you're past the edge of the language standard. Of course, somebody could submit a proposal to the C++ standards committee to support this; you might even unify the syntax with that of the C++AMP extentsion which enables running a subset of C++ on the GPU. Even better, somebody could teach LLVM how to compile multiple versions automatically.)

How is the compiler supposed to understand the behavior of "std::sort" without omniscience? If your answer to that is "you write some tests"... well, you can write your tests in C++ as well. And then you could explicitly test those specializations.

Ah - no, not different specialisations and not understanding the behaviour. The same function (same data types, same parameters), just with several versions in different languages and optimised for different CPU features.

For example, imagine you've got 12 different versions of a "u32 findGreatestCommonDivisor(u32 first, u32 second)" function. Maybe 9 of them can't be executed on the CPU; one is high level language code, one is 32-bit 80x86 with SSE and one is 32-bit 80x86 without SSE. Compiler can generate code for the 3 different versions, give them the same inputs and check that they all return the same outputs. Of course it might not be able to test every possible combination of input values (at least, not quickly enough), but it can certainly test the edge cases and a few thousand "random" values (and maybe just keep on going until someone presses a "cancel" button). Also; for a distributed system you could push it out to remote systems, increasing the number of versions you can test (e.g. the PowerPC assembly version and the ARM assembly version and the 80x86 assembly version, all being compared to the high level code version at the same time on different computers).

For "pure functions" (no side effects) this is relatively easy, and there's good reasons for the compiler to detect if a function is pure or not anyway. Beyond that it gets tricky.

For example, if the function reads/writes to memory, then you'd have to make sure any memory that will be read is the same for all versions beforehand, and check that any memory modified is the same for all versions after. Another problem is when the function happens to use the kernel API - you can check if all versions pass the same arguments to the same kernel API function, but checking any further than that is likely to be difficult or impossible.

For the "tricky" cases, the simplest way is to require a unit test to set things up properly and test the results. In that case you'd be testing to make sure all versions (that can be run) pass the unit test; rather than making sure each version produces the same output from the same inputs without any unit test.

If you decide that for strings you're doing a lot of lookups/searching and want to switch to a hash or something instead of an array (and end up wanting a merge sort for the rare cases that you do sort) then guess what, it's all spread everywhere. It's completely idiotic.

What? Now we are sorting hash tables?

Now we're converting the original "general purpose slop" into something better suited for specific cases. E.g. originally it used a generic sort, then we decide it'd be better to switch to a hash or something for one specific case.

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 optimiser that did the vectorisation?

Did your compiler tell you there's a potential bug on every single line of that code? Hint: See if you can write a list of all the cases that overflows can/will cause incorrect results.

Bogus argument detected! "Implementing this is hard so its worthless to me?"

Given that the topic is about writing an OS and compiler from scratch, there's nothing bogus about this argument at all. Everything is easy if someone else does all the hard stuff for you.


Cheers,

Brendan

[Brendan]

Hi,

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?

You keep track of the range of values that could possibly be in every variable at each specific point (for every single piece of code).

Of course you only need to look at one function at a time, and it gets much easier once you break the function down into a simplified form (e.g. SSA).

The main problem is how the language is designed. If you say "all things that the compiler suspects could lead to overflow are errors" then it's very different to "overflows cause undefined behaviour that we know programmers will abuse and therefore can't assume are errors".


Cheers,

Brendan

[Brendan]

Hi,

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).

Well, that's not much different from the programmer that only cares about search algorithms and has to wade through several different files of puke just to figure out where all the copies of the bubble sort code have gone that they want to replace with quicksort.

Does that ever happen for any application programmer (or any programmer, excluding people writing libraries)?

Why don't people working on libraries count? That's real code as well.

If you assume the number of people who use the library is greater than the number of people that write the library, then you have to assume that people writing libraries are a minority. Note: if you assume the number of people writing the library is greater than the number of people using it, then you have to assume something is seriously wrong.

Typically you're working on a specific area, like adding a "search for keyword" feature, or parsing data from a file, or figuring out some problem with some networking code; and never care about all code for searching all data types (or all code for all lists, or ...) at the same time.

In practice, when I work on a feature, and I find out that the existing infrastructure isn't quite good enough, I don't add a specific hack for my specific feature, but I try to do it right, so that people working on other areas (perhaps myself a few weeks later) can take advantage of it, too.

So, if you're asked to do add 2 numbers together, you'll worry about code that you may never need at all; including code to add vectors, code to add strings, code to add matrices, code to add people, code to add web pages, code to add spreadsheets, and code to add everything else everyone could possibly imagine; and then spend the rest of your life writing unit tests and never actually finish writing code to add the 2 numbers that actually mattered?

If you've got a function that accepts "TestStruct" you get a compile-time error if you accidentally try to pass a "BrendanStruct". If you've got a generic/template (or macro) and you pass a "BrendanStruct" you get no compile-time error and the compiler generates a function for that type instead (assuming that the generic/template thing actually works for more than one data type).

Oh, really? I'm not sure to which of the functions I should pass the BrendanStruct array because it should be obvious that it works neither with the IntSort, nor the StringSort, nor the StructSort, and as you can probably infer from the existence of the other instantiations of the function, not with the generic sort either. I did it anyway for all of them (tell me if you have more creative ways of doing it that I should try out):

Code: Select all

    foo: BrendanArray := ((x => 6), (x => 2), (x => 7), (x => 6));
...
    IntegerSort(foo);
    StringSort(foo);
    StructSort(foo);
    sort(foo);

Code: Select all

test.adb:90:17: expected type "IntArray" defined at line 31
test.adb:90:17: found type "BrendanArray" defined at line 66
test.adb:91:16: expected type "StrArray" defined at line 38
test.adb:91:16: found type "BrendanArray" defined at line 66
test.adb:92:16: expected type "StructArray" defined at line 54
test.adb:92:16: found type "BrendanArray" defined at line 66
test.adb:93:05: must instantiate generic procedure "sort" before call

Thank you for proving that generics don't work (e.g. don't accept any data type without specialisations).


Cheers,

Brendan

[HoTT]

Thank you for proving that generics don't work (e.g. don't accept any data type without specialisations).

It's no problem to have generic functions that e.g. sort every random access range with elements of T, if T can be assigned/moved, given a comparator f such that f(a, b) iff a < b. It's not a problem to automatically fall back to a global comparator like a operator<, if it is available for T. It was never about supporting all types, but all suited types.

If you are concerned about costs of comparisons you could use an generic schwartzsort routine instead.

You can even wrap the result type with a Sorted(T) typewrapper that allows lookups after sorting to use binary search automatically.

This is called abstraction which has proven itself a useful technique both in computer science and math.

So, if you're asked to do add 2 numbers together, you'll worry about code that you may never need at all; including code to add vectors, code to add strings, code to add matrices, code to add people, code to add web pages, code to add spreadsheets, and code to add everything else everyone could possibly imagine; and then spend the rest of your life writing unit tests and never actually finish writing code to add the 2 numbers that actually mattered?

Oh, please.

[Brendan]

Hi,

Ok, so let's summarise. In general there are 3 categories:

• generic/templates that don't avoid code duplication, and end up being complex messes with individual pieces scattered all over the place (specialisations, operator overloading)
• generics/templates that do avoid code duplication, but end up being complex messes that have to handle a wide range of data types and typically fail for unexpected corner-cases (and then up being generics/templates that don't avoid code duplication)
• generics/templates that are neither of the above cases, that are so simple that it's easier to write the code yourself than to bother finding it or figuring out the args, etc

Of course I am exaggerating a bit here; but...

This entire discussion originated from from this:

Yes - keep the language clean and simple. This makes it easier for you to write the compilers, but also makes it easier for other programmers to learn and use your language later (including making it easier for programmers to find bugs). If you must add fancy features, add features that help humans avoid mistakes and/or make it easier for people and compilers ensure that code is correct. Don't add features that make things more complex, or more ambiguous, or make it harder to ensure code is correct (e.g. templates/generics, operator overloading, etc).

Remember that it's easy to add more complex feature to a "too simple" language later on (without causing compatibility problems and breaking older code written for your language), but virtually impossible to remove features from a "too complex" language later.

Basically all I was saying is keep it simple, you can always add more complex features after you've got "version 1" working.

But no, that can't make sense! Apparently you have to support 150% of everything in the latest C++ spec in "version 0.0.2" of your compiler; and that's all extremely easy to do (if you're someone that's never had to do any of the hard work yourself)...

Of course there are also other (perfectly valid) reasons to not support generics/templates; like making sure people like Kevin and Owen never go anywhere near my project. You might think I'm joking, but I really do agree with Linus on this.


Cheers,

Brendan

[Kevin]

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).

The point is, you can always do this, should need arise. Even with programming languages that support generics. But you don't have to for the majority of cases where the generic version works just fine.

Thank you for proving that generics don't work (e.g. don't accept any data type without specialisations).

You have a strange concept of working generics. I still have only one parametrised implementation and I instantiate it for multiple data types. This is exactly what generics are about and what I consider useful language functionality.

If you think it's a problem that I need to tell the compiler for which types I want it, that probably means that you think that C functions don't work either, because you have to declare them before you call them.

Basically all I was saying is keep it simple, you can always add more complex features after you've got "version 1" working.

And you're right with that, but it's not all you were saying. You were saying that generics are features that make things more complex, or more ambiguous, or make it harder to ensure code is correct and confirmed in the following discussion that you think they are something you should never, under any circumstances allow into a programming language, no matter which version.

This is a completely different approach to it than "Looks like a cool feature, but a bit scary to implement. Maybe I'll consider it for version 2." (Which might be myself if I were to write a compiler.)

[Brendan]

Hi,

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).

The point is, you can always do this, should need arise. Even with programming languages that support generics. But you don't have to for the majority of cases where the generic version works just fine.

Sure, but once it's buried under several layers of abstractions it's harder to find the performance problem and harder to fix it when you do.

Thank you for proving that generics don't work (e.g. don't accept any data type without specialisations).

You have a strange concept of working generics. I still have only one parametrised implementation and I instantiate it for multiple data types. This is exactly what generics are about and what I consider useful language functionality.

If you think it's a problem that I need to tell the compiler for which types I want it, that probably means that you think that C functions don't work either, because you have to declare them before you call them.

Either generics save work (e.g. same code for many data types) and can't catch "wrong type" bugs, or they don't (different specialisations and/or operator overloading for different data types) and can catch "wrong type" bugs. You're attempting to pretend that they do both at the same time. This is nonsense.

Basically all I was saying is keep it simple, you can always add more complex features after you've got "version 1" working.

And you're right with that, but it's not all you were saying. You were saying that generics are features that make things more complex, or more ambiguous, or make it harder to ensure code is correct and confirmed in the following discussion that you think they are something you should never, under any circumstances allow into a programming language, no matter which version.

This is a completely different approach to it than "Looks like a cool feature, but a bit scary to implement. Maybe I'll consider it for version 2." (Which might be myself if I were to write a compiler.)

Yes, and I still hold that view. It's not what started this mess though.

Mostly, I doubt anything I say will ever make you realise "fancy puke" is counter-productive - you're an "academic" (and no, that is not a compliment).


Cheers,

brendan

[Kevin]

Sure, but once it's buried under several layers of abstractions it's harder to find the performance problem and harder to fix it when you do.

I think this is a mostly theoretical problem. If an algorithm sucks, it usually sucks no matter what data type it touches, so you can find and fix the problem in the generic version. In the exceptional case that it doesn't, you can still profile and analyse that version, which will hopefully show you why a specific instance doesn't perform well. And then you'll probably have to switch it to some different implementation, because it used the wrong abstraction.

This is like breaking up a function when you see that it's used in too different situations. It happens, and when you see it, you fix it. No big deal.

Either generics save work (e.g. same code for many data types) and can't catch "wrong type" bugs, or they don't (different specialisations and/or operator overloading for different data types) and can catch "wrong type" bugs. You're attempting to pretend that they do both at the same time. This is nonsense.

No, what's nonsense is the notion that differernt specialisations mean no code reuse (specialisation not in the meaning of those C++ template implementations for one specific type, but of instantiations of a generic function like in my Ada code). As you can see in my code, I did reuse the sort algorithm and it does save work. The instantiation for each data type is additional code indeed, but in contrast to a search algorithm (or whatever the generic function you have) it is trivial code that is hard to get wrong.

Mostly, I doubt anything I say will ever make you realise "fancy puke" is counter-productive - you're an "academic" (and no, that is not a compliment).

Not sure about you, but I have enough contact with real-world code.

[Brendan]

Hi,

Sure, but once it's buried under several layers of abstractions it's harder to find the performance problem and harder to fix it when you do.

I think this is a mostly theoretical problem. If an algorithm sucks, it usually sucks no matter what data type it touches, so you can find and fix the problem in the generic version. In the exceptional case that it doesn't, you can still profile and analyse that version, which will hopefully show you why a specific instance doesn't perform well. And then you'll probably have to switch it to some different implementation, because it used the wrong abstraction.

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.

Either generics save work (e.g. same code for many data types) and can't catch "wrong type" bugs, or they don't (different specialisations and/or operator overloading for different data types) and can catch "wrong type" bugs. You're attempting to pretend that they do both at the same time. This is nonsense.

No, what's nonsense is the notion that differernt specialisations mean no code reuse (specialisation not in the meaning of those C++ template implementations for one specific type, but of instantiations of a generic function like in my Ada code). As you can see in my code, I did reuse the sort algorithm and it does save work. The instantiation for each data type is additional code indeed, but in contrast to a search algorithm (or whatever the generic function you have) it is trivial code that is hard to get wrong.

Sigh. This is like trying to wipe your butt with grease-proof paper - the turd just keeps sliding around. 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.

Mostly, I doubt anything I say will ever make you realise "fancy puke" is counter-productive - you're an "academic" (and no, that is not a compliment).

Not sure about you, but I have enough contact with real-world code.

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.


Cheers,

Brendan

[skeen]

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

• # Understand the task at hand by;
  • ¤ Reading the specification for the code generation phase
    ¤ Refreshing background knowledge, i.e. by scanning the code generation section of the dragon book.
    ¤ Reading up on related code/documentation, i.e. the specification / layout of the AST, and the specification / layout of the output instructions.
    ¤ ...
  * The required beforehand knowledge is in place.
  # Write a conceptual idea down;
  • ¤ For instance doing pseudo code / comment implementation of sections
    ¤ Possibly iteration several times on the conceptual idea
    ¤ ...
  * The conceptual idea, has been conceived
  # Write down the skeletal structure of the program;
  • ¤ Find points of logical separation
    ¤ Find points of standard operations, i.e. sorting, searching, ect.
    ¤ ...
  * The conceptual idea, has been concreted at an abstract level
  # Do a quick concrete implementation of the conceptual idea
  • ¤ Test that the design works, ect.
    ¤ Possibly iterate on the design
    ¤ ...
  * The implementation works, confirmed by unit tests (may be a bit slow, ect.)
  # Documentation, followed by initial distribution.
  * The code is now usable to everyone else, and component testing may be executed.
  # Refactor and recode the concrete implementation, to make it industrial strength
  * The code is now industrial strength, and is trusted to work
  # Further refactoring, bug fixes, ect.

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;

• # Being able to concisely specify my intent;
  This is usually where most programming languages fail on me, and C++ is no exception!!
  Whenever I have to wrap my head around language specifics in order to be able to express my intent, I lose focus on the task at hand, get irritated and the net result is a bad outcome.
  
  # Being able to focus on the task at hand
  In addition to the above, I prefer to be able to focus on my specific task, rather than focus on implementing sort, search, ect. Whenever I need something, then I expect to be able to write this intent directly, alike;

  Code: Select all

  let list = [ 1 ; 3 ; 9 ; 2 ; 5 ; 4; 4; 8 ; 4 ] in
  sort list
  

  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.
  
  # Being guided to a correct implementation
  This, to me at least, usually means having a good static type system, and without the forced type annotations!
  It also means having good tools, which can help in the profiling / debugging process.

I hope that we can at least agree on the intents of the above, that is, to be able to focus on the task you're given without having to re-implement standard algorithms, or fight the language.

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). For instance the example in the above could easily be changed to;

Code: Select all

let list = [ "ok" ; "sure" ; "Brendan" ; "whatever" ] in
sort list

If I went with a struct, I'd have to specify how I would like to sort it, by intent could be; by some variable followed by some other variable, and the specification of that intent in a comparator, isn't that bad (at least not to me).

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.

As for having multiple sorting algorithms; I actually prefer letting the library deal with this. When my intent is to sort something, I actually don't care how, as long as it's 'optimal' for my case, i.e. I don't care if the implementation uses randomized quicksort, shellsort, or whatever, but I would expect that if the input is like in the above examples, it should use something like insertion sort, while if the input is some huge array of integers (to be sorted in ascending or descending order), then I'd expect the implementation do so something like multi-threaded MSD radix sort.

[skeen]

Imagine a triangle like this:

Code: Select all

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

A huge area (from the bottom of the triangle up) represents about 6.5 billion people who have no experience programming at all. At the tip, most of that small area represents normal programmers (ranging in skill). A very tiny part at the very top of the triangle represents people that understand the more advanced things (like template meta-programming). The highest point of the triangle represents a single person who is likely to be smarter than Einstien.

Near the bottom you've got (e.g.) 4 year-olds that understand concepts like conditions "if (you don't eat that spinnach) { you get no ice cream for dessert }". Above them you've got 10 year-olds that understand basic algebra like "x = y*2 + k", and can easily understand concepts like loops and functions.

Now have a look at something like Etoys. I've seen videos (here's one done by Alan Kay himself) where kids are doing programming to model the behaviour of thousands of ants; not because they're learning programming, but because they're learning about ants. On the other hand, we've got people spending tens of thousands of dollars and 4 years (or more) of time to go to university, not to learn about complex things (like the biology of ants that leads to complex group behaviors) but to learn simple things (like programming).

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.

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!

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).

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?

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.

What I do think is that the benefits are not worth the increase in difficulty/complexity; regardless of how large/small the increase is.

Just because you don't see the benefits of generics, does this mean it's always bad?

No. For example, stabbing a stranger in the face is almost always bad, but there are cases (e.g. a terrorist about to detonate a bomb and kill thousands of people) where it could be a very good thing. In the same way, generics are almost always bad, but there are cases (e.g. a terrorist trying to program a nuclear missile guidance system to use for killing thousands of people) where it could be a very good thing.

Also note that I *do* see the benefits of generics. In my eyes these benefits are small. I also see the disadvantages. In my eyes the disadvantages are massive.

The fallacy of accident is an unsound argumentation technique.

And I know you don't think that the benefits outweighs the disadvantages, and really that's your loss. I just hope, that I'll never get to work on your project, which is a shame to state, because I honestly think that what you're doing is really interesting!!

[skeen]

Skeen might have been right for containers, but not all templates are containers. I was more interested in "all templates" rather than some restricted subset, and replied with this:

"If all you do is replace your payload data type with T, then you've probably ended up with a template that works with some data types (e.g. integers) and fails with others (e.g. strings); and while you may think that was easy some other sucker that tries to use it only to find it doesn't work probably won't think it's so easy."

Now; skeen was talking about containers, but never mentioned any specific type of container (and certainly didn't mention associative maps). My comment was mostly about templates in general (rather than just one use of templates) and didn't mention any containers (and certainly didn't mention associative maps). For the entire topic (not just this part of the conversation) I'm quite sure that nobody has mentioned "associative map" anywhere at all.

Basically; you didn't know what you were responding to and now (by saying "Obviously you can't just take any arbitrary function and make it templated") you're agreeing with what I was saying in the first place. Of course facts are inconvenient, so you accuse me of making a straw-man while at the same time pulling "associative maps" out of some undisclosed magic orifice. Nice job.

Indeed my point was on containers, rather than on algorithms, however I do believe that any algorithm can be rewritten as a generic one, the main point here, is just to restrain the generic arguments necessarily; say you have the same the algorithm, which works on two different finite fields, say one for F2 and one for F3.

What you do, is that you combine them into a single generic implementation, while restraining the domain of acceptable types, such that only finite fields may be given as argument, i.e. an infinite field shouldn't be accepted, neither should integral domains or commutative rings, because they are entire different constructs, for which the algorithm doesn't apply. - As your algorithm should have been restrained to only accept, say numerical types.

Just as a side note, N3580 (Concepts Lite), if I recall (cba to look it up) actually work on brining this restraining to C++ templates.

[bwat]

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.

[Kevin]

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).

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.

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.

[skeen]

A few comments on the discussion of Kevin's Ada example; While I like you approach (Kevin) for taking the discussion away from C++, I think it's troublesome to do so, in this context, given that most people who do OS development mainly use C related languages, this is the main reason why I choose to focus my argument on C++, as it's less 'alien' to most programmers in this fora.

I don't think C++ is a very well designed language, in terms of dealing with generics, compared to say Java, Ada, dynamic languages, ect., however people like Brendan have to choke on less 'alien' syntax when inspecting it, which qualifies it for being a representative for generic languages on this fora.

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.

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.