Class Material

Chapter 1: Practical Functional Programming

Introduction

1. Introduction

Functional Programming: Expressions, Values, Types using TypeScript

2. Semantics of Programming Languages and Types

3. TypeScript: Complex Data Types, JSON, FP Processing of JSON

4. Type Checking

5. Data Types and Operations on Data

6. Composition and Monads

Chapter 2: Syntax and Semantics with Scheme

Defining a Programming Language Bottom-up: Elements of Programming

1. Elements of Programming - Defining Scheme Bottom-up

2.Higher-order Functions in Scheme and Local Variables

Syntax

3.Syntax of Programming Languages: BNF, Abstract Syntax Tree

4.Syntactic Operations: L1 Parsing, Type Guards, Scoping, Lexical Addresses, Syntactic Rewrites

Operational Semantics: Substitution-based Interpreter

5. Operational Semantics: L1 evaluation, environment

6. Substitution Model: L2 (ProcExp, IfExp), Closures, L3 (SExp), Error Processing, Applicative Order vs. Normal Order evaluation

Operational Semantics: Environment-based Interpreter

7. Environment Model, L4 evaluation, let evaluation, visual notation of environments, using closures, closure-based compound data structures

8. Recursion and Mutation

Chapter 3: Type Checking and Type Inference

1. Type Checking with Full Type Annotations

2. Type Inference

3. Type Inference System

Code

Type Checking (Code and Tests)

• TExp.ts: AST for the type language (to write type annotations)
• L5-ast.ts: AST for L5 with Type Annotations (same as L4-ast with type annotations)
• L5-env.ts: Environment for L5 (similar to L4-env-box.ts)
• L5-value.ts: Values definition for L5 (similar to L4-value-box.ts)
• L5-eval.ts: Interpreter for L5 with Type Annotations (similar to L4-eval-box.ts)
• evalPrimitive.ts: Primitive handling for L5 (same as L4 with type checking).
• TEnv.ts: Type Environments

• L5-typecheck.ts: Type Checker for fully type annotated L5 programs

• L5-eval.test.ts: Tests for L5 interpreter
• L5-typecheck.test.ts: Tests for type checker

Type Inference with Type Equations

• Substitution ADT: make-sub, sub-apply, sub-combine

• Type Equations Algorithm: L5-exp->pool, pool->equations, solve-equations, infer

• Substitution ADT Tests
• Type Equations Tests

Type Inference with Type Var Unification (Optimized Type Equations)

• Type Inference: checkEqualType with unification, check-no-occurrence, typeofExp

• Type Inference Tests

Chapter 4: Control Structures

• Asynchronous Programming, Promises and Generators
• Continuation Passing Style
• Lazy Lists and Generators in Scheme
• From Recursion to Iteration in TypeScript through CPS

Code

• Asynchronous code examples in Node.js: Promises and Generators
• coroutine1.rkt - Coroutines and Generators in Racket
• lzl.rkt - Lazy-lists in Racket

Deriving an iterative interpreter for L5 using CPS and Registerization

The following code relies on the files of the L5 interpreter from the previous chapter. Add the files to the same folder.

• sum.ts: Turning a recursive TypeScript function into iterative code in JavaScript - general method (CPS, concrete data structures for continuations, registerization, iteration).

• L6-eval.ts: A CPS version of the L5 interpreter (same AST as L5).

• L6-eval.tests.ts: Same tests as L5 using the L6 version.

• L7a-eval.ts: L6 CPS interpreter with explicit continuation ADT
• L7b-eval.ts: L6 CPS interpreter with concrete continuation data structures
• L7c-eval.ts: L6 CPS interpreter with registers and iterative interpreter.
• L7-tests.ts: Tests for L7c interpreter demonstrating that tail-recursive code is executed iteratively.

Chapter 5: Logic Programming

• Relational Logic Programming
• Logic Programming
• Logic Programming Interpreter in Scheme

Code

To install the full package of the Logic Programming system in Racket:

Clone the code from github

• Unzip it in a folder /ppl/src/logic
• Launch DrRacket
• Load the file “answer-query-test.rkt”
• Run the tests - it should print

  6 tests passed.
  5 tests passed.
  9 tests passed.
  

• LP-ast.rkt: AST for Logic Programming
• LP-ast-tests.rkt: AST tests and examples
• LP-rename.rkt: variable renaming
• substitution-ADT.rkt: Substitution ADT
• substitution-adt-tests.rkt: Substitution tests
• lazy-tree-ADT.rkt: Lazy tree ADT
• lazy-tree-ADT-tests.rkt: lazy tree tests
• auxiliary.rkt: auxiliary functions
• utils.rkt: Utility functions
• unify.rkt: unification algorithm
• term-equation-adt.rkt: term equation ADT (pair of terms)
• unify-tests.rkt: unification tests
• answer-query.rkt: answer-query algorithm
• answer-query-test.rkt: answer query tests