[Music] [Music] as a computer science major we all know the object oriented programming is now the dominant programming paradigm and has significantly changed the field of software engineering and today we are honored to have a speaker barabara lisco who has won twoing award for her contributions uh to the development of object oriented programming Professor uh Lisov now uh is a Institute professor at the MIT ECS Department he has developed two language a clue and Argus that later led to the development of object oriented um program programming languages and Professor Lov is also the first um
women that was awarded PhD in the in computer science so today she's here to talk about the power of abstraction yeah thank you [Music] okay so um it's a great honor to win something like the touring award and one of the things that it did to me was caus me to go back and reflect on what had happened and how I managed to uh develop the ideas that led to the award and so that's what I'm going to talk about today um I'm going to first of all talk about uh the work that went on
that led to this idea of abstract data types which was the main reason that I got the Touring award uh then I'm going to talk about clue which was the language I developed to explore that idea I'll make a few remarks about some work I did on type hierarchy and then I'll conclude so I'm going to start with some prehistory um so I got my PhD from Stanford and what you may not know is that I did my work in AI uh my PhD thesis was on a program to play chess end games and I
knew uh sort of halfway through my time at Stamford that I Actually wanted to move out of AI into systems I decided to stick with AI to get my PhD because after all that's the main point of getting a PhD is to finish and go on and do something else uh but when I uh left um I went to work at the miter Corporation and I switched from AI into systems and the first project I worked on there was to design something called the Venus machine and this was was a machine architecture uh what was
going on at That time was that um people were using something called microprogramming so this is the inner data 3 this is the machine on which I developed the Venus machine and this microprogramming was really basically uh something that was a lot like a risk machine so as I recall the inata 3 had an instruction set consisting of 16 instructions and very much like what you would have on a risk processor it came equipped with readon memory I believe There were 16k uh words of readon memory but I can't remember for sure uh it had
a u a teletype a tape reader and a console so it was a pretty primitive machine and the idea was that uh you would take a machine like this and you would use those low-level instructions to develop a more usable instruction set that the pro people would really write programs in now later on it turned out that we were actually fairly happy using risk Machine so one of the interesting questions is you know why did people think that that low-level instruction set wasn't sufficient in itself and I think the answer was uh actually some of
the machines were pretty Baro at that time so there was a sort of an idea that machines ought to have complicated instruction sets but another point is that people wrote a lot of uh programs in machine language in those days and I think one of the reasons that we can Live with a risk architecture is that it's actually the compiler generating the code rather than people writing that code it would be very tedious to have to write many quences of instructions in order to do simple things okay so I developed the uh Venus machine on
the in dat 3 and the most interesting thing about that instruction set which I've mostly entirely forgotten about was that I took semaphor this idea of dyst that he talked about in his Famous paper on the th operating system and put them into the hardware um so other than that that was a pretty vanilla system and then of course uh what happens when you de velop something like the Venus machine is the next question that arises is well what's it good for is it good for anything and so uh to answer that question I developed
the Venus operating system and uh this is a you know pretty early days this is Around 1960 68 or 69 and uh the Venus operating system was a small time sharing system it supported 16 uh concurrent users and it was a good Target uh test case for this machine because um I could take advantage of the fores for all the process scheduling and so forth that needs to happen in an operating system so I finished working on the Venus system sometime around uh early 19 sometime in 1970 probably and at that Point um I started
to work on programming methodology so what happened was there was a software crisis now that probably doesn't seem too astounding to you because there's always been a software crisis there's still a soft Ware crisis uh but maybe the software crisis was a little new at that point people were coming to realize that what we wanted to produ in software was beyond our abilities we really didn't understand How to produce software very well we had we were very ambitious about what we wanted to do in software another thing that happened at that time was that the
machines tended to be under bought you know machines were a real cost you had to go out and spend money and they were pretty expensive in those days and so it wasn't unusual for project to decide to try and save on the hardware by taking it out of the software the software costs were not real you know you just Couldn't figure out how much it was going to cost to to to build the software so not only were we Building Systems that were sort of more than we could manage but we were doing them on
machines that weren't powerful enough and so that added a whole other dimension to the problem so the government was very worried about this and mider is a corporation that does a lot of work for government research and uh they asked miter to look into this Question of how can we uh get control of this software crisis and so I started to work on this project and uh program methodology is actually about two related but different topics first of all there's the question of how should programs be designed you know what's a good design methodology for
coming up with a uh an implementation structure that's going to actually solve the problem that you're interested in solving and the second Problem is how should those end products be structured what kind of organization makes sense for them so what I'm going to do now is I'm going to talk about some of the literature that existed at that time so I read a whole bunch of papers so I went out what I came in with was i' done all this work on Venus and all the stuff I'd done before and I went out and I
read the literature and I'm going to talk about a few of the papers that I read um I'm sure that some of you In the audience have already read these papers but I suspect that many of you have not and and U I recommend them I'm not trying to say these are the only good papers but uh this is a set of good papers and I do think as a field in computer science we don't pay enough attention to the past and we have a tendency not to know what went before and it's a good
idea to know what went before okay so here's the landscap as that existed at that time the first Paper I want to talk about is this paper of dyr called goto statement considered harmful okay now this was a very controversial paper um and this may seem surprising to you because today the battle in some sense is over the go-to statement is gone you know it doesn't arise in the programming languages that we're familiar with but at the time it was an important part of programming languages like Fortran for example and there was a lot of
resistance to this Particular paper what dyster said in his paper was that when we reason about a program we are looking at the program text which is a static description of what's going to happen but we're actually reasoning about the program when it runs and so therefore in order to make the reasoning process work better it would be good if the static structure was very closely related to the dynamic structure and when you have a go-to Statement you're sort of jumping around and there isn't that very close correlation and then he talked about debugging as
an example of how you can get into trouble with the go-to statement if you think about debugging you're at a particular point in your program and you're trying to figure out what went wrong and in order to answer that question question you need to know how you got there and if you're using a program with well structured control Structures that answer the answer to that question is pretty easy to get at but if there are go-to statement you could have come from anywhere and I should say as an aside that prior to my work prior
to getting my PhD I maintained a huge program written in machine language that had non- reentrant code where the program actually modified itself in order to take you know save one instruction it would stick a little break Branch statement over on top of Something else because it knew that it was going to take that Branch later on so I had a lot of sympathy with getting rid of Goos go-to are minor compared to what I just described okay why was there so much controversy well I think that partly it was just that people uh were
used to doing things in a particular way and of course you can write good programs that have go-to in them but dyra admitted that um I think also though that the Programming language that existed at that time uh didn't have adequate control structures in them so if you think about the use of go-to in some of these old programming languages you can see that they were used for very good reasons for example if you don't have an exception mechanism in your program your programming language then passing a label as an argument to a procedure gives
you a way of jumping to the Handler and getting it out of the normal Flow of control or if you don't have a case statement in your programming language then using a table of labels is a very good way to simulate a case statement which is a valuable programming construct so I think that the arguments against were some to some extent you know Justified based on the weakness of the control structures in the programming languages okay the next paper is this excellent paper by Nicholas ver on Program development by stepwise refinement this is a program
this is a paper that's about the design process and it's specifically it's about top down design so ver says you start with your program statement and you think about you make one design decision and this gives you a certain structure to your program and after you've made that one design decision you take some of those things that are left these are like statements in an abstract language Where the uh language doesn't really exist and so you couldn't run it and you sort of pick up one or more of those statements and then you figure out
what to do with them and you proceed in this very orderly way one decision at a time um the the uh program that he used here was the eight Queens program problem and his first design decision was that we'll get a solution that has one column in it and when we're happy with that we'll go to the second column And if we have to backtrack we'll backtrack so that's a sort of an example um I would say that ver uh was not particularly interested in the program structure he was interested more in the design process
and of course we all know today that you can't entirely do top- down design you have to also be informed by sort of bottomup considerations where you take into account what's doable but there's no doubt that a design process to a very large extent has to be topped Down because if we don't focus on what it is we're trying to provide how can we possibly end up with a program that actually does what we want um here's a very famous paper by Dave parnis uh this is one of two actually uh Dave was actually more
interested in program structure than he was in program design and so what he says in this paper is that your in product has to have these things called modules he says I don't know what these Modules are exactly but they interact with one another and it's very important to understand these interactions and so there's this famous quote here the connections between modules are the assumptions which the modules make about one another and what he's pointing out there is that the connections had better be small because if you're going to understand things you know the simpler
the better and there can be lots of connections you know they may not be Direct this one branches to there there could be a lot of connections in data as well okay now as a result of these papers and a whole bunch of others I haven't talked about and also my work on the Venus system what happened was I realized as I was doing all this reading that I'd actually been using a methodology in the design of Venus and the methodology was based on something called partitions and I wrote this up in this paper that
was published in 1972 and here's what a partition is it's a module it has a whole bunch of stuff hidden inside it and it provides an interface consisting of a bunch of operations and the idea is that you can only communicate or only get access to the stuff that's hidden inside by making calls on these operations and Venus was uh the design of Venus was unusual maybe in that the whole system was organized this way it was very common at that time instead for for programs to all Communicate through some global storage and so what's
happening here is rather than having global storage and everybody uses it instead I divided that storage up I stuck each bit of it into some different partition and had this very orderly way of the partitions interacting with one another so that was what was described in this paper okay now um so I had produced this paper on partition I and at this point I moved From miter to MIT so in the fall of 1971 I started at MIT and um I was an assistant professor and I was learning how to teach courses that I had
no background in and stuff like that sort of common stuff for an assistant professor perhaps uh but as far as research was concerned I was really really interested in programe methodology I should say by the way that uh it's not surprising that my background was in systems at this point Because if you think about operating systems at the very least there's a very clean separation between the user code and the systems code if you didn't have a very strong boundary there of course you would have no way of guaranteeing that the system does what it's
supposed to do and so that probably did color my thinking anyway I was really interested in program methodology and the problem that I was focused on was how can these ideas be used to to build programs what I felt was you could read these papers they seem to make a lot of sense when you read them but then when you tried to apply the ideas to a program of your own it was really unclear what to do and I'm thinking particularly here about the ideas of parness and my own ideas about partition so I had
this these ideas about modularity but I just didn't know how to convey these ideas to people and so I thought and thought and thought about this and sometime during the fall Of 1972 I made this connection between partitions and Abstract data types and in ret respect it seems like it was clear that there was this connection and you know you sort of look at the work of Paris and you can say yeah he was talking about modules and there were resources inside so that was another thing that was sort of clear but of course it
wasn't clear at the time and another point but I have no idea where The idea came from so it was there waiting to be discovered okay this is very common when you make a an advance like this there's something sitting there it's waiting to be discovered it isn't uncommon if more than one person discovers it at about the same time I was thinking about it a lot you know and then one day you know there it was okay so that was in the fall of 1972 in the spring of 1972 there was a uh this
sig plan sigopt interface meeting And this this was a meeting that was ostensively about uh programming languages in which to implement systems however the program the meeting itself was actually mostly about program methodology and so that was sort of the topic that was being discussed and I gave a paper I mean I gave a talk on my ideas about abstract data types and Steve zillis who was a graduate student at MIT uh had a paper there that talked about very similar ideas so Steve was an Unusual graduate student he worked for IBM he was older
uh and IBM was allowing him to pursue his thesis sort of part-time and uh so he'd been thinking a lot about programming so Steve and I were had similar ideas and so we started to work together so now I'm going to tell you what you know what re what we did okay so here's Memorial landscape so Steve and I between us were very knowledgeable about programming languages Steve came From IBM he knew all the languages that IBM was producing there was Fortran there was pl1 he knew basic uh I had done all that work in
lisp and because because that lisp was the language you used to do the work in Ai and uh in addition we knew about the you know what was going on in programming languages in general that was the time of the alol languages and uh that was what you might call the academic stream of languages and so we were familiar with all the Work that was going on in programming languages so I'm going to check about a few papers again uh first of all you may not know that there was a time when people talked a
lot about what were called extensible languages so the idea was that um when you design a programming language this is always a problem when you design a programming language you take away expressive power because you provide this language and underneath it is say The machine language that you use to implement it and there are things that somebody could have done if they had had access to that machine language that they aren't going to be able to do using your programming language there was a lot of worry about this there was a lot of talk at
the time about Universal programming languages and whether these could ever work and so forth I mean obvious obviously we can see now they do work but there was a lot of worry that By designing a programming language and having people use it you were taking something away from them and this was bad and so extensible languages were an attempt to give it back and this first paper by Steve Schuman and Pierre Jiran um is a survey paper that talked about the state-of-the-art in extensible languages at this point in time and what they pointed out in
that paper was that there were two partic two different kinds of research that were going on First of all there was what they called syntactic extensibility and the idea here was that you know I've got a program and I'm using factorial in it why can't I have the exclamation point and use that whenever I want to call the factorial program and they actually talked about you know letting users specify syntax in BNF and then you know as a result of this the compiler would now be compiling a different language than it compiled before in general
this Is a really bad idea and the reason it's a bad idea is because we know today that program readability is much more important than program writability that was not so clear at the time at the time there was a lot of focus on let's make programs really easy to write and less of an understanding that not just reading but understanding is what really matters programs are read many more times than they're written and it's very important that you use a standard syntax So that at least the reader doesn't have to contend with uh trying
to figure out what your syntax means means I mean of course you could use these tools in a good way you could Define a sort of a special domain language that's used by a whole category of users and that's specialized for that domain but in general you would not want every programmer who came along deciding to change the syntax a little because it made it a little easier for what they Were doing the other thing that Steve Schuman and Pier Jan talked about was SE semantic extensions and what they meant by this basically was type
definitions so you could say FU equals array of int something like that that's kind of a a semantic extension except they meant a little more than that and Bob baller's thesis talks about one example of what they were talking about what he says in his thesis is I'd like to have data types and each of these data types is Going to have four operations so he's thinking about data types as always being Collections and the operations are you can add something to collection you can take something out of a collection you can access something in
the collection or mod or modify something in the collection so the four obvious things um so in a way it's kind of like a straight jacket you know every every data type has to fit into this format but the idea of having a data type with A set of operations with it you know you can see coming out of this work however there was no encapsulation in this so it was just a and and furthermore there was syntax so you could say uh you know a sign s to X and this would mean pop because
s was a stack and X was the thing that was coming out of the stack okay uh here's a paper on simulus 67 uh this is a very uh a good book to have your in your library this is what we Used to refer to as a little black book it's a book it has three important papers in it this is one of them by do and about simulus 67 there's a paper by dyra on effectively top- down design and a paper by Tony about data structures and it's a sort of a classic okay simulus
67 was a very interesting language it was definitely ahead of its time and it's a precursor of small talk and the following object-oriented programming languages it Had a mechanism a class mechanism where you could Define uh some data structures and a bunch of operations that executed on those data structures and then you could have a subass where you sort of took that code and you extended it to provide more functionality um so it's very much related to the object-oriented School of programming it didn't have any encapsulation so in that sense it didn't provide what I
thought was the most Important thing that you wanted for abstract data types uh here's a very important paper by Jim Morris this is one of two um Jim was very interested in modularity the way that Dave parnis was and what he says in this paper is that it's very important when you have your modular program structure that you be able to reason about each module in isolation I mean this is a key idea that underlines the whole reason why Modularity is a good idea if you can I you have to be able to think about
each module separately and not have to worry that something's going on somewhere else in the program that makes your reasoning invalid and then Jim went on to point out that there were two things you had to watch out for that would make modularity not work the first thing would be if there was a way for code outside the module to get inside the module and modify Stuff okay and the second thing was if there was a way for code on the outside to fake it you know to produce what appears to be an instance of
the module and somehow get the module to operate on it because then you can't expect that the module's going to behave properly and actually this paper was a very early uh sort of ahead of its time paper he talked about very important ideas in how you reason about data abstractions because he was talking about Representation and variance you know what kind of if you think about the the data structures that are inside the module what kinds of predicates are true for all instances of the module and he was also talking a bit about abstraction functions
how you relate the inside to the outside uh he then went on to talk about well how do I get protection because you know we're talking about enforcing this and his idea was to have two operators Seal and unseal so the idea is when data came from the module you'd seal it up and think about it as encryption you'd encrypt it with a key that only the module knew and then when it came back in again the module would decrypt it and only if it decrypted successfully would it be so this way encrypting protects it
and decrypting guarantees that you can't be faking it okay finally there's this paper bed Bill wolf and Mary Shaw Global variable Considered harmful and you can see that this name comes from dyra paper and it was structured sort of like Dyer's paper um so what they're talking about there is you know algo introduced this notion of block structure and block structure was a good idea and a bad idea it was a good idea because as you go into an inner block you can have definitions in there that stuff on the outside of the block can't
get at so it gives you a kind of locality and modularity it Protects that region from Stu on the outside but it was a bad idea because it also had this notion that stuff on the outside was accessible everywhere and so there was this notion of sort of global scope and what they were talking about is that Global scope is not so great because you have all these programs that communicate through those global variables and these add a whole bunch of extra connections and they make it much harder to figure out what that module's Actually
doing you have to put this in the context of the time and think about it from the point of view of the academic stream of languages which were all focused on block structure and which seem to have the idea that your entire program ought to be one big block you know with global sort of on the outside and then these inter Scopes and inner Scopes okay so Steve and I read all these papers and um we worked Intensively over that maybe six-month period And what I remember is the summer of 19 73 where as far
as I can remember it never rained because Steve and I had lunch Outdoors every day there was a lovely outdoor space in near the building where I worked with trees and benches and we used to meet for lunch every day and we'd be talking about you our ideas and how we'd Advance them in the period in between and by the end of the summer we had written this paper About abstract data types uh which was actually published in April of 1974 now what was in this paper was first of all it talked specifically about what
is an abstract data type and it made the point that an abstract data type has objects but it also has operations and the operations are the only way you can access the objects so there's complete encapsulation only the operations themselves can get inside and it also made the point that Whatever the set of operations is it's going to be specific to the type that's being defined so there's no idea that there's some predefined set of operations as there was in Bob Bowser's work instead whatever this typee is you define the operations that make sense for
it in addition the paper proposed a programming language so in a sketch so it talked about a way to implement abstract data types it said that we Ought to have polymorphism in other words it's not going to be enough to Define set of integers as a type we're going to want to Define set where there could be a set of integers a set of reals and so forth uh it also said we'd like to have static type checking but we weren't sure we could manage it and the reason we were unsure was because of the
polymorphism and it should have an exception handling mechanism so now what I'm going to do is I'm going to talk about how I went from abstract data types to clue so here we are now in the fall of 1973 and um it may seem like I was already sort of working on clue because I just talked about a paper that had stuff in it but in fact it was a decision to go forward and take this next step of turning those sketchy ideas into something real now what happened in 1973 is that three new graduate
students arrived at MIT and decided they wanted To work with me and these three graduate students Russ Atkinson Craig shappard and Alan Snider were along with me the real designers of Clue by now Steve had moved off and he was working he was coming to all our design meetings but he wasn't working on clue he was working on his PhD thesis which was about algebraic specifications of abstract data types and there was also a large group of people who came to our meetings the whole of Jack Dennis's data flow group Used to come to our
meetings but the real work was done by the four of us I would have loved to have shown you some pictures of these people but I don't have them at that time and I don't think it's too interesting to show you they look like today this is a picture me with Jack Dennis in about 1973 or 4 and Jack Dennis as I mentioned was one of the people who used to come to the group meetings okay so I had very specific reasons why I decided to design a programming language and they're uh pretty compelling when
you think about it the first one is that uh programmers think about programs by in terms of programming languages so programming languages are a very good way to convey ideas to programmers because they are the thing we work with the second point was if you put ideas into a programming language and say okay build your programs in this programming language We you'll be able to find out whether these ideas really work or not the third thing is that programming languages are mathematical objects they are precisely defined now mind you at that time they weren't all
that precisely defined because in fact the compiler was the definition and the next compiler might Define things a little bit differently these were the days uh before operational semantics came along you know so people were struggling at that Point with how would you specify a programming langu language nevertheless we tried even though we didn't have any formal tools available to come up with a very careful precise definition of the language and this was very important because a lot of the work in the literature was very mushy you know they had these ideas that kind of
waved their hands a bit and they never quite got down to exactly what the rules were and so by putting stuff into a programming Language it mean we had to make the rules precise and then the final question was performance is very important and we're going to have to implement this language and we have to think about whether the features that we're coming up with can be can be implemented in such a way that they perform well okay so we're doing language design language design is really hard and actually it's Ain to interface design so
Interface design is also not so easy and I think sometimes people don't think carefully enough about their interface design because in fact you ought to think about it as a programming language it may not have so much syntax but it does control everything that your users can do and so these principles at the top apply to interface design just as much as they apply to a programming language it has to be expressive enough they have to be able to do easily the Things that they really need to do but it better be simple and easy
to use because otherwise they'll be confused about it and they won't find it easy to nice to use and of course it has to have adequate performance it doesn't have have to have super duper performance people get very confused about that but it has to have performance that's good enough that it matches whatever it is that you're trying to Provide okay in addition to these goals which are for every programming language we had a few others we wanted minimality by which we meant we wanted to put in just the set of features we thought we
could get by with and nothing more because we were kind of looking for that minimal sort of design Point by uniformity we meant that whatever was built into the language ought to apply to the abstraction mechanisms as well and that was primarily Polymorphism and then by safety we meant we'd like the language compiler and runtime to find as many errors as possible so that to make the job of producing correct programs easier we also had some restrictions uh the first one no concurrency was not there going in I originally did think that clue would be
a language in which you could write parallel programs but I threw that out pretty early on and that was very Important decision because uh when you're designing because it allowed me to focus on the main point of the uh of the uh Project without getting distracted by concurrency which is a difficult problem in its own right it had no go-to that's coming directly from dyra um it had no inheritance because that was not the point the point was encapsulation data abstra action it was not an inheritance mechanism and in fact I was paying very little
attention to Inheritance and the work on small talk was more or less contemporaneous and I didn't even know anything about it till around 1975 there were some assumptions and decisions that got made almost without noticing and here what you mostly see is my list background so I'd written lots of code and lisp so I really was going away from the alol school here you know Alo says your program is one big block and they Were very concerned about pointers and the Heap was something considered dangerous but lisp is a heap-based language with garbage collection and
that was a decision that we made early on and it was a very important decision and the reason it's important is because if you want to do separate compilation where here I have a program that uses a data type here I have a program that implements it and if you'd like to be able to do that in a way that allows you For example to not have to recompile the using Code if I choose a different way of representing the data abstraction then if you put that stuff on the stack you're going to have trouble
because you need to know how much space to reserve on the stack but if I put it in the Heap no problem so it was really an important decision and an interesting point is that the work that bill wolf and Mary Shaw did on alard which was another data abstraction language developed at about The same time they went to the stack Direction and I think it gave them a lot of trouble and added more problems that we were able to S side step it had no block structure uh I mean it did have block structure
inside the modules but it was not you know the one big program with block structure instead it was a separate compilation uh program like the kinds of stuff you see today and that again is coming from lisp if you think about lisp You know you write this procedure you write that procedure you just keep adding to your program except this was a compiled language rather than interpreted language however where it deviated significantly from lisp is that it had static type check and this was also based on my experience in lisp because I used to get
so annoyed when I was working on my thesis at these errors in my program that a little static analysis would have gotten rid Of okay so what I'm going to do now is talk a bit about clue and I'm just going to focus on the abstraction mechanisms there was a lot of other stuff going on in clue but I'm not going to going to talk about that okay so clusters are what we had to implement abstract data types and the most interesting thing on this slide is the Top Line because there what you see is
a list of operation names so this is making that point that a data type Provides a bunch of operations and this is how you interact with their objects so the interface of a cluster listed the operation names what I've added to the slide now is a little code that uses a data type and what's really interesting on this part is that dollar sign notation it's crufty and I would not design it this way today probably but it's actually making a semantic point and that is in clue we thought of the Operations as belonging to the
data type rather than to the objects so this is very different from the object-oriented languages where you say x dot you know push or whatever it is here we would think of push as belonging to stack not to a particular stack object and that notation is expressing it very directly and the reason why we use the dollar sign notation is because of course there could be many types that have operations with the same name so you have to have Some way of disambiguating what you're doing okay here's a little bit of the implementation of a
data type and what's interesting on this slide is that rep equals line uh this is this is like what you would do in Java where you have a set of instance variables so this was how we expressed the representation of the objects most often the rep would be a record type and it would have several Fields so you know instead of having a ray EV an it might have been a record With a size field and then an elements field and then finally here's one of the operations and what's interesting here is the use of
that word CVT in the header okay and what that is is a sort of personification of Jim Morris's ideas of seal and unseal this is Seal so the idea is that inside we have a rep object an array outside we have an inset and as we push out we seal up the array and turn it into an inset and CVT could also Be used as an argument and that was the unseal okay however unlike Jim Morris's paper where he talked about uh implementing this not through encryption but through some sort of hidden key this was
all done through compile time analysis okay here's polymorphism so you can build not just an inset but you could build a set and the type would be the parameter we didn't call these polymorphic in those days we call these Type generators because we thought of this as being a piece of code which when given a parameter value would produce a type and actually you can see on the bottom of the slide when I say that set of in there I'm in some sense invoking the set cluster to produce a set of in and that's a
type okay all right now there's a problem however with polymorphic function uh sets and it took us a long time to figure out a solution to this the Problem is that not every type makes sense as an argument okay so if you think about sets in order for there to be a legitimate parameter for sets that type has to have an equality relation on it because when you stick something in a set if you stick the same thing in again twice you know if it goes in twice it's only in there once if you remove
it you know just once okay so not all types have an equality Relation um and so we just didn't know what to do with this for a long time but finally we came up with a solution and that was this wear Clause so we added to the header of a parameterized cluster a wear Clause that told you for the parameter type what operations it had to have and so here I'm saying it has to have an operation named equal which takes in two T's and returns a Boolean okay and then given this uh wear Clause
I can do compile time checking because I can check when we instantiate that the type being put in as a parameter does have such an operation and I also inside when I compile the code of set I can use that operation and here's a place where I'm using it I'm actually using it down there in that if E equals x of I uh that's a little what we called syntactic sugar so we provided a very minor way of taking a Little convenient syntax and turning it into the longer form of calling the equal operation directly
okay all right now I want to talk about exception handling and exception handling then was not like it is today there was a lot of confusion about exception handling and it was very unclear what an exception handling mechanism ought to be we did think exception handling was very important And the reason it's important it's still as important now as it ever was it's because first of all you'd like to to Define if possible total functions that work over all the elements of their domain okay and but in addition generally speaking a function is not able
to do the same thing for all elements of its domain and when it has to do something different you want a way of it bringing bringing this to the attention of the caller and So mushing it into a return value doesn't work very well because the caller can ignore that and so forth so you want an exception mechanism because that allows you to bring things to the attention of your caller but it was sort of unclear how to do this and John good enough wrote this paper in 1975 in which he talked about what is
the state-of-the-art with respect to exception handling and he also proposed some notation but the what he said about The state-of-the-art was that there were two key issues first of all should an exception mechanism be a termination mechanism or a resumption mechanism so termination means you make a call to the procedure it throws an exception and stops that's the end of that procedure resumption means it throws up something some other code handles it and then when that's finished control resumes in the procedure that threw the exception and pl1 has a mechanism like that in fact Pl1
has a mechanism where you could throw an exception maybe you resume maybe you don't okay and then the other thing that was not clear or that had many different techniques was how do you specify the handlers today we think about them as being at the call site or related to the call side through the program structure but then they might have been defined off on the side you might have said for this module here's the exception I want to handle how Here's the here's how I want to handle that exception and so forth okay so
with this as a background we settled on an exception mechanism that was a termination mechanism here's just a little code uh for the choose operation which is an operation of set that returns an arbitrary element of the set and obviously if you pass this an empty set it can't return an element and so in that case it signals empty and that's the end of that call and then Here's a little Handler okay so we chose call site as has become the norm today so here I have a call the choose operation and I've attached an
accept statement to it okay so this probably all looks very familiar to you because this is how it's done today uh there is one thing about the clue mechanism though that isn't done today and I actually think clue did a better job than what's happening in languages today um if you think about What happens when an exception comes up from from procedure that you call there are three possibilities okay first of all you might handle it so I'm running through a loop the exception happens this means it's the end of the loop I go on
and do the next thing another thing that happens is you propagate it so an exception at a lower level means that I also I'm going to have to terminate an exception but the exception that I terminate in is different from what Happened below it's my exception but there's a third possibility shouldn't happen so for example I just checked that the set was was non- empty then I called choose well you know choose might throw an exception and the real question here is you know what does the language design say you have to do about this
so if you think about Java Java says you better write the code that handles the exception you think about c c says Ah you just let the exception go racing up Okay these are both not very good decisions the first one is bad because you end up with all this useless exception handling code and the second one is bad because now you never know what the interfaces of your modules are since any old exception could come shooting up through them what clue did was something different it had the failure exception so what happened in the
runtime was if an exception or actually the compile time if an Exception should happen happen and it wasn't handled by the code of the caller it we actually changed it into the failure exception and the failure exception had an argument which was the name of the exception that caused the problem and then the idea was every procedure had this one additional exception failure and this was typically treated in a very different way you know you would go back to some high level of your program where you had a checkpoint You throw away everything and start
over again okay and the principles that guided us were on the one hand to have accurate interfaces and on the other hand to avoid all that useless code okay the final topic here is iterators so many not all but many data types are collection types and whenever you collect stuff it's probably because you wanted to do something with it and typically what you want to do with it is iterate over it I want to print all the Elements in the set or I want to add them together or whatever it is that I want to
do so you have the need for a construct like that and we simply had no idea how to do this uh we had a couple of ideas that we could have used with the mechanisms we had available for example I could take the set apart maybe I have a select operation which returns an arbitary element and takes it out of the set that way I could iterate over the set using the select operation but At the end the set's empty and sometimes I don't want to make the set empty I'd like to use it further
okay or we could complicate the abstraction I could turn the set into an order set with a notion of the first element the second element and so forth but it's in general really a bad idea to take an abstraction and make it more complicated so that was also not a very desirable solution so what happened was we went to visit the group at Carnegie melon this is Bill Wolf and Mary Shaw who were developing the alard language and they described to us a mechanism they were developing called generators and you can think here about Java
generators okay so the idea was the generator had several different operations and one of them would return the next element and one of them would tell you when you were finished or something like that and it was linked to a four statement and we could see that this was a solution to our problem Except we thought it was sort of inelegant and so on the plane ride home Russ Atkinson who was one of the students I mentioned before invented iterators and the basic idea in an iterator is it's like a procedure except that it yields
results and so the idea here is I'm calling an iterator in my four statement so members is an iterator and when the force statement starts I call members and members is going to produce the elements of the set In some order and so when it produces an element then we run the body of the loop and when we get to the end of that iteration we go back into the iterator which produces another element and so we go back and forth like this until finally the iter Ator is finished and that terminates the loop so
that's the basic idea of iterators and here just to sort of complete the story is a little example of how you would Implement members and Notice that it also is implemented using an iterator so these iterators um do not have full expressive power so iterators are defined they can be nested they can be recursive but they cannot be used to build to compare say two lists side by side supposing I wanted to check whether two lists side by side had the same elements I could not do that with iterators I could only look at one
list at a time and this was a conscious Decision basically what we were going for here was what you might call the 90% solution where we had a mechanism that was simple and easy to use and was mostly what you wanted and then the idea was well if somebody wanted something more complicated they could build it directly using data types of a generator type solution a final point is that this provided a very efficient implementation technique what we did is we took the body of the loop we turned it into a Little procedure and passed
it as an argument to the iterator code so you would call the iterator which would call the loop body and so that made a very efficient mechanism whereas a more complex iterator mechanism is um requires basically a co-routine like structure the main thing to look at there is how easy it is to implement that iterator and uh this is a pretty simple one but walking over a list can be pretty hairy if you try to do it with Generators it's very straightforward with iterators okay so that's it for clue okay so after clue what happened
was yes one thing I'm really curious about in clue is if you looked at all that code there were no semicolons after any lines when did you realize that that stuff wasn't necessary in these types of uh yeah in languages so this is the question was how come we have no Semicolons and the answer is it was a conscious decision we decided to develop the grammar to get rid of the semicolon because they were so annoying in the languages at that time you were always getting these errors you know did the semicolon go before the
end or maybe the semicolon couldn't go before the end and those were sort of Arcane rules and so we just decided you can design a grammar that doesn't require semicolons did you know that already um it's Other um we I think we took it as something we wanted to do and you know I think we had to play around with the grammar a bit to make it work but it uh just seemed like it so it was so silly to have these stupid syntactic errors that meant nothing there's a lot of stuff I haven't talked
about in clue and that's an example of one of the things I'm not covering okay so after clue I actually moved into distributed computing um and When I developed the arus line language that's a language that has concurrency in it so it's like I put that concurrency problem aside and then I picked it up later but when I picked it up in augus by then the internet was beginning was actually the arpanet and so I picked it up in the context of distributed computing and Argus is a language in which to build distributed applications uh
and i' I've been mostly working in distributed computing ever Since although I have made little steps into programming language design every now and then it's not just Argus I designed something called polyj which was when I was very annoyed that Java didn't have polymorphism so with my student Andrew Myers we developed a polymorphic Java and so forth uh the only thing I wanted to tell you about was one last thing that's related to this oh and and another point is I did continue to work on program methodology I also was very interested in the question
of how do you specify abstract data types how do you reason about the correctness of abstract data types so I did a lot of work in those areas um but I did want to talk a bit about type hierarchy so what happened was in 1987 I was asked to give a keynote at oopsa and I decided that uh this would be a good time to visit object-oriented languages and find out what was going on With them I hadn't been paying much attention to them and so I read a lot of papers and some of them
were pretty bad and some of them were okay but what I discovered was that um there was mass confusion and the problem stemmed from the fact that inheritance mechanism were being used for two purposes and these two purposes have different needs they were being used for implementation and also for type hierarchy so implementation is just you You know you have a class and then you say well here's my Class C and C Prime is a subass and then C Prime sort of inherits all sorts of code from C and the main thing I don't personally
think that implementation inheritance is actually very important um I just pointed out in the paper that it violates encapsulation because Small Talk which was the main object-oriented language at the time had encapsulation in the sense that using Code you know Could use objects and would not be able to get at the private Fields but that was not true of the uh subclasses and so if you wanted to reimplement this class that created a problem where you had to worry about those subclasses on the other hand I thought that type hierarchy was very interesting but it
wasn't very well understood stood and I read papers in which people were clearly really confused about it so you know there was a paper I can't remember What paper this was in which they talked about how stacks and cues could each be subtypes of one another because they chose you know an add method that added an element and a remove method that removed an element and therefore you know they've got methods of the same name they've got the same methods and therefore each one could be a subtype of another and yet clearly this is not
true true because if you wrote a program that expected a stack and somebody gave you a Cue you'd be awfully surprised okay so in this paper I wrote a simple statement that says objects of subtypes should behave like those of supertypes if used via supertype methods so sort of the obvious intuition if you think about it you know I'm write a program in terms of something super type I know what that super type is supposed to behave like I'm actually past an object of a subtype well that's fine you know I use it with The
super type methods it just should behave the way that I think the super type should and this was U this the keynote at oopsa um was actually published a year later I also talked in that paper about the relationship of subtypes to polymorphism on the top line I have the clue mechanism where I talked about the operations on the bottom line I show how you could have done it with a type hierarchy I actually think the type hierarchy method is better um but notice That in either case there's this got to be a semantic part
to it as well as syntactic part uh you have to be able to in the one hand it's not just that t has equals T has to have an equality relation right and it's not just that you know s is a subtype of T but it actually has to behave like T but the proofs happen at different times and that's why I think maybe the subtype mechanism is better because you define the subtype once and you prove it then Whereas the other kind of proof would have to have happen every time you instantiate okay what
was interesting about this paper was it turned into something called the lisov substitution principle and this was not a name I invented I didn't even know about it for many years and then I think what happened is someone sent me an email and they said can you explain this thing about the Lov substitution principle and I discovered that there was a you know There was chat on the Internet it's still going on it's called LSP nowadays it's actually though very important for object-oriented programming because it's a sort of a basic principle and later on with
Janette Wing I did some I formalized it to make it precise okay so that's pretty much it okay here's the thing that was so stunning to me I I really hadn't been thinking about it and when I started to Think about it I realized that the world had changed from the time I did that work to now and in fact my husband who was following what was going on in the internet about the time I got the touring award and he was looking every day there was more stuff uh came across a quote from somebody
who said well what's she getting that award for everybody knows this and I mean that just shows you how the world had changed and so it's amazing I mean really Amazing on the other hand you know things are not that great yeah this is how they're done but you know know we still have a software crisis we still don't know how to build programs all that well this these techniques help but you know lot more is left to do so I just wanted to conclude with a few challenges this is not intended to be everything
that one might do research on and mostly I focused here on um systems area programming languages um it's Striking that there hasn't been much progress in abstraction since data data abstraction I've been waiting for that new thing now maybe map ruce is a an example of something that's coming along that's new um you know some of the stuff in patterns there are some some abstraction mechanisms there that are interesting but by and large there hasn't been much and that's maybe that's what it is you know or maybe somebody will have a Breakthrough and we'll see
a better way of doing things and that will improve the programming process um massively parallel computers are the problem today the real problem is how do you implement how do you implement programs that run on them um we can all see how we can use a small number of processors um but you know can we use a 100 processors can we use a thousand processors you can use them if you have Data parallel uh if a data parallel structure works in your problem but you know could I Implement a database on such a machine so
uh you know we're not going to be able to use these machines unless we can figure out how to Pro program them this may be just the right answer by the way I mean just because Moore's Law is running out of steam doesn't mean that Intel has to sell us computers with thousands of processors in them it's a kind of a gap there but On the other hand I think this is a very important problem and it would be nice we haven't made much progress in parallel programming in all these years and so you know
now is a good time to look at it again it's clearly this is an area that's a very rich source of problems for machine Architects it's a very rich source of problems for people who work in operating systems but the real question is the programming languages or the programming paradigms How are we going to use those machines that's going to be the Crux of the problem the other thing I think is really interesting is the internet as a computer this is more in the area that I'm you know in uh we can see this happening
with cloud computing storage and computation are moving online but there's just a host of problems out there um nothing is really very well defined the semantics of writing running a program on the cloud you know when Something goes wrong what does it exactly mean uh the same is true for storage the storage is not all that well- defined the semantics are not necessarily what you want and so there's a whole bunch of problems that need to be solved to make that a reality and I don't think this is entirely a systems problem there could be
a programming language problem there too maybe we'd like to actually write programs that run on the cloud and think of them as being Sort of distributed programs with comp components that can be put in different places it's kind of odd to me that programming languages today they only give you the ability to write something that runs on one machine and then you link up your pieces I'm talking now about distributed computing by going to some other mechanism you know net or something like that maybe we really could have a programming language where you write your
whole distributed program As a program in that language and that might be a good thing to look into so anyway there's many problems left I know I'm talking to many students here so there's lots of research to do and that's the end thank [Applause] you I'd be happy to answer questions if there's um yes as a uh programming language designer what what do you think about The programming languages that a lot of people are using today some of the there were things like python R be JavaScript which were you know to some extent some of
those were designed by accident or certainly a lot of them designed by people who didn't have a background in designing languages but have become very popular and in some cases intractable like you know you you can't avoid JavaScript if you're doing stuff on the web yeah no matter how much you love it Or hate it it's just there and that's what we have to deal with yeah I I think it's very sad I I don't don't and I guess what happened is that the programming language people were ignoring this audience and so therefore uh amateurs
stepped in to fill in the Gap and you know we're all paying for it so I had a sort of a horrifying experience by proxy I have to say because it was one of my graduate students who discovered this but we were Looking at a web server and this web server had confidential information that it was in charge of and it was just kept up there in the global storage and all the code could access it and you know it was just uh who could say that there was any Security in this code I mean
it's it's like it's back to the bad old days so um I honestly have not been following the programming language world my friends tell me that uh you know python is gradually turning into a pretty good Language they tell me that Ruby has iterators um I've got gotten kind of interested so I was thinking maybe I'd start looking at them but I I do think there's in some sense the world of the professional programmer I mean we may not build our programs in Java because we're at too low a level and the performance matters too
much but we use the principles you know and then there's this other world where an awful lot of code is being written and it's being Written in languages that aren't very good by people who don't know what they're doing and you know so it's really a problem and there's a tremendous um I don't know people don't like strongly typed languages and maybe that's because the strongly typed languages have too too much syntax in them because you know it isn't necessary to have Types on all the variables you need Types on the Interfaces and so maybe
you know I think it'd be good for programming language people to pay attention to this and maybe something better uh can come along and uh you know will start to improve the situation I also think the systems people are to blame because especially when you look at the browser side the uh way those you know those are fundamentally operating systems but they're terrible operating systems so um you know that's another place where work Needs to be done so we should take questions from the remote audience first because that link will yeah sure so are there
any questions from UNC or NCSU I I'd be happy to take questions from the remote audience if somebody has a question bar yes um can you say anything about the decisions you made in choosing the parameter passing conventions include like call by value or call by reference what what was your thinking about that I couldn't tell from the Description uh we used to refer to as call by object it's really exactly what Java has if you ignore the fact that Java has integers and they're treated differently if you just think about the objects and you're
always passing pointers um it was a decision we made very early I never liked call by reference I really didn't like call by name how does it differ from call by reference uh call by reference if you remember in C for Example you can actually have a pointer in the stack up to the stack and then the idea is you can assign to that variable and it'll assign you know so really clue is an object-oriented language in the sense that the all the objects are sitting in the Heap the program variables all point to those
objects and when you call a procedure you simply pass those pointers along so it really is I mean it's I I I'm not sure about the Technical term at this point whether call by reference now means that but Heap variables that was sort of the view nothing was by accident include there was a lot of we thought about everything you know so everything was thought about and for example we um we never actually implemented but we intended to implement uh checking of uninitialized variables so we decided that if you think about you have a declaration
so you create a new variable You know is it required by the language that you immediately assign to it so it's never uninitialized or not okay this is a language design decision and our design decision was that we would not require it to be initialized because if you do that what you do is you end up sometimes with phony initializations where the person just wasn't ready to initialize you could initialize if you wanted but you didn't have to and then by simple program analysis you can Mostly figure out whether when a variable is used it
has been initialized and so in the few cases that were left we would do runtime checking okay so that's a very you know reasonable way of handling the problem where you catch the errors when they exist but it really has no cost most of the time because most of the time through compiler analysis you can figure out that no checking was needed that's just an example of the kind of stuff we Did think about I think there was a question over here yeah I think much of the discussion on abstractions was on a structures uh
have you followed much about what's going on in abstractions for Behavior like State machines activity diagrams and works in the programming language world we use them to learn how to program but in the operating systems in middleware area these abstractions seem to becoming an integral part Of uh application um so I have to say I have not paid very much attention to workflows I mean I'm a little familiar with them but I haven't been paying a lot of attention so yeah yeah I have another question about iterators um so in your example you had set
and there's no order right um right but sometimes you do want that order preserve like if you iterate through a stack or you iterate through a sort of list y but There doesn't seem to I mean I couldn't figure out how you would actually enforce that in the implementation of okay so um in a programming language you never the programming language doesn't capture semantics you know all a programming language does is it a type checking does a very simple part of correctness checking you can capture some of what's needed to ensure your program is correct
by having strong typing and type Checking but to really get a correct program you have to have specifications and it's so in the it's in the specification that this information would be given so for example the specification for the member's operation for set would say maybe arbitrary order whereas the specification for a stack would probably say from earliest to latest and you would put this into the specification and then you know the implementation would only be correct if You could prove that it matched the specification and the using Code could then rely on the specification
uh one thing that's interesting about iterators by the way is that sometimes with an iterator it's okay if the code in the Loop modifies the element being iterated over and sometimes it's not okay and so part of the specification for the iterator has to say whether it's okay or not so the reason I'm having no trouble answering Your question is because this is the kind of stuff I taught in my course uh I I developed a course at MIT about uh programming methodology and software engineering and I taught the kids about specifications you know about
how to specify all the different kinds of abstraction mechanisms I also taught them all about how to reason about the correctness of um data abstractions including uh what rep invariants were what abstraction functions were and I Even had them implementing rep invariants and abstraction functions because uh these are not only really good for increasing their understanding but they're also very useful when you're debugging because the repon variant you can check in your test Suite to make sure it's always holding and the abstraction function you can use to see whether the object looks like what you
think it's supposed to look like at this particular moment in time um I always Worked with informal specifications so I developed a way of writing informal specifications with a sort of a syntax that's not that dissimilar from some of the stuff you see in Java where you you know put in your comments yes when you explored some of the ideas relating to inheritance where did you fall on the idea of multiple inheritance like in C++ or not multiple inheritance I know that might start a flame War yeah no I I didn't uh pay an Awful
lot of attention to that I do think that some of it probably came from the fact that they were trying to do two different things with one mechanism so you might use inheritance because you could borrow from this implementation but the behavior you were trying to get was this other thing over there but I don't really have a position on this I was um sort of not focused on it yeah yes you've mentioned debugging now twice um There's it seems like there's this uh kind of uh mean going around in some of the programming languages
communities where um debugging is considered bad um or a crutch um I I've actually heard it I'm just kind of curious what your thoughts in General on heug well you know dyes were always told you should write programs that were correct from the day one and you didn't you didn't have to test them um um I'm listen I'm pragmatic You know yeah you try to write correct programs but you have to test them and if they have errors in them you know so it's very important so another thing I teach in that course that course
doesn't exist anymore but that I used to teach in that course was how to develop uh good test Suites um because you know getting a good test Suite in place is very important part of the process for uh making sure your programs work right but They got errors in them you got to debug them so U I don't think it's a matter of uh you know I don't think there's a philosophy here I think it's you know it's how the world is we should be so lucky that we could write programs that were correct without
uh you know on the first try so yes were there any moments uh where you said when you took ideas from other engineering principles and you said okay Wait a moment civil engineers are doing this thing perhaps we should do something like them to make our Engineering Process more as robust and as Rel as them I can't say I ever took anything from another engineering discipline except that I when I started the work on on program methodology and modularity I kind of envied the electrical engineers because I felt that they had a much easier uh
job than we did since you know you have to build Your systems out of components those components are connected by wires and this kind of forces a natural modularity on you whereas in the software domain it was so plastic you could do anything and so we had to invent all the principles that U sort of got us to where we are today but no I I'm not an engineer by training I came out of math and then I went into computer science I don't know a tremendous amount about other Engineering disciplines yes so um questions
about the goal just to show the concept of abct oh you were actually thinking that might Beed by a lot of people like like what I thought like later Java like he took so much from but use but nowadays don't that's right so the question was uh did I think of clue as being a language that would be then produced Commercially and uh I was really in it for the research so I wasn't thinking about that but when I finished the work on clue which was around the late '70s um I did think about it
a bit and the world was different then so today you could take something like the clue compiler you could put it online as freeware and you might very well have adopters I mean that's what's sort of going on in those days though the only way you could have a language that would Be commercially viable would be for it to be coming out of a company that provided support and so forth so I would have had to stop doing research and have formed a company and it just wasn't not the thing that I decided it it
was like there was a big path a big fork in the road at that point and I decided not to go in that direction but instead to go into that distributed computing Direction it's you know it it was definitely a decision and it's not you Know I and I can't say I regret it but in fact you know it would have been nice to see clue get out there and be more used but um it's very nice now though that the ideas have in fact moved into mainstream languages yes when you find yourself writing code
now what language um you know the way I survive as a faculty member is I don't write code uh I might student my that's what graduate students are for we mostly Implement using C and C++ uh the reason is that we're always building platforms that we want other people to build applications on top of and performance matters so much for us that uh we have to to sort of pay attention to that I hope my students are writing good code um it used to be the case that they all taught my course and so they'd
all had rigorous training and modular construction and as you know you can write perfectly nice programs in see And C C++ there's not any you have to you have to be disciplined but you can do it but um yeah so thank you you're welcome