Barbara Liskov Wins Turing Award

jonniee writes "MIT Professor Barbara Liskov has been granted the ACM's Turing Award. Liskov, the first US woman to earn a PhD in computer science, was recognized for helping make software more reliable, consistent and resistant to errors and hacking. She is only the second woman to receive the honor, which carries a $250,000 purse and is often described as the 'Nobel Prize in computing.'"

Comments

Relations all the way down

[Baldrson]

Liskov says: "Today the field is on a very sound foundation."

If only it were true.

I recall, in fact, the point in time when I first ran across Liskov's CLU in the context of working one of the first commercial distributed computing environments for the mass market, VIEWTRON, and determining the real problem with distributed programming was finding an appropriate relational formalism.

We're still struggling with the object-relational impedance mismatch today. The closest we are to finding a "solid basis" for computer science is a general field of philosophy called "structural realism" which attempts to find the proper roles of relations vs relata in creating our models of the world.

If anything, our descriptions should be "relations all the way down" unless we can find a good way, as some are attempting, to finally unify the two concepts as conjugates of one another.

Coincidentally

[counterplex]

I happen to have a printout of an article on "The Liskov Substitution Principle" and was wondering just yesterday how it is that as programmers we use these principles in everyday life yet don't know their names or the stories of how they came about. As the first US woman to earn a PhD in CS, I'm sure there are some interesting stories to tell about it.

For those who might not have her original text handy, the Liskov Substitution Principle states (rather obviously):

If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2 then S is a subtype of T

which, when stated in the words of Robert "Uncle Bob" Martin as something we probably all intuitively understand from our daily work, is:

Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it

Re:Coincidentally

[shutdown -p now]

Yes, of course... I hate this thing. It should have been List<Derived> to List<Base>, of course.

The even sadder part of the story is that Java 5 allows the cast because of type erasure (with a warning, but still...).

Re:Coincidentally

[Estanislao Mart�nez]

Casting from a container of Derived to a container of Base should be safe.

Not if your container supports an operation to add elements to the collection. If you could do that cast, you could cast the Container of Derived to Container of Base and add an arbitrary element of type Base, but not of type Derived.

More generally, if X(Y) is a type parametrized over Y, and Z is a subtype of Y, then asserting that X(Z) is a subtype of X(Y) fails, because X might have an operation that takes an argument of the parameter type.

Re:Coincidentally

[shutdown -p now]

class Base { }
class Derived1 : Base { }
class Derived2 : Base { }
 
List<Derived1> derived1List = new List<Derived1>();
List<Base> baseList = derived1List; // you may think that it is okay ...
baseList.Add(new Derived2());
Derived1 derived1 = derivedList[0]; // ... up until this moment

