8 posts tagged “geekery”

Reduce! Reuse! Recycle!

Jul 29, 2008
Post a comment

ZOMG. I just found this paper written by David Teller in 2004. It's freaking awesome.

Abstract

Although limits of resources such as memory or disk usage are one of the key problems of many communicating applications, most process algebras fail to take this aspect of mobile and concurrent systems into account. In order to study this problem, we introduce the Controlled π-calculus, an extension of the π-calculus with a notion of recovery of unused resources with an explicit (parametrized) garbage-collection and dead-process elimination. We discuss the definition of garbage-collection and dead-process elimination for concurrent, communicating applications, and provide a type-based technique for statically proving resource bounds. Selected examples are presented and show the potential of the Controlled π-calculus.

Dead process elimination! Just what I was hoping I wouldn't have to invent myself! Thank you, Dr. Teller!

Zen and the Art Of Static Type Inference

Jul 29, 2008
Post a comment

Hee!

The Koan of Static Type Safety

A disciple of another sect invited Markus Mottl to the beach. As he is driving his car along, he tells Markus: "Dynamic Typing makes me more productive! I can write my program faster if I do not have to worry about the compiler complaining about types". Since it is a long trip, the disciple of Dynamic Typing decides to make a stop for petrol. He enters the station to pay for the fuel and purchase a slurpee, while Markus attends to the refueling. Markus notes that the petrol pump is in use, so he starts pumping diesel fuel into the disciple's car. The disciple cries out, "Hey! What are you doing, this is a petrol car!". Markus replies, "Well, I wanted to get to the beach faster".

More Things I've Learned About Compiler Design

Jun 28, 2008
Post a comment

When your language allows the programmer to specify the precedence of operators, you're going to have a hard time parsing it with a grammar accepted by Yacc. That's because Yacc produces LALR(1) parsers, and that isn't going to work for you. Fortunately, for my current project, I have a really nice module of parsing combinators in my OCaml NAE Core Foundation that can produce LL(x) parsers. What's so nice about it? I can still use a static lexer with it, and I've got a nice lexical analyzer already. (It supports layout boxes like the ones planned for Haskell', which is the first reasonable model for whitespace sensitive syntax I've ever seen.)

So— what do you know? It turns out all that fiddling around wasn't necessarily a complete waste of time.

"Compilers You Can Formally Trust"

Jun 26, 2008
Post a comment

Oh, now that is rude.

How much do YOU trust your compiler? Is your compiler on your side? Or is it on the other side? How would you find out? If you could find out, would you really want to know? How would you react if you discovered your compiler was lying to you? Spying on you for your enemies? Sabotaging your programs? Terrorizing your users?

Don't just report your compiler! Certify it!

(On a related note... should I be worried that this is French project?)

F⋎!

Jun 26, 2008
Post a comment

Thanks to Didier Rémy and Benoît Montagu, I now have a solution to my type system problem.

ML est mort! Vivat F^⋎! Vivat! Vivat! Vivat!

Where Is James?

Jun 1, 2008
Post a comment

I've been distracted lately while other things have been happening, and I haven't had much time to comment on them. Here's a bit of catching up...

Apparently, my Future Without IPv6 rant got picked up at Reddit.com, and it prompted some unexpected discussion around the web (you can find it yourself). Much it is the predictable combination of denial and magickal thinking that goes with the territory, but some of it is thought provoking. One of the more interesting responses came in the email from the author of RFC 1669. My reply: "Yep, you sure called it." I wish I had time to offer a more cogent reply to the contributors who had interesting things to say at Reddit, but like I said: distracted. Maybe next weekend.

This weekend, I'm up to my eyeballs in non-techie things. The bottles for the next batch of Tumultuous Uproar Imperial Stout are currently sanitizing in the oven. There's a batch of Six Dæmon that needs to be racked as soon as the stout comes out of its carboy. Also, it's finally time to pitch the blackberries into the lambic I started over two years ago. (Yes, folks: that bump in the pellicle is not a scary fungal growth on the top of my beer; it's the hygrometer I left in the wort, and which is now completely unreadable.)

