Skip to main content
Loading Explore guides…
Language Design · Acedra
Home
Explore
Computer Science
Language Design
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
138 segments
Copy
Hide video
0:00
>> DFB: The theme of today's talk is "How to succeed in language design without really trying" So could you please welcome back Brian Kernighan. [applause] >> BWK: Thanks Dave. Thank you very much for that kind introduction. It's a real pleasure to be back at Nottingham and to see the new buildings, as opposed to the old ones, which of course I don't
0:22
remember after 30 years at all. And also just thanks to the Computer Science department for the Honorary Professor appointment which is definitely an unexpected pleasure -- so, I really appreciate that. OK so let's see what we're going to talk about. We're mostly going to talk about languages in some sense or another. To some extent tools, as Dave hinted. There will actually be a
0:40
taste of document preparation in it, but not the whole story. I've had to do that because Dave is here and along with others of his former students and others. So let's start this way. So, this actually comes from a real story at Princeton. A student -- a computer science undergraduate -- thank you undergraduates for showing up, you can answer this question! So the student, whose name I have now forgotten - this is only a few years ago -- told me of something that his room-mate was doing.
1:06
The room-mate had been -- was in some other field. Geology -- or something like that, and had been set this task of lots and lots and lots of data. Find out all of the big-ish volcanic eruptions like this. And so the question is: "How do you proceed with a test like this?" And of course what my young friend said, deprecating his room-mate who was obviously a lowly Geology type,
1:26
He said: "He was doing it by hand !". And you think: "Would you do this by hand?" . No way! Nobody here would do it by hand? Right? So, everybody would do the same thing, I predict. You would write a program. Then the thing gets a little interesting. What language would you used to write it in? So, a show of hands or shout out an answer -- this is an audience survey -- "What language would you use for this task?" >> Reply from audience: AWK >> BWK: AWK! Good man! AWK. Anybody else? [laughter]
1:55
I paid these guys ahead of time. [laughter] >> Reply from audience: Shell >> BWK: 'bash', OK. We've got a shell expert here. >> SRB (from audience): Assembler! >> BWK: OK, Steve's a special case. [laughter] >> Reply from audience: Basic -- it's the only one I still know. >> BWK: Yeah! Basic would actually be a good idea. You get the idea -- there's lots of different possibilities. So anyway, I was once quoted -- I think
2:16
even accurately -- as saying if I were marooned on a desert island the language I would like to have with me a compiler for would be C. And so I thought to myself, let me write it in C. So I wrote it in C, like this. It's sort of embarrassing, at this point, to recollect just how long it took me to do this because, well, the first thing is 'fgets'. I can never remember what the order of the arguments is. Is the file pointer first or last -- well, dammit, got that wrong first time and
2:46
does it return EOF or NULL? And the answer is "yes", but not the one I picked first. and so I got that wrong. I blew the 'scanf' because you have to say %lf and not %d, or even %ld, and so I got that wrong, And then 'strtok' which has got to be the world's worstly -- worstly ?! -- the wrong word. The world's worst- designed subroutine or function ever. Just couldn't
3:09
get it right. So, it probably took me 20 minutes, or half an hour and, of course, the program isn't very good because it's not very robust. If I give it very long input, or malformed input, or something, we get the wrong answer. So generally this is not the right choice of language for this sort of task. So then I turned to my other favorite programming language -- and I wrote it in AWK. [laughter] And there it is.
3:35
And it took, as you can guess, about two seconds to write, worked perfectly the first time. It is robust. Nothing will go wrong etc., etc. So this I think is a good example of the kind of thing that you get with languages, or at least things that you can think about. Notation makes a tremendous amount of difference If you have a good notation it makes it a lot easier to do a job. And a lot of language work is thinking about what is an
3:59
appropriate notation for the kinds of things that you want to do in a particular programming language. Another issue, that is sort of related, is programmer efficiency. How long does it take a programmer to write a piece of code? Can you write it in 2 seconds or 20 minutes? That's a big difference and so if nothing else matters but the amount of time that the programmer takes to write it, then you want something that's very easy. And so again there's a
4:25
set of tradeoffs that go into picking the language that you have in mind. What about efficiency? Well, for a program like this, which is probably run once, efficiency just doesn't matter. Right, no matter what on a modern machine it's gonna run in a tiny fraction of a second and I probably spent more time doing C compilers than I did in running the AWK version, even if I ran it more than once. So efficiency doesn't matter.
4:49
Programmer efficiency is much more important than machine efficiency for this kind of thing. But on the other hand there are plenty of programs for which machine efficiency actually does matter and I can assure you from personal first-hand experience that Google doesn't run its search engine with AWK, right? They use C, or C++, or something like that. So, lots of different things that go into this question of what do you do -- what is
5:13
your language of choice. So there are lots of programming languages -- you have lots and lots of them to choose from, and in fact there's so many. There's an image that I was trying to find my image here -- here it is. Everybody here is, I suspect, familiar with the image from Genesis 11 -- the image of the Tower of Babel, in which people are trying to build the Tower to reach heaven. God gets kind of ticked off at this and says "I'll spread you out all over the world and we'll give you
5:38
lots and lots of different languages". And this, of course, was for natural languages but in some sense the same thing has happened with programming languages. And so this Tower of Babel was actually a VERY popular art form in the 1500s and 1600s. This is Pieter Bruegel the Elder from the 1560s, or something like that. So this is a famous one. There's another one which I actually like, which is not so famous, and I actually don't know who the artist is. I've tried
6:00
Google search on it and I can't find whoever that is. But that one is kind of nicer in some sense because the tower structure is more obvious and there's another reason why I like it and it's this one. This is the cover of CACM fifty-five years ago -- this is January 1961. And 1961 you think, that is roughly thirteen years after Maurice Wilkes ran the first stored-program computer -- the EDSAC. Thirteen years later. Look at all of those programming languages! And if it was a
6:34
problem of that many programming languages in 1961 what do you think the issue is today? We've got lots. Some of those are still alive -- not very many, but you'll occasionally see SIMULA, down there, LISP is still alive and well, I don't know. But you get the idea. FORTRAN? Oh yeah FORTRAN! FORTRAN is still alive. I suspect BASIC is there too. Lots of these.
6:56
And of course the image was used by Jean Sammet on the cover of her book in 1969, which attempted to be an encyclopedic survey of all the programming languages that were in reasonable use at that time. Of course it would be inconceivable for her to do that same kind of book today. Maybe we can do some classifications, so let me do a bit of, well either over-simplification, or revisionist history if you like. In the nineteen forties -- these decade boundaries are completely arbitrary
7:22
in some sense. In the late forties we had people writing absolute machine code -- putting things into machines, in binary, using either switches on a panel or perhaps, if they were lucky, paper tape, something like that. That's the way that the EDSAC was programmed originally, if I understand it correctly. Very quickly people realized that you could do better. That you could get the machine to do some of the work for you by basically the clerical stuff: assembly
7:51
languages to convert op-codes into bit-patterns; convert addresses into where they are really going to be in the memory and so on. Call that the 1950s. In the 1960s -- and this is really the late fifties -- the thing that -- probably the biggest single advance in computing, at least on the software side, was the invention of high-level languages, where you raised the level of discourse above the details of a particular machine architecture and
8:19
brought it to something that was closer to the way that a real person would think about solving that kind of problem. So FORTRAN for engineering kinds of problems; COBOL for business kinds of problems; BASIC for instruction, things like that. So you lifted it up. And this had a couple of real advantages. One is that it meant that lots more people could write code -- that you didn't have to be an expert any more -- or, at least, not an expert in the assembly language of a
8:49
particular machine. You could write your program once and translate it -- in your own terms -- and translate it into a particular machine. And then the flip side of that, of course, is that if you wrote it once in a high-level language like FORTRAN, then you could translate it into whatever machine you happen to run on. So this was a tremendous leap forward. Now, every one of those things, Algol, FORTRAN and so on were focused
9:11
on a particular domain of applicability to some extent. What happened in the 70s I think, is the development of languages that would let you take on some of the hard-core computing things that go into writing compilers, loaders, assemblers, editors and so on, and ultimately the operating system itself. And that was the role of C, primarily. C is certainly the survivor of that era, that you could write any of these really core central components of
9:38
computing, in a high-level language, so that was very, very important. Now, what's going on here? As time passes computers are getting more powerful and more memory and that means the programs are getting bigger and it becomes harder and harder to maintain intellectual control of the programs as they get bigger. And so we start to add things to languages that help us maintain control of
10:01
the structure of the code. And that leads to object-oriented languages of which C++, I suppose, is the dominant example these days. In the 90s -- I'm running out of things to describe these with -- sorry -- but certainly strong typing in its various forms ... Finally somebody saw it! Thank you. [Audience member reacts to slide's description of Java as 'strongly hyped'] I thought it was worth a try. [laughter]
10:23
Languages like Java - and you notice that Java is ... well first, it is strongly typed. But the other thing is that it's again taking advantage of the fact that hardware's gotten more and more powerful. You can afford to do something that isn't compiled into efficient machine code but in fact is an interpreter. Which draws away a factor of something in speed, but is easier on
10:44
programmers and makes portability very much easier. OK -- and I don't know what happens in the 2000s, and then the 2010s, well we're only halfway through and it's unclear but there's a lot of ongoing work in languages -- mainstream programming languages like this. Languages that will take on any task, reasonably well, over the whole spectrum of things you might want to do. Now, I don't know what's gonna happen with some of these new languages, I will call this "totally up in the air".
11:11
There's a parallel stream, which I think is interesting, which is scripting languages. And again loosely decades is not quite accurate. A very, very early example of that is SNOBOL, a language that is, I think, totally dead at this point although you never know. And then the people in the 70s discovering that you could program in the command interpreter of the operating system -- something that, sort of, in retrospect is obvious but seemed like a neat and new idea
11:36
at the time. And then we get languages like AWK and other scripting languages, sort of in the 80s. AWK dates from roughly 1977. And then we get three scripting languages and I probably should put Ruby up here, or something like that as well, and then JavaScript. JavaScript, in fact, started in 1995 but is the dominant scripting language, I would say, and certainly on the Web ever since. And I don't know what's gonna happen again
12:07
in the decade that we're in the middle of. So we have, so far: mainstream programming languages, scripting languages. What's a scripting language? I've always liked Larry Wall's definition of scripting languages but we can be a little more precise than that, perhaps. I think the fundamental thing about scripting languages is that text is a fundamental data type in the language, that they manipulate text as
12:29
well as numbers and that's different than let's say, C, where text is kind of an afterthought almost in some ways; it's not a natural act to do text processing in C, although lots of people do. Regular Expressions tend to be an integral part of scripting languages; sometimes they are libraries, like they are in Python, or I guess in PHP, and sometimes they're built
12:49
right into the language, in some sense, as they definitely are in AWK and in Perl, and I think Ruby and to some extent in JavaScript. Either way they are part of it in a way that they really weren't in mainstream programming languages. All scripting languages have associative arrays, sometimes as the only data structure for manipulating more than one thing at a time. And all scripting languages tend to play fast and loose with types. So the type theory that you might have in
13:16
something like SML or OCaml or Haskell, or whatever, -- type inference and so on -- minimal in scripting languages, often nonexistent at all -- whatever it is it's OK, we'll manipulate it. And then usually interpreters, taking advantage of the fact that machines are much more powerful, so you can actually don't have to worry too much about how fast something runs, it's good enough. So there's a third stream
13:45
that fits some of the folks here, which I'm leaving blank, The reason I'm leaving it -- there are two reasons I'm leaving it blank. One is that I don't know enough about it to say anything intelligent, so it's probably better not to reveal my ignorance and the other is that I think, realistically, functional programming languages starting with LISP and going on to things like Haskell and OCaml today, are relatively little used
14:11
in what I will call "the real world", i.e., not in a University. If you picked a random hundred programmers on the streets of Nottingham, or whatever, I guess that five of them would be functional programmers, at most. It would be down in the noise in that sense. So, the flip side of that is that everybody profits tremendously from the kinds of things that have been learned by research in functional programming languages. All kinds of interesting things that have been first
14:39
explored in those languages have found their way, over the years, into mainstream programming languages. I guess you could start with recursion as an early example. Garbage collection; I would guess type inference and functions as first-class citizens. All of those things started in functional programming languages and then find their way into mainstream practice
14:59
because they're such a good idea. And then, finally the fourth stream and this comes to what Dave was talking about a few moments ago, this idea of domain-specific languages: languages that focus not on taking on all kinds of programming problems but rather on a fairly narrow, specific domain, in some sense. The languages need not even be Turing complete; in other words you might not be able to simulate
15:21
anything with them. And there are lots and lots of examples of those and we mentioned regular expressions, of course, And the shell and AWK have that property. Lots and lots of document-preparation languages over a whole spectrum of things. They are languages in the sense that they have formal, rigorous grammars and well-defined semantics at least in principle. Languages like that. SQL in its pure form is a declarative language, but obviously a language focused on database retrieval.
15:51
R, a language for statistics, which I'm guessing many people have used here. And AMPL, a language for mathematical optimization, which, viewed from a distance, is sort of analagous to R -- big complicated algebraic structure of things applied to a narrow domain. So I think what I'm going to do is to talk about some of these kinds of things, focusing briefly on AWK, and then on AMPL, and then come back to some of the document preparation kinds of things. That's where we're going.
16:21
One of the interesting things about domain-specific languages and something I would actually like you to try and take away today. They are smaller and simpler than big mainstream, general-purpose languages and that means that it's actually quite reasonable that somebody in this room could say, you know, "If I designed a language to solve a particular problem I could actually make my job easier". And so you can think of building a small language that focuses on some
16:47
task and that's pretty reasonable. Thinking I'm gonna build the next version of C++ -- not so reasonable. I'm not knocking you -- but that's harder. Something small, something of the scope of some of these things like regular expressions or some document preparation tool, much easier and well within the grasp of anybody in a relatively short period of time -- a good way to attack problems. I've been involved with the design and implementation of special-purpose
17:15
languages like this for a very long time over a whole spectrum of activities. I've probably done eight or ten of them, depending on how you count. A couple of them actually survive quite well; they're really used, people use them today. I noticed several people -- thank you -- said AWK would be the way they would approach a problem. So AWK is an example of a survivor. I have done some languages which were successful in their time, but
17:41
the time has passed. And then there were others that sank without a trace, without leaving any mark on the world at all. So I won't spend too much time on those. OK. But let me talk about some of these languages and see what's going on. As I do, think about what is it that might make a language sort of succeed for something where other people would want to use it. You built it -- other people would want to pick up on it. Or what might you do that would mean that other
18:07
people would never use it. So think about the success and failure. Think about how well the notation of the language matches the tasks that it's meant to take on. That's the sort of thing that I'm going to talk about at this point. Now I keep harping on notation. I think it's actually an important issue. Benjamin Whorf, who was an American linguist lived in, roughly, the 1900 to 1940 -- to 1945 -- period, something like that.
18:28
Benjamin Whorf studied mostly the languages of Native Americans in the south-west, people like the Navajo, and he had this wonderful remark about language shaping the way we think and determining what we can think about. He was talking about natural language. I think it applies even more strongly to the artificial languages that we create to tell our computers what to do. And so it's worth remembering that. The other
19:00
language-related quote that I've got here, is one from Alan Perlis. Alan Perlis knew a thing or two about language design. He was part of the original Algol group. He created one of the very first and most influential programming languages ever, and this observation that a programming language should change the way you think about something, otherwise it's not worth worrying about. If you haven't seen
19:23
his epigrams on programming, Google it; go look at it. There's probably a couple of hundred epigrams there. Most of them are quite perceptive and many of them are actually kind of funny. And so it's worth just looking at -- a great guy. So with all of that in mind, let me talk then about something which everybody here appears to be semi-familiar with.
19:45
Actually, let me do another audience survey. How many people here have used AWK? Ha! I could skip the next 10 slides! OK. Let me at least rip over them fairly quickly. So AWK derives from experience with the UNIX shell, which was not actually very good for numbers. Somebody suggested that they would use Bash or a shell for numeric computation. The shell is not very good for that. And I was interested in that sort of thing when Al Aho and Peter Weinberger and I were thinking about this.
20:17
Al was interested in regular expressions. He had just done a program called Egrep, which I suspect many of you at least have heard of, if not used regularly. And so he was very interested in that. Peter was interested in database kinds of things and so the combination of three people interested in these sort of peripherally related to each other issues led to this language which was meant for doing these very simple one-liner kinds of
20:45
programs, things that you thought should be only a line of code. How do you design a language so they are only one line of code? So, data selection. Finding all of the volcanic eruptions whose magnitude is greater than 6 is an example of data selection. Here's a bunch of data, give me the ones that match a particular condition. Sometimes you want to transform them in some weird way. And sometimes you want to do a report
21:07
generation kind of thing. Summarization. So this is what AWK was meant to do and the things in blue are, in fact, AWK programs that will do that. So the language itself uses a notational paradigm which I think is extremely useful, very valuable. And if you look for it you'll see it in a lot of different places. It's the idea of a pattern-action language. What you want to do is you have a bunch of patterns. And for each pattern
21:34
there's a corresponding action and you just look at the data and when you see an instance of the pattern you do the corresponding action. And so that works for all kinds of things very nicely. Grep, for example, the pattern is just a single regular expression and the action is: "Print it if it matches". Sed, a sequence of editing commands, those are the patterns; the actions are whatever you do when you see one of those patterns. You think
21:55
about the YACC parser-generator. The patterns are the grammar entities and the syntactic rules of the grammar. Think about Lex, the lexical analyzer generator. All kinds of things have that structure. So pattern-actions are a very effective notation. People resonate with it because that's the way we think. You see pattern-action, I guess, in the pattern-matching stuff in functional languages too. I'll just say that just to make it look like I know something -- even if it's not true.
22:22
So anyway AWK is basically a bunch of pattern- actions, like that. The patterns are things like regular expressions or numeric tests like '$3 > 6' and the action is a language that looks like C. Another principle of notation, perhaps, is build on what people are already familiar with. Don't invent something brand new if there's something already there that's really pretty decent and that people will know about already. And then the structure says: "Automate what you
22:50
can", so that people don't have to write code that's just boiler-plate when you know what you want to do anyway, which is to go through all the data. So AWK is, in effect, three nested loops: go over the files; in each file go over the lines; in each line go over the patterns and, if the pattern matches, do the action. And so that's the whole structure of the thing. We spent a lot of time when we were working on this
23:12
trying to put features into the language that made it easy to do these one-liner things, where something you know in your heart it's one line long. It really shouldn't take more than that. What can you do in the language design to actually make it so that it takes one line - and nothing more? So we did a lot of things automatically. Reading through the input and splitting it? Completely automatic -- you don't have to
23:35
think about it. It just does the right thing and that goes right down to splitting the individual lines into fields, because people wanted to pick up the first field, the second field and so on. Variables in the language. You need variables obviously but what we did was to say "Huh!, what goes into a variable?" Could be a string, could be a number, we don't care. Either was fine. We'll just try to keep track of it, and try to
23:56
do consistent arithmetic, or other operations, depending on whether it seems to be a string or seems to be a number. Don't worry about initialization of types etc. Build some operators, throw some variables in for things that you already know. Why should the user have to compute them if you know them yourself? That's very easy. I mentioned associative arrays -- I'll come back to that in a second. We need some kind of data structuring mechanism, something to handle aggregates of data,
24:23
and the associative array is good for that. I mentioned Egrep, that's what Al was working on. And in fact the first version of AWK -- the current version of AWK at least as I put it -- is still Al's code from 1976 with the same bugs in it as there always were. Control -- I've mentioned that. And so on. And so it's all pretty straightforward. All aimed at making the language so that something that was simple, in
24:45
your mind, should be simple when you wrote the code. So that in principle you could just type an AWK program at the command line and have it work. Let me say just a word about associative arrays. Associative arrays are THE most useful single data structure. Period. If you're only going to teach one data structure in an undergraduate course, teach them the associative array, right? It's the only one that matters. All the
25:07
others are derivative, in some sense. So here's an example of associative arrays, again with the standard undergraduate computation: "What's your budget for beer and pizza?" So I've a bunch of records that say how much pizza I bought and how much it cost. And I want to know the total at the end of it. Add up all the corresponding pizza values and all the corresponding beer values. And here's the AWK program which does it. This is actually
25:30
an action with no pattern. And so one of those "Do it automatically things" is to say that when you have an action with no pattern, do it on every input line. On every line it says: "Increment the pizza element or the beer element by whatever you see in the second field". And then at the end go over them and just print the accumulated values. And that's so straightforward that I can actually
25:58
type it correctly at the command line. Just do that computation, which I do on a very familiar everyday basis. So there's lots of lessons that can be learned and I think I probably mentioned these over and over again. Lessons that you learn if you do a language and other people use it. Or even if they don't. But primarily if other people use it you learn things and I've seen the same kinds of lessons show up over and over
26:23
again. So let me sort of summarize them in the context of AWK but the same thing happens in other places. One is if you do anything useful people will abuse it. Guaranteed! And so AWK has been used for all kinds of screwball things. We meant it for one-line programs. So the typical AWK program is one or two lines long. I've seen AWK programs as long as 20,000 lines. That is serious abuse -- by somebody who's obviously deranged. [Laughter]
26:56
So you can write all kinds of things in it because it's a string processing language and it's pretty good, and associative arrays let you do symbol tables very easily. And so on. I see programs that generate AWK and have written them myself. That seems like a very useful thing to do. And I've even seen people learn to program starting with AWK. Which, as Jon and I were talking earlier -- and Graham maybe -- about:
27:13
"What's the first programming language here?". And I'm gonna guess it isn't going to be AWK either. And something that's important. If you have a program which is used and people start to write programs that generate that, you discover very rapidly that machine-generated input is different from input written by people. First it's voluminous because machines are tireless in cranking the stuff out, and secondly it doesn't know about all the places where something might not quite work
27:44
right, or whatever. And so machine generated output stresses programs very much harder than people do. And so it's a good way to test programs and find out when they don't work. One of the very first -- *the* first implementation of the C++ compiler that Bjarne Stroustrup wrote at Bell Labs. was written in C++, of course, but it generated C. And so the output of the C++ compiler was C that was utterly, unbelievably, inscrutable to humans.
28:14
And it was a stress test for compilers because it had things -- expressions that were nested twenty, thirty, forty, levels of parentheses deep, with all kinds of weird names that were very similar and it just tended to break C compilers. Machine generated stuff is just different. If you design a language and other people use it, you very quickly learn that you screwed up. There's no shortage of screw-ups in AWK. A couple of
28:37
them I can take credit for myself; the others I'll pass on to my colleagues. And another thing is this tension between changing something because you got it wrong or because you've have a better idea, versus trying to keep it stable so that people can learn something don't have to keep trying -- to keep up with your language. I don't know how many of you are writing Swift code to make your iOS applications, for example. But Swift keeps changing and people have code that
29:05
works and oops! it doesn't work any more with the next version. That's a problem and how do you stop that? And at the same time if you've done something wrong, or you need new features, people want to add things. So there's this pressure, this continuous pressure for adding more stuff, but at the same time keeping things small. Hard to do. And I always like this observation from Tony Hoare about not including untried ideas
29:32
of your own in a language. But somebody's gotta try them. How does it get started?! Anyway, I have one example of a perverse AWK program. I had several but I think I'll not impose on you. I'll just show you the one. This is from 99-bottles-of-beer.net. It's a site that has programs that print the lyrics of 99 bottles of beer on the wall, 99 bottles of beer ... if one of those bottles should happen to fall etc. You all know this drinking song? It
30:05
has that in fifteen-hundred-odd languages and it's interesting -- there are more weird languages than you could imagine -- back to the Tower of Babel -- and this is one of the AWK versions and I rather like it. OK, I want to switch gears, then, to a language which I'm guessing will be rather less familiar to everybody here. This is this language called AMPL. So has anybody here used AMPL? Total deadly silence. OK, I should have started here. Skipped all that AWK stuff.
30:34
So -- everybody here knows what linear programming is, right? Basically you've got a system of constraints and you want to find a solution; you want a set of variables whose values, plugged in, satisfy all the constraints, and at the same time minimize or maximize some objective function. So that's fundamentally what linear programming is. If the constraints and the objective are linear and then you can have things where they're not linear
30:59
and you get other stuff like integer programming, quadratic programming, and so on. How do you describe this system of equations or inequalities and the constraints and so on? How do you describe that? In olden times that used to be done either with a program that was called a matrix generator, which would generate a giant matrix of the coefficients of the constraints. Or there was a really klunky
31:22
language that made Fortran look elegant, called GAMS, which was modeled on Fortran but it was awful. So Bob Fourer and Dave Gay and I worked on this. Bob Fourer was a professor until fairly recently in the operations research -- what was it called? -- the Industrial Engineering and Management Science department at Northwestern University near Chicago. He spent his sabbatical year with us at
31:44
Bell Labs in 1984, that golden era. He had this idea for a language, and Dave Gay and I worked on the design of the language with him, and I made the first implementation of AMPL, which was my first C++ program, so as you can imagine, it was pretty crappy. So what AMPL is, it's a language that lets you describe optimization problems in a notation that's relatively convenient for somebody who understands basically mathematics, simple mathematical notation.
32:17
You start with a description of what the problem is, and you write it down algebraically as I would write it on the board here or over there. What the description of the problem was. We would transliterate that into AMPL, and then AMPL would take that description of the problem, and the data for a specific instance of it, and turn that into something that would go into an optimization program -- a solver. The solver would think for a while and then produce
32:43
results back, and AMPL would reverse the process so you could see the results in the form that you had originally posed the problem. That's basically what it does. Let me give you an example because that's a lot of arm-waving. So here's an example of a classic optimization problem called the diet problem. The diet problem: you have to feed a large number of people, and you want to make sure that you don't give them too much of fat, sugar and stuff like that, but you give them
33:11
enough of nutrients they need, like various vitamins and so on, and you want to do it at minimum cost. So think of it as how do you feed people who live in dormitories or residences? The university's desperately eager to pay as little as they can to keep you guys alive but they want to keep you alive, just barely. OK, so that's the idea. OK, so this is sort of an algebraic specification of a diet problem. It says look, I've got foods and I've got nutrients, and I've got an array
33:34
which is how much of each nutrient is there for any given kind of food, so it's a two-dimensional array. Then I've got things like how much does a particular kind of food cost, and what nutrients does it contain, and things like that. Then what I'm want to do is figure out how many packages do I buy. Now this one is posed as I want to buy TV dinners, which were a popular form of ... food --
33:54
I guess, sort of food -- back in the States. I want to minimize the cost, which is how many packages do I buy of each type and how much does that package cost. And I have some constraints, which are basically I want to make sure I get enough nutrients but not too much, for each of the various things. That's fundamentally it. That's what I would write if I were a professor doing operations research and writing things on the board. And what AMPL does is to take that same thing and
34:20
convert it into a language that you and I could, as computer people, say, "Oh, OK, I see what it is." I've got sets, I've got parameters, two-dimensional parameters, one-dimensional parameters. I've got indexing, things like "for all the i in nutrients, this has to be greater than that." And then here's what I want to buy, I want to buy this which has to be at least this many but not more than that many. And I want to minimize the total cost, which is the sum of these things:
34:47
the cost of a package times how many you have to buy of the package. I have the constraints. It has to be at least this much and no more than that much for each of the nutrients. You can see that the basic entities are fundamentally indexing over sets, in a reasonably natural way. It's a purely declarative language at that point. It doesn't say anything about the computational process; it's just taking data in and producing a big matrix -- very big but very sparse.
35:16
A typical industrial linear programming model might have, oh, 1,000 to 10,000 rows and 1,000 to 10,000 columns but the density would be way under 1 percent. So very big but very sparse matrices. Then the solver thinks and back comes the value. So that's the fundamental AMPL language. But then there's something that's kind of interesting about it as well. I've got the data to worry about.
35:39
Because that model would describe any number of diet optimization problems, but specific ones, what I would do to buy TV dinners is different from what I would do to feed undergraduates, which is different than what I would do to run a high-end restaurant. There's all different kinds of things, different data. And so within AMPL there is also a data specification language -- various ways in which you can put in the data for this. A lot of it just building tables.
36:05
There's lots of different ways to do it. So a modeling language, a data description language and then of course you have to actually run the silly thing, And so there's yet another language, kind of a command language, a shell level kind of subcommands, sort of like Git or something like that, where there's lots of subcommands that say "Here's the model, here's the processing I want you to run, I want you to display the stuff in some format." So you have all of these various things.
36:30
The particular data like I gave you there, which I'm not going to go into, says that the optimum cheapest diet is nothing but macaroni and cheese. You probably knew that anyway. You can see certain problems, like it says that you're supposed to buy forty six and two-thirds packages of macaroni and cheese. And when I last looked, Sainsbury's didn't sell that, nor did Tesco. So in fact if you wanted an integer solution, it's pretty easy. You go back to here, and all you would have to do is
37:01
to say right here "integer" and it's done. And if we do the translation into essentially the same representation, it would go into a solver, but the solver has to know how to do integer linear programming, which is a much harder problem, because that's NP-complete. So the model doesn't change except for the addition basically of one word. That's the advantage of having a modeling language like that.
37:31
So AMPL, in spite of the fact that none of you have ever heard of it, has been sort of successful. I would call it a big frog in a very small pond, in some sense. It is taught in university courses though apparently not here -- a total failure of the British educational system. [laughter] But it is taught in Princeton. I didn't know that before I got there. And it's definitely used in industry. There's lots and lots of companies that you have heard of that use AMPL a lot. Major airlines
37:58
use it for crew scheduling for example; and major manufacturing companies use it for figuring out production line stuff, and transportation companies in general use it for getting things from here to there. So it's really used there and it supports this tiny, tiny company where I'm a very inactive part of it. The language started out, as I mentioned, purely declarative. You couldn't say anything except "Here it is, go solve it" but it turned out that wasn't enough for the kinds of things
38:29
that people wanted to do. So what happened is that we had to add to it the trappings of real programming languages, the things that make them Turing complete. So it now has loops and conditionals and function call mechanisms and so on. All of the stuff that you need. The problem is that that stuff was added later, so the syntax is really weird and irregular. And that I think is a general observation about languages. You start with something
38:56
that you think is relatively clean. It has what would be called, I guess Fred Brooks called it "conceptual integrity". And then you start adding stuff to it and you lose that -- whatever cleanliness there might have been originally. And certainly in AMPL I think that the added stuff for loops and conditionals and so on is really quite ugly. I didn't add it, so I can't take any blame for that. The other thing that's kind of interesting just off to the side, and we'll come
39:26
back to it, as a question of success or failure. AMPL is proprietary. It is not open source. If you want it, you have to pay for it. It's what keeps this little tiny company going. We were talking earlier today about what's the role of Open Source and how do companies know what would have happened if some of the things that people did in the early days were open source, or weren't open source, today. I'm guessing that
39:51
AMPL and analogous things survive today as proprietary or closed because it's not worth anybody's effort to just go and build one for fun. Nobody here is going to put the effort into building a replacement for this just as a labor of apply it again. And it really worked, both times. love because it's too much work and so perhaps we're OK.
40:12
But that's a weak reed to stand on and so it's possible, at some point, somebody will come along with something that is better than AMPL or at least equivalent that doesn't cost anything and is supported and maintained. At that point the little tiny company will go out of business. It will have no effect on me so it's OK.
40:37
>> Question from audience: "Couldn't your company support itself through consulting operations, which is what a lot of Open Source companies do?" >> BWK: It think that you could support yourself through consulting operations. I that would be a reasonable alternative. It's tricky and I'm certainly not a business person here, but consulting is kind of a retail operation, whereas selling software like this is closer to being a wholesale operation. And so it's hard to scale up consulting
40:54
kinds of things and maintain even just enough people to do it, let alone to do it well. But that is the model for many open-source kinds of companies. I guess Red Hat would be one of the more visible examples. They provide add-ons that cost money And I guess the sort of 'freemium' model that you see on lots of Web sites has that property too. "We'll give you the basic one; it's fine; anything you want. If you want something good, you have to pay us." And so
41:20
you could imagine doing something like that. So maybe the basic linear programming version of this thing free, for you especially, free. But if you want to do stochastic programming, no way; you've got to pay. That kind of thing. So it could work. As I said, I'm very disconnected from the company although I trade mail with Bob and Dave fairly regularly. I don't know what their plans are for that kind of contingency. It would be interesting to know.
41:47
OK. Thank you. Now, we get to the document preparation part of the talk. Not very much, but I wanted to talk about a couple of things in document preparation. I worked on these kinds of things back in the seventies and the eighties to some extent, and it's part of Dave and I shared interest for many many years, a source of good fun certainly for me and I hope for him as well.
42:14
These are a couple of languages that I want to talk about very briefly, which were I think quite good at their time, but in various ways their time has passed, their ecological niche has disappeared, and so they have languished, is probably the best thing you could say about them. The obvious one is this language called EQN, which I did with Lorinda Cherry. The idea is that if I want to typeset complicated material - mathematical material - how do I do that? The standard document formatting
42:44
tools of the time when we did this didn't have any way to do mathematics. So I had the idea that mathemtics is spoken aloud by mathematicians and others when they turn their back to the audience and scribble things on the board like this, they say "x sub i equals pi". Everybody knows what that means. You don't have to see what they wrote, because the spoken language of mathematics, at least for simple stuff, is completely
43:09
clear. And so the idea was to translate that into formatting commands that would draw the mathematical expressions appropriately. This coincides almost exactly with the invention of the pipe mechanism in Unix, at a time when machines were very, very small with limited capabilities -- the first Unix machine had 64 K bytes of memory. K; not M; not G. 64 Kbytes. So that meant that any individual program was going to be fairly small and you couldn't combine
43:41
a bunch of features into one program because you didn't have room to run it. And so we were forced, I guess, into this idea of using the pipeline, where there was a program to process the mathematical part and it fed stuff into the program that handled ordinary text. And because they were separate programs anyway, you could think of doing a different language where the notation was appropriate, where you could have notation that was sort of the way mathematics is spoken by real
44:05
mathematicians, and others: engineers, scientists, whatever. We did that, and it worked out actually extremely well. The mathematics mode in TeX derives from that. Don Knuth looked at it, said "Ah, OK", and then went off and put his own spin on it to make something that's very much richer, more robust, higher quality output, but fundamentally that same idea, something that you could actually write fairly easily.
44:29
So sometimes resource constraints actually work in your favor. A couple of simple examples of EQN. The interesting thing here -- I talked about notation. Notation is important. This notation is easier than TeX because it doesn't do as much. But this notation has the property that you can teach it to people who have no mathematical or background of any sort. We routinely taught this to typists at Bell Labs, who didn't know any mathematics but they could learn this in
44:59
an hour to produce the level of complexity of mathematical documents that were standard at the Labs at the time. There's no problem of how to teach them that stuff and after a while they taught themselves. The notation is actually pretty easy and straightforward. The implementation of EQN was based on YACC, the parser generator. I assume you've at least heard of YACC if not used it. Another example of a specialized
45:24
language, a language that takes a grammar and converts it into a recognizer for things written in that language. EQN used that. I think EQN would not have come about if I hadn't had YACC available because I couldn't write parsers to save my life. But I can get a program to write a parser for me; that was really good. And so that actually worked out rather well. And it's sort of weird now but if you think -- you put a paper in a conference, the first thing you do is you
45:49
write the paper, put it into PDF, and you send it off to them, right? That's the way it works. That was a totally foreign concept forty-odd years ago. Gee! you did what Dave described -- you got, you know -- there was a typesetter and somebody who did typesetting professionally, and so on. This is the first, and I think probably the only, paper that was ever published in CACM where the typesetting was done by the authors, and not by some compositor, because we wanted to show it off.
46:16
And so we did that. And we made it look pretty much the same way, modulo the fonts not being quite right, the same way as ACM looked. Of course today this is commonplace. I don't think journals work this way, but certainly conference proceedings absolutely do. And so, a new idea at the time. but definitely moribund at this point, is this language called Pic. The other language that I want to talk about also, I think kind of interesting in some ways,
46:44
Dave mentioned the Linotron 202. We had done a lot of interesting work on typesetting using a previous typesetter, a mechanical nightmare called the Graphic Systems Model CAT. And the stuff that we had done, which included Troff, and EQN, and Mike Lesk's TBL program for doing tables, was sufficiently useful -- I mean documents at Bell Labs were being produced by that stuff all the time -- that we were able to convince our management to spend 50,000 U.S. dollars
47:18
in 1977 I guess, to buy this Linotron 202 device, on the grounds that we would then be able to produce even richer documents, things that had pictures in them as well as mathematics and tables. And so to do that, I created this language called Pic, which is basically a language for specifying drawings, line drawings like, think flowcharts or something like organization charts, in terms of textual description of the pictures. So rather than drawing something on the screen with the mouse,
47:52
describe it in words, and a program, Pic, would convert that into Troff commands that would actually draw it. So if you learn a good trick -- pipelines, separate programs, separate language --
48:08
I'm going to give you just an example or two of Pic in action. Here's a really trivial one. Input, process, output -- kind of generic. That's what we do here -- input, process, output... teaching programming whatever. And so the language was meant to make those kinds of things really, really easy, like that, and without having to do anything in the way of arithmetic, it just sort of positioned things at the right size in the right positions. It had more bells and whistles.
48:35
And so here's an example. This is actually from a couple of years ago, three or four years ago, when I actually cared about this. It's an arbitrary picture of voltage over time. OK? And you can see in there an instance of something I talked about before. The first version of Pic didn't have any notion of loops or conditionals. But that's got a loop in it; it's got a 'for' loop. Again... needed it, to be able to do certain kinds of things, gets added,
49:03
with a horrible syntax. So I learned a lesson but not very well. And I seem to have blocked off the rest of it, but you get the idea about that. So there I have it, and there's that nice neat curve, written in Pic. So I could have drawn that thing just as well freehand, or at least an artist could have drawn it just as well freehand with a drawing system, and it would look perfect. But the thing that I wanted this picture for was in fact the next picture, which is
49:30
this one, where I want to show what it means to sample a waveform by saying, you know, "Here's these little vertical places where you sample the value of the waveform", and that lets you reconstruct the waveform. And doing that from the original Pic picture is trivial. Right? I just have to add a conditional in there that says, "Every fourth line, please print it." And that would be very hard if I'd had an artist very carefully create that first curve,
49:55
because then I'd have to pay the artist to go in and very carefully do the vertical lines. And here, with those two pictures, if I change my mind about the frequency or the shape of the curve or anything else, it's a trivial job to modify it. So textual descriptions have a lot of advantages for that. Now something else that I mentioned is this idea of ... machine-generated input for programs. So Pic is a language which lets you draw pictures. There are certain specialized kinds of
50:23
pictures that perhaps you could generate the Pic for. And my colleague Jon Bentley had this idea of "Gee, you know, graphs are a very specialized form of picture." All right? So let's design a language that takes data of whatever form, and converts it into neatly drawn graphs. And how will we do that? We'll convert that stuff into Pic, which in turn goes into Troff. So if an idea is good, making it recursive makes it better.
50:50
That's what we did with that. That is kind of a mediocre graph, but you get the idea of how this worked: machine-generated input. So if a language is useful, then you can generate it by program. So, as I say, these are two languages that -- if you count Grap, three -- that were I think quite useful in their time, but their time has passed. And the reason that their time has passed is that the Troff time has sort of passed.
51:21
Apologies to Dave, who still does even more on it than anybody else, I guess. It's sort of passed. It was actually very very good for lots of things, but it's been pretty much superseded in most people's eyes by TeX or LaTeX or something of that sort. And some of the good ideas are preserved, and some of the good ideas are kind of disappearing, unfortunately. But that's a reason why languages fail sometimes, is that their niche, their place in the ecology where they fit, has gone away.
51:53
So, why do languages succeed? Well, I've harped on notation a fair amount. I think the big deal is the notation -- it really has to solve a problem that people care about in a way that makes it easy enough to write the code. If it doesn't do that, then it isn't going to fly at all, in some sense. I think it's helpful to be what I would call 'culturally compatible'. Languages based on C, where the surface syntax sort of looks like C, have done pretty well
52:18
over the years, if you think of C++, and Java, and Javascript, and I suppose arguably Perl, and certainly AWK... all of those things have taken that surface syntax so it's familiar, mutated it a bit, but, you know, fundamentally it's the same thing. It's not like you have to follow it. So Python is different, and Ruby's kind of a weird mishmash, I guess, etc... we -- go where you want. So it's, I think -- all of those things help a language to succeed. If it's familiar enough,
52:44
then you're probably willing to try it and see if you can get over some kind of hump. And the other thing is that it has to be environmentally compatible as well. You have -- you don't want to have to buy into too much of a new way of doing business. One of the reasons why C++ succeeded, in spite of its complexities and other properties, was that it fit absolutely naturally into the C ecosystem. It ran on Unix,
53:11
libraries were compatible, the source code looked very similar at one end of the usage spectrum, so it was a conscious engineering choice by Bjarne Stroustrup to make it as close to C as he could, so that it would propagate that way; you didn't have to buy into a bunch of new ways of doing things. And the comparison between that and, say, SML (Standard ML) at the time, which is absolutely concurrent
53:37
in time, was that that required very much more buy-in, more, you know, stuff you had to import into the environment. So leaving aside even the unfamiliarity of the language, it was just too hard to use, in some sense. This question of open source and -- versus proprietary... I don't know. You could argue that either way, but I think today languages which are not open source are going to have real trouble,
54:00
for the most part, just because when it's open source, people are willing to invest something in it, because they know that it will -- they don't have -- well, first, they don't have to pay for it in the first place, and whatever they do will help improve it overall. So I think for the most part, open source is an important aspect of this. And then these sort of very amorphous things. What's the competition?
54:24
So the competition for C back in the early to mid 1970s as a system programming language was... Pascal?! People seriously suggested Pascal as a system programming language. Pascal had lots of good things about it, but... system programming? It's a joke. You couldn't possibly do it in that. So that was an example. Oh, and the other competition for C, at sort of the other end of that little spectrum, was languages that were typeless, like BCPL, which was really elegant,
54:55
but typeless language: didn't match the architecture of the machines at the time. So, weak competition. Think about Javascript, versus Java, on browsers. Java got there first, but wasn't the right kind of competition. Javascript did better, because it was enormously easier for people to send Javascript source code to a browser, rather than having to compile something and then send the compiled result to the browser.
55:27
So Java never took off, really, on the browser side of things; Javascript always won there. It helps to have good luck. C had good luck in timing. It came along with minicomputers. Then it got a new burst of life with workstations; think of the Sun workstations. And then it got another burst with the PC. And then it got another burst with embedded systems. So C has kind of been surfing the wave for a long time, getting that fresh wind each time. Think of Objective C, if you can. Objective C...
56:07
kind of a C++, not look-alike, that's the wrong characterization -- but, you know, attempting to compete in the same space, pretty much unused. And then it was picked up to run on the NeXT Workstation, by Steve Jobs, and then carried into Apple, where it was used for a very long time (and still is, obviously) to create software for MacOSX, and, to some extent, iOS. What's going to happen when Swift comes along? I think Swift is probably... you can correct me,
56:33
I think probably going to be the death of Objective C over the next -- pick a time period -- 5 or 10 years. I don't know for sure, but I will guess that might be the case. But the success of Objective C, and then, was luck, you know, just being in the right place at the right time perhaps, and then I think its death will be its niche probably goes away. And I don't know how any of this stuff will work on new languages, like Rust, or Go, or Dart, which I mentioned earlier.
57:06
And then why do languages fail? Well, I already told you some of the answers. The domain disappears. That's what happened to a lot of the Troff-related tools. Just -- it's gone away. The engineering might be bad: languages are too big, or too complicated. Algol-68 is a wonderful example produced in the United Kingdom. PL/1 is a wonderful example produced in the United States. Too big, too slow, too late, too complicated -- all kinds of things like that.
57:32
What about Perl 6? We would call that "too late"? We would probably call that too late. I think Perl's time has passed, because it's stopped evolving in some sense, and Perl 6 is never going to arrive, really -- and so Perl's, in some sense, missed a boat. Permanently, I don't know; it's still a very useful language, but that will be interesting to see what happens. How about C++? Too big? Awfully big? Awfully complicated? Is it going to go away?
58:05
Probably not because the embedded base. There's an awful lot of C++ code out there, and people are writing a fair amount of new stuff. But you wonder whether it's passed some threshold of complexity that's beyond mortals, at least ordinary people. And then there's questions of the sort of philosophical choices. Some languages take ideology a little too far. to functional languages in some sense. A lot of people -- me, in particular --
58:38
do not think in the sort of mathematically rigorous and abstract way that you need to be a functional programmer. So, who knows. Lots of different reasons why languages potentially fail. Now I think very few languages ever disappear totally. So that's why I said "fail to thrive". They don't disappear; it's just that they don't grow. And their user population shrinks. Let me close with an observation from Alan Perlis, which is absolutely true.
59:07
I don't care what your language is; you can write lousy code - which is, I guess, another way of what he said. But what it suggests to me is that there is still lots and lots and lots of room for going off and inventing, creating new languages that in some sense try to combine the best stuff from what went before, but have some new take on it that makes it interesting and better in some sort of way. The "too mathematical" brush, you could, I suppose, arguably apply
59:28
So probably if you want to do this, the place to start is with domain-specific languages, rather than big general-purpose ones. Don't build the next C++, but build the next -- I don't know, regular expressions -- you know, something small. And you might discover that it's an enormous amount of fun, and that you might have an effect on things, and it's certainly very satisfying. So, anyway, that's all I wanted to say. Thank you again very much for your hospitality
59:52
and your attention. I really appreciate it. [applause]
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat