This class explored what programs mean and how languages work, starting from the untyped lambda calculus and ending with a small Haskell-like language with its own interpreter and REPL. Most of the work came as “projects” (graded as assignments), each focused on a different view of computation.

Project 0 – Lambda Calculus

Goal: get comfortable with computation as substitution only.

I:

• Stepped through equational proofs like NOT TRUE ⇒ FALSE and ADD TWO TWO ⇒ FOUR using only β-reduction and unfolding definitions (=a>, =b>, =d>).
• Wrote raw λ-terms for arithmetic and predicates (SKIP1, DEC, SUB, ISZ, EQL) and checked they reduce to the right numerals.

Example of the style of work:

AND TRUE FALSE
  =a> (\p q -> p q FALSE) TRUE FALSE
  =b> TRUE FALSE FALSE
  =a> (\x y -> x) FALSE FALSE
  =b> FALSE

Project 1 – Tail Recursion & Fixed Points

Focus: tail recursion and turning loops into higher-order functions.

I implemented:

• Tail-recursive helpers like assoc, removeDuplicates, and a generic “while”:

wwhile :: (a -> (Bool, a)) -> a -> a
wwhile f x0 = go x0
  where
    go x = let (cont, x') = f x
           in if cont then go x' else x'

• Fixed-point computations:
  • fixpointL f x0 → entire trajectory [x0, x1, …, xn]
  • fixpointW f x0 → just the final xn such that f xn == xn (e.g., Collatz or cosine).

Project 2 – Random Art

We turned an expression language into a picture generator.

I:

• Defined and pretty-printed an expression AST:

data Expr
  = VarX | VarY
  | Sine Expr | Cosine Expr
  | Average Expr Expr
  | Times Expr Expr
  | Thresh Expr Expr Expr Expr
  -- + two extra custom constructors in the assignment

• Wrote eval :: Double -> Double -> Expr -> Double that maps (x, y) ∈ [-1,1]^2 into [-1,1].
• Implemented build :: Int -> Expr to randomly generate expression trees of a given depth.
• Used the provided driver to generate grayscale and RGB PNGs; then added two new operators (one ternary) and extended exprToString, eval, and build to support them.

Project 3 – Folds & Big Integers

First part: getting fluent with folds.

• Rewrote standard patterns using folds:

sqSum :: [Int] -> Int
sqSum = foldl (\acc x -> acc + x * x) 0

pipe :: [a -> a] -> (a -> a)
pipe fs = foldl (.) id fs

• Built helpers like sepConcat and stringOfList to practice combining map + fold.

Second part: arbitrary-precision arithmetic using lists:

type BigInt = [Int]  -- e.g. [9,9,9,8] ≡ 9998

I:

• Implemented clone, padZero, removeZero.
• Wrote bigAdd, mulByDigit, and bigMul using folds and explicit carries, ensuring normalized results (no leading zeros, zero as []).

Project 4 – Nano: A Mini Haskell

Here we built a small functional language and its interpreter.

Core pieces:

data Expr
  = EInt Int | EBool Bool | ENil | EVar Id
  | EBin Binop Expr Expr
  | EIf Expr Expr Expr
  | ELet Id Expr Expr
  | ELam Id Expr
  | EApp Expr Expr
  deriving Eq

data Value
  = VInt Int | VBool Bool
  | VClos Env Id Expr      -- non-recursive function
  | VRec Id Env Id Expr    -- recursive function
  | VPrim (Value -> Value) -- builtins like head/tail
  | VNil | VCons Value Value

I:

• Implemented lookupId and eval :: Env -> Expr -> Value, including:
  • Integers, booleans, binary ops (+, -, *, ==, <, &&, ||, Cons).
  • Conditionals, let bindings, closures, recursion (VRec), and lists (ENil, Cons, head, tail).
• Wrote a lexer (Alex) and parser (Happy) that:
  • Tokenize identifiers, numbers, let, if/then/else, \x ->, list syntax [] and [a,b,c].
  • Parse expressions with correct precedence and associativity (application highest, || lowest, etc.).

Project 5 – Type Classes, Exceptions & REPL

Final project: combine data structures, monads, and a real interactive shell.

1. Sets via BST + QuickCheck
I implemented a binary search tree and set API:

data BST a = Leaf | Node a (BST a) (BST a)

contains :: Ord a => a -> BST a -> Bool
add      :: Ord a => a -> BST a -> BST a
remove   :: Ord a => a -> BST a -> BST a

Plus:

• build to construct a BST from a list and fold for in-order traversal.
• removeMin as a helper for remove.
• Several QuickCheck properties (e.g., prop_build, prop_add_isOrd, prop_remove_isOrd) and fixed a failing property about duplicates by adjusting the spec to match set semantics.

2. Exceptions with Either
Refactored evaluation to track exceptions explicitly:

evalE :: Env -> Expr -> Either Value Value
eval  :: Env -> Expr -> Value
eval env e = either id id (evalE env e)

I:

• Added EThr e and ETry e1 x e2 to Expr.
• Propagated exceptions through all constructs using monadic Either operations (no giant case nests).
• Implemented throw and try/catch semantics so thrown values can be caught and bound to a name.

3. Nano REPL
Finally, I built a small command-line REPL:

main :: IO ()
main = do
  setLocaleEncoding utf8
  replLoop 0 preludeEnv

Features:

• :quit – exit.
• :run file – parse and evaluate a Nano file, print the result.
• :load file – load top-level definitions into the environment (on top of the built-in prelude) and then:
  • Evaluate expressions that call those definitions interactively.
• Bare input lines are parsed as Nano expressions and evaluated in the current environment.

Overall, the projects walked from pure λ-calculus proofs, through Haskell recursion patterns and expression-driven graphics, to a fully working mini language + interpreter + REPL.