News for hackers. Stuff that matters.
Re:We Who Value Simplicity Have Built Incomprehensible Machines by loup-vaillant on Saturday May 19, 2012 @09:08AM (#3995847)
I don't disagree, but these points needs highlighting:

> It's easy to complain about complexity, harder to offer a simpler but equally capable alternative.

Want real stuff? Check out VPRI's work: http://vpri.org/html/work/ifnct.htm Right now, they're working on a 20KLOC OS (including desktop publishing, messaging, and the whole compilation chain). That's about 4 orders of magnitude smaller than current systems. Here is their last progress report on the STEPS project: http://www.vpri.org/pdf/tr2011004_steps11.pdf

> The most important part by far is to leave out anything you possibly can.

This is also the most overlooked part by far. I deal with something similar at my day job: I noticed that I am relatively poor at dealing with masses of complexity. My co-workers fare better. On the other hand, they don't mind small unjustified complexities. The latest bit I saw was this (in C++):

  class Foo {
  public:
    out_t1 bar(in_t1 in);  
    out_t2 baz(in_t2 in);  

  private:
    static mem data;
  };

  // example
  Foo foo;
  out = foo.bar(in);
As it turned out, this "class" didn't have any state whatsoever. There was `data` of course, but it was never modified after its first initialisation at program launch. I devised a simpler interface (which happens to be backward compatible):

  class Foo {
  public:
    static out_t1 bar(in_t1 in);  
    static out_t2 baz(in_t2 in);  
  };

  // example:
  out = Foo::bar(in);
It's not much, so they say it's no big deal, and act as if it does not count. But it adds up quickly, often to the point where I can reduce the line count of a procedure by half, without even understanding the code! (I know how to do correctness preserving modifications.)
Re:We Who Value Simplicity Have Built Incomprehensible Machines by pmahoney on Saturday May 19, 2012 @11:53AM (#3996209)
I've seen these VPRI links before. I've read through that PDF and various web pages, but I still have a poor understanding of what exactly they are doing.

Is it possible to summarize in a paragraph how they are able to achieve this LOC reduction? Is it simply that systems like Linux et. al. have been cobbled together by many hands over many years while VPRI has a single vision? Are there coding techniques I can use today in my own work? The only example I've found was a mention of some networking stack that was able to make use of a parsing engine, rather than implementing a custom networking-specific engine. This sounds like nothing more (not to trivialize this task) than choosing the correct parts to turn into reusable libraries and then reusing them.

> they don't mind small unjustified complexities

This is something I've noticed as well. Complex code of my own creation grates on my nerves until I am able to erode it and smooth it out. I get the impression that not everyone feels this way.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by loup-vaillant on Saturday May 19, 2012 @01:47PM (#3996514)
I count 3 "miracles". In ascending order of awesomeness, these would be:

(1) No feature creep. They provide essential functionality, little more. I say that's a good thing, because if you miss functionality, the system lets you build it relatively easily. My guess is, it explains about 1 order of magnitude (it divides code volume by 10).

(2) Factor everything. Again not very impressive, but it goes a long way. Just good engineering principles applied systematically across the system. For instance, they have one graphic stack, which draws everything in every program, including the window manager. They also have one document type. A side effect of this approach is a greatly increased integration. My guess is, it explains about 1 order of magnitude.

(Warning: the divide between (1) and (2) is somewhat arbitrary. In some ways, the STEPS system provide more functionality than current systems. I think the trick is to stop thinking in terms of features, but in terms of capabilities. For instance, UNIX don't have a feature to sort Apache log files by IP address. But it has `sort` and `awk`, and therefore it has the capability.)

(3) Build the right tools. The tools being mostly domain specific programming languages. And that is the impressive part. Their language are so expressive and simple that they can reduce code volume by two orders of magnitude without breaking a sweat. I don't know exactly how they came up with such languages, yet they did. The tree core languages that may interest you here are Ometa http://www.tinlizzie.org/ometa/, Maru http://piumarta.com/software/maru/, and Nile. Ometa is like Lex+Yacc, only much simpler and more general (it lets you transform trees, and flatten them, which makes it suitable for all compilation stages). Maru is a not-so-inefficient self-implementing language, based on 2 cores (lambdas and objects) which can implement each other.

So, 1+1+2=4. Or 1010100=10,000. I'm oversimplifying of course, but I think this gives an idea.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by jules on Saturday May 19, 2012 @05:47PM (#3997187)
The other comments here already explain how they do it on a high level, here I'll try to explain it on a slightly more technical level.

They use DSLs very heavily. The heart of their system is OMeta, a high level pattern matching and transformation language. It works both on flat data (in which case it acts as a parser: transform flat text into structured data) and on structured data, transforming it to different structured data. The compilers for all their DSLs, including the OMeta compiler itself, are written in OMeta.

All these compilers are very short (very roughly 200 lines each?). Because they can define new languages with so little code, they pretty much have a different language for each problem they want to solve. For example for the graphics rendering they define a concise data parallel language, they have a low level intermediate language, and a couple of others (e.g. Maru (Lisp like) and Ants (for implementing WYSIWYG editing) and amusingly the TCP RFC).

Of course DSLs are not enough. If you wanted to make an exact copy of Ubuntu or Windows then no matter how good your DSLs, you're not going to make it in 20k lines. So they simplify the personal computing stack a lot. For example they don't have separate programs for document editing (MS Word), presentations (PowerPoint), internet browsing (NOT the web -- their own web format instead of HTML -- you're never going to be able implement the traditional web stack in 20k lines), email, spreadsheets, etc. Instead they unify all of this in their universal documents. So they don't try to copy, but they try to get something that's functionally equivalent. The result is pretty powerful and potentially more useful: you can put a spreadsheet table in a document, in an email, on an internet page, etc. When they extend the universal document with a new feature (for example graphs, or math typesetting) then all these individual uses benefit, instead of doing each feature N times as we do now.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by zurn on Sunday May 20, 2012 @10:34AM (#3998847)
Links to source code repos can be found at http://www.vpri.org/vp_wiki/index.php/Main_Page
Re:We Who Value Simplicity Have Built Incomprehensible Machines by beagle3 on Saturday May 19, 2012 @01:25PM (#3996448)
> Is it possible to summarize in a paragraph how they are able to achieve this LOC reduction?

I think it hangs on two principles:

1) more expressive tools at the price of performance.

2) use existing data as much as possible, but only complying with standards where really necessary.

1) is using e.e. Ometa & friends, which make it possible to (e.g.) implement a reasonable JS engine on top of any reasonable dynamic runtime with 100-200 lines or so.

2) is using e.g. the RFCs the define IP, TCP and UDP as input to a processor -- thereby, having a guaranteed-to-match-specification implementation, without having to repeat any of the struct/constants/details. The RFCs do not count among their 20K lines -- they are probably 3K lines themselves. The parser that parses RFC into data structures and some executable code IS counted in those 20K - but, last I looked, was less than 100 lines.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by loup-vaillant on Saturday May 19, 2012 @01:52PM (#3996525)
1) But as it turned out, the cost wasn't so high after all. (They didn't expect their graphic stack to run fast enough in a laptop, yet it does.)

