Static Vs. Dynamic Typing

Static vs. dynamic typing. Here's my ravings.

Being thoroughly trained in ML, I understand the benefits of static typing. Here are some claimed benefits.

1. Reduced CPU usage since types don't need to be checked at runtime
2. Reduced memory usage since types don't need to be stored at runtime
3. Other type-directed optimizations
4. Discovery of errors as early as possible, for all my code
5. Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged

Now let's look at the claimed benefits of dynamic typing.

1. Easier to run and test since there are practically no compile-time or link-time errors
2. Programs are not limited by the expressiveness of the type system of the language — e.g. heterogeneous data structures w/o explicit tagging
3. Allows for implicit open recursion, late binding, dynamic scope, and duck typing
4. Programs are simpler since I don't have to worry about types. Things are often coerced implicitly making my programs more concise, and I don't have to use really abstract things like type variables and higher-order types. In other words, they have been abstracted away by being pushed down to a place I don't have to think about.
5. Faster prototyping due to not having to write down types which change often during prototyping

There are a few claimed benefits, however, which are not true. Allow me to refute.

Myth: Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged.

It's true that dynamic typing is a special case of static typing. This can be seen by simply creating a tagged union where each branch is a different possible runtime type. Then make every expression in your language a value of this type. Voila — dynamic typing.1

However, it does not follow that this makes static typing more powerful. To see this more clearly, let's use a simpler example. C vs. assembly. C is more powerful than assembly. But there are things you can write in assembly that you simply can not write in C. Because you are restricted. Restricted by the definition of the C language which does not know anything about your cool new machine instruction to factor large numbers and break your gramma's closely-guarded RSA-encrypted banana nut bread recipes. However, anything you can write in C, you can obviously write in assembly. So C is a special case, or subset, of assembly.

In other words, the more powerful language is the one that is the subset.

And this does not depend on the specifics of the language. So in the case of dynamic vs. static typing, dynamic typing is actually more powerful. I alluded to this already by the fact that dynamic typing abstracts away types by pushing them down into the runtime system.

Myth: Dynamic typing allows for faster prototyping due to not having to write down types which change often during prototyping.

This myth stems from the belief that types in dynamically typed languages don't have to be written down at all, while types always have to be written in statically typed languages. And this is absolutely false!

First of all, even though you don't have to declare the types of variables and functions in dynamically typed languages, you still write down some types. Whenever you make a class, declare fields or methods of a class, or specify inheritance relationships, you are creating and/or specifying types.

Secondly, type information does not need to be specified in statically typed languages that include type inference. Many languages with type inference like ML and Haskell are specifically designed so that you don't have to write down any types. The only exceptions are enumeration-like data structures (i.e. tagged unions) which have runtime values. So the difference between the amount of type information you must write depends greatly on the language itself, not whether that language has static or dynamic typing.

So we are down to the following for static typing.

1. Reduced CPU usage since types don't need to be checked at runtime
2. Reduced memory usage since types don't need to be stored at runtime
3. Other type-directed optimizations
4. Discovery of errors as early as possible, for all my code
5. Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged

And for dynamic typing.

1. Easier to run and test since there are practically no compile-time or link-time errors
2. Programs are not limited by the expressiveness of the type system of the language — e.g. heterogeneous data structures w/o explicit tagging
3. Allows for implicit open recursion, late binding, dynamic scope, and duck typing
4. Programs are simpler since I don't have to worry about types. Things are often coerced implicitly making my programs more concise, and I don't have to use really abstract things like type variables and higher-order types. In other words, they have been abstracted away by being pushed down to a place I don't have to think about.
5. Faster prototyping due to not having to write down types which change often during prototyping

Some people have counterarguments as to why these are not real benefits. I will go through some of them.

Myth: The cost of runtime type information in speed or memory is not significant, especially with today's hardware.

In general keyboard-speed applications, the cost of runtime type information is not significant. But in core loops, it can be huge. Because it is not just a matter of checking the types, which itself can be very costly in a loop. But the fact that you must store everything as a tagged value means that everything must be stored as a pair in memory. This means that in dynamically typed languages, there is no way to specify the computation of adding the values in two registers and storing the result in another register. The add operation in a dynamically typed language must load a tag from memory, conditionally branch on the value of the tag, load a 2nd tag from memory, conditionally branch on the value of that tag, load the first number from memory, load the 2nd number from memory, add the numbers, store the result in memory, and then store a new tag. This is ignoring the case where the runtime system has to allocate memory for this new object, as the statically typed version may spill registers, so call it even.

For such a simple operation though, this is a huge cost.

