Tag Archives: Haskell

Dear Lazyweb: Does this software exist?

I’ve been wondering if the following kind of testing management software exists (preferably free software, of course).

It would allow one to specify a number of test cases. For each, one should be able to describe preconditions, testing instructions and expected outcome. Also, file attachments should be supported in case a test case needs a particular data set.

It would publish a web site describing each test case.

A tester (who in the free software world could be anyone) would take a test case, follow the instructions given and observe whatever outcome occurs. The tester would then file a test report with this software, either a terse success report or a more verbose failure report.

The software should maintain testing statistics so that testers could easily choose test cases that have a dearth of reports.

As a bonus, it would be nice if the software could submit a failure report as a bug report .

(Note that this would be useful for handling the sort of tests that cannot be automated. There are many good ways already to run automated test suites.)

A note on Planet Haskell policy

I quote from the Planet Haskell FAQ:

A common misunderstanding about Planet Haskell is that it republishes only Haskell content. That is not its mission. A Planet shows what is happening in the community, what people are thinking about or doing. Thus Planets tend to contain a fair bit of “off-topic” material. Think of it as a feature, not a bug.

As such, it is my policy, as a Planet Haskell editor, to encourage people to give us their general feed, unless there are specific reasons to do otherwise (see the FAQ for discussion). People who do that have no selective control over what posts are republished by Planet Haskell – what they post, we republish.

The reason behind this policy is given in the quote. To spell it out: A Planet is not a scholarly journal, nor is it a discussion forum. It is a way for people to read the blogs of like-minded people. Blogs are their authors’ podiums for pontificating on whatever they like; I as a Planet Haskell editor only care about whether they are Haskell people, not (in general) about the content of their specific posts.

If you have issues with that policy, talk to us at planet@community.haskell.org. Please do not harass individual posters with comments like “Why did you post this on Planet Haskell?”

New Netnews (Usenet) RFCs

The RFC editor has finally released

  • K. Murchison, Ed., C. Lindsey, D. Kohn: Netnews Article Format. RFC 5536, November 2009.
  • R. Allbery, Ed., C. Lindsey: Netnews Architecture and Protocols. RFC 5537, November 2009.

They obsolete the venerable RFC 1036 (Standard for Interchange of USENET Messages) from December 1987.

The new RFCs are the work of the IETF working group USEFOR, chartered November 1997 and concluded March 2009. I’ve heard it was not quite the longest lived IETF working group ever. (I personally missed the group by a couple of months, since I started following Netnews and NNTP standardization in April, due to Alue.)

Both RFCs are on the Standards Track, currenlty as Proposed Standards. In my opinion, they are a huge improvement over both RFC 1036 and son-of-1036 (which will probably be published as a Historic RFC real soon now).

Star Trek

It is curious to see that the eleventh movie in a series is the first to bear the series name with no adornment. It is apt, however: Star Trek is a clear attempt at rebooting the universe and basically forgetting most of the decades-heavy baggage. It seems to me that the reboot was fairly well done, too.

The movie opens with the birth of James Tiberius Kirk, and follows his development into the Captain of the Enterprise. Along the way, we also see the growth of Spock from adolescence into Kirk’s trusted sidekick and also into … well. Despite the fact that the action plot macguffins are time travel and planet-killer weaponry, it is mainly a story of personal vengeance, personal tragedy, and personal growth. Curiously enough, although Kirk gets a lot of screen time, it is really the personal story of Spock.

Besides Kirk and Spock, we also get to meet reimagined versions of Uhura (I like!), McCoy, Sulu, Chekov and Scott. And Christopher Pike, the first Captain of the Enterprise. The appearance of Leonard Nimoy as the pre-reboot Spock merits a special mention and a special thanks.

I overheard someone say in the theatre, after the movie ended, that the movie was a ripoff and had nothing to do with anything that had gone before. I respectfully disagree. The old Star Trek continuum had been weighed down by all the history into being a 600-pound elderly man who is unable to leave the couch on his own. This movie provided a clearn reboot, ripping out most of the baggage, retaining the essence of classic Star Trek and giving a healthy, new platform for good new stories. One just hopes Paramount is wise enough not to foul it up again.

