>> 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 
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
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 
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
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 
called Pic.
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,
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,
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
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.
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...
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.
[applause]
