mvhutz/lambda
1
0
Fork 0
Code Issues 3 Pull Requests Actions Packages Projects Releases Wiki Activity

Compare commits

base: mvhutz:feat/updated-arch
Branches Tags
mvhutz:main mvhutz:feat/updated-arch mvhutz:feat/upgrade mvhutz:feat/debruijn-engine
..
compare: mvhutz:528956b03394844064544eaac27aa0fa04245bd5
Branches Tags
mvhutz:feat/updated-arch mvhutz:feat/upgrade mvhutz:main mvhutz:feat/debruijn-engine

1 Commits
feat/updat ... 528956b033

Author SHA1 Message Date
M.V. Hutz
528956b033 feat: add De Bruijn indexed reduction engine 
Add a new interpreter option (-i debruijn) that uses De Bruijn indices
for variable representation, eliminating the need for variable renaming
during substitution.

- Add -i flag to select interpreter (lambda or debruijn)
- Create debruijn package with Expression types (Variable with index,
  Abstraction without parameter, Application)
- Implement shift and substitute operations for De Bruijn indices
- Add conversion functions between lambda and De Bruijn representations
- Update CLI to support switching between interpreters
- Add De Bruijn tests to verify all samples pass

Closes #26
 2026-01-16 19:36:05 -05:00
59 changed files with 1471 additions and 745 deletions
Expand all files Collapse all files

2
.gitea/ISSUE_TEMPLATE/bug.md
View File

@@ -1,6 +1,6 @@
---
name: "Bug Report"
about: "Report a bug or unexpected behavior in the lambda runtime."
about: "Report a bug or unexpected behavior in the lambda interpreter."
title: "fix: "
ref: "main"
assignees: []

2
.gitea/ISSUE_TEMPLATE/feature.md
View File

@@ -1,6 +1,6 @@
---
name: "Feature Request"
about: "Suggest a new feature or enhancement for the lambda runtime."
about: "Suggest a new feature or enhancement for the lambda interpreter."
title: "feat: "
ref: "main"
assignees: []

5
.golangci.yml
View File

@@ -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,9 +126,6 @@ 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:

2
LICENSE
View File

@@ -48,7 +48,7 @@ The "source code" for a work means the preferred form of the work for making mod
A "Standard Interface" means an interface that either is an official standard defined by a recognized standards body, or, in the case of interfaces specified for a particular programming language, one that is widely used among developers working in that language.
The "System Libraries" of an executable work include anything, other than the work as a whole, that (a) is included in the normal form of packaging a Major Component, but which is not part of that Major Component, and (b) serves only to enable use of the work with that Major Component, or to implement a Standard Interface for which an implementation is available to the public in source code form. A "Major Component", in this context, means a major essential component (kernel, window system, and so on) of the specific operating system (if any) on which the executable work runs, or a compiler used to produce the work, or an object code runtime used to run it.
The "System Libraries" of an executable work include anything, other than the work as a whole, that (a) is included in the normal form of packaging a Major Component, but which is not part of that Major Component, and (b) serves only to enable use of the work with that Major Component, or to implement a Standard Interface for which an implementation is available to the public in source code form. A "Major Component", in this context, means a major essential component (kernel, window system, and so on) of the specific operating system (if any) on which the executable work runs, or a compiler used to produce the work, or an object code interpreter used to run it.
The "Corresponding Source" for a work in object code form means all the source code needed to generate, install, and (for an executable work) run the object code and to modify the work, including scripts to control those activities. However, it does not include the work's System Libraries, or general-purpose tools or generally available free programs which are used unmodified in performing those activities but which are not part of the work. For example, Corresponding Source includes interface definition files associated with source files for the work, and the source code for shared libraries and dynamically linked subprograms that the work is specifically designed to require, such as by intimate data communication or control flow between those
subprograms and other parts of the work.

8
Makefile
View File

@@ -1,21 +1,20 @@
BINARY_NAME=lambda
TEST=simple
.PHONY: help build run profile explain graph docs test bench lint clean
.PHONY: help build run profile explain graph docs test bench 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 " run - Build and run the lambda interpreter (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 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:
@@ -46,9 +45,6 @@ test:
bench:
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}
rm -f program.out

2
README.md
View File

@@ -1,6 +1,6 @@
# lambda
Making a lambda calculus runtime in Go.
Making a lambda calculus interpreter in Go.
## Things to talk about

36
cmd/lambda/lambda.go
View File

@@ -7,7 +7,9 @@ import (
"git.maximhutz.com/max/lambda/internal/config"
"git.maximhutz.com/max/lambda/internal/plugins"
"git.maximhutz.com/max/lambda/pkg/convert"
"git.maximhutz.com/max/lambda/pkg/normalorder"
"git.maximhutz.com/max/lambda/pkg/debruijn"
"git.maximhutz.com/max/lambda/pkg/lambda"
"git.maximhutz.com/max/lambda/pkg/reducer"
"git.maximhutz.com/max/lambda/pkg/saccharine"
)
@@ -33,35 +35,51 @@ func main() {
compiled := convert.SaccharineToLambda(ast)
logger.Info("compiled λ expression", "tree", compiled.String())
// Create reducer with the compiled expression.
runtime := normalorder.NewRuntime(compiled)
// Create reducer based on the selected interpreter.
var red reducer.Reducer
switch options.Interpreter {
case config.DeBruijnInterpreter:
dbExpr := convert.LambdaToDeBruijn(compiled)
logger.Info("converted to De Bruijn", "tree", dbExpr.String())
red = debruijn.NewNormalOrderReducer(&dbExpr)
default:
red = lambda.NewNormalOrderReducer(&compiled)
}
// If the user selected to track CPU performance, attach a profiler.
if options.Profile != "" {
plugins.NewPerformance(options.Profile, runtime)
plugins.NewPerformance(options.Profile, red)
}
// If the user selected to produce a step-by-step explanation, attach an
// observer.
if options.Explanation {
plugins.NewExplanation(runtime)
plugins.NewExplanation(red)
}
// If the user opted to track statistics, attach a tracker.
if options.Statistics {
plugins.NewStatistics(runtime)
plugins.NewStatistics(red)
}
// If the user selected for verbose debug logs, attach a reduction tracker.
if options.Verbose {
plugins.NewLogs(logger, runtime)
plugins.NewLogs(logger, red)
}
// Run reduction.
runtime.Run()
red.Reduce()
// Return the final reduced result.
result := runtime.Expression().String()
// For De Bruijn, convert back to lambda for consistent output.
var result string
if options.Interpreter == config.DeBruijnInterpreter {
dbExpr := red.Expression().(debruijn.Expression)
lambdaExpr := convert.DeBruijnToLambda(dbExpr)
result = lambdaExpr.String()
} else {
result = red.Expression().String()
}
err = options.Destination.Write(result)
cli.HandleError(err)
}

88
cmd/lambda/lambda_test.go
View File

