feat: functional options pattern

## Description

`iterator.Try` previously copied the entire iterator and synced it back on success, causing an unnecessary heap allocation on every call.
This PR simplifies `Try` to save and restore the index directly, and removes the now-unused `Copy` and `Sync` methods.

- Rewrite `ScanRune` and `ParseRawToken` as peek-then-advance, eliminating the need for `Try` at leaf level.
- Remove redundant `Try` wrappers from `parseExpression`, `parseAbstraction`, `parseApplication`, `parseLet`, and `parseToken`, which are already disambiguated by their callers.
- Keep `Try` only where true backtracking is needed: `parseStatement`, which must choose between `parseLet` and `parseDeclare`.
- Fix pre-existing panic in saccharine `parseExpression` when the iterator is exhausted (added `Done()` guard).

### Decisions

- `Try` now operates on the original iterator instead of a copy, removing the confusing pattern where the callback's `i` was a different object than the caller's `i`.
- Removed `parseSoftBreak` and `parseHardBreak` helper functions since `ParseRawToken` no longer needs `Try` wrapping.

## Benefits

- Eliminates a heap allocation per `Try` call.
- Reduces nesting and indirection in all parse functions.
- Makes the code easier to follow by removing the shadow-`i` pattern.
- `Try` is now only used at genuine choice points in the grammar.

## Checklist

- [x] Code follows conventional commit format.
- [x] Branch follows naming convention (`<type>/<description>`). Always use underscores.
- [x] Tests pass (if applicable).
- [x] Documentation updated (if applicable).

Reviewed-on: #47
Co-authored-by: M.V. Hutz <git@maximhutz.me>
Co-committed-by: M.V. Hutz <git@maximhutz.me>

.golangci.yml

@@ -48,7 +48,7 @@ linters:
       # More information: https://golangci-lint.run/usage/false-positives/#comments
       #
       # Please uncomment the following line if your code is not using the godoc format
-      - comments
+      # - comments
 
       # Common false positives
       # feel free to remove this if you don't have any false positives
@@ -126,6 +126,9 @@ linters:
         # Blank import should be only in a main or test package, or have a comment justifying it.
         - name: blank-imports
 
+        # Packages should have comments of the form "Package x ...".
+        - name: package-comments
+
         # context.Context() should be the first parameter of a function when provided as argument.
         - name: context-as-argument
           arguments:
@@ -157,6 +160,8 @@ linters:
           arguments:
             # make error messages clearer
             - "sayRepetitiveInsteadOfStutters"
+            # require comments on public interface methods
+            - "checkPublicInterface"
 
         # incrementing an integer variable by 1 is recommended to be done using the `++` operator
         - name: increment-decrement

Makefile

@@ -1,30 +1,53 @@
 BINARY_NAME=lambda
+TEST=simple
 
-.PHONY: help build docs test bench clean
+.PHONY: help build run profile explain graph docs test bench lint clean
 .DEFAULT_GOAL := help
 .SILENT:
 
 help:
 	echo "Available targets:"
 	echo "  build    - Build the lambda executable"
+	echo "  run      - Build and run the lambda runtime (use TEST=<name> to specify sample)"
+	echo "  profile  - Build and run with CPU profiling enabled"
+	echo "  explain  - Build and run with explanation mode and profiling"
+	echo "  graph    - Generate and open CPU profile visualization"
 	echo "  docs     - Start local godoc server on port 6060"
-	echo "  test     - Run tests"
-	echo "  bench    - Run benchmarks"
+	echo "  test     - Run tests for all samples"
+	echo "  bench    - Run benchmarks for all samples"
+	echo "  lint     - Run golangci-lint on all packages"
 	echo "  clean    - Remove all build artifacts"
 
 build:
 	go build -o ${BINARY_NAME} ./cmd/lambda
 	chmod +x ${BINARY_NAME}
 
+run: build
+	./${BINARY_NAME} -s -f ./tests/$(TEST).test -o program.out
+
+profile: build
+	./${BINARY_NAME} -p profile/cpu.prof -f ./tests/$(TEST).test -o program.out
+
+explain: build
+	./${BINARY_NAME} -x -p profile/cpu.prof -f ./tests/$(TEST).test -o program.out > explain.out
+
+graph:
+	go tool pprof -raw -output=profile/cpu.raw profile/cpu.prof
+	go tool pprof -svg profile/cpu.prof > profile/cpu.svg
+	echo ">>> View at 'file://$(PWD)/profile/cpu.svg'"
+
 docs:
 	echo ">>> View at 'http://localhost:6060/pkg/git.maximhutz.com/max/lambda/'"
 	go run golang.org/x/tools/cmd/godoc@latest -http=:6060
 
 test:
-	go test -v ./...
+	go test -v ./cmd/lambda
 
 bench:
-	go test -bench=. -benchtime=10x -cpu=4 ./...
+	go test -bench=. -benchtime=10x -cpu=4 ./cmd/lambda
+
+lint:
+	go run github.com/golangci/golangci-lint/v2/cmd/golangci-lint@latest run ./...
 
 clean:
 	rm -f ${BINARY_NAME}

cmd/lambda/convert.go

@@ -1,30 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var convertCmd = &cobra.Command{
-	Use:   "convert [input] [output]",
-	Short: "Convert between lambda calculus representations",
-	Long: `Convert lambda calculus expressions between different representations.
-
-The format is inferred from file extensions when possible.
-Use --from and --to flags to override format detection.`,
-	Example: `  lambda convert input.sch output.dbi
-  lambda convert input.txt output.txt --from saccharine --to lambda`,
-	Args: cobra.ExactArgs(2),
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	convertCmd.Flags().String("from", "", "source format")
-	convertCmd.Flags().String("to", "", "target format")
-	rootCmd.AddCommand(convertCmd)
-}

cmd/lambda/engine.go

@@ -1,21 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var engineCmd = &cobra.Command{
-	Use:   "engine",
-	Short: "List available evaluation engines",
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	rootCmd.AddCommand(engineCmd)
-}

cmd/lambda/lambda.go

@@ -0,0 +1,32 @@
+// Package main defines the 'lambda' command-line interface (CLI).
+package main
+
+import (
+	"os"
+
+	"github.com/spf13/cobra"
+)
+
+func Lambda() *cobra.Command {
+	cmd := &cobra.Command{
+		Use:   "lambda",
+		Short: "Lambda calculus interpreter",
+		Long:  "A lambda calculus interpreter supporting multiple representations.",
+		RunE: func(cmd *cobra.Command, _ []string) error {
+			return cmd.Help()
+		},
+	}
+
+	cmd.AddCommand(LambdaConvert())
+	cmd.AddCommand(LambdaEngine())
+	cmd.AddCommand(LambdaReduce())
+
+	return cmd
+}
+
+func main() {
+	lambda := Lambda()
+	if err := lambda.Execute(); err != nil {
+		os.Exit(1)
+	}
+}

cmd/lambda/lambda_convert.go

@@ -0,0 +1,95 @@
+package main
+
+import (
+	"fmt"
+	"os"
+	"path/filepath"
+	"strings"
+
+	"github.com/spf13/cobra"
+)
+
+// inferReprFromPath returns the repr type based on file extension.
+func inferReprFromPath(path string) (string, error) {
+	switch ext := strings.ToLower(filepath.Ext(path)); ext {
+	case ".lambda", ".lam", ".lc":
+		return "lambda", nil
+	case ".saccharine", ".sch":
+		return "saccharine", nil
+	default:
+		return "", fmt.Errorf("unknown file extension '%s'", ext)
+	}
+}
+
+func LambdaConvert() *cobra.Command {
+	var inputReprFlag, outputReprFlag string
+
+	cmd := &cobra.Command{
+		Use:          "convert <input-file> <output-file>",
+		Aliases:      []string{"conv"},
+		Short:        "Convert between lambda calculus representations",
+		SilenceUsage: true,
+		RunE: func(cmd *cobra.Command, args []string) error {
+			if len(args) != 2 {
+				return cmd.Help()
+			}
+
+			var err error
+			inputPath, outputPath := args[0], args[1]
+
+			// Use flag if provided, otherwise infer from extension.
+			inputRepr := inputReprFlag
+			if inputRepr == "" {
+				if inputRepr, err = inferReprFromPath(inputPath); err != nil {
+					return fmt.Errorf("input file: %w", err)
+				}
+			}
+
+			outputRepr := outputReprFlag
+			if outputRepr == "" {
+				if outputRepr, err = inferReprFromPath(outputPath); err != nil {
+					return fmt.Errorf("output file: %w", err)
+				}
+			}
+
+			// Read input file.
+			input, err := os.ReadFile(inputPath)
+			if err != nil {
+				return fmt.Errorf("reading input file: %w", err)
+			}
+
+			r := GetRegistry()
+
+			// Parse input into syntax tree.
+			repr, err := r.Unmarshal(string(input), inputRepr)
+			if err != nil {
+				return fmt.Errorf("parsing input: %w", err)
+			}
+
+			// Convert to output repr if different.
+			result, err := r.ConvertTo(repr, outputRepr)
+			if err != nil {
+				return fmt.Errorf("converting %s to %s: %w", inputRepr, outputRepr, err)
+			}
+
+			// Marshal output.
+			output, err := r.Marshal(result)
+			if err != nil {
+				return fmt.Errorf("unmarshaling output: %w", err)
+			}
+
+			// Write output file.
+			err = os.WriteFile(outputPath, []byte(output), 0644)
+			if err != nil {
+				return fmt.Errorf("writing output file: %w", err)
+			}
+
+			return nil
+		},
+	}
+
+	cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
+	cmd.Flags().StringVarP(&outputReprFlag, "output", "o", "", "Output representation (inferred from extension if unset)")
+
+	return cmd
+}

cmd/lambda/lambda_engine.go

@@ -0,0 +1,20 @@
+package main
+
+import (
+	"github.com/spf13/cobra"
+)
+
+func LambdaEngine() *cobra.Command {
+	cmd := &cobra.Command{
+		Use:     "engine",
+		Aliases: []string{"eng"},
+		Short:   "Information about available engines",
+		RunE: func(cmd *cobra.Command, _ []string) error {
+			return cmd.Help()
+		},
+	}
+
+	cmd.AddCommand(LambdaEngineList())
+
+	return cmd
+}

cmd/lambda/lambda_engine_list.go

@@ -0,0 +1,26 @@
+package main
+
+import (
+	"fmt"
+
+	"github.com/spf13/cobra"
+)
+
+func LambdaEngineList() *cobra.Command {
+	cmd := &cobra.Command{
+		Use:     "list",
+		Aliases: []string{"ls"},
+		Short:   "List available engines",
+		RunE: func(*cobra.Command, []string) error {
+			r := GetRegistry()
+
+			for engine := range r.ListEngines() {
+				fmt.Println(engine.Name())
+			}
+
+			return nil
+		},
+	}
+
+	return cmd
+}

cmd/lambda/lambda_reduce.go

@@ -0,0 +1,108 @@
+package main
+
+import (
+	"fmt"
+
+	"github.com/spf13/cobra"
+
+	"git.maximhutz.com/max/lambda/internal/cli"
+	"git.maximhutz.com/max/lambda/internal/registry"
+)
+
+func LambdaReduce() *cobra.Command {
+	var inputReprFlag string
+	var engineFlag string
+
+	cmd := &cobra.Command{
+		Use:          "reduce <input-file>",
+		Short:        "Reduce a lambda calculus expression",
+		SilenceUsage: true,
+		Aliases:      []string{"run"},
+		RunE: func(cmd *cobra.Command, args []string) error {
+			var err error
+			if len(args) != 1 {
+				return cmd.Help()
+			}
+
+			inputPath := args[0]
+
+			// Get input source.
+			var source cli.Source
+			if inputPath == "-" {
+				source = cli.StdinSource{}
+			} else {
+				source = cli.FileSource{Path: inputPath}
+			}
+
+			destination := cli.StdoutDestination{}
+
+			r := GetRegistry()
+
+			// Get input.
+			input, err := source.Extract()
+			if err != nil {
+				return err
+			}
+
+			// Use flag if provided, otherwise infer from extension.
+			inputRepr := inputReprFlag
+			if inputRepr == "" {
+				if inputRepr, err = inferReprFromPath(inputPath); err != nil {
+					return fmt.Errorf("input file: %w", err)
+				}
+			}
+
+			// Find engine.
+			var engine registry.Engine
+			if engineFlag == "" {
+				if engine, err = r.GetDefaultEngine(inputRepr); err != nil {
+					return err
+				}
+			} else {
+				if engine, err = r.GetEngine(engineFlag); err != nil {
+					return err
+				}
+			}
+
+			// Parse code into syntax tree.
+			repr, err := r.Unmarshal(input, inputRepr)
+			if err != nil {
+				return err
+			}
+
+			// Compile expression to lambda calculus.
+			compiled, err := r.ConvertTo(repr, "lambda")
+			if err != nil {
+				return err
+			}
+
+			// Create process.
+			process, err := engine.Load(compiled)
+			if err != nil {
+				return err
+			}
+
+			// Run reduction.
+			for process.Step(1) {
+			}
+
+			// Return the final reduced result.
+			result, err := process.Get()
+			if err != nil {
+				return err
+			}
+
+			output, err := r.Marshal(result)
+			if err != nil {
+				return err
+			}
+
+			return destination.Write(output)
+		},
+	}
+
+	cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
+	cmd.Flags().StringVarP(&engineFlag, "engine", "e", "", "Reduction engine (inferred from '--input' if unset)")
+
+	return cmd
+}

