164 Midterm Prep

As of 12:35AM October 28th 2025, I am in poor shape.

FINAL PREP

• types
• constructors
• values

Expression: resolves to a value - returns anything but a Unit - ex: 3 Statement: expresses an action to be carried out - returns a Unit (equivalent to Null / Nil / no value in languages besides OCaml) - ex: print_endline "hi"

semicolon is an operator that errors if the program snippet on its left isn't an expression

Compiler Components

Source code --tokenizer(lexer)--> Tokens --parser--> AST --code gen--> Instructions --linker/assembler--> Binary

frontend: tokenizer and parser backend: code gen and linker/assembler

assembler: - takes in program.s - assembly -> machine code

linker: - links machine code chunks

---

S-expressions: lists containing symbols and numbers

compile.ml

compile function: - input: program - output: string of assembly representing that program

compile_to_file helper function that puts compile output in a file

runtime.c

• uses _entry from compile function from compile.ml

Compiler Correctness, Booleans

@ - list append operator

if we could throw our compiler away and run the program, it happens at runtime!

---

• cmp x y

  • if x - y = 0 (aka if x == y):
    • set zf to 1
  • else:
    • set zf to 0

• setz R

  • if ZF == 1:
    • set last byte of R to 1
  • else:
    • set last byte of R to 0

• jz L

  • if ZF == 1, jump to label L

• jmp L

  • jump to label L

anything not false behaves as true in our compiler

---

our language is: - dynamically typed - eagerly evaluated - function args get evaluated right when function is called, not when they're used within the func! - lexically scoped - For example, say we define a function f: (define (f x y) (+ (g x) (g y))). With lexical scope, we can refer to x and y in the body of f, but we can’t refer to them once we’re in the body of g, even though g is called by f. - https://stackoverflow.com/questions/22394089/static-lexical-scoping-vs-dynamic-scoping-pseudocode

Week 0

compiler : source_program -> target_program

Compilers take source code written in one language and return source code written in another language.

interpreter : source_program -> value

Interpreters take source code written in some language and return a value.

164 compiler : OCaml -> x86-64 machine code

• runtime is in C

entry function: the entry point to the code our compiler is producing

---

OCaml

• is a functional programming language
  • for each input, it always produces the same output
• has first-class functions
  • you can use functions as input to other functions, and produce functions as output
• has type inference
  • compiler automatically figures out most data types
• is statically-typed
  • detects type errors at compile time
• is type-safe
  • limits which kinds of operations can be performed on which kinds of data
• is primarily immutable
  • no side effects that update state when producing a return value

In the toplevel, running let x = 24;; returns val x : int = 42.

• "x has type int and equals 42."

Week 1

S-Expressions

type s_exp =
    Sym of string | Num of int | Lst of s_exp list

• Lst takes as its argument a list of other s-expressions.
  • fold_left

Unary Operations

Pipeline expressions: x |> f is the same as f x.

Dev environment

Works for Fall 2025

flake.nix

{
  description = "cs164";
  inputs = {
    nixpkgs.url = "github:nixos/nixpkgs?ref=nixos-unstable";
    systems.url = "github:nix-systems/default";
  };
  outputs = { self, nixpkgs, systems }:
    let
      pkgsFor = system: nixpkgs.legacyPackages.${system};
      forAllSystems = fn: nixpkgs.lib.genAttrs (import systems) (system: fn (pkgsFor system));
    in
    {
      packages = forAllSystems (pkgs: {
        default = pkgs.callPackage ./. { };
      });
      devShells = forAllSystems (pkgs: {
        default = pkgs.mkShell {
          inputsFrom = [ self.packages.${pkgs.system}.default ];
          #shellHook = "mkdocs serve";
        };
      });
      formatter = forAllSystems (pkgs: pkgs.nixpkgs-fmt);
    };
}

default.nix

{ pkgs }:

pkgs.stdenvNoCC.mkDerivation {
  name = "cs164";
  src = ./.;

  nativeBuildInputs = with pkgs; [
    ocaml
    dune_3
    ocamlPackages.findlib
    ocamlPackages.ounit2
    ocamlPackages.ppx_deriving
    ocamlPackages.menhir
    ocamlPackages.yojson
    ocamlPackages.janeStreet.shexp
    ocamlPackages.core_unix
    ocamlPackages.ppx_blob
    nasm

    # for examples in class notes
    libgccjit
  ];
}

In a directory with both of these files on a machine with Nix installed, run nix develop --extra-experimental-features nix-command --extra-experimental-features flakes. Remove flags if you have flakes or nix-command enabled systemwide.