7 ms·

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

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.

beagle3 14y ago
> 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.
- loup-vaillant 14y ago
  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.
  - beagle3 14y ago
    > 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.
loup-vaillant 14y ago
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/ http://www.tinlizzie.org/ometa/, Maru http://piumarta.com/software/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.
jules 14y ago
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.
- zurn 14y ago
  Links to source code repos can be found at http://www.vpri.org/vp_wiki/index.php/Main_Page http://www.vpri.org/vp_wiki/index.php/Main_Page
kragen 14y ago
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.

beagle3 14y ago

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

loup-vaillant 14y ago
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.
- beagle3 14y ago
  > 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.

loup-vaillant 14y ago

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/ http://www.tinlizzie.org/ometa/, Maru http://piumarta.com/software/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.

jules 14y ago

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.

zurn 14y ago
Links to source code repos can be found at http://www.vpri.org/vp_wiki/index.php/Main_Page http://www.vpri.org/vp_wiki/index.php/Main_Page

kragen 14y ago

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.