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

Turing test

[ignishin]

Does this mean she passed the turing test?

Re:Turing test

[MrEricSir]

I hope not. MIT professors are not human.

Re:Turing test

[dedazo]

At MIT, they give the test to the professors the award to the machines. Yeeeaaahhh

Re:Turing test

[rockNme2349]

Oblig XKCD

http://xkcd.com/329/

Re:Turing test

[Stormwatch]

No, it means she is turing-complete.

Re:Turing test

[Bozdune]

While there's no doubting her accomplishments, I will say that my enjoyment of 6.170 was in spite of her.

Not surprised.

I had no use for her in 1978. She actively assisted in flunking a good friend of mine out of the PhD program. She turned down a thesis idea I had, called it "totally the wrong direction" -- and three years later a guy got a PhD and an award with the same idea at Waterloo.

Maybe she mellowed with age, but given your comment, I guess not.

Good for her...

[Em Emalb]

I bet she has some stories from "the old days" of being about the only female geek around.

Good for her.

Re:Good for her...

[saiha]

Yeah, there are like twice as many now.

Purses and wallets?

[interkin3tic]

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

Did they give $250,000 wallets to the men who won previously?

Re:Purses and wallets?

[CaptainPatent]

No, they're just bragging about the luxurious accessories the award lugs around all day.

So does that mean...

[Chris Mattern]

...we can't tell her apart from a computer over a teletype link?

No, wait...

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]

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.

To be honest, I would consider anyone who does not know what LSP is, to be OO-ignorant, even if (s)he does code in an OO language. It is a very fundamental rule, much more important that all the fancy design patterns. I guess it's possible to "invent" it on your own, just as it's possible to normalize databases without remembering, or even knowing about the strict NF definitions, but in either case, chances are high you'll get it wrong eventually.

Re:Coincidentally

[shutdown -p now]

On a side note... I remember a lot of people complaining about how Java 5 generics were oh-so-unobvious and hard when it came to lower and upper bounds etc. Meanwhile, the topic "why can't I cast List to List - this must be broken!" is recurring on microsoft.public.dotnet.languages.csharp probably about every two weeks. Both cases are absolutely trivial when one understands and carefully applies LSP to the problem.

Which, I guess, just shows that many Java and .NET programmers don't really understand the theory behind their tools, even when it's directly applicable to the code they write every day. Sad...

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!

Re:Coincidentally

[ChunderDownunder]

I survived 8 years as a OO programmer without hearing this term. Even then, only as a question on a recruitment agency test.

So either I went to the wrong university, and consistently the wrong employers, or it's one of those self-evident principles that just didn't have a name before Barbara turned up.

Re:Coincidentally

[shutdown -p now]

So either I went to the wrong university, and consistently the wrong employers

Employers aren't there to teach you these things, and a lot don't care so long as you crank out code that mostly works (and, let's face it, it's not always easy to tell for them, and the concepts of "formal correctness" and "readability" and "maintainability" are often not even on their radar, unless a developer brings that up). And as for university - it may well be. If they had an OOD design course and never mentioned it, or at least described it in a formal way, then they wasted your time.

Of course, it had somehow become an established norm that "object-oriented design" course in the uni is basically just applied Java programming; from what I've seen, the best you can expect from a typical graduate when it comes to OOD theory is to be able to recite "encapsulation, inheritance, polymorphism" when asked what OO even is. It's especially ironic as only one of those three is actually a required ingredient, and even that is wrongly named. The very notion of MI gets people educated that way thoroughly confused when they first meet it, and you can forget about multimethods...

or it's one of those self-evident principles that just didn't have a name before Barbara turned up.

It was formulated by her in 1987. Unless your 8 years were mostly in Simula or Smalltalk, it did have a name by the time you've started working with OO. Definitely so if you've been doing Java or .NET.

As for self-evidence... I sort of wish it was, and it really is very simple conceptually, but the fact that so many people still get it wrong over and over again shows that, apparently, it's not all that self-evident for your typical coder.

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.

Re:1968

[UnknownSoldier]

> The field could still use more women though.

Why?

Do you complain that we need more pregnant men also?