Myth: Type-checking is a substitute for testing.

Again, absolutely not true. Although some people may use type-checking (static in particular) for testing program correctness, this is neither its intended purpose nor its limit of use. Type-checking is more about ensuring meaningful, well-defined execution than ensuring correctness. Even though you may hear strong static-typing advocates say, "When your program type-checks, you'll often find that it just works", this is simply not true for large, intricate programs. Although type-checking may help you find errors, it is not the same as testing. Thus, it is not a suitable substitute for testing.

Static type-checking will however discover one entire class (or a few classes) of errors at compile-time, early in the development cycle — something that is dependent upon executing every code path in a dynamically-typed language, which is simply infeasible.

Other Issues

Open Recursion, Late Binding, Dynamic Scope

Open recursion and late binding are just special cases of dynamic scope. It's not clear whether having these features is a good thing or not. They make it easy to introduce bugs when extending code in a way that was originally not intended (which happens fairly often). They can definitely be useful though since they allow you to do things that can't be done easily without the features. But as I explained earlier, more flexibility does not imply power. In fact it's the opposite, as long as the constraints are well-designed. Except in bottlenecks where optimization is crucial, Duff's device is a bad feature for a language to support. And although you can implement open recursion in a statically typed language, you can't implement dynamic scope in general (and be type-safe) without converting your entire program to use tagged values, which would be implementing the entirety of dynamic typing. So in this respect, dynamic typing is actually more flexible.

Some may argue that the language should not constrain the programmer. Let him decide whether or not to use it. After all, exceptions are a special case of dynamic scoping, and many statically-typed languages support this. The problem is that you will inevitably be using or extending someone else's code. And the person who wrote that code will inevitably make a judgment call that you consider to be poor, making the code non-obvious and unnecessarily complicated from your perspective — which can really be said about any powerful language feature, so maybe it's just me. But this one can make it especially difficult to reason about your programs. ...Again, it's not completely clear whether these features are good or bad.

Type-Directed Optimizations

If you care about performance, which you will for just about any production app, type-directed optimizations can help you a great deal. I won't go into the details of how they work, but the basic idea is that the compiler uses type information to optimize your code. Theoretically, you could have a compiler for a dynamically-typed language that performed the same optimizations. However, to do this at compile-time, it would have to collect the same information as a compiler for a statically-typed language. I've never seen a compiler able to do this in general, but such a hybrid is the future of typing.

An alternative is for the compiler to do the optimizations at run-time — i.e. just-in-time.

The problem with static typing is that there are always more type-directed optimizations that would be nice to do is always more type-expressiveness that would be nice to add, and so more and more complicated type systems emerge, oftentimes complicating a language with quirks such as ML's value restriction. On the other hand, if dynamic typing were used, the problem causing such complication would disappear. A simple solution is often the best.

Types in the Source Code

Dynamic-typing advocates claim that writing down types is a hindrance, especially during prototyping. This stems from the assumption that you have to do additional work to think of and change the types of the expressions you're dealing with.

I definitely understand the criticism of writing down types because I don't usually write down loop invariants, so I could see that as being "extra work". But types are no different. Both types and loop invariants are required to create the program, but not to execute the program.

For anyone who's become proficient in a language with a powerful type system, he knows that in order to even write a meaningful program, you have to use the correct types. And so when you're writing the program, you implicitly (and unconsciously for some) give a type to every single expression you write. So why not write down all this extra information that was used to create the program so that it can be used not only by the compiler, but by you when you come back to your code after a week. The same goes for invariants — loop invariants in particular — but I'll save that for another post on theorem provers!

Knowing what I know about theorem-proving and loop invariants, I believe writing down the types is the right thing. However, in a prototyping situation where the types are changing faster than you can type them, you shouldn't have to write them down. That's where type-inference comes in. But as the system begins to stabilize — as some parts which are getting pushed down in the hierarchy do — you should write the types down, because at that point you know what the types should be, and the extra information can be used by the compiler to check and optimize, and by those reading your code to understand your program's interfaces and semantics.

Typing of the Future

Here's the typing hybrid I see as the future, as the answer is never on either end of a spectrum, but a balance somewhere in the middle — a pattern of the Universe.

1. The flexibility to omit the vast majority of types, but consequently,
2. a significant amount of type-inference that uses
3. a powerful type system that is so expressive that it is itself Turing-complete, which requires
4. blurring the lines between compile-time and runtime to the point where the programmer can not always tell (and should not always care) whether static or dynamic typing is being used by the compiler.

And we will get there by pushing on.

---