@@ -7,12 +7,13 @@ import (
"testing"
"git.maximhutz.com/max/lambda/pkg/convert"
"git.maximhutz.com/max/lambda/pkg/normalorder"
"git.maximhutz.com/max/lambda/pkg/debruijn"
"git.maximhutz.com/max/lambda/pkg/lambda"
"git.maximhutz.com/max/lambda/pkg/saccharine"
"github.com/stretchr/testify/assert"
)
// Helper function to run a single sample through the lambda runtime.
// Helper function to run a single sample through the lambda interpreter.
func runSample(samplePath string) (string, error) {
// Read the sample file.
input, err := os.ReadFile(samplePath)
@@ -30,13 +31,42 @@ func runSample(samplePath string) (string, error) {
compiled := convert.SaccharineToLambda(ast)
// Create and run the reducer.
reducer := normalorder.NewRuntime(compiled)
reducer.Run()
reducer := lambda.NewNormalOrderReducer(&compiled)
reducer.Reduce()
return reducer.Expression().String() + "\n", nil
}
// Test that all samples produce expected output.
// Helper function to run a single sample through the De Bruijn interpreter.
func runSampleDeBruijn(samplePath string) (string, error) {
// Read the sample file.
input, err := os.ReadFile(samplePath)
if err != nil {
return "", err
}
// Parse code into syntax tree.
ast, err := saccharine.Parse(string(input))
if err != nil {
return "", err
}
// Compile expression to lambda calculus.
compiled := convert.SaccharineToLambda(ast)
// Convert to De Bruijn and run reducer.
dbExpr := convert.LambdaToDeBruijn(compiled)
reducer := debruijn.NewNormalOrderReducer(&dbExpr)
reducer.Reduce()
// Convert back to lambda for output.
result := reducer.Expression().(debruijn.Expression)
lambdaResult := convert.DeBruijnToLambda(result)
return lambdaResult.String() + "\n", nil
}
// Test that all samples produce expected output with lambda interpreter.
func TestSamplesValidity(t *testing.T) {
// Discover all .test files in the tests directory.
testFiles, err := filepath.Glob("../../tests/*.test")
@@ -65,6 +95,35 @@ func TestSamplesValidity(t *testing.T) {
}
}
// Test that all samples produce expected output with De Bruijn interpreter.
func TestSamplesValidityDeBruijn(t *testing.T) {
// Discover all .test files in the tests directory.
testFiles, err := filepath.Glob("../../tests/*.test")
assert.NoError(t, err, "Failed to read tests directory.")
assert.NotEmpty(t, testFiles, "No '*.test' files found in directory.")
for _, testPath := range testFiles {
// Build expected file path.
expectedPath := strings.TrimSuffix(testPath, filepath.Ext(testPath)) + ".expected"
name := strings.TrimSuffix(filepath.Base(testPath), filepath.Ext(testPath))
t.Run(name, func(t *testing.T) {
// Run the sample and capture output.
actual, err := runSampleDeBruijn(testPath)
assert.NoError(t, err, "Failed to run sample.")
// Read expected output.
expectedBytes, err := os.ReadFile(expectedPath)
assert.NoError(t, err, "Failed to read expected output.")
expected := string(expectedBytes)
// Compare outputs.
assert.Equal(t, expected, actual, "Output does not match expected.")
})
}
}
// Benchmark all samples using sub-benchmarks.
func BenchmarkSamples(b *testing.B) {
// Discover all .test files in the tests directory.
@@ -83,3 +142,22 @@ func BenchmarkSamples(b *testing.B) {
})
}
}
// Benchmark all samples using De Bruijn interpreter.
func BenchmarkSamplesDeBruijn(b *testing.B) {
// Discover all .test files in the tests directory.
testFiles, err := filepath.Glob("../../tests/*.test")
assert.NoError(b, err, "Failed to read tests directory.")
assert.NotEmpty(b, testFiles, "No '*.test' files found in directory.")
for _, path := range testFiles {
name := strings.TrimSuffix(filepath.Base(path), filepath.Ext(path))
b.Run(name, func(b *testing.B) {
for b.Loop() {
_, err := runSampleDeBruijn(path)
assert.NoError(b, err, "Failed to run sample.")
}
})
}
}

26
cmd/lambda/registry.go
View File

@@ -1,26 +0,0 @@
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"
"git.maximhutz.com/max/lambda/pkg/lambda"
"git.maximhutz.com/max/lambda/pkg/saccharine"
)
func MakeRegistry() *registry.Registry {
r := registry.New()
// Codecs
r.AddCodec(cli.ConvertCodec(convert.Saccharine2Lambda{}, "saccharine", "lambda"))
// Engines
r.AddEngine(cli.ConvertEngine(normalorder.Engine{}, "normalorder", "lambda"))
// Marshalers
r.AddMarshaler(cli.ConvertMarshaler(lambda.Marshaler{}, "lambda"))
r.AddMarshaler(cli.ConvertMarshaler(saccharine.Marshaler{}, "saccharine"))
return r
}

55
internal/cli/codec.go
View File

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

49
internal/cli/engine.go
View File

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

42
internal/cli/marshaler.go
View File

@@ -1,42 +0,0 @@
package cli
import (
"fmt"
"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 {
return "", fmt.Errorf("could not parse '%v' as 'string'", t)
}
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}
}

21
internal/cli/repr.go
View File

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

9
internal/config/config.go
View File