After that, I hope I'll be able to finish the penultimate chapter in the second draft of my dumb fantasy novel. I put it aside a few weeks ago, and I'm starting to get antsy about not having done anything with it.

On the techie side of things, I recently got a bug report that my OCaml Network Application Environment code that ships in Debian is failing their build. It doesn't compile on the latest version of OCaml. The code in CVS does, but I haven't packaged up a release yet. Gotta do that soon.

The other big technology thing that has me distracted right now is LLVM. It turns out there are pretty good OCaml bindings for language front-ends that target LLVM, so I'm now excited by the possibility that lowly imbeciles like me could be authors of useful programming languages that compile down to fast, tight machine code for a wide variety of processor architectures. The LLVM people have done all the really scary heavy lifting by taking the difficulty of writing a back-end out of the process of writing a new language. With OCaml for a development tool, even a blithering moron like me can write a front-end for a new language, so that's what I'm playing with these days.

Why does James want a new language? I can hear you asking.

After learning OCaml, Haskell, Scheme, Objective-C, C++, Perl5, Python (not in that order), it really fricking pains me that I still have to use C89 as a programming language. I write embedded software for a living. Stuff that runs inside the kernel is high-level code for me. In the kernel, you've got all kinds of operating system services available: threads, dynamic storage, etc. You can sorta get away with arguments to the effect that "a tasteful subset of C++" is appropriate for code that runs in the kernel, but they start breaking down in embedded development environments where you're really constrained on code size. Most embedded software developers just laugh out loud when you tell them that you're serious: they should have written that in Python.

I want a language with the following properties (listed in order of descending importance):

Suitable for embedded systems development. "Can I write a microkernel with it?"
Accurate garbage collection of the dynamic store is available, but optional.
Safe pointers, à la Cyclone.
A Hindley-Milner type inference engine.
Language front-end knows all the semantics, so error messages are sensible, i.e. no text preprocessor.
Some additional hackery to make interfaces with build systems not have to suck so much. (More on that later.)
Built-ins for concurrency, à la JoCaml or Concurrent Haskell. (Cyclone fails here.)
Syntax that doesn't make me want to claw my eyes out while I'm reading my own code. (Cyclone fails badly here.)

Can I do this? Probably not. I am not the mad scientist I used to be. (I was never going to be one of the sparkiest of the sparks anyway.) But LLVM is so freaking awesome, I feel compelled to try and fail rather than not to try at all.

I've got a tiny little bit of the language implemented at this point, i.e. basically just some of the constant expression evaluations and a portion of the abstract syntax tree construction for the primitive types. I'm a long way off from even opening the LLVM modules.

