1 Introduction
| #lang plait | package: plait |
1.1 Course Overview: Why Study Programming Languages?
You have all programmed in a programming language, but so far, you’ve most likely only interacted with the language as an oracle: you have written programs, and you have learned the meaning of various programs by running them and seeing what happens. This is like how a baby learns to speak: you have learned about programming languages observationally, sometimes also called by immersion.
This course is all about the active study of programming languages. It’s a bit like an English class: we will break programming languages into their tiny gruesome pieces to learn about how they work. It’s also a bit like a math class: we will give precise definitions for what programs do, and study the consequences of those choices. And of course, it’s a programming class: you will write a lot of code and implement a host of different programming languages throughout the course.
In this course, we will actively engage in the study of programming languages. Programming languages have many facets:
Social: A programming language is a means of communication between programmers, and exists in a social environment with its own customs.
Mathematical: Programs written in a programming language have an abstract notion of "meaning", given as a definition.
Implementation: A programming language can be realized as a program (a compiler, interpreter, etc.) that can be run by a computer and programmed in.
We will study these aspects in turn and implement many programming languages ourselves. Along the way, we will understand more about today’s programminmg languages, and understand where programming languages may be going in the future.
1.1.1 Consequences of Programming Language Design
"Explaining a joke is like dissecting a frog. You understand it better but the frog dies in the process."
― E.B. White
#include <iostream> |
|
int main() { |
while(true) {} |
} |
void go_home_c_plus_plus_you_are_drunk() { |
std::cout << "lol" << std::endl; |
} |
If you answered "loop forever", you would be wrong for the latest version of C running on Clang, see for yourself by running it here. In fact, this program prints "lol" to the console. The reason why it does this isn’t so important. The fact that it does this at all is what matters. It turns out that this behavior is mathematically legal; the C specification permits this "optimization".
This video is recommended viewing.
[] + [] |
If you answered "empty string", you know a lot of JavaScript and you are right! Why does this evaluate to the empty string? Well, + becomes string append, so it coerces its arguments into strings, and the empty array is coerced into the empty string. Of course!
What’s the point? Aren’t programming languages just funny complicated things that sometimes have weird behavior, just like how English sometimes has strange oddities that we simply accept?
Yes, and no. Languages are synthetic creatures: we made them! Every oddity in a language was someone’s idea that they thought was a really cool idea that would help them, or someone else, program. Sometimes, it is only in hindsight – after programming in a language for many years and writing lots of code – that we realize a cool-seeming idea wasn’t so cool after all.
An important example is Tony Hoare’s billion dollar mistake: null pointers. Consider the following Java program:
public class Example { |
public static void main(String[] args) { |
Object obj = null; |
obj.hashCode(); |
} |
} |
This program causes a runtime error. The design question is: should Java’s typechecker permit this program? Today, it does: you can compile this program, and running it will yield a runtime error. The problem with null values is that they can happen anywhere; programs can surprisingly fail due to a mystery null appearing and not being handled properly, leading to very expensive debugging to track down where the null value originated. Over time, due to this cost, programming languages have slowly moved away from this model: languages like Rust do not permit arbitrary null values, and by and large this is accepted and no one complains about missing their null values.
The moral of the story is: language design is important and can impact generations of programmers. Many of today’s programming languages were developed in a very ad-hoc way; they have small mistakes and big mistakes, and programmers just learn to live with them. As a society, we are beginning to grapple with the enormous technical debt of programming in languages with poor design decisions: for instance, the federal government is advocating for programming in memory-safe languages. The main aim of this class is to study the systematic design of programming languages: what are the choices one can make in making a programming language, and how are those choices implemented. It might even make you a better programmer.
1.1.2 Tips for Success in the Course
Read the syllabus carefully and ask questions if anything is unclear.
Attend lectures and take your own notes. It might be useful for you to follow along with the code yourself.
Read the course notes and give feedback on them if you see any typos.
Make use of your resources. Go to office hours if you need help, ask questions on Piazza.
Communicate with the instructor if you are struggling or need accomodations.
Start assignments early; they can be quite tricky and you might need help. Test your code!
1.2 Plait
One lesson we will see in this class is that the smaller a programming language is, the harder it is to mess up. Plait is a programming lanugage designed for teaching programming languages courses. It is small, so it has less opportunities for mistakes. It has scheme-like s-expression syntax and an ML-like type system. See the Plait tutorial here. We won’t cover every feature you need from Plait in this lecture; you are expected to learn some on your own.
A Plait program is a sequence of Plait expressions. The following is a plait program:
> 10 - Number
10
This interaction shows that the plait expression 10 has type Number and runs to the value 10. You should run this program by typing it into the DrRacket interactions window.
In these notes, definitions of important terms are written in bold. Important ideas are written with emphasis.
> #t - Boolean
#t
> #f - Boolean
#f
> "hello" - String
"hello"
One more value that may less familiar are Symbols. Symbols are use-defined values that can be passed around and compared. They are created using the single quote character like this:
> 'hello - Symbol
'hello
1.2.1 Plait Functions
Functions in Plait are called like this: (f arg1 arg2 ...). All function calls are wrapped in parenthesis; this is where the term "s-expression" comes from (the "s" has an open paren for the top half, and a close paren for the bottom half).
There are lots of built-in functions in Plait. Here are a few:
> (+ 1 2) - Number
3
> (* 3 4) - Number
12
> (< 10 4) - Boolean
#f
> (string-append "a" "b") - String
"ab"
Plait is a typed language, so it will complain if you try to run a program that is not well-typed. You can see the type of a function by entering it into the interaction window:
> + - (Number Number -> Number)
#<procedure:+>
This says the function + takes two arguments each of type Number and returns a Number. If we try to call this function with arguments of the wrong type we’ll get a helpful error.
Everything in Plait is a function call, including things like conditionals:
> (if (< 10 3) (display "then branch taken") (display "else branch taken"))
- Void
else branch taken
Which parens should I use? Plait has two kinds of parenthesis, () and []. They behave the same, but look different. Mimic the style of parens that you see in class and examples; it helps make your code easier to read stylistically. For more on style, see here.
> (cond [(< 10 3) (display "first branch taken")] [#f (display "second branch taken")] [#t (display "third branch taken")])
- Void
third branch taken
In Plait, functions are also values. They are declared using the λ (or lambda) syntax:
> (λ (x) (+ x 1)) - (Number -> Number)
#<procedure>
Functions can be called in the usual way:
> ((λ (x) (+ x 1)) 10) - Number
11
1.2.2 Definitions
A definition is a name that is bound to a value. We can create definitions using the built-in define keyword:
> (define pi 3.14) > pi - Number
3.14
Using define we can declare named functions:
> (define myadd (λ (x y) (+ x y))) > (myadd 1 2) - Number
3
There is a shorthand for declaring functions that doesn’t involve λ that we will use more frequently:
> (define (myadd1 x y) (+ x y)) > (myadd1 10 20) - Number
30
Functions have types. In this case, the type of your function is inferred. We can see the inferred type by entering its name into the prompt:
> myadd1 - (Number Number -> Number)
#<procedure:myadd1>
It’s considered good style to manually annotate the type of your functions. This is done by declaring the type of the function before its definition in the following way:
> (my-typed-add1 : (Number -> Number))
> (define (my-typed-add1 x) (+ x 1))
1.2.3 Local Variables
Local variables are created using the let keyword:
> (let [(x 10)] x) - Number
10
There are other ways of introducing local variables like let* and letrec; we will return to these as needed.
1.2.4 Lists
Lists are an important primitive datatype. A list is one of two things: an empty list empty, or a pair (cons hd tl) where hd is the first element of the list and tl is the rest of the list. For example:
The type (Listof 'a) is a list of something of type 'a. The symbol 'a stands for an unknown type, to be filled in later. It’s analogous to a generic in Java.
> empty - (Listof 'a)
'()
> (cons 1 empty) - (Listof Number)
'(1)
> (cons 1 (cons 2 empty)) - (Listof Number)
'(1 2)
It’s tedious to declare lists this way, so we have several short-hand notations for making lists:
> (list 1 2 3) - (Listof Number)
'(1 2 3)
> '(1 2 3) - (Listof Number)
'(1 2 3)
The quote symbol is special. Read the rules for how it works by clicking on the link in the quote here: 'a.
We’ve seen how to build lists, but not how to unbuild them. We will unbuild lists by using the type-case keyword:
> (define my-list '(1 2 3))
> (define (add-list l) (type-case (Listof Number) l [empty 0] [(cons hd tl) (+ hd (add-list tl))])) > (add-list my-list) - Number
6
1.2.5 Testing and Errors
Plait has built-in functions for testing that your code behaves as expected. The function (test actual expected) tests that actual evaluates to expected. You should use them in your programs, like this:
> (test (add-list '(1 2 3)) 6)
- Void
good (add-list (quote (1 2 3))) at line 34
expected: 6
given: 6
1.3 Syntax: Programs Are Data
Our study of programming languages begins with understanding how programs are represented to the computer. Surface syntax is the textual representation of a program: it’s what you type into your editor. Consider the following surface syntax:
1 + 2 |
This represents the program "add 1 and 2". Of course, we could have also written the program using an alternative surface syntax, s-expressions:
(+ 1 2) |
There are clearly countless different kinds of surface syntax. What we need is an abstraction: we want to abstract away the details of how surface syntax is written into a more uniform representation. This is called abstract syntax, which can be represented as the following datastructure:
> (define-type CalcLang (numE [value : Number]) (addE [left : CalcLang] [right : CalcLang]))
Then, we can create the "add 1 and 2" program as follows:
> (define add1to2 (addE (numE 1) (numE 2)))
This same abstract syntax can represent a variety of different surface syntax. The process of translating surface syntax into abstract syntax is called parsing; we will discuss this a bit more next lecture.
1.4 Semantics: Giving a Programming Language Meaning
Semantics associates a meaning with abstract syntax. What does the program add1to2 do? Intuitively, this program should "evaluate to 3" by performing the addition 1+2.
We define the semantics of programs compositionally by giving a meaning to each part. Let’s start by giving a specification for the semantics of calculator programs using English:
(numE v) evaluates to v
If l evaluates to v1 and r evaluates to v2, then (addE l r) evaluates to v1 + v2.
We are using one language, English, to describe the behavior of another language, CalcLang. It’s helpful to give these two languages names to denote their roles. We call CalcLang the object language: it’s the language we are trying to describe. We call English the meta-language: it’s the language we’re using to describe another one.
"This book will perhaps only be understood by those who have themselves already thought the thoughts which are expressed in itor similar thoughts."
– L. Wittgenstein, Introduction to the Tractatus Logico-Philosophicus.
1.4.1 Plait as a Meta-Language
We can use Plait as a meta-language for describing the meaning of CalcLang programs. To do this, we can write an interpreter: a Plait program that runs CalcLang programs. Here is an example of such a program:
> (define (interp-calc e) (type-case CalcLang e [(numE v) v] [(addE e1 e2) (+ (interp-calc e1) (interp-calc e2))]))
> (test (interp-calc (addE (numE 1) (numE 2))) 3)
- Void
good (interp-calc (addE (numE 1) (numE 2))) at line 38
expected: 3
given: 3
> (test (interp-calc (addE (addE (numE 1) (numE 2)) (numE 3))) 6)
- Void
good (interp-calc (addE (addE (numE 1) (numE 2)) (numE 3))) at line 39
expected: 6
given: 6
Here, we delegate the problem of defining the meaning of the values 3 and 6 to Plait: these are Plait numbers. We also delegate the meaning of + to Plait: this is Plait addition.
This is our first programming language. We will see many more.