1. This is where the "un(i)typed language" joke comes from. A language that is "untyped" really has exactly one type for all expressions.

You Can Only See...

It's been a re-occurring idea recently that you can only see what you already know. How then   do you ever get to see the things you don't know?

It seems you just have to force yourself. You have to push yourself and trudge through it. Just dive in even though you don't feel comfortable with it. And force yourself to use, and thus learn, the new thing. It's always hard at first, but after repeated use, you start to get more comfortable and develop an intuition.

After reading On Intelligence by Jeff Hawkins, it became obvious to me that not only do genetic memories exist, but I have them and they control me all the time. Reading that book was the trigger that allowed me to understand something new. And now I can see the concept of genetic memories. Something that was not obvious to me   now became obvious.

The interesting thing is that this is not just for technology or scientific theories. But also artistic, social, or spiritual matters. For example, why is it that many believe in astrology, miracles, or the existence of a greater power (a.k.a. a god) while others explain it away in terms of chance, scientific laws, or something else trivial and uninteresting?

Due to my numerous run-ins recently with this idea, I'm beginning to think these are just more examples of things that can only be seen if you already get the underlying concepts that make them up.

On a related note, reading The Neverending Story made me realize it's possible to create something that always existed.

A Strange Medium

Code is a very strange medium. Because of compilers, constructing a program is practically free once you unambiguously design it in code. But the design is constantly changing. It's really like building a skyscraper. So many intricate details, all working together. If any one piece fails, it could cause the whole building to collapse. But somehow it all must integrate to form a coherent whole.

The difference with code though, is that you're always extending it. With a building, the architect designs it once, perfects it, and then sends it off to be constructed. Sure it may come back to him during construction for modifications due to changes in materials or budget. The client may even say, "I want it to have 2 more floors." Fine. Add in the 2 more floors. Work in the new materials, et cetera. But once it's built, it's built.

With programs, there are similar milestones in releases, but there is never an end to the changes and additions of features. Moreover, after you've been working with something for a while, you begin to see patterns. And it makes sense to factor those patterns out — to abstract them away and push them down into a lower level. Or, you may even see a way of redesigning that is so fundamental, that the only sensible way of doing it would be to redo the specification completely.

Because over time, your understanding both of the problem and the solution changes.

The Hard Test

It's recently come to my attention that there are smart, capable programmers out there who are resistant to learning and/or using more powerful programming languages.

I have to admit, in hindsight, syntax can be a huge deterrent. The first thing I used to do when I saw Lisp's parentheses was try to parse them like parentheses in other languages — basically implementing a stack in my head. This is extremely difficult. And the parens just make the code ugly. Something like Haskell on the other hand, I look at that and it's just beautiful.

When I started coding in Scheme and mentioned to someone more familiar with it that I was having difficulty with the parens, he pointed out the fact that you don't have to parse the parentheses in Lisp or Scheme. Just use an editor like Emacs that automatically indents properly based on the parens, and simply look at the indentation.

Oh. That makes things easier.

But besides the whole high learning curve, Lisp in general is very abstract. And thinking abstractly is hard. Now, people don't like doing things that are hard. Why would anyone want to do something that was hard when they could do it an easier way. And this is exactly the reason why most people avoid more abstract programming languages. However, that very abstractness is what makes them so powerful. As long as people believe "anything that can be done in language X, I can do in my language", they will never advance. So many people fall into this trap because of the Turing-machine idea of expressiveness.

But programming isn't only about expression, it's about understanding.

It's a shame though that people who are smart enough to work with abstract tools shy away from them because they are hard. Due to the fact that they are hard to use, the majority of people can't use them to their full potential. Therefore, anyone who has the ability can move ahead of the pack.

The fact that something is hard is never a good reason to not do it. In fact, it's often a reason to do it. If I'm faced with a choice where I seem unable to decide, I ask myself, which option is harder. Because that is probably the right choice. I'm probably only considering the other one to avoid the difficulty in the right choice.

ML → Scheme

I wrote my first real Scheme macro today. It was a macro to emulate ML's pattern-matching.

Writing a type-checker in Scheme, I found myself writing all these list?, eq?, and let* expressions, making my code look way too complicated than necessary. All of that can be done simply and concisely with pattern-matching. For Lisp hackers out there that aren't familiar with pattern-matching, it's basically a destructuring-bind where you can have constants or symbols in your binding expression which are compared with the value you are binding to, sort of like a cond where the predicates are implicitly specified in the pattern.

The great thing about pattern-matching is that code to process data looks just like the data you are processing. So it makes it extremely easy to look at code that uses pattern-matching and see what it's doing, as opposed to equivalent code that uses explicit conditionals and lets.

