Re: What is Expressiveness in a Computer Language

4 views
Skip to first unread message

Neelakantan Krishnaswami

unread,
Jun 22, 2006, 4:28:47 PM6/22/06
to
In article <1150998222....@i40g2000cwc.googlegroups.com>, Joe
Marshall wrote:
>
> That's the important point: I want to run broken code. I want to run
> as much of the working fragments as I can, and I want a `safety net' to
> prevent me from performing undefined operations, but I want the safety
> net to catch me at the *last* possible moment. I'm not playing it safe
> and staying where the compiler can prove I'll be ok. I'm living
> dangerously and wandering near the edge where the compiler can't quite
> prove that I'll fail.

Hi Joe,

How do you write programs? Specifically, how do you write and debug
higher-order programs that involve lots of combinators (eg, code
that's partially CPS-converted, or in state-passing style, and also
uses maps and folds)?

The reason I ask is that I see that there are Scheme programmers that
manage to do this successfully. However, I switched to ML because I
just couldn't get that kind of code right without having type errors
to guide me.

Since people like you and Matthias and Shriram obviously *can* write
this kind of code, I'm curious what your strategies are.

--
Neel Krishnaswami
ne...@cs.cmu.edu

Shriram Krishnamurthi

unread,
Jul 5, 2006, 10:15:27 PM7/5/06
to
[Ignoring Neel's follow-up to c.l.functional, because I don't read it.]

Neelakantan Krishnaswami wrote:
>
> Since people like you and Matthias and Shriram obviously *can* write
> this kind of code, I'm curious what your strategies are.

I program bottom-up. So I'm constantly testing my code as I go.
Testing early and often makes a huge difference.

For the most part I program as if I were in ML. I program with a type
discipline, so I make relatively few type errors.

But then, for the past few years, most of the code I've written has
been for Web applications, and there I wouldn't get much help from the
type system anyway. The type system might have helped me with static
HTML validation (if it could handle all the vagaries of HTML variants,
and cascading style sheets, and so on...which is a big if!), but it's
not something I've found a great need for. Given the shlock Web
browsers will print, my generated HTML is hardly a problem for them.

Once in a while I've written throw-away "scripting" code that's really
annoying. In some such cases I've been tempted to pop over and look
at the type signatures of the corresponding libraries in OCaml, and
they're all based on neutral types (eg, strings). So, no help.

Two years ago I assessed all the bugs we'd run into in Continue, our
Web-based conference paper management system (continue.cs.brown.edu).
Some were type errors, but they were small bugs. Many were HTML
errors, but

(a) they too were minor
(b) they were immediately evident from the page output

(Yes, fixing both kinds of errors sometimes took a few minutes. A
good type system that gave good error reports would have saved us
those minutes.)

But then, I realized, I'd had a few errors that had really kept me up
at night: some because they took that long to find, all because of the
gravity of the problem. In other words, you know, the truly ***bad
stuff***. And I realized they *all* had to do with access control.
So that's what I've done research in for the past two years.

So, it's not that I don't make type mistakes, or that the ones I make
don't annoy me. But these aren't where my deep bugs are. Presumably
that's not where your deep bugs are, either, if you're writing
interesting, modern applications.

I don't have any deep hostility towards types, nor are my opinions
about them nearly as strong as those of someone like Joe Marshall.
The problem is getting them to live nicely with the world the rest of
my code inhabits. This is precisely what the thesis work of my PhD
student, Guillaume Marceau, is about, using ML-style let-based
polymorphism as the canonical typed language.

Shriram

Joe Marshall

unread,
Jul 6, 2006, 1:39:04 PM7/6/06
to

Shriram Krishnamurthi wrote:
> I don't have any deep hostility towards types, nor are my opinions
> about them nearly as strong as those of someone like Joe Marshall.

I surprised Arthur Gleckler the other day when I said that I have
essentially a favorable view of static types. I'll probably surprise a
few more people if I mention that it was Matthias Blume who persuaded
me. His argument was this: Why would anyone *not* want the computer
to find bugs *automatically* at compile time? (Ignore the practical
difficulties for a second.) I have no problem with this *in
principle*.

> The problem is getting them to live nicely with the world the rest of
> my code inhabits.

That's the rub. I object to giving the computer hints about types
(especially at the beginning of a project), and I truly object to the
computer refusing to run any part of my program unless it *all* type
checks. I also like to use type-ignorant constructs like lists; the
type checker has a hard time with these.

So while I have no problem with static types in principle, they don't
do an awful lot for me in practice.

Interestingly, I have wanted some static type guarantees in mature
code. In a complex project I was working on, the low-level library
code was quite stable. Certain library routines were able to take
advantage of the fact that all callers passed objects of a particular
representation. By declaring the type to the compiler, we were able to
get it to produce very fast code. We'd provide a generic wrapper
function that would dynamically check that the arguments matched the
required type before calling the fast code (and either calling the slow
code or raising an error otherwise), but I'd have really preferred it
if the compiler could have automatically dispatched to the correct
code, or if it could have raised an error if the caller misused the
library.

I don't like to declare types in experimental code because I really
don't know what the type is at that point. Once the code is fairly
mature and I'm happy with the design, it becomes rather obvious what
the types are. At this point in the process I would welcome more help
from the compiler.

> Neelakantan Krishnaswami wrote:
> >
> > Since people like you and Matthias and Shriram obviously *can* write
> > this kind of code, I'm curious what your strategies are.

I've been thinking about this for the past several days. I'm curious
as well. I *think* that there are several common strategies and that
people get used to one or two that are successful for them. Marshall
Spight has questioned me on this as well.

I'd like to do a programming contest where the object is not to be
first, fastest, or best, but to have different groups and people
demonstrate different programming strategies as they build the program.
Static type aficionados seem to want to design the types at the
get-go, while dynamic people seem to want to design the data and
control flow first. I'd like to see how these approaches contrast.

For higher-order functional programming, I think I might be using a
different model than you. I see LAMBDA not so much as specifying a
function, but as marking a code fragment. I see the higher-order
functions not so much as a mapping between function spaces, but rather
as a template. The missing pieces are the code fragments provided by
LAMBDA expressions elsewhere. The type of a higher-order function is
parameterized by the type of the code fragment in a particular
instantiation of that function, so I *think* that my strategy might be
that I'm internally flattening the higher-order type to something
relatively simple. But I'm not really sure --- I just hack.

> I program bottom-up. So I'm constantly testing my code as I go.
> Testing early and often makes a huge difference.

I prefer a stratified design strategy. I'll work on a layer at a time
(not necessarily the bottom or the top). I do a lot of playing around
with partially implemented functions and explore how different parts of
the program need to interact with other parts.

> For the most part I program as if I were in ML. I program with a type
> discipline, so I make relatively few type errors.

When I *know* the type (like if it is an index into an array), I put in
explicit type checks. When I don't know the type (it is an `object' of
some sort) I leave them out.

>
> So, it's not that I don't make type mistakes, or that the ones I make
> don't annoy me. But these aren't where my deep bugs are. Presumably
> that's not where your deep bugs are, either, if you're writing
> interesting, modern applications.

The deep bugs I find generally have to do with a misunderstanding
between two parts of the system. It is often hard to localize the bug:
both parts of the system are doing reasonable work, but they don't do
it together.

David A. Herman

unread,
Jul 6, 2006, 6:28:12 PM7/6/06
to Joe Marshall, dhe...@ccs.neu.edu, s...@cs.brown.edu
> His argument was this: Why would anyone *not* want the computer
> to find bugs *automatically* at compile time? (Ignore the practical
> difficulties for a second.) I have no problem with this *in
> principle*.

This is one of the two good reasons for automatic static type checking.
Coding in a typed discipline involves understanding and often documenting
the types of a program. Indeed, why not let the computer automate this?

The second reason, though, is that static type checking gives a programmer
the flexibility to *change* the data design. Documenting invariants in
unchecked comments is notorious for being prone to getting out of synch
with the actual program. When you document your types in comments (or
don't document them at all) and then make a change to the type structure,
you get no help from the computer. I was recently burned by a number of
type errors in a compiler I'm writing in Scheme, errors that had lain
dormant for months when I changed just a couple of the types in my AST
definition. This would have been trivial in ML; it would have caught all
of the modules that needed to change and guided me in all my refactorings
one by one. Instead, months down the road, I had to try to remember what
the changes had been and try to perform the type-checking algorithm myself
across the entire codebase. This didn't take minutes, but hours. And my
codebase is only a few thousand lines!

Just as you say, Joe, it's critical to give the programmer flexibility to
discover and reshape the structure of the program during the development
process. This is why I generally like languages with many equational
properties: they tend to admit a larger set of useful refactorings. But
types don't necessarily hinder this flexibility, they in fact increase it.

> > The problem is getting them to live nicely with the world the rest of
> > my code inhabits.
>
> That's the rub. I object to giving the computer hints about types
> (especially at the beginning of a project), and I truly object to the
> computer refusing to run any part of my program unless it *all* type
> checks. I also like to use type-ignorant constructs like lists; the
> type checker has a hard time with these.
>

> [SNIP]


>
> I don't like to declare types in experimental code because I really
> don't know what the type is at that point. Once the code is fairly
> mature and I'm happy with the design, it becomes rather obvious what
> the types are. At this point in the process I would welcome more help
> from the compiler.

I think that so-called "optional" type systems hold a lot of promise in
addressing your usage patterns. It's a hot research topic, and there are
lots of variants with different names: optional types, pluggable types,
static types with Dynamic, hybrid types, etc. Some of the literature is
bogus, but some of it has potential.

If you don't have to document types when they're obvious, or where there
are impedance mismatches, or where you simply don't know what the types
are, then the type system becomes a tool that helps automate the
programming process and facilitate refactoring, rather than an austere and
inflexible design discipline.

> Shriram Krishnamurthi wrote:
>
> > For the most part I program as if I were in ML. I program with a type
> > discipline, so I make relatively few type errors.

I hear this argument a lot, and it's true. But it's missing the fact that
type systems don't just catch errors, they facilitate *change*.

Dave

Shriram Krishnamurthi

unread,
Jul 7, 2006, 8:16:11 AM7/7/06
to
Joe Marshall said:

> > The problem is getting them to live nicely with the world the rest of
> > my code inhabits.
>
> That's the rub. I object to giving the computer hints about types
> (especially at the beginning of a project)

But you do give the computer hints all the time. Every time you write
down the value 3, you tell the computer you want a number. When you
write down (cons 'x (cons 'y empty)), you tell the computer you want a
list of symbols. There are hints all over your program. And these
hints are just what a type inference engine picks up.

