8 How to Design Programming Languages
This lecture draws on material from How to Design Programs.
8.1 Standards and Skills
The midterm grades will come next week. The midterm itself, as well as your finalized grading for homework assignments 1-4, is prompting me to revise our current curriculum.
8.1.1 Changes
The major change that this entails is that we will be moving away from a traditional points-based system towards a standards/skills based system. Similar to how I provided high-level "skills" in preperation for the midterm, I will provide low-level "skills" that will be used to inform you of your grade.
You will have the opportunity to redo your midterm (this will be one of your homework assignments).
Our main driver for evaluating skills will be pen-and-paper assessments. We’ll have a couple of these today. If the skills being evaluated are not yet there, You can always retake these.
The lecture notes format will reference How to Design Programs, which will be a main driver for the next half of the semester.
I’m going to move all my office hours to remote only (and in-office by appointment). It seems that people prefer this more, anyhow.
No concept check this week, these will return in a different form.
The mid-semester survey was already announced – this would be a great time to reflect on the semester so far.
A small preview is below:
8.1.2 Standards
At a very high level, the three pillars of the class we are teaching surround the following competencies:
Computation: I can design, implement, and explain functional programs over structured data, including syntax trees.
Generalizing Computation: I can explain program evaluation and design interpreters using a language’s syntax, binding structure, and operational semantics.
Analyzing Computation: I can analyze expressions and design type checkers using typing rules, and reason about type soundness
Additionally, this class evaluates how well you can connect these three ideas together:
Synthesis of the above skills: I can explain and defend a small language extension by connecting its syntax, runtime semantics, typing rules, interpreter implementation, and type-checker implementation.
Today we are going to make a small modification to one of these standards, namely, Computation. The change will be:
Computation: I can design, implement, and explain functional programs over structured data, including syntax trees using the design recipe.
8.2 Systematic Program Design
We will start by transporting ourselves all the way back to CalcLang and equip ourselves with a new tool: The Design Recipe.
First off, what is an interpreter? An interpreter is a program that takes another program as input and carries out its meaning. It interacts with people ("users") and with the environment in which that program runs.
Broadening this scope to programs, any reasonably complete program is going to consists of many building blocks: some deal with input, some create output, while some bridge the gap between those two.
We use functions and functional programming as a fundamental building block for the programs we write because everyone encounters functions in pre-algebra and because the simplest programs are leveraging these same concepts. The key is to discover which functions are needed, how to connect them, and how to build them from basic ingredients.
In this context, “systematic program design” refers to a mix of two concepts: design recipes and iterative refinement. These will be the core structural driver not only of how we will write programs, but also how we build new language features. In fact, we touched on some of these concept previously, but in revisiting this in more detail are going to solidify this into a concrete "meta-skill" working for us at all levels of program design.
A core takeaway from this is that programs are more than just examples of "my code works." They are also crucial for high-level communication. This means that they must be readable (and explainable) by others.
8.2.1 Design Recipes
Design recipes apply to both complete programs and individual functions. The function-level design recipes share a common design process, detailed in the following six essential steps. The title of each step specifies the expected outcome(s); the "commands" following suggest the key activities. Examples play a central role at almost every stage.
From Problem Analysis to Data Definitions: Identify the information that must be represented and how it is represented in the chosen programming language. Formulate data definitions and illustrate them with examples.
Signature, Purpose Statement, Header: State what kind of data the desired function consumes and produces. Formulate a concise answer to the question what the function computes. Define a stub that lives up to the signature.
Functional Examples: Work through examples that illustrate the function’s purpose.
Function Template: Translate the data definitions into an outline of the function.
Function Definition: Fill in the gaps in the function template. Exploit the purpose statement and the examples.
Testing: Articulate the examples as tests and ensure that the function passes all. Doing so discovers mistakes. Tests also supplement examples in that they help others read and understand the definition when the need arises—and it will arise for any serious program.
8.2.2 Iterative Refinement
Iterative Refinement addresses the issue that problems are complex and multifaceted. Getting everything right at once is nearly impossible. Instead, computer scientists borrow iterative refinement from the physical sciences to tackle this design problem. In essence, iterative refinement recommends stripping away all inessential details at first and finding a solution for the remaining core problem. A refinement step adds in one of these omitted details and re-solves the expanded problem, using the existing solution as much as possible. A repetition, also called an iteration, of these refinement steps eventually leads to a complete solution.
In this sense, a programmer is a miniscientist. Scientists create approximate models for some idealized version of the world to make predictions about it. As long as the model’s predictions come true, everything is fine; when the predicted events differ from the actual ones, scientists revise their models to reduce the discrepancy. In a similar vein, when programmers are given a task, they create a first design, turn it into code, evaluate it with actual users, and iteratively refine the design until the program’s behavior closely matches the desired product.
8.2.3 Transforming ASTs
Let’s put our design recipe into action with a program we want to write that performs a transformation on this AST. We’ll start with some small task:
"Given an AST, I want to double all nodes in the ast."
This is very vauge, but we can still apply Step 1: "From Problem Analysis to Data Definitions." We’ll use Calc for our AST...
> (define-type Calc (numE [value : Number]) (addE [left : Calc] [right : Calc]) (mulE [left : Calc] [right : Calc]))
...and doubling a node in a calc AST will grow the tree.
1 --> 1 * 1 |
2 + 3 --> (2 * 2) + (3 * 3) |
2 * 3 --> (2 * 2) * (3 * 3) |
We don't want to write the function just yet. Instead, we’ll add in a signature, purpose statement, and header for our function:
; Our type signature: |
; double : Calc -> Calc |
; |
; Our purpose statement: |
; takes a Calc AST node and multiplies each numE with itself. |
; |
; Our function header, which is just a stub that satisfies the signature: |
(define (double x) x) |
Again, we don't want to write the function just yet. Next, we’ll add in a functional examples:
;; double : Calc -> Calc |
;; |
;; Takes a Calc AST node and multiplies each numE with itself. |
;; |
;; Examples: |
;; (numE 1) --> (mulE (numE 1) (numE 1)) |
;; (addE (numE 2) (numE 3)) --> (addE (mulE (numE 1) (numE 1)) (mulE (numE 2) (numE 2))) |
;; (mulE (numE 2) (numE 3)) --> (mulE (mulE (numE 1) (numE 1)) (mulE (numE 2) (numE 2))) |
(define (double x) x) |
Our function template is our basic structural recursion pattern, which you should be familiar with: type-case
(define (double e) |
(type-case Calc e |
[(numE e) (numE e)] |
[(addE l r) (addE l r)] |
[(mulE l r) (mulE l r)])) |
> (define (double e) (type-case Calc e [(numE e) (mulE (numE e) (numE e))] [(addE l r) (addE (double l) (double r))] [(mulE l r) (mulE (double l) (double r))])) > (test (double (numE 1)) (mulE (numE 1) (numE 1)))
- Void
good (double (numE 1)) at line 4
expected: (mulE (numE 1) (numE 1))
given: (mulE (numE 1) (numE 1))
> (test (double (addE (numE 2) (numE 3))) (addE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3))))
- Void
good (double (addE (numE 2) (numE 3))) at line 5
expected: (addE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3)))
given: (addE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3)))
> (test (double (mulE (numE 2) (numE 3))) (mulE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3))))
- Void
good (double (mulE (numE 2) (numE 3))) at line 6
expected: (mulE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3)))
given: (mulE (mulE (numE 2) (numE 2)) (mulE (numE 3) (numE 3)))
It is crucial that you do the design process in this order. The design process replicates the scientific method! The design process turns programming into science but the beauty of code is that we can take ideas about the world and get instant feedback on our experiments.
8.3 Systematic Programing Language Design
Now that we have a recipe for designing programs, we can generalize this approach towards designing a language. When we think about the design recipe above, we are simply computing functions on trees, but now we want to understand the meaning of these trees.
Previously, we discussed a Design Recipe for Type-Checking and it should be no surprise that this is inspired directly from HtDP. We’ll elide types for now and go back to our runtime semantics. This time, modifications are shown in red:
From Language Analysis to Data Definitions: Identify the information that must be represented. Formulate data definitions (surface syntax, values, and abstract syntax) and illustrate them with examples.
Signature, Purpose Statement, Header: State what kind of data your interpreter consumes (the defined AST) and produces (Values? Numbers? Errors?). Formulate a concise answer to the question of what the languages semantics are. Define a stub that lives up to the signature.
Functional Examples: Work through examples that illustrate the interpreter’s purpose.
Function Template: Translate the AST definition into an outline of the interpreter.
Function Definition: Fill in the gaps in the function template. Exploit the purpose statement and the examples.
Testing: Articulate the examples as tests and ensure that the interpreter passes all. Doing so discovers mistakes. Tests also supplement examples in that they help others read and understand the definition when the need arises—and it will arise for any serious program.
8.3.1 Lambda with the Design Recipe
Let’s look at the untyped lambda calculus this time:
Write the small-step interpreter for the untyped lambda calculus.
We’ll start by better understanding what the lambda calculus is, that’s its grammar, and then I’ll introduce a second notation (which was touched on in homework 2) which we can use to describe our stepping rules.
Lambda is a simple language that only has three forms:
e ::= n -- numbers |
| x -- identifiers |
| (lambda (x) e) -- lambdas |
| (e e) -- applications |
|
Lambdas are both expressions, but also values – we’ll need a datatype for both of these:
> (define-type Lam (num [n : Number]) (var [name : Symbol]) (lam [arg : Symbol] [body : Lam]) (app [fn : Lam] [arg : Lam]))
Next we’ll define a signature, purpose statement, and header.
;; step : Lam -> Lam |
;; |
;; Purpose statement: |
;; step is a small-step interpreter for the untyped lambda calculus. |
;; |
;; Examples: |
;; |
;; 1 --> 1 step leaves values unchanged |
|
;; (lambda (x) x) |
;; --> (lambda (x) x) step leaves values unchanged |
;; |
;; (lambda (x) x) 1 |
;; --> 1 [cbv1] step with a function on the left, value on the right. |
;; |
;; 1 (lambda (x) x) |
;; --> error! stuck: there is no function on the left |
;; |
;; (lambda (x) (x 3)) (lambda (x) x) |
;; --> (lambda (x) x) 3 [cbv1] step with function on the left, value on the right. |
;; --> 3 [cbv1] step with function on the left, value on the right. |
;; |
;; ((lambda (x) (lambda (y) x)) 7) 9 |
;; --> (lambda (y) 7) 9 [cbv3] step the function position |
;; --> 7 [cbv2] substitute 9 for y |
(step : Lam -> Lam) |
(define (step e) e) |
Here, I’ve presented an alternative notation to step a program (although you saw it on hw2). We’ll return to this in a bit. For now, we need our small-step interpreter template:
(step : (Lam -> Lam)) |
(define (step e) |
(type-case Lam e |
[(num x) ...] |
[(var x) ...] |
[(lam x body) ...] |
[(app fn arg) |
(... (step fn) |
(step arg) ...)])) |
Filling these out follows the call-by-value semantics, which uses three rules.
[cbv1] Once the function and argument are values, apply the function.
[cbv2] If the function is a value but the argument is not, then evaluate it.
[cbv3] If the function is not a value, evaluate it until it is.
> (subst : (Symbol Lam Lam -> Lam))
> (define (subst id assignment body) (type-case Lam body [(num x) (num x)] [(var x) (if (equal? id x) assignment (var x))] [(app e1 e2) (app (subst id assignment e1) (subst id assignment e2))] [(lam x body) (if (equal? x id) (lam x body) (lam x (subst id assignment body)))])) > (step : (Lam -> Lam))
> (define (step e) (type-case Lam e [(num x) (num x)] [(var x) (error 'runtime "unbound variable")] [(lam x body) (lam x body)] [(app fn arg) (type-case Lam fn [(lam x body) (type-case Lam arg [(num n) (subst x (num n) body)] [(lam a b) (subst x (lam a b) body)] [else (app fn (step arg))])] [(app l r) (app (step fn) arg)] [else (error 'runtime "application on non-function")])])) > (test (step (num 1)) (num 1))
- Void
good (step (num 1)) at line 12
expected: (num 1)
given: (num 1)
> (test (step (lam 'x (var 'x))) (lam 'x (var 'x)))
- Void
good (step (lam (quote x) (var (quote x)))) at line 13
expected: (lam 'x (var 'x))
given: (lam 'x (var 'x))
> (test (step (app (lam 'x (var 'x)) (num 1))) (num 1))
- Void
good (step (app (lam (quote x) (var (quote x))) (num 1))) at line 14
expected: (num 1)
given: (num 1)
> (test/exn (step (app (num 1) (lam 'x (var 'x)))) "application on non-function")
- Void
good (step (app (num 1) (lam (quote x) (var (quote x))))) at line 15
expected: "application on non-function"
given: "runtime: application on non-function"
> (test (step (num 1)) (num 1))
- Void
good (step (num 1)) at line 16
expected: (num 1)
given: (num 1)
> (test (step (lam 'x (var 'x))) (lam 'x (var 'x)))
- Void
good (step (lam (quote x) (var (quote x)))) at line 17
expected: (lam 'x (var 'x))
given: (lam 'x (var 'x))
> (test (step (app (lam 'x (var 'x)) (num 1))) (num 1))
- Void
good (step (app (lam (quote x) (var (quote x))) (num 1))) at line 18
expected: (num 1)
given: (num 1)
> (test/exn (step (app (num 1) (lam 'x (var 'x)))) "application on non-function")
- Void
good (step (app (num 1) (lam (quote x) (var (quote x))))) at line 19
expected: "application on non-function"
given: "runtime: application on non-function"
> (define eid (lam 'x (var 'x))) > (define x3 (lam 'x (app (var 'x) (num 3)))) > (test (step (app x3 eid)) (app eid (num 3)))
- Void
good (step (app x3 eid)) at line 22
expected: (app (lam 'x (var 'x)) (num 3))
given: (app (lam 'x (var 'x)) (num 3))
> (test (step (step (app eid (num 3)))) (num 3))
- Void
good (step (step (app eid (num 3)))) at line 23
expected: (num 3)
given: (num 3)
8.3.2 From Program Traces to Evaluation Rules
Let’s look at those program traces once more.
We write wrote down small-step semantics, we used e \longrightarrow e{}’ to describe one call to our step function: the expression e produces the expression e{}’.
Let’s look at this --> notation with respect to our operational semantics.
8.3.2.1 Values
Numbers and lambda abstractions are values v. Our implementation returns values unchanged:
1 --> 1 |
(lambda (x) x) --> (lambda (x) x) |
We can describe both cases with one rule:
\frac{ }{v \longrightarrow v} \qquad \text{[val]}
There are no premises above the line. The conclusion below the line applies to any value.
8.3.2.2 Call-by-value
Our rules for call-by-value are then the following:
[cbv1] Once the function and argument are values, substitute:
(lambda (x) x) 1 --> 1
aka:
(lambda (x) body) value --> body[x ↦ value]
As an inference rule: \frac{}{ (\lambda x.\,e)\,v \longrightarrow e[x \mapsto v] } \qquad \text{[cbv3]}- [cbv2] if the function is a value but the argument is not, then evaluate it.
fn arg
_____________ __________________
(lambda (x) x) ((lambda (x) x) 1)
--> (lambda (x) x) 1
-------------- ---
fn arg
aka:
(lambda (x) body) e_arg --> (lambda (x) body) (step e_arg)
if e_arg not a value.
As an inference rule: \frac{ e_2 \text{ not a value} \qquad e_2 \longrightarrow e_2{}’ }{ (\lambda x.\,e_1)\,e_2 \longrightarrow (\lambda x.\,e_1)\,e_2{}’ } \qquad \text{[cbv2]}
- [cbv3] If the function is not a value, evaluate it until it is (the argument isn’t implicitly).
fn arg
_______________________________ ____
((lambda (x) x) (lambda (x) x)) 1
--> (lambda (x) x) 1
-------------- ---
fn arg
aka:
e_fn e_arg --> (step e_fn) e_arg if e_fn not a value.
Inference rule \frac{ e_1 \text{ not a value} \qquad e_1 \longrightarrow e_1{}’ }{ e_1\,e_2 \longrightarrow e_1{}’\,e_2 } \qquad \text{[cbv3]}