Without pattern-matching:

(cond ((and (list? exp) (eq? (first exp) 'typ-arrow)) (let ((param-typ (second exp)) (ret-typ (third exp))) (do-stuff param-typ ret-typ)) ((and (list? exp) (eq? (first exp) 'typ-union)) (let ((branch-typs (second exp))) (do-stuff-to-branches branch-typs))))

With:

(match exp (('typ-arrow param-typ ret-typ) (do-stuff param-typ ret-typ) (('typ-union branch-typs) (do-stuff-to-branches branch-typs)))

Anyway, when I first started using Scheme, I didn't like the prefix notation and the paren-syntax — or lack of syntax. Compiler writers out there, you know what I mean. ;-) Frankly, I don't know anyone who does like it at first. I thought, I'd rather write code in a more familiar way, then switch to prefixed constructors when I needed to create code like I would in ML. For example, the SML/NJ compiler exposes the abstract syntax as a datatype, so you can do just this.

However, this means that there are 2 representations of code in the language. Two. ...And that doesn't seem right.

After working with macros (I finally had the conceptual break-through of figuring out how to use double backquotes — ick!), I realized, this makes sense. The idea that code and data have the exact same concrete representation makes total sense. So much so that I believe this is the right way to do it.

But one question that comes to mind is, why does that one representation have to be prefix notation with parentheses everywhere?

It's not clear whether being able to write data in the same form as the regular parsed grammar (infixes and all) would be a good thing or not.

One thing I've since learned, but had trouble with when I first switched from ML to Scheme, was that in Scheme, the meaning of parentheses is overloaded. In ML, parentheses are used for disambiguation of parsing, and that's all. This is almost strictly so in OCaml. But in Scheme, not only is it used for specifying the parse in lists and sub-lists in quoted expressions, but also for function application. This confused the hell out of me for a little while, and my first inclination was to avoid using quote (i.e. ') and use list instead. But I soon got over that.

Overall, my experience learning Scheme has been extremely rewarding, as a great way to recognize patterns in something is to experience something completely different from it. And many decisions that were made in designing ML, the opposite choices were taken for Scheme or Lisp.

Seeing ML Clearly

I went to school at Carnegie Mellon. And there, the computer science department is big on research. For system-level programming, they use C. But for almost all theoretical or type related topics, they use ML. In particular, Standard ML.

So since I was really interested in compilers and type-theory, I became very familiar with ML. First how to use it. Then how to use it to make interpreters. How compilers work. And eventually, how to compile ML code. A relative expert in ML.

While at CMU, I was thoroughly trained in the benefits of strongly typed languages, the pitfalls of weakly typed languages, and why static typing can result in more efficient code than dynamic typing. I was also introduced to the idea of typed intermediate languages — that compilers have multiple phases which translate code to entirely different languages, each of which is strongly typed, getting closer and closer to the target language after each phase. In other words SourceLang => IL1 => IL2 => ... => ILn => TargetLang. And after I got the hang of it, I thought ML was great! Oh, how I became to loath writing code in other languages. Look! Look how easy and beautiful the code would be in ML.

But recently, for the first time, I've had a real reason to write some code in Scheme. Scheme is similar to ML in that it's functional. But it's dynamically typed. Moreover, some flavors have "features" in them like dynamic scope that make it very difficult to look at a piece of code and determine whether it will compute gracefully or result in an error. One of the biggest benefits of static typing is that it reveals errors in your programs as early as possible — at compile time. Dynamic typing on the other hand, reveals errors as late as possible. If a branch of code is never taken, you'll never know whether that piece of code will fail, possibly until you ship your code and your users break it, losing millions (even lives) in the process.

So all through school, I was on one side. I was very very close with ML. But now that I've been using Scheme (and also toying with Qi [pdf]), I've been on the other side. And now, for the first time ever, I can judge ML for what it truly is. And here's what I've found.

I still think ML's a great language. Early bug detection and the invariants that are captured in types are so utterly essential to writing correct code that I can't believe it's still being done the other way. I literally can't go writing more than a couple Scheme functions before I have to write down the types in comments, because otherwise, I have to try to hold all this stuff in my head. It's not something that is in addition to writing the code; types are something I implicitly think about when I create code. When I look at a piece of code, to see if it makes sense I type-check it in my head, in the same way that I execute it in my head when debugging for example.

However, I've realized there are a few very powerful abstractions that are missing from ML (or lacking).

1. Macros
2. Reader Macros
3. Unrestricted Execution of Types

...Maybe I'll go into the details later.