Class 1.1: Programming Languages

Summary

Language

Humans use language to communicate ideas with each other. Arguably our use of language is a big distinction in what it means to be human, and a huge advantage our ancestors had in developing and passing along knowledge — to us!

Many of you will know or at least have some familiarity with languages other than English. Think for a moment about what these languages have in common, and how they differ.

Two important aspects (which of course also apply to programming languages) are expressivity and precision. Expressivity is about being able to describe something easily or naturally, and precision is about making it clear exactly what you mean.

For example, German has a single word Kummerspeck which means, roughly, the weight one gains from overeating during stressful times. Describing this same concept in English is possible, but it’s a bit more awkward and lengthy; we might say German is more expressive on this topic.

For another example, consider the sentence “I saw her duck.” Is this referring to someone’s quacky pet, or to bending down? That’s an example of how English (and probably every human language) can be imprecise, leading to multiple different interpretations of the same words.

Programming Languages

A programming language has a similar goal of human languages: it’s a set of rules and practices for communicating, or expressing ideas, between two different individuals. Except of course, that one of those individuals is (usually) a computer!

In terms of precision, we have much higher standards for programming langages than human ones. Generally speaking (we will talk about it more next class!) in a well-designed programming language, there should only be exactly one meaning of any given program. Ambiguity is sometimes helpful in human speech, and perhaps necessary for us to express complex emotions and so on, but in programming languages it’s to be avoided!

In terms of expressivity, programming languages are much more limited than human languages. We don’t need to talk about stress eating or feathered friends in a programming language; we just need to explain what we want the computer to do.

Still, expressivity can differ greatly between programming languages. For example, here is a C program to get the first 50 Fibonacci numbers in an array and then print them out:

#include <stdio.h>
#include <stdlib.h>

int main() {
  long *fibs = malloc(50 * sizeof(long));
  fibs[0] = 0;
  fibs[1] = 1;
  for (int i = 2; i < 50; ++i) {
    fibs[i] = fibs[i-2] + fibs[i-1];
  }
  for (int i = 0; i < 49; ++i) {
    printf("%ld ", fibs[i]);
  }
  printf("%ld\n", fibs[49]);
  free(fibs);
  return 0;
}

In Haskell, due to something called lazy evaluation which we might learn about later in the semester, we can do exactly the same computation like this:

fibs = 0 : 1 : (zipWith (+) fibs $ tail fibs)
take 50 fibs

Roughly, these two lines translate to:

And yes, it actually works! (Try it with ghci in a terminal if you dare.)

The point is, Haskell is much more expressive here because it allows us to work with things like “imagined” infinite lists on a real computer, which isn’t really possible in C.

Tradeoffs

Programming languages are inherently a compromise. They are meant for communication between humans and computers, so we shouldn’t expect them to be perfect for either the human or the computer.

We just saw an example of Haskell and C, where the Haskell language ends up being much more expressive. But that doesn’t mean Haskell is a “better” language than C, just that it has different trade-offs and capabilities. Compared to Haskell, C is much closer to how the computer actually works for example, allowing for much faster execution at run-time.

Compiled vs Interpreted

Remember the title of this course: Programming Languages and Implementation. What is that last part about? It means somehow getting that program written in some programming language to actually run on a real computer.

There are generally two ways that this happens:

These two approaches actually share a lot in common, as we will see. They both need to read source code and understand what the programmer is saying. But the compiler must then go a step further and output code in another lower-level language.

Interpreters are generally a bit easier to create, and allow for more flexible code. But compilers are actually still involved no matter what; the interpreter itself probably needed to be written in a compiled language at some point!

Goals of the class

The course policy states the class learning objectives in kind of a formal way.

To put it more succinctly, we are trying to accomplish a single thing:

You are going to design a new programming language, and an interpreter and compiler for that language, from scratch.

That’s really it! But it’s going to be a long, tough journey to get there.

There are many reasons why we are doing this: