Andrej Bauer对于语言设计的观点
3 views
Skip to first unread message
zhang3
Apr 19, 2009, 5:05:22 AM4/19/09
to Zero programming language
Andrej Bauer对于语言设计的观点
作者 Jonathan Allen译者 张逸 发布于 2009年4月18日 上午8时5分
社区
.NET
主题
编程
Andrej Bauer发表了一篇名为《编程语言的设计》的文章。他基于一个简单的前提：“程序员是这样的一群人，他们健忘，懒惰，会犯所有可能的错
误。”
因此，设计者的任务就是让编程语言能够弥补这些不足。语言不能太复杂，否则程序员总是会一知半解。一门语言应该提供众多有用的库，以此来纵容程
序员的懒惰，并让语言可以直接而简洁地表达其思想。语言必须支持结构优雅的源代码，否则程序员就会滥用复制-粘贴的方法。语言必须竭尽所能地捕获编程错
误，尤其是那些司空见惯、频繁出现的错误。一旦找到错误，它必须指出错误的真实原因，最好是提供人们能够理解的错误消息。
运用该理论的第一部分就是避免因为未知而出现的错误。他写道：
这一原则告诉我们，允许无效引用的主意实在糟糕，因为程序员会创建这些无效引用。的确，对于最近设计的语言如Java和Python，就不允许
你做这种“盲人骑瞎马”的危险事情，例如：
int *p = (int *)0xabcdef;
遗憾的是，许多设计者并没有认识到空指针或空对象带来的危害。
.NET编程特别遵循了这一原则。它不仅提供了Java所拥有的“空引用异常”，而且还提供了Nullable值类型以解决通用的问题。还有一种新方法
是代码契约，但目前该技术还不成熟，没有形成产品。
Andrej在比较了强类型对象与基于列表的数据结构后，又转向对变量定义的讨论。他就这一问题提出的一些有趣的观点，可以应用在.NET编程中。
如果你仔细观察变量通常是如何使用的，就会发现几种独特的用法：
* 通常对变量的赋值只有一次，并被当作不变的对象
* 循环或列表中的变量包括了列表或对象集合的所有元素
* 变量存储了当前状态，并且真正是可变的
循环计数器应该是可变的吗？我不这样认为。在循环体中改变循环计数器的代码会让人感到迷惑，也容易犯错。如果你希望操作计数器，可以使用
while循环来代替。因此，在以上三种情形中，有两种情形我们认为是不变的，但目前流行的编程语言却只为我们提供了变量。这太愚蠢了。我们设计的语言
在默认情况下应该是不变的值。如果程序员需要一个可变的值，可以显式地指定。
在C#或VB中可以这样吗？当然可以，而且并不难。
对于只赋值一次的变量，我们可以 考虑使用现有的类型推断功能。在C#中，可以编写“def x = ...”，而不是“var x = ...”。或
者我们也可以简单地使用现有的关键字“const”。这也完全符合VB的所谓“做我所思，而非我言（do what I mean, not
what I say）”的哲学，如早绑定与迟绑定。重要的是关键字足够简短；如果使用“readonly”这样较长的关键字，开发人员可能拒绝使
用。
第二种情形更简单。只要循环变量发生了改变，就会弹出编译器的警告信息。
对于最后一种情形，使用正常可变变量的情形应该会越来越少见。当然不会完全禁止，但除非真正需要就不要使用。
至于编译时检查与运行时检查，以及未定义的标识符，实际上并不适用于主流的.NET程序员。但是，如果你正在考虑使用IronPython或
IronRuby，那么你最好还是了解一下它们可能引发的一些问题。
总之，Andrej Bauer发表的《编程语言的设计》一文，很好地介绍了下一代语言应该致力于解决的各种问题。
查看英文原文：Andrej Bauer on Language Design
On programming language design
Filed under: General, Programming, Tutorial — Andrej Bauer @ 18:29
In a recent post I claimed that Python’s lambda construct is broken.
This attracted some angry responses by people who thought I was
confused about how Python works. Luckily there were also many useful
responses from which I learnt. This post is a response to comment 27,
which asks me to say more about my calling certain design decisions in
Python crazy.
Language design is like architecture. The architect is bound by the
rules of nature, he has to take into account the properties of the
building materials, and he must never forget the purpose that the
building will serve. Likewise, the designer of a programming language
is bound by the theorems of computability theory, he must take into
account the properties of the underlying hardware, and he must never
forget that the language is used by programmers.
When I teach the theory of programming languages, I tell my students
that there is a design principle from which almost everything else
follows:
“Programmers are just humans: forgetful, lazy, and they make every
mistake imaginable.”
Therefore, it is the task of the designer to make a programming
language which counters these deficiencies. A language must not be too
complex, lest the programmer forget half of it. A language must
support the programmer’s laziness by providing lots of useful
libraries, and by making it possible to express ideas directly and
succinctly. The language must allow good organization of source code,
otherwise the programmer will use the copy-paste method. The language
must try really hard to catch programming mistakes, especially the
mundane ones that happen to everyone all the time. When it finds a
mistake, it must point to the true reason for it, preferably with an
error message that humans understand.
You will notice that so far I have not said a word about efficiency.
If this were the year 1972 we would talk about efficiency first and
forget about the programmers, because 37 years ago hardware and
processing time were the scarcest resources. Today we live in
different times when the most expensive resource is development time.
In 1972 it was a good design decision to implement arrays in C so that
they did not carry with them information about their lengths (save a
couple of bytes on each array), it was a good decision not to check
for out-of-bounds errors in array indexing (save a couple of CPU
cycles), and it was a good decision not to have garbage collection (it
didn’t work well anyhow). From today’s point of view all these
decisions were horrible mistakes. Buffer overflows, which are a
consequence of missing out-of-bounds checks, cost the industry huge
amounts of money every year, while lack of automated garbage
collection results in memory leaks that cause programs to be unstable.
Of course, even today C might be just the right tool for your specific
task. I am not saying that memory efficiency and speed are not
important. They are not as important as they used to be. The first
objective in a programming language design today should be
friendliness to programmers. A lot is known about how to write an
optimizing compiler and how to generate efficient code, so usually the
design of the language does not prevent generation of efficient
compiled or interpreted code.
People do not make bad design decisions because they are evil or
stupid. They make them because they judge that the advantages of the
decision outweigh the disadvantages. What they often do not see is
that they could have achieved the same advantages in a different way,
without introducing the disadvantages. Therefore, it is very important
to get the order right: first make sure the design avoids the
disadvantages, then think about how to get the advantages back.
Let us now apply these principles to several examples.
Undefined values (NULL, null, undef, None)
Suppose we want a language with references (pointers in C). The
principle tells us that it is a bad idea to allow invalid references
because programmers will create them. Indeed, most recently designed
languages, say Java and Python, do not allow you to write obviously
risky things, such as
int *p = (int *)0xabcdef;
Unfortunately, many designers have still not learnt that the special
NULL pointer or null object is an equally bad idea. Python’s None,
perl’s undef, and SQL’s NULL all fall in the same category. I can hear
you list lots of advantages of having these. But stick to the
principle: NULL is wrong because it causes horrible and tricky
mistakes which appear even after the program was tested thoroughly.
You cannot introduce NULL into the language and tell the programmer to
be careful about it. The programmer is not capable of being careful!
There is plenty of evidence to support this sad fact.
Therefore NULL, null, None and undef must go. I shall collectively
denote these with Python’s None. Of course, if we take away None, we
must put something else back in. To see what is needed, consider the
fact that None is intended as a special constant that signifies
“missing value”. Problems occur when a given value could be either
“proper” or “missing” and the programmer forgets to consider the case
of missing value. The solution is to design the language in such a way
that the programmer is always forced to consider both possibilities.
For example, Haskell does this with the datatype Maybe, which has two
kinds of values:
* Nothing, meaning “missing value”
* Just x, meaning “the value is x“
The only way to use such a value in Haskell is to consider both cases,
otherwise the compiler complains. The language is forcing the
programmer to do the right thing. Is this annoying? You will probably
feel annoyed if you are used to ugly hacks with None, but a bit of
experience will quickly convince you that the advantages easily
outweigh your tendency for laziness. By the way, Haskell actually
supports your laziness. Once you tell it that the type of a value is
Maybe, it will find for you all the places where you need to be
careful about Nothing. C, Java, Python, and perl stay silent and let
you suffer through your own mistaken uses of NULL’s, null’s, None’s,
and undef’s.
Other languages that let you have the data type like Haskell’s Maybe
are ML and Ocaml because they have sum types. Pascal, Modula-2 and C
have broken sum types because they require the programmer to handle
the tag by hand.
Everything is an object (or list, or array)
Many languages are advertised as “simple” because in them everything
is expressed with just a couple of basic concepts. Lisp and scheme
programmers proudly represent all sorts of data with conses and lists.
Fortran programmers implement linked lists and trees with arrays. In
Java and Python “everything is an object”, more or less.
It is good to have a simple language, but it is not good to sacrifice
its expressiveness to the point where most of the time the programmer
has to encode the concepts that he really needs indirectly with those
available in the language. Programmers cannot do such things reliably,
and the compiler cannot help them with the task because it does not
know what is in programmer’s head.
Let us look at a typical example in scheme. Suppose we would like to
represent binary trees in which the nodes are labeled with integers.
In scheme we might do this by representing the empty tree as (), and
use a three-element list (k l r) to represent a tree whose root is
labeled by k, the left subtree is l, and the right subtree is r. A
quick search on Google shows that this is a popular way of
implementing trees in scheme. It’s simple, it’s cool, it’s easy to
explain to the students, but scheme will have no idea whatsoever what
you’re doing. There are a number of trivial mistakes which can be made
with such a representation, and scheme won’t detect them (at best you
will get a runtime error): you might write (l k r) instead of (k l r),
you might mistakenly pass a four-element list to a function expecting
a tree, you might mistakenly think that the integer 42 is a valid
representation of the tree (42 () ()), you might mistakenly try to
compute the left subtree of the empty tree, etc. And remember, the
programmer will make all these mistakes.
With objects the situation is somewhat better. In Java we would define
a class Tree with three attributes root, left, and right. It will be
impossible to build a tree with a missing attribute, or too many
attributes. But we will hit another problem: how to represent the
empty tree? There are several choices none of which is ideal:
1. the empty tree is null: this is the worst solution, as any Java
programmer knows
2. we define a class Tree and subclasses EmptyTree and NodeTree
represent the two different kinds of tree
3. we add a fourth attribute empty of type boolean which tells us
whether the tree is empty
There are probably other options. The first solution is horrible, as
every Java programmer knows, because it leads to many
NullPointerExceptions. The second solution is probably the most
“object-orientedly correct” but people find it impractical, as it
spreads code around in two classes. When I taught java I lectured the
third solution, but that one has the big disadvantage that the
programmer is responsible for checking every time whether a tree is
empty or not.
A decent programming language should help with the following common
problems regarding binary trees:
1. Prevent the construction of an invalid tree, such as one with
missing parts, or dangling pointers.
2. Prevent at compile time access to a component which is not
there. For example, the compiler should detect the fact that the
programmer is trying to access the left subtree of the empty tree.
3. Make sure the programmer never forgets to consider both
possibilities–the empty tree and the non-empty tree.
The above scheme representation does not help with the first problem.
A C implementation with pointers would allow dangling pointers. An
object-oriented solution typically won’t help with the second and the
third problems.
You might wonder what it is that I want. The answer is that the
programming language should have built-in inductive data types,
because that’s what binary trees are. In Haskell, which has inductive
data types, trees are defined directly in terms of their structure:
data Tree = Empty | Node Int Tree Tree
This expresses the definition of trees directly: a tree is either
empty or a node composed of an integer and two trees. Haskell will be
able to catch all the common problems listed above. Other languages
supporting this sort of definition are ML, Ocaml, F#, and
interestingly Visual Prolog (I am told by Wikipedia).
We might ask for more. Suppose we wanted to implement binary search
trees. Then we would require that the left subtree only contains nodes
that are smaller than the root, and the right subtree only nodes that
are larger than the root. Can a programming language be designed so
that this property is guaranteed? Yes, for example the compiler could
insert suitable checks into the code so that anomalies are detected
during execution as soon as they occur. This might be nice for
debugging purposes, but what is production code supposed to do if it
discovers an anomalous data structure during its execution? Ignore it?
Raise an exception? It is much more useful to know before the program
is run that the data structure will never be corrupted. Here we hit
against a law of nature: there is no algorithm that would analyze an
arbitrary piece of code and determine whether it will only produce
valid search trees. It is a fact of life. If you really want to check
that your programs are correct you will have to help the compiler.
There are excellent tools for doing that, such as Coq and Agda–have a
look to see how programmers might develop their code in the future.
Confusing definitions and variables
A definition binds an identifier to a particular fixed value. A
variable or a mutable value is a memory location which holds a value
that can be read and changed. These two notions should not be
confused. Unfortunately, traditional programming languages only
provide variables, so many programmers don’t even understand what
definitions are. Java tries to fix this with the final declaration,
and C++ with the const declaration, but these are not used by
programmers as much as they could be (which is a typical sign of
dubious design decisions).
Using variables instead of definitions is wrong for a number of
reasons. First, if the compiler knows which identifiers are bound to
immutable values it can optimize the code better. It can, for example,
decide to store the value in a register, or to keep around several
copies without worrying about synchronization between them (think
threaded applications). Second, if we allow the programmer to change a
value which is supposed to be constant, then he will do so.
If you observe how variables are typically used, you will see several
distinct uses:
* often a variable is only assigned to once and is used as an
(immutable) definition
* a variable in a loop or list comprehension ranges over the
elements of a list, or a collection of objects
* a variable stores the current state and is genuinely mutable
Should loop counters be mutable? I think not. Code that changes the
loop counter in the body of the loop is confusing and error prone. If
you want to fiddle with counters, use the while loop instead. So in
two out of three cases we want our variables to be immutable, but the
popular programming languages only give us variables. That’s silly. We
should design the language so that the default case is an immutable
value. If the programmer wants a mutable value, he should say so
explicitly. This is just the opposite of what Java and C++ do. An
example of a language that is designed this way is ML and ocaml. In
Haskell you have to jump through hoops to get mutable values (now I am
going to hear it from a monad aficionado, please spare me an
unnecessary burst of anger).
Out of scope variables
I thought I would not have to explain why undefined identifiers are a
bad a idea, but the reader in comment 27 explicitly asked about this.
If a programmer refers to an undefined name then an error should be
reported. Concretely, I claimed that Python should complain about the
following definition:
def f(n): return i + n
What is i? Pythonists will quickly point out that i will be defined
later, and how deferred definitions are useful because they allows us
to define mutually recursive functions. Indeed, Java and Haskell also
accept mutually recursive definitions. But unlike Python they make
sure that nothing is missing at the time of definition, whereas Python
will only complain when the above function f is used. To be honest,
Python kindly displays the correct error message showing that the
trouble is with the definition of f. But why should this be a runtime
error when the mistake can easily be detected at compile time?
Actually, this question leads to a more general question, which I
consider next.
When should mistakes be discovered?
Should programming bugs be discovered by the programmer or by the
user? The answer seems pretty clear. Therefore, a language should be
designed so that as many programming errors as possible are discovered
early on, that is before the program is sent to the user. In fact, in
order to speed up development (remember that the development time is
expensive) the programmer should be told about errors without having
to run the program and directing its execution to the place where the
latest code change actually gets executed.
This philosophy leads to the design of statically checked languages. A
typical feature of such a language is that all the types are known at
compile time. In contrast, a dynamically typed languages checks the
types during runtime. Java, Haskell and ocaml are of the former kind,
scheme, javascript and Python of the latter.
There are situations in which a statically checked language is better,
for example if you’re writing a program that will control a laser
during eye surgery. But there are also situations in which maximum
flexibility is required of a program, for example programs that are
embedded in web pages. The web as we know it would not exist if every
javascript error caused the browser to reject the entire web page (try
finding a page on a major web site that does not have any javascript
errors).
Let me also point out that testing cannot replace good language
design. Testing is very important, but it should be used to discover
problems that cannot be discovered earlier in the development cycle.
I used to think that statically checked languages are better for
teaching because they prevent the students from doing obviously stupid
things. About two years ago I changed my mind. The students learn much
better by doing stupid things than by being told by an oppressive
compiler that their programs are stupid. So this year I switched to
Python. The students are happier, and so am I (because I don’t have to
explain that code must be properly indented). Python does not whine
all the time. Instead it lets them explore the possibilities, and by
discovering which ones crash their programs they seem to understand
better how the machine works.
45 Comments »
1.
This is a nice summary of many popular fallacies in language
design, which many defend to the death against all reason. I would
point out that a commonality here is the absence of sum types in
popular languages. Another is over-emphasis of mutation and state,
ranging from the mutable variables problems you point out up through
piles and piles of object nonsense that makes matters worse and worse
and worse. Just try to implement “delete” from a binary search tree
represented in the contorted “object-oriented style”. It’s appalling
because the class of a node can change from non-empty to empty, but
with everything being a reference the effect is only felt further up
the tree, and then you have to worry about aliasing. It’s a disaster.
Finally, I would suggest heading off the usual nonsensical argument
about static vs dynamic typing by pointing out that dynamic typing is
a mode of use of static typing (so-called dynamic languages pick a
single recursive type and obsess over it for no useful purpose), so it
can hardly be opposed to static typing, much less an alternative to
it. Moreover, every single thing you can do in a so-called dynamic
language can be done directly and easily in a static language—but as
soon as you do, you realize that you really don’t want to do this
after all (but you can, if you’re obsessive about that one true type
that everything must have).
Comment by Robert Harper — April 11, 2009 @ 19:36
2.
“Lisp and scheme programmers proudly represent all sorts of data
with conses and lists”
That is not true. Both Common Lisp and Scheme have arrays; and
Common Lisp even has bit vectors! Depending on your system, is
compiled as efficiently as it would if you used an int or char array
in C — with the advantage that in Common Lisp you declare it as a bit
vector and use bit operators on its elements (in C you have to use
bitwise operations on chars/ints, create masks to select specific
bits, etc).
Also, Common Lisp has structs (see defstruct), which (in SBCL/
CMUCL) is compiled as “contiguous memory location”, just as a C
struct.
Comment by w-g — April 11, 2009 @ 20:59
3.
I don’t know how to respond to this other than to say that
Python’s philosophy doesn’t match yours. As CAR Hoare said:
“I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously no
deficiencies, the other way is to make it so complicated there are no
obvious deficiencies.”
Python definitely encourages the former. To steal a quote from
Perl, does the language give you enough rope to hang yourself with?
Sure. But python is so simple a language that these kinds of stupid
mistakes are usually pretty easy to spot.
Haskell’s designers seem to disagree. Peyton Jones once said
that “any language large enough to be useful must be dauntingly
complex.”
Take the piece of code you post:
def f(n): return i + n
The problem is that based on this piece of code, we *don’t know*
if i is in scope or not. The above code becomes valid if it’s placed
in this context:
def g():
i = 0
def f(n): return i + n
return f
Are there ways to allow this behavior *and* remove the
possibility of stupid mistakes? Sure. But not without adding several
layers of complexity to the language. Does that mean it’s bad? Not
necessarily. But then we go back to the dichotomy: do you encourage
reliable code through simplicity or do you create reliability through
better compiler checks?
I’m of the belief that compiler checks don’t eliminate or even
reduce programmer stupidity. They just make it go deeper by creating
complexity. Have I written my fair share of stupid python code? Sure.
But it’s rare that I ever find myself saying “WTF is this code doing?”
But you obviously view things differently and that’s a good
thing.
Comment by Jason Baker — April 11, 2009 @ 21:19
4.
Jason, I intended that piece of code defining f to be a complete
module. Isn’t that obvious? Otherwise everything I wrote about it does
not make any sense.
Secondly, the claims you and I make are verifiable. There must
be research out there measuring whether “simple” languages have fewer
bugs, and whether static typing reduces programming errors. It would
seem tricky however to measure such things reliably.
Comment by Andrej Bauer — April 11, 2009 @ 21:26
5.
> Make sure the programmer never forgets to consider both
possibilities–the empty tree and the non-empty tree.
I’m not sure about this one. I often have to put error “won’t
reach this” in match statements in ML.
Comment by Jules — April 11, 2009 @ 21:45
6.
[...] Andrej Bauer added an interesting post today on
Mathematics and Computation » On programming language designHere’s a
small readingThe architect is bound by the rules of nature, he has to
take into account the properties of the building materials, and he
must never forget the purpose that the building will serve. … I can
hear you list lots of advantages of having these. But stick to the
principle: NULL is wrong because it causes horrible and tricky
mistakes which appear even after the program was tested thoroughly.
You cannot introduce NULL into the language and tell the programmer to
be careful … [...]
Pingback by Internet Marketing Email » Blog Archive »
Mathematics and Computation » On programming language design — April
11, 2009 @ 22:24
7.
[...] View original post here: Mathematics and Computation » On
programming language design [...]
Pingback by Mathematics and Computation » On programming
language design — April 12, 2009 @ 00:15
8.
Let’s say I agree that programmers are stupid: Then perhaps we
should educate them instead of giving them blunt tools that can’t hurt
them.
Now to change the subject. As any good Java programmer will tell
you, representing the empty tree by null is the best solution. The
only disadvantage you gave, that NullPointerException will happen, is
simply not a pragmatic reason. For if it happens, it will happen
quickly and will make you think harder about the code. The two sub-
classes solution sucks for the reason you mentioned: It makes the code
hard to read, because it’s spread out. The boolean solution is by far
the worst: Just as in the null-solution you are responsible to check
for empty trees with no help from the compiler, when you get an
exception it doesn’t directly translate to “you forgot the empty tree
case”, and you occupy extra memory. (Yes, using extra memory is bad,
especially when you don’t gain anything.) There is absolutely no
excuse for using this solution, let alone teach it.
Most people find it easier to think about a stateful world and
some find it easier to think about a stateless world. Of course, at
some deep level both formalisms are equivalent. It’s sad to see time
and again people from one camp claiming that the others are ignorants,
instead of acknowledging that different people have different styles
of thinking.
Comment by Radu Grigore — April 12, 2009 @ 00:16
9.
Jules: I’ve realized that dummy “can’t happen” matching (with
assert false) is
becoming rare in my OCaml code, as I tend to construct the data
types in ways
that allow exhaustive matching without impossible branches, for
instance by
using polymorphic variants instead of regular sum types or
encodings like ['a
* 'a list] for non-empty lists.
At any rate, even if you do end up using “impossible” matches,
at least the
type system forces you to be explicit and to take a minute to
think about
whether the branch can be reached or not.
Comment by mfp — April 12, 2009 @ 00:37
10.
Reply to Radu: You misunderstand me. I am not saying that
programmers are stupid. I am saying they make mistakes because they
are humans. They can’t help it, no matter how smart they are. Most
mistakes are really, really dumb, like mismatching the parenthesis,
writing pritn insteand of print, forgetting to initialize a variable,
etc. This has nothing to do with intelligence. It’s about how our
brains work. We’re not robots.
You are suggesting that the programmer should think about his
program hard. Yes, he should be thinking hard how to make his program
good, not how to get rid of silly errors. That is just a waste of
energy.
The tools I am suggesting are far from being blunt. Programming
languages such as ML and Haskell are way, way more expressive than
Java or Python.
Comment by Andrej Bauer — April 12, 2009 @ 01:18
11.
[...] Web pages need to be dynamic?Posted on Saturday, April 11,
2009 at 9:41 PM. Towards the end of his “On programming language
design” article, which does a very good job of pointing out the
benefits and necessity of statically-typed [...]
Pingback by Pinderkent: Do programming languages for code
embedded in Web pages need to be dynamic? — April 12, 2009 @ 02:16
12.
Arrgh, all this brainy talk is makin’ me head spin. Get back to
swabbin’ the deck, matey, unless you’d rather be hangin’ from the
mast.
Comment by Captain Morgan — April 12, 2009 @ 05:07
13.
I’m not sure if this was covered in the comments to the closure
post, but here’s the main issue:
Suppose you have a bunch of inline code that you want to turn
into a zero-arg closure. Suppose that code modifies some variable i.
If the closure takes the value of i at definition time and turns it
into a local variable, the code works differently when you create the
closure than when you inline it.
This adds an extra layer of confusion since macros and closures
would behave differently. You can’t apply the logic of a pure
functional language to an imperative stateful one. The example above
is a reasonably common one, that comes up if you realize you have the
same bit of code in both branches of an if.
Comment by chris — April 12, 2009 @ 06:06
14.
Reply to Radu:
You are dead-wrong about using nulls for empty trees, or any
other collection for that matter. You can’t even call myTree.count()
safely if you have a null. That’s why most guidelines say to always
return empty collections instead.
Comment by Jonathan Allen — April 12, 2009 @ 06:14
15.
> But then we go back to the dichotomy: do you encourage
reliable code through simplicity or do you create reliability through
better compiler checks?
Why not both?
Visual Basic will give you a compiler warning if you try to use
a loop variable in a lambda. If you still want to do it you can, but
at least you are warned.
Comment by Jonathan Allen — April 12, 2009 @ 06:17
16.
Thanks for a concise but thorough summary of important issues.
Regarding your example of binary search trees, there are some
interesting recent alternatives to Coq and Agda for enforcing these
sorts of constraints. I am thinking specifically of the Sage language
from Cormac Flanagan and his students at UC Santa Cruz (also Steve
Freund at Williams); I heard about it from Aaron Tomb during a recent
tech talk at Galois. In their tech report Sage: Unified Hybrid Checking
for First-Class Types, General Refinement Types, and Dynamic, they in
fact use binary search trees as a motivating example (quoting from
their Section 2.1):
Note that Sage supports dependent function types, and so the
type of the third argument to search can depend on the values of the
first and second arguments.
…
The Sage compiler uses an automatic theorem prover to
statically verify that the specified ordering invariants on binary
search trees are satisfied by these two functions — no run-time
checking is required.
…
This precisely-typed BST implementation can inter-operate
cleanly with dynamically-typed client code, while still preserving the
ordering invariant on BSTs.
Sage constitutes an interesting design which manages to
accommodate dependent types in a statically-typed setting; I’d be
interested in hearing your opinion of it.
Oh, and a PS to Bob Harper: the “one true type that everything
must have”, is that the One True Type that in the Darkness Binds Them?
(at run-time, presumably :) )
Comment by Fritz Ruehr — April 12, 2009 @ 06:57
17.
Lists and arrays are objects.
Comment by Eric Florenzano — April 12, 2009 @ 07:40
18.
“Programmers are just humans: forgetful, lazy, and make every
mistake imaginable. Therefore, it is the task of the designer to make
a programming language which counters these deficiencies.”
Wait, what? Aren’t programming language designers also human?
Shouldn’t one of the designer’s top priorities, then, be to make
sure the programmer can work around possible deficiencies of the
language design?
Comment by Ken — April 12, 2009 @ 07:44
19.
Have you looked at Scala? It addresses most of the issues you
bring up. While it does have null (for compatibility with Java), the
idiomatic alternative is the Option type, which is the equivalent to
Haskell’s Maybe. Case classes and pattern matching are a statically
checked way to define and operate on datatypes. Definitions (vals) and
variables (vars) are syntactic equals, but convention dictates that
vals are preferred over vars. Scala’s lambdas aren’t broken in the way
that Python’s are. There’s even a special syntax for lambdas. For-
comprehensions are like Python’s list comprehensions but on steroids
(closer in expressiveness to Haskell’s do-notation).
Scala is statically checked, it has a powerful type system, ok
type inference, and it’s fully compatible with Java. It basically
takes Java, drags it halfway to Haskell, halfway to ML, and ends up
looking a little like Python.
Comment by Jorge Ortiz — April 12, 2009 @ 08:13
20.
Reply to 15: This sounds like a joke and I am not really sure
what you want. Perhaps the fact that a general purpose language is
Turing complete?
Comment by Andrej Bauer — April 12, 2009 @ 09:07
21.
http://www.reddit.com/r/programming/comments/8brly/on_programming_language_design/c08szul
Comment by smallpaul — April 12, 2009 @ 09:08
22.
Jonathan Allen: what do the “left” and “right” methods return
for a Java EmptyCollection instance? By default they will return NULL
with Java inheritance, right? So what do you prefer? To have them
return? an exception? Another EmptyCollection? An infinite tree of
EmptyCollections?
Comment by smallpaul — April 12, 2009 @ 09:12
23.
Perhaps the following analogy is a good response to comment 8 by
Radu:
Mathematicians are certainly intelligent enough to calculate
128+395 in their head or on paper. But it will be boring, error-prone
and tedious. Fortunately, mathematicians have recognized that this
task can be performed by a machine and they can now spend their time
with more interesting things.
Similarly, programmers are certainly intelligent enough to
carefully handle null pointers, but why bother? Let the language and
compiler figure it out.
Comment by Heinrich Apfelmus — April 12, 2009 @ 09:28
24.
This is a reply to smallpaul, an angry person from Reddit. I
have edited the post to make the idea with trees as subclasses more
precise. Thank you for pointing out the lack of clarity in an
insulting way.
Commenting further on smallpaul’s, uhm, “review” on Reddit
(comment 21): recursion or something equivalent to it (loops, for
example) is necessary in a programming language that is Turing
complete, but NULL’s are not. This is the reason I would not advocate
elimination of recursion. Although I do think it would be beneficial
to separate structural recursion (a.k.a. primitive recursion), which
is guaranteed to terminate, from general recursion. I just don’t know
how to present it in a language without making it annoying.
Comment by Andrej Bauer — April 12, 2009 @ 09:38
25.
> There are probably other options. The first solution is
horrible, as every Java programmer knows, because it leads to many
NullPointerExceptions. The second solution is probably the most
“object-orientedly correct” but people find it impractical, as it
spreads code around in two classes. When I taught java I lectured the
third solution, but that one has the big disadvantage that the
programmer is responsible for checking every time whether a tree is
empty or not.
What code does the EmptyTree class have? If we are emulating
your Haskell example then all of these classes would have data and no
code. Conversely, if we wanted to add code, we’d put it only on the
NodeTree (given that the EmptyTree has no state and serves as simply a
sentinel).
You can use these classes as almost exactly the same as
Haskell’s constructors and the consumer will be forced to cast to the
right subclass (as in Haskell) before they fish out a value or a child
node. The only issue is that the consumer must use instanceof before
the cast rather than doing both in the same expression as Haskell
does. Still, that’s not a huge issue.
> we add a fourth attribute empty of type boolean which tells us
whether the tree is empty
> When I taught java I lectured the third solution, but that one
has the big disadvantage that the programmer is responsible for
checking every time whether a tree is empty or not.
If you use this solution, then what do the “right” and “left”
properties return?
Why is it easier or better to check for “is_empty” than to check
“==null”? As long as the responsibility to check is on the programmer,
what’s the difference?
Comment by smallpaul — April 12, 2009 @ 10:20
26.
“… In fact, in order to speed up development (remember that the
development time is expensive) the programmer should be told about
errors without having to run the program and directing its execution
to the place where the latest code change actually gets executed.”
Are you suggesting that the expense of code written in a
strongly typed language can be reduced by cutting down test coverage?
Well, I hope not. Especially in combination with the classic FUD-”eye
surgery” example.
I’m always dazzled by this kind of argument from static type
advocates. It completely blinds out the nature of decision problems
and creates the illusion that in recent time there was any progress
happening towards a static type checking/static analysis system that
converges “number of compiler errors in the program” and “number of
bugs in the program” in any significant way. As soon as this doesn’t
happen (and imho it will never happen) your test coverage needs to be
high, no matter what language you use.
So if your test coverage needs to be high anyway this degrades
the extra-hassle of a static type checking compiler rather to a matter
of taste than a matter of “extra security”.
Comment by Sebastian Morawietz — April 12, 2009 @ 10:29
27.
Another way to represent empty, say, trees in Java would be to
define an interface CanBeEmpty and derive trees from it. Method IsEmpty
() is obvious and method Empty() would create an empty object (yes, a
cast to the tree would be required; an inconvenience, but resolved at
compile time). This does nor solve the fundamental problem of the
value of an unitialized tree, but will help the programmer to build
trees properly.
Comment by Simon Hawkin — April 12, 2009 @ 10:53
28.
Dear Sebastian: No, I am not suggesting that static typing can
replace testing. And nowhere did I say that. But I also disagree with
you when you say that testing can replace static type checking. How
are you going to perform tests which GUARANTEE that type errors will
not occur, other than by performing complete type checking?
Read my post again and try to understand it in a POSITIVE way
(the incredible amount of hostility and misunderstanding is getting a
bit tiresome). I said it is good to tell the programmer about errors
as early in the development cycle as possible. You cannot possibly
object to that. You say that static typechecking is a hassle. Perhaps
it is. But imagine a complex program which has big startup costs. I
make a very small change in the code (in a way that cannot be easily
tested as a unit). Then I have to run the program just to be told
something is wrong. Then I have to look at the code to discover myself
that I made a trivial mistake. How is that less hassle than having the
compiler immediately refuse my code change?
I write programs in statically and dynamically typed languages
(mostly ocaml and Python), and have pretty good idea about what each
brings. I wonder how many of the angry readers here have active
experience with a wide spectrum of languages, or how many have
bothered to actually implement different kinds of languages. The types
of statically typed languages are not a hassle, they are a blessing.
The dynamic nature of Python is not such a big problem as the
proponents of statically-typed languages would have you think. (For
example, in web development it’s really nice that the changes in the
server code are immediately reflected on the web page–without
recompilation and server restart.) In my opinion, at the end of the
day the quality of the code depends more on the quality of its author
than on the quality of the language he uses. But this does not mean
that the quality of the programming language does not matter.
I teach the theory of programming languages, where I teach both
statically and dynamically typed languages. I do NOT tell my students
that dynamically typed languages are bad. I tell them that no one
language is the solution to all programming tasks. I emphasize the
benfits of static typing (obviously) but I do not belittle other
options. Most of all I want the students to understand the reasoning
behind design decisions. I also teach programming to beginners. Mostly
because of my advocating, this year my department switch from a
statically typed language (Java) to a dynamically typed one (Python).
I belive Python is better for teaching than Java. My limited
experience with teaching ocaml to beginners is not sufficient to say
what happens if you teach them ML or Haskell. I am most definitely not
saying that Haskell is the solution to everything, and my actions
clearly support that claim.
So please stop the religous wars. They are pointless. And one
more thing: when you write your comments be polite, or I will reject
the comment. If you think I said something incredibly stupid, then you
should suspect there is a misunderstanding (either by you, or because
I wrote something in an unclear way, or I made a mistake). You can
always ask politely instead of making insulting claims right off the
bat.
After wading though all the replies, I see several valid points
in the comments. The most interesting so far is: how would you
implement the Maybe datatype (with all its good properties) in a
dynamically typed language? It’s an interesting design question. So
let’s talk about that, can we?
Comment by Andrej Bauer — April 12, 2009 @ 11:08
29.
[...] [...]
Pingback by Posts about Programming from google blogs as of
April 12, 2009 « tryfly.com — April 12, 2009 @ 11:58
30.
Here’s a direct translation to Ruby:
class Maybe
def nothing?
self.class == Nothing
end
def just?
not nothing?
end
end
class Nothing < Maybe
end
class Just < Maybe
attr_accessor :value
def initialize(x)
@value = x
end
end
One of the problems with static typing is that there is no clear
choice for language designers. If you choose dynamic typing you’re
done, and you’re at a local maximum in the design space. If you choose
static typing you have to design the type system very carefully. There
is a whole spectrum between most safety and most flexibility.
Dynamic typing also allows you to solve problems like pickling/
distribution in a more straightforward way.
Comment by Jules — April 12, 2009 @ 13:35
31.
Or this version:
class Maybe
def nothing?
end
def just?
not nothing?
end
end
class Nothing < Maybe
def nothing?
true
end
end
class Just < Maybe
attr_accessor :value
def initialize(x)
@value = x
end
def nothing?
false
end
end
Comment by Jules — April 12, 2009 @ 13:37
32.
The title should be: “On programming language design or why
Haskell is my favorite language”.
And seriously, (left-tree my-tree), (right-tree my-tree), (value
my-tree), (is-empty? my-tree).
Comment by Poouik — April 12, 2009 @ 17:01
33.
I tend to agree with ken.
Your article suggests to me a dillemma. If programmers are human
and fallible, are not the designers who are also human just as capable
of error? If what you seek is the one true language which can properly
detect the intent of the programmer and protect them from their own
mistakes then I would be amazed if you ever discover it.
Instead, wouldn’t a more natural solution be a language which
gives the programmer the ability to modify it to suit the problem
domain? To take you binary tree example, you chose languages which
have primitives that can be used to emulate a solution, but their
implementation wasn’t built to understand those compositions. But what
if there was a language that allowed you to construct a grammar and
even a syntax that would operate on binary trees as you define them?
Such a language already exists and I believe it’s called common
lisp. The advantage of it is that whatever construct or operator or
even syntax that the language designers failed to include can be added
by the programmers as they explore their problem domain.
Comment by j_king — April 12, 2009 @ 17:04
34.
I don’t know Haskell at all, but I’ve always heard that it’s not
trivial to control the memory consumption of a Haskell program. If
this is true, and if I apply your theory that programmer’s are
“forgetful, lazy, and make every mistake imaginable”, isn’t that then
a strong reason not to use Haskell? Of course, if you know what you’re
doing, you probably can write Haskell programs that behave reasonably,
memory-wise. But then, if you know what you’re doing, you can write
very nice programs in C too.
Comment by Freek — April 12, 2009 @ 19:05
35.
It wasn’t and isn’t my intention to be impolite. Sorry, if my
previous comment was perceived this way.
But to be perfectly clear: I read your essay, I understood your
points (I guess) and I thoroughly disagree. Furthermore, the tone your
last two essays are written in at least suggests that you’re familiar
with the concept of dealing some out:
In your paragraph “Undefined values…”, you’re not giving the
creators of SQL, perl and python the benefit of the doubt. They didn’t
learn their lesson that the introduction of nil into a language is a
mistake - period. Others might call this a design decision. A
questionable one in your eyes - maybe, but oh well.
The reference post “Python’s lambda is broken!” is basically a
rant, ending with “What were the implementors of Python thinking?!”.
Considering that, you got many helpful replies pointing out the
different implementations of closures in different languages.
If there is a way to read the complete last paragraph “When
should mistakes be discovered?” other than a dichotomy between
(static==secure) vs. (dynamic==flexible but less secure), tell me how
to. It’s difficult to not resolve the initial question into “In
languages written in dynamic languages, errors are discovered by the
user.”
But towards your question concerning “Maybe”.
A function returning “Maybe Integer” is basically returning a
tuple of a potential return value (type Integer) plus the potential
information that something bad happened. Of course it is absolutely
possible to implement this kind of thing in ruby as Jules pointed out.
But the very concept is already implemented in all major languages as
Exception in the form of begin/rescue in ruby, or x=f(y) or blah() in
perl. But to ask how to enforce error handling up the call stack in a
dynamic language is equivalent to “tell me how to enforce types in a
dynamic language”. You don’t.
This leads us right back to the central question:
Does solidly implemented software that is reasonably well
covered with tests get even more secure by formally enforcing a type
system? After years of software development, starting in Eiffel, Java,
C/C++ and now Ruby, JavaScript, C I have absolutely no reason to
assume this.
Therefore I consider it as a valid question of tastes (which is
the least amount of religiosity I can offer :).
Comment by Sebastian Morawietz — April 12, 2009 @ 19:07
36.
In this essay, the comments and the reddit comments you write, I
hear three different things. I’d like you to please select one of the
following and say which one represents your feelings. I’d also suggest
that if you want to be clear in your writing that you stick to the one
you select in subsequent articles and be clear about it.
The three statements are:
1. I prefer static type checking languages. It’s a personal
preference.
2. Static type checked languages are better. They are always
better.
3. Statically typed checked languages are better for CERTAIN
KINDS OF PROJECTS AND PROGRAMMERS and dynamically typed languages are
better for others.
With each post you shift between those three statements
randomly, and in fact seem to switch around within this single post.
At the beginning you say Python’s design decisions are crazy and short-
sighted. Then by the end you say that you find Python and Javascript
better for certain tasks.
Comment by smallpaul — April 12, 2009 @ 19:40
37.
Reply to Freek (33): Yes, memory consumption in Haskell can be
quite unpredictable. This has always been one of the main criticisms
of functional languages by John Reynolds, a pioneer of programming
language theory.
Reply to smallpaul (35): Statically typed languages are my
personal preference, _especially_ because of the kind of programming
that I do. But I also write programs in dynamic languages and they’re
perfectly ok. In theory statically typed languages should always be a
win, but practice shows that dyamically typed languages fare pretty
well in the real world.
I need to do some real work, so I’ll stop replying now. Feel
free to rant and so on. When I have a bit of time I’ll implement
Python as I would have done it: the constraint is that it has to be a
dynamically typed language with lots of reflection and maximum
flexibility. See you then.
Comment by Andrej Bauer — April 12, 2009 @ 20:11
38.
Hi Andrej,
It seems I’m a little late to the party!
I would like to thank you, sincerely, no smirking, for your
considered reply to my original comment. This is one of the few posts
I have seen that contains, but is not limited to, a discussion of a
good dynamic language versus a good static language.
I have not programmed in OCaml, Haskel, or ML - but I do see
their examples on Rosetta Code which makes comparison easy (for
example: http://www.rosettacode.org/wiki/Y_combinator#OCaml). I
started my interest in Python in the mid 90’s. I have personal
experience of languages changing the way I think about problem solving
after being exposed to the SKILL programming language (a lisp
dialect), but also of how a language must be more ‘complete’ or ‘well
rounded’ before it would be prudent to invest too much time in it.
I think I should spend some time now investigating one of these
functional, type-inferred, languages so I can more meaningfully join
the debate.
I did, welcome the addition of at least a syntax for adding type
information to Python in this post:
http://paddy3118.blogspot.com/2008/11/smearing-static-vs-dynamic-typing.html
But looking back, what I would take from my post was this:
“You would need to think of static/dynamic as a continuum where
instead of having languages bunched at either end, you would have a
smearing out towards the middle.”
- Paddy.
Comment by Paddy3118 — April 12, 2009 @ 21:29
39.
The problem with the def f(n): return i + n is not as
straightforward as you might think, even if this function is the only
thing in a module, because you can do import mymodule; mymodule.i =
10; print mymodule.f(1). Obviously, doing exactly that is silly, but
it hints at the fundamental property of Python objects (be that
classes or modules) that is extremely useful. Of course, it is most
useful with classes because of the existence of standard interception
vectors such as getattr, so one may argue that modules could be made
different, at least requiring all attributes of a module to be
explicitly declared (but allowing redefinition, as it is widely used
way of providing custom handlers, and just plain easy way of quickly
tweaking module behaviour), yet there might be legitimate uses for the
whole functionality (some kind of metaprogramming maybe). Actually I’m
aware of one real case when it is used in the core library:
sys.setdefaultencoding is deleted by site.py during startup,
undoubtedly there are more. So, basically, changing the way it works
would complicate the language (making modules really different from
all other kinds of objects) and violate Python ideology of not
restricting users to do what they want because they could come up with
some wonderful unexpected ways of doing things. And the price is not
so high, considering Python’s primary area of application, that is not
eye surgery.
Comment by Fj — April 12, 2009 @ 23:28
40.
[...] programming language design Andrej Bauer has a very nice
article about language design on his blog, which happens to reflect a
lot of what I believe about [...]
Pingback by On programming language design « Occasionally sane —
April 13, 2009 @ 00:06
41.
[...] and Learning April 12, 2009 Via Michael Feather’s blog:
“On programming language design” I used to think that statically
checked languages are better for teaching because they prevent the
[...]
Pingback by Types and Learning « Günther Noack’s blog — April
13, 2009 @ 12:44
42.
@Johnatan Allen: Of course you would use an empty collection
instead of null! I was talking about how you implement a tree, which
can be used to represent a collection, not about the interface of a
collection. These are very different things.
Comment by Radu Grigore — April 13, 2009 @ 23:13
43.
@Heinrich Apfelmus: I agree. I think that Java should have a non-
null data type, and its absence is one of the things that makes me
prefer Haskell and ML. I’m not sure, though, how is that contradicting
what I said.
Comment by Radu Grigore — April 13, 2009 @ 23:27
44.
@Andrej Bauer: Forgetting that trees can be empty is not a
“silly” mistake in my opinion. YMMV.
Comment by Radu Grigore — April 13, 2009 @ 23:29
45.
Haskell and ML have some really nice features the Maybe type is
one of my favorite constructs too, but these languages will never be
very useful until they have a real tool chain. Anyone who has ever
tried to find a bug in a large unfamiliar Haskell code base will know
what I mean. It is shockingly time consuming because the debugging
tool chain is so primitive and things like dynamic linking only have
experimental support. The reality is that as fun and beautiful as it
is to write in Haskell and as good as the language itself is, it is
just not a terribly useful platform for everyday software development.
The ecosystem around it is not filled with people that are interested
in getting things done.
Comment by Frank — April 18, 2009 @ 10:15
作者 Jonathan Allen译者 张逸 发布于 2009年4月18日 上午8时5分
社区
.NET
主题
编程
Andrej Bauer发表了一篇名为《编程语言的设计》的文章。他基于一个简单的前提：“程序员是这样的一群人，他们健忘，懒惰，会犯所有可能的错
误。”
因此，设计者的任务就是让编程语言能够弥补这些不足。语言不能太复杂，否则程序员总是会一知半解。一门语言应该提供众多有用的库，以此来纵容程
序员的懒惰，并让语言可以直接而简洁地表达其思想。语言必须支持结构优雅的源代码，否则程序员就会滥用复制-粘贴的方法。语言必须竭尽所能地捕获编程错
误，尤其是那些司空见惯、频繁出现的错误。一旦找到错误，它必须指出错误的真实原因，最好是提供人们能够理解的错误消息。
运用该理论的第一部分就是避免因为未知而出现的错误。他写道：
这一原则告诉我们，允许无效引用的主意实在糟糕，因为程序员会创建这些无效引用。的确，对于最近设计的语言如Java和Python，就不允许
你做这种“盲人骑瞎马”的危险事情，例如：
int *p = (int *)0xabcdef;
遗憾的是，许多设计者并没有认识到空指针或空对象带来的危害。
.NET编程特别遵循了这一原则。它不仅提供了Java所拥有的“空引用异常”，而且还提供了Nullable值类型以解决通用的问题。还有一种新方法
是代码契约，但目前该技术还不成熟，没有形成产品。
Andrej在比较了强类型对象与基于列表的数据结构后，又转向对变量定义的讨论。他就这一问题提出的一些有趣的观点，可以应用在.NET编程中。
如果你仔细观察变量通常是如何使用的，就会发现几种独特的用法：
* 通常对变量的赋值只有一次，并被当作不变的对象
* 循环或列表中的变量包括了列表或对象集合的所有元素
* 变量存储了当前状态，并且真正是可变的
循环计数器应该是可变的吗？我不这样认为。在循环体中改变循环计数器的代码会让人感到迷惑，也容易犯错。如果你希望操作计数器，可以使用
while循环来代替。因此，在以上三种情形中，有两种情形我们认为是不变的，但目前流行的编程语言却只为我们提供了变量。这太愚蠢了。我们设计的语言
在默认情况下应该是不变的值。如果程序员需要一个可变的值，可以显式地指定。
在C#或VB中可以这样吗？当然可以，而且并不难。
对于只赋值一次的变量，我们可以 考虑使用现有的类型推断功能。在C#中，可以编写“def x = ...”，而不是“var x = ...”。或
者我们也可以简单地使用现有的关键字“const”。这也完全符合VB的所谓“做我所思，而非我言（do what I mean, not
what I say）”的哲学，如早绑定与迟绑定。重要的是关键字足够简短；如果使用“readonly”这样较长的关键字，开发人员可能拒绝使
用。
第二种情形更简单。只要循环变量发生了改变，就会弹出编译器的警告信息。
对于最后一种情形，使用正常可变变量的情形应该会越来越少见。当然不会完全禁止，但除非真正需要就不要使用。
至于编译时检查与运行时检查，以及未定义的标识符，实际上并不适用于主流的.NET程序员。但是，如果你正在考虑使用IronPython或
IronRuby，那么你最好还是了解一下它们可能引发的一些问题。
总之，Andrej Bauer发表的《编程语言的设计》一文，很好地介绍了下一代语言应该致力于解决的各种问题。
查看英文原文：Andrej Bauer on Language Design
On programming language design
Filed under: General, Programming, Tutorial — Andrej Bauer @ 18:29
In a recent post I claimed that Python’s lambda construct is broken.
This attracted some angry responses by people who thought I was
confused about how Python works. Luckily there were also many useful
responses from which I learnt. This post is a response to comment 27,
which asks me to say more about my calling certain design decisions in
Python crazy.
Language design is like architecture. The architect is bound by the
rules of nature, he has to take into account the properties of the
building materials, and he must never forget the purpose that the
building will serve. Likewise, the designer of a programming language
is bound by the theorems of computability theory, he must take into
account the properties of the underlying hardware, and he must never
forget that the language is used by programmers.
When I teach the theory of programming languages, I tell my students
that there is a design principle from which almost everything else
follows:
“Programmers are just humans: forgetful, lazy, and they make every
mistake imaginable.”
Therefore, it is the task of the designer to make a programming
language which counters these deficiencies. A language must not be too
complex, lest the programmer forget half of it. A language must
support the programmer’s laziness by providing lots of useful
libraries, and by making it possible to express ideas directly and
succinctly. The language must allow good organization of source code,
otherwise the programmer will use the copy-paste method. The language
must try really hard to catch programming mistakes, especially the
mundane ones that happen to everyone all the time. When it finds a
mistake, it must point to the true reason for it, preferably with an
error message that humans understand.
You will notice that so far I have not said a word about efficiency.
If this were the year 1972 we would talk about efficiency first and
forget about the programmers, because 37 years ago hardware and
processing time were the scarcest resources. Today we live in
different times when the most expensive resource is development time.
In 1972 it was a good design decision to implement arrays in C so that
they did not carry with them information about their lengths (save a
couple of bytes on each array), it was a good decision not to check
for out-of-bounds errors in array indexing (save a couple of CPU
cycles), and it was a good decision not to have garbage collection (it
didn’t work well anyhow). From today’s point of view all these
decisions were horrible mistakes. Buffer overflows, which are a
consequence of missing out-of-bounds checks, cost the industry huge
amounts of money every year, while lack of automated garbage
collection results in memory leaks that cause programs to be unstable.
Of course, even today C might be just the right tool for your specific
task. I am not saying that memory efficiency and speed are not
important. They are not as important as they used to be. The first
objective in a programming language design today should be
friendliness to programmers. A lot is known about how to write an
optimizing compiler and how to generate efficient code, so usually the
design of the language does not prevent generation of efficient
compiled or interpreted code.
People do not make bad design decisions because they are evil or
stupid. They make them because they judge that the advantages of the
decision outweigh the disadvantages. What they often do not see is
that they could have achieved the same advantages in a different way,
without introducing the disadvantages. Therefore, it is very important
to get the order right: first make sure the design avoids the
disadvantages, then think about how to get the advantages back.
Let us now apply these principles to several examples.
Undefined values (NULL, null, undef, None)
Suppose we want a language with references (pointers in C). The
principle tells us that it is a bad idea to allow invalid references
because programmers will create them. Indeed, most recently designed
languages, say Java and Python, do not allow you to write obviously
risky things, such as
int *p = (int *)0xabcdef;
Unfortunately, many designers have still not learnt that the special
NULL pointer or null object is an equally bad idea. Python’s None,
perl’s undef, and SQL’s NULL all fall in the same category. I can hear
you list lots of advantages of having these. But stick to the
principle: NULL is wrong because it causes horrible and tricky
mistakes which appear even after the program was tested thoroughly.
You cannot introduce NULL into the language and tell the programmer to
be careful about it. The programmer is not capable of being careful!
There is plenty of evidence to support this sad fact.
Therefore NULL, null, None and undef must go. I shall collectively
denote these with Python’s None. Of course, if we take away None, we
must put something else back in. To see what is needed, consider the
fact that None is intended as a special constant that signifies
“missing value”. Problems occur when a given value could be either
“proper” or “missing” and the programmer forgets to consider the case
of missing value. The solution is to design the language in such a way
that the programmer is always forced to consider both possibilities.
For example, Haskell does this with the datatype Maybe, which has two
kinds of values:
* Nothing, meaning “missing value”
* Just x, meaning “the value is x“
The only way to use such a value in Haskell is to consider both cases,
otherwise the compiler complains. The language is forcing the
programmer to do the right thing. Is this annoying? You will probably
feel annoyed if you are used to ugly hacks with None, but a bit of
experience will quickly convince you that the advantages easily
outweigh your tendency for laziness. By the way, Haskell actually
supports your laziness. Once you tell it that the type of a value is
Maybe, it will find for you all the places where you need to be
careful about Nothing. C, Java, Python, and perl stay silent and let
you suffer through your own mistaken uses of NULL’s, null’s, None’s,
and undef’s.
Other languages that let you have the data type like Haskell’s Maybe
are ML and Ocaml because they have sum types. Pascal, Modula-2 and C
have broken sum types because they require the programmer to handle
the tag by hand.
Everything is an object (or list, or array)
Many languages are advertised as “simple” because in them everything
is expressed with just a couple of basic concepts. Lisp and scheme
programmers proudly represent all sorts of data with conses and lists.
Fortran programmers implement linked lists and trees with arrays. In
Java and Python “everything is an object”, more or less.
It is good to have a simple language, but it is not good to sacrifice
its expressiveness to the point where most of the time the programmer
has to encode the concepts that he really needs indirectly with those
available in the language. Programmers cannot do such things reliably,
and the compiler cannot help them with the task because it does not
know what is in programmer’s head.
Let us look at a typical example in scheme. Suppose we would like to
represent binary trees in which the nodes are labeled with integers.
In scheme we might do this by representing the empty tree as (), and
use a three-element list (k l r) to represent a tree whose root is
labeled by k, the left subtree is l, and the right subtree is r. A
quick search on Google shows that this is a popular way of
implementing trees in scheme. It’s simple, it’s cool, it’s easy to
explain to the students, but scheme will have no idea whatsoever what
you’re doing. There are a number of trivial mistakes which can be made
with such a representation, and scheme won’t detect them (at best you
will get a runtime error): you might write (l k r) instead of (k l r),
you might mistakenly pass a four-element list to a function expecting
a tree, you might mistakenly think that the integer 42 is a valid
representation of the tree (42 () ()), you might mistakenly try to
compute the left subtree of the empty tree, etc. And remember, the
programmer will make all these mistakes.
With objects the situation is somewhat better. In Java we would define
a class Tree with three attributes root, left, and right. It will be
impossible to build a tree with a missing attribute, or too many
attributes. But we will hit another problem: how to represent the
empty tree? There are several choices none of which is ideal:
1. the empty tree is null: this is the worst solution, as any Java
programmer knows
2. we define a class Tree and subclasses EmptyTree and NodeTree
represent the two different kinds of tree
3. we add a fourth attribute empty of type boolean which tells us
whether the tree is empty
There are probably other options. The first solution is horrible, as
every Java programmer knows, because it leads to many
NullPointerExceptions. The second solution is probably the most
“object-orientedly correct” but people find it impractical, as it
spreads code around in two classes. When I taught java I lectured the
third solution, but that one has the big disadvantage that the
programmer is responsible for checking every time whether a tree is
empty or not.
A decent programming language should help with the following common
problems regarding binary trees:
1. Prevent the construction of an invalid tree, such as one with
missing parts, or dangling pointers.
2. Prevent at compile time access to a component which is not
there. For example, the compiler should detect the fact that the
programmer is trying to access the left subtree of the empty tree.
3. Make sure the programmer never forgets to consider both
possibilities–the empty tree and the non-empty tree.
The above scheme representation does not help with the first problem.
A C implementation with pointers would allow dangling pointers. An
object-oriented solution typically won’t help with the second and the
third problems.
You might wonder what it is that I want. The answer is that the
programming language should have built-in inductive data types,
because that’s what binary trees are. In Haskell, which has inductive
data types, trees are defined directly in terms of their structure:
data Tree = Empty | Node Int Tree Tree
This expresses the definition of trees directly: a tree is either
empty or a node composed of an integer and two trees. Haskell will be
able to catch all the common problems listed above. Other languages
supporting this sort of definition are ML, Ocaml, F#, and
interestingly Visual Prolog (I am told by Wikipedia).
We might ask for more. Suppose we wanted to implement binary search
trees. Then we would require that the left subtree only contains nodes
that are smaller than the root, and the right subtree only nodes that
are larger than the root. Can a programming language be designed so
that this property is guaranteed? Yes, for example the compiler could
insert suitable checks into the code so that anomalies are detected
during execution as soon as they occur. This might be nice for
debugging purposes, but what is production code supposed to do if it
discovers an anomalous data structure during its execution? Ignore it?
Raise an exception? It is much more useful to know before the program
is run that the data structure will never be corrupted. Here we hit
against a law of nature: there is no algorithm that would analyze an
arbitrary piece of code and determine whether it will only produce
valid search trees. It is a fact of life. If you really want to check
that your programs are correct you will have to help the compiler.
There are excellent tools for doing that, such as Coq and Agda–have a
look to see how programmers might develop their code in the future.
Confusing definitions and variables
A definition binds an identifier to a particular fixed value. A
variable or a mutable value is a memory location which holds a value
that can be read and changed. These two notions should not be
confused. Unfortunately, traditional programming languages only
provide variables, so many programmers don’t even understand what
definitions are. Java tries to fix this with the final declaration,
and C++ with the const declaration, but these are not used by
programmers as much as they could be (which is a typical sign of
dubious design decisions).
Using variables instead of definitions is wrong for a number of
reasons. First, if the compiler knows which identifiers are bound to
immutable values it can optimize the code better. It can, for example,
decide to store the value in a register, or to keep around several
copies without worrying about synchronization between them (think
threaded applications). Second, if we allow the programmer to change a
value which is supposed to be constant, then he will do so.
If you observe how variables are typically used, you will see several
distinct uses:
* often a variable is only assigned to once and is used as an
(immutable) definition
* a variable in a loop or list comprehension ranges over the
elements of a list, or a collection of objects
* a variable stores the current state and is genuinely mutable
Should loop counters be mutable? I think not. Code that changes the
loop counter in the body of the loop is confusing and error prone. If
you want to fiddle with counters, use the while loop instead. So in
two out of three cases we want our variables to be immutable, but the
popular programming languages only give us variables. That’s silly. We
should design the language so that the default case is an immutable
value. If the programmer wants a mutable value, he should say so
explicitly. This is just the opposite of what Java and C++ do. An
example of a language that is designed this way is ML and ocaml. In
Haskell you have to jump through hoops to get mutable values (now I am
going to hear it from a monad aficionado, please spare me an
unnecessary burst of anger).
Out of scope variables
I thought I would not have to explain why undefined identifiers are a
bad a idea, but the reader in comment 27 explicitly asked about this.
If a programmer refers to an undefined name then an error should be
reported. Concretely, I claimed that Python should complain about the
following definition:
def f(n): return i + n
What is i? Pythonists will quickly point out that i will be defined
later, and how deferred definitions are useful because they allows us
to define mutually recursive functions. Indeed, Java and Haskell also
accept mutually recursive definitions. But unlike Python they make
sure that nothing is missing at the time of definition, whereas Python
will only complain when the above function f is used. To be honest,
Python kindly displays the correct error message showing that the
trouble is with the definition of f. But why should this be a runtime
error when the mistake can easily be detected at compile time?
Actually, this question leads to a more general question, which I
consider next.
When should mistakes be discovered?
Should programming bugs be discovered by the programmer or by the
user? The answer seems pretty clear. Therefore, a language should be
designed so that as many programming errors as possible are discovered
early on, that is before the program is sent to the user. In fact, in
order to speed up development (remember that the development time is
expensive) the programmer should be told about errors without having
to run the program and directing its execution to the place where the
latest code change actually gets executed.
This philosophy leads to the design of statically checked languages. A
typical feature of such a language is that all the types are known at
compile time. In contrast, a dynamically typed languages checks the
types during runtime. Java, Haskell and ocaml are of the former kind,
scheme, javascript and Python of the latter.
There are situations in which a statically checked language is better,
for example if you’re writing a program that will control a laser
during eye surgery. But there are also situations in which maximum
flexibility is required of a program, for example programs that are
embedded in web pages. The web as we know it would not exist if every
javascript error caused the browser to reject the entire web page (try
finding a page on a major web site that does not have any javascript
errors).
Let me also point out that testing cannot replace good language
design. Testing is very important, but it should be used to discover
problems that cannot be discovered earlier in the development cycle.
I used to think that statically checked languages are better for
teaching because they prevent the students from doing obviously stupid
things. About two years ago I changed my mind. The students learn much
better by doing stupid things than by being told by an oppressive
compiler that their programs are stupid. So this year I switched to
Python. The students are happier, and so am I (because I don’t have to
explain that code must be properly indented). Python does not whine
all the time. Instead it lets them explore the possibilities, and by
discovering which ones crash their programs they seem to understand
better how the machine works.
45 Comments »
1.
This is a nice summary of many popular fallacies in language
design, which many defend to the death against all reason. I would
point out that a commonality here is the absence of sum types in
popular languages. Another is over-emphasis of mutation and state,
ranging from the mutable variables problems you point out up through
piles and piles of object nonsense that makes matters worse and worse
and worse. Just try to implement “delete” from a binary search tree
represented in the contorted “object-oriented style”. It’s appalling
because the class of a node can change from non-empty to empty, but
with everything being a reference the effect is only felt further up
the tree, and then you have to worry about aliasing. It’s a disaster.
Finally, I would suggest heading off the usual nonsensical argument
about static vs dynamic typing by pointing out that dynamic typing is
a mode of use of static typing (so-called dynamic languages pick a
single recursive type and obsess over it for no useful purpose), so it
can hardly be opposed to static typing, much less an alternative to
it. Moreover, every single thing you can do in a so-called dynamic
language can be done directly and easily in a static language—but as
soon as you do, you realize that you really don’t want to do this
after all (but you can, if you’re obsessive about that one true type
that everything must have).
Comment by Robert Harper — April 11, 2009 @ 19:36
2.
“Lisp and scheme programmers proudly represent all sorts of data
with conses and lists”
That is not true. Both Common Lisp and Scheme have arrays; and
Common Lisp even has bit vectors! Depending on your system, is
compiled as efficiently as it would if you used an int or char array
in C — with the advantage that in Common Lisp you declare it as a bit
vector and use bit operators on its elements (in C you have to use
bitwise operations on chars/ints, create masks to select specific
bits, etc).
Also, Common Lisp has structs (see defstruct), which (in SBCL/
CMUCL) is compiled as “contiguous memory location”, just as a C
struct.
Comment by w-g — April 11, 2009 @ 20:59
3.
I don’t know how to respond to this other than to say that
Python’s philosophy doesn’t match yours. As CAR Hoare said:
“I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously no
deficiencies, the other way is to make it so complicated there are no
obvious deficiencies.”
Python definitely encourages the former. To steal a quote from
Perl, does the language give you enough rope to hang yourself with?
Sure. But python is so simple a language that these kinds of stupid
mistakes are usually pretty easy to spot.
Haskell’s designers seem to disagree. Peyton Jones once said
that “any language large enough to be useful must be dauntingly
complex.”
Take the piece of code you post:
def f(n): return i + n
The problem is that based on this piece of code, we *don’t know*
if i is in scope or not. The above code becomes valid if it’s placed
in this context:
def g():
i = 0
def f(n): return i + n
return f
Are there ways to allow this behavior *and* remove the
possibility of stupid mistakes? Sure. But not without adding several
layers of complexity to the language. Does that mean it’s bad? Not
necessarily. But then we go back to the dichotomy: do you encourage
reliable code through simplicity or do you create reliability through
better compiler checks?
I’m of the belief that compiler checks don’t eliminate or even
reduce programmer stupidity. They just make it go deeper by creating
complexity. Have I written my fair share of stupid python code? Sure.
But it’s rare that I ever find myself saying “WTF is this code doing?”
But you obviously view things differently and that’s a good
thing.
Comment by Jason Baker — April 11, 2009 @ 21:19
4.
Jason, I intended that piece of code defining f to be a complete
module. Isn’t that obvious? Otherwise everything I wrote about it does
not make any sense.
Secondly, the claims you and I make are verifiable. There must
be research out there measuring whether “simple” languages have fewer
bugs, and whether static typing reduces programming errors. It would
seem tricky however to measure such things reliably.
Comment by Andrej Bauer — April 11, 2009 @ 21:26
5.
> Make sure the programmer never forgets to consider both
possibilities–the empty tree and the non-empty tree.
I’m not sure about this one. I often have to put error “won’t
reach this” in match statements in ML.
Comment by Jules — April 11, 2009 @ 21:45
6.
[...] Andrej Bauer added an interesting post today on
Mathematics and Computation » On programming language designHere’s a
small readingThe architect is bound by the rules of nature, he has to
take into account the properties of the building materials, and he
must never forget the purpose that the building will serve. … I can
hear you list lots of advantages of having these. But stick to the
principle: NULL is wrong because it causes horrible and tricky
mistakes which appear even after the program was tested thoroughly.
You cannot introduce NULL into the language and tell the programmer to
be careful … [...]
Pingback by Internet Marketing Email » Blog Archive »
Mathematics and Computation » On programming language design — April
11, 2009 @ 22:24
7.
[...] View original post here: Mathematics and Computation » On
programming language design [...]
Pingback by Mathematics and Computation » On programming
language design — April 12, 2009 @ 00:15
8.
Let’s say I agree that programmers are stupid: Then perhaps we
should educate them instead of giving them blunt tools that can’t hurt
them.
Now to change the subject. As any good Java programmer will tell
you, representing the empty tree by null is the best solution. The
only disadvantage you gave, that NullPointerException will happen, is
simply not a pragmatic reason. For if it happens, it will happen
quickly and will make you think harder about the code. The two sub-
classes solution sucks for the reason you mentioned: It makes the code
hard to read, because it’s spread out. The boolean solution is by far
the worst: Just as in the null-solution you are responsible to check
for empty trees with no help from the compiler, when you get an
exception it doesn’t directly translate to “you forgot the empty tree
case”, and you occupy extra memory. (Yes, using extra memory is bad,
especially when you don’t gain anything.) There is absolutely no
excuse for using this solution, let alone teach it.
Most people find it easier to think about a stateful world and
some find it easier to think about a stateless world. Of course, at
some deep level both formalisms are equivalent. It’s sad to see time
and again people from one camp claiming that the others are ignorants,
instead of acknowledging that different people have different styles
of thinking.
Comment by Radu Grigore — April 12, 2009 @ 00:16
9.
Jules: I’ve realized that dummy “can’t happen” matching (with
assert false) is
becoming rare in my OCaml code, as I tend to construct the data
types in ways
that allow exhaustive matching without impossible branches, for
instance by
using polymorphic variants instead of regular sum types or
encodings like ['a
* 'a list] for non-empty lists.
At any rate, even if you do end up using “impossible” matches,
at least the
type system forces you to be explicit and to take a minute to
think about
whether the branch can be reached or not.
Comment by mfp — April 12, 2009 @ 00:37
10.
Reply to Radu: You misunderstand me. I am not saying that
programmers are stupid. I am saying they make mistakes because they
are humans. They can’t help it, no matter how smart they are. Most
mistakes are really, really dumb, like mismatching the parenthesis,
writing pritn insteand of print, forgetting to initialize a variable,
etc. This has nothing to do with intelligence. It’s about how our
brains work. We’re not robots.
You are suggesting that the programmer should think about his
program hard. Yes, he should be thinking hard how to make his program
good, not how to get rid of silly errors. That is just a waste of
energy.
The tools I am suggesting are far from being blunt. Programming
languages such as ML and Haskell are way, way more expressive than
Java or Python.
Comment by Andrej Bauer — April 12, 2009 @ 01:18
11.
[...] Web pages need to be dynamic?Posted on Saturday, April 11,
2009 at 9:41 PM. Towards the end of his “On programming language
design” article, which does a very good job of pointing out the
benefits and necessity of statically-typed [...]
Pingback by Pinderkent: Do programming languages for code
embedded in Web pages need to be dynamic? — April 12, 2009 @ 02:16
12.
Arrgh, all this brainy talk is makin’ me head spin. Get back to
swabbin’ the deck, matey, unless you’d rather be hangin’ from the
mast.
Comment by Captain Morgan — April 12, 2009 @ 05:07
13.
I’m not sure if this was covered in the comments to the closure
post, but here’s the main issue:
Suppose you have a bunch of inline code that you want to turn
into a zero-arg closure. Suppose that code modifies some variable i.
If the closure takes the value of i at definition time and turns it
into a local variable, the code works differently when you create the
closure than when you inline it.
This adds an extra layer of confusion since macros and closures
would behave differently. You can’t apply the logic of a pure
functional language to an imperative stateful one. The example above
is a reasonably common one, that comes up if you realize you have the
same bit of code in both branches of an if.
Comment by chris — April 12, 2009 @ 06:06
14.
Reply to Radu:
You are dead-wrong about using nulls for empty trees, or any
other collection for that matter. You can’t even call myTree.count()
safely if you have a null. That’s why most guidelines say to always
return empty collections instead.
Comment by Jonathan Allen — April 12, 2009 @ 06:14
15.
> But then we go back to the dichotomy: do you encourage
reliable code through simplicity or do you create reliability through
better compiler checks?
Why not both?
Visual Basic will give you a compiler warning if you try to use
a loop variable in a lambda. If you still want to do it you can, but
at least you are warned.
Comment by Jonathan Allen — April 12, 2009 @ 06:17
16.
Thanks for a concise but thorough summary of important issues.
Regarding your example of binary search trees, there are some
interesting recent alternatives to Coq and Agda for enforcing these
sorts of constraints. I am thinking specifically of the Sage language
from Cormac Flanagan and his students at UC Santa Cruz (also Steve
Freund at Williams); I heard about it from Aaron Tomb during a recent
tech talk at Galois. In their tech report Sage: Unified Hybrid Checking
for First-Class Types, General Refinement Types, and Dynamic, they in
fact use binary search trees as a motivating example (quoting from
their Section 2.1):
Note that Sage supports dependent function types, and so the
type of the third argument to search can depend on the values of the
first and second arguments.
…
The Sage compiler uses an automatic theorem prover to
statically verify that the specified ordering invariants on binary
search trees are satisfied by these two functions — no run-time
checking is required.
…
This precisely-typed BST implementation can inter-operate
cleanly with dynamically-typed client code, while still preserving the
ordering invariant on BSTs.
Sage constitutes an interesting design which manages to
accommodate dependent types in a statically-typed setting; I’d be
interested in hearing your opinion of it.
Oh, and a PS to Bob Harper: the “one true type that everything
must have”, is that the One True Type that in the Darkness Binds Them?
(at run-time, presumably :) )
Comment by Fritz Ruehr — April 12, 2009 @ 06:57
17.
Lists and arrays are objects.
Comment by Eric Florenzano — April 12, 2009 @ 07:40
18.
“Programmers are just humans: forgetful, lazy, and make every
mistake imaginable. Therefore, it is the task of the designer to make
a programming language which counters these deficiencies.”
Wait, what? Aren’t programming language designers also human?
Shouldn’t one of the designer’s top priorities, then, be to make
sure the programmer can work around possible deficiencies of the
language design?
Comment by Ken — April 12, 2009 @ 07:44
19.
Have you looked at Scala? It addresses most of the issues you
bring up. While it does have null (for compatibility with Java), the
idiomatic alternative is the Option type, which is the equivalent to
Haskell’s Maybe. Case classes and pattern matching are a statically
checked way to define and operate on datatypes. Definitions (vals) and
variables (vars) are syntactic equals, but convention dictates that
vals are preferred over vars. Scala’s lambdas aren’t broken in the way
that Python’s are. There’s even a special syntax for lambdas. For-
comprehensions are like Python’s list comprehensions but on steroids
(closer in expressiveness to Haskell’s do-notation).
Scala is statically checked, it has a powerful type system, ok
type inference, and it’s fully compatible with Java. It basically
takes Java, drags it halfway to Haskell, halfway to ML, and ends up
looking a little like Python.
Comment by Jorge Ortiz — April 12, 2009 @ 08:13
20.
Reply to 15: This sounds like a joke and I am not really sure
what you want. Perhaps the fact that a general purpose language is
Turing complete?
Comment by Andrej Bauer — April 12, 2009 @ 09:07
21.
http://www.reddit.com/r/programming/comments/8brly/on_programming_language_design/c08szul
Comment by smallpaul — April 12, 2009 @ 09:08
22.
Jonathan Allen: what do the “left” and “right” methods return
for a Java EmptyCollection instance? By default they will return NULL
with Java inheritance, right? So what do you prefer? To have them
return? an exception? Another EmptyCollection? An infinite tree of
EmptyCollections?
Comment by smallpaul — April 12, 2009 @ 09:12
23.
Perhaps the following analogy is a good response to comment 8 by
Radu:
Mathematicians are certainly intelligent enough to calculate
128+395 in their head or on paper. But it will be boring, error-prone
and tedious. Fortunately, mathematicians have recognized that this
task can be performed by a machine and they can now spend their time
with more interesting things.
Similarly, programmers are certainly intelligent enough to
carefully handle null pointers, but why bother? Let the language and
compiler figure it out.
Comment by Heinrich Apfelmus — April 12, 2009 @ 09:28
24.
This is a reply to smallpaul, an angry person from Reddit. I
have edited the post to make the idea with trees as subclasses more
precise. Thank you for pointing out the lack of clarity in an
insulting way.
Commenting further on smallpaul’s, uhm, “review” on Reddit
(comment 21): recursion or something equivalent to it (loops, for
example) is necessary in a programming language that is Turing
complete, but NULL’s are not. This is the reason I would not advocate
elimination of recursion. Although I do think it would be beneficial
to separate structural recursion (a.k.a. primitive recursion), which
is guaranteed to terminate, from general recursion. I just don’t know
how to present it in a language without making it annoying.
Comment by Andrej Bauer — April 12, 2009 @ 09:38
25.
> There are probably other options. The first solution is
horrible, as every Java programmer knows, because it leads to many
NullPointerExceptions. The second solution is probably the most
“object-orientedly correct” but people find it impractical, as it
spreads code around in two classes. When I taught java I lectured the
third solution, but that one has the big disadvantage that the
programmer is responsible for checking every time whether a tree is
empty or not.
What code does the EmptyTree class have? If we are emulating
your Haskell example then all of these classes would have data and no
code. Conversely, if we wanted to add code, we’d put it only on the
NodeTree (given that the EmptyTree has no state and serves as simply a
sentinel).
You can use these classes as almost exactly the same as
Haskell’s constructors and the consumer will be forced to cast to the
right subclass (as in Haskell) before they fish out a value or a child
node. The only issue is that the consumer must use instanceof before
the cast rather than doing both in the same expression as Haskell
does. Still, that’s not a huge issue.
> we add a fourth attribute empty of type boolean which tells us
whether the tree is empty
> When I taught java I lectured the third solution, but that one
has the big disadvantage that the programmer is responsible for
checking every time whether a tree is empty or not.
If you use this solution, then what do the “right” and “left”
properties return?
Why is it easier or better to check for “is_empty” than to check
“==null”? As long as the responsibility to check is on the programmer,
what’s the difference?
Comment by smallpaul — April 12, 2009 @ 10:20
26.
“… In fact, in order to speed up development (remember that the
development time is expensive) the programmer should be told about
errors without having to run the program and directing its execution
to the place where the latest code change actually gets executed.”
Are you suggesting that the expense of code written in a
strongly typed language can be reduced by cutting down test coverage?
Well, I hope not. Especially in combination with the classic FUD-”eye
surgery” example.
I’m always dazzled by this kind of argument from static type
advocates. It completely blinds out the nature of decision problems
and creates the illusion that in recent time there was any progress
happening towards a static type checking/static analysis system that
converges “number of compiler errors in the program” and “number of
bugs in the program” in any significant way. As soon as this doesn’t
happen (and imho it will never happen) your test coverage needs to be
high, no matter what language you use.
So if your test coverage needs to be high anyway this degrades
the extra-hassle of a static type checking compiler rather to a matter
of taste than a matter of “extra security”.
Comment by Sebastian Morawietz — April 12, 2009 @ 10:29
27.
Another way to represent empty, say, trees in Java would be to
define an interface CanBeEmpty and derive trees from it. Method IsEmpty
() is obvious and method Empty() would create an empty object (yes, a
cast to the tree would be required; an inconvenience, but resolved at
compile time). This does nor solve the fundamental problem of the
value of an unitialized tree, but will help the programmer to build
trees properly.
Comment by Simon Hawkin — April 12, 2009 @ 10:53
28.
Dear Sebastian: No, I am not suggesting that static typing can
replace testing. And nowhere did I say that. But I also disagree with
you when you say that testing can replace static type checking. How
are you going to perform tests which GUARANTEE that type errors will
not occur, other than by performing complete type checking?
Read my post again and try to understand it in a POSITIVE way
(the incredible amount of hostility and misunderstanding is getting a
bit tiresome). I said it is good to tell the programmer about errors
as early in the development cycle as possible. You cannot possibly
object to that. You say that static typechecking is a hassle. Perhaps
it is. But imagine a complex program which has big startup costs. I
make a very small change in the code (in a way that cannot be easily
tested as a unit). Then I have to run the program just to be told
something is wrong. Then I have to look at the code to discover myself
that I made a trivial mistake. How is that less hassle than having the
compiler immediately refuse my code change?
I write programs in statically and dynamically typed languages
(mostly ocaml and Python), and have pretty good idea about what each
brings. I wonder how many of the angry readers here have active
experience with a wide spectrum of languages, or how many have
bothered to actually implement different kinds of languages. The types
of statically typed languages are not a hassle, they are a blessing.
The dynamic nature of Python is not such a big problem as the
proponents of statically-typed languages would have you think. (For
example, in web development it’s really nice that the changes in the
server code are immediately reflected on the web page–without
recompilation and server restart.) In my opinion, at the end of the
day the quality of the code depends more on the quality of its author
than on the quality of the language he uses. But this does not mean
that the quality of the programming language does not matter.
I teach the theory of programming languages, where I teach both
statically and dynamically typed languages. I do NOT tell my students
that dynamically typed languages are bad. I tell them that no one
language is the solution to all programming tasks. I emphasize the
benfits of static typing (obviously) but I do not belittle other
options. Most of all I want the students to understand the reasoning
behind design decisions. I also teach programming to beginners. Mostly
because of my advocating, this year my department switch from a
statically typed language (Java) to a dynamically typed one (Python).
I belive Python is better for teaching than Java. My limited
experience with teaching ocaml to beginners is not sufficient to say
what happens if you teach them ML or Haskell. I am most definitely not
saying that Haskell is the solution to everything, and my actions
clearly support that claim.
So please stop the religous wars. They are pointless. And one
more thing: when you write your comments be polite, or I will reject
the comment. If you think I said something incredibly stupid, then you
should suspect there is a misunderstanding (either by you, or because
I wrote something in an unclear way, or I made a mistake). You can
always ask politely instead of making insulting claims right off the
bat.
After wading though all the replies, I see several valid points
in the comments. The most interesting so far is: how would you
implement the Maybe datatype (with all its good properties) in a
dynamically typed language? It’s an interesting design question. So
let’s talk about that, can we?
Comment by Andrej Bauer — April 12, 2009 @ 11:08
29.
[...] [...]
Pingback by Posts about Programming from google blogs as of
April 12, 2009 « tryfly.com — April 12, 2009 @ 11:58
30.
Here’s a direct translation to Ruby:
class Maybe
def nothing?
self.class == Nothing
end
def just?
not nothing?
end
end
class Nothing < Maybe
end
class Just < Maybe
attr_accessor :value
def initialize(x)
@value = x
end
end
One of the problems with static typing is that there is no clear
choice for language designers. If you choose dynamic typing you’re
done, and you’re at a local maximum in the design space. If you choose
static typing you have to design the type system very carefully. There
is a whole spectrum between most safety and most flexibility.
Dynamic typing also allows you to solve problems like pickling/
distribution in a more straightforward way.
Comment by Jules — April 12, 2009 @ 13:35
31.
Or this version:
class Maybe
def nothing?
end
def just?
not nothing?
end
end
class Nothing < Maybe
def nothing?
true
end
end
class Just < Maybe
attr_accessor :value
def initialize(x)
@value = x
end
def nothing?
false
end
end
Comment by Jules — April 12, 2009 @ 13:37
32.
The title should be: “On programming language design or why
Haskell is my favorite language”.
And seriously, (left-tree my-tree), (right-tree my-tree), (value
my-tree), (is-empty? my-tree).
Comment by Poouik — April 12, 2009 @ 17:01
33.
I tend to agree with ken.
Your article suggests to me a dillemma. If programmers are human
and fallible, are not the designers who are also human just as capable
of error? If what you seek is the one true language which can properly
detect the intent of the programmer and protect them from their own
mistakes then I would be amazed if you ever discover it.
Instead, wouldn’t a more natural solution be a language which
gives the programmer the ability to modify it to suit the problem
domain? To take you binary tree example, you chose languages which
have primitives that can be used to emulate a solution, but their
implementation wasn’t built to understand those compositions. But what
if there was a language that allowed you to construct a grammar and
even a syntax that would operate on binary trees as you define them?
Such a language already exists and I believe it’s called common
lisp. The advantage of it is that whatever construct or operator or
even syntax that the language designers failed to include can be added
by the programmers as they explore their problem domain.
Comment by j_king — April 12, 2009 @ 17:04
34.
I don’t know Haskell at all, but I’ve always heard that it’s not
trivial to control the memory consumption of a Haskell program. If
this is true, and if I apply your theory that programmer’s are
“forgetful, lazy, and make every mistake imaginable”, isn’t that then
a strong reason not to use Haskell? Of course, if you know what you’re
doing, you probably can write Haskell programs that behave reasonably,
memory-wise. But then, if you know what you’re doing, you can write
very nice programs in C too.
Comment by Freek — April 12, 2009 @ 19:05
35.
It wasn’t and isn’t my intention to be impolite. Sorry, if my
previous comment was perceived this way.
But to be perfectly clear: I read your essay, I understood your
points (I guess) and I thoroughly disagree. Furthermore, the tone your
last two essays are written in at least suggests that you’re familiar
with the concept of dealing some out:
In your paragraph “Undefined values…”, you’re not giving the
creators of SQL, perl and python the benefit of the doubt. They didn’t
learn their lesson that the introduction of nil into a language is a
mistake - period. Others might call this a design decision. A
questionable one in your eyes - maybe, but oh well.
The reference post “Python’s lambda is broken!” is basically a
rant, ending with “What were the implementors of Python thinking?!”.
Considering that, you got many helpful replies pointing out the
different implementations of closures in different languages.
If there is a way to read the complete last paragraph “When
should mistakes be discovered?” other than a dichotomy between
(static==secure) vs. (dynamic==flexible but less secure), tell me how
to. It’s difficult to not resolve the initial question into “In
languages written in dynamic languages, errors are discovered by the
user.”
But towards your question concerning “Maybe”.
A function returning “Maybe Integer” is basically returning a
tuple of a potential return value (type Integer) plus the potential
information that something bad happened. Of course it is absolutely
possible to implement this kind of thing in ruby as Jules pointed out.
But the very concept is already implemented in all major languages as
Exception in the form of begin/rescue in ruby, or x=f(y) or blah() in
perl. But to ask how to enforce error handling up the call stack in a
dynamic language is equivalent to “tell me how to enforce types in a
dynamic language”. You don’t.
This leads us right back to the central question:
Does solidly implemented software that is reasonably well
covered with tests get even more secure by formally enforcing a type
system? After years of software development, starting in Eiffel, Java,
C/C++ and now Ruby, JavaScript, C I have absolutely no reason to
assume this.
Therefore I consider it as a valid question of tastes (which is
the least amount of religiosity I can offer :).
Comment by Sebastian Morawietz — April 12, 2009 @ 19:07
36.
In this essay, the comments and the reddit comments you write, I
hear three different things. I’d like you to please select one of the
following and say which one represents your feelings. I’d also suggest
that if you want to be clear in your writing that you stick to the one
you select in subsequent articles and be clear about it.
The three statements are:
1. I prefer static type checking languages. It’s a personal
preference.
2. Static type checked languages are better. They are always
better.
3. Statically typed checked languages are better for CERTAIN
KINDS OF PROJECTS AND PROGRAMMERS and dynamically typed languages are
better for others.
With each post you shift between those three statements
randomly, and in fact seem to switch around within this single post.
At the beginning you say Python’s design decisions are crazy and short-
sighted. Then by the end you say that you find Python and Javascript
better for certain tasks.
Comment by smallpaul — April 12, 2009 @ 19:40
37.
Reply to Freek (33): Yes, memory consumption in Haskell can be
quite unpredictable. This has always been one of the main criticisms
of functional languages by John Reynolds, a pioneer of programming
language theory.
Reply to smallpaul (35): Statically typed languages are my
personal preference, _especially_ because of the kind of programming
that I do. But I also write programs in dynamic languages and they’re
perfectly ok. In theory statically typed languages should always be a
win, but practice shows that dyamically typed languages fare pretty
well in the real world.
I need to do some real work, so I’ll stop replying now. Feel
free to rant and so on. When I have a bit of time I’ll implement
Python as I would have done it: the constraint is that it has to be a
dynamically typed language with lots of reflection and maximum
flexibility. See you then.
Comment by Andrej Bauer — April 12, 2009 @ 20:11
38.
Hi Andrej,
It seems I’m a little late to the party!
I would like to thank you, sincerely, no smirking, for your
considered reply to my original comment. This is one of the few posts
I have seen that contains, but is not limited to, a discussion of a
good dynamic language versus a good static language.
I have not programmed in OCaml, Haskel, or ML - but I do see
their examples on Rosetta Code which makes comparison easy (for
example: http://www.rosettacode.org/wiki/Y_combinator#OCaml). I
started my interest in Python in the mid 90’s. I have personal
experience of languages changing the way I think about problem solving
after being exposed to the SKILL programming language (a lisp
dialect), but also of how a language must be more ‘complete’ or ‘well
rounded’ before it would be prudent to invest too much time in it.
I think I should spend some time now investigating one of these
functional, type-inferred, languages so I can more meaningfully join
the debate.
I did, welcome the addition of at least a syntax for adding type
information to Python in this post:
http://paddy3118.blogspot.com/2008/11/smearing-static-vs-dynamic-typing.html
But looking back, what I would take from my post was this:
“You would need to think of static/dynamic as a continuum where
instead of having languages bunched at either end, you would have a
smearing out towards the middle.”
- Paddy.
Comment by Paddy3118 — April 12, 2009 @ 21:29
39.
The problem with the def f(n): return i + n is not as
straightforward as you might think, even if this function is the only
thing in a module, because you can do import mymodule; mymodule.i =
10; print mymodule.f(1). Obviously, doing exactly that is silly, but
it hints at the fundamental property of Python objects (be that
classes or modules) that is extremely useful. Of course, it is most
useful with classes because of the existence of standard interception
vectors such as getattr, so one may argue that modules could be made
different, at least requiring all attributes of a module to be
explicitly declared (but allowing redefinition, as it is widely used
way of providing custom handlers, and just plain easy way of quickly
tweaking module behaviour), yet there might be legitimate uses for the
whole functionality (some kind of metaprogramming maybe). Actually I’m
aware of one real case when it is used in the core library:
sys.setdefaultencoding is deleted by site.py during startup,
undoubtedly there are more. So, basically, changing the way it works
would complicate the language (making modules really different from
all other kinds of objects) and violate Python ideology of not
restricting users to do what they want because they could come up with
some wonderful unexpected ways of doing things. And the price is not
so high, considering Python’s primary area of application, that is not
eye surgery.
Comment by Fj — April 12, 2009 @ 23:28
40.
[...] programming language design Andrej Bauer has a very nice
article about language design on his blog, which happens to reflect a
lot of what I believe about [...]
Pingback by On programming language design « Occasionally sane —
April 13, 2009 @ 00:06
41.
[...] and Learning April 12, 2009 Via Michael Feather’s blog:
“On programming language design” I used to think that statically
checked languages are better for teaching because they prevent the
[...]
Pingback by Types and Learning « Günther Noack’s blog — April
13, 2009 @ 12:44
42.
@Johnatan Allen: Of course you would use an empty collection
instead of null! I was talking about how you implement a tree, which
can be used to represent a collection, not about the interface of a
collection. These are very different things.
Comment by Radu Grigore — April 13, 2009 @ 23:13
43.
@Heinrich Apfelmus: I agree. I think that Java should have a non-
null data type, and its absence is one of the things that makes me
prefer Haskell and ML. I’m not sure, though, how is that contradicting
what I said.
Comment by Radu Grigore — April 13, 2009 @ 23:27
44.
@Andrej Bauer: Forgetting that trees can be empty is not a
“silly” mistake in my opinion. YMMV.
Comment by Radu Grigore — April 13, 2009 @ 23:29
45.
Haskell and ML have some really nice features the Maybe type is
one of my favorite constructs too, but these languages will never be
very useful until they have a real tool chain. Anyone who has ever
tried to find a bug in a large unfamiliar Haskell code base will know
what I mean. It is shockingly time consuming because the debugging
tool chain is so primitive and things like dynamic linking only have
experimental support. The reality is that as fun and beautiful as it
is to write in Haskell and as good as the language itself is, it is
just not a terribly useful platform for everyday software development.
The ecosystem around it is not filled with people that are interested
in getting things done.
Comment by Frank — April 18, 2009 @ 10:15
Reply all
Reply to author
Forward
0 new messages