feat: new registry

.golangci.yml

@@ -160,8 +160,6 @@ 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

cmd/lambda/lambda.go

@@ -1,4 +1,3 @@
-// Package main defines the 'lambda' command-line interface (CLI).
 package main
 
 import (

cmd/lambda/lambda_convert.go

@@ -26,7 +26,6 @@ func LambdaConvert() *cobra.Command {
 
 	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 {
@@ -88,8 +87,8 @@ func LambdaConvert() *cobra.Command {
 		},
 	}
 
-	cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
+	cmd.Flags().StringVar(&inputReprFlag, "from", "", "Input representation (inferred from extension if unset)")
-	cmd.Flags().StringVarP(&outputReprFlag, "output", "o", "", "Output representation (inferred from extension if unset)")
+	cmd.Flags().StringVar(&outputReprFlag, "to", "", "Output representation (inferred from extension if unset)")
 
 	return cmd
 }

cmd/lambda/lambda_engine.go

@@ -7,9 +7,8 @@ import (
 func LambdaEngine() *cobra.Command {
 	cmd := &cobra.Command{
 		Use:   "engine",
-		Aliases: []string{"eng"},
 		Short: "Information about available engines",
-		RunE: func(cmd *cobra.Command, _ []string) error {
+		RunE: func(cmd *cobra.Command, args []string) error {
 			return cmd.Help()
 		},
 	}

cmd/lambda/lambda_engine_list.go

@@ -11,7 +11,7 @@ func LambdaEngineList() *cobra.Command {
 		Use:     "list",
 		Aliases: []string{"ls"},
 		Short:   "List available engines",
-		RunE: func(*cobra.Command, []string) error {
+		RunE: func(cmd *cobra.Command, args []string) error {
 			r := GetRegistry()
 
 			for engine := range r.ListEngines() {

cmd/lambda/lambda_reduce.go

@@ -6,7 +6,7 @@ import (
 	"github.com/spf13/cobra"
 
 	"git.maximhutz.com/max/lambda/internal/cli"
-	"git.maximhutz.com/max/lambda/internal/registry"
+	"git.maximhutz.com/max/lambda/internal/config"
 )
 
 func LambdaReduce() *cobra.Command {
@@ -27,14 +27,14 @@ func LambdaReduce() *cobra.Command {
 			inputPath := args[0]
 
 			// Get input source.
-			var source cli.Source
+			var source config.Source
 			if inputPath == "-" {
-				source = cli.StdinSource{}
+				source = config.StdinSource{}
 			} else {
-				source = cli.FileSource{Path: inputPath}
+				source = config.FileSource{Path: inputPath}
 			}
 
-			destination := cli.StdoutDestination{}
+			destination := config.StdoutDestination{}
 
 			r := GetRegistry()
 
@@ -53,7 +53,7 @@ func LambdaReduce() *cobra.Command {
 			}
 
 			// Find engine.
-			var engine registry.Engine
+			var engine cli.Engine
 			if engineFlag == "" {
 				if engine, err = r.GetDefaultEngine(inputRepr); err != nil {
 					return err
@@ -77,7 +77,8 @@ func LambdaReduce() *cobra.Command {
 			}
 
 			// Create process.
-			process, err := engine.Load(compiled)
+			process := engine.Load()
+			err = process.Set(compiled)
 			if err != nil {
 				return err
 			}
@@ -101,7 +102,7 @@ func LambdaReduce() *cobra.Command {
 		},
 	}
 
-	cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
+	cmd.Flags().StringVar(&inputReprFlag, "from", "", "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

@@ -1,6 +1,7 @@
 package main
 
 import (
+	"git.maximhutz.com/max/lambda/internal/cli"
 	"git.maximhutz.com/max/lambda/internal/registry"
 	"git.maximhutz.com/max/lambda/pkg/convert"
 	"git.maximhutz.com/max/lambda/pkg/engine/normalorder"
@@ -12,15 +13,14 @@ func GetRegistry() *registry.Registry {
 	r := registry.New()
 
 	// Codecs
-	(registry.RegisterConversion(r, convert.Saccharine2Lambda, "saccharine", "lambda"))
+	r.MustAddConversions(cli.ConvertCodec(convert.Saccharine2Lambda{}, "saccharine", "lambda")...)
-	(registry.RegisterConversion(r, convert.Lambda2Saccharine, "lambda", "saccharine"))
 
 	// Engines
-	(registry.RegisterEngine(r, normalorder.NewProcess, "normalorder", "lambda"))
+	r.MustAddEngine(cli.ConvertEngine(normalorder.Engine{}, "normalorder", "lambda"))
 
 	// Marshalers
-	(registry.RegisterCodec(r, lambda.Codec{}, "lambda"))
+	r.MustAddMarshaler(cli.ConvertMarshaler(lambda.Marshaler{}, "lambda"))
-	(registry.RegisterCodec(r, saccharine.Codec{}, "saccharine"))
+	r.MustAddMarshaler(cli.ConvertMarshaler(saccharine.Marshaler{}, "saccharine"))
 
 	return r
 }

internal/cli/cli.go

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

internal/cli/conversion.go

@@ -0,0 +1,67 @@
+package cli
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+type Conversion interface {
+	InType() string
+	OutType() string
+
+	Run(Repr) (Repr, error)
+}
+
+type forwardCodec[T, U any] struct {
+	codec           codec.Codec[T, U]
+	inType, outType string
+}
+
+func (c forwardCodec[T, U]) Run(r Repr) (Repr, error) {
+	t, ok := r.Data().(T)
+	if !ok {
+		return nil, fmt.Errorf("could not parse '%v' as '%s'", t, c.inType)
+	}
+
+	u, err := c.codec.Encode(t)
+	if err != nil {
+		return nil, err
+	}
+
+	return NewRepr(c.outType, u), nil
+}
+
+func (c forwardCodec[T, U]) InType() string { return c.inType }
+
+func (c forwardCodec[T, U]) OutType() string { return c.outType }
+
+type backwardCodec[T, U any] struct {
+	codec           codec.Codec[T, U]
+	inType, outType string
+}
+
+func (c backwardCodec[T, U]) Run(r Repr) (Repr, error) {
+	u, ok := r.Data().(U)
+	if !ok {
+		return nil, fmt.Errorf("could not parse '%v' as '%s'", r, c.outType)
+	}
+
+	t, err := c.codec.Decode(u)
+	if err != nil {
+		return nil, err
+	}
+
+	return NewRepr(c.inType, t), nil
+}
+
+func (c backwardCodec[T, U]) InType() string { return c.outType }
+
+func (c backwardCodec[T, U]) OutType() string { return c.inType }
+
+func ConvertCodec[T, U any](e codec.Codec[T, U], inType, outType string) []Conversion {
+	return []Conversion{
+		forwardCodec[T, U]{e, inType, outType},
+		backwardCodec[T, U]{e, inType, outType},
+	}
+}

internal/cli/engine.go

@@ -0,0 +1,27 @@
+package cli
+
+import "git.maximhutz.com/max/lambda/pkg/engine"
+
+type Engine interface {
+	Load() Process
+	Name() string
+	InType() string
+}
+
+type convertedEngine[T any] struct {
+	engine engine.Engine[T]
+	name   string
+	inType string
+}
+
+func (e convertedEngine[T]) InType() string { return e.inType }
+
+func (e convertedEngine[T]) Name() string { return e.name }
+
+func (e convertedEngine[T]) Load() Process {
+	return convertedProcess[T]{e.engine.Load(), e.inType}
+}
+
+func ConvertEngine[T any](e engine.Engine[T], name, inType string) Engine {
+	return &convertedEngine[T]{e, name, inType}
+}

internal/cli/marshaler.go

@@ -0,0 +1,45 @@
+package cli
+
+import (
+	"fmt"
+	"reflect"
+
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+type Marshaler interface {
+	codec.Marshaler[Repr]
+
+	InType() string
+}
+
+type convertedMarshaler[T any] struct {
+	codec  codec.Marshaler[T]
+	inType string
+}
+
+func (c convertedMarshaler[T]) Decode(s string) (Repr, error) {
+	t, err := c.codec.Decode(s)
+	if err != nil {
+		return nil, err
+	}
+
+	return NewRepr(c.inType, t), nil
+}
+
+func (c convertedMarshaler[T]) Encode(r Repr) (string, error) {
+	t, ok := r.Data().(T)
+	if !ok {
+		dataType := reflect.TypeOf(r.Data())
+		allowedType := reflect.TypeFor[T]()
+		return "", fmt.Errorf("marshaler for '%s' cannot parse '%s'", allowedType, dataType)
+	}
+
+	return c.codec.Encode(t)
+}
+
+func (c convertedMarshaler[T]) InType() string { return c.inType }
+
+func ConvertMarshaler[T any](e codec.Marshaler[T], inType string) Marshaler {
+	return convertedMarshaler[T]{e, inType}
+}

internal/cli/process.go

@@ -0,0 +1,41 @@
+package cli
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/engine"
+)
+
+type Process interface {
+	engine.Process[Repr]
+
+	InType() string
+}
+
+type convertedProcess[T any] struct {
+	process engine.Process[T]
+	inType  string
+}
+
+func (e convertedProcess[T]) InType() string { return e.inType }
+
+func (b convertedProcess[T]) Get() (Repr, error) {
+	s, err := b.process.Get()
+	if err != nil {
+		return nil, err
+	}
+
+	return NewRepr(b.inType, s), nil
+}
+
+func (b convertedProcess[T]) Set(r Repr) error {
+	if t, ok := r.Data().(T); ok {
+		return b.process.Set(t)
+	}
+
+	return fmt.Errorf("Incorrent format '%s' for engine '%s'.", r.Id(), b.inType)
+}
+
+func (b convertedProcess[T]) Step(i int) bool {
+	return b.process.Step(i)
+}

internal/cli/repr.go

@@ -0,0 +1,21 @@
+package cli
+
+type Repr interface {
+	// Id returns to name of the objects underlying representation. If is
+	// assumed that if two Repr objects have the same Id(), they share the same
+	// representation.
+	Id() string
+
+	Data() any
+}
+
+type baseRepr struct {
+	id   string
+	data any
+}
+
+func (r baseRepr) Id() string { return r.id }
+
+func (r baseRepr) Data() any { return r.data }
+
+func NewRepr(id string, data any) Repr { return baseRepr{id, data} }

internal/config/config.go

@@ -0,0 +1,12 @@
+// Package "config" parses ad handles the user settings given to the program.
+package config
+
+// Configuration settings for the program.
+type Config struct {
+	Source      Source      // The source code given to the program.
+	Destination Destination // The destination for the final result.
+	Verbose     bool        // Whether or not to print debug logs.
+	Explanation bool        // Whether or not to print an explanation of the reduction.
+	Profile     string      // If not nil, print a CPU profile during execution.
+	Statistics  bool        // Whether or not to print statistics.
+}

internal/config/destination.go

@@ -1,29 +1,27 @@
-package cli
+package config
 
 import (
 	"fmt"
 	"os"
 )
 
-// A Destination is method of writing output to the user.
+// A method of writing output to the user.
 type Destination interface {
 	// Write data to this destination.
 	Write(data string) error
 }
 
-// An StdoutDestination writes to stdout.
+// A destination writing 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.
+// A destination writing 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/config/get_logger.go

@@ -0,0 +1,23 @@
+package config
+
+import (
+	"log/slog"
+	"os"
+)
+
+// Returns a structured logger with the appropriate configurations.
+func (c Config) GetLogger() *slog.Logger {
+	// By default, only print out errors.
+	level := slog.LevelError
+
+	// If the user set the output to be "VERBOSE", return the debug logs.
+	if c.Verbose {
+		level = slog.LevelInfo
+	}
+
+	return slog.New(
+		slog.NewTextHandler(os.Stdout, &slog.HandlerOptions{
+			Level: level,
+		}),
+	)
+}

internal/config/parse_from_args.go

@@ -0,0 +1,56 @@
+package config
+
+import (
+	"flag"
+	"fmt"
+)
+
+// Extract the program configuration from the command-line arguments.
+func FromArgs() (*Config, error) {
+	// Relevant flags.
+	verbose := flag.Bool("v", false, "Verbosity. If set, the program will print logs.")
+	explanation := flag.Bool("x", false, "Explanation. Whether or not to show all reduction steps.")
+	statistics := flag.Bool("s", false, "Statistics. If set, the process will print various statistics about the run.")
+	profile := flag.String("p", "", "CPU profiling. If an output file is defined, the program will profile its execution and dump its results into it.")
+	file := flag.String("f", "", "File. If set, read source from the specified file.")
+	output := flag.String("o", "", "Output. If set, write result to the specified file. Use '-' for stdout (default).")
+	flag.Parse()
+
+	// Parse source type.
+	var source Source
+	if *file != "" {
+		// File flag takes precedence.
+		if flag.NArg() > 0 {
+			return nil, fmt.Errorf("cannot specify both -f flag and positional argument")
+		}
+		source = FileSource{Path: *file}
+	} else if flag.NArg() == 0 {
+		return nil, fmt.Errorf("no input given")
+	} else if flag.NArg() > 1 {
+		return nil, fmt.Errorf("more than 1 command-line argument")
+	} else {
+		// Positional argument.
+		if flag.Arg(0) == "-" {
+			source = StdinSource{}
+		} else {
+			source = StringSource{Data: flag.Arg(0)}
+		}
+	}
+
+	// Parse destination type.
+	var destination Destination
+	if *output == "" || *output == "-" {
+		destination = StdoutDestination{}
+	} else {
+		destination = FileDestination{Path: *output}
+	}
+
+	return &Config{
+		Source:      source,
+		Destination: destination,
+		Verbose:     *verbose,
+		Explanation: *explanation,
+		Profile:     *profile,
+		Statistics:  *statistics,
+	}, nil
+}

internal/config/source.go

@@ -1,26 +1,24 @@
-package cli
+package config
 
 import (
 	"io"
 	"os"
 )
 
-// A Source is a method of extracting input from the user.
+// A method of extracting input from the user.
 type Source interface {
-	// Extract fetches data from this source.
+	// Fetch data from this source.
 	Extract() (string, error)
 }
 
-// A StringSource is defined by a string.
+// A source 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.
+// A source pulling 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 {
@@ -30,10 +28,9 @@ func (s StdinSource) Extract() (string, error) {
 	return string(data), nil
 }
 
-// A FileSource reads from a file.
+// A source reading 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 {

internal/registry/codec.go

@@ -1,58 +0,0 @@
-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

@@ -1,59 +0,0 @@
-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

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

internal/registry/engine.go

@@ -1,58 +0,0 @@
-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

@@ -1,26 +0,0 @@
-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

@@ -1,35 +0,0 @@
-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

@@ -1,33 +1,71 @@
-// Package registry defines a structure to hold all available representations,
-// engines, and conversions between them.
 package registry
 
 import (
 	"fmt"
 	"iter"
 	"maps"
+
+	"git.maximhutz.com/max/lambda/internal/cli"
 )
 
-// A Registry holds all representations, conversions, codecs, and engines
-// available to the program.
 type Registry struct {
-	codecs    map[string]Codec
+	marshalers map[string]cli.Marshaler
 	converter  *Converter
-	engines   map[string]Engine
+	engines    map[string]cli.Engine
 }
 
-// New makes an empty registry.
 func New() *Registry {
 	return &Registry{
-		codecs:    map[string]Codec{},
+		marshalers: map[string]cli.Marshaler{},
 		converter:  NewConverter(),
-		engines:   map[string]Engine{},
+		engines:    map[string]cli.Engine{},
 	}
 }
 
-// GetEngine finds an engine based on its name. Returns an error if an engine
+func (r *Registry) AddConversions(conversions ...cli.Conversion) error {
-// with that name cannot be found.
+	for _, conversion := range conversions {
-func (r Registry) GetEngine(name string) (Engine, error) {
+		r.converter.Add(conversion)
+	}
+
+	return nil
+}
+func (r *Registry) MustAddConversions(conversions ...cli.Conversion) {
+	if err := r.AddConversions(conversions...); err != nil {
+		panic(err)
+	}
+}
+
+func (r *Registry) AddMarshaler(c cli.Marshaler) error {
+	if _, ok := r.marshalers[c.InType()]; ok {
+		return fmt.Errorf("marshaler for '%s' already registered", c.InType())
+	}
+
+	r.marshalers[c.InType()] = c
+	return nil
+}
+
+func (r *Registry) MustAddMarshaler(c cli.Marshaler) {
+	if err := r.AddMarshaler(c); err != nil {
+		panic(err)
+	}
+}
+
+func (r *Registry) AddEngine(e cli.Engine) error {
+	if _, ok := r.engines[e.Name()]; ok {
+		return fmt.Errorf("engine '%s' already registered", e.Name())
+	}
+
+	r.engines[e.Name()] = e
+	return nil
+}
+
+func (r *Registry) MustAddEngine(e cli.Engine) {
+	if err := r.AddEngine(e); err != nil {
+		panic(err)
+	}
+}
+
+func (r Registry) GetEngine(name string) (cli.Engine, error) {
 	e, ok := r.engines[name]
 	if !ok {
 		return nil, fmt.Errorf("engine '%s' not found", name)
@@ -36,38 +74,27 @@ func (r Registry) GetEngine(name string) (Engine, error) {
 	return e, nil
 }
 
-// ListEngines returns all available engines to the registry.
+func (r Registry) ListEngines() iter.Seq[cli.Engine] {
-func (r Registry) ListEngines() iter.Seq[Engine] {
 	return maps.Values(r.engines)
 }
 
-// GetDefaultEngine infers the preferred engine for a representation. Returns an
+func (r *Registry) GetDefaultEngine(id string) (cli.Engine, error) {
-// 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)
-
-	// return nil, fmt.Errorf("no engine for '%s'", id)
 }
 
-// ConvertTo attempts to convert an expression of one type of representation to
+func (r *Registry) ConvertTo(repr cli.Repr, outType string) (cli.Repr, error) {
-// another. Returns the converted expression, otherwise an error.
+	path, err := r.ConversionPath(repr.Id(), outType)
-//
-// 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
+	result := repr
 	for _, conversion := range path {
 		result, err = conversion.Run(result)
 		if err != nil {
@@ -78,21 +105,17 @@ func (r *Registry) ConvertTo(expr Expr, outType string) (Expr, error) {
 	return result, err
 }
 
-// Marshal serializes an expression, given that representation has a codec.
+func (r *Registry) Marshal(repr cli.Repr) (string, error) {
-// Returns an error if the representation is not registered, or it has no codec.
+	m, ok := r.marshalers[repr.Id()]
-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 "", fmt.Errorf("no marshaler for '%s'", repr.Id())
 	}
 
-	return m.Encode(expr)
+	return m.Encode(repr)
 }
 
-// Unmarshal deserializes an expression. Returns an error if the representation
+func (r *Registry) Unmarshal(s string, outType string) (cli.Repr, error) {
-// or a codec for it is not registered.
+	m, ok := r.marshalers[outType]
-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)
 	}
@@ -114,11 +137,8 @@ func reverse[T any](list []T) []T {
 	return reversed
 }
 
-// ConversionPath attempts to find a set of valid conversions that (if applied)
+func (r *Registry) ConversionPath(from, to string) ([]cli.Conversion, error) {
-// convert one representation to another. Returns an error if no path can be
+	backtrack := map[string]cli.Conversion{}
-// found.
-func (r *Registry) ConversionPath(from, to string) ([]Conversion, error) {
-	backtrack := map[string]Conversion{}
 	iteration := []string{from}
 	for len(iteration) > 0 {
 		nextIteration := []string{}
@@ -137,7 +157,7 @@ func (r *Registry) ConversionPath(from, to string) ([]Conversion, error) {
 		iteration = nextIteration
 	}
 
-	reversedPath := []Conversion{}
+	reversedPath := []cli.Conversion{}
 	current := to
 	for current != from {
 		conversion, ok := backtrack[current]

internal/registry_new/conversion.go

@@ -0,0 +1,9 @@
+package registrynew
+
+// Conversion
+type Conversion interface {
+	InRepr() string
+	OutRepr() string
+
+	Run(Expr) (Expr, error)
+}

internal/registry_new/engine.go

@@ -0,0 +1,12 @@
+package registrynew
+
+type Process interface {
+	Get() (Expr, error)
+	Step(int) bool
+}
+
+type Engine interface {
+	Load(Expr) Process
+	Name() string
+	InRepr() string
+}

internal/registry_new/expr.go

@@ -0,0 +1,7 @@
+package registrynew
+
+type Expr interface {
+	Repr() string
+
+	Data() any
+}

internal/registry_new/marshaler.go

@@ -0,0 +1,5 @@
+package registrynew
+
+type Marshaler interface {
+	InType() string
+}

internal/registry_new/registry.go

@@ -0,0 +1,10 @@
+package registrynew
+
+import "iter"
+
+type Registry interface {
+	ListEngines() iter.Seq[string]
+	GetEngine(name string) (Engine, error)
+
+	ListReprs() iter.Seq[string]
+}

internal/registry_new/repr.go

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

pkg/codec/codec.go

@@ -1,20 +1,8 @@
-// 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.
+type Codec[T, U any] interface {
-// Returns an error if the input expression cannot be converted.
+	Encode(T) (U, error)
-type Conversion[T, U any] = func(T) (U, error)
+	Decode(U) (T, 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)
 }
+
+type Marshaler[T any] = Codec[T, string]

pkg/convert/saccharine_to_lambda.go

@@ -1,16 +1,15 @@
-// Package convert defined some standard conversions between various types of
-// representations.
 package convert
 
 import (
 	"fmt"
 
+	"git.maximhutz.com/max/lambda/pkg/codec"
 	"git.maximhutz.com/max/lambda/pkg/lambda"
 	"git.maximhutz.com/max/lambda/pkg/saccharine"
 )
 
 func encodeAtom(n *saccharine.Atom) lambda.Expression {
-	return lambda.Variable{Name: n.Name}
+	return lambda.NewVariable(n.Name)
 }
 
 func encodeAbstraction(n *saccharine.Abstraction) lambda.Expression {
@@ -21,13 +20,13 @@ func encodeAbstraction(n *saccharine.Abstraction) lambda.Expression {
 	// 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 := lambda.GetFree(result)
+		freeVars := result.GetFree()
 		freshName := lambda.GenerateFreshName(freeVars)
 		parameters = append(parameters, freshName)
 	}
 
 	for i := len(parameters) - 1; i >= 0; i-- {
-		result = lambda.Abstraction{Parameter: parameters[i], Body: result}
+		result = lambda.NewAbstraction(parameters[i], result)
 	}
 
 	return result
@@ -43,7 +42,7 @@ func encodeApplication(n *saccharine.Application) lambda.Expression {
 	}
 
 	for _, argument := range arguments {
-		result = lambda.Application{Abstraction: result, Argument: argument}
+		result = lambda.NewApplication(result, argument)
 	}
 
 	return result
@@ -55,22 +54,22 @@ func reduceLet(s *saccharine.LetStatement, e lambda.Expression) lambda.Expressio
 	if len(s.Parameters) == 0 {
 		value = encodeExpression(s.Body)
 	} else {
-		value = encodeAbstraction(&saccharine.Abstraction{Parameters: s.Parameters, Body: s.Body})
+		value = encodeAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
 	}
 
-	return lambda.Application{
+	return lambda.NewApplication(
-		Abstraction: lambda.Abstraction{Parameter: s.Name, Body: e},
+		lambda.NewAbstraction(s.Name, e),
-		Argument:    value,
+		value,
-	}
+	)
 }
 
 func reduceDeclare(s *saccharine.DeclareStatement, e lambda.Expression) lambda.Expression {
-	freshVar := lambda.GenerateFreshName(lambda.GetFree(e))
+	freshVar := lambda.GenerateFreshName(e.GetFree())
 
-	return lambda.Application{
+	return lambda.NewApplication(
-		Abstraction: lambda.Abstraction{Parameter: freshVar, Body: e},
+		lambda.NewAbstraction(freshVar, e),
-		Argument:    encodeExpression(s.Value),
+		encodeExpression(s.Value),
-	}
+	)
 }
 
 func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Expression {
@@ -112,27 +111,28 @@ func encodeExpression(s saccharine.Expression) lambda.Expression {
 func decodeExression(l lambda.Expression) saccharine.Expression {
 	switch l := l.(type) {
 	case lambda.Variable:
-		return &saccharine.Atom{Name: l.Name}
+		return saccharine.NewAtom(l.Name())
 	case lambda.Abstraction:
-		return &saccharine.Abstraction{
+		return saccharine.NewAbstraction(
-			Parameters: []string{l.Parameter},
+			[]string{l.Parameter()},
-			Body:       decodeExression(l.Body)}
+			decodeExression(l.Body()))
 	case lambda.Application:
-		return &saccharine.Application{
+		return saccharine.NewApplication(
-			Abstraction: decodeExression(l.Abstraction),
+			decodeExression(l.Abstraction()),
-			Arguments:   []saccharine.Expression{decodeExression(l.Argument)}}
+			[]saccharine.Expression{decodeExression(l.Argument())})
 	default:
 		panic(fmt.Errorf("unknown expression type: %T", l))
 	}
 }
 
-// Lambda2Saccharine converts a pure lambda calculus expression into its
+type Saccharine2Lambda struct{}
-// Saccharine counterpart.
+
-func Lambda2Saccharine(l lambda.Expression) (saccharine.Expression, error) {
+func (c Saccharine2Lambda) Decode(l lambda.Expression) (saccharine.Expression, error) {
 	return decodeExression(l), nil
 }
 
-// Saccharine2Lambda desugars a saccharine expression into pure lambda calculus.
+func (c Saccharine2Lambda) Encode(s saccharine.Expression) (lambda.Expression, error) {
-func Saccharine2Lambda(s saccharine.Expression) (lambda.Expression, error) {
 	return encodeExpression(s), nil
 }
+
+var _ codec.Codec[saccharine.Expression, lambda.Expression] = (*Saccharine2Lambda)(nil)

pkg/emitter/emitter.go

@@ -0,0 +1,46 @@
+package emitter
+
+import "git.maximhutz.com/max/lambda/pkg/set"
+
+type Emitter[E comparable] interface {
+	On(E, func()) Listener[E]
+	Off(Listener[E])
+	Emit(E)
+}
+
+type BaseEmitter[E comparable] struct {
+	listeners map[E]set.Set[Listener[E]]
+}
+
+func (e *BaseEmitter[E]) On(kind E, fn func()) Listener[E] {
+	if e.listeners[kind] == nil {
+		e.listeners[kind] = set.New[Listener[E]]()
+	}
+
+	listener := &BaseListener[E]{kind, fn}
+	e.listeners[kind].Add(listener)
+	return listener
+}
+
+func (e *BaseEmitter[E]) Off(listener Listener[E]) {
+	kind := listener.Kind()
+	if e.listeners[kind] != nil {
+		e.listeners[kind].Remove(listener)
+	}
+}
+
+func (e *BaseEmitter[E]) Emit(event E) {
+	if e.listeners[event] == nil {
+		e.listeners[event] = set.New[Listener[E]]()
+	}
+
+	for listener := range e.listeners[event].Items() {
+		listener.Run()
+	}
+}
+
+func New[E comparable]() *BaseEmitter[E] {
+	return &BaseEmitter[E]{
+		listeners: map[E]set.Set[Listener[E]]{},
+	}
+}

pkg/emitter/listener.go

@@ -0,0 +1,19 @@
+package emitter
+
+type Listener[E comparable] interface {
+	Kind() E
+	Run()
+}
+
+type BaseListener[E comparable] struct {
+	kind E
+	fn   func()
+}
+
+func (l BaseListener[E]) Kind() E {
+	return l.kind
+}
+
+func (l BaseListener[E]) Run() {
+	l.fn()
+}

pkg/engine/engine.go

@@ -1,18 +1,11 @@
-// Package engine defines a general process of reducing a lambda calculus
-// expression.
 package engine
 
-// A Process handles the reduction of a single expression.
+type Engine[T any] interface {
-type Process[T any] interface {
+	Load() Process[T]
-	// Get the current state of the process.
-	// Returns an error if the current state cannot be represented.
-	Get() (T, error)
-
-	// 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
 }
 
-// An Engine is an function that generates reduction processes.
+type Process[T any] interface {
-type Engine[T any] = func(T) (Process[T], error)
+	Get() (T, error)
+	Set(T) error
+	Step(int) bool
+}

pkg/engine/normalorder/engine.go

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

pkg/engine/normalorder/reduce_once.go

@@ -1,39 +0,0 @@
-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/engine/normalorder/reduce_one.go

@@ -0,0 +1,34 @@
+package normalorder
+
+import "git.maximhutz.com/max/lambda/pkg/lambda"
+
+func ReduceOnce(e lambda.Expression) (lambda.Expression, bool) {
+	switch e := e.(type) {
+	case lambda.Abstraction:
+		body, reduced := ReduceOnce(e.Body())
+		if reduced {
+			return lambda.NewAbstraction(e.Parameter(), body), true
+		}
+		return e, false
+
+	case lambda.Application:
+		if fn, fnOk := e.Abstraction().(lambda.Abstraction); fnOk {
+			return fn.Body().Substitute(fn.Parameter(), e.Argument()), true
+		}
+
+		abs, reduced := ReduceOnce(e.Abstraction())
+		if reduced {
+			return lambda.NewApplication(abs, e.Argument()), true
+		}
+
+		arg, reduced := ReduceOnce(e.Argument())
+		if reduced {
+			return lambda.NewApplication(e.Abstraction(), arg), true
+		}
+
+		return e, false
+
+	default:
+		return e, false
+	}
+}

pkg/iterator/iterator.go

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

@@ -1,27 +0,0 @@
-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/expression.go

@@ -0,0 +1,100 @@
+package lambda
+
+import (
+	"fmt"
+
+	"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 {
+	fmt.Stringer
+
+	// 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
+}
+
+/** ------------------------------------------------------------------------- */
+
+type Abstraction struct {
+	parameter string
+	body      Expression
+}
+
+var _ Expression = Abstraction{}
+
+func (a Abstraction) Parameter() string {
+	return a.parameter
+}
+
+func (a Abstraction) Body() Expression {
+	return a.body
+}
+
+func (a Abstraction) String() string {
+	return "\\" + a.parameter + "." + a.body.String()
+}
+
+func NewAbstraction(parameter string, body Expression) Abstraction {
+	return Abstraction{parameter, body}
+}
+
+/** ------------------------------------------------------------------------- */
+
+type Application struct {
+	abstraction Expression
+	argument    Expression
+}
+
+var _ Expression = Application{}
+
+func (a Application) Abstraction() Expression {
+	return a.abstraction
+}
+
+func (a Application) Argument() Expression {
+	return a.argument
+}
+
+func (a Application) String() string {
+	return "(" + a.abstraction.String() + " " + a.argument.String() + ")"
+}
+
+func NewApplication(abstraction Expression, argument Expression) Application {
+	return Application{abstraction, argument}
+}
+
+/** ------------------------------------------------------------------------- */
+
+type Variable struct {
+	name string
+}
+
+var _ Expression = Variable{}
+
+func (v Variable) Name() string {
+	return v.name
+}
+
+func (v Variable) String() string {
+	return v.name
+}
+
+func NewVariable(name string) Variable {
+	return Variable{name}
+}

pkg/lambda/get_free_variables.go

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

pkg/lambda/is_free_variable.go

@@ -1,18 +1,12 @@
 package lambda
 
-import "fmt"
+func (e Variable) IsFree(n string) bool {
+	return e.Name() == n
+}
 
-// IsFree returns true if the variable name n occurs free in the expression.
+func (e Abstraction) IsFree(n string) bool {
-// This function does not mutate the input expression.
+	return e.Parameter() != n && e.Body().IsFree(n)
-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))
 }
+func (e Application) IsFree(n string) bool {
+	return e.Abstraction().IsFree(n) || e.Argument().IsFree(n)
 }

pkg/lambda/lambda.go

@@ -1,31 +0,0 @@
-// 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/marshaler.go

@@ -0,0 +1,19 @@
+package lambda
+
+import (
+	"fmt"
+
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+type Marshaler struct{}
+
+func (m Marshaler) Decode(string) (Expression, error) {
+	return nil, fmt.Errorf("unimplemented")
+}
+
+func (m Marshaler) Encode(e Expression) (string, error) {
+	return e.String(), nil
+}
+
+var _ codec.Marshaler[Expression] = (*Marshaler)(nil)

pkg/lambda/parse.go

@@ -1,80 +0,0 @@
-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

@@ -1,31 +1,28 @@
 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 {
+func (e Variable) Rename(target string, newName string) Expression {
-	switch e := e.(type) {
+	if e.Name() == target {
-	case Variable:
+		return NewVariable(newName)
-		if e.Name == target {
-			return Variable{Name: newName}
 	}
 
 	return e
-	case Abstraction:
+}
-		newParam := e.Parameter
+
-		if e.Parameter == target {
+func (e Abstraction) Rename(target string, newName string) Expression {
+	newParam := e.Parameter()
+	if e.Parameter() == target {
 		newParam = newName
 	}
 
-		newBody := Rename(e.Body, target, newName)
+	newBody := e.Body().Rename(target, newName)
 
-		return Abstraction{Parameter: newParam, Body: newBody}
+	return NewAbstraction(newParam, newBody)
-	case Application:
+}
-		newAbs := Rename(e.Abstraction, target, newName)
-		newArg := Rename(e.Argument, target, newName)
 
-		return Application{Abstraction: newAbs, Argument: newArg}
+func (e Application) Rename(target string, newName string) Expression {
-	default:
+	newAbs := e.Abstraction().Rename(target, newName)
-		panic(fmt.Errorf("unknown expression type: %v", e))
+	newArg := e.Argument().Rename(target, newName)
-	}
+
+	return NewApplication(newAbs, newArg)
 }

pkg/lambda/scan.go

@@ -1,18 +0,0 @@
-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

@@ -1,17 +0,0 @@
-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

@@ -1,41 +1,35 @@
 package lambda
 
-import "fmt"
+func (e Variable) Substitute(target string, replacement Expression) Expression {
-
+	if e.Name() == target {
-// 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 {
+
+func (e Abstraction) Substitute(target string, replacement Expression) Expression {
+	if e.Parameter() == target {
 		return e
 	}
 
-		body := e.Body
+	body := e.Body()
-		param := e.Parameter
+	param := e.Parameter()
-		if IsFree(replacement, param) {
+	if replacement.IsFree(param) {
-			freeVars := GetFree(replacement)
+		freeVars := replacement.GetFree()
-			freeVars.Merge(GetFree(body))
+		freeVars.Merge(body.GetFree())
 		freshVar := GenerateFreshName(freeVars)
-			body = Rename(body, param, freshVar)
+		body = body.Rename(param, freshVar)
 		param = freshVar
 	}
 
-		newBody := Substitute(body, target, replacement)
+	newBody := body.Substitute(target, replacement)
-		return Abstraction{Parameter: param, Body: newBody}
+	return NewAbstraction(param, newBody)
-	case Application:
+}
-		abs := Substitute(e.Abstraction, target, replacement)
-		arg := Substitute(e.Argument, target, replacement)
 
-		return Application{Abstraction: abs, Argument: arg}
+func (e Application) Substitute(target string, replacement Expression) Expression {
-	default:
+	abs := e.Abstraction().Substitute(target, replacement)
-		panic(fmt.Errorf("unknown expression type: %v", e))
+	arg := e.Argument().Substitute(target, replacement)
-	}
+
+	return NewApplication(abs, arg)
 }

pkg/lambda/token.go

@@ -1,45 +0,0 @@
-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/saccharine/codec.go

@@ -1,27 +0,0 @@
-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/expression.go

@@ -0,0 +1,49 @@
+package saccharine
+
+type Expression interface {
+	IsExpression()
+}
+
+/** ------------------------------------------------------------------------- */
+
+type Abstraction struct {
+	Parameters []string
+	Body       Expression
+}
+
+type Application struct {
+	Abstraction Expression
+	Arguments   []Expression
+}
+
+type Atom struct {
+	Name string
+}
+
+type Clause struct {
+	Statements []Statement
+	Returns    Expression
+}
+
+func (Abstraction) IsExpression() {}
+func (Application) IsExpression() {}
+func (Atom) IsExpression()        {}
+func (Clause) IsExpression()      {}
+
+/** ------------------------------------------------------------------------- */
+
+func NewAbstraction(parameter []string, body Expression) *Abstraction {
+	return &Abstraction{Parameters: parameter, Body: body}
+}
+
+func NewApplication(abstraction Expression, arguments []Expression) *Application {
+	return &Application{Abstraction: abstraction, Arguments: arguments}
+}
+
+func NewAtom(name string) *Atom {
+	return &Atom{Name: name}
+}
+
+func NewClause(statements []Statement, returns Expression) *Clause {
+	return &Clause{Statements: statements, Returns: returns}
+}

pkg/saccharine/marshaler.go

@@ -0,0 +1,24 @@
+// Package "saccharine" provides a simple language built on top of λ-calculus,
+// to facilitate productive coding using it.
+package saccharine
+
+import (
+	"git.maximhutz.com/max/lambda/pkg/codec"
+)
+
+type Marshaler struct{}
+
+func (m Marshaler) Decode(s string) (Expression, error) {
+	tokens, err := scan(s)
+	if err != nil {
+		return nil, err
+	}
+
+	return parse(tokens)
+}
+
+func (m Marshaler) Encode(e Expression) (string, error) {
+	return stringifyExpression(e), nil
+}
+
+var _ codec.Marshaler[Expression] = (*Marshaler)(nil)

pkg/saccharine/parse.go

@@ -5,89 +5,122 @@ import (
 	"fmt"
 
 	"git.maximhutz.com/max/lambda/pkg/iterator"
-	"git.maximhutz.com/max/lambda/pkg/token"
+	"git.maximhutz.com/max/lambda/pkg/trace"
 )
 
-type tokenIterator = iterator.Iterator[Token]
+type TokenIterator = iterator.Iterator[Token]
 
-func passSoftBreaks(i *tokenIterator) {
+func parseRawToken(i *TokenIterator, expected TokenType) (*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'", expected.Name(), tok.Value)
+		} else {
+			return &tok, nil
+		}
+	})
+}
+
+func passSoftBreaks(i *TokenIterator) {
 	for {
-		if _, err := token.ParseRawToken(i, TokenSoftBreak); err != nil {
+		if _, err := parseRawToken(i, TokenSoftBreak); err != nil {
 			return
 		}
 	}
 }
 
-func parseToken(i *tokenIterator, expected TokenType, ignoreSoftBreaks bool) (*Token, error) {
+func parseToken(i *TokenIterator, expected TokenType, ignoreSoftBreaks bool) (*Token, error) {
+	return iterator.Do(i, func(i *TokenIterator) (*Token, error) {
 		if ignoreSoftBreaks {
 			passSoftBreaks(i)
 		}
 
-	return token.ParseRawToken(i, expected)
+		return parseRawToken(i, expected)
+	})
 }
 
-func parseString(i *tokenIterator) (string, error) {
+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)
+		return "", trace.Wrap(err, "no variable (col %d)", i.Index())
 	} else {
 		return tok.Value, nil
 	}
 }
 
-func parseBreak(i *tokenIterator) (*Token, error) {
+func parseBreak(i *TokenIterator) (*Token, error) {
-	if tok, softErr := token.ParseRawToken(i, TokenSoftBreak); softErr == nil {
+	if tok, softErr := parseRawToken(i, TokenSoftBreak); softErr == nil {
 		return tok, nil
-	} else if tok, hardErr := token.ParseRawToken(i, TokenHardBreak); hardErr == nil {
+	} else if tok, hardErr := parseRawToken(i, TokenHardBreak); hardErr == nil {
 		return tok, nil
 	} else {
 		return nil, errors.Join(softErr, hardErr)
 	}
 }
 
-func parseAbstraction(i *tokenIterator) (*Abstraction, error) {
+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, fmt.Errorf("no function slash (col %d): %w", i.MustGet().Column, err)
+			return nil, trace.Wrap(err, "no function slash (col %d)", i.MustGet().Column)
-	} else if parameters, err := token.ParseList(i, parseString, 0); err != nil {
+		} else if parameters, err := 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)
+			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 &Abstraction{Parameters: parameters, Body: body}, nil
+			return NewAbstraction(parameters, body), nil
 		}
+	})
 }
 
-func parseApplication(i *tokenIterator) (*Application, error) {
+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, fmt.Errorf("no openning brackets (col %d): %w", i.MustGet().Column, err)
+			return nil, trace.Wrap(err, "no openning brackets (col %d)", i.MustGet().Column)
-	} else if expressions, err := token.ParseList(i, parseExpression, 1); err != nil {
+		} else if expressions, err := 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)
+			return nil, trace.Wrap(err, "no closing brackets (col %d)", i.MustGet().Column)
 		} else {
-		return &Application{Abstraction: expressions[0], Arguments: expressions[1:]}, nil
+			return NewApplication(expressions[0], expressions[1:]), nil
 		}
+	})
 }
 
-func parseAtom(i *tokenIterator) (*Atom, error) {
+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)
+		return nil, trace.Wrap(err, "no variable (col %d)", i.Index())
 	} else {
-		return &Atom{Name: tok.Value}, nil
+		return NewAtom(tok.Value), nil
 	}
 }
 
-func parseStatements(i *tokenIterator) ([]Statement, error) {
+func parseStatements(i *TokenIterator) ([]Statement, error) {
 	statements := []Statement{}
 
 	//nolint:errcheck
-	token.ParseList(i, parseBreak, 0)
+	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() {
+		} else if _, err := parseList(i, parseBreak, 1); err != nil && !i.Done() {
 			break
 		} else {
 			statements = append(statements, statement)
@@ -97,7 +130,7 @@ func parseStatements(i *tokenIterator) ([]Statement, error) {
 	return statements, nil
 }
 
-func parseClause(i *tokenIterator, braces bool) (*Clause, error) {
+func parseClause(i *TokenIterator, braces bool) (*Clause, error) {
 	if braces {
 		if _, err := parseToken(i, TokenOpenBrace, true); err != nil {
 			return nil, err
@@ -123,16 +156,13 @@ func parseClause(i *tokenIterator, braces bool) (*Clause, error) {
 		}
 	}
 
-	return &Clause{Statements: stmts[:len(stmts)-1], Returns: last.Value}, nil
+	return NewClause(stmts[:len(stmts)-1], last.Value), nil
 }
 
-func parseExpression(i *tokenIterator) (Expression, error) {
+func parseExpression(i *TokenIterator) (Expression, error) {
+	return iterator.Do(i, func(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)
@@ -145,32 +175,35 @@ func parseExpression(i *tokenIterator) (Expression, error) {
 		default:
 			return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
 		}
+	})
 }
 
-func parseLet(i *tokenIterator) (*LetStatement, error) {
+func parseLet(i *TokenIterator) (*LetStatement, error) {
-	if parameters, err := token.ParseList(i, parseString, 1); err != nil {
+	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 &LetStatement{Name: parameters[0], Parameters: parameters[1:], Body: body}, nil
+			return NewLet(parameters[0], parameters[1:], body), nil
 		}
+	})
 }
 
-func parseDeclare(i *tokenIterator) (*DeclareStatement, error) {
+func parseDeclare(i *TokenIterator) (*DeclareStatement, error) {
 	if value, err := parseExpression(i); err != nil {
 		return nil, err
 	} else {
-		return &DeclareStatement{Value: value}, nil
+		return NewDeclare(value), nil
 	}
 }
 
-func parseStatement(i *tokenIterator) (Statement, error) {
+func parseStatement(i *TokenIterator) (Statement, error) {
-	if let, letErr := iterator.Try(i, parseLet); letErr == nil {
+	if let, letErr := parseLet(i); letErr == nil {
 		return let, nil
-	} else if declare, declErr := iterator.Try(i, parseDeclare); declErr == nil {
+	} else if declare, declErr := parseDeclare(i); declErr == nil {
 		return declare, nil
 	} else {
 		return nil, errors.Join(letErr, declErr)

pkg/saccharine/saccharine.go

@@ -1,60 +0,0 @@
-// 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

@@ -1,24 +1,130 @@
 package saccharine
 
-import "git.maximhutz.com/max/lambda/pkg/token"
+import (
+	"errors"
+	"fmt"
+	"unicode"
 
-// scanner is the declarative lexer for the Saccharine language.
+	"git.maximhutz.com/max/lambda/pkg/iterator"
-var scanner = token.NewScanner(
+	"git.maximhutz.com/max/lambda/pkg/trace"
-	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.
+// isVariables determines whether a rune can be a valid variable.
-func scan(input string) ([]Token, error) {
+func isVariable(r rune) bool {
-	return scanner.Scan(input)
+	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 NewTokenOpenParen(index), nil
+	case letter == ')':
+		return NewTokenCloseParen(index), nil
+	case letter == '.':
+		return NewTokenDot(index), nil
+	case letter == '\\':
+		return NewTokenSlash(index), nil
+	case letter == '\n':
+		return NewTokenSoftBreak(index), nil
+	case letter == '{':
+		return NewTokenOpenBrace(index), nil
+	case letter == '}':
+		return NewTokenCloseBrace(index), nil
+	case letter == ':':
+		if _, err := scanCharacter(i, '='); err != nil {
+			return nil, err
+		} else {
+			return NewTokenAssign(index), nil
+		}
+	case letter == ';':
+		return NewTokenHardBreak(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 NewTokenAtom(string(atom), index), nil
+	}
+
+	return nil, fmt.Errorf("unknown character '%v'", string(letter))
+}
+
+// scan 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/saccharine/statement.go

@@ -0,0 +1,30 @@
+package saccharine
+
+type Statement interface {
+	IsStatement()
+}
+
+/** ------------------------------------------------------------------------- */
+
+type LetStatement struct {
+	Name       string
+	Parameters []string
+	Body       Expression
+}
+
+type DeclareStatement struct {
+	Value Expression
+}
+
+func (LetStatement) IsStatement()     {}
+func (DeclareStatement) IsStatement() {}
+
+/** ------------------------------------------------------------------------- */
+
+func NewLet(name string, parameters []string, body Expression) *LetStatement {
+	return &LetStatement{Name: name, Parameters: parameters, Body: body}
+}
+
+func NewDeclare(value Expression) *DeclareStatement {
+	return &DeclareStatement{Value: value}
+}

pkg/saccharine/token.go

@@ -1,65 +1,91 @@
 package saccharine
 
-import (
+import "fmt"
-	"fmt"
 
-	"git.maximhutz.com/max/lambda/pkg/token"
+// All tokens in the pseudo-lambda language.
-)
-
-// 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 // Denotes the '(' token.
-	TokenOpenParen TokenType = iota
+	TokenCloseParen                  // Denotes the ')' token.
-	// TokenCloseParen denotes the ')' token.
+	TokenOpenBrace                   // Denotes the '{' token.
-	TokenCloseParen
+	TokenCloseBrace                  // Denotes the '}' token.
-	// TokenOpenBrace denotes the '{' token.
+	TokenHardBreak                   // Denotes the ';' token.
-	TokenOpenBrace
+	TokenAssign                      // Denotes the ':=' token.
-	// TokenCloseBrace denotes the '}' token.
+	TokenAtom                        // Denotes an alpha-numeric variable.
-	TokenCloseBrace
+	TokenSlash                       // Denotes the '/' token.
-	// TokenHardBreak denotes the ';' token.
+	TokenDot                         // Denotes the '.' token.
-	TokenHardBreak
+	TokenSoftBreak                   // Denotes a new-line.
-	// 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.
+// A representation of a token in source code.
+type Token struct {
+	Column int       // Where the token begins in the source text.
+	Type   TokenType // What type the token is.
+	Value  string    // The value of the token.
+}
+
+func NewTokenOpenParen(column int) *Token {
+	return &Token{Type: TokenOpenParen, Column: column, Value: "("}
+}
+
+func NewTokenCloseParen(column int) *Token {
+	return &Token{Type: TokenCloseParen, Column: column, Value: ")"}
+}
+
+func NewTokenOpenBrace(column int) *Token {
+	return &Token{Type: TokenOpenBrace, Column: column, Value: "{"}
+}
+
+func NewTokenCloseBrace(column int) *Token {
+	return &Token{Type: TokenCloseBrace, Column: column, Value: "}"}
+}
+
+func NewTokenDot(column int) *Token {
+	return &Token{Type: TokenDot, Column: column, Value: "."}
+}
+
+func NewTokenHardBreak(column int) *Token {
+	return &Token{Type: TokenHardBreak, Column: column, Value: ";"}
+}
+
+func NewTokenAssign(column int) *Token {
+	return &Token{Type: TokenAssign, Column: column, Value: ":="}
+}
+
+func NewTokenSlash(column int) *Token {
+	return &Token{Type: TokenSlash, Column: column, Value: "\\"}
+}
+
+func NewTokenAtom(name string, column int) *Token {
+	return &Token{Type: TokenAtom, Column: column, Value: name}
+}
+
+func NewTokenSoftBreak(column int) *Token {
+	return &Token{Type: TokenSoftBreak, Column: column, Value: "\\n"}
+}
+
 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 TokenAtom:
+		return "ATOM"
 	case TokenSoftBreak:
 		return "\\n"
+	case TokenHardBreak:
+		return ";"
 	default:
 		panic(fmt.Errorf("unknown token type %v", t))
 	}
 }
 
-// Token is the concrete token type for the Saccharine language.
+func (t Token) Name() string {
-type Token = token.Token[TokenType]
+	return t.Type.Name()
+}

pkg/set/set.go

@@ -1,41 +1,31 @@
-// 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{}
 
@@ -46,8 +36,6 @@ 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 {
@@ -58,7 +46,6 @@ 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

@@ -1,42 +0,0 @@
-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

@@ -1,129 +0,0 @@
-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

@@ -1,24 +0,0 @@
-// 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

@@ -0,0 +1,25 @@
+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)
+}