Re:1968

[MoellerPlesset2]

Why? Do you complain that we need more pregnant men also?

Men aren't capable of becoming pregnant. I however, happen to believe women are just as capable of being good computer scientists as men are.
The fact that only a small minority of computer scientists are women, means that upwards of half our best CS talent is going to waste.

I think that's a pity.

Re:1968

[geekoid]

"The field could still use more women though."

Why?
Not that there shouldn't, but you are blindly stating something without any argument.
WHat does a women bring that a man doesn? or vise versa?

When we can determine that, then maybe we can find out why the field continues to attracts so few women. Even in the presence of programs that push very hard to get door open and to give women priority in the education there just aren't a lot of women.

I am genuinely interested in why?
Yhe more I think about it, the more I wonder if it is the type of work.

Hey mods:
There is a difference between genuinely wondering why a disparity exists(as I am) then sexism or bigotry.

Re:1968

[Kerrigann]

I don't know why in recent times there is such a disparity of men and women in C.S., but I imagine your attitude might have something to do with it...

I really don't know how to respond to this... you're either trying to be funny (but got modded +3 insightful), or are seriously trying to imply that a woman who's good at C.S. is as much of a freak as a pregnant man.

All of a sudden I feel very alone in this field.

Re:1968

[turing_m]

Why?

Just a guess, but maybe his tastes don't lean towards guys with beards and questionable personal hygiene.

Re:1968

[UnknownSoldier]

> you're either trying to be funny (but got modded +3 insightful), or are seriously trying to imply that a woman who's good at C.S. is as much of a freak as a pregnant man.

Try neither. I had no emoticon, and I had no implications -- I just asked a simple question, in order to why find out where this assumption is coming from.

I have seen this slippery-slope type of Political Censorship before and all it does is lead to reverse discrimination. Replace Women with Ethnic / Religion / X of your choice.

This completely focuses on the wrong problem by making a problem where one doesn't exist. The gender of a Computer Scientist doesn't fucking matter -- the only things that do are...
  a) Are they competent? How well do they know their doman? How well can they solve problems?
  b) How professional are they when interacting with
        i) colleagues?
        ii) the layman?

A better question to ask is "How effective are we teaching computer scientists?"

I still have never seen a good answer to this question.

Re:1968

[Charan]

WHat does a women bring that a man doesn? or vise versa?

A different perspective. And maybe a less-confrontational attitude.

Re:1968

[Lunzo]

The field could still use more women though.

Better rhetorical questions:
* Do you complain we need more male nurses?
* Do you complain we need more male teachers?
* Do you complain we need more female garbage collectors?

Gender equality is not the same as having a 50/50 male/female split in every field.

making software more reliable?

[erroneus]

Software is ALWAYS reliable. It is the code that people write that sucks.

I don't know how many people come from the "old school" of programming, but when I started, we didn't have all these libraries to link to. When we wanted a function to happen, we wrote it. And when we wrote it, we checked for overflows, underflows, error status and illegal input. We didn't rely on what few functions that already existed.

Most fatal program flaws are ridiculously easy to prevent, but bad programming habits prevail and short of creating some human language interpreter that writes code as it should be written, nothing will replace lazy programmers who trust library functions too much. And yes, I know about deadlines and not having time to waste and all that stuff. But there is something most people are also missing -- pride! I know that when I do something, I am putting my name on it whether it is directly or otherwise. And if my name gets associated with something, I make damned sure that it works and is of good quality. With the stuff that goes out these days (especially SQL injection?! PLEASE! What could be more fundamental than screening out acquired text data for illegal characters and lengths?!) it is clear that pride in one's own work is not something that commonly exists.

For those of you out there who agree with me, it probably doesn't apply to you. For those that disagree, tell me why? Why is a programming error FIXABLE but not PREVENTABLE?

Re:making software more reliable?

[Anonymous Coward]

Software is ALWAYS reliable. It is the code that people write that sucks.

No, computers are reliable. They'll do exactly what you tell them to do. Software, however, sucks, since it is simply a representation of the code that people write, which also sucks.

Re:making software more reliable?

[ChienAndalu]

