A Path to Enlightenment in Programming Language Theory

I have also learnt how to write compilers for simple languages (mostly from Appel's book). Through reading the book, I picked up ML. At first it was an uncomfortable transition from C, but I eventually loved writing ML code. Strong typing eliminates a lot of common errors, and the compiler really feels like a friend that's watching over you.

Later on, I decided to pick up Haskell. Frankly it was a lot harder to get used to it (I still can't say I understand Haskell) because of how side effects in Haskell are made much more explicit than either C or ML. But after about a year and a half, I can now code comfortably in Haskell. And if someone let me choose a language that I can only code in for the rest of my life, it might actually just be Haskell.

But ML and Haskell are not without their problems.

C and functional languages like ML/Haskell have different problem domains. Haskell, being (almost) pure, is really good at modeling side-effect free computations.

The compiling process is really a translation process (thus a computation), and it's easier to model it in Haskell. It is quite easy to mess things up in a language like C where side-effects show up everywhere, although if you're disciplined enough you could probably translate a Haskell program into C with some modifications.

But Haskell/ML is definitely not for everything. I would not write a kernel in Haskell (although I do know people who have done it). With the runtime problem aside, it doesn't give me enough control over the bare metal it's running over (or it's probably I just don't know it well enough yet). I can't layout things exactly the way I want with Haskell, but with C, I can build structs, cast integers into pointers (might not be a good idea, but sometimes necessary when you're dealing with a kernel) and so on. With C it feels like you're the creator, taking care of everything, hence, you have much more responsibility on your shoulder. But with Haskell, the compiler takes care a lot of things for you if you're in the right problem domain, and it lets you focus on abstractions and the problem itself.

Anyway, just a little thought. I love Haskell and C equally, and they're both absolutely wonderful languages. But try to keep yourself open and just try a little bit of new things at a time. Pretty soon you might find yourself designing compiler for your own language in Haskell (or C)!

It's kind of like astronomy - you can (and should) start with looking up, and notice that the stars rotate around the north star. Terms like right ascension, azimuth, celestial spheres, plane of the ecliptic, etc...these are impressive and important sounding and they really get in the way of understanding.

It's not arbitrary picking astronomy as my example, because in the end computers are physical systems. They are quite unique because they are capable of actions that look like violations of the second law - e.g. you can quite easily reverse a program that simulates gas diffusion, and simulate putting that gas back in a jar - that is, you can define an incredibly delicate system, and reset it for nothing, like being able to use a kitchen for anything and then clean it instantly, for free. More generally, all of a computers negentropy can be recovered for little or no cost after arbitrary disorder! They are also unique because they can rapidly and accurately and repeatedly traverse very specific state spaces, which is unlike anything in the universe, including the human brain.

As a physical system, a computer extends through time, and it's state is in general time dependent. Coupling signals across time is, I believe, what programming is about. We have special names (jargon!) for different signals - we call signals that come earlier "programming" and signals that come later "runtime input". But only useful distinction is between signals that arise from outside the system, and those which arise inside (that is, programming and input are the same; but input arising from results of a function call are profoundly different). It's useful because only the latter can recurse, which is both a source of error, but also the only possible way "intelligence" (or any really complicated behavior) could possibly express. The only other thing that matters is the shape of the system state - which constrains, in some ways, the kinds of states the system can achieve (or, because it's a universal machine, it constrains the general patterns of state traversal in some hand-wavy sense).

I built something that demonstrates these ideas, if anyone's interested.

A: I'm a simple Python programmer. Please tell me why I need types.

B: Types let you catch many bugs that would otherwise cause compile time errors or require compile time checks or testing.

A: But I've seen studies that suggest that static typing does not prevent bugs.

B: When I said static typing, I meant dependently typed languages, which can express almost any constraints at compile time, not just the basic constraints expressed by static typing.

A: Great, you've convinced me. What dependently typed languages can I use in my production system.

B: Errrr

As a mathematical theory, a way to think about programming, and a research project for future languages, type theory is very interesting. But it's not otherwise that useful for the practicing programmer.

The problem with this may be best expressed by Whorf[1]:

"Language shapes the way we think, and determines what we can think about."

A philosophical school of thought concerned with this is known as Linguistic Relativity[2]. But I digress.

Part of internalizing foreign concepts is approaching them with minimal prior prejudices. Trying to relate concepts inexpressible in C to C idioms is extremely difficult, if not impossible, before being able to _translate_ those concepts into what can be represented in C. It's the classic "chicken and egg" problem.

The best thing I can think to recommend is to pick a language which is generally considered capable of supporting the concepts you wish to learn and approach it as if you have never seen a programming language before.

> When I open Pierce TaPL and see immediately ML my heart sinks.

IMHO, this reinforces the fact that tools which you have used before (likely to great success) are influencing your view of those tools which you are not as familiar. IOW, you learned BASIC, x86 assembler, and C... Why not ML?

Best of luck and hopefully the path you walk is fun!

1 - http://www.searchquotes.com/quotation/Language_shapes_the_wa...

2 - https://en.wikipedia.org/wiki/Linguistic_relativity