It was worth it, I thought.

It’s time to fix the ABI

SELinux is entirely correct about disallowing dynamic code generation, as it is a major security risk.

Disregarding Just-In-Time compilation, the main legitimate need for dynamic code generation is to support (downward) closures that are ABI-compatible with normal C functions. GCC’s local functions extension of C is one example, and many non-C languages need them badly in their foreign-function interfaces (Haskell is one, Ada I’m told is another).

A closure is a function pointer that refers to a function that is local to another function. That function has access to the local variables of the parent function, and this access is provided by having the caller give the callee a static link (a pointer to the parent function’s stack frame) as a hidden parameter. If the call is direct (that is, not through a function pointer), the caller knows the appropriate static link and can just pass it. The trouble comes with function pointers, as we need some way of including the static link in the function pointer.

The simplest way is to have function pointers be two words long; one of the words contains the classical function pointer (that is, the entry point address), and the other contains the static link. Unfortunately, the prevalent C ABIs, including the SYSV ABI used by GNU/Linux, mandate that function pointers are one word long. The only way I know to work around this is to dynamically generate, when the function pointer is created, a small snippet of code that loads the correct static link to the appropriate place and jumps to the actual code of the function, and use the address of this snippet (usually called a trampoline) as the function pointer. The snippet is generated on the stack or in the heap, and thus requires an executable stack or executable dynamic memory.

It’s time to fix the ABI to allow for proper two-word function pointers.

The Dying Philosophers Problem

Reading a masters thesis draft that mentions the dining philosophers problem – a parable about the difficulties of process synchronization very well known in computer science – it occurred to me that it must not be a very good idea to eat just spaghetti (or just rice). I asked a nutritionist about it, and here is her answer. Even if they manage to avoid deadlock or livelock, dying of malnutrition is not going to be their first problem, go read the full story!

[Typos and thinkos corrected after initial publication]

Benja on denotational semantics

My friend Benja Fallenstein got carried away in the comment section of my latest post on recursion and wrote a tutorial on how it all relates to denotational semantics. It’s a shame it is buried somewhere in the comments, so I am reposting the comment here with Benja’s permission.

The tagline is, Denotational semantics tutorials. It’s the new monad tutorials!


Benja Fallenstein writes:

Having read and understood [the] entire post, I can now summarize Antti-Juhani’s complaint in a way that programmers with no theoretical background will understand:

“The definition is an infinite recursion. Sure, it’s self-referential, but since it recurses forever, it doesn’t actually define what ‘recursion’ is!”

:-)

That said, I find it kind of a pity to introduce all this theory without talking about why it nicely models the real world. Antti-Juhani argues that this pretty much the definition of “popularized science,” but I have to admit that, as definitions go, I like “recursion: see recursion” better. :)

So let me have a quick go. [UPDATE: Didn’t turn out to be quick at all. This is, in fact, as long as Antti-Juhani’s original post. Proceed at your own peril.]

All of this comes from denotational semantics, which is concerned with what expressions in a programming language “mean” — and which ones mean the same thing. For example, “7″ ‘denotes’ the number seven, “7+2″ denotes the number nine, and “5+4″ also denotes the number nine.

Now, here’s the knotty problem. If we have

f(x) = if x = 0 then 1 else x*f(x-1)

then f(4) denotes the number twenty-four, but what does f(-2) denote?

So, denotational semantics introduces a new, special value, “recurses forever.” An expression of type ‘integer’ either denotes an integer, or, like f(-2), it denotes “recurses forever.”

Now, about these partial orders. (Reminder: A partial order says, for every pair (x,y) of elements of a certain set, that x is smaller than y, equal to y, larger than y, or “incomparable” to y.) Here is Benja’s guide to what the partial orders of denotational semantics mean:

Let’s say that you write a program where, in one place, you can plug in either x or y. If you can write such a program that prints “foo” when you plug in x and prints “bar” when plug in y, then x and y are “incomparable.” If you can’t do that, but you can write a program that prints “foo” when you plug in y, and recurses forever when you plug in x, then x is smaller than y. If every program you can write will do the same thing whether you plug in x or y, then x and y are equal.