cmd/lambda/registry.go

@@ -0,0 +1,26 @@
+package main
+
+import (
+	"git.maximhutz.com/max/lambda/internal/registry"
+	"git.maximhutz.com/max/lambda/pkg/convert"
+	"git.maximhutz.com/max/lambda/pkg/engine/normalorder"
+	"git.maximhutz.com/max/lambda/pkg/lambda"
+	"git.maximhutz.com/max/lambda/pkg/saccharine"
+)
+
+func GetRegistry() *registry.Registry {
+	r := registry.New()
+
+	// Codecs
+	(registry.RegisterConversion(r, convert.Saccharine2Lambda, "saccharine", "lambda"))
+	(registry.RegisterConversion(r, convert.Lambda2Saccharine, "lambda", "saccharine"))
+
+	// Engines
+	(registry.RegisterEngine(r, normalorder.NewProcess, "normalorder", "lambda"))
+
+	// Marshalers
+	(registry.RegisterCodec(r, lambda.Codec{}, "lambda"))
+	(registry.RegisterCodec(r, saccharine.Codec{}, "saccharine"))
+
+	return r
+}

cmd/lambda/repl.go

@@ -1,27 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var replCmd = &cobra.Command{
-	Use:   "repl",
-	Short: "Start an interactive lambda calculus REPL",
-	Long: `Start an interactive Read-Eval-Print Loop for lambda calculus.
-
-Enter lambda expressions to evaluate them.
-Type 'exit' or 'quit' to leave the REPL.
-Press Ctrl+D to exit.`,
-	Example: `  lambda repl`,
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	rootCmd.AddCommand(replCmd)
-}

cmd/lambda/repr.go

@@ -1,21 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var reprCmd = &cobra.Command{
-	Use:   "repr",
-	Short: "List available representations",
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	rootCmd.AddCommand(reprCmd)
-}

cmd/lambda/root.go

@@ -1,19 +0,0 @@
-package main
-
-import (
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var rootCmd = &cobra.Command{
-	Use:   "lambda",
-	Short: "A lambda calculus interpreter and toolkit",
-	Long:  `Lambda is a CLI tool for working with lambda calculus expressions.`,
-}
-
-func main() {
-	if err := rootCmd.Execute(); err != nil {
-		os.Exit(1)
-	}
-}

cmd/lambda/run.go

@@ -1,31 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var runCmd = &cobra.Command{
-	Use:   "run [expression]",
-	Short: "Evaluate a lambda calculus expression",
-	Long: `Evaluate a lambda calculus expression and print the result.
-
-The expression can be provided as an argument, read from a file with --file,
-or piped through stdin.`,
-	Example: `  lambda run "\x.x"
-  echo "\x.x" | lambda run
-  lambda run --file program.sch
-  lambda run --file program.sch --engine krivine`,
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	runCmd.Flags().StringP("file", "f", "", "read expression from file")
-	runCmd.Flags().StringP("engine", "e", "normal", "evaluation engine to use")
-	rootCmd.AddCommand(runCmd)
-}

cmd/lambda/trace.go

@@ -1,28 +0,0 @@
-package main
-
-import (
-	"fmt"
-	"os"
-
-	"github.com/spf13/cobra"
-)
-
-var traceCmd = &cobra.Command{
-	Use:   "trace [file]",
-	Short: "Trace the evaluation of a lambda calculus expression",
-	Long: `Trace the step-by-step evaluation of a lambda calculus expression.
-
-This command shows each reduction step during evaluation.`,
-	Example: `  lambda trace program.sch
-  lambda trace program.sch --engine krivine`,
-	Args: cobra.ExactArgs(1),
-	Run: func(cmd *cobra.Command, args []string) {
-		fmt.Fprintln(os.Stderr, "not implemented")
-		os.Exit(1)
-	},
-}
-
-func init() {
-	traceCmd.Flags().StringP("engine", "e", "normal", "evaluation engine to use")
-	rootCmd.AddCommand(traceCmd)
-}

go.mod

@@ -2,13 +2,9 @@ module git.maximhutz.com/max/lambda
 
 go 1.25.5
 
-require github.com/stretchr/testify v1.11.1
+require github.com/spf13/cobra v1.10.2
 
 require (
-	github.com/davecgh/go-spew v1.1.1 // indirect
 	github.com/inconshreveable/mousetrap v1.1.0 // indirect
-	github.com/pmezard/go-difflib v1.0.0 // indirect
-	github.com/spf13/cobra v1.10.2 // indirect
-	github.com/spf13/pflag v1.0.9 // indirect
-	gopkg.in/yaml.v3 v3.0.1 // indirect
+	github.com/spf13/pflag v1.0.10 // indirect
 )

go.sum

@@ -1,18 +1,11 @@
 github.com/cpuguy83/go-md2man/v2 v2.0.6/go.mod h1:oOW0eioCTA6cOiMLiUPZOpcVxMig6NIQQ7OS05n1F4g=
-github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
-github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/inconshreveable/mousetrap v1.1.0 h1:wN+x4NVGpMsO7ErUn/mUI3vEoE6Jt13X2s0bqwp9tc8=
 github.com/inconshreveable/mousetrap v1.1.0/go.mod h1:vpF70FUmC8bwa3OWnCshd2FqLfsEA9PFc4w1p2J65bw=
-github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
-github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
 github.com/russross/blackfriday/v2 v2.1.0/go.mod h1:+Rmxgy9KzJVeS9/2gXHxylqXiyQDYRxCVz55jmeOWTM=
 github.com/spf13/cobra v1.10.2 h1:DMTTonx5m65Ic0GOoRY2c16WCbHxOOw6xxezuLaBpcU=
 github.com/spf13/cobra v1.10.2/go.mod h1:7C1pvHqHw5A4vrJfjNwvOdzYu0Gml16OCs2GRiTUUS4=
-github.com/spf13/pflag v1.0.9 h1:9exaQaMOCwffKiiiYk6/BndUBv+iRViNW+4lEMi0PvY=
 github.com/spf13/pflag v1.0.9/go.mod h1:McXfInJRrz4CZXVZOBLb0bTZqETkiAhM9Iw0y3An2Bg=
-github.com/stretchr/testify v1.11.1 h1:7s2iGBzp5EwR7/aIZr8ao5+dra3wiQyKjjFuvgVKu7U=
-github.com/stretchr/testify v1.11.1/go.mod h1:wZwfW3scLgRK+23gO65QZefKpKQRnfz6sD981Nm4B6U=
+github.com/spf13/pflag v1.0.10 h1:4EBh2KAYBwaONj6b2Ye1GiHfwjqyROoF4RwYO+vPwFk=
+github.com/spf13/pflag v1.0.10/go.mod h1:McXfInJRrz4CZXVZOBLb0bTZqETkiAhM9Iw0y3An2Bg=
 go.yaml.in/yaml/v3 v3.0.4/go.mod h1:DhzuOOF2ATzADvBadXxruRBLzYTpT36CKvDb3+aBEFg=
 gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
-gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
-gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=

internal/cli/cli.go

@@ -0,0 +1,2 @@
+// Package cli package provides various utilities to the 'lambda' program.
+package cli

internal/cli/destination.go

@@ -0,0 +1,29 @@
+package cli
+
+import (
+	"fmt"
+	"os"
+)
+
+// A Destination is method of writing output to the user.
+type Destination interface {
+	// Write data to this destination.
+	Write(data string) error
+}
+
+// An StdoutDestination writes to stdout.
+type StdoutDestination struct{}
+
+// Write outputs to standard output.
+func (d StdoutDestination) Write(data string) error {
+	fmt.Println(data)
+	return nil
+}
+
+// A FileDestination writes to a file.
+type FileDestination struct{ Path string }
+
+// Write outputs to a file.
+func (d FileDestination) Write(data string) error {
+	return os.WriteFile(d.Path, []byte(data+"\n"), 0644)
+}

internal/cli/source.go

@@ -0,0 +1,44 @@
+package cli
+
+import (
+	"io"
+	"os"
+)
+
+// A Source is a method of extracting input from the user.
+type Source interface {
+	// Extract fetches data from this source.
+	Extract() (string, error)
+}
+
+// A StringSource is defined by a string.
+type StringSource struct{ Data string }
+
+// Extract pulls input data from the internal string.
+func (s StringSource) Extract() (string, error) { return s.Data, nil }
+
+// A StdinSource pulls from standard input.
+type StdinSource struct{}
+
+// Extract pulls input data from standard input.
+func (s StdinSource) Extract() (string, error) {
+	data, err := io.ReadAll(os.Stdin)
+	if err != nil {
+		return "", err
+	}
+
+	return string(data), nil
+}
+
+// A FileSource reads from a file.
+type FileSource struct{ Path string }
+
+// Extract pulls input data from the file source.
+func (s FileSource) Extract() (string, error) {
+	data, err := os.ReadFile(s.Path)
+	if err != nil {
+		return "", err
+	}
+
+	return string(data), nil
+}

internal/registry/codec.go

@@ -0,0 +1,58 @@
+package registry
+
+import (
+	"fmt"
+	"reflect"
+
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+// A Codec is a type-erased codec that serializes and deserializes expressions
+// as Expr values, regardless of the underlying representation type.
+type Codec interface {
+	codec.Codec[Expr]
+
+	// InType returns the name of the representation this codec handles.
+	InType() string
+}
+
+// A registeredCodec adapts a typed codec.Codec[T] into the type-erased Codec
+// interface. It wraps decoded values into Expr on decode, and extracts the
+// underlying T from an Expr on encode.
+type registeredCodec[T any] struct {
+	codec  codec.Codec[T]
+	inType string
+}
+
+func (c registeredCodec[T]) Decode(s string) (Expr, error) {
+	t, err := c.codec.Decode(s)
+	if err != nil {
+		return nil, err
+	}
+
+	return NewExpr(c.inType, t), nil
+}
+
+func (c registeredCodec[T]) Encode(r Expr) (string, error) {
+	t, ok := r.Data().(T)
+	if !ok {
+		dataType := reflect.TypeOf(r.Data())
+		allowedType := reflect.TypeFor[T]()
+		return "", fmt.Errorf("Codec for '%s' cannot parse '%s'", allowedType, dataType)
+	}
+
+	return c.codec.Encode(t)
+}
+
+func (c registeredCodec[T]) InType() string { return c.inType }
+
+// RegisterCodec registers a typed codec under the given representation name.
+// Returns an error if a codec for that representation is already registered.
+func RegisterCodec[T any](registry *Registry, m codec.Codec[T], inType string) error {
+	if _, ok := registry.codecs[inType]; ok {
+		return fmt.Errorf("Codec for '%s' already registered", inType)
+	}
+
+	registry.codecs[inType] = registeredCodec[T]{m, inType}
+	return nil
+}

internal/registry/conversion.go

@@ -0,0 +1,59 @@
+package registry
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+// A Conversion is a type-erased transformation from one representation to
+// another. It operates on Expr values, hiding the underlying representation
+// types.
+type Conversion interface {
+	// InType returns the name of the source representation.
+	InType() string
+	// OutType returns the name of the target representation.
+	OutType() string
+
+	// Run applies the conversion to the given expression. Returns an error if
+	// the expression's data does not match the expected source type.
+	Run(Expr) (Expr, error)
+}
+
+// A registeredConversion adapts a typed codec.Conversion[T, U] into the
+// type-erased Conversion interface. It extracts the underlying T from an Expr,
+// applies the conversion, and wraps the result as a new Expr.
+type registeredConversion[T, U any] struct {
+	conversion      codec.Conversion[T, U]
+	inType, outType string
+}
+
+func (c registeredConversion[T, U]) Run(expr Expr) (Expr, error) {
+	t, ok := expr.Data().(T)
+	if !ok {
+		return nil, fmt.Errorf("could not parse '%v' as '%s'", t, c.inType)
+	}
+
+	u, err := c.conversion(t)
+	if err != nil {
+		return nil, err
+	}
+
+	return NewExpr(c.outType, u), nil
+}
+
+func (c registeredConversion[T, U]) InType() string { return c.inType }
+
+func (c registeredConversion[T, U]) OutType() string { return c.outType }
+
+// RegisterConversion registers a typed conversion function between two
+// representations.
+func RegisterConversion[T, U any](
+	registry *Registry,
+	conversion codec.Conversion[T, U],
+	inType, outType string,
+) error {
+	registry.converter.Add(registeredConversion[T, U]{conversion, inType, outType})
+
+	return nil
+}

internal/registry/converter.go

@@ -0,0 +1,30 @@
+package registry
+
+// A Converter is a directed graph of conversions between representations. Each
+// node is a representation name, and each edge is a Conversion.
+type Converter struct {
+	data map[string][]Conversion
+}
+
+// NewConverter creates an empty Converter with no registered conversions.
+func NewConverter() *Converter {
+	return &Converter{data: map[string][]Conversion{}}
+}
+
+// Add registers a conversion, adding an edge from its source representation
+// to its target representation.
+func (g *Converter) Add(c Conversion) {
+	conversionsFromIn, ok := g.data[c.InType()]
+	if !ok {
+		conversionsFromIn = []Conversion{}
+	}
+
+	conversionsFromIn = append(conversionsFromIn, c)
+	g.data[c.InType()] = conversionsFromIn
+}
+
+// ConversionsFrom returns all conversions that have the given representation
+// as their source type.
+func (g *Converter) ConversionsFrom(t string) []Conversion {
+	return g.data[t]
+}

internal/registry/engine.go

@@ -0,0 +1,58 @@
+package registry
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/engine"
+)
+
+// An Engine is a type-erased evaluation engine that can load an expression
+// into a runnable Process.
+type Engine interface {
+	// Load prepares an expression for evaluation, returning a Process. Returns
+	// an error if the expression's data does not match the engine's expected
+	// representation type.
+	Load(Expr) (Process, error)
+	// Name returns the name of this engine.
+	Name() string
+	// InType returns the name of the representation this engine operates on.
+	InType() string
+}
+
+// A registeredEngine adapts a typed engine.Engine[T] into the type-erased
+// Engine interface. It extracts the underlying T from an Expr before passing it
+// to the engine.
+type registeredEngine[T any] struct {
+	engine engine.Engine[T]
+	name   string
+	inType string
+}
+
+func (e registeredEngine[T]) InType() string { return e.inType }
+
+func (e registeredEngine[T]) Name() string { return e.name }
+
+func (e registeredEngine[T]) Load(expr Expr) (Process, error) {
+	t, ok := expr.Data().(T)
+	if !ok {
+		return nil, fmt.Errorf("incorrect format '%s' for engine '%s'", expr.Repr(), e.inType)
+	}
+
+	process, err := e.engine(t)
+	if err != nil {
+		return nil, err
+	}
+
+	return registeredProcess[T]{process, e.inType}, nil
+}
+
+// RegisterEngine registers a typed engine under the given name. Returns an
+// error if an engine with that name is already registered.
+func RegisterEngine[T any](registry *Registry, e engine.Engine[T], name, inType string) error {
+	if _, ok := registry.engines[name]; ok {
+		return fmt.Errorf("engine '%s' already registered", name)
+	}
+
+	registry.engines[name] = &registeredEngine[T]{e, name, inType}
+	return nil
+}

internal/registry/expr.go

@@ -0,0 +1,26 @@
+package registry
+
+// An Expr is a type-erased lambda calculus expression. It can have any type of
+// representation, so long as that type is known to the registry it is handled
+// by.
+type Expr interface {
+	// Repr returns the name of the underlying representation. Two expressions
+	// with the same Repr() are assumed to have the same representation type.
+	Repr() string
+
+	// Data returns the underlying expression data.
+	Data() any
+}
+
+// A baseExpr is the default implementation of Expr.
+type baseExpr struct {
+	id   string
+	data any
+}
+
+func (e baseExpr) Repr() string { return e.id }
+
+func (e baseExpr) Data() any { return e.data }
+
+// NewExpr creates an Expr with the given representation name and data.
+func NewExpr(id string, data any) Expr { return baseExpr{id, data} }

internal/registry/process.go

@@ -0,0 +1,35 @@
+package registry
+
+import (
+	"git.maximhutz.com/max/lambda/pkg/engine"
+)
+
+// A Process is a type-erased reduction process that operates on Expr values.
+type Process interface {
+	engine.Process[Expr]
+
+	// InType returns the name of the representation this process operates on.
+	InType() string
+}
+
+// A registeredProcess adapts a typed engine.Process[T] into the type-erased
+// Process interface. It wraps the result of Get into an Expr.
+type registeredProcess[T any] struct {
+	process engine.Process[T]
+	inType  string
+}
+
+func (p registeredProcess[T]) InType() string { return p.inType }
+
+func (p registeredProcess[T]) Get() (Expr, error) {
+	s, err := p.process.Get()
+	if err != nil {
+		return nil, err
+	}
+
+	return NewExpr(p.inType, s), nil
+}
+
+func (p registeredProcess[T]) Step(i int) bool {
+	return p.process.Step(i)
+}

internal/registry/registry.go

@@ -0,0 +1,153 @@
+// Package registry defines a structure to hold all available representations,
+// engines, and conversions between them.
+package registry
+
+import (
+	"fmt"
+	"iter"
+	"maps"
+)
+
+// A Registry holds all representations, conversions, codecs, and engines
+// available to the program.
+type Registry struct {
+	codecs    map[string]Codec
+	converter *Converter
+	engines   map[string]Engine
+}
+
+// New makes an empty registry.
+func New() *Registry {
+	return &Registry{
+		codecs:    map[string]Codec{},
+		converter: NewConverter(),
+		engines:   map[string]Engine{},
+	}
+}
+
+// GetEngine finds an engine based on its name. Returns an error if an engine
+// with that name cannot be found.
+func (r Registry) GetEngine(name string) (Engine, error) {
+	e, ok := r.engines[name]
+	if !ok {
+		return nil, fmt.Errorf("engine '%s' not found", name)
+	}
+
+	return e, nil
+}
+
+// ListEngines returns all available engines to the registry.
+func (r Registry) ListEngines() iter.Seq[Engine] {
+	return maps.Values(r.engines)
+}
+
+// GetDefaultEngine infers the preferred engine for a representation. Returns an
+// error if one cannot be chosen.
+func (r *Registry) GetDefaultEngine(id string) (Engine, error) {
+	for _, engine := range r.engines {
+		if engine.InType() == id {
+			return engine, nil
+		}
+	}
+
+	return r.GetEngine("normalorder")
+
+	// return nil, fmt.Errorf("no engine for '%s'", id)
+}
+
+// ConvertTo attempts to convert an expression of one type of representation to
+// another. Returns the converted expression, otherwise an error.
+//
+// It can convert between any two types of representations, given there is a
+// valid conversion path between them. It uses BFS to traverse a graph of
+// conversion edges, and converts along the shortest path.
+func (r *Registry) ConvertTo(expr Expr, outType string) (Expr, error) {
+	path, err := r.ConversionPath(expr.Repr(), outType)
+	if err != nil {
+		return nil, err
+	}
+
+	result := expr
+	for _, conversion := range path {
+		result, err = conversion.Run(result)
+		if err != nil {
+			return nil, fmt.Errorf("converting '%s' to '%s': %w", conversion.InType(), conversion.OutType(), err)
+		}
+	}
+
+	return result, err
+}
+
+// Marshal serializes an expression, given that representation has a codec.
+// Returns an error if the representation is not registered, or it has no codec.
+func (r *Registry) Marshal(expr Expr) (string, error) {
+	m, ok := r.codecs[expr.Repr()]
+	if !ok {
+		return "", fmt.Errorf("no marshaler for '%s'", expr.Repr())
+	}
+
+	return m.Encode(expr)
+}
+
+// Unmarshal deserializes an expression. Returns an error if the representation
+// or a codec for it is not registered.
+func (r *Registry) Unmarshal(s string, outType string) (Expr, error) {
+	m, ok := r.codecs[outType]
+	if !ok {
+		return nil, fmt.Errorf("no marshaler for '%s'", outType)
+	}
+
+	return m.Decode(s)
+}
+
+func reverse[T any](list []T) []T {
+	if list == nil {
+		return list
+	}
+
+	reversed := []T{}
+
+	for i := len(list) - 1; i >= 0; i-- {
+		reversed = append(reversed, list[i])
+	}
+
+	return reversed
+}
+
+// ConversionPath attempts to find a set of valid conversions that (if applied)
+// convert one representation to another. Returns an error if no path can be
+// found.
+func (r *Registry) ConversionPath(from, to string) ([]Conversion, error) {
+	backtrack := map[string]Conversion{}
+	iteration := []string{from}
+	for len(iteration) > 0 {
+		nextIteration := []string{}
+
+		for _, item := range iteration {
+			for _, conversion := range r.converter.ConversionsFrom(item) {
+				if _, ok := backtrack[conversion.OutType()]; ok {
+					continue
+				}
+
+				nextIteration = append(nextIteration, conversion.OutType())
+				backtrack[conversion.OutType()] = conversion
+			}
+		}
+
+		iteration = nextIteration
+	}
+
+	reversedPath := []Conversion{}
+	current := to
+	for current != from {
+		conversion, ok := backtrack[current]
+		if !ok {
+			return nil, fmt.Errorf("no valid conversion from '%s' to '%s'", from, to)
+		}
+
+		reversedPath = append(reversedPath, conversion)
+		current = conversion.InType()
+	}
+
+	return reverse(reversedPath), nil
+}

pkg/codec/codec.go

@@ -0,0 +1,20 @@
+// Package codec defines processes to convert between different representations
+// of lambda calculus, and serialize the different representations.
+package codec
+
+// A Conversion is a function that turns one representation into another.
+// Returns an error if the input expression cannot be converted.
+type Conversion[T, U any] = func(T) (U, error)
+
+// A Codec is an object that can serialize/deserialize one type of
+// representation. It is assumed that for any x ∋ T, Decode(Encode(x)) = x.
+type Codec[T any] interface {
+	// Encode takes an expression, and returns its serialized format, as a
+	// string. Returns an error if the expression cannot be serialized.
+	Encode(T) (string, error)
+
+	// Decode takes the serialized format of an expression, and returns its true
+	// value. Returns an error if the string doesn't correctly represent any
+	// valid expression.
+	Decode(string) (T, error)
+}

pkg/convert/saccharine_to_lambda.go

@@ -1,47 +1,49 @@
+// Package convert defined some standard conversions between various types of
+// representations.
 package convert
 
 import (
 	"fmt"
 
-	"git.maximhutz.com/max/lambda/pkg/repr/lambda"
-	"git.maximhutz.com/max/lambda/pkg/repr/saccharine"
+	"git.maximhutz.com/max/lambda/pkg/lambda"
+	"git.maximhutz.com/max/lambda/pkg/saccharine"
 )
 
-func convertAtom(n *saccharine.Variable) lambda.Expression {
-	return lambda.NewVariable(n.Name)
+func encodeAtom(n *saccharine.Atom) lambda.Expression {
+	return lambda.Variable{Name: n.Name}
 }
 
-func convertAbstraction(n *saccharine.Abstraction) lambda.Expression {
-	result := SaccharineToLambda(n.Body)
+func encodeAbstraction(n *saccharine.Abstraction) lambda.Expression {
+	result := encodeExpression(n.Body)
 
 	parameters := n.Parameters
 
 	// If the function has no parameters, it is a thunk. Lambda calculus still
 	// requires _some_ parameter exists, so generate one.
 	if len(parameters) == 0 {
-		freeVars := result.GetFree()
+		freeVars := lambda.GetFree(result)
 		freshName := lambda.GenerateFreshName(freeVars)
 		parameters = append(parameters, freshName)
 	}
 
 	for i := len(parameters) - 1; i >= 0; i-- {
-		result = lambda.NewAbstraction(parameters[i], result)
+		result = lambda.Abstraction{Parameter: parameters[i], Body: result}
 	}
 
 	return result
 }
 
-func convertApplication(n *saccharine.Application) lambda.Expression {
-	result := SaccharineToLambda(n.Abstraction)
+func encodeApplication(n *saccharine.Application) lambda.Expression {
+	result := encodeExpression(n.Abstraction)
 
 	arguments := []lambda.Expression{}
 	for _, argument := range n.Arguments {
-		convertedArgument := SaccharineToLambda(argument)
-		arguments = append(arguments, convertedArgument)
+		encodeedArgument := encodeExpression(argument)
+		arguments = append(arguments, encodeedArgument)
 	}
 
 	for _, argument := range arguments {
-		result = lambda.NewApplication(result, argument)
+		result = lambda.Application{Abstraction: result, Argument: argument}
 	}
 
 	return result
@@ -51,24 +53,24 @@ func reduceLet(s *saccharine.LetStatement, e lambda.Expression) lambda.Expressio
 	var value lambda.Expression
 
 	if len(s.Parameters) == 0 {
-		value = SaccharineToLambda(s.Body)
+		value = encodeExpression(s.Body)
 	} else {
-		value = convertAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
+		value = encodeAbstraction(&saccharine.Abstraction{Parameters: s.Parameters, Body: s.Body})
 	}
 
-	return lambda.NewApplication(
-		lambda.NewAbstraction(s.Name, e),
-		value,
-	)
+	return lambda.Application{
+		Abstraction: lambda.Abstraction{Parameter: s.Name, Body: e},
+		Argument:    value,
+	}
 }
 
 func reduceDeclare(s *saccharine.DeclareStatement, e lambda.Expression) lambda.Expression {
-	freshVar := lambda.GenerateFreshName(e.GetFree())
+	freshVar := lambda.GenerateFreshName(lambda.GetFree(e))
 
-	return lambda.NewApplication(
-		lambda.NewAbstraction(freshVar, e),
-		SaccharineToLambda(s.Value),
-	)
+	return lambda.Application{
+		Abstraction: lambda.Abstraction{Parameter: freshVar, Body: e},
+		Argument:    encodeExpression(s.Value),
+	}
 }
 
 func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Expression {
@@ -82,8 +84,8 @@ func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Express
 	}
 }
 
-func convertClause(n *saccharine.Clause) lambda.Expression {
-	result := SaccharineToLambda(n.Returns)
+func encodeClause(n *saccharine.Clause) lambda.Expression {
+	result := encodeExpression(n.Returns)
 
 	for i := len(n.Statements) - 1; i >= 0; i-- {
 		result = reduceStatement(n.Statements[i], result)
@@ -92,17 +94,45 @@ func convertClause(n *saccharine.Clause) lambda.Expression {
 	return result
 }
 
-func SaccharineToLambda(n saccharine.Expression) lambda.Expression {
-	switch n := n.(type) {
-	case *saccharine.Variable:
-		return convertAtom(n)
+func encodeExpression(s saccharine.Expression) lambda.Expression {
+	switch s := s.(type) {
+	case *saccharine.Atom:
+		return encodeAtom(s)
 	case *saccharine.Abstraction:
-		return convertAbstraction(n)
+		return encodeAbstraction(s)
 	case *saccharine.Application:
-		return convertApplication(n)
+		return encodeApplication(s)
 	case *saccharine.Clause:
-		return convertClause(n)
+		return encodeClause(s)
 	default:
-		panic(fmt.Errorf("unknown expression type: %T", n))
+		panic(fmt.Errorf("unknown expression type: %T", s))
 	}
 }
+
+func decodeExression(l lambda.Expression) saccharine.Expression {
+	switch l := l.(type) {
+	case lambda.Variable:
+		return &saccharine.Atom{Name: l.Name}
+	case lambda.Abstraction:
+		return &saccharine.Abstraction{
+			Parameters: []string{l.Parameter},
+			Body:       decodeExression(l.Body)}
+	case lambda.Application:
+		return &saccharine.Application{
+			Abstraction: decodeExression(l.Abstraction),
+			Arguments:   []saccharine.Expression{decodeExression(l.Argument)}}
+	default:
+		panic(fmt.Errorf("unknown expression type: %T", l))
+	}
+}
+
+// Lambda2Saccharine converts a pure lambda calculus expression into its
+// Saccharine counterpart.
+func Lambda2Saccharine(l lambda.Expression) (saccharine.Expression, error) {
+	return decodeExression(l), nil
+}
+
+// Saccharine2Lambda desugars a saccharine expression into pure lambda calculus.
+func Saccharine2Lambda(s saccharine.Expression) (lambda.Expression, error) {
+	return encodeExpression(s), nil
+}

pkg/engine/engine.go

@@ -1,23 +1,18 @@
+// Package engine defines a general process of reducing a lambda calculus
+// expression.
 package engine
 
-import (
-	"fmt"
+// A Process handles the reduction of a single expression.
+type Process[T any] interface {
+	// Get the current state of the process.
+	// Returns an error if the current state cannot be represented.
+	Get() (T, error)
 
-	"git.maximhutz.com/max/lambda/pkg/repr"
-)
-
-type Engine[R repr.Repr] interface {
-	Run(trace bool, count int) (Trace, bool)
-	Step() uint64
-	State() (repr.Repr, error)
-
-	fmt.Stringer
+	// Step performs reduction(s) on the representation. If the number of steps
+	// defined is less than zero, it will perform as many reductions as
+	// possible. Returns whether a reduction was performed.
+	Step(int) bool
 }
 
-type Trace interface {
-	Before() string
-	After() string
-	Step() uint64
-	TransitionName() string
-	TransitionNodes() string
-}
+// An Engine is an function that generates reduction processes.
+type Engine[T any] = func(T) (Process[T], error)

pkg/engine/normalorder/engine.go

@@ -0,0 +1,42 @@
+// Package normalorder contains an engine that reduces a 'lambda.Expression'
+// in the normal order.
+package normalorder
+
+import (
+	"git.maximhutz.com/max/lambda/pkg/engine"
+	"git.maximhutz.com/max/lambda/pkg/lambda"
+)
+
+type process struct {
+	expr lambda.Expression
+}
+
+func (e process) Get() (lambda.Expression, error) {
+	return e.expr, nil
+}
+
+func (e *process) Set(l lambda.Expression) error {
+	e.expr = l
+	return nil
+}
+
+func (e *process) Step(i int) bool {
+	for range i {
+		next, reduced := ReduceOnce(e.expr)
+		if !reduced {
+			return false
+		}
+
+		e.expr = next
+	}
+
+	return true
+}
+
+// NewProcess creates a new redution process.
+func NewProcess(expression lambda.Expression) (engine.Process[lambda.Expression], error) {
+	return &process{expr: expression}, nil
+}
+
+var _ engine.Process[lambda.Expression] = (*process)(nil)
+var _ engine.Engine[lambda.Expression] = NewProcess

pkg/engine/normalorder/reduce_once.go

@@ -0,0 +1,39 @@
+package normalorder
+
+import "git.maximhutz.com/max/lambda/pkg/lambda"
+
+// ReduceOnce attempts to apply a single reduction to a lambda expression.
+// It returns (1) the final expression (reduced, or not), and (2) whether or not
+// a reduction was applied.
+//
+// If a reduction is not applied, it returns the original expression.
+func ReduceOnce(e lambda.Expression) (lambda.Expression, bool) {
+	switch e := e.(type) {
+	case lambda.Abstraction:
+		body, reduced := ReduceOnce(e.Body)
+		if reduced {
+			return lambda.Abstraction{Parameter: e.Parameter, Body: body}, true
+		}
+		return e, false
+
+	case lambda.Application:
+		if fn, fnOk := e.Abstraction.(lambda.Abstraction); fnOk {
+			return lambda.Substitute(fn.Body, fn.Parameter, e.Argument), true
+		}
+
+		abs, reduced := ReduceOnce(e.Abstraction)
+		if reduced {
+			return lambda.Application{Abstraction: abs, Argument: e.Argument}, true
+		}
+
+		arg, reduced := ReduceOnce(e.Argument)
+		if reduced {
+			return lambda.Application{Abstraction: e.Abstraction, Argument: arg}, true
+		}
+
+		return e, false
+
+	default:
+		return e, false
+	}
+}

pkg/iterator/iterator.go

@@ -1,35 +1,25 @@
-/*
-Package "iterator"
-*/
+// Package iterator defines a generic way to iterator over a slice of data.
 package iterator
 
 import "fmt"
 
-// An iterator over slices.
+// An Iterator traverses over slices.
 type Iterator[T any] struct {
 	items []T
 	index int
 }
 
-// Create a new iterator, over a set of items.
+// Of creates a new iterator, over a set of defined items.
 func Of[T any](items []T) *Iterator[T] {
 	return &Iterator[T]{items: items, index: 0}
 }
 
-// Returns the current position of the iterator.
+// Index returns the current position of the iterator.
 func (i Iterator[T]) Index() int {
 	return i.index
 }
 
-func (i Iterator[T]) Copy() *Iterator[T] {
-	return &Iterator[T]{items: i.items, index: i.index}
-}
-
-func (i *Iterator[T]) Sync(o *Iterator[T]) {
-	i.index = o.index
-}
-
-// Create a new iterator, over a set of items.
+// Get returns the datum at the current position of the iterator.
 func (i Iterator[T]) Get() (T, error) {
 	var null T
 	if i.Done() {
@@ -39,22 +29,26 @@ func (i Iterator[T]) Get() (T, error) {
 	return i.items[i.index], nil
 }
 
+// MustGet is a version of Get, that panics if the datum cannot be returned.
 func (i Iterator[T]) MustGet() T {
-	var null T
-	if i.Done() {
-		return null
+	t, err := i.Get()
+	if err != nil {
+		panic(fmt.Errorf("cannot get current token: %w", err))
 	}
 
-	return i.items[i.index]
+	return t
 }
 
+// Forward increments the iterator if the iterator is not yet at the end of the
+// slice.
 func (i *Iterator[T]) Forward() {
 	if !i.Done() {
 		i.index++
 	}
 }
 
-// Create a new iterator, over a set of items.
+// Next attempts to increment the iterator. Returns an error if it cannot be
+// incremented.
 func (i *Iterator[T]) Next() (T, error) {
 	item, err := i.Get()
 	if err == nil {
@@ -64,22 +58,37 @@ func (i *Iterator[T]) Next() (T, error) {
 	return item, err
 }
 
-// Create a new iterator, over a set of items.
+// Back decrements the iterator. If the iterator is already at the beginning of
+// the slice, this is a no-op.
 func (i *Iterator[T]) Back() {
 	i.index = max(i.index-1, 0)
 }
 
-// Returns the current position of the iterator.
+// Done returns whether the iterator is at the end of the slice or not.
 func (i Iterator[T]) Done() bool {
 	return i.index == len(i.items)
 }
 
-func Do[T any, U any](i *Iterator[T], fn func(i *Iterator[T]) (U, error)) (U, error) {
-	i2 := i.Copy()
+// While increments the iterator as long as the current item satisfies the
+// predicate. The first item that does not match is left unconsumed.
+func (i *Iterator[T]) While(fn func(T) bool) {
+	for !i.Done() {
+		if !fn(i.MustGet()) {
+			return
+		}
+		i.Forward()
+	}
+}
 
-	out, err := fn(i2)
-	if err == nil {
-		i.Sync(i2)
+// Try attempts to perform an operation using the iterator. If the operation
+// succeeds, the iterator keeps its new position. If the operation fails, the
+// iterator is rolled back, and an error is returned.
+func Try[T any, U any](i *Iterator[T], fn func(i *Iterator[T]) (U, error)) (U, error) {
+	saved := i.index
+
+	out, err := fn(i)
+	if err != nil {
+		i.index = saved
 	}
 
 	return out, err

pkg/lambda/codec.go

@@ -0,0 +1,27 @@
+package lambda
+
+import (
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+// A Codec is a [codec.Codec] that serializes lambda calculus expressions.
+type Codec struct{}
+
+// Decode parses a string as lambda calculus.
+// Returns an error if it cannot.
+func (m Codec) Decode(s string) (Expression, error) {
+	tokens, err := scan(s)
+	if err != nil {
+		return nil, err
+	}
+
+	return parse(tokens)
+}
+
+// Encode turns a lambda calculus expression into a string.
+// Returns an error if it cannot.
+func (m Codec) Encode(e Expression) (string, error) {
+	return Stringify(e), nil
+}
+
+var _ codec.Codec[Expression] = (*Codec)(nil)

pkg/lambda/get_free_variables.go

@@ -0,0 +1,27 @@
+package lambda
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/set"
+)
+
+// GetFree returns the set of all free variable names in the expression.
+// This function does not mutate the input expression.
+// The returned set is newly allocated and can be modified by the caller.
+func GetFree(e Expression) set.Set[string] {
+	switch e := e.(type) {
+	case Variable:
+		return set.New(e.Name)
+	case Abstraction:
+		vars := GetFree(e.Body)
+		vars.Remove(e.Parameter)
+		return vars
+	case Application:
+		vars := GetFree(e.Abstraction)
+		vars.Merge(GetFree(e.Argument))
+		return vars
+	default:
+		panic(fmt.Errorf("unknown expression type: %v", e))
+	}
+}

pkg/lambda/is_free_variable.go

@@ -0,0 +1,18 @@
+package lambda
+
+import "fmt"
+
+// IsFree returns true if the variable name n occurs free in the expression.
+// This function does not mutate the input expression.
+func IsFree(e Expression, n string) bool {
+	switch e := e.(type) {
+	case Variable:
+		return e.Name == n
+	case Abstraction:
+		return e.Parameter != n && IsFree(e.Body, n)
+	case Application:
+		return IsFree(e.Abstraction, n) || IsFree(e.Argument, n)
+	default:
+		panic(fmt.Errorf("unknown expression type: %v", e))
+	}
+}

pkg/lambda/lambda.go

@@ -0,0 +1,31 @@
+// Package lambda defines the AST for the untyped lambda calculus.
+package lambda
+
+// An Expression is a node in the lambda calculus abstract syntax tree.
+// It is a sealed interface; only types in this package may implement it.
+type Expression interface {
+	expression()
+}
+
+// An Abstraction binds a single parameter over a body expression.
+type Abstraction struct {
+	Parameter string
+	Body      Expression
+}
+
+func (a Abstraction) expression() {}
+
+// An Application applies an abstraction to a single argument.
+type Application struct {
+	Abstraction Expression
+	Argument    Expression
+}
+
+func (a Application) expression() {}
+
+// A Variable is a named reference to a bound or free variable.
+type Variable struct {
+	Name string
+}
+
+func (v Variable) expression() {}

pkg/lambda/parse.go

@@ -0,0 +1,80 @@
+package lambda
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/iterator"
+	"git.maximhutz.com/max/lambda/pkg/token"
+)
+
+type tokenIterator = iterator.Iterator[lambdaToken]
+
+func parseVariable(i *tokenIterator) (Expression, error) {
+	if tok, err := token.ParseRawToken(i, tokenAtom); err != nil {
+		return nil, fmt.Errorf("expected variable (col %d): %w", i.Index(), err)
+	} else {
+		return Variable{Name: tok.Value}, nil
+	}
+}
+
+func parseAbstraction(i *tokenIterator) (Expression, error) {
+	if _, err := token.ParseRawToken(i, tokenSlash); err != nil {
+		return nil, fmt.Errorf("no backslash (col %d): %w", i.Index(), err)
+	} else if param, err := token.ParseRawToken(i, tokenAtom); err != nil {
+		return nil, fmt.Errorf("no param (col %d): %w", i.Index(), err)
+	} else if _, err := token.ParseRawToken(i, tokenDot); err != nil {
+		return nil, fmt.Errorf("no dot (col %d): %w", i.Index(), err)
+	} else if body, err := parseExpression(i); err != nil {
+		return nil, err
+	} else {
+		return Abstraction{Parameter: param.Value, Body: body}, nil
+	}
+}
+
+func parseApplication(i *tokenIterator) (Expression, error) {
+	if _, err := token.ParseRawToken(i, tokenOpenParen); err != nil {
+		return nil, fmt.Errorf("no opening paren (col %d): %w", i.Index(), err)
+	} else if abstraction, err := parseExpression(i); err != nil {
+		return nil, fmt.Errorf("expected function expression: %w", err)
+	} else if argument, err := parseExpression(i); err != nil {
+		return nil, fmt.Errorf("expected argument expression: %w", err)
+	} else if _, err := token.ParseRawToken(i, tokenCloseParen); err != nil {
+		return nil, fmt.Errorf("no closing paren (col %d): %w", i.Index(), err)
+	} else {
+		return Application{Abstraction: abstraction, Argument: argument}, nil
+	}
+}
+
+func parseExpression(i *tokenIterator) (Expression, error) {
+	peek, err := i.Get()
+	if err != nil {
+		return nil, err
+	}
+
+	switch peek.Type {
+	case tokenOpenParen:
+		return parseApplication(i)
+	case tokenSlash:
+		return parseAbstraction(i)
+	case tokenAtom:
+		return parseVariable(i)
+	default:
+		return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
+	}
+}
+
+// parse converts a token slice into a lambda calculus expression.
+func parse(tokens []lambdaToken) (Expression, error) {
+	i := iterator.Of(tokens)
+
+	exp, err := parseExpression(i)
+	if err != nil {
+		return nil, err
+	}
+
+	if !i.Done() {
+		return nil, fmt.Errorf("expected EOF, found more tokens (col %d)", i.MustGet().Column)
+	}
+
+	return exp, nil
+}

pkg/lambda/rename.go

@@ -0,0 +1,31 @@
+package lambda
+
+import "fmt"
+
+// Rename replaces all occurrences of the target variable name with the new name.
+func Rename(e Expression, target string, newName string) Expression {
+	switch e := e.(type) {
+	case Variable:
+		if e.Name == target {
+			return Variable{Name: newName}
+		}
+
+		return e
+	case Abstraction:
+		newParam := e.Parameter
+		if e.Parameter == target {
+			newParam = newName
+		}
+
+		newBody := Rename(e.Body, target, newName)
+
+		return Abstraction{Parameter: newParam, Body: newBody}
+	case Application:
+		newAbs := Rename(e.Abstraction, target, newName)
+		newArg := Rename(e.Argument, target, newName)
+
+		return Application{Abstraction: newAbs, Argument: newArg}
+	default:
+		panic(fmt.Errorf("unknown expression type: %v", e))
+	}
+}

pkg/lambda/scan.go

@@ -0,0 +1,18 @@
+package lambda
+
+import "git.maximhutz.com/max/lambda/pkg/token"
+
+// scanner is the declarative lexer for the lambda calculus.
+var scanner = token.NewScanner(
+	token.On(`\(`, tokenOpenParen, 0),
+	token.On(`\)`, tokenCloseParen, 0),
+	token.On(`\\`, tokenSlash, 0),
+	token.On(`\.`, tokenDot, 0),
+	token.On(`[a-zA-Z0-9_]+`, tokenAtom, 0),
+	token.Skip[tokenType](`\s+`, 0),
+)
+
+// scan tokenizes an input string into lambda calculus tokens.
+func scan(input string) ([]lambdaToken, error) {
+	return scanner.Scan(input)
+}

pkg/lambda/stringify.go

@@ -0,0 +1,17 @@
+package lambda
+
+import "fmt"
+
+// Stringify turns an expression as a string.
+func Stringify(e Expression) string {
+	switch e := e.(type) {
+	case Variable:
+		return e.Name
+	case Abstraction:
+		return "\\" + e.Parameter + "." + Stringify(e.Body)
+	case Application:
+		return "(" + Stringify(e.Abstraction) + " " + Stringify(e.Argument) + ")"
+	default:
+		panic(fmt.Errorf("unknown expression type: %v", e))
+	}
+}

pkg/lambda/substitute.go

@@ -0,0 +1,41 @@
+package lambda
+
+import "fmt"
+
+// Substitute replaces all free occurrences of the target variable with the
+// replacement expression. Alpha-renaming is performed automatically to
+// avoid variable capture.
+func Substitute(e Expression, target string, replacement Expression) Expression {
+	switch e := e.(type) {
+	case Variable:
+		if e.Name == target {
+			return replacement
+		}
+
+		return e
+	case Abstraction:
+		if e.Parameter == target {
+			return e
+		}
+
+		body := e.Body
+		param := e.Parameter
+		if IsFree(replacement, param) {
+			freeVars := GetFree(replacement)
+			freeVars.Merge(GetFree(body))
+			freshVar := GenerateFreshName(freeVars)
+			body = Rename(body, param, freshVar)
+			param = freshVar
+		}
+
+		newBody := Substitute(body, target, replacement)
+		return Abstraction{Parameter: param, Body: newBody}
+	case Application:
+		abs := Substitute(e.Abstraction, target, replacement)
+		arg := Substitute(e.Argument, target, replacement)
+
+		return Application{Abstraction: abs, Argument: arg}
+	default:
+		panic(fmt.Errorf("unknown expression type: %v", e))
+	}
+}

pkg/lambda/token.go

@@ -0,0 +1,45 @@
+package lambda
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/token"
+)
+
+// A tokenType is an identifier for any token in the lambda calculus.
+type tokenType int
+
+// All official tokens of the lambda calculus.
+const (
+	// tokenOpenParen denotes the '(' token.
+	tokenOpenParen tokenType = iota
+	// tokenCloseParen denotes the ')' token.
+	tokenCloseParen
+	// tokenSlash denotes the '\' token.
+	tokenSlash
+	// tokenDot denotes the '.' token.
+	tokenDot
+	// tokenAtom denotes an alpha-numeric variable.
+	tokenAtom
+)
+
+// Name returns the type of the tokenType, as a string.
+func (t tokenType) Name() string {
+	switch t {
+	case tokenOpenParen:
+		return "("
+	case tokenCloseParen:
+		return ")"
+	case tokenSlash:
+		return "\\"
+	case tokenDot:
+		return "."
+	case tokenAtom:
+		return "ATOM"
+	default:
+		panic(fmt.Errorf("unknown token type %v", t))
+	}
+}
+
+// lambdaToken is the concrete token type for the lambda calculus.
+type lambdaToken = token.Token[tokenType]

pkg/repr/lambda/expression.go

@@ -1,87 +0,0 @@
-package lambda
-
-import (
-	"git.maximhutz.com/max/lambda/pkg/repr"
-	"git.maximhutz.com/max/lambda/pkg/set"
-)
-
-// Expression is the interface for all lambda calculus expression types.
-// It embeds the general expr.Expression interface for cross-mode compatibility.
-type Expression interface {
-	repr.Repr
-
-	// Substitute replaces all free occurrences of the target variable with the
-	// replacement expression. Alpha-renaming is performed automatically to
-	// avoid variable capture.
-	Substitute(target string, replacement Expression) Expression
-
-	// GetFree returns the set of all free variable names in the expression.
-	// This function does not mutate the input expression.
-	// The returned set is newly allocated and can be modified by the caller.
-	GetFree() set.Set[string]
-
-	// Rename replaces all occurrences of the target variable name with the new name.
-	Rename(target string, newName string) Expression
-
-	// IsFree returns true if the variable name n occurs free in the expression.
-	// This function does not mutate the input expression.
-	IsFree(n string) bool
-}
-
-var (
-	_ Expression = Abstraction{}
-	_ Expression = Application{}
-	_ Expression = Variable{}
-)
-
-/** ------------------------------------------------------------------------- */
-
-type Abstraction struct {
-	parameter string
-	body      Expression
-}
-
-func (a Abstraction) Parameter() string {
-	return a.parameter
-}
-
-func (a Abstraction) Body() Expression {
-	return a.body
-}
-
-func NewAbstraction(parameter string, body Expression) Abstraction {
-	return Abstraction{parameter, body}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type Application struct {
-	abstraction Expression
-	argument    Expression
-}
-
-func (a Application) Abstraction() Expression {
-	return a.abstraction
-}
-
-func (a Application) Argument() Expression {
-	return a.argument
-}
-
-func NewApplication(abstraction Expression, argument Expression) Application {
-	return Application{abstraction, argument}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type Variable struct {
-	name string
-}
-
-func (v Variable) Name() string {
-	return v.name
-}
-
-func NewVariable(name string) Variable {
-	return Variable{name}
-}

pkg/repr/lambda/get_free_variables.go

@@ -1,19 +0,0 @@
-package lambda
-
-import "git.maximhutz.com/max/lambda/pkg/set"
-
-func (e Variable) GetFree() set.Set[string] {
-	return set.New(e.Name())
-}
-
-func (e Abstraction) GetFree() set.Set[string] {
-	vars := e.Body().GetFree()
-	vars.Remove(e.Parameter())
-	return vars
-}
-
-func (e Application) GetFree() set.Set[string] {
-	vars := e.Abstraction().GetFree()
-	vars.Merge(e.Argument().GetFree())
-	return vars
-}

pkg/repr/lambda/is_free_variable.go

@@ -1,12 +0,0 @@
-package lambda
-
-func (e Variable) IsFree(n string) bool {
-	return e.Name() == n
-}
-
-func (e Abstraction) IsFree(n string) bool {
-	return e.Parameter() != n && e.Body().IsFree(n)
-}
-func (e Application) IsFree(n string) bool {
-	return e.Abstraction().IsFree(n) || e.Argument().IsFree(n)
-}

pkg/repr/lambda/rename.go

@@ -1,28 +0,0 @@
-package lambda
-
-// Rename replaces all occurrences of the target variable name with the new name.
-func (e Variable) Rename(target string, newName string) Expression {
-	if e.Name() == target {
-		return NewVariable(newName)
-	}
-
-	return e
-}
-
-func (e Abstraction) Rename(target string, newName string) Expression {
-	newParam := e.Parameter()
-	if e.Parameter() == target {
-		newParam = newName
-	}
-
-	newBody := e.Body().Rename(target, newName)
-
-	return NewAbstraction(newParam, newBody)
-}
-
-func (e Application) Rename(target string, newName string) Expression {
-	newAbs := e.Abstraction().Rename(target, newName)
-	newArg := e.Argument().Rename(target, newName)
-
-	return NewApplication(newAbs, newArg)
-}

pkg/repr/lambda/substitute.go

@@ -1,35 +0,0 @@
-package lambda
-
-func (e Variable) Substitute(target string, replacement Expression) Expression {
-	if e.Name() == target {
-		return replacement
-	}
-
-	return e
-}
-
-func (e Abstraction) Substitute(target string, replacement Expression) Expression {
-	if e.Parameter() == target {
-		return e
-	}
-
-	body := e.Body()
-	param := e.Parameter()
-	if replacement.IsFree(param) {
-		freeVars := replacement.GetFree()
-		freeVars.Merge(body.GetFree())
-		freshVar := GenerateFreshName(freeVars)
-		body = body.Rename(param, freshVar)
-		param = freshVar
-	}
-
-	newBody := body.Substitute(target, replacement)
-	return NewAbstraction(param, newBody)
-}
-
-func (e Application) Substitute(target string, replacement Expression) Expression {
-	abs := e.Abstraction().Substitute(target, replacement)
-	arg := e.Argument().Substitute(target, replacement)
-
-	return NewApplication(abs, arg)
-}

pkg/repr/repr.go

@@ -1,4 +0,0 @@
-package repr
-
-type Repr interface {
-}

pkg/repr/saccharine/expression.go

@@ -1,59 +0,0 @@
-package saccharine
-
-import (
-	"git.maximhutz.com/max/lambda/pkg/repr"
-)
-
-type Expression interface {
-	repr.Repr
-}
-
-var (
-	_ Expression = Abstraction{}
-	_ Expression = Application{}
-	_ Expression = Variable{}
-	_ Expression = Clause{}
-)
-
-/** ------------------------------------------------------------------------- */
-
-type Abstraction struct {
-	Parameters []string
-	Body       Expression
-}
-
-func NewAbstraction(parameter []string, body Expression) *Abstraction {
-	return &Abstraction{Parameters: parameter, Body: body}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type Application struct {
-	Abstraction Expression
-	Arguments   []Expression
-}
-
-func NewApplication(abstraction Expression, arguments []Expression) *Application {
-	return &Application{Abstraction: abstraction, Arguments: arguments}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type Variable struct {
-	Name string
-}
-
-func NewVariable(name string) *Variable {
-	return &Variable{Name: name}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type Clause struct {
-	Statements []Statement
-	Returns    Expression
-}
-
-func NewClause(statements []Statement, returns Expression) *Clause {
-	return &Clause{Statements: statements, Returns: returns}
-}

pkg/repr/saccharine/parse.go

@@ -1,237 +0,0 @@
-package saccharine
-
-import (
-	"errors"
-	"fmt"
-
-	"git.maximhutz.com/max/lambda/pkg/iterator"
-	"git.maximhutz.com/max/lambda/pkg/trace"
-)
-
-type TokenIterator = iterator.Iterator[Token]
-
-func parseRawToken(i *TokenIterator, expected Type) (*Token, error) {
-	return iterator.Do(i, func(i *TokenIterator) (*Token, error) {
-		if tok, err := i.Next(); err != nil {
-			return nil, err
-		} else if tok.Type != expected {
-			return nil, fmt.Errorf("expected token %v, got %v'", Name(expected), tok.Value)
-		} else {
-			return &tok, nil
-		}
-	})
-}
-
-func passSoftBreaks(i *TokenIterator) {
-	for {
-		if _, err := parseRawToken(i, TokenSoftBreak); err != nil {
-			return
-		}
-	}
-}
-
-func parseToken(i *TokenIterator, expected Type, ignoreSoftBreaks bool) (*Token, error) {
-	return iterator.Do(i, func(i *TokenIterator) (*Token, error) {
-		if ignoreSoftBreaks {
-			passSoftBreaks(i)
-		}
-
-		return parseRawToken(i, expected)
-	})
-}
-
-func parseString(i *TokenIterator) (string, error) {
-	if tok, err := parseToken(i, TokenAtom, true); err != nil {
-		return "", trace.Wrap(err, "no variable (col %d)", i.Index())
-	} else {
-		return tok.Value, nil
-	}
-}
-
-func parseBreak(i *TokenIterator) (*Token, error) {
-	if tok, softErr := parseRawToken(i, TokenSoftBreak); softErr == nil {
-		return tok, nil
-	} else if tok, hardErr := parseRawToken(i, TokenHardBreak); hardErr == nil {
-		return tok, nil
-	} else {
-		return nil, errors.Join(softErr, hardErr)
-	}
-}
-
-func parseList[U any](i *TokenIterator, fn func(*TokenIterator) (U, error), minimum int) ([]U, error) {
-	results := []U{}
-
-	for {
-		if u, err := fn(i); err != nil {
-			if len(results) < minimum {
-				return nil, trace.Wrap(err, "expected at least '%v' items, got only '%v'", minimum, len(results))
-			}
-			return results, nil
-		} else {
-			results = append(results, u)
-		}
-	}
-}
-
-func parseAbstraction(i *TokenIterator) (*Abstraction, error) {
-	return iterator.Do(i, func(i *TokenIterator) (*Abstraction, error) {
-		if _, err := parseToken(i, TokenSlash, true); err != nil {
-			return nil, trace.Wrap(err, "no function slash (col %d)", i.MustGet().Column)
-		} else if parameters, err := parseList(i, parseString, 0); err != nil {
-			return nil, err
-		} else if _, err = parseToken(i, TokenDot, true); err != nil {
-			return nil, trace.Wrap(err, "no function dot (col %d)", i.MustGet().Column)
-		} else if body, err := parseExpression(i); err != nil {
-			return nil, err
-		} else {
-			return NewAbstraction(parameters, body), nil
-		}
-	})
-}
-
-func parseApplication(i *TokenIterator) (*Application, error) {
-	return iterator.Do(i, func(i *TokenIterator) (*Application, error) {
-		if _, err := parseToken(i, TokenOpenParen, true); err != nil {
-			return nil, trace.Wrap(err, "no openning brackets (col %d)", i.MustGet().Column)
-		} else if expressions, err := parseList(i, parseExpression, 1); err != nil {
-			return nil, err
-		} else if _, err := parseToken(i, TokenCloseParen, true); err != nil {
-			return nil, trace.Wrap(err, "no closing brackets (col %d)", i.MustGet().Column)
-		} else {
-			return NewApplication(expressions[0], expressions[1:]), nil
-		}
-	})
-}
-
-func parseAtom(i *TokenIterator) (*Variable, error) {
-	if tok, err := parseToken(i, TokenAtom, true); err != nil {
-		return nil, trace.Wrap(err, "no variable (col %d)", i.Index())
-	} else {
-		return NewVariable(tok.Value), nil
-	}
-}
-
-func parseStatements(i *TokenIterator) ([]Statement, error) {
-	statements := []Statement{}
-
-	//nolint:errcheck
-	parseList(i, parseBreak, 0)
-
-	for {
-		if statement, err := parseStatement(i); err != nil {
-			break
-		} else if _, err := parseList(i, parseBreak, 1); err != nil && !i.Done() {
-			break
-		} else {
-			statements = append(statements, statement)
-		}
-	}
-
-	return statements, nil
-}
-
-func parseClause(i *TokenIterator, braces bool) (*Clause, error) {
-	if braces {
-		if _, err := parseToken(i, TokenOpenBrace, true); err != nil {
-			return nil, err
-		}
-	}
-
-	var stmts []Statement
-	var last *DeclareStatement
-	var err error
-	var ok bool
-
-	if stmts, err = parseStatements(i); err != nil {
-		return nil, err
-	} else if len(stmts) == 0 {
-		return nil, fmt.Errorf("no statements in clause")
-	} else if last, ok = stmts[len(stmts)-1].(*DeclareStatement); !ok {
-		return nil, fmt.Errorf("this clause contains no final return value (col %d)", i.MustGet().Column)
-	}
-
-	if braces {
-		if _, err := parseToken(i, TokenCloseBrace, true); err != nil {
-			return nil, err
-		}
-	}
-
-	return NewClause(stmts[:len(stmts)-1], last.Value), nil
-}
-
-func parseExpression(i *TokenIterator) (Expression, error) {
-	return iterator.Do(i, func(i *TokenIterator) (Expression, error) {
-		passSoftBreaks(i)
-
-		switch peek := i.MustGet(); peek.Type {
-		case TokenOpenParen:
-			return parseApplication(i)
-		case TokenSlash:
-			return parseAbstraction(i)
-		case TokenAtom:
-			return parseAtom(i)
-		case TokenOpenBrace:
-			return parseClause(i, true)
-		default:
-			return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
-		}
-	})
-}
-
-func parseLet(i *TokenIterator) (*LetStatement, error) {
-	return iterator.Do(i, func(i *TokenIterator) (*LetStatement, error) {
-		if parameters, err := parseList(i, parseString, 1); err != nil {
-			return nil, err
-		} else if _, err := parseToken(i, TokenAssign, true); err != nil {
-			return nil, err
-		} else if body, err := parseExpression(i); err != nil {
-			return nil, err
-		} else {
-			return NewLet(parameters[0], parameters[1:], body), nil
-		}
-	})
-}
-
-func parseDeclare(i *TokenIterator) (*DeclareStatement, error) {
-	if value, err := parseExpression(i); err != nil {
-		return nil, err
-	} else {
-		return NewDeclare(value), nil
-	}
-}
-
-func parseStatement(i *TokenIterator) (Statement, error) {
-	if let, letErr := parseLet(i); letErr == nil {
-		return let, nil
-	} else if declare, declErr := parseDeclare(i); declErr == nil {
-		return declare, nil
-	} else {
-		return nil, errors.Join(letErr, declErr)
-	}
-}
-
-// Given a list of tokens, attempt to parse it into an syntax tree.
-func parse(tokens []Token) (Expression, error) {
-	i := iterator.Of(tokens)
-
-	exp, err := parseClause(i, false)
-	if err != nil {
-		return nil, err
-	}
-
-	if !i.Done() {
-		return nil, fmt.Errorf("expected EOF, found more code (col %d)", i.MustGet().Column)
-	}
-
-	return exp, nil
-}
-
-// Convert a piece of valid saccharine code into an expression.
-func Parse(code string) (Expression, error) {
-	tokens, err := Scan(code)
-	if err != nil {
-		return nil, err
-	}
-
-	return parse(tokens)
-}

pkg/repr/saccharine/scan.go

@@ -1,130 +0,0 @@
-package saccharine
-
-import (
-	"errors"
-	"fmt"
-	"unicode"
-
-	"git.maximhutz.com/max/lambda/pkg/iterator"
-	"git.maximhutz.com/max/lambda/pkg/trace"
-)
-
-// isVariables determines whether a rune can be a valid variable.
-func isVariable(r rune) bool {
-	return unicode.IsLetter(r) || unicode.IsNumber(r)
-}
-
-func scanRune(i *iterator.Iterator[rune], expected func(rune) bool) (rune, error) {
-	i2 := i.Copy()
-
-	if r, err := i2.Next(); err != nil {
-		return r, err
-	} else if !expected(r) {
-		return r, fmt.Errorf("got unexpected rune %v'", r)
-	} else {
-		i.Sync(i2)
-		return r, nil
-	}
-}
-
-func scanCharacter(i *iterator.Iterator[rune], expected rune) (rune, error) {
-	i2 := i.Copy()
-
-	if r, err := i2.Next(); err != nil {
-		return r, err
-	} else if r != expected {
-		return r, fmt.Errorf("got unexpected rune %v'", r)
-	} else {
-		i.Sync(i2)
-		return r, nil
-	}
-}
-
-// Pulls the next token from an iterator over runes. If it cannot, it will
-// return nil. If an error occurs, it will return that.
-func scanToken(i *iterator.Iterator[rune]) (*Token, error) {
-	index := i.Index()
-
-	if i.Done() {
-		return nil, nil
-	}
-
-	letter, err := i.Next()
-	if err != nil {
-		return nil, trace.Wrap(err, "cannot produce next token")
-	}
-
-	switch {
-	case letter == '(':
-		return NewOpenParen(index), nil
-	case letter == ')':
-		return NewCloseParen(index), nil
-	case letter == '.':
-		return NewDot(index), nil
-	case letter == '\\':
-		return NewSlash(index), nil
-	case letter == '\n':
-		return NewSoftBreak(index), nil
-	case letter == '{':
-		return NewOpenBrace(index), nil
-	case letter == '}':
-		return NewCloseBrace(index), nil
-	case letter == ':':
-		if _, err := scanCharacter(i, '='); err != nil {
-			return nil, err
-		} else {
-			return NewAssign(index), nil
-		}
-	case letter == ';':
-		return NewHardBreak(index), nil
-	case letter == '#':
-		// Skip everything until the next newline or EOF.
-		for !i.Done() {
-			r, err := i.Next()
-			if err != nil {
-				return nil, trace.Wrap(err, "error while parsing comment")
-			}
-
-			if r == '\n' {
-				// Put the newline back so it can be processed as a soft break.
-				i.Back()
-				break
-			}
-		}
-		return nil, nil
-	case unicode.IsSpace(letter):
-		return nil, nil
-	case isVariable(letter):
-		atom := []rune{letter}
-
-		for {
-			if r, err := scanRune(i, isVariable); err != nil {
-				break
-			} else {
-				atom = append(atom, r)
-			}
-		}
-
-		return NewAtom(string(atom), index), nil
-	}
-
-	return nil, fmt.Errorf("unknown character '%v'", string(letter))
-}
-
-// Parse a string into tokens.
-func Scan(input string) ([]Token, error) {
-	i := iterator.Of([]rune(input))
-	tokens := []Token{}
-	errorList := []error{}
-
-	for !i.Done() {
-		token, err := scanToken(i)
-		if err != nil {
-			errorList = append(errorList, err)
-		} else if token != nil {
-			tokens = append(tokens, *token)
-		}
-	}
-
-	return tokens, errors.Join(errorList...)
-}

pkg/repr/saccharine/statement.go

@@ -1,31 +0,0 @@
-package saccharine
-
-import (
-	"git.maximhutz.com/max/lambda/pkg/repr"
-)
-
-type Statement interface {
-	repr.Repr
-}
-
-/** ------------------------------------------------------------------------- */
-
-type LetStatement struct {
-	Name       string
-	Parameters []string
-	Body       Expression
-}
-
-func NewLet(name string, parameters []string, body Expression) *LetStatement {
-	return &LetStatement{Name: name, Parameters: parameters, Body: body}
-}
-
-/** ------------------------------------------------------------------------- */
-
-type DeclareStatement struct {
-	Value Expression
-}
-
-func NewDeclare(value Expression) *DeclareStatement {
-	return &DeclareStatement{Value: value}
-}

pkg/repr/saccharine/token.go

@@ -1,91 +0,0 @@
-package saccharine
-
-import "fmt"
-
-// All tokens in the pseudo-lambda language.
-type Type int
-
-const (
-	TokenOpenParen  Type = iota // Denotes the '(' token.
-	TokenCloseParen             // Denotes the ')' token.
-	TokenOpenBrace              // Denotes the '{' token.
-	TokenCloseBrace             // Denotes the '}' token.
-	TokenHardBreak              // Denotes the ';' token.
-	TokenAssign                 // Denotes the ':=' token.
-	TokenAtom                   // Denotes an alpha-numeric variable.
-	TokenSlash                  // Denotes the '/' token.
-	TokenDot                    // Denotes the '.' token.
-	TokenSoftBreak              // Denotes a new-line.
-)
-
-// A representation of a token in source code.
-type Token struct {
-	Column int    // Where the token begins in the source text.
-	Type   Type   // What type the token is.
-	Value  string // The value of the token.
-}
-
-func NewOpenParen(column int) *Token {
-	return &Token{Type: TokenOpenParen, Column: column, Value: "("}
-}
-
-func NewCloseParen(column int) *Token {
-	return &Token{Type: TokenCloseParen, Column: column, Value: ")"}
-}
-
-func NewOpenBrace(column int) *Token {
-	return &Token{Type: TokenOpenBrace, Column: column, Value: "{"}
-}
-
-func NewCloseBrace(column int) *Token {
-	return &Token{Type: TokenCloseBrace, Column: column, Value: "}"}
-}
-
-func NewDot(column int) *Token {
-	return &Token{Type: TokenDot, Column: column, Value: "."}
-}
-
-func NewHardBreak(column int) *Token {
-	return &Token{Type: TokenHardBreak, Column: column, Value: ";"}
-}
-
-func NewAssign(column int) *Token {
-	return &Token{Type: TokenAssign, Column: column, Value: ":="}
-}
-
-func NewSlash(column int) *Token {
-	return &Token{Type: TokenSlash, Column: column, Value: "\\"}
-}
-
-func NewAtom(name string, column int) *Token {
-	return &Token{Type: TokenAtom, Column: column, Value: name}
-}
-
-func NewSoftBreak(column int) *Token {
-	return &Token{Type: TokenSoftBreak, Column: column, Value: "\\n"}
-}
-
-func Name(typ Type) string {
-	switch typ {
-	case TokenOpenParen:
-		return "("
-	case TokenCloseParen:
-		return ")"
-	case TokenSlash:
-		return "\\"
-	case TokenDot:
-		return "."
-	case TokenAtom:
-		return "ATOM"
-	case TokenSoftBreak:
-		return "\\n"
-	case TokenHardBreak:
-		return ";"
-	default:
-		panic(fmt.Errorf("unknown token type %v", typ))
-	}
-}
-
-func (t Token) Name() string {
-	return Name(t.Type)
-}

pkg/saccharine/codec.go

@@ -0,0 +1,27 @@
+package saccharine
+
+import (
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+// A Codec is a [codec.Codec] that serializes Saccharine expressions.
+type Codec struct{}
+
+// Decode parses a string as Saccharine source code. Returns an error
+// if it cannot.
+func (c Codec) Decode(s string) (Expression, error) {
+	tokens, err := scan(s)
+	if err != nil {
+		return nil, err
+	}
+
+	return parse(tokens)
+}
+
+// Encode turns a Saccharine expression into a string. Returns an error if it
+// cannot.
+func (c Codec) Encode(e Expression) (string, error) {
+	return stringifyExpression(e), nil
+}
+
+var _ codec.Codec[Expression] = (*Codec)(nil)

pkg/saccharine/parse.go

@@ -0,0 +1,194 @@
+package saccharine
+
+import (
+	"errors"
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/iterator"
+	"git.maximhutz.com/max/lambda/pkg/token"
+)
+
+type tokenIterator = iterator.Iterator[Token]
+
+func passSoftBreaks(i *tokenIterator) {
+	for {
+		if _, err := token.ParseRawToken(i, TokenSoftBreak); err != nil {
+			return
+		}
+	}
+}
+
+func parseToken(i *tokenIterator, expected TokenType, ignoreSoftBreaks bool) (*Token, error) {
+	if ignoreSoftBreaks {
+		passSoftBreaks(i)
+	}
+
+	return token.ParseRawToken(i, expected)
+}
+
+func parseString(i *tokenIterator) (string, error) {
+	if tok, err := parseToken(i, TokenAtom, true); err != nil {
+		return "", fmt.Errorf("no variable (col %d): %w", i.Index(), err)
+	} else {
+		return tok.Value, nil
+	}
+}
+
+func parseBreak(i *tokenIterator) (*Token, error) {
+	if tok, softErr := token.ParseRawToken(i, TokenSoftBreak); softErr == nil {
+		return tok, nil
+	} else if tok, hardErr := token.ParseRawToken(i, TokenHardBreak); hardErr == nil {
+		return tok, nil
+	} else {
+		return nil, errors.Join(softErr, hardErr)
+	}
+}
+
+func parseAbstraction(i *tokenIterator) (*Abstraction, error) {
+	if _, err := parseToken(i, TokenSlash, true); err != nil {
+		return nil, fmt.Errorf("no function slash (col %d): %w", i.MustGet().Column, err)
+	} else if parameters, err := token.ParseList(i, parseString, 0); err != nil {
+		return nil, err
+	} else if _, err = parseToken(i, TokenDot, true); err != nil {
+		return nil, fmt.Errorf("no function dot (col %d): %w", i.MustGet().Column, err)
+	} else if body, err := parseExpression(i); err != nil {
+		return nil, err
+	} else {
+		return &Abstraction{Parameters: parameters, Body: body}, nil
+	}
+}
+
+func parseApplication(i *tokenIterator) (*Application, error) {
+	if _, err := parseToken(i, TokenOpenParen, true); err != nil {
+		return nil, fmt.Errorf("no openning brackets (col %d): %w", i.MustGet().Column, err)
+	} else if expressions, err := token.ParseList(i, parseExpression, 1); err != nil {
+		return nil, err
+	} else if _, err := parseToken(i, TokenCloseParen, true); err != nil {
+		return nil, fmt.Errorf("no closing brackets (col %d): %w", i.MustGet().Column, err)
+	} else {
+		return &Application{Abstraction: expressions[0], Arguments: expressions[1:]}, nil
+	}
+}
+
+func parseAtom(i *tokenIterator) (*Atom, error) {
+	if tok, err := parseToken(i, TokenAtom, true); err != nil {
+		return nil, fmt.Errorf("no variable (col %d): %w", i.Index(), err)
+	} else {
+		return &Atom{Name: tok.Value}, nil
+	}
+}
+
+func parseStatements(i *tokenIterator) ([]Statement, error) {
+	statements := []Statement{}
+
+	//nolint:errcheck
+	token.ParseList(i, parseBreak, 0)
+
+	for {
+		if statement, err := parseStatement(i); err != nil {
+			break
+		} else if _, err := token.ParseList(i, parseBreak, 1); err != nil && !i.Done() {
+			break
+		} else {
+			statements = append(statements, statement)
+		}
+	}
+
+	return statements, nil
+}
+
+func parseClause(i *tokenIterator, braces bool) (*Clause, error) {
+	if braces {
+		if _, err := parseToken(i, TokenOpenBrace, true); err != nil {
+			return nil, err
+		}
+	}
+
+	var stmts []Statement
+	var last *DeclareStatement
+	var err error
+	var ok bool
+
+	if stmts, err = parseStatements(i); err != nil {
+		return nil, err
+	} else if len(stmts) == 0 {
+		return nil, fmt.Errorf("no statements in clause")
+	} else if last, ok = stmts[len(stmts)-1].(*DeclareStatement); !ok {
+		return nil, fmt.Errorf("this clause contains no final return value (col %d)", i.MustGet().Column)
+	}
+
+	if braces {
+		if _, err := parseToken(i, TokenCloseBrace, true); err != nil {
+			return nil, err
+		}
+	}
+
+	return &Clause{Statements: stmts[:len(stmts)-1], Returns: last.Value}, nil
+}
+
+func parseExpression(i *tokenIterator) (Expression, error) {
+	passSoftBreaks(i)
+
+	if i.Done() {
+		return nil, fmt.Errorf("unexpected end of input")
+	}
+
+	switch peek := i.MustGet(); peek.Type {
+	case TokenOpenParen:
+		return parseApplication(i)
+	case TokenSlash:
+		return parseAbstraction(i)
+	case TokenAtom:
+		return parseAtom(i)
+	case TokenOpenBrace:
+		return parseClause(i, true)
+	default:
+		return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
+	}
+}
+
+func parseLet(i *tokenIterator) (*LetStatement, error) {
+	if parameters, err := token.ParseList(i, parseString, 1); err != nil {
+		return nil, err
+	} else if _, err := parseToken(i, TokenAssign, true); err != nil {
+		return nil, err
+	} else if body, err := parseExpression(i); err != nil {
+		return nil, err
+	} else {
+		return &LetStatement{Name: parameters[0], Parameters: parameters[1:], Body: body}, nil
+	}
+}
+
+func parseDeclare(i *tokenIterator) (*DeclareStatement, error) {
+	if value, err := parseExpression(i); err != nil {
+		return nil, err
+	} else {
+		return &DeclareStatement{Value: value}, nil
+	}
+}
+
+func parseStatement(i *tokenIterator) (Statement, error) {
+	if let, letErr := iterator.Try(i, parseLet); letErr == nil {
+		return let, nil
+	} else if declare, declErr := iterator.Try(i, parseDeclare); declErr == nil {
+		return declare, nil
+	} else {
+		return nil, errors.Join(letErr, declErr)
+	}
+}
+
+// Given a list of tokens, attempt to parse it into an syntax tree.
+func parse(tokens []Token) (Expression, error) {
+	i := iterator.Of(tokens)
+
+	exp, err := parseClause(i, false)
+	if err != nil {
+		return nil, err
+	}
+
+	if !i.Done() {
+		return nil, fmt.Errorf("expected EOF, found more code (col %d)", i.MustGet().Column)
+	}
+
+	return exp, nil
+}

pkg/saccharine/saccharine.go

@@ -0,0 +1,60 @@
+// Package saccharine defines the AST for the Saccharine language, a sugared
+// lambda calculus with let bindings and multi-statement clauses.
+package saccharine
+
+// An Expression is a node in the Saccharine abstract syntax tree.
+// It is a sealed interface; only types in this package may implement it.
+type Expression interface {
+	expression()
+}
+
+// An Abstraction is a lambda expression with zero or more parameters.
+// A zero-parameter abstraction is treated as a thunk.
+type Abstraction struct {
+	Parameters []string
+	Body       Expression
+}
+
+// An Application applies an expression to zero or more arguments.
+type Application struct {
+	Abstraction Expression
+	Arguments   []Expression
+}
+
+// An Atom is a named variable.
+type Atom struct {
+	Name string
+}
+
+// A Clause is a sequence of statements followed by a return expression.
+type Clause struct {
+	Statements []Statement
+	Returns    Expression
+}
+
+func (Abstraction) expression() {}
+func (Application) expression() {}
+func (Atom) expression()        {}
+func (Clause) expression()      {}
+
+// A Statement is a declaration within a Clause.
+// It is a sealed interface; only types in this package may implement it.
+type Statement interface {
+	statement()
+}
+
+// A LetStatement binds a name (with optional parameters) to an expression.
+type LetStatement struct {
+	Name       string
+	Parameters []string
+	Body       Expression
+}
+
+// A DeclareStatement evaluates an expression for its side effects within a
+// clause.
+type DeclareStatement struct {
+	Value Expression
+}
+
+func (LetStatement) statement()     {}
+func (DeclareStatement) statement() {}

pkg/saccharine/scan.go

@@ -0,0 +1,24 @@
+package saccharine
+
+import "git.maximhutz.com/max/lambda/pkg/token"
+
+// scanner is the declarative lexer for the Saccharine language.
+var scanner = token.NewScanner(
+	token.On(`:=`, TokenAssign, 1),
+	token.On(`\(`, TokenOpenParen, 0),
+	token.On(`\)`, TokenCloseParen, 0),
+	token.On(`\{`, TokenOpenBrace, 0),
+	token.On(`\}`, TokenCloseBrace, 0),
+	token.On(`;`, TokenHardBreak, 0),
+	token.On(`\n`, TokenSoftBreak, 0),
+	token.On(`\\`, TokenSlash, 0),
+	token.On(`\.`, TokenDot, 0),
+	token.On(`[a-zA-Z0-9_]+`, TokenAtom, 0),
+	token.Skip[TokenType](`#[^\n]*`, 0),
+	token.Skip[TokenType](`[^\S\n]+`, 0),
+)
+
+// scan tokenizes a string into Saccharine tokens.
+func scan(input string) ([]Token, error) {
+	return scanner.Scan(input)
+}

pkg/saccharine/stringify.go

@@ -5,30 +5,30 @@ import (
 	"strings"
 )
 
-func stringifyAtom(n *Variable) string {
+func stringifyAtom(n *Atom) string {
 	return n.Name
 }
 
 func stringifyAbstraction(n *Abstraction) string {
-	return "\\" + strings.Join(n.Parameters, " ") + "." + Stringify(n.Body)
+	return "\\" + strings.Join(n.Parameters, " ") + "." + stringifyExpression(n.Body)
 }
 
 func stringifyApplication(n *Application) string {
-	arguments := []string{Stringify(n.Abstraction)}
+	arguments := []string{stringifyExpression(n.Abstraction)}
 
 	for _, argument := range n.Arguments {
-		arguments = append(arguments, Stringify(argument))
+		arguments = append(arguments, stringifyExpression(argument))
 	}
 
 	return "(" + strings.Join(arguments, " ") + ")"
 }
 
 func stringifyLet(s *LetStatement) string {
-	return s.Name + " " + strings.Join(s.Parameters, " ") + " := " + Stringify(s.Body)
+	return s.Name + " " + strings.Join(s.Parameters, " ") + " := " + stringifyExpression(s.Body)
 }
 
 func stringifyDeclare(s *DeclareStatement) string {
-	return Stringify(s.Value)
+	return stringifyExpression(s.Value)
 }
 
 func stringifyStatement(s Statement) string {
@@ -49,13 +49,13 @@ func stringifyClause(n *Clause) string {
 		stmts += stringifyStatement(statement) + "; "
 	}
 
-	return "{ " + stmts + Stringify(n.Returns) + " }"
+	return "{ " + stmts + stringifyExpression(n.Returns) + " }"
 }
 
 // Convert an expression back into valid source code.
-func Stringify(n Expression) string {
+func stringifyExpression(n Expression) string {
 	switch n := n.(type) {
-	case *Variable:
+	case *Atom:
 		return stringifyAtom(n)
 	case *Abstraction:
 		return stringifyAbstraction(n)

pkg/saccharine/token.go

@@ -0,0 +1,65 @@
+package saccharine
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/token"
+)
+
+// A TokenType is an identifier for any token in the Saccharine language.
+type TokenType int
+
+// All official tokens of the Saccharine language.
+const (
+	// TokenOpenParen denotes the '(' token.
+	TokenOpenParen TokenType = iota
+	// TokenCloseParen denotes the ')' token.
+	TokenCloseParen
+	// TokenOpenBrace denotes the '{' token.
+	TokenOpenBrace
+	// TokenCloseBrace denotes the '}' token.
+	TokenCloseBrace
+	// TokenHardBreak denotes the ';' token.
+	TokenHardBreak
+	// TokenAssign denotes the ':=' token.
+	TokenAssign
+	// TokenAtom denotes an alpha-numeric variable.
+	TokenAtom
+	// TokenSlash denotes the '\\' token.
+	TokenSlash
+	// TokenDot denotes the '.' token.
+	TokenDot
+	// TokenSoftBreak denotes a new-line.
+	TokenSoftBreak
+)
+
+// Name returns the type of the TokenType, as a string.
+func (t TokenType) Name() string {
+	switch t {
+	case TokenOpenParen:
+		return "("
+	case TokenCloseParen:
+		return ")"
+	case TokenOpenBrace:
+		return "{"
+	case TokenCloseBrace:
+		return "}"
+	case TokenHardBreak:
+		return ";"
+	case TokenAssign:
+		return ":="
+	case TokenAtom:
+		return "ATOM"
+	case TokenSlash:
+		return "\\"
+	case TokenDot:
+		return "."
+	case TokenSoftBreak:
+		return "\\n"
+	default:
+		panic(fmt.Errorf("unknown token type %v", t))
+	}
+}
+
+// Token is the concrete token type for the Saccharine language.
+type Token = token.Token[TokenType]

pkg/set/set.go

@@ -1,31 +1,41 @@
+// Package set defines a generic, mutable unordered set data structure.
 package set
 
 import "iter"
 
+// A Set is an implementation of an mutable, unordered set. It uses a Golang map
+// as its underlying data structure.
 type Set[T comparable] map[T]bool
 
+// Add appends a list of items into the set.
 func (s Set[T]) Add(items ...T) {
 	for _, item := range items {
 		s[item] = true
 	}
 }
 
+// Has returns true an item is present in the set.
 func (s Set[T]) Has(item T) bool {
 	return s[item]
 }
 
+// Remove deletes a list of items from the set.
 func (s Set[T]) Remove(items ...T) {
 	for _, item := range items {
 		delete(s, item)
 	}
 }
 
+// Merge adds all items in the argument into the set. The argument is not
+// mutated.
 func (s Set[T]) Merge(o Set[T]) {
 	for item := range o {
 		s.Add(item)
 	}
 }
 
+// ToList returns all items present in the set, as a slice. The order of the
+// items is not guaranteed.
 func (s Set[T]) ToList() []T {
 	list := []T{}
 
@@ -36,6 +46,8 @@ func (s Set[T]) ToList() []T {
 	return list
 }
 
+// Items returns a sequence of all items present in the set. The order of the
+// items is not guaranteed.
 func (s Set[T]) Items() iter.Seq[T] {
 	return func(yield func(T) bool) {
 		for item := range s {
@@ -46,6 +58,7 @@ func (s Set[T]) Items() iter.Seq[T] {
 	}
 }
 
+// New creates a set of all items as argument.
 func New[T comparable](items ...T) Set[T] {
 	result := Set[T]{}
 

pkg/token/parse.go

@@ -0,0 +1,42 @@
+package token
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/iterator"
+)
+
+// ParseRawToken consumes the next token from the iterator if its type matches
+// the expected type.
+// Returns an error if the iterator is exhausted or the token type does not
+// match.
+func ParseRawToken[T Type](i *iterator.Iterator[Token[T]], expected T) (*Token[T], error) {
+	tok, err := i.Get()
+	if err != nil {
+		return nil, err
+	}
+	if tok.Type != expected {
+		return nil, fmt.Errorf("expected token '%v', got '%v'", expected.Name(), tok.Value)
+	}
+	i.Forward()
+	return &tok, nil
+}
+
+// ParseList repeatedly applies a parse function, collecting results into a
+// slice.
+// Stops when the parse function returns an error.
+// Returns an error if fewer than minimum results are collected.
+func ParseList[T Type, U any](i *iterator.Iterator[Token[T]], fn func(*iterator.Iterator[Token[T]]) (U, error), minimum int) ([]U, error) {
+	results := []U{}
+
+	for {
+		if u, err := fn(i); err != nil {
+			if len(results) < minimum {
+				return nil, fmt.Errorf("expected at least '%v' items, got only '%v': %w", minimum, len(results), err)
+			}
+			return results, nil
+		} else {
+			results = append(results, u)
+		}
+	}
+}

pkg/token/scanner.go

@@ -0,0 +1,129 @@
+package token
+
+import (
+	"errors"
+	"fmt"
+	"regexp"
+	"slices"
+)
+
+// A rule describes a single lexical pattern for the scanner.
+type rule[T Type] struct {
+	pattern    *regexp.Regexp
+	typ        T
+	precedence int
+	skip       bool
+}
+
+// compare orders rules by descending precedence.
+func (r rule[T]) compare(other rule[T]) int {
+	return other.precedence - r.precedence
+}
+
+// An Option configures a Scanner during construction.
+type Option[T Type] func(rules []rule[T]) []rule[T]
+
+// On returns an option that registers a token-emitting rule.
+// The token's value is the matched text.
+// Higher precedence rules are tried first.
+func On[T Type](pattern string, typ T, precedence int) Option[T] {
+	return func(rules []rule[T]) []rule[T] {
+		return append(rules, rule[T]{
+			pattern:    compileAnchored(pattern),
+			typ:        typ,
+			precedence: precedence,
+		})
+	}
+}
+
+// Skip returns an option that registers a non-emitting rule.
+// This is used for whitespace and comments.
+// Higher precedence rules are tried first.
+func Skip[T Type](pattern string, precedence int) Option[T] {
+	return func(rules []rule[T]) []rule[T] {
+		return append(rules, rule[T]{
+			pattern:    compileAnchored(pattern),
+			precedence: precedence,
+			skip:       true,
+		})
+	}
+}
+
+// A Scanner is a declarative lexer built from a set of regex rules.
+// Rules are sorted by precedence (highest first), with registration order as
+// tiebreaker.
+// At each position, the first matching rule wins.
+type Scanner[T Type] struct {
+	rules []rule[T]
+}
+
+// NewScanner creates a Scanner by applying the given options and sorting the
+// resulting rules by precedence.
+func NewScanner[T Type](opts ...Option[T]) *Scanner[T] {
+	var rules []rule[T]
+	for _, opt := range opts {
+		rules = opt(rules)
+	}
+
+	slices.SortStableFunc(rules, rule[T].compare)
+
+	return &Scanner[T]{rules: rules}
+}
+
+// scanOne tries each rule at the current position and returns the first match.
+// Returns the token (or nil if skipped) and the number of bytes consumed.
+// Returns 0 if no rule matched.
+func (s *Scanner[T]) scanOne(input string, pos int) (*Token[T], int) {
+	for _, r := range s.rules {
+		loc := r.pattern.FindStringIndex(input[pos:])
+		if loc == nil || loc[1] == 0 {
+			continue
+		}
+
+		if r.skip {
+			return nil, loc[1]
+		}
+
+		return &Token[T]{
+			Type:   r.typ,
+			Value:  input[pos : pos+loc[1]],
+			Column: pos,
+		}, loc[1]
+	}
+
+	return nil, 0
+}
+
+// Scan tokenizes the input string using the registered rules.
+// At each position, rules are tried in precedence order and the first match
+// wins.
+// If no rule matches, an error is recorded and the scanner advances one byte.
+func (s *Scanner[T]) Scan(input string) ([]Token[T], error) {
+	tokens := []Token[T]{}
+	errorList := []error{}
+
+	for pos := 0; pos < len(input); {
+		tok, n := s.scanOne(input, pos)
+
+		if n == 0 {
+			errorList = append(errorList, fmt.Errorf("unknown character '%v'", string(input[pos])))
+			pos++
+			continue
+		}
+
+		if tok != nil {
+			tokens = append(tokens, *tok)
+		}
+
+		pos += n
+	}
+
+	return tokens, errors.Join(errorList...)
+}
+
+// compileAnchored compiles a regex pattern, prepending \A so it only matches
+// at the current scan position.
+// Patterns must not be pre-anchored.
+func compileAnchored(pattern string) *regexp.Regexp {
+	return regexp.MustCompile(`\A(?:` + pattern + `)`)
+}

pkg/token/token.go

@@ -0,0 +1,24 @@
+// Package token provides generic token types and scanning/parsing primitives
+// for building language-specific lexers and parsers.
+package token
+
+// A Type is a constraint for language-specific token type enums.
+// It must be comparable (for equality checks) and must have a Name method
+// that returns a human-readable string for error messages.
+type Type interface {
+	comparable
+	// Name returns a human-readable name for this token type.
+	Name() string
+}
+
+// A Token is a lexical unit in a source language.
+type Token[T Type] struct {
+	Column int    // Where the token begins in the source text.
+	Type   T      // What type the token is.
+	Value  string // The value of the token.
+}
+
+// Name returns the type of the Token, as a string.
+func (t Token[T]) Name() string {
+	return t.Type.Name()
+}

pkg/trace/trace.go

@@ -1,25 +0,0 @@
-package trace
-
-import (
-	"errors"
-	"fmt"
-	"strings"
-)
-
-func Indent(s string, size int) string {
-	lines := strings.Lines(s)
-	indent := strings.Repeat(" ", size)
-
-	indented := ""
-	for line := range lines {
-		indented += indent + line
-	}
-
-	return indented
-}
-
-func Wrap(child error, format string, a ...any) error {
-	parent := fmt.Errorf(format, a...)
-	childErrString := Indent(child.Error(), 4)
-	return errors.New(parent.Error() + "\n" + childErrString)
-}