@@ -1,6 +1,14 @@
// Package "config" parses ad handles the user settings given to the program.
package config
// Interpreter specifies the reduction engine to use.
type Interpreter string
const (
LambdaInterpreter Interpreter = "lambda"
DeBruijnInterpreter Interpreter = "debruijn"
)
// Configuration settings for the program.
type Config struct {
Source Source // The source code given to the program.
@@ -9,4 +17,5 @@ type Config struct {
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.
Interpreter Interpreter // The interpreter engine to use.
}

13
internal/config/parse_from_args.go
View File

@@ -14,8 +14,20 @@ func FromArgs() (*Config, error) {
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).")
interpreter := flag.String("i", "lambda", "Interpreter. The reduction engine to use: 'lambda' or 'debruijn'.")
flag.Parse()
// Validate interpreter flag.
var interpType Interpreter
switch *interpreter {
case "lambda":
interpType = LambdaInterpreter
case "debruijn":
interpType = DeBruijnInterpreter
default:
return nil, fmt.Errorf("invalid interpreter: %s (must be 'lambda' or 'debruijn')", *interpreter)
}
// Parse source type.
var source Source
if *file != "" {
@@ -52,5 +64,6 @@ func FromArgs() (*Config, error) {
Explanation: *explanation,
Profile: *profile,
Statistics: *statistics,
Interpreter: interpType,
}, nil
}

23
internal/plugins/debug.go Normal file
View File

@@ -0,0 +1,23 @@
package plugins
import (
"log/slog"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
type Logs struct {
logger *slog.Logger
reducer reducer.Reducer
}
func NewLogs(logger *slog.Logger, r reducer.Reducer) *Logs {
plugin := &Logs{logger, r}
r.On(reducer.StepEvent, plugin.Step)
return plugin
}
func (t *Logs) Step() {
t.logger.Info("reduction", "tree", t.reducer.Expression().String())
}

31
internal/plugins/explanation.go Normal file
View File

@@ -0,0 +1,31 @@
// Package "explanation" provides an observer to gather the reasoning during the
// reduction, and present a thorough explanation to the user for each step.
package plugins
import (
"fmt"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
// Track the reductions made by a reduction process.
type Explanation struct {
reducer reducer.Reducer
}
// Attaches a new explanation tracker to a reducer.
func NewExplanation(r reducer.Reducer) *Explanation {
plugin := &Explanation{reducer: r}
r.On(reducer.StartEvent, plugin.Start)
r.On(reducer.StepEvent, plugin.Step)
return plugin
}
func (t *Explanation) Start() {
fmt.Println(t.reducer.Expression().String())
}
func (t *Explanation) Step() {
fmt.Println(" =", t.reducer.Expression().String())
}

59
internal/plugins/performance.go Normal file
View File

@@ -0,0 +1,59 @@
// Package "performance" provides a tracker to observer CPU performance during
// execution.
package plugins
import (
"os"
"path/filepath"
"runtime/pprof"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
// Observes a reduction process, and publishes a CPU performance profile on
// completion.
type Performance struct {
File string
filePointer *os.File
Error error
}
// Create a performance tracker that outputs a profile to "file".
func NewPerformance(file string, process reducer.Reducer) *Performance {
plugin := &Performance{File: file}
process.On(reducer.StartEvent, plugin.Start)
process.On(reducer.StopEvent, plugin.Stop)
return plugin
}
// Begin profiling.
func (t *Performance) Start() {
var absPath string
absPath, t.Error = filepath.Abs(t.File)
if t.Error != nil {
return
}
t.Error = os.MkdirAll(filepath.Dir(absPath), 0777)
if t.Error != nil {
return
}
t.filePointer, t.Error = os.Create(absPath)
if t.Error != nil {
return
}
t.Error = pprof.StartCPUProfile(t.filePointer)
if t.Error != nil {
return
}
}
// Stop profiling.
func (t *Performance) Stop() {
pprof.StopCPUProfile()
t.filePointer.Close()
}

44
internal/plugins/statistics.go Normal file
View File

@@ -0,0 +1,44 @@
package plugins
import (
"fmt"
"os"
"time"
"git.maximhutz.com/max/lambda/internal/statistics"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
// An observer, to track reduction performance.
type Statistics struct {
start time.Time
steps uint64
}
// Create a new reduction performance Statistics.
func NewStatistics(r reducer.Reducer) *Statistics {
plugin := &Statistics{}
r.On(reducer.StartEvent, plugin.Start)
r.On(reducer.StepEvent, plugin.Step)
r.On(reducer.StopEvent, plugin.Stop)
return plugin
}
func (t *Statistics) Start() {
t.start = time.Now()
t.steps = 0
}
func (t *Statistics) Step() {
t.steps++
}
func (t *Statistics) Stop() {
results := statistics.Results{
StepsTaken: t.steps,
TimeElapsed: uint64(time.Since(t.start).Milliseconds()),
}
fmt.Fprint(os.Stderr, results.String())
}

75
internal/registry/registry.go
View File

@@ -1,75 +0,0 @@
package registry
import (
"fmt"
"git.maximhutz.com/max/lambda/internal/cli"
)
type Registry struct {
marshalers map[string]cli.Marshaler
codecs []cli.Codec
engines map[string]cli.Engine
}
func New() *Registry {
return &Registry{
marshalers: map[string]cli.Marshaler{},
codecs: []cli.Codec{},
engines: map[string]cli.Engine{},
}
}
func (r *Registry) AddCodec(c cli.Codec) error {
r.codecs = append(r.codecs, c)
return nil
}
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) 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) GetEngine(name string) (cli.Engine, error) {
e, ok := r.engines[name]
if !ok {
return nil, fmt.Errorf("engine '%s' not found", name)
}
return e, nil
}
func (r *Registry) ConvertTo(repr cli.Repr, outType string) (cli.Repr, error) {
panic("")
}
func (r *Registry) Marshal(repr cli.Repr) (string, error) {
m, ok := r.marshalers[repr.Id()]
if !ok {
return "", fmt.Errorf("no marshaler for '%s'", repr.Id())
}
return m.Encode(repr)
}
func (r *Registry) Unmarshal(s string, outType string) (cli.Repr, error) {
m, ok := r.marshalers[outType]
if !ok {
return nil, fmt.Errorf("no marshaler for '%s'", outType)
}
return m.Decode(s)
}

28
internal/statistics/statistics.go Normal file
View File

@@ -0,0 +1,28 @@
// Package "statistics" provides a way to observer reduction speed during
// execution.
package statistics
import (
"fmt"
"strings"
)
// Statistics for a specific reduction.
type Results struct {
StepsTaken uint64 // Number of steps taken during execution.
TimeElapsed uint64 // The time (ms) taken for execution to complete.
}
// Returns the average number of operations per second of the execution.
func (r Results) OpsPerSecond() float32 {
return float32(r.StepsTaken) / (float32(r.TimeElapsed) / 1000)
}
// Format the results as a string.
func (r Results) String() string {
builder := strings.Builder{}
fmt.Fprintln(&builder, "Time Spent:", r.TimeElapsed, "ms")
fmt.Fprintln(&builder, "Steps:", r.StepsTaken)
fmt.Fprintln(&builder, "Speed:", r.OpsPerSecond(), "ops")
return builder.String()
}

8
pkg/codec/codec.go
View File

@@ -1,8 +0,0 @@
package codec
type Codec[T, U any] interface {
Encode(T) (U, error)
Decode(U) (T, error)
}
type Marshaler[T any] = Codec[T, string]

82
pkg/convert/debruijn_to_lambda.go Normal file
View File

@@ -0,0 +1,82 @@
package convert
import (
"fmt"
"git.maximhutz.com/max/lambda/pkg/debruijn"
"git.maximhutz.com/max/lambda/pkg/lambda"
"git.maximhutz.com/max/lambda/pkg/set"
)
// DeBruijnToLambda converts a De Bruijn indexed expression back to named lambda calculus.
func DeBruijnToLambda(expr debruijn.Expression) lambda.Expression {
return deBruijnToLambdaWithContext(expr, []string{})
}
func deBruijnToLambdaWithContext(expr debruijn.Expression, context []string) lambda.Expression {
switch e := expr.(type) {
case *debruijn.Variable:
index := e.Index()
if index < len(context) {
// Bound variable: look up name in context.
name := context[len(context)-1-index]
return lambda.NewVariable(name)
}
// Free variable: use the label if available.
if e.Label() != "" {
return lambda.NewVariable(e.Label())
}
// Generate a name for free variables without labels.
return lambda.NewVariable(fmt.Sprintf("free%d", index))
case *debruijn.Abstraction:
// Generate a fresh parameter name.
used := collectUsedNames(e.Body(), context)
paramName := generateFreshName(used)
newContext := append(context, paramName)
body := deBruijnToLambdaWithContext(e.Body(), newContext)
return lambda.NewAbstraction(paramName, body)
case *debruijn.Application:
abs := deBruijnToLambdaWithContext(e.Abstraction(), context)
arg := deBruijnToLambdaWithContext(e.Argument(), context)
return lambda.NewApplication(abs, arg)
default:
panic("unknown expression type")
}
}
// collectUsedNames gathers all variable labels used in an expression.
func collectUsedNames(expr debruijn.Expression, context []string) *set.Set[string] {
used := set.New[string]()
for _, name := range context {
used.Add(name)
}
collectUsedNamesHelper(expr, used)
return used
}
func collectUsedNamesHelper(expr debruijn.Expression, used *set.Set[string]) {
switch e := expr.(type) {
case *debruijn.Variable:
if e.Label() != "" {
used.Add(e.Label())
}
case *debruijn.Abstraction:
collectUsedNamesHelper(e.Body(), used)
case *debruijn.Application:
collectUsedNamesHelper(e.Abstraction(), used)
collectUsedNamesHelper(e.Argument(), used)
}
}
// generateFreshName creates a fresh variable name not in the used set.
func generateFreshName(used *set.Set[string]) string {
for i := 0; ; i++ {
name := fmt.Sprintf("_%d", i)
if !used.Has(name) {
return name
}
}
}

44
pkg/convert/lambda_to_debruijn.go Normal file
View File

@@ -0,0 +1,44 @@
package convert
import (
"git.maximhutz.com/max/lambda/pkg/debruijn"
"git.maximhutz.com/max/lambda/pkg/lambda"
)
// LambdaToDeBruijn converts a lambda calculus expression to De Bruijn indexed form.
// The context parameter tracks bound variables from outer abstractions.
func LambdaToDeBruijn(expr lambda.Expression) debruijn.Expression {
return lambdaToDeBruijnWithContext(expr, []string{})
}
func lambdaToDeBruijnWithContext(expr lambda.Expression, context []string) debruijn.Expression {
switch e := expr.(type) {
case *lambda.Variable:
name := e.Value()
// Search for the variable in the context (innermost to outermost).
for i := len(context) - 1; i >= 0; i-- {
if context[i] == name {
index := len(context) - 1 - i
return debruijn.NewVariable(index, name)
}
}
// Free variable: use a negative index to mark it.
// We encode free variables with index = len(context) + position.
// For simplicity, we use a large index that won't conflict.
return debruijn.NewVariable(len(context), name)
case *lambda.Abstraction:
// Add the parameter to the context.
newContext := append(context, e.Parameter())
body := lambdaToDeBruijnWithContext(e.Body(), newContext)
return debruijn.NewAbstraction(body)
case *lambda.Application:
abs := lambdaToDeBruijnWithContext(e.Abstraction(), context)
arg := lambdaToDeBruijnWithContext(e.Argument(), context)
return debruijn.NewApplication(abs, arg)
default:
panic("unknown expression type")
}
}

72
pkg/convert/saccharine_to_lambda.go
View File

@@ -3,24 +3,23 @@ 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 {
func convertAtom(n *saccharine.Atom) lambda.Expression {
return lambda.NewVariable(n.Name)
}
func encodeAbstraction(n *saccharine.Abstraction) lambda.Expression {
result := encodeExpression(n.Body)
func convertAbstraction(n *saccharine.Abstraction) lambda.Expression {
result := SaccharineToLambda(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.GetFreeVariables(result)
freshName := lambda.GenerateFreshName(freeVars)
parameters = append(parameters, freshName)
}
@@ -32,13 +31,13 @@ func encodeAbstraction(n *saccharine.Abstraction) lambda.Expression {
return result
}
func encodeApplication(n *saccharine.Application) lambda.Expression {
result := encodeExpression(n.Abstraction)
func convertApplication(n *saccharine.Application) lambda.Expression {
result := SaccharineToLambda(n.Abstraction)
arguments := []lambda.Expression{}
for _, argument := range n.Arguments {
encodeedArgument := encodeExpression(argument)
arguments = append(arguments, encodeedArgument)
convertedArgument := SaccharineToLambda(argument)
arguments = append(arguments, convertedArgument)
}
for _, argument := range arguments {
@@ -52,9 +51,9 @@ func reduceLet(s *saccharine.LetStatement, e lambda.Expression) lambda.Expressio
var value lambda.Expression
if len(s.Parameters) == 0 {
value = encodeExpression(s.Body)
value = SaccharineToLambda(s.Body)
} else {
value = encodeAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
value = convertAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
}
return lambda.NewApplication(
@@ -64,11 +63,11 @@ func reduceLet(s *saccharine.LetStatement, e lambda.Expression) lambda.Expressio
}
func reduceDeclare(s *saccharine.DeclareStatement, e lambda.Expression) lambda.Expression {
freshVar := lambda.GenerateFreshName(e.GetFree())
freshVar := lambda.GenerateFreshName(lambda.GetFreeVariables(e))
return lambda.NewApplication(
lambda.NewAbstraction(freshVar, e),
encodeExpression(s.Value),
SaccharineToLambda(s.Value),
)
}
@@ -83,8 +82,8 @@ func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Express
}
}
func encodeClause(n *saccharine.Clause) lambda.Expression {
result := encodeExpression(n.Returns)
func convertClause(n *saccharine.Clause) lambda.Expression {
result := SaccharineToLambda(n.Returns)
for i := len(n.Statements) - 1; i >= 0; i-- {
result = reduceStatement(n.Statements[i], result)
@@ -93,46 +92,17 @@ func encodeClause(n *saccharine.Clause) lambda.Expression {
return result
}
func encodeExpression(s saccharine.Expression) lambda.Expression {
switch s := s.(type) {
func SaccharineToLambda(n saccharine.Expression) lambda.Expression {
switch n := n.(type) {
case *saccharine.Atom:
return encodeAtom(s)
return convertAtom(n)
case *saccharine.Abstraction:
return encodeAbstraction(s)
return convertAbstraction(n)
case *saccharine.Application:
return encodeApplication(s)
return convertApplication(n)
case *saccharine.Clause:
return encodeClause(s)
return convertClause(n)
default:
panic(fmt.Errorf("unknown expression type: %T", s))
panic(fmt.Errorf("unknown expression type: %T", n))
}
}
func decodeExression(l lambda.Expression) saccharine.Expression {
switch l := l.(type) {
case lambda.Variable:
return saccharine.NewAtom(l.Name())
case lambda.Abstraction:
return saccharine.NewAbstraction(
[]string{l.Parameter()},
decodeExression(l.Body()))
case lambda.Application:
return saccharine.NewApplication(
decodeExression(l.Abstraction()),
[]saccharine.Expression{decodeExression(l.Argument())})
default:
panic(fmt.Errorf("unknown expression type: %T", l))
}
}
type Saccharine2Lambda struct{}
func (c Saccharine2Lambda) Decode(l lambda.Expression) (saccharine.Expression, error) {
return decodeExression(l), nil
}
func (c Saccharine2Lambda) Encode(s saccharine.Expression) (lambda.Expression, error) {
return encodeExpression(s), nil
}
var _ codec.Codec[saccharine.Expression, lambda.Expression] = (*Saccharine2Lambda)(nil)

119
pkg/debruijn/expression.go Normal file
View File

@@ -0,0 +1,119 @@
// Package debruijn provides De Bruijn indexed lambda calculus expressions.
// De Bruijn indices eliminate the need for variable names by using numeric
// indices to refer to bound variables, avoiding capture issues during substitution.
package debruijn
import "git.maximhutz.com/max/lambda/pkg/expr"
// Expression is the interface for all De Bruijn indexed expression types.
// It embeds the general expr.Expression interface for cross-mode compatibility.
type Expression interface {
expr.Expression
Accept(Visitor)
}
/** ------------------------------------------------------------------------- */
// Abstraction represents a lambda abstraction without a named parameter.
// In De Bruijn notation, the parameter is implicit and referenced by index 0
// within the body.
type Abstraction struct {
body Expression
}
// Body returns the body of the abstraction.
func (a *Abstraction) Body() Expression {
return a.body
}
// Accept implements the Visitor pattern.
func (a *Abstraction) Accept(v Visitor) {
v.VisitAbstraction(a)
}
// String returns the De Bruijn notation string representation.
func (a *Abstraction) String() string {
return Stringify(a)
}
// NewAbstraction creates a new De Bruijn abstraction with the given body.
func NewAbstraction(body Expression) *Abstraction {
return &Abstraction{body: body}
}
/** ------------------------------------------------------------------------- */
// Application represents the application of one expression to another.
type Application struct {
abstraction Expression
argument Expression
}
// Abstraction returns the function expression being applied.
func (a *Application) Abstraction() Expression {
return a.abstraction
}
// Argument returns the argument expression.
func (a *Application) Argument() Expression {
return a.argument
}
// Accept implements the Visitor pattern.
func (a *Application) Accept(v Visitor) {
v.VisitApplication(a)
}
// String returns the De Bruijn notation string representation.
func (a *Application) String() string {
return Stringify(a)
}
// NewApplication creates a new application expression.
func NewApplication(abstraction Expression, argument Expression) *Application {
return &Application{abstraction: abstraction, argument: argument}
}
/** ------------------------------------------------------------------------- */
// Variable represents a De Bruijn indexed variable.
// The index indicates how many binders to skip to find the binding abstraction.
// The label is an optional hint for display purposes.
type Variable struct {
index int
label string
}
// Index returns the De Bruijn index.
func (v *Variable) Index() int {
return v.index
}
// Label returns the optional variable label.
func (v *Variable) Label() string {
return v.label
}
// Accept implements the Visitor pattern.
func (v *Variable) Accept(visitor Visitor) {
visitor.VisitVariable(v)
}
// String returns the De Bruijn notation string representation.
func (v *Variable) String() string {
return Stringify(v)
}
// NewVariable creates a new De Bruijn variable with the given index and label.
func NewVariable(index int, label string) *Variable {
return &Variable{index: index, label: label}
}
/** ------------------------------------------------------------------------- */
// Visitor interface for traversing De Bruijn expressions.
type Visitor interface {
VisitAbstraction(*Abstraction)
VisitApplication(*Application)
VisitVariable(*Variable)
}

76
pkg/debruijn/iterator.go Normal file
View File

@@ -0,0 +1,76 @@
package debruijn
// Iterator provides depth-first traversal of De Bruijn expressions.
type Iterator struct {
trace []*Expression
}
// NewIterator creates a new iterator starting at the given expression.
func NewIterator(expr *Expression) *Iterator {
return &Iterator{[]*Expression{expr}}
}
// Done returns true when the iterator has finished traversal.
func (i *Iterator) Done() bool {
return len(i.trace) == 0
}
// Current returns a pointer to the current expression.
func (i *Iterator) Current() *Expression {
if i.Done() {
return nil
}
return i.trace[len(i.trace)-1]
}
// Parent returns a pointer to the parent expression.
func (i *Iterator) Parent() *Expression {
if len(i.trace) < 2 {
return nil
}
return i.trace[len(i.trace)-2]
}
// Swap replaces the current expression with the given expression.
func (i *Iterator) Swap(with Expression) {
current := i.Current()
if current != nil {
*current = with
}
}
// Back moves the iterator back to the parent expression.
func (i *Iterator) Back() bool {
if i.Done() {
return false
}
i.trace = i.trace[:len(i.trace)-1]
return true
}
// Next advances the iterator to the next expression in leftmost-outermost order.
func (i *Iterator) Next() {
switch typed := (*i.Current()).(type) {
case *Abstraction:
i.trace = append(i.trace, &typed.body)
case *Application:
i.trace = append(i.trace, &typed.abstraction)
case *Variable:
for len(i.trace) > 1 {
if app, ok := (*i.Parent()).(*Application); ok {
if app.abstraction == *i.Current() {
i.Back()
i.trace = append(i.trace, &app.argument)
return
}
}
i.Back()
}
i.trace = []*Expression{}
}
}

72
pkg/debruijn/reducer.go Normal file
View File

@@ -0,0 +1,72 @@
package debruijn
import (
"git.maximhutz.com/max/lambda/pkg/emitter"
"git.maximhutz.com/max/lambda/pkg/expr"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
// NormalOrderReducer implements normal order (leftmost-outermost) reduction
// for De Bruijn indexed lambda calculus expressions.
type NormalOrderReducer struct {
emitter.BaseEmitter[reducer.Event]
expression *Expression
}
// NewNormalOrderReducer creates a new normal order reducer.
func NewNormalOrderReducer(expression *Expression) *NormalOrderReducer {
return &NormalOrderReducer{
BaseEmitter: *emitter.New[reducer.Event](),
expression: expression,
}
}
// Expression returns the current expression state.
func (r *NormalOrderReducer) Expression() expr.Expression {
return *r.expression
}
// isViable checks if an expression is a redex (reducible expression).
// A redex is an application of an abstraction to an argument.
func isViable(e *Expression) (*Abstraction, Expression, bool) {
if e == nil {
return nil, nil, false
} else if app, appOk := (*e).(*Application); !appOk {
return nil, nil, false
} else if fn, fnOk := app.abstraction.(*Abstraction); !fnOk {
return nil, nil, false
} else {
return fn, app.argument, true
}
}
// betaReduce performs a single beta reduction step.
// Given (\. body) arg, it substitutes arg for index 0 in body,
// then shifts the result down to account for the removed abstraction.
func betaReduce(fn *Abstraction, arg Expression) Expression {
// Substitute arg for variable 0 in the body.
substituted := Substitute(fn.body, 0, Shift(arg, 1, 0))
// Shift down to account for the removed abstraction.
return Shift(substituted, -1, 0)
}
// Reduce performs normal order reduction on a De Bruijn expression.
func (r *NormalOrderReducer) Reduce() {
r.Emit(reducer.StartEvent)
it := NewIterator(r.expression)
for !it.Done() {
if fn, arg, ok := isViable(it.Current()); !ok {
it.Next()
} else {
it.Swap(betaReduce(fn, arg))
r.Emit(reducer.StepEvent)
if _, _, ok := isViable(it.Parent()); ok {
it.Back()
}
}
}
r.Emit(reducer.StopEvent)
}

32
pkg/debruijn/shift.go Normal file
View File

@@ -0,0 +1,32 @@
package debruijn
// Shift increments all free variable indices in an expression by the given amount.
// A variable is free if its index is >= the cutoff (depth of nested abstractions).
// This is necessary when substituting an expression into a different binding context.
func Shift(expr Expression, amount int, cutoff int) Expression {
switch e := expr.(type) {
case *Variable:
if e.index >= cutoff {
return NewVariable(e.index+amount, e.label)
}
return e
case *Abstraction:
newBody := Shift(e.body, amount, cutoff+1)
if newBody == e.body {
return e
}
return NewAbstraction(newBody)
case *Application:
newAbs := Shift(e.abstraction, amount, cutoff)
newArg := Shift(e.argument, amount, cutoff)
if newAbs == e.abstraction && newArg == e.argument {
return e
}
return NewApplication(newAbs, newArg)
default:
return expr
}
}

35
pkg/debruijn/stringify.go Normal file
View File

@@ -0,0 +1,35 @@
package debruijn
import (
"strconv"
"strings"
)
type stringifyVisitor struct {
builder strings.Builder
}
func (v *stringifyVisitor) VisitVariable(a *Variable) {
v.builder.WriteString(strconv.Itoa(a.index))
}
func (v *stringifyVisitor) VisitAbstraction(f *Abstraction) {
v.builder.WriteRune('\\')
v.builder.WriteRune('.')
f.body.Accept(v)
}
func (v *stringifyVisitor) VisitApplication(c *Application) {
v.builder.WriteRune('(')
c.abstraction.Accept(v)
v.builder.WriteRune(' ')
c.argument.Accept(v)
v.builder.WriteRune(')')
}
// Stringify converts a De Bruijn expression to its string representation.
func Stringify(e Expression) string {
b := &stringifyVisitor{builder: strings.Builder{}}
e.Accept(b)
return b.builder.String()
}

34
pkg/debruijn/substitute.go Normal file
View File

@@ -0,0 +1,34 @@
package debruijn
// Substitute replaces the variable at the given index with the replacement expression.
// The replacement is shifted appropriately as we descend into nested abstractions.
func Substitute(expr Expression, index int, replacement Expression) Expression {
switch e := expr.(type) {
case *Variable:
if e.index == index {
return replacement
}
return e
case *Abstraction:
// When entering an abstraction, increment the target index and shift the
// replacement to account for the new binding context.
shiftedReplacement := Shift(replacement, 1, 0)
newBody := Substitute(e.body, index+1, shiftedReplacement)
if newBody == e.body {
return e
}
return NewAbstraction(newBody)
case *Application:
newAbs := Substitute(e.abstraction, index, replacement)
newArg := Substitute(e.argument, index, replacement)
if newAbs == e.abstraction && newArg == e.argument {
return e
}
return NewApplication(newAbs, newArg)
default:
return expr
}
}

6
pkg/deltanet/deltanet.go Normal file
View File

@@ -0,0 +1,6 @@
// Package "deltanet" is a reduction strategy using ∆-nets.
package deltanet
type Graph struct {
Nodes []Node
}

94
pkg/deltanet/node.go Normal file
View File

@@ -0,0 +1,94 @@
package deltanet
/** ------------------------------------------------------------------------- */
// A connection between exactly two nodes in a graph.
type Edge struct {
A, B Node
}
// Returns all nodes the edge is connected to.
func (e Edge) GetConnections() []Node { return []Node{e.A, e.B} }
// Determines if a node is connected via this edge.
func (e Edge) IsConnected(n Node) bool { return e.A == n || e.B == n }
// Swaps an edges connected with one node, for another.
func (e *Edge) Swap(from Node, to Node) {
if e.A == from {
e.A = to
}
if e.B == from {
e.B = to
}
}
// Returns true if the edge is connected to each node via their pricniple ports.
func (e Edge) IsPrincipleEdge() bool {
return e.A.GetMainPort() == e && e.B.GetMainPort() == e
}
/** ------------------------------------------------------------------------- */
type Node interface {
// Returns the principle port that the node is attached to.
GetMainPort() Edge
// Returns all auxiliary ports that the node has. These ports are guaranteed
// to be ordered clockwise, as they would appear graphically.
GetAuxPorts() []Edge
// Returns the label of the node. May be blank.
GetLabel() string
}
/** ------------------------------------------------------------------------- */
type EraserNode struct {
Main Edge
}
func (n EraserNode) GetLabel() string { return "Ⓧ" }
func (n EraserNode) GetMainPort() Edge { return n.Main }
func (n EraserNode) GetAuxPorts() []Edge { return []Edge{} }
/** ------------------------------------------------------------------------- */
type ReplicatorNode struct {
Main Edge
Level uint
Aux []Edge
Deltas []int
}
func (n ReplicatorNode) GetLabel() string { return "" }
func (n ReplicatorNode) GetMainPort() Edge { return n.Main }
func (n ReplicatorNode) GetAuxPorts() []Edge { return n.Aux }
// Returns the level of the replicator node.
func (n ReplicatorNode) GetLevel() uint { return n.Level }
/** ------------------------------------------------------------------------- */
type FanNode struct {
Label string
Main Edge
Left, Right Edge
}
func (n FanNode) GetLabel() string { return n.Label }
func (n FanNode) GetMainPort() Edge { return n.Main }
func (n FanNode) GetAuxPorts() []Edge { return []Edge{n.Left, n.Right} }
/** ------------------------------------------------------------------------- */
type TerminalNode struct {
Label string
Main Edge
}
func (n TerminalNode) GetLabel() string { return n.Label }
func (n TerminalNode) GetMainPort() Edge { return n.Main }
func (n TerminalNode) GetAuxPorts() []Edge { return []Edge{} }
/** ------------------------------------------------------------------------- */

4
pkg/emitter/emitter.go
View File

@@ -9,7 +9,7 @@ type Emitter[E comparable] interface {
}
type BaseEmitter[E comparable] struct {
listeners map[E]set.Set[Listener[E]]
listeners map[E]*set.Set[Listener[E]]
}
func (e *BaseEmitter[E]) On(kind E, fn func()) Listener[E] {
@@ -41,6 +41,6 @@ func (e *BaseEmitter[E]) Emit(event E) {
func New[E comparable]() *BaseEmitter[E] {
return &BaseEmitter[E]{
listeners: map[E]set.Set[Listener[E]]{},
listeners: map[E]*set.Set[Listener[E]]{},
}
}

7
pkg/engine/engine.go
View File

@@ -1,7 +0,0 @@
package engine
type Engine[T any] interface {
Get() (T, error)
Set(T) error
Step(int) bool
}

34
pkg/engine/normalorder/engine.go
View File

@@ -1,34 +0,0 @@
package normalorder
import (
"git.maximhutz.com/max/lambda/pkg/engine"
"git.maximhutz.com/max/lambda/pkg/lambda"
)
type Engine struct {
expr lambda.Expression
}
func (e Engine) Get() (lambda.Expression, error) {
return e.expr, nil
}
func (e Engine) Set(l lambda.Expression) error {
e.expr = l
return nil
}
func (e Engine) Step(i int) bool {
var reduced bool
for range i {
e.expr, reduced = ReduceOnce(e.expr)
if !reduced {
return false
}
}
return true
}
var _ engine.Engine[lambda.Expression] = (*Engine)(nil)

34
pkg/engine/normalorder/reduce_one.go
View File

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

11
pkg/expr/expr.go Normal file
View File

@@ -0,0 +1,11 @@
// Package expr provides the abstract Expression interface for all evaluatable
// expression types in the lambda interpreter.
package expr
// Expression is the base interface for all evaluatable expression types.
// Different evaluation modes (lambda calculus, SKI combinators, typed lambda
// calculus, etc.) implement this interface with their own concrete types.
type Expression interface {
// String returns a human-readable representation of the expression.
String() string
}

90
pkg/lambda/expression.go
View File

@@ -1,32 +1,12 @@
package lambda
import (
"fmt"
"git.maximhutz.com/max/lambda/pkg/set"
)
import "git.maximhutz.com/max/lambda/pkg/expr"
// 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
expr.Expression
Accept(Visitor)
}
/** ------------------------------------------------------------------------- */
@@ -36,22 +16,24 @@ type Abstraction struct {
body Expression
}
var _ Expression = Abstraction{}
func (a Abstraction) Parameter() string {
func (a *Abstraction) Parameter() string {
return a.parameter
}
func (a Abstraction) Body() Expression {
func (a *Abstraction) Body() Expression {
return a.body
}
func (a Abstraction) String() string {
return "\\" + a.parameter + "." + a.body.String()
func (a *Abstraction) Accept(v Visitor) {
v.VisitAbstraction(a)
}
func NewAbstraction(parameter string, body Expression) Abstraction {
return Abstraction{parameter, body}
func (a *Abstraction) String() string {
return Stringify(a)
}
func NewAbstraction(parameter string, body Expression) *Abstraction {
return &Abstraction{parameter: parameter, body: body}
}
/** ------------------------------------------------------------------------- */
@@ -61,40 +43,52 @@ type Application struct {
argument Expression
}
var _ Expression = Application{}
func (a Application) Abstraction() Expression {
func (a *Application) Abstraction() Expression {
return a.abstraction
}
func (a Application) Argument() Expression {
func (a *Application) Argument() Expression {
return a.argument
}
func (a Application) String() string {
return "(" + a.abstraction.String() + " " + a.argument.String() + ")"
func (a *Application) Accept(v Visitor) {
v.VisitApplication(a)
}
func NewApplication(abstraction Expression, argument Expression) Application {
return Application{abstraction, argument}
func (a *Application) String() string {
return Stringify(a)
}
func NewApplication(abstraction Expression, argument Expression) *Application {
return &Application{abstraction: abstraction, argument: argument}
}
/** ------------------------------------------------------------------------- */
type Variable struct {
name string
value string
}
var _ Expression = Variable{}
func (v Variable) Name() string {
return v.name
func (v *Variable) Value() string {
return v.value
}
func (v Variable) String() string {
return v.name
func (v *Variable) Accept(visitor Visitor) {
visitor.VisitVariable(v)
}
func NewVariable(name string) Variable {
return Variable{name}
func (v *Variable) String() string {
return Stringify(v)
}
func NewVariable(name string) *Variable {
return &Variable{value: name}
}
/** ------------------------------------------------------------------------- */
type Visitor interface {
VisitAbstraction(*Abstraction)
VisitApplication(*Application)
VisitVariable(*Variable)
}

4
pkg/lambda/generate_name.go
View File

@@ -6,9 +6,7 @@ import (
"git.maximhutz.com/max/lambda/pkg/set"
)
// GenerateFreshName generates a variable name that is not in the used set.
// This function does not mutate the used set.
func GenerateFreshName(used set.Set[string]) string {
func GenerateFreshName(used *set.Set[string]) string {
for i := uint64(0); ; i++ {
attempt := "_" + string(strconv.AppendUint(nil, i, 10))

25
pkg/lambda/get_free_variables.go
View File

@@ -2,18 +2,19 @@ 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())
func GetFreeVariables(e Expression) *set.Set[string] {
switch e := e.(type) {
case *Variable:
return set.New(e.value)
case *Abstraction:
vars := GetFreeVariables(e.body)
vars.Remove(e.parameter)
return vars
}
func (e Application) GetFree() set.Set[string] {
vars := e.Abstraction().GetFree()
vars.Merge(e.Argument().GetFree())
case *Application:
vars := GetFreeVariables(e.abstraction)
vars.Merge(GetFreeVariables(e.argument))
return vars
default:
return nil
}
}

20
pkg/lambda/is_free_variable.go
View File

@@ -1,12 +1,14 @@
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)
func IsFreeVariable(n string, e Expression) bool {
switch e := e.(type) {
case *Variable:
return e.value == n
case *Abstraction:
return e.parameter != n && IsFreeVariable(n, e.body)
case *Application:
return IsFreeVariable(n, e.abstraction) || IsFreeVariable(n, e.argument)
default:
return false
}
}

68
pkg/lambda/iterator.go Normal file
View File

@@ -0,0 +1,68 @@
package lambda
type Iterator struct {
trace []*Expression
}
func NewIterator(expr *Expression) *Iterator {
return &Iterator{[]*Expression{expr}}
}
func (i *Iterator) Done() bool {
return len(i.trace) == 0
}
func (i *Iterator) Current() *Expression {
if i.Done() {
return nil
}
return i.trace[len(i.trace)-1]
}
func (i *Iterator) Parent() *Expression {
if len(i.trace) < 2 {
return nil
}
return i.trace[len(i.trace)-2]
}
func (i *Iterator) Swap(with Expression) {
current := i.Current()
if current != nil {
*current = with
}
}
func (i *Iterator) Back() bool {
if i.Done() {
return false
}
i.trace = i.trace[:len(i.trace)-1]
return true
}
func (i *Iterator) Next() {
switch typed := (*i.Current()).(type) {
case *Abstraction:
i.trace = append(i.trace, &typed.body)
case *Application:
i.trace = append(i.trace, &typed.abstraction)
case *Variable:
for len(i.trace) > 1 {
if app, ok := (*i.Parent()).(*Application); ok {
if app.abstraction == *i.Current() {
i.Back()
i.trace = append(i.trace, &app.argument)
return
}
}
i.Back()
}
i.trace = []*Expression{}
}
}

19
pkg/lambda/marshaler.go
View File

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

61
pkg/lambda/reducer.go Normal file
View File

@@ -0,0 +1,61 @@
package lambda
import (
"git.maximhutz.com/max/lambda/pkg/emitter"
"git.maximhutz.com/max/lambda/pkg/expr"
"git.maximhutz.com/max/lambda/pkg/reducer"
)
// NormalOrderReducer implements normal order (leftmost-outermost) reduction
// for lambda calculus expressions.
type NormalOrderReducer struct {
emitter.BaseEmitter[reducer.Event]
expression *Expression
}
// NewNormalOrderReducer creates a new normal order reducer.
func NewNormalOrderReducer(expression *Expression) *NormalOrderReducer {
return &NormalOrderReducer{
BaseEmitter: *emitter.New[reducer.Event](),
expression: expression,
}
}
// Expression returns the current expression state.
func (r *NormalOrderReducer) Expression() expr.Expression {
return *r.expression
}
func isViable(e *Expression) (*Abstraction, Expression, bool) {
if e == nil {
return nil, nil, false
} else if app, appOk := (*e).(*Application); !appOk {
return nil, nil, false
} else if fn, fnOk := app.abstraction.(*Abstraction); !fnOk {
return nil, nil, false
} else {
return fn, app.argument, true
}
}
// Reduce performs normal order reduction on a lambda expression.
// The expression must be a lambda.Expression; other types are returned unchanged.
func (r *NormalOrderReducer) Reduce() {
r.Emit(reducer.StartEvent)
it := NewIterator(r.expression)
for !it.Done() {
if fn, arg, ok := isViable(it.Current()); !ok {
it.Next()
} else {
it.Swap(Substitute(fn.body, fn.parameter, arg))
r.Emit(reducer.StepEvent)
if _, _, ok := isViable(it.Parent()); ok {
it.Back()
}
}
}
r.Emit(reducer.StopEvent)
}

36
pkg/lambda/rename.go
View File

@@ -1,28 +1,38 @@
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 {
func Rename(expr Expression, target string, newName string) Expression {
switch e := expr.(type) {
case *Variable:
if e.value == target {
return NewVariable(newName)
}
return e
}
func (e Abstraction) Rename(target string, newName string) Expression {
newParam := e.Parameter()
if e.Parameter() == target {
case *Abstraction:
newParam := e.parameter
if e.parameter == target {
newParam = newName
}
newBody := e.Body().Rename(target, newName)
newBody := Rename(e.body, target, newName)
if newParam == e.parameter && newBody == e.body {
return e
}
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)
case *Application:
newAbs := Rename(e.abstraction, target, newName)
newArg := Rename(e.argument, target, newName)
if newAbs == e.abstraction && newArg == e.argument {
return e
}
return NewApplication(newAbs, newArg)
default:
return expr
}
}

32
pkg/lambda/stringify.go Normal file
View File

@@ -0,0 +1,32 @@
package lambda
import "strings"
type stringifyVisitor struct {
builder strings.Builder
}
func (v *stringifyVisitor) VisitVariable(a *Variable) {
v.builder.WriteString(a.value)
}
func (v *stringifyVisitor) VisitAbstraction(f *Abstraction) {
v.builder.WriteRune('\\')
v.builder.WriteString(f.parameter)
v.builder.WriteRune('.')
f.body.Accept(v)
}
func (v *stringifyVisitor) VisitApplication(c *Application) {
v.builder.WriteRune('(')
c.abstraction.Accept(v)
v.builder.WriteRune(' ')
c.argument.Accept(v)
v.builder.WriteRune(')')
}
func Stringify(e Expression) string {
b := &stringifyVisitor{builder: strings.Builder{}}
e.Accept(b)
return b.builder.String()
}

47
pkg/lambda/substitute.go
View File

@@ -1,35 +1,46 @@
package lambda
func (e Variable) Substitute(target string, replacement Expression) Expression {
if e.Name() == target {
func Substitute(expr Expression, target string, replacement Expression) Expression {
switch e := expr.(type) {
case *Variable:
if e.value == target {
return replacement
}
return e
}
func (e Abstraction) Substitute(target string, replacement Expression) Expression {
if e.Parameter() == target {
case *Abstraction:
if e.parameter == target {
return e
}
body := e.Body()
param := e.Parameter()
if replacement.IsFree(param) {
freeVars := replacement.GetFree()
freeVars.Merge(body.GetFree())
body := e.body
param := e.parameter
if IsFreeVariable(param, replacement) {
freeVars := GetFreeVariables(replacement)
freeVars.Merge(GetFreeVariables(body))
freshVar := GenerateFreshName(freeVars)
body = body.Rename(param, freshVar)
body = Rename(body, param, freshVar)
param = freshVar
}
newBody := body.Substitute(target, replacement)
newBody := Substitute(body, target, replacement)
if newBody == body && param == e.parameter {
return e
}
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)
case *Application:
newAbs := Substitute(e.abstraction, target, replacement)
newArg := Substitute(e.argument, target, replacement)
return NewApplication(abs, arg)
if newAbs == e.abstraction && newArg == e.argument {
return e
}
return NewApplication(newAbs, newArg)
default:
return expr
}
}

13
pkg/reducer/events.go Normal file
View File

@@ -0,0 +1,13 @@
package reducer
// Event represents lifecycle events during reduction.
type Event int
const (
// StartEvent is emitted before reduction begins.
StartEvent Event = iota
// StepEvent is emitted after each reduction step.
StepEvent
// StopEvent is emitted after reduction completes.
StopEvent
)

27
pkg/reducer/reducer.go Normal file
View File

@@ -0,0 +1,27 @@
// Package reducer provides the abstract Reducer interface for all expression
// reduction strategies.
package reducer
import (
"git.maximhutz.com/max/lambda/pkg/emitter"
"git.maximhutz.com/max/lambda/pkg/expr"
)
// Reducer defines the interface for expression reduction strategies.
// Different evaluation modes (normal order, applicative order, SKI combinators,
// etc.) implement this interface with their own reduction logic.
//
// Reducers also implement the Emitter interface to allow plugins to observe
// reduction lifecycle events (Start, Step, Stop).
type Reducer interface {
emitter.Emitter[Event]
// Reduce performs all reduction steps on the expression.
// Emits StartEvent before reduction, StepEvent after each step, and
// StopEvent after completion.
// Returns the final reduced expression.
Reduce()
// Expression returns the current expression state.
Expression() expr.Expression
}

24
pkg/saccharine/marshaler.go
View File

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

49
pkg/saccharine/parse.go
View File

@@ -5,17 +5,18 @@ import (
"fmt"
"git.maximhutz.com/max/lambda/pkg/iterator"
"git.maximhutz.com/max/lambda/pkg/saccharine/token"
"git.maximhutz.com/max/lambda/pkg/trace"
)
type TokenIterator = iterator.Iterator[Token]
type TokenIterator = iterator.Iterator[token.Token]
func parseRawToken(i *TokenIterator, expected TokenType) (*Token, error) {
return iterator.Do(i, func(i *TokenIterator) (*Token, error) {
func parseRawToken(i *TokenIterator, expected token.Type) (*token.Token, error) {
return iterator.Do(i, func(i *TokenIterator) (*token.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)
return nil, fmt.Errorf("expected token %v, got %v'", token.Name(expected), tok.Value)
} else {
return &tok, nil
}
@@ -24,14 +25,14 @@ func parseRawToken(i *TokenIterator, expected TokenType) (*Token, error) {
func passSoftBreaks(i *TokenIterator) {
for {
if _, err := parseRawToken(i, TokenSoftBreak); err != nil {
if _, err := parseRawToken(i, token.SoftBreak); err != nil {
return
}
}
}
func parseToken(i *TokenIterator, expected TokenType, ignoreSoftBreaks bool) (*Token, error) {
return iterator.Do(i, func(i *TokenIterator) (*Token, error) {
func parseToken(i *TokenIterator, expected token.Type, ignoreSoftBreaks bool) (*token.Token, error) {
return iterator.Do(i, func(i *TokenIterator) (*token.Token, error) {
if ignoreSoftBreaks {
passSoftBreaks(i)
}
@@ -41,17 +42,17 @@ func parseToken(i *TokenIterator, expected TokenType, ignoreSoftBreaks bool) (*T
}
func parseString(i *TokenIterator) (string, error) {
if tok, err := parseToken(i, TokenAtom, true); err != nil {
if tok, err := parseToken(i, token.Atom, 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 {
func parseBreak(i *TokenIterator) (*token.Token, error) {
if tok, softErr := parseRawToken(i, token.SoftBreak); softErr == nil {
return tok, nil
} else if tok, hardErr := parseRawToken(i, TokenHardBreak); hardErr == nil {
} else if tok, hardErr := parseRawToken(i, token.HardBreak); hardErr == nil {
return tok, nil
} else {
return nil, errors.Join(softErr, hardErr)
@@ -75,11 +76,11 @@ func parseList[U any](i *TokenIterator, fn func(*TokenIterator) (U, error), mini
func parseAbstraction(i *TokenIterator) (*Abstraction, error) {
return iterator.Do(i, func(i *TokenIterator) (*Abstraction, error) {
if _, err := parseToken(i, TokenSlash, true); err != nil {
if _, err := parseToken(i, token.Slash, 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 {
} else if _, err = parseToken(i, token.Dot, 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
@@ -91,11 +92,11 @@ func parseAbstraction(i *TokenIterator) (*Abstraction, error) {
func parseApplication(i *TokenIterator) (*Application, error) {
return iterator.Do(i, func(i *TokenIterator) (*Application, error) {
if _, err := parseToken(i, TokenOpenParen, true); err != nil {
if _, err := parseToken(i, token.OpenParen, 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 {
} else if _, err := parseToken(i, token.CloseParen, true); err != nil {
return nil, trace.Wrap(err, "no closing brackets (col %d)", i.MustGet().Column)
} else {
return NewApplication(expressions[0], expressions[1:]), nil
@@ -104,7 +105,7 @@ func parseApplication(i *TokenIterator) (*Application, error) {
}
func parseAtom(i *TokenIterator) (*Atom, error) {
if tok, err := parseToken(i, TokenAtom, true); err != nil {
if tok, err := parseToken(i, token.Atom, true); err != nil {
return nil, trace.Wrap(err, "no variable (col %d)", i.Index())
} else {
return NewAtom(tok.Value), nil
@@ -132,7 +133,7 @@ func parseStatements(i *TokenIterator) ([]Statement, error) {
func parseClause(i *TokenIterator, braces bool) (*Clause, error) {
if braces {
if _, err := parseToken(i, TokenOpenBrace, true); err != nil {
if _, err := parseToken(i, token.OpenBrace, true); err != nil {
return nil, err
}
}
@@ -151,7 +152,7 @@ func parseClause(i *TokenIterator, braces bool) (*Clause, error) {
}
if braces {
if _, err := parseToken(i, TokenCloseBrace, true); err != nil {
if _, err := parseToken(i, token.CloseBrace, true); err != nil {
return nil, err
}
}
@@ -164,13 +165,13 @@ func parseExpression(i *TokenIterator) (Expression, error) {
passSoftBreaks(i)
switch peek := i.MustGet(); peek.Type {
case TokenOpenParen:
case token.OpenParen:
return parseApplication(i)
case TokenSlash:
case token.Slash:
return parseAbstraction(i)
case TokenAtom:
case token.Atom:
return parseAtom(i)
case TokenOpenBrace:
case token.OpenBrace:
return parseClause(i, true)
default:
return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
@@ -182,7 +183,7 @@ 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 {
} else if _, err := parseToken(i, token.Assign, true); err != nil {
return nil, err
} else if body, err := parseExpression(i); err != nil {
return nil, err
@@ -211,7 +212,7 @@ func parseStatement(i *TokenIterator) (Statement, error) {
}
// Given a list of tokens, attempt to parse it into an syntax tree.
func parse(tokens []Token) (Expression, error) {
func parse(tokens []token.Token) (Expression, error) {
i := iterator.Of(tokens)
exp, err := parseClause(i, false)

22
pkg/saccharine/saccharine.go Normal file
View File

@@ -0,0 +1,22 @@
// 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/saccharine/token"
)
// Convert a piece of valid saccharine code into an expression.
func Parse(code string) (Expression, error) {
tokens, err := token.Parse(code)
if err != nil {
return nil, err
}
return parse(tokens)
}
// Convert a parsed saccharine expression back into source code.
func Stringify(expression Expression) string {
return stringifyExpression(expression)
}

91
pkg/saccharine/token.go
View File

@@ -1,91 +0,0 @@
package saccharine
import "fmt"
// All tokens in the pseudo-lambda language.
type TokenType int
const (
TokenOpenParen TokenType = 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 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 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))
}
}
func (t Token) Name() string {
return t.Type.Name()
}

38
pkg/saccharine/scan.go → pkg/saccharine/token/parse.go
View File

@@ -1,4 +1,4 @@
package saccharine
package token
import (
"errors"
@@ -14,7 +14,7 @@ func isVariable(r rune) bool {
return unicode.IsLetter(r) || unicode.IsNumber(r)
}
func scanRune(i *iterator.Iterator[rune], expected func(rune) bool) (rune, error) {
func parseRune(i *iterator.Iterator[rune], expected func(rune) bool) (rune, error) {
i2 := i.Copy()
if r, err := i2.Next(); err != nil {
@@ -27,7 +27,7 @@ func scanRune(i *iterator.Iterator[rune], expected func(rune) bool) (rune, error
}
}
func scanCharacter(i *iterator.Iterator[rune], expected rune) (rune, error) {
func parseCharacter(i *iterator.Iterator[rune], expected rune) (rune, error) {
i2 := i.Copy()
if r, err := i2.Next(); err != nil {
@@ -42,7 +42,7 @@ func scanCharacter(i *iterator.Iterator[rune], expected rune) (rune, error) {
// 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) {
func getToken(i *iterator.Iterator[rune]) (*Token, error) {
index := i.Index()
if i.Done() {
@@ -56,27 +56,27 @@ func scanToken(i *iterator.Iterator[rune]) (*Token, error) {
switch {
case letter == '(':
return NewTokenOpenParen(index), nil
return NewOpenParen(index), nil
case letter == ')':
return NewTokenCloseParen(index), nil
return NewCloseParen(index), nil
case letter == '.':
return NewTokenDot(index), nil
return NewDot(index), nil
case letter == '\\':
return NewTokenSlash(index), nil
return NewSlash(index), nil
case letter == '\n':
return NewTokenSoftBreak(index), nil
return NewSoftBreak(index), nil
case letter == '{':
return NewTokenOpenBrace(index), nil
return NewOpenBrace(index), nil
case letter == '}':
return NewTokenCloseBrace(index), nil
return NewCloseBrace(index), nil
case letter == ':':
if _, err := scanCharacter(i, '='); err != nil {
if _, err := parseCharacter(i, '='); err != nil {
return nil, err
} else {
return NewTokenAssign(index), nil
return NewAssign(index), nil
}
case letter == ';':
return NewTokenHardBreak(index), nil
return NewHardBreak(index), nil
case letter == '#':
// Skip everything until the next newline or EOF.
for !i.Done() {
@@ -98,27 +98,27 @@ func scanToken(i *iterator.Iterator[rune]) (*Token, error) {
atom := []rune{letter}
for {
if r, err := scanRune(i, isVariable); err != nil {
if r, err := parseRune(i, isVariable); err != nil {
break
} else {
atom = append(atom, r)
}
}
return NewTokenAtom(string(atom), index), nil
return NewAtom(string(atom), index), nil
}
return nil, fmt.Errorf("unknown character '%v'", string(letter))
}
// scan a string into tokens.
func scan(input string) ([]Token, error) {
// Parse a string into tokens.
func Parse(input string) ([]Token, error) {
i := iterator.Of([]rune(input))
tokens := []Token{}
errorList := []error{}
for !i.Done() {
token, err := scanToken(i)
token, err := getToken(i)
if err != nil {
errorList = append(errorList, err)
} else if token != nil {

91
pkg/saccharine/token/token.go Normal file
View File

@@ -0,0 +1,91 @@
package token
import "fmt"
// All tokens in the pseudo-lambda language.
type Type int
const (
OpenParen Type = iota // Denotes the '(' token.
CloseParen // Denotes the ')' token.
OpenBrace // Denotes the '{' token.
CloseBrace // Denotes the '}' token.
HardBreak // Denotes the ';' token.
Assign // Denotes the ':=' token.
Atom // Denotes an alpha-numeric variable.
Slash // Denotes the '/' token.
Dot // Denotes the '.' token.
SoftBreak // 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: OpenParen, Column: column, Value: "("}
}
func NewCloseParen(column int) *Token {
return &Token{Type: CloseParen, Column: column, Value: ")"}
}
func NewOpenBrace(column int) *Token {
return &Token{Type: OpenBrace, Column: column, Value: "{"}
}
func NewCloseBrace(column int) *Token {
return &Token{Type: CloseBrace, Column: column, Value: "}"}
}
func NewDot(column int) *Token {
return &Token{Type: Dot, Column: column, Value: "."}
}
func NewHardBreak(column int) *Token {
return &Token{Type: HardBreak, Column: column, Value: ";"}
}
func NewAssign(column int) *Token {
return &Token{Type: Assign, Column: column, Value: ":="}
}
func NewSlash(column int) *Token {
return &Token{Type: Slash, Column: column, Value: "\\"}
}
func NewAtom(name string, column int) *Token {
return &Token{Type: Atom, Column: column, Value: name}
}
func NewSoftBreak(column int) *Token {
return &Token{Type: SoftBreak, Column: column, Value: "\\n"}
}
func Name(typ Type) string {
switch typ {
case OpenParen:
return "("
case CloseParen:
return ")"
case Slash:
return "\\"
case Dot:
return "."
case Atom:
return "ATOM"
case SoftBreak:
return "\\n"
case HardBreak:
return ";"
default:
panic(fmt.Errorf("unknown token type %v", typ))
}
}
func (t Token) Name() string {
return Name(t.Type)
}

16
pkg/set/set.go
View File

@@ -4,9 +4,9 @@ import "iter"
type Set[T comparable] map[T]bool
func (s Set[T]) Add(items ...T) {
func (s *Set[T]) Add(items ...T) {
for _, item := range items {
s[item] = true
(*s)[item] = true
}
}
@@ -14,14 +14,14 @@ func (s Set[T]) Has(item T) bool {
return s[item]
}
func (s Set[T]) Remove(items ...T) {
func (s *Set[T]) Remove(items ...T) {
for _, item := range items {
delete(s, item)
delete(*s, item)
}
}
func (s Set[T]) Merge(o Set[T]) {
for item := range o {
func (s *Set[T]) Merge(o *Set[T]) {
for item := range *o {
s.Add(item)
}
}
@@ -46,8 +46,8 @@ func (s Set[T]) Items() iter.Seq[T] {
}
}
func New[T comparable](items ...T) Set[T] {
result := Set[T]{}
func New[T comparable](items ...T) *Set[T] {
result := &Set[T]{}
for _, item := range items {
result.Add(item)

1
tests/church_6^6.expected Normal file
View File

File diff suppressed because one or more lines are too long

8
tests/church_6^6.test Normal file
View File

@@ -0,0 +1,8 @@
0 := \f.\x.x
inc n := \f x.(f (n f x))
exp n m := (m n)
print n := (n F X)
N := (inc (inc (inc (inc (inc (inc 0))))))
(print (exp N N))