Modern Programming Language Theory

In the beginning, there was machine code: raw, unadorned hexadecimal numbers. In indeed, glorious work was written by the unsung heros of that time. (See also: the story of Mel.) But at some point, a bright young spark decided that he could replace cryptic bytes like 0x05 with clearer mnemonics, like MOVE or ADD. Then, in order to actually run his programs, he would use another program called an "assembler": a program that would read a program in this mnemonic language, called "assembly", and produce the actual hexadecimal form of the program (the "binary"). Assembly code looks like this (this is the standard Fibonacci function):

fib:
        .cfi_startproc
        pushl	%ebp
        .cfi_def_cfa_offset 8
        .cfi_offset 5, -8
        xorl	%ecx, %ecx
        movl	%esp, %ebp
        .cfi_def_cfa_register 5
        movl	$1, %edx
        pushl	%ebx
        xorl	%eax, %eax
        movl	8(%ebp), %ebx
        .cfi_offset 3, -12
        jmp	.L2
.L3:
        movl	%edx, %eax
        incl	%ecx
        addl	%edx, %edx
.L2:
        cmpl	%ebx, %ecx
        jl	.L3
        popl	%ebx
        .cfi_restore 3
        popl	%ebp
        .cfi_def_cfa 4, 4
        .cfi_restore 5
        ret
        .cfi_endproc

At that moment, the field of programming language theory was born, with the goal of making programs ever easier, safer, and faster to write. Nowadays, programming language theory is a large, well-developed branch of computer science. Today, we'll look at what modern aspects of this branch do and the advances brought by it.

Programming language theory has, as stated above, the broad goal of making programming easier. But let's be more specific; what are some properties of programs we'd like to achieve?

Correctness

We'd like programs to be correct, to not have bugs. In computer science, we can study the use of formal reasoning and proof about programs, and the use of various forms of testing, to improve our confidence that programs work.

Extensibility

We'd like to make it possible to extend and change programs, and to use them in novel ways.

Expressivity

We'd like to make it possible to use as many ways as possible of thinking about a program.

Productivity

We'd like to make programmers as productive as possible; in particular, we don't want to force them to repeat themselves, or force them to deal manually with things the computer can do for them.

Usability

We'd like to make it simple to solve various hard program design problems, such as designing for concurrency, or for security.

To this end, many different paradigms and approaches to language design have been explored in computer science. We'll talk about:

• Functional Programming, as demonstrated by Scheme or Haskell
• Metaprogramming, as demonstrated by Lisp or Scheme
• Type Theory and Correctness, as demonstrated by Haskell or Coq
• Dynamism, as demonstrated by Smalltalk or Scheme
• Concurrency / Parallelism, as demonstrated by Erlang or Clojure

We'll talk about these in terms of the fundamental ideas of the subject, so in a lot of cases we'll either be inventing notation as it happens to be useful, or using an amalgam of various languages. I'll try to add notes about what languages tend to emphasize that discipline.

Fundamentally, functional programming is characterized by the notion of functions as abstraction. Now, it isn't that much of a stretch to say that properly choosing and creating abstractions is one of the fundamental parts of programming. So by understanding how one can use functions as a very general abstraction mechanism, one can gain a powerful programming tool; and likewise we'd like to design languages to take advantage of this.

The reason functions are good at abstraction is that they combine behavior and data, while being rather lightweight. This function+data idea is called a closure. Closures are present in many mainstream languages, including Python, Ruby, C++11, and Java 1.8, as well as in almost all of the less mainstream languages.

The benefit of closures is that it is easy to pass around behavior. For example, suppose we're writing a multi-threaded program. One of the things we might want to do is have a "critical section": a section that only one thread can run at a time. In languages without closures, I would likely do this by creating a new class that inherits from a certain superclass. But this is silly since I'm not describing a type of object, I'm describing a behavior. In a functional language, we could write the critical section code to instead take a function as an argument that describes the behavior that goes inside the critical section. We might use it like so:

def/fn double-last [lst] <-
    let (x <- pop lst) <-
      push lst <- * 2 x

critical-section double-last