Pavel Panchekha


Share under CC-BY-SA.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

Modern Programming Language Theory


This is just a quick sketch of the class, and will be filled in likely only if the class it taught again.

Programming language theory is a rather modern field of computer science, whose goal is to make the task of writing programs easier. This class investigated modern approaches and trends in programming language theory; looked at examples of leading paradigms; and discussed how various features would be used in actual programs in the real world.

The Role of Programming Languages

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):

	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
	movl	%edx, %eax
	incl	%ecx
	addl	%edx, %edx
	cmpl	%ebx, %ecx
	jl	.L3
	popl	%ebx
	.cfi_restore 3
	popl	%ebp
	.cfi_def_cfa 4, 4
	.cfi_restore 5

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.

Goals of Programming Language Theory

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?

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.
We'd like to make it possible to extend and change programs, and to use them in novel ways.
We'd like to make it possible to use as many ways as possible of thinking about a program.
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.
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.

Functional Programming

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 


Type Theory