A full TCP/IP stack in under 200 LoC (and the power of DSLs) | Hacker News Reader

A full TCP/IP stack in under 200 LoC (and the power of DSLs)

moserware.com

132 pointsdschobel20 comments

The "meta-meta language-language" he mentions is OMeta. OMeta combines parsing and lexing and allows you to build your AST in your host language. It's really expressive and beats the pants off any other parsing framework I've used. The Viewpoints group is doing some of the most exciting work in CS right now, there's a lot of other interesting ideas they've been working on.

There are Python and Ruby implementations available. You can play with OMeta here: http://tinlizzie.org/ometa/

aside of alan kay, ian piumarta is working at vpri at cola (common object lambda abstration) and ometa right now. i recently posted a relevant video of alan kay's talk at intel's berkeley research lab on the topic of programming languages:

http://irbseminars.intel-research.net/ (since this link is very interesting in its own right, i am going to post it directly to HN as an article)

I think lisps, such as common lisp, do this too, since they also allow you to manipulate the repl lexer besides defining your own DSL.

Yes, TCP/IP is damned simple if you model it as a trivial lock-step protocol. And this is a slick little piece of code. But it has nothing whatsoever to do with the 10,000+ lines of code that modern operating systems deploy to allow hundreds of competing TCPs to figure out how to share a link.

Interview question: what's the important thing TCP provides over UDP?

Fail answer: I don't know.

Push answer: Reliability.

Win answer: Congestion control.

Can you explain why there would be hundreds of competing TCPs?

I thought there were only a handful (Tahoe, Reno, Vegas, New Reno et al) of popular algorithms for the congestion control bit but it's all still TCP as specced in RFC 2581, no?

From where does all the complexity come?

He probably means hundreds of competing TCP connections across a single link, which is common in the Internet (or in your LAN if you use BitTorrent).

Two laptops attach to a wi-fi hub connected to a DSL line provided by a major telco. One starts a large download. Why doesn't it completely monopolize the skinny straw that connects the 10+mb/s network it actually sees to the gigabit network beyond the DSL? Why can the second laptop start another large download and both see reasonable download speeds? At a more basic level, how do these TCP's even know how fast to drive the transfer? All they see is a multimegabit wireless network. They're not psychic, and there's no configuration box or DHCP setting for "256 kb/s dsl uplink".

That's what TCP actually buys you.

You can make a reliable UDP protocol with a few tens of lines of code. It's called "TFTP", and it's god-awful slow.

This is an important distinction - the difference between production code that takes care of all of the edge cases that make things work in practice and the straight-forward implementation of the basic idea. But I think that's besides the point. The production implementations of TCP could probably be simpler and easier to understand if they were implemented in a similar manner as what's in this article.

It was a risk though, because I had to trust that I understood the problem domain well enough to invest a lot of time in the parser/interpreter. - First comment on blog http://www.moserware.com/2008/04/towards-moores-law-software...

Solving a problem is hard. Generalizing it to a class of problems is harder. Encapsulating it in a language with specialized syntax and semantics is harder still.

I think this is one reason that DSLs are not that popular, and is one reason why most new languages mimic existing languages like crazy (apart from for user-familiarity to ease adoption). The exceptions, like brainfuck and lolcats, use familiar semantics; and are only novel in syntax.

As for a Moore's Law for software, I'm going with Fred Brooks' Law of "No Silver Bullet". Complexity is hard, the best we can do is abstract away foundational concepts into components, as we understand them, and then SOTSOG.

The TCP/IP diagram syntax is really cool - but because it's clear, not because it's short; I think the parsing code in C would actually be shorter than the ASCII art.

Given that DSLs are hard, it does not follow that sticking "foundational concepts" into "components" is a better strategy than DSLs. If you write a DSL, you are standing on the shoulders of real giants. If you rely on components, you are going with the recently formed current conventional wisdom, and you are standing on the shoulders of relative peons.

Note that Fred Brooks argues for conceptual integrity, provided by a single human being, as the most important guarantee of product quality. If you use components, then you are accepting a system partitioning that has been decided many layers above you. If you design languages, then you cut out most of those layers. This gives you far more control over product quality.

Yeah, it's hard. Quality is hard. If your primary goal is anything other than quality, you will probably not produce a product with much of it. That's the real reason why there's no silver bullet.

"If you write a DSL, you are standing on the shoulders of real giants."

In what sense do you mean that? Serious question, not sarcastic. It seems to me that if you build a DSL you're not standing on anybody's shoulders, which seems rather a disadvantage, but I say this to show you what I'm not understanding in your point, not as a criticism, as I believe you meant something else.

You are standing on the shoulders of people who design languages, vs. standing on the shoulders of people who write libraries. Languages are much closer to the central concepts in computing, and the people who work on them have done a lot more careful and general thinking, in general, than what goes into libraries. Libraries are great to build on, but only so long as they are almost exactly what you need already, because you can't change them to any significant degree.

There's a reason why all the best languages (lisp/forth/etc) are language building languages, not library building languages. A library building language is just a DSL that you can't modify. You can write anything in it, but so what? You can write anything in Brainfuck too - that's what the term "Turing tarpit" was coined to describe.

When someone tells you what their favorite language is, you should ask what that person does. If all they do is write web apps, they probably like their language because it is a good web app DSL. Nothing wrong with that, except that it doesn't scale (webapps scale, but they do it by scaling the database, not the language).

Downright impressive. I'm implementing the TCP/IP stack for my OS at the moment, and it's sitting at about 400 lines before TCP (ethernet, IP, DHCP, and ARP). Definitely going to see how I can improve it after this.

Hi Daeken,

That's impressive. Are you writing your OS for study purposes or you have something special in mind? I am interested in knowing as I am planning to do the same and might want to consult you.

There's a post about the background and motivation for the OS (Renraku) here: http://daeken.com/renraku-future-os

If you want to talk more about it or OS dev in general, feel free to ping me on IRC (Daeken on freenode) or on AIM (bloomfilter).

Are you doing this for fun or do you have something else in mind ? I'm curious :)

Just something that's interested me for years. Might eventually become a part of some commercial embedded devices I've planned, but that's a long way out.

A friend of mine made millions selling his TCP/IP stacks since the mid 80s; he has written tens of them, all in various assembly languages.

Let me add that most of his work was for TCP/IP over serial ..

At my startup I'm implementing these ideas from VPRI right now, we focus on implementing a parallel message-passing architecture in hardware and software. Founders wanted!

I thought the language implementation was much more impressive: http://3.bp.blogspot.com/_Zfbv3mHcYrc/R_cAAN-Jc2I/AAAAAAAAAZ...

So close to BNF, and so clear in its deviations. Would be nice if I could use something like this to extend Python or JS and compile to them...

Reply on news.ycombinator.com