2) What, they do not count the RFC they parse? I'd count that as cheating: if the RFC is part of the meaning of the system, it should be taken into account.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by beagle3 on Saturday May 19, 2012 @03:29PM (#3996786)
> What, they do not count the RFC they parse?

No, they don't.

> I'd count that as cheating: if the RFC is part of the meaning of the system, it should be taken into account.

I don't think it is cheating. The RFC text is essentially arbitrary, and "god-given" as far they are concerned -- and must only be adhered to for compliance with other systems. (If they designed their own network protocols, I would have agreed with you). By parsing it and generating code, they guarantee that the code conforms with the spec (which is more than you can say for any other network stack implementation!).

And it's all down to what they are trying to achieve: They are NOT trying to minimize LOC -- if they wanted to do that, they'd build everything in obfuscated APL or J.

They want to get to a state in which a person can understand / audit the entire software stack of a system they are running. 20k was selected as what a person can completely follow & understand in a reasonable amount of time (weeks, not years or centuries)

You cannot (average human "you") understand/audit a TCP/IP stack without reading the RFCs; therefore, they don't think they need to double-count it, and neither do I. Furthermore, if tomorrow the world switches to curveCP, they wouldn't include the related RFCs either -- only the code they had to write to make it work.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by kragen on Sunday May 20, 2012 @12:51AM (#3997974)
Aside from the things described by the other commenters, a big thing they're doing is accepting major performance hits that are no longer relevant. xterm on this netbook renders text onto the screen by copying prerendered glyph rectangles loaded by the X server from PCF files into the framebuffer, because that's how you had to do it in 1984, because you were on a barely-1-MIPS workstation, and if you tried to do something fancier at the time (including masked copies, so you don't need to have a character in your font for á, but can overstrike a ́ and an a) xterm would have displayed text noticeably slowly. But this level of optimization is kind of a waste on this 1000-MIPS netbook, let alone a 30,000-MIPS desktop machine. And it costs a lot of code complexity.

By contrast, STEPS treats each letter as a polygon or group of polygons, and rasterizes your polygons when it's time to draw them. So, among other things, you can rotate, scale, and color your text just like any other object, and the amount of code devoted to text rendering is tiny. The performance cost may be one to three orders of magnitude in that case, but that's acceptable for an interactive windowing system.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by haberman on Saturday May 19, 2012 @12:31PM (#3996302)
> Want real stuff? Check out VPRI's work

I didn't mean to make it sound like simplicity is not possible. Quite the contrary, I believe it is possible and extremely worthwhile, and it's something I have dedicated an enormous amount of time to in my own work.

All I'm saying is that the essay was not worthwhile to me, because it offered no insight that helps us get there.

> It's not much, so they say it's no big deal, and act as if it does not count.

I agree that your version is far superior, and that it is a big deal. If I saw code that constructed a class but the class didn't have any state, it would interrupt my flow while I stopped to figure out wtf is going on.

Re:We Who Value Simplicity Have Built Incomprehensible Machines by loup-vaillant on Saturday May 19, 2012 @01:16PM (#3996415)
I didn't mean to imply that you meant what you didn't mean… That was poor phrasing on my part. Actually I agree with you. Saying that something sucks is worthwhile only when few know it. When everyone does, we ought to take the next step, and propose solutions (or at least analyse the problem more deeply than it has been). I was just saying "there! There! A solution!!".