(We ignore details like out-of-memory errors and *how long* a program takes to do something.)

Examples:

- 5 and 7 are incomparable. Proof: if ___ == 5 then print “foo” else print “bar”.

- f(-2) < f(2). Proof: if ___ == 2 then print “foo” else print “foo” — if you plug in f(-2), this will loop forever, if you plug in f(2), it’ll print “foo”.

- (5+2) = 7. Whatever program I write, it will do the same thing, no matter which of these expressions I plug in.

Now, with expressions of type ‘integer,’ the resulting partial order is: “Recurses forever” is smaller than everything else. All other values are incomparable.

Recall from Antti-Juhani’s post that the bottom element (⊥) is defined to be the smallest element of a mathematical universe (if such a beast exists). Since “recurses forever” is smaller than everything else, it’s the bottom element of this universe. That’s what denotational semantics calls it. (Haskell, too.)

Of course, this partial order is kind of boring (the technical term is ‘flat’). It gets more interesting when we consider functions.

In general, we can talk about functions from values of type S to values of type T, where we already know the partial orders of S and T. In particular, we can talk about functions from integers to integers.

Now, if you can find an x and a program that prints “foo” when you plug in f(x) and “bar” if you plug in g(x), then you can write a program that prints “foo” when you plug in f, and “bar” when you plug in g. (Exercise! ;-) ) Further, denotational semantics wants applying a function to a parameter and then doing something with the result to be the *only* way you can get information about a function. No f.get_function_name, please. (If your programming language has that, you can’t map the functions of your programming language 1:1 to the functions of denotational semantics.)

By my rule above, this implies that f <= g if and only if f(x) <= g(x) for all x. Since formal theories can’t have fuzzy stuff like my rule, denotational semantics takes this as the *definition* of the partial order on functions.

The bottom element of this mathematical universe, then, is the function that always returns bottom, no matter what it is given — or in other words, a function that recurses forever, no matter what parameter you pass to it.

(Side note. Denotational semantics allows only “monotone” functions — that is, if x <= y, then f(x) <= f(y) for all f, x, and y. That’s an example of how all these definitions allow us to make formal statements about the real world. In the real world, if you can find a function f and a program that prints “foo” when given f(x) and “bar” when given f(y), then you have a program that prints “foo” when given x and “bar” when given y — so if f(x) and f(y) are incomparable, then x and y must be incomparable, and the other way around, if x and y are comparable, then f(x) and f(y) must be comparable, too. (This reasoning doesn’t exclude the case that x <= y and f(x) >= f(y). If you really care, prove it yourself. :) ) This ends the side note.)

Recall, now, Antti-Juhani’s definition of recursion: An equation of the form x = some expression (which may contain x), interpreted as a recursive definition, defines x to be the smallest value satisfying this equation. The models constructed in denotational semantics have the property that for any equation of this form, the set of values satisfying it does have a smallest element, so ‘x’ is well-defined no matter what the equation is.

It’s important to note that this does not mean that x has to be “bottom,” because there are equations to which “bottom” is not a solution. Let’s look at a slightly simpler example than the one Antti-Juhani gave.

f(x) = if x = 0 then 0 else f(x-1)

We have f(0) = 1, but bottom(0) = bottom, so f can’t be bottom.

The equation has more than one solution, though. It is satisfied by a function that returns 0 for x >= 0 and “returns bottom” (recurses forever) for x < 0; but it is also satisfied by a function that returns 0 for every input. And by an infinite number of functions that return 0 for some negative inputs and bottom for others.

We “want” the first of these solutions, of course, because that’s what we get if we interpret the equation as a computer program, and computer programs are what we’re trying to model. But we’re in luck: The first solution is smaller than all the other ones, because for all inputs, they either return the same value, or the solution we want returns ‘bottom’ and the solution we don’t want returns 0 (and bottom < 0).

The point of it all is, of course, that when we interpret an equation as a computer program, we always get the least value satisfying the equation (if we use a partial order that follows my rule, above). And that, my friend, is denotational semantics.