Fall 2024: CS 6520 Programming Languages

Week 1

Overview of this course. Shplait programming language basic overview.

Development template

1. Types: data representation
2. Tests: write function signature and tests
3. Template: write the layout of the function body
4. Body: finish function body case-by-case

Homework: Familiar with Shplait.

Week 2

Introduction of Shplait lists.

Homework: Natural recursion implementation with template.

Week 3

Binding and environment

• Binding: bind an expression to an variable.
• Environment: store the bindings.

Homework: Write a interpreter for Moe programming language using Shplait.

• Parse: parse Moe to Shplait data representation (expression).
• Subst: substitude identifiers with expressions.
• Interp: interpret expressions to integer.

Week 4

Lambda: function as values. We can also bind anonymous function to variable. Mutable states and stores.

• Box: store location of the value.
• Unbox: get the value of a given location.
• Setbox: update the value of a given location.

Homework: Implement Moe conditions and boolean. Also, implement thunks and force.

• Thunk: delay a computation, until it is called by force.
• Force: evaluate a thunk expression.

Week 5

Record: similar to C’s struct. A record can have a list of fields and values. Variable: mutable variable. Fluid let: syntax sugar. Instead of changing the interpreter, we can change the parser to genereate a let form that is matching fluid let.

Homework: Implement Moe begin and record initialization, access and mutation.

• Record: implement with Moe’s box expression.

Week 6

Syntax sugar and encoding Currying: a function takes an argument that returns another function takes another argument. Midterm: The concept of box is important! Think of box as a pointer, then everything is clear.

#true = fun(x) : fun(y) : x
#false = fun(x) : fun(y) : y

Week 7

letrec, mk_rec for encoding recursion. However, the problem with mk_rec is that we assuem the right hand side as a procedure. Use fun (): ... as a delay for implementing recursion. Optionof has two variants: none and some.

Homework: Implement syntax sugar for recursive bindings, recursive function and two arguments function.

Week 9

Lazy evaluation Continuation

Week 10

Trace continuation Garbage Collection Compiler

Homework: Implement neg, avg and support zero or multiple arguments for function call with continuation.

Week 11

Compiler Midterm

Homework: Implement a compiler that translate Moe with garbage collection.

Week 12

Class Inheritance

Homework: Implement instantiation, instanceof, select.

Week 13

Type checker checks types of the program before interpreting it.

Homework: Typechecker.

Week 14

Type checker with unify.

Homework: Typecheck if0 and list.

Week 15

Polymorphism

Homework: Parameterized over types and functions.

Week 16

Macro Programming Language research

Homework: final project