> and I truly object to the
> computer refusing to run any part of my program unless it *all* type
> checks. I also like to use type-ignorant constructs like lists; the
> type checker has a hard time with these.

These two issues are not actually distinct. I rarely ever want to run
a program that isn't, at *some* level, type-correct. But I do
prototype with programs that won't fit one particular type system or
another (but the invariants still fit in my head). So this is
precisely what Guillaume's thesis is about: letting me write part of
my program inside and part of it outside the grasp of the type system,
and meaningfully mediating the interaction between the two.

> I don't like to declare types in experimental code because I really
> don't know what the type is at that point.

Red herring. Type inference is, what, one of the truly great ideas of
computer science. You don't need to declare types.

Shriram

Joe Marshall

unread,
Jul 7, 2006, 6:54:27 PM7/7/06
to

Shriram Krishnamurthi wrote:
> Joe Marshall said:
>
> > > The problem is getting them to live nicely with the world the rest of
> > > my code inhabits.
> >
> > That's the rub. I object to giving the computer hints about types
> > (especially at the beginning of a project)
>
> But you do give the computer hints all the time. Every time you write
> down the value 3, you tell the computer you want a number. When you
> write down (cons 'x (cons 'y empty)), you tell the computer you want a
> list of symbols. There are hints all over your program. And these
> hints are just what a type inference engine picks up.

Of course I don't mind these! What I object to is mindlessly typing
String myString = new String();

You think the compiler might understand I want a string? Should I tell
it a few more times?

>
> > I don't like to declare types in experimental code because I really
> > don't know what the type is at that point.
>
> Red herring. Type inference is, what, one of the truly great ideas of
> computer science. You don't need to declare types.

Says you. Try leaving out the types in Java or C++ and see how far it
gets you.

Yeah, I understand that Java and C++ are primitive with regard to type
technology, but languages with sophisticated type inference are even
*less* popular than Lisp!

Shriram Krishnamurthi

unread,
Jul 8, 2006, 8:56:32 AM7/8/06
to
Joe Marshall said:

> Of course I don't mind these! What I object to is mindlessly typing
> String myString = new String();

So don't program in a language with a mindless type system. Duh. But
don't equate "typed programming" with programming in a language with a
mindless type system. Picking your opponent's weakest point in an
argument does you no credit.

Type inference is a bit like garbage collection: It isn't the right
tool in all situations, but it works remarkably well in most
situations. If you choose to not employ it, that's more a statement
about your prejudices than it is about the technology in question.
Don't make broad, sweeping statements about the technology.

Shriram

PS: Languages with "sophisticated type inference" may be less popular
than Lisp, but that's because languages with sophisticated
*anything* are less popular than languages without. But languages
with unsophisticated type inference, like OCaml, seem to have no
shortage of popularity. I see first-hand evidence all around me.

Joe Marshall

unread,
Jul 10, 2006, 12:48:36 PM7/10/06
to

Shriram Krishnamurthi wrote:
> Joe Marshall said:
>
> > Of course I don't mind these! What I object to is mindlessly typing
> > String myString = new String();
>
> So don't program in a language with a mindless type system. Duh. But
> don't equate "typed programming" with programming in a language with a
> mindless type system. Picking your opponent's weakest point in an
> argument does you no credit.

Am I arguing? I stated earlier that I have essentially a favorable
view of static types.

Reply all
Reply to author
Forward
0 new messages