The correct way to handle this sort of thing is covariance (and contravariance) at point of use, not at point of type declaration. So you declare a method as taking "a List where T is derived from Base" - and now you can pass List to it, and within the body of the method, you can call operator[] (since it's covariant), but you cannot call Add(Base), since it's not. Java 5 wildcards "? extends T" and "? super T" cover this ground, for covariance and contravariance, respectively

Eiffel falls into this trap, by the way - it makes all generic types covariant with respect to type parameters without any restrictions. The above code (or rather its Eiffel analog) will compile, but at run-time, the behavior is essentially undefined - it will usually raise an exception for non-primitive types at element insertion, but for primitive types it doesn't even bother to check, so you can insert a REAL into an ARRAYED_LIST{INTEGER} (since both types derive from NUMERIC), and will silently get garbage. Ouch!

1968

[MoellerPlesset2]

Since it's not in the article, I looked it up. She got her PhD in 1968.

I initially thought that kind of sucked (Cambridge's 'Diploma in Computer Science' has been awarded since 1954), but apparently the first US PhD in CS named as such was in 1965 (University of Pennsylvania).

The field could still use more women though.

Yes

[Baldrson]

Aside from academic pissing contests you have a much more immediate worry: The lack of bankruptcy protection afforded student loans coupled with the trend in life-time income prospects for CS graduates.

She was not the first woman to get the turring awd

[addininja]

Frances E. Allen got the turing award in 2006 http://en.wikipedia.org/wiki/Frances_E._Allen http://en.wikipedia.org/wiki/Turing_Award

Re:Translation for Americans

[Chris Burke]

We don't call it that. We call it toilet paper like normal people. Makers of toilet paper call it bathroom tissue, I guess because they want a name that's a little more distant from "ass wipe" or less evocative of a porcelain bowl filled with crap or something, though they'll talk about their "bathroom tissue" in advertisements while showing cartoon bears (chosen because as everyone knows, bears shit in the woods) with little scraps of toilet paper all over their fat bear asses, which I can't help but wonder who the fuck has this problem and why, but I'm afraid of the answer, and apparently the right brand of ass wipe will solve it so lets just try to forget about that okay?

What were we talking about? Oh right. It's called "pop". "Soda" is okay too I guess.

Re:making software more reliable?

[jc42]

Even a simple ADD instruction will give the wrong result when the hardware fails.

True, but the reality is much worse than that. A simple ADD instruction will also give a wrong result, on all current "popular" CPUs, when the hardware is working exactly as designed.

To the people who design CPUs, adding two positive integers and getting a negative result is exactly what the hardware should do in some cases, depending on the values of the integers. This wreaks havoc with software designs that assume the mathematical definition of integer addition.

Yes, I know that the hardware also sets an overflow flag bit somewhere to indicate that the result isn't (mathematically) correct. But the implementations of most programming languages, including all the common ones, knowingly and intentionally hides the overflow flag from the software. If you pick up a few of the top-selling programming-language texts, and look through the index for information on how the language handles things like integer overflows, you typically won't find any mention of it. The people working at "higher" levels can't be bothered with such mundane details.

They get away with all this because the people paying money for the computer systems and the software aren't generally willing to pay for hardware or software that always produces correct results. Programmers who insist on such correctness tend to find themselves shuffled off to the side or laid off, in favor of programmers who can write software to management's release schedules.

This is all hardly a secret. People have learned that you don't have to be secretive about how crappy most software (or hardware) is, because the people in positions to control purchasing don't read the technical literature and don't particularly care about such geeky stuff as overflow bits. So we can talk about it all we like amongst ourselves; it makes no difference to the people signing the purchase orders and paying our salaries.

Re:LSP it's not a guideline, it's a rule.

[Estanislao Mart�nez]

My understanding is that OP's formulation of the LSP just won't work, because the term "behavior" is too broad. (For reference, here's the formulation I'm referring to: "If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2 then S is a subtype of T.")

The Wikipedia article has a better formulation, in terms of properties proveable of objects of the types in question (which I suspect is still not quite right, but that's another topic). Basically, for your supertype Publisher, there is some set of properties that should be proveable of every object of that type; for example, the type signature of the methods in question, and invariants that the operations on the type respect. Those properties should be respected by the subtypes for them to be correctly called subtypes at all.

In your example, given the premise that an object is of type Publisher, then it can be proven that the object has the operation publish(). Given that premise, however, it cannot be proven that the publish() operation sends either email or SMS.

A violation of the principle would be to implement SMSPublisher as a subclass of EmailPublisher. In that case, given the premise that an object is of type EmailPublisher, then it can be proven that its publish() method sends email. However, given the premise that an object is of type SMSPublisher, it cannot be proven that its publish() method sends email; therefore, SMSPublisher is not semantically a subtype of EmailPublisher.*

* I don't think this argument is quite right, actually, because we haven't defined very clearly what we mean by "object" and "type" very well. A better, but less precise formulation is that if your code relies on the invariant (i.e., proveable property) that objects of type EmailPublisher send email, then making SMSPublisher a subclass of EmailPublisher will break your code.