No, electrons are reliable. They'll do what you tell them to do. Hardware engineers however design crappy hardware.

Re:making software more reliable?

[morgan_greywolf]

but when I started, we didn't have all these libraries to link to. When we wanted a function to happen, we wrote it.

Functions? Back when I started, we didn't have functions. We had jump instructions.

You kids and your newfangled 'functions' and 'libraries'. Now get off my lawn!

Re:making software more reliable?

[Colonel Korn]

No, quantum mechanics is reliable. It defines physical uncertainties in a robust way. Electrons suffer from crappy positional and momentum certainty.

Re:making software more reliable?

[Ardeaem]

No, electrons are reliable. They'll do what you tell them to do.

I, for one, am never sure quite what my electrons are doing. After that Heisenberg guy, they've been a bit flaky...

Re:making software more reliable?

[Ardeaem]

Functions? Back when I started, we didn't have functions. We had jump instructions.

When I first learned to program as a kid, I taught myself how to write pseudo-functions using goto. I looked back at those programs a few years later, and they were completely unreadable. Now, my wife does a little programming on the side (we're both researchers) and she loves goto. I keep trying to tell her NOT TO USE GOTO, but she never listens. It's painful to read her code. I think we might need counseling for this...

Re:making software more reliable?

[Chibi Merrow]

I don't know how many people come from the "old school" of programming, but when I started, we didn't have all these libraries to link to. When we wanted a function to happen, we wrote it. And when we wrote it, we checked for overflows, underflows, error status and illegal input. We didn't rely on what few functions that already existed.

That's great. Now that you guys built up the roads, bridges, and traffic lights... The rest of us are interested in actually using them to GET SOMEWHERE.

Rewriting OpenGL, a scene graph, network interface code, XML Readers, etc, etc, etc. for each project would only lead to increasing the amount of buggy code in existence and no actual work getting done. We really should be past reinventing the square wheel...

Seriously, you've gone beyond the stereotypical "In my day..." old coot bullshit and straight into loony "uphill both ways in a snowstorm" territory. Using library functions instead of writing your own isn't any different than using power tools over hand tools, the quality of the result has to do with the person using them, not how easy the tools are to use. And while something built by hand may *seem* nicer, the difference in the end doesn't really matter--and you're able to get a hell of a lot more done with modern tools.

Re:making software more reliable?

[iminplaya]

No, quantum mechanics is reliable. It defines physical uncertainties in a robust way.

Only when you're watching. Behind your back it's complete chaos.

Re:making software more reliable?

[spacefiddle]

Now get off my lawn!

10 PRINT LAWN
20 GOTO CURB

Re:making software more reliable?

[Workaphobia]

http://xkcd.com/485/

No, Brian Greene is reliable. He's been knitting furiously since the beginning of the universe, and isn't likely to quit anytime soon.

Quantum mechanics suffers from being far more difficult to understand than a tiny man controlling reality.

Re:making software more reliable?

[Workaphobia]

Now some bugs are inexcusable. Divide by 0 crashes spring to mind as the most glaringly obvious inexcusable bug.

Why is everyone talking about all these obvious elementary bugs? Division by zero, integer overflow, illegal input... I haven't even heard anyone mention anything as sophisticated as a NULL pointer dereference, much less a memory deallocation problem or God forbid a race condition.

It's just that everyone around this thread is trying to have this profound discussion of fundamental software errors, yet talks like they're in a high school programming class.

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

[refactored]

Sadly, too many people still think it's a guideline, not a rule. Sorry, if your code violates the LSP, you've got a bug, it just hasn't bitten you yet.

She deserves recognition for the vast number of latent defects she has effectively removed from the worlds software with the LSP alone, I'm glad she got the award.

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

[Catiline]

"if your code violates the LSP, you've got a bug, it just hasn't bitten you yet. ..."

False.

Proof, please; you are contesting an award-winning theory, and I for one side with prevailing theory until further evidence is provided.

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

[Workaphobia]

What are you talking about? It's not a theory, it's a definition. One specific definition out of several, I would imagine. Moreover, nothing in it says "OBEY ME OR YOU'RE BUGGED"; it's a very good guideline for sensible program design, but it has nothing to do with the completely independent definition of a bug in the general sense. Of course, you can always *make* the LSP part of your design criteria so that violations of it do in fact constitute bugs for your project, but that's a different matter.

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

If you write code to work with a Polygon reference but it fails to work with a Triangle reference, and Triangle is a subclass of Polygon, that does not indicate that you have a bug in your code. It merely indicates that Triangle, despite being a subclass, does not constitute a subtype under this definition.

If that's not good enough for you, notice that the statement is an if, not an iff (if and only if). Therefore, that sentence alone does nothing to rule out what can be a subtype of T.

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.

Re:seriously?

[Kozar_The_Malignant]

tangents that were largely unrelated to software development.

Tangents are related to geometry, not software development. Besides, professors write textbooks so they can make their students buy them, and the professors get some of the students' money; not because they're any good at it. I thought everyone knew that.

More women in the old days

[Simian Road]

Apparently there were far more women in computing in "the old days". The dominance of the male geeks is a relatively recent phenomenon.

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.

Re:Don't let the award fool you.

[geekoid]

HAHAHahahhaha...
Someone with your sig has the gall to write that about a book?

Irony is rich today.

Oh, and how about an example of where she is wrong? I don't think I ahve ever read her stuff but I would like to see an example of what you are talking about.

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:Purses and wallets? Nahh... she got a $250k

[vishbar]

Fashion jokes aren't gonna go to far on Slashdot, buddy. Just a word of advice.

Proof, hmm, would you like a price tag on that?

[refactored]

How about a billion dollars for violating LSP. http://developers.slashdot.org/article.pl?sid=09/03/03/1459209 If you think about it, That's exactly what Tony Hoares mistake was. A violation of LSP. Sometimes the thing pointed to by "T *" does not behave as an instance of T. When it doesn't, as all too often it doesn't. Bad Shit happens. Sorry, type checking compiler can't help you thanks to Hoare's mistake.

In context of history of languages

[dpigott]

CLU drew on the lessons learned with both Alphard and Vers. Alphard was from CMU and written by Wulf and Shaw, Wulf also writing the famous BLISS. Vers was made by Jay Early, whose parser was hugely important in all the compilers of the time. THe language itself (and its V-graphs) was heavily influenced by the Mem-theory of Anatol Holt (who was on the Alogl Committee and was a principle in designing the astonishing GP and GPX systems for the UNIVAC - first languages to explicitly feature ADTs per se. That became ACT, the adaptable programming system for the Army's Fieldata portable computers (portable in a completely different sense to the modern usage. He also hated Unicode, but that was a rival programming system back then. So reading the reports at the time can be misleading - "don't use Unicode on Portable Computers!"). Holt's ideas permeate computing, the notion of making any system of data representation as abstract as possible goes back to him.

CLU was written using MDL (pronounced muddle) which was a protoreplacement for LISP which featured ADTs. MDL was cowritten by Sussmann of LISP fame as a basis for PLANNER which became Scheme, and perhaps more geekly interesting is that is was also used for writing ZIL (and if you don't know about ZIL, you shouldn't be reading Slashdot)

CLU evolved into Argus, but the ideas were also used in the Theta programming system for the Thor OO database, and was also in PolyJ which was (as it suggests) a Polymorphic Java

Another fascinating development of the CLU ideas the SPIL system that Liskov co-wrote at the USAF-sponsored MITRE corp, which was in turn used for writing the VENUS operating system

Liskov has pioneered the notion of abstraction per se in language design for 40 years, and this generics-based approached is now taken for granted. She fully deserved the award for her insights as well as for her determination in fighting the reductionism represented by previous recipients (eg Dijkstra) although opposed by others (eg Iverson)

I have extracts for reports for all language of these on the HOPL website HOPL.murdoch.edu.au (too many URLs to paste in individually). Find CLU http://hopl.murdoch.edu.au/showlanguage.prx?exp=637&name=CLU and follow the genealogy links. And if you haven't yet seen my 4000-strong programming-language family tree it is worth printing out for wallpaper if you have an A1 plotter.