>>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 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 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. 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, 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] 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 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 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 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. 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 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 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. 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 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 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 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 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. 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 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 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 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 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 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 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 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] 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 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”. 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 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
scripting language, I would say, and certainly on the Web ever since. And I don’t know what’s gonna
happen again 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 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 right into the language, in some sense, as
they definitely are in AWK and in Perl, and I think
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 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 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 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 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 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 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. 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. 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 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 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 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 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. 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 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 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. 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. 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 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 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 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 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. 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 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 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 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 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, 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 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 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 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 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 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] 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: “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 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. 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 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 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 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 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. 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 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 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 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. 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 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 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 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 — 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 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: 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. 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. 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. 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. 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 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. 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 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 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 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 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 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. 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.>>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 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 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. 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. 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 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 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 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 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. 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 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 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 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. 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
The other language that I want to talk about also,
I think kind of interesting in some ways, 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 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, 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 — 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. 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, 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 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, 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 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. 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. 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. 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 over the years, if you think of C++, and Java,
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, 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, 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 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, 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? 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, but typeless language: didn’t match the architecture
and then send the compiled result to the browser. So Java never took off, really, on the browser side
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… 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, 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. 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. 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? 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 — 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. 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 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 and your attention. I really appreciate it.