One of the things I'm doing that doesn't seem like the usual approach used by more experienced language designers (I'm curious to know why) is that I'm focusing early on making the error messages and warning produced by my compiler as useful and descriptive as possible. (I'm taking a cue from the Clang developers here.)

For example, here's a little snippet of test code in my crazy language that I'm currently using:

(#--- This is a test ---#) static w a := 64 / a static g := 32
packet v a b := a array[w b] packet b := word 8 packet p z i := b sign -zvma z array[i] sign -o packet r := v [form [k :: word g, n :: b array[w 128]]] 2
##| STATIC EXPRESSION TYPE ERROR static k := w ()
##|-- End of file

This code is supposed to assign the static variable 'k' the result of applying the void literal to the static function 'w' (defined near the top of the program). Don't get too excited about the syntax here— that's highly subject to change this early in the game.

Here's the error message my compiler produces for the source code above:

test.pi0:2:15-20: error: static binary operator '/' types mismatch... static w a := 64 / a ^^^^^^ test.pi0:11:13-16: ...evaluated here: static k := w () ^^^^

Already, this is better than most of the supposedly mature tools I'm using in my professional work today. Why don't language designers focus on getting the diagnostic messages right in the first go around? I don't understand.

Anyway, yes I know this syntax makes you want to claw your eyes out. That's your problem. It makes sense to me. In fact, the way I would characterize the nature of this project I'm playing with is that I'm trying to define the intermediate language that currently only exists in my head, from which all the code I have to write professionally these days has to be translated into C89 before it will run.

One of the amusing things about this project, of course, is that LLVM has a C-language back end. In practical terms, this means that I can write my code in my own language, have the compiler spit out LLVM bitcode, pipe that into the LLVM compiler with the -arch=c flag, and get shiny C-language source code that does what I want. Maybe not the most readable C language source code... but, then, have you seen my hand-coded C lately?

Flux, Not Voltage

May 1, 2008
Post a comment

Reading about the discovery of memristors in EE Times today brings back fuzzy memories of my undergraduate classes in electronics engineering.

[...]

"Electronic theorists have been using the wrong pair of variables all these years--voltage and charge. The missing part of electronic theory was that the fundamental pair of variables is flux and charge," said Chua. "The situation is analogous to what is called "Aristotle's Law of Motion, which was wrong, because he said that force must be proportional to velocity. That misled people for 2000 years until Newton came along and pointed out that Aristotle was using the wrong variables. Newton said that force is proportional to acceleration--the change in velocity. This is exactly the situation with electronic circuit theory today. All electronic textbooks have been teaching using the wrong variables--voltage and charge--explaining away inaccuracies as anomalies. What they should have been teaching is the relationship between changes in voltage, or flux, and charge."

This rings bells for me. I have some of those textbooks. The relationship between electric and magnet fields has always seemed elegantly symmetrical... except, I remember being highly annoyed that the universe seemed to have a missing passive circuit element. I remember asking my professors about it, and being less than satisfied with the answers I got back. I think they were something like this: "there is this thing called a memristor, but nobody thinks about them much." More than twenty years later, I'm acutely aware of what these things could be made to do, and I'm excited about the prospects of what these guys at HP Labs (and others, apparently) have discovered.

I've got a feeling that's about to change. A lot. There's another article about them in Scientific American.

Do You See What Happens, Larry?

Mar 21, 2008
Post a comment

I'm vastly amused by this.

When businesses want to communicate with their customers via e-mail, many send messages with a bogus return address, e.g. "somethinghere@donotreply.com." The practice is meant to communicate to recipients that any replies will go unread.

But when those messages are sent to an inactive e-mail address or the recipient ignores the instruction and replies anyway, the missives don't just disappear into the digital ether.

Instead, they land in Chet Faliszek's e-mail box.

There's a lesson here for protocol architects.

Some people will rely on the system your protocol enables without really understanding how it all works. Their ignorance can make it surprisingly easy for them to do things by mistake that have very serious security consequences for themselves and, potentially, for everyone.

Other people, who understand how the system works, and the protocols that enable it, will discovery these interesting vulnerabilities. They will then exploit them with varying degrees of malice aforethought.

Now, imagine for a moment that Chet Faliszek were one of these people, i.e. someone who does business with phishers and spam gangs, or who is a spammer or a phisher, instead of someone who seems to have taken an interest in trying to educate people who are otherwise dangerously ignorant. In a way, that would make it easier to rip the domain away from him by force and hand it over to some kind of regulated public entity. But, Chet Faliszek isn't doing anything wrong— yet— and, as a result, there is a continuing risk to the system posed by the dumbass convention of using donotreply.com as if it were a reserved domain name.

I don't know how to design protocols that don't have this kind of weakness in them. It seems like a real problem. Maybe, an intractable one. I wish there were a good system for minimizing the system risks inherent in a protocol architecture prior to its widespread adoption. I don't think there is one.

I think it's just a matter of making sure your architects aren't treated like dog-crap.