Compare commits
5 Commits
feat/scann
...
66ab8d6b1c
| Author | SHA1 | Date | |
|---|---|---|---|
66ab8d6b1c
|
|||
|
dc9a1b2b7d | ||
|
|
7e59d5cefa | ||
|
|
9f06a5109f | ||
|
|
b2b2655c1e |
@@ -1,58 +0,0 @@
|
||||
---
|
||||
name: "Bug Report"
|
||||
about: "Report a bug or unexpected behavior in the lambda runtime."
|
||||
title: "fix: "
|
||||
ref: "main"
|
||||
assignees: []
|
||||
labels:
|
||||
- bug
|
||||
---
|
||||
|
||||
## Context
|
||||
|
||||
<!--
|
||||
Describe what you were trying to do when you encountered the bug.
|
||||
Explain what you expected to happen.
|
||||
-->
|
||||
|
||||
## Current Behavior
|
||||
|
||||
<!--
|
||||
Describe what actually happened.
|
||||
Be specific about the incorrect behavior or error.
|
||||
-->
|
||||
|
||||
## Steps to Reproduce
|
||||
|
||||
<!--
|
||||
Provide step-by-step instructions to reproduce the issue.
|
||||
Include any relevant code, commands, or input.
|
||||
-->
|
||||
|
||||
1.
|
||||
2.
|
||||
3.
|
||||
|
||||
## Expected Behavior
|
||||
|
||||
<!--
|
||||
Describe what should happen instead.
|
||||
-->
|
||||
|
||||
## Environment
|
||||
|
||||
<!--
|
||||
Provide relevant information about your environment.
|
||||
-->
|
||||
|
||||
- Lambda version:
|
||||
- Go version:
|
||||
- Operating system:
|
||||
|
||||
## Additional Context
|
||||
|
||||
<!--
|
||||
Add any other context about the problem.
|
||||
Include error messages, logs, or screenshots if applicable.
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
@@ -1,44 +0,0 @@
|
||||
---
|
||||
name: "Feature Request"
|
||||
about: "Suggest a new feature or enhancement for the lambda runtime."
|
||||
title: "feat: "
|
||||
ref: "main"
|
||||
assignees: []
|
||||
labels:
|
||||
- enhancement
|
||||
---
|
||||
|
||||
## Context
|
||||
|
||||
<!--
|
||||
Describe the problem or limitation you're encountering.
|
||||
Explain why this feature would be valuable.
|
||||
-->
|
||||
|
||||
## Proposed Solution
|
||||
|
||||
<!--
|
||||
Describe your proposed solution or enhancement.
|
||||
Be specific about what you want to see implemented.
|
||||
-->
|
||||
|
||||
## Alternatives Considered
|
||||
|
||||
<!--
|
||||
List any alternative solutions or approaches you've considered.
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
|
||||
## Acceptance Criteria
|
||||
|
||||
<!--
|
||||
List clear, testable criteria that define when this feature is complete.
|
||||
Use bullet points starting with •
|
||||
-->
|
||||
|
||||
## Additional Context
|
||||
|
||||
<!--
|
||||
Add any other context, screenshots, or examples about the feature request.
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
@@ -1,37 +0,0 @@
|
||||
---
|
||||
name: "General Issue"
|
||||
about: "Create an issue that doesn't fit other templates."
|
||||
title: ""
|
||||
ref: "main"
|
||||
assignees: []
|
||||
labels: []
|
||||
---
|
||||
|
||||
## Context
|
||||
|
||||
<!--
|
||||
Describe the background and context for this issue.
|
||||
Explain why this issue exists.
|
||||
-->
|
||||
|
||||
## Description
|
||||
|
||||
<!--
|
||||
Provide a detailed description of what needs to be done.
|
||||
Be clear and specific about the requirements.
|
||||
-->
|
||||
|
||||
## Acceptance Criteria
|
||||
|
||||
<!--
|
||||
List clear, testable criteria that define when this issue is complete.
|
||||
Use bullet points starting with •
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
|
||||
## Additional Context
|
||||
|
||||
<!--
|
||||
Add any other relevant information, links, or references.
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
@@ -1,37 +0,0 @@
|
||||
---
|
||||
name: "Default Template"
|
||||
about: "The default template for `lambda`."
|
||||
title: "<type>: <description>"
|
||||
ref: "main"
|
||||
assignees: []
|
||||
labels: []
|
||||
---
|
||||
|
||||
## Description
|
||||
|
||||
<!--
|
||||
First, describe the context for the PR.
|
||||
Then, explain why the PR exists.
|
||||
Finally, in concise, sentence-long bullets, explain each change.
|
||||
-->
|
||||
|
||||
### Decisions
|
||||
|
||||
<!--
|
||||
List any major architectural decisions here.
|
||||
If none exist, omit this section.
|
||||
-->
|
||||
|
||||
## Benefits
|
||||
|
||||
<!--
|
||||
List any major benefits here.
|
||||
How would this PR improve the codebase/product?
|
||||
-->
|
||||
|
||||
## Checklist
|
||||
|
||||
- [ ] Code follows conventional commit format.
|
||||
- [ ] Branch follows naming convention (`<type>/<description>`). Always use underscores.
|
||||
- [ ] Tests pass (if applicable).
|
||||
- [ ] Documentation updated (if applicable).
|
||||
4
.gitignore
vendored
4
.gitignore
vendored
@@ -3,13 +3,15 @@
|
||||
# https://github.com/github/gitignore/blob/main/community/Golang/Go.AllowList.gitignore
|
||||
#
|
||||
# Binaries for programs and plugins
|
||||
/lambda
|
||||
*.exe
|
||||
*.exe~
|
||||
*.dll
|
||||
*.so
|
||||
*.dylib
|
||||
|
||||
# Test binary, built with `go test -c`
|
||||
*.test
|
||||
|
||||
# Output of the go coverage tool, specifically when used with LiteIDE
|
||||
*.out
|
||||
|
||||
|
||||
160
.golangci.yml
160
.golangci.yml
@@ -1,235 +1,83 @@
|
||||
---
|
||||
# golangci-lint configuration file made by @ccoVeille
|
||||
# Source: https://github.com/ccoVeille/golangci-lint-config-examples/
|
||||
# Author: @ccoVeille
|
||||
# License: MIT
|
||||
# Variant: 03-safe
|
||||
# Version: v2.0.0
|
||||
#
|
||||
version: "2"
|
||||
|
||||
formatters:
|
||||
enable:
|
||||
# format the code
|
||||
- gofmt
|
||||
# format the block of imports
|
||||
- gci
|
||||
|
||||
settings:
|
||||
# format the code with Go standard library
|
||||
gofmt:
|
||||
# simplify the code
|
||||
# https://pkg.go.dev/cmd/gofmt#hdr-The_simplify_command
|
||||
simplify: true
|
||||
rewrite-rules:
|
||||
# replace `interface{}` with `any` in the code on format
|
||||
- pattern: 'interface{}'
|
||||
replacement: 'any'
|
||||
|
||||
# make sure imports are always in a deterministic order
|
||||
# https://github.com/daixiang0/gci/
|
||||
gci: # define the section orders for imports
|
||||
|
||||
gci:
|
||||
sections:
|
||||
# Standard section: captures all standard packages.
|
||||
- standard
|
||||
# Default section: catchall that is not standard or custom
|
||||
- default
|
||||
# linters that related to local tool, so they should be separated
|
||||
- localmodule
|
||||
|
||||
linters:
|
||||
exclusions:
|
||||
# these presets where present in the v1 version of golangci-lint
|
||||
# it's interesting to keep them when migrating, but removing them should be the goal
|
||||
presets:
|
||||
# exclude check on comments format in godoc
|
||||
# These are common false positives in poor code
|
||||
# you should not use this on recent code you write from scratch
|
||||
# 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
|
||||
|
||||
# Common false positives
|
||||
# feel free to remove this if you don't have any false positives
|
||||
# More information: https://golangci-lint.run/usage/false-positives/#common-false-positives
|
||||
- comments
|
||||
- common-false-positives
|
||||
|
||||
# Legacy preset is not recommended anymore
|
||||
# More information: https://golangci-lint.run/usage/false-positives/#legacy
|
||||
- legacy
|
||||
|
||||
# std-error-handling is a set of rules that avoid reporting unhandled errors on common functions/methods
|
||||
# More information: https://golangci-lint.run/usage/false-positives/#std-error-handling
|
||||
- std-error-handling
|
||||
|
||||
# some linters are enabled by default
|
||||
# https://golangci-lint.run/usage/linters/
|
||||
#
|
||||
# enable some extra linters
|
||||
enable:
|
||||
# Errcheck is a program for checking for unchecked errors in Go code.
|
||||
- errcheck
|
||||
|
||||
# Vet examines Go source code and reports suspicious constructs.
|
||||
- govet
|
||||
|
||||
# Detects when assignments to existing variables are not used.
|
||||
- ineffassign
|
||||
|
||||
# It's a set of rules from staticcheck. See https://staticcheck.io/
|
||||
- staticcheck
|
||||
|
||||
# Checks Go code for unused constants, variables, functions and types.
|
||||
- unused
|
||||
|
||||
# Fast, configurable, extensible, flexible, and beautiful linter for Go.
|
||||
# Drop-in replacement of golint.
|
||||
- revive
|
||||
|
||||
# make sure to use t.Helper() when needed
|
||||
- thelper
|
||||
|
||||
# mirror suggests rewrites to avoid unnecessary []byte/string conversion
|
||||
- mirror
|
||||
|
||||
# detect the possibility to use variables/constants from the Go standard library.
|
||||
- usestdlibvars
|
||||
|
||||
# Finds commonly misspelled English words.
|
||||
- misspell
|
||||
|
||||
# Checks for duplicate words in the source code.
|
||||
- dupword
|
||||
|
||||
# linter to detect errors invalid key values count
|
||||
- loggercheck
|
||||
|
||||
# detect when a package or method could be replaced by one from the standard library
|
||||
- exptostd
|
||||
|
||||
# detects nested contexts in loops or function literals
|
||||
- fatcontext
|
||||
|
||||
# Reports uses of functions with replacement inside the testing package.
|
||||
- usetesting
|
||||
|
||||
settings:
|
||||
revive:
|
||||
rules:
|
||||
# these are the default revive rules
|
||||
# you can remove the whole "rules" node if you want
|
||||
# BUT
|
||||
# ! /!\ they all need to be present when you want to add more rules than the default ones
|
||||
# otherwise, you won't have the default rules, but only the ones you define in the "rules" node
|
||||
|
||||
# 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:
|
||||
- allowTypesBefore: "*testing.T"
|
||||
|
||||
# Basic types should not be used as a key in `context.WithValue`
|
||||
- name: context-keys-type
|
||||
|
||||
# Importing with `.` makes the programs much harder to understand
|
||||
- name: dot-imports
|
||||
|
||||
# Empty blocks make code less readable and could be a symptom of a bug or unfinished refactoring.
|
||||
- name: empty-block
|
||||
|
||||
# for better readability, variables of type `error` must be named with the prefix `err`.
|
||||
- name: error-naming
|
||||
|
||||
# for better readability, the errors should be last in the list of returned values by a function.
|
||||
- name: error-return
|
||||
|
||||
# for better readability, error messages should not be capitalized or end with punctuation or a newline.
|
||||
- name: error-strings
|
||||
|
||||
# report when replacing `errors.New(fmt.Sprintf())` with `fmt.Errorf()` is possible
|
||||
- name: errorf
|
||||
|
||||
# check naming and commenting conventions on exported symbols.
|
||||
- name: exported
|
||||
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
|
||||
|
||||
# highlights redundant else-blocks that can be eliminated from the code
|
||||
# - name: indent-error-flow
|
||||
|
||||
# This rule suggests a shorter way of writing ranges that do not use the second value.
|
||||
- name: range
|
||||
|
||||
# receiver names in a method should reflect the struct name (p for Person, for example)
|
||||
- name: receiver-naming
|
||||
|
||||
# redefining built in names (true, false, append, make) can lead to bugs very difficult to detect.
|
||||
- name: redefines-builtin-id
|
||||
|
||||
# redundant else-blocks that can be eliminated from the code.
|
||||
# - name: superfluous-else
|
||||
|
||||
# prevent confusing name for variables when using `time` package
|
||||
- name: time-naming
|
||||
|
||||
# warns when an exported function or method returns a value of an un-exported type.
|
||||
- name: unexported-return
|
||||
|
||||
# spots and proposes to remove unreachable code. also helps to spot errors
|
||||
- name: unreachable-code
|
||||
|
||||
# Functions or methods with unused parameters can be a symptom of an unfinished refactoring or a bug.
|
||||
- name: unused-parameter
|
||||
|
||||
# report when a variable declaration can be simplified
|
||||
- name: var-declaration
|
||||
|
||||
# warns when initialism, variable or package naming conventions are not followed.
|
||||
- name: var-naming
|
||||
|
||||
misspell:
|
||||
# Correct spellings using locale preferences for US or UK.
|
||||
# Setting locale to US will correct the British spelling of 'colour' to 'color'.
|
||||
# Default ("") is to use a neutral variety of English.
|
||||
locale: US
|
||||
|
||||
# List of words to ignore
|
||||
# among the one defined in https://github.com/golangci/misspell/blob/master/words.go
|
||||
ignore-rules: []
|
||||
# - valor
|
||||
# - and
|
||||
|
||||
# Extra word corrections.
|
||||
extra-words: []
|
||||
# - typo: "whattever"
|
||||
# correction: "whatever"
|
||||
|
||||
output:
|
||||
# Order to use when sorting results.
|
||||
# Possible values: `file`, `linter`, and `severity`.
|
||||
#
|
||||
# If the severity values are inside the following list, they are ordered in this order:
|
||||
# 1. error
|
||||
# 2. warning
|
||||
# 3. high
|
||||
# 4. medium
|
||||
# 5. low
|
||||
# Either they are sorted alphabetically.
|
||||
#
|
||||
# Default: ["file"]
|
||||
sort-order:
|
||||
- linter
|
||||
- severity
|
||||
- file # filepath, line, and column.
|
||||
- file
|
||||
|
||||
3
.vscode/settings.json
vendored
Normal file
3
.vscode/settings.json
vendored
Normal file
@@ -0,0 +1,3 @@
|
||||
{
|
||||
"makefile.configureOnOpen": false
|
||||
}
|
||||
69
CLAUDE.md
69
CLAUDE.md
@@ -1,12 +1,6 @@
|
||||
# Guide To `lambda`
|
||||
|
||||
## Documentation Style
|
||||
|
||||
Use full sentences.
|
||||
Every sentence gets its own line in Markdown.
|
||||
Every sentence ends in a period.
|
||||
|
||||
## Coding Style
|
||||
## Coding Styles
|
||||
|
||||
### Conventional Commits
|
||||
|
||||
@@ -20,8 +14,6 @@ Use conventional commit format: `<type>: <description>`.
|
||||
- `fix: correct variable renaming in nested abstractions`
|
||||
- `docs: update Makefile documentation`
|
||||
|
||||
DO NOT advertise Claude.
|
||||
|
||||
### Branch Names
|
||||
|
||||
Use format: `<type>/<description>` with kebab-case.
|
||||
@@ -35,71 +27,16 @@ Use format: `<type>/<description>` with kebab-case.
|
||||
- `docs/makefile-improvements`
|
||||
- `refactor/silent-directive`
|
||||
|
||||
DO NOT advertise Claude.
|
||||
|
||||
## Issue Management
|
||||
|
||||
Use the `tea` CLI (Gitea command-line tool) for issue operations.
|
||||
|
||||
**Common commands**:
|
||||
|
||||
- `tea issues list` - List all issues.
|
||||
- `tea issues <number>` - View details of a specific issue.
|
||||
- `tea issues create --title "<title>" --body "<description>"` - Create a new issue.
|
||||
- `tea issues close <number>` - Close an issue.
|
||||
|
||||
**Reading issues**: Use `tea issues <number>` to read the full details of an issue before starting work.
|
||||
|
||||
## Issue Workflow
|
||||
|
||||
When working on an issue:
|
||||
|
||||
1. Read the issue using `tea issues <number>` to understand requirements.
|
||||
2. Create a feature branch following the branch naming convention.
|
||||
3. Make commits following the conventional commit format.
|
||||
4. Submit a pull request when ready.
|
||||
|
||||
**Important**: Never commit directly to `main`.
|
||||
All work must be done in a feature branch and submitted via pull request.
|
||||
|
||||
## Pull Request Management
|
||||
|
||||
Use the `tea` CLI (Gitea command-line tool) for PR operations instead of `gh`.
|
||||
|
||||
**Common commands**:
|
||||
|
||||
- `tea pr create --title "<title>" --description "<body>"` - Create a new pull request.
|
||||
- `tea pr create` - Create a new pull request.
|
||||
- `tea pr list` - List pull requests.
|
||||
- `tea pr checkout <number>` - Check out a PR locally.
|
||||
- `tea pr close <number>` - Close a pull request.
|
||||
- `tea pr merge <number>` - Merge a pull request.
|
||||
|
||||
**Note**: Use `--description` (not `--body`) for PR body content.
|
||||
|
||||
**Creating PRs**: Always create PRs in a branch other than `main`, to the `main` branch unless specified otherwise. ALWAYS FOLLOW THE PR TEMPLATE, EXACTLY.
|
||||
|
||||
**Linking issues**: When a PR solves an issue, reference the issue in both the commit message and PR description using `Closes #<number>`.
|
||||
This automatically links and closes the issue when the PR is merged.
|
||||
|
||||
### Updating PRs
|
||||
|
||||
When pushing additional changes to an existing PR, add a comment summarizing the new commits.
|
||||
This keeps reviewers informed of what changed since the initial PR description.
|
||||
|
||||
Use the `tea` CLI to add comments to pull requests:
|
||||
|
||||
```bash
|
||||
tea comment <number> "Comment text"
|
||||
```
|
||||
|
||||
#### Examples
|
||||
|
||||
```bash
|
||||
# Add a comment to PR #42
|
||||
tea comment 42 "Updated implementation based on feedback"
|
||||
|
||||
# Add a multi-line comment
|
||||
tea comment 42 "Summary of changes:
|
||||
- Fixed bug in reducer
|
||||
- Added new tests"
|
||||
```
|
||||
**Creating PRs**: Always create PRs in a branch other than `main`, to the `main` branch unless specified otherwise.
|
||||
|
||||
2
LICENSE
2
LICENSE
@@ -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.
|
||||
|
||||
64
Makefile
64
Makefile
@@ -1,55 +1,21 @@
|
||||
BINARY_NAME=lambda
|
||||
BINARY_NAME=lambda.exe
|
||||
|
||||
it:
|
||||
@ go build -o ${BINARY_NAME} ./cmd/lambda
|
||||
@ chmod +x ${BINARY_NAME}
|
||||
|
||||
TEST=simple
|
||||
|
||||
.PHONY: help build run profile explain graph docs test bench lint clean
|
||||
.DEFAULT_GOAL := help
|
||||
.SILENT:
|
||||
run: it
|
||||
@ ./lambda.exe - < ./samples/$(TEST).txt > program.out
|
||||
|
||||
help:
|
||||
echo "Available targets:"
|
||||
echo " build - Build the lambda executable"
|
||||
echo " run - Build and run the lambda runtime (use TEST=<name> to specify sample)"
|
||||
echo " profile - Build and run with CPU profiling enabled"
|
||||
echo " explain - Build and run with explanation mode and profiling"
|
||||
echo " graph - Generate and open CPU profile visualization"
|
||||
echo " docs - Start local godoc server on port 6060"
|
||||
echo " test - Run tests for all samples"
|
||||
echo " bench - Run benchmarks for all samples"
|
||||
echo " lint - Run golangci-lint on all packages"
|
||||
echo " clean - Remove all build artifacts"
|
||||
profile: it
|
||||
@ ./lambda.exe -p profile/cpu.prof - < ./samples/$(TEST).txt > program.out
|
||||
|
||||
build:
|
||||
go build -o ${BINARY_NAME} ./cmd/lambda
|
||||
chmod +x ${BINARY_NAME}
|
||||
|
||||
run: build
|
||||
./${BINARY_NAME} -s -f ./tests/$(TEST).test -o program.out
|
||||
|
||||
profile: build
|
||||
./${BINARY_NAME} -p profile/cpu.prof -f ./tests/$(TEST).test -o program.out
|
||||
|
||||
explain: build
|
||||
./${BINARY_NAME} -x -p profile/cpu.prof -f ./tests/$(TEST).test -o program.out > explain.out
|
||||
explain: it
|
||||
@ ./lambda.exe -x -p profile/cpu.prof - < ./samples/$(TEST).txt > program.out
|
||||
|
||||
graph:
|
||||
go tool pprof -raw -output=profile/cpu.raw profile/cpu.prof
|
||||
go tool pprof -svg profile/cpu.prof > profile/cpu.svg
|
||||
echo ">>> View at 'file://$(PWD)/profile/cpu.svg'"
|
||||
|
||||
docs:
|
||||
echo ">>> View at 'http://localhost:6060/pkg/git.maximhutz.com/max/lambda/'"
|
||||
go run golang.org/x/tools/cmd/godoc@latest -http=:6060
|
||||
|
||||
test:
|
||||
go test -v ./cmd/lambda
|
||||
|
||||
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
|
||||
rm -rf profile/
|
||||
@ go tool pprof -raw -output=profile/cpu.raw profile/cpu.prof
|
||||
@ go tool pprof -svg profile/cpu.prof > profile/cpu.svg
|
||||
@ echo "Profile graph saved to 'file://profile/cpu.svg'"
|
||||
|
||||
@@ -1,6 +1,6 @@
|
||||
# lambda
|
||||
|
||||
Making a lambda calculus runtime in Go.
|
||||
Making a lambda calculus interpreter in Go.
|
||||
|
||||
## Things to talk about
|
||||
|
||||
|
||||
@@ -1,32 +1,76 @@
|
||||
// Package main defines the 'lambda' command-line interface (CLI).
|
||||
package main
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"os"
|
||||
|
||||
"github.com/spf13/cobra"
|
||||
"git.maximhutz.com/max/lambda/internal/cli"
|
||||
"git.maximhutz.com/max/lambda/internal/config"
|
||||
"git.maximhutz.com/max/lambda/internal/engine"
|
||||
"git.maximhutz.com/max/lambda/internal/explanation"
|
||||
"git.maximhutz.com/max/lambda/internal/performance"
|
||||
"git.maximhutz.com/max/lambda/internal/statistics"
|
||||
"git.maximhutz.com/max/lambda/pkg/convert"
|
||||
"git.maximhutz.com/max/lambda/pkg/lambda"
|
||||
"git.maximhutz.com/max/lambda/pkg/saccharine"
|
||||
)
|
||||
|
||||
func Lambda() *cobra.Command {
|
||||
cmd := &cobra.Command{
|
||||
Use: "lambda",
|
||||
Short: "Lambda calculus interpreter",
|
||||
Long: "A lambda calculus interpreter supporting multiple representations.",
|
||||
RunE: func(cmd *cobra.Command, _ []string) error {
|
||||
return cmd.Help()
|
||||
},
|
||||
}
|
||||
|
||||
cmd.AddCommand(LambdaConvert())
|
||||
cmd.AddCommand(LambdaEngine())
|
||||
cmd.AddCommand(LambdaReduce())
|
||||
|
||||
return cmd
|
||||
}
|
||||
|
||||
func main() {
|
||||
lambda := Lambda()
|
||||
if err := lambda.Execute(); err != nil {
|
||||
os.Exit(1)
|
||||
// Parse CLI arguments.
|
||||
options, err := config.FromArgs()
|
||||
cli.HandleError(err)
|
||||
|
||||
logger := options.GetLogger()
|
||||
logger.Info("using program arguments", "args", os.Args)
|
||||
logger.Info("parsed CLI options", "options", options)
|
||||
|
||||
// Get input.
|
||||
input, err := options.Source.Extract()
|
||||
cli.HandleError(err)
|
||||
|
||||
// Parse code into syntax tree.
|
||||
ast, err := saccharine.Parse(input)
|
||||
cli.HandleError(err)
|
||||
logger.Info("parsed syntax tree", "tree", ast)
|
||||
|
||||
// Compile expression to lambda calculus.
|
||||
compiled := convert.SaccharineToLambda(ast)
|
||||
logger.Info("compiled λ expression", "tree", lambda.Stringify(compiled))
|
||||
|
||||
// Create reduction engine.
|
||||
process := engine.New(options, &compiled)
|
||||
|
||||
// If the user selected to track CPU performance, attach a profiler to the
|
||||
// process.
|
||||
if options.Profile != "" {
|
||||
profiler := performance.Track(options.Profile)
|
||||
process.On("start", profiler.Start)
|
||||
process.On("end", profiler.End)
|
||||
}
|
||||
|
||||
// If the user selected to produce a step-by-step explanation, attach an
|
||||
// observer here.
|
||||
if options.Explanation {
|
||||
explanation.Track(process)
|
||||
}
|
||||
|
||||
// If the user opted to track statistics, attach a tracker here, too.
|
||||
if options.Statistics {
|
||||
statistics := statistics.Track()
|
||||
process.On("start", statistics.Start)
|
||||
process.On("step", statistics.Step)
|
||||
process.On("end", statistics.End)
|
||||
}
|
||||
|
||||
// If the user selected for verbose debug logs, attach a reduction tracker.
|
||||
if options.Verbose {
|
||||
process.On("step", func() {
|
||||
logger.Info("reduction", "tree", lambda.Stringify(compiled))
|
||||
})
|
||||
}
|
||||
|
||||
process.Run()
|
||||
|
||||
// Return the final reduced result.
|
||||
fmt.Println(lambda.Stringify(compiled))
|
||||
}
|
||||
|
||||
@@ -1,95 +0,0 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"os"
|
||||
"path/filepath"
|
||||
"strings"
|
||||
|
||||
"github.com/spf13/cobra"
|
||||
)
|
||||
|
||||
// inferReprFromPath returns the repr type based on file extension.
|
||||
func inferReprFromPath(path string) (string, error) {
|
||||
switch ext := strings.ToLower(filepath.Ext(path)); ext {
|
||||
case ".lambda", ".lam", ".lc":
|
||||
return "lambda", nil
|
||||
case ".saccharine", ".sch":
|
||||
return "saccharine", nil
|
||||
default:
|
||||
return "", fmt.Errorf("unknown file extension '%s'", ext)
|
||||
}
|
||||
}
|
||||
|
||||
func LambdaConvert() *cobra.Command {
|
||||
var inputReprFlag, outputReprFlag string
|
||||
|
||||
cmd := &cobra.Command{
|
||||
Use: "convert <input-file> <output-file>",
|
||||
Aliases: []string{"conv"},
|
||||
Short: "Convert between lambda calculus representations",
|
||||
SilenceUsage: true,
|
||||
RunE: func(cmd *cobra.Command, args []string) error {
|
||||
if len(args) != 2 {
|
||||
return cmd.Help()
|
||||
}
|
||||
|
||||
var err error
|
||||
inputPath, outputPath := args[0], args[1]
|
||||
|
||||
// Use flag if provided, otherwise infer from extension.
|
||||
inputRepr := inputReprFlag
|
||||
if inputRepr == "" {
|
||||
if inputRepr, err = inferReprFromPath(inputPath); err != nil {
|
||||
return fmt.Errorf("input file: %w", err)
|
||||
}
|
||||
}
|
||||
|
||||
outputRepr := outputReprFlag
|
||||
if outputRepr == "" {
|
||||
if outputRepr, err = inferReprFromPath(outputPath); err != nil {
|
||||
return fmt.Errorf("output file: %w", err)
|
||||
}
|
||||
}
|
||||
|
||||
// Read input file.
|
||||
input, err := os.ReadFile(inputPath)
|
||||
if err != nil {
|
||||
return fmt.Errorf("reading input file: %w", err)
|
||||
}
|
||||
|
||||
r := GetRegistry()
|
||||
|
||||
// Parse input into syntax tree.
|
||||
repr, err := r.Unmarshal(string(input), inputRepr)
|
||||
if err != nil {
|
||||
return fmt.Errorf("parsing input: %w", err)
|
||||
}
|
||||
|
||||
// Convert to output repr if different.
|
||||
result, err := r.ConvertTo(repr, outputRepr)
|
||||
if err != nil {
|
||||
return fmt.Errorf("converting %s to %s: %w", inputRepr, outputRepr, err)
|
||||
}
|
||||
|
||||
// Marshal output.
|
||||
output, err := r.Marshal(result)
|
||||
if err != nil {
|
||||
return fmt.Errorf("unmarshaling output: %w", err)
|
||||
}
|
||||
|
||||
// Write output file.
|
||||
err = os.WriteFile(outputPath, []byte(output), 0644)
|
||||
if err != nil {
|
||||
return fmt.Errorf("writing output file: %w", err)
|
||||
}
|
||||
|
||||
return nil
|
||||
},
|
||||
}
|
||||
|
||||
cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
|
||||
cmd.Flags().StringVarP(&outputReprFlag, "output", "o", "", "Output representation (inferred from extension if unset)")
|
||||
|
||||
return cmd
|
||||
}
|
||||
@@ -1,20 +0,0 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"github.com/spf13/cobra"
|
||||
)
|
||||
|
||||
func LambdaEngine() *cobra.Command {
|
||||
cmd := &cobra.Command{
|
||||
Use: "engine",
|
||||
Aliases: []string{"eng"},
|
||||
Short: "Information about available engines",
|
||||
RunE: func(cmd *cobra.Command, _ []string) error {
|
||||
return cmd.Help()
|
||||
},
|
||||
}
|
||||
|
||||
cmd.AddCommand(LambdaEngineList())
|
||||
|
||||
return cmd
|
||||
}
|
||||
@@ -1,26 +0,0 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
|
||||
"github.com/spf13/cobra"
|
||||
)
|
||||
|
||||
func LambdaEngineList() *cobra.Command {
|
||||
cmd := &cobra.Command{
|
||||
Use: "list",
|
||||
Aliases: []string{"ls"},
|
||||
Short: "List available engines",
|
||||
RunE: func(*cobra.Command, []string) error {
|
||||
r := GetRegistry()
|
||||
|
||||
for engine := range r.ListEngines() {
|
||||
fmt.Println(engine.Name())
|
||||
}
|
||||
|
||||
return nil
|
||||
},
|
||||
}
|
||||
|
||||
return cmd
|
||||
}
|
||||
@@ -1,108 +0,0 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
|
||||
"github.com/spf13/cobra"
|
||||
|
||||
"git.maximhutz.com/max/lambda/internal/cli"
|
||||
"git.maximhutz.com/max/lambda/internal/registry"
|
||||
)
|
||||
|
||||
func LambdaReduce() *cobra.Command {
|
||||
var inputReprFlag string
|
||||
var engineFlag string
|
||||
|
||||
cmd := &cobra.Command{
|
||||
Use: "reduce <input-file>",
|
||||
Short: "Reduce a lambda calculus expression",
|
||||
SilenceUsage: true,
|
||||
Aliases: []string{"run"},
|
||||
RunE: func(cmd *cobra.Command, args []string) error {
|
||||
var err error
|
||||
if len(args) != 1 {
|
||||
return cmd.Help()
|
||||
}
|
||||
|
||||
inputPath := args[0]
|
||||
|
||||
// Get input source.
|
||||
var source cli.Source
|
||||
if inputPath == "-" {
|
||||
source = cli.StdinSource{}
|
||||
} else {
|
||||
source = cli.FileSource{Path: inputPath}
|
||||
}
|
||||
|
||||
destination := cli.StdoutDestination{}
|
||||
|
||||
r := GetRegistry()
|
||||
|
||||
// Get input.
|
||||
input, err := source.Extract()
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
// Use flag if provided, otherwise infer from extension.
|
||||
inputRepr := inputReprFlag
|
||||
if inputRepr == "" {
|
||||
if inputRepr, err = inferReprFromPath(inputPath); err != nil {
|
||||
return fmt.Errorf("input file: %w", err)
|
||||
}
|
||||
}
|
||||
|
||||
// Find engine.
|
||||
var engine registry.Engine
|
||||
if engineFlag == "" {
|
||||
if engine, err = r.GetDefaultEngine(inputRepr); err != nil {
|
||||
return err
|
||||
}
|
||||
} else {
|
||||
if engine, err = r.GetEngine(engineFlag); err != nil {
|
||||
return err
|
||||
}
|
||||
}
|
||||
|
||||
// Parse code into syntax tree.
|
||||
repr, err := r.Unmarshal(input, inputRepr)
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
// Compile expression to lambda calculus.
|
||||
compiled, err := r.ConvertTo(repr, "lambda")
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
// Create process.
|
||||
process, err := engine.Load(compiled)
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
// Run reduction.
|
||||
for process.Step(1) {
|
||||
}
|
||||
|
||||
// Return the final reduced result.
|
||||
result, err := process.Get()
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
output, err := r.Marshal(result)
|
||||
if err != nil {
|
||||
return err
|
||||
}
|
||||
|
||||
return destination.Write(output)
|
||||
},
|
||||
}
|
||||
|
||||
cmd.Flags().StringVarP(&inputReprFlag, "input", "i", "", "Input representation (inferred from extension if unset)")
|
||||
cmd.Flags().StringVarP(&engineFlag, "engine", "e", "", "Reduction engine (inferred from '--input' if unset)")
|
||||
|
||||
return cmd
|
||||
}
|
||||
@@ -1,26 +0,0 @@
|
||||
package main
|
||||
|
||||
import (
|
||||
"git.maximhutz.com/max/lambda/internal/registry"
|
||||
"git.maximhutz.com/max/lambda/pkg/convert"
|
||||
"git.maximhutz.com/max/lambda/pkg/engine/normalorder"
|
||||
"git.maximhutz.com/max/lambda/pkg/lambda"
|
||||
"git.maximhutz.com/max/lambda/pkg/saccharine"
|
||||
)
|
||||
|
||||
func GetRegistry() *registry.Registry {
|
||||
r := registry.New()
|
||||
|
||||
// Codecs
|
||||
(registry.RegisterConversion(r, convert.Saccharine2Lambda, "saccharine", "lambda"))
|
||||
(registry.RegisterConversion(r, convert.Lambda2Saccharine, "lambda", "saccharine"))
|
||||
|
||||
// Engines
|
||||
(registry.RegisterEngine(r, normalorder.NewProcess, "normalorder", "lambda"))
|
||||
|
||||
// Marshalers
|
||||
(registry.RegisterCodec(r, lambda.Codec{}, "lambda"))
|
||||
(registry.RegisterCodec(r, saccharine.Codec{}, "saccharine"))
|
||||
|
||||
return r
|
||||
}
|
||||
7
go.mod
7
go.mod
@@ -1,10 +1,3 @@
|
||||
module git.maximhutz.com/max/lambda
|
||||
|
||||
go 1.25.5
|
||||
|
||||
require github.com/spf13/cobra v1.10.2
|
||||
|
||||
require (
|
||||
github.com/inconshreveable/mousetrap v1.1.0 // indirect
|
||||
github.com/spf13/pflag v1.0.10 // indirect
|
||||
)
|
||||
|
||||
11
go.sum
11
go.sum
@@ -1,11 +0,0 @@
|
||||
github.com/cpuguy83/go-md2man/v2 v2.0.6/go.mod h1:oOW0eioCTA6cOiMLiUPZOpcVxMig6NIQQ7OS05n1F4g=
|
||||
github.com/inconshreveable/mousetrap v1.1.0 h1:wN+x4NVGpMsO7ErUn/mUI3vEoE6Jt13X2s0bqwp9tc8=
|
||||
github.com/inconshreveable/mousetrap v1.1.0/go.mod h1:vpF70FUmC8bwa3OWnCshd2FqLfsEA9PFc4w1p2J65bw=
|
||||
github.com/russross/blackfriday/v2 v2.1.0/go.mod h1:+Rmxgy9KzJVeS9/2gXHxylqXiyQDYRxCVz55jmeOWTM=
|
||||
github.com/spf13/cobra v1.10.2 h1:DMTTonx5m65Ic0GOoRY2c16WCbHxOOw6xxezuLaBpcU=
|
||||
github.com/spf13/cobra v1.10.2/go.mod h1:7C1pvHqHw5A4vrJfjNwvOdzYu0Gml16OCs2GRiTUUS4=
|
||||
github.com/spf13/pflag v1.0.9/go.mod h1:McXfInJRrz4CZXVZOBLb0bTZqETkiAhM9Iw0y3An2Bg=
|
||||
github.com/spf13/pflag v1.0.10 h1:4EBh2KAYBwaONj6b2Ye1GiHfwjqyROoF4RwYO+vPwFk=
|
||||
github.com/spf13/pflag v1.0.10/go.mod h1:McXfInJRrz4CZXVZOBLb0bTZqETkiAhM9Iw0y3An2Bg=
|
||||
go.yaml.in/yaml/v3 v3.0.4/go.mod h1:DhzuOOF2ATzADvBadXxruRBLzYTpT36CKvDb3+aBEFg=
|
||||
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
|
||||
@@ -1,2 +0,0 @@
|
||||
// Package cli package provides various utilities to the 'lambda' program.
|
||||
package cli
|
||||
@@ -1,29 +0,0 @@
|
||||
package cli
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"os"
|
||||
)
|
||||
|
||||
// A Destination is method of writing output to the user.
|
||||
type Destination interface {
|
||||
// Write data to this destination.
|
||||
Write(data string) error
|
||||
}
|
||||
|
||||
// An StdoutDestination writes to stdout.
|
||||
type StdoutDestination struct{}
|
||||
|
||||
// Write outputs to standard output.
|
||||
func (d StdoutDestination) Write(data string) error {
|
||||
fmt.Println(data)
|
||||
return nil
|
||||
}
|
||||
|
||||
// A FileDestination writes to a file.
|
||||
type FileDestination struct{ Path string }
|
||||
|
||||
// Write outputs to a file.
|
||||
func (d FileDestination) Write(data string) error {
|
||||
return os.WriteFile(d.Path, []byte(data+"\n"), 0644)
|
||||
}
|
||||
18
internal/cli/exit.go
Normal file
18
internal/cli/exit.go
Normal file
@@ -0,0 +1,18 @@
|
||||
// Package "cli" provides miscellaneous helper functions.
|
||||
package cli
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"os"
|
||||
)
|
||||
|
||||
// A helper function to handle errors in the program. If it is given an error,
|
||||
// the program will exist, and print the error.
|
||||
func HandleError(err error) {
|
||||
if err == nil {
|
||||
return
|
||||
}
|
||||
|
||||
fmt.Fprintln(os.Stderr, "ERROR:", err)
|
||||
os.Exit(1)
|
||||
}
|
||||
@@ -1,44 +0,0 @@
|
||||
package cli
|
||||
|
||||
import (
|
||||
"io"
|
||||
"os"
|
||||
)
|
||||
|
||||
// A Source is a method of extracting input from the user.
|
||||
type Source interface {
|
||||
// Extract fetches data from this source.
|
||||
Extract() (string, error)
|
||||
}
|
||||
|
||||
// A StringSource is defined by a string.
|
||||
type StringSource struct{ Data string }
|
||||
|
||||
// Extract pulls input data from the internal string.
|
||||
func (s StringSource) Extract() (string, error) { return s.Data, nil }
|
||||
|
||||
// A StdinSource pulls from standard input.
|
||||
type StdinSource struct{}
|
||||
|
||||
// Extract pulls input data from standard input.
|
||||
func (s StdinSource) Extract() (string, error) {
|
||||
data, err := io.ReadAll(os.Stdin)
|
||||
if err != nil {
|
||||
return "", err
|
||||
}
|
||||
|
||||
return string(data), nil
|
||||
}
|
||||
|
||||
// A FileSource reads from a file.
|
||||
type FileSource struct{ Path string }
|
||||
|
||||
// Extract pulls input data from the file source.
|
||||
func (s FileSource) Extract() (string, error) {
|
||||
data, err := os.ReadFile(s.Path)
|
||||
if err != nil {
|
||||
return "", err
|
||||
}
|
||||
|
||||
return string(data), nil
|
||||
}
|
||||
11
internal/config/config.go
Normal file
11
internal/config/config.go
Normal file
@@ -0,0 +1,11 @@
|
||||
// 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.
|
||||
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.
|
||||
}
|
||||
23
internal/config/get_logger.go
Normal file
23
internal/config/get_logger.go
Normal file
@@ -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,
|
||||
}),
|
||||
)
|
||||
}
|
||||
39
internal/config/parse_from_args.go
Normal file
39
internal/config/parse_from_args.go
Normal file
@@ -0,0 +1,39 @@
|
||||
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.")
|
||||
flag.Parse()
|
||||
|
||||
// There must only be one input argument.
|
||||
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")
|
||||
}
|
||||
|
||||
// Parse source type.
|
||||
var source Source
|
||||
if flag.Arg(0) == "-" {
|
||||
source = StdinSource{}
|
||||
} else {
|
||||
source = StringSource{Data: flag.Arg(0)}
|
||||
}
|
||||
|
||||
return &Config{
|
||||
Source: source,
|
||||
Verbose: *verbose,
|
||||
Explanation: *explanation,
|
||||
Profile: *profile,
|
||||
Statistics: *statistics,
|
||||
}, nil
|
||||
}
|
||||
29
internal/config/source.go
Normal file
29
internal/config/source.go
Normal file
@@ -0,0 +1,29 @@
|
||||
package config
|
||||
|
||||
import (
|
||||
"io"
|
||||
"os"
|
||||
)
|
||||
|
||||
// A method of extracting input from the user.
|
||||
type Source interface {
|
||||
// Fetch data from this source.
|
||||
Extract() (string, error)
|
||||
}
|
||||
|
||||
// A source defined by a string.
|
||||
type StringSource struct{ Data string }
|
||||
|
||||
func (s StringSource) Extract() (string, error) { return s.Data, nil }
|
||||
|
||||
// A source pulling from standard input.
|
||||
type StdinSource struct{}
|
||||
|
||||
func (s StdinSource) Extract() (string, error) {
|
||||
data, err := io.ReadAll(os.Stdin)
|
||||
if err != nil {
|
||||
return "", err
|
||||
}
|
||||
|
||||
return string(data), nil
|
||||
}
|
||||
32
internal/engine/engine.go
Normal file
32
internal/engine/engine.go
Normal file
@@ -0,0 +1,32 @@
|
||||
// Package "engine" provides an extensible interface for users to interfact with
|
||||
// λ-calculus.
|
||||
package engine
|
||||
|
||||
import (
|
||||
"git.maximhutz.com/max/lambda/internal/config"
|
||||
"git.maximhutz.com/max/lambda/pkg/emitter"
|
||||
"git.maximhutz.com/max/lambda/pkg/lambda"
|
||||
)
|
||||
|
||||
// A process for reducing one λ-expression.
|
||||
type Engine struct {
|
||||
Config *config.Config
|
||||
Expression *lambda.Expression
|
||||
emitter.Emitter
|
||||
}
|
||||
|
||||
// Create a new engine, given an unreduced λ-expression.
|
||||
func New(config *config.Config, expression *lambda.Expression) *Engine {
|
||||
return &Engine{Config: config, Expression: expression}
|
||||
}
|
||||
|
||||
// Begin the reduction process.
|
||||
func (e Engine) Run() {
|
||||
e.Emit("start")
|
||||
|
||||
for lambda.ReduceOnce(e.Expression) {
|
||||
e.Emit("step")
|
||||
}
|
||||
|
||||
e.Emit("end")
|
||||
}
|
||||
32
internal/explanation/tracker.go
Normal file
32
internal/explanation/tracker.go
Normal file
@@ -0,0 +1,32 @@
|
||||
// Package "explanation" provides a observer to gather the reasoning during the
|
||||
// reduction, and present a thorough explanation to the user for each step.
|
||||
package explanation
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
|
||||
"git.maximhutz.com/max/lambda/internal/engine"
|
||||
"git.maximhutz.com/max/lambda/pkg/lambda"
|
||||
)
|
||||
|
||||
// Track the reductions made by a reduction proess.
|
||||
type Tracker struct {
|
||||
process *engine.Engine
|
||||
}
|
||||
|
||||
// Attaches a new explanation tracker to a process.
|
||||
func Track(process *engine.Engine) *Tracker {
|
||||
tracker := &Tracker{process: process}
|
||||
process.On("start", tracker.Start)
|
||||
process.On("step", tracker.Step)
|
||||
|
||||
return tracker
|
||||
}
|
||||
|
||||
func (t *Tracker) Start() {
|
||||
fmt.Println(lambda.Stringify(*t.process.Expression))
|
||||
}
|
||||
|
||||
func (t *Tracker) Step() {
|
||||
fmt.Println(" =", lambda.Stringify(*t.process.Expression))
|
||||
}
|
||||
53
internal/performance/tracker.go
Normal file
53
internal/performance/tracker.go
Normal file
@@ -0,0 +1,53 @@
|
||||
// Package "performance" provides a tracker to observer CPU performance during
|
||||
// execution.
|
||||
package performance
|
||||
|
||||
import (
|
||||
"os"
|
||||
"path/filepath"
|
||||
"runtime/pprof"
|
||||
)
|
||||
|
||||
// Observes a reduction process, and publishes a CPU performance profile on
|
||||
// completion.
|
||||
type Tracker struct {
|
||||
File string
|
||||
filePointer *os.File
|
||||
Error error
|
||||
}
|
||||
|
||||
// Create a performance tracker that outputs a profile to "file".
|
||||
func Track(file string) *Tracker {
|
||||
return &Tracker{File: file}
|
||||
}
|
||||
|
||||
// Begin profiling.
|
||||
func (t *Tracker) 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 *Tracker) End() {
|
||||
pprof.StopCPUProfile()
|
||||
t.filePointer.Close()
|
||||
}
|
||||
@@ -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
|
||||
}
|
||||
@@ -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
|
||||
}
|
||||
@@ -1,30 +0,0 @@
|
||||
package registry
|
||||
|
||||
// A Converter is a directed graph of conversions between representations. Each
|
||||
// node is a representation name, and each edge is a Conversion.
|
||||
type Converter struct {
|
||||
data map[string][]Conversion
|
||||
}
|
||||
|
||||
// NewConverter creates an empty Converter with no registered conversions.
|
||||
func NewConverter() *Converter {
|
||||
return &Converter{data: map[string][]Conversion{}}
|
||||
}
|
||||
|
||||
// Add registers a conversion, adding an edge from its source representation
|
||||
// to its target representation.
|
||||
func (g *Converter) Add(c Conversion) {
|
||||
conversionsFromIn, ok := g.data[c.InType()]
|
||||
if !ok {
|
||||
conversionsFromIn = []Conversion{}
|
||||
}
|
||||
|
||||
conversionsFromIn = append(conversionsFromIn, c)
|
||||
g.data[c.InType()] = conversionsFromIn
|
||||
}
|
||||
|
||||
// ConversionsFrom returns all conversions that have the given representation
|
||||
// as their source type.
|
||||
func (g *Converter) ConversionsFrom(t string) []Conversion {
|
||||
return g.data[t]
|
||||
}
|
||||
@@ -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] = ®isteredEngine[T]{e, name, inType}
|
||||
return nil
|
||||
}
|
||||
@@ -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} }
|
||||
@@ -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)
|
||||
}
|
||||
@@ -1,153 +0,0 @@
|
||||
// Package registry defines a structure to hold all available representations,
|
||||
// engines, and conversions between them.
|
||||
package registry
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"iter"
|
||||
"maps"
|
||||
)
|
||||
|
||||
// A Registry holds all representations, conversions, codecs, and engines
|
||||
// available to the program.
|
||||
type Registry struct {
|
||||
codecs map[string]Codec
|
||||
converter *Converter
|
||||
engines map[string]Engine
|
||||
}
|
||||
|
||||
// New makes an empty registry.
|
||||
func New() *Registry {
|
||||
return &Registry{
|
||||
codecs: map[string]Codec{},
|
||||
converter: NewConverter(),
|
||||
engines: map[string]Engine{},
|
||||
}
|
||||
}
|
||||
|
||||
// GetEngine finds an engine based on its name. Returns an error if an engine
|
||||
// with that name cannot be found.
|
||||
func (r Registry) GetEngine(name string) (Engine, error) {
|
||||
e, ok := r.engines[name]
|
||||
if !ok {
|
||||
return nil, fmt.Errorf("engine '%s' not found", name)
|
||||
}
|
||||
|
||||
return e, nil
|
||||
}
|
||||
|
||||
// ListEngines returns all available engines to the registry.
|
||||
func (r Registry) ListEngines() iter.Seq[Engine] {
|
||||
return maps.Values(r.engines)
|
||||
}
|
||||
|
||||
// GetDefaultEngine infers the preferred engine for a representation. Returns an
|
||||
// error if one cannot be chosen.
|
||||
func (r *Registry) GetDefaultEngine(id string) (Engine, error) {
|
||||
for _, engine := range r.engines {
|
||||
if engine.InType() == id {
|
||||
return engine, nil
|
||||
}
|
||||
}
|
||||
|
||||
return r.GetEngine("normalorder")
|
||||
|
||||
// return nil, fmt.Errorf("no engine for '%s'", id)
|
||||
}
|
||||
|
||||
// ConvertTo attempts to convert an expression of one type of representation to
|
||||
// another. Returns the converted expression, otherwise an error.
|
||||
//
|
||||
// It can convert between any two types of representations, given there is a
|
||||
// valid conversion path between them. It uses BFS to traverse a graph of
|
||||
// conversion edges, and converts along the shortest path.
|
||||
func (r *Registry) ConvertTo(expr Expr, outType string) (Expr, error) {
|
||||
path, err := r.ConversionPath(expr.Repr(), outType)
|
||||
if err != nil {
|
||||
return nil, err
|
||||
}
|
||||
|
||||
result := expr
|
||||
for _, conversion := range path {
|
||||
result, err = conversion.Run(result)
|
||||
if err != nil {
|
||||
return nil, fmt.Errorf("converting '%s' to '%s': %w", conversion.InType(), conversion.OutType(), err)
|
||||
}
|
||||
}
|
||||
|
||||
return result, err
|
||||
}
|
||||
|
||||
// Marshal serializes an expression, given that representation has a codec.
|
||||
// Returns an error if the representation is not registered, or it has no codec.
|
||||
func (r *Registry) Marshal(expr Expr) (string, error) {
|
||||
m, ok := r.codecs[expr.Repr()]
|
||||
if !ok {
|
||||
return "", fmt.Errorf("no marshaler for '%s'", expr.Repr())
|
||||
}
|
||||
|
||||
return m.Encode(expr)
|
||||
}
|
||||
|
||||
// Unmarshal deserializes an expression. Returns an error if the representation
|
||||
// or a codec for it is not registered.
|
||||
func (r *Registry) Unmarshal(s string, outType string) (Expr, error) {
|
||||
m, ok := r.codecs[outType]
|
||||
if !ok {
|
||||
return nil, fmt.Errorf("no marshaler for '%s'", outType)
|
||||
}
|
||||
|
||||
return m.Decode(s)
|
||||
}
|
||||
|
||||
func reverse[T any](list []T) []T {
|
||||
if list == nil {
|
||||
return list
|
||||
}
|
||||
|
||||
reversed := []T{}
|
||||
|
||||
for i := len(list) - 1; i >= 0; i-- {
|
||||
reversed = append(reversed, list[i])
|
||||
}
|
||||
|
||||
return reversed
|
||||
}
|
||||
|
||||
// ConversionPath attempts to find a set of valid conversions that (if applied)
|
||||
// convert one representation to another. Returns an error if no path can be
|
||||
// found.
|
||||
func (r *Registry) ConversionPath(from, to string) ([]Conversion, error) {
|
||||
backtrack := map[string]Conversion{}
|
||||
iteration := []string{from}
|
||||
for len(iteration) > 0 {
|
||||
nextIteration := []string{}
|
||||
|
||||
for _, item := range iteration {
|
||||
for _, conversion := range r.converter.ConversionsFrom(item) {
|
||||
if _, ok := backtrack[conversion.OutType()]; ok {
|
||||
continue
|
||||
}
|
||||
|
||||
nextIteration = append(nextIteration, conversion.OutType())
|
||||
backtrack[conversion.OutType()] = conversion
|
||||
}
|
||||
}
|
||||
|
||||
iteration = nextIteration
|
||||
}
|
||||
|
||||
reversedPath := []Conversion{}
|
||||
current := to
|
||||
for current != from {
|
||||
conversion, ok := backtrack[current]
|
||||
if !ok {
|
||||
return nil, fmt.Errorf("no valid conversion from '%s' to '%s'", from, to)
|
||||
}
|
||||
|
||||
reversedPath = append(reversedPath, conversion)
|
||||
current = conversion.InType()
|
||||
}
|
||||
|
||||
return reverse(reversedPath), nil
|
||||
}
|
||||
28
internal/statistics/statistics.go
Normal file
28
internal/statistics/statistics.go
Normal 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()
|
||||
}
|
||||
36
internal/statistics/tracker.go
Normal file
36
internal/statistics/tracker.go
Normal file
@@ -0,0 +1,36 @@
|
||||
package statistics
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
"os"
|
||||
"time"
|
||||
)
|
||||
|
||||
// An observer, to track reduction performance.
|
||||
type Tracker struct {
|
||||
start time.Time
|
||||
steps uint64
|
||||
}
|
||||
|
||||
// Create a new reduction performance tracker.
|
||||
func Track() *Tracker {
|
||||
return &Tracker{}
|
||||
}
|
||||
|
||||
func (t *Tracker) Start() {
|
||||
t.start = time.Now()
|
||||
t.steps = 0
|
||||
}
|
||||
|
||||
func (t *Tracker) Step() {
|
||||
t.steps++
|
||||
}
|
||||
|
||||
func (t *Tracker) End() {
|
||||
results := Results{
|
||||
StepsTaken: t.steps,
|
||||
TimeElapsed: uint64(time.Since(t.start).Milliseconds()),
|
||||
}
|
||||
|
||||
fmt.Fprint(os.Stderr, results.String())
|
||||
}
|
||||
@@ -1,20 +0,0 @@
|
||||
// Package codec defines processes to convert between different representations
|
||||
// of lambda calculus, and serialize the different representations.
|
||||
package codec
|
||||
|
||||
// A Conversion is a function that turns one representation into another.
|
||||
// Returns an error if the input expression cannot be converted.
|
||||
type Conversion[T, U any] = func(T) (U, error)
|
||||
|
||||
// A Codec is an object that can serialize/deserialize one type of
|
||||
// representation. It is assumed that for any x ∋ T, Decode(Encode(x)) = x.
|
||||
type Codec[T any] interface {
|
||||
// Encode takes an expression, and returns its serialized format, as a
|
||||
// string. Returns an error if the expression cannot be serialized.
|
||||
Encode(T) (string, error)
|
||||
|
||||
// Decode takes the serialized format of an expression, and returns its true
|
||||
// value. Returns an error if the string doesn't correctly represent any
|
||||
// valid expression.
|
||||
Decode(string) (T, error)
|
||||
}
|
||||
@@ -1,5 +1,3 @@
|
||||
// Package convert defined some standard conversions between various types of
|
||||
// representations.
|
||||
package convert
|
||||
|
||||
import (
|
||||
@@ -9,41 +7,41 @@ import (
|
||||
"git.maximhutz.com/max/lambda/pkg/saccharine"
|
||||
)
|
||||
|
||||
func encodeAtom(n *saccharine.Atom) lambda.Expression {
|
||||
return lambda.Variable{Name: n.Name}
|
||||
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 := lambda.GetFree(result)
|
||||
freeVars := lambda.GetFreeVariables(result)
|
||||
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
|
||||
}
|
||||
|
||||
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 {
|
||||
result = lambda.Application{Abstraction: result, Argument: argument}
|
||||
result = lambda.NewApplication(result, argument)
|
||||
}
|
||||
|
||||
return result
|
||||
@@ -53,24 +51,24 @@ 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.Abstraction{Parameters: s.Parameters, Body: s.Body})
|
||||
value = convertAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
|
||||
}
|
||||
|
||||
return lambda.Application{
|
||||
Abstraction: lambda.Abstraction{Parameter: s.Name, Body: e},
|
||||
Argument: value,
|
||||
}
|
||||
return lambda.NewApplication(
|
||||
lambda.NewAbstraction(s.Name, e),
|
||||
value,
|
||||
)
|
||||
}
|
||||
|
||||
func reduceDeclare(s *saccharine.DeclareStatement, e lambda.Expression) lambda.Expression {
|
||||
freshVar := lambda.GenerateFreshName(lambda.GetFree(e))
|
||||
freshVar := lambda.GenerateFreshName(lambda.GetFreeVariables(e))
|
||||
|
||||
return lambda.Application{
|
||||
Abstraction: lambda.Abstraction{Parameter: freshVar, Body: e},
|
||||
Argument: encodeExpression(s.Value),
|
||||
}
|
||||
return lambda.NewApplication(
|
||||
lambda.NewAbstraction(freshVar, e),
|
||||
SaccharineToLambda(s.Value),
|
||||
)
|
||||
}
|
||||
|
||||
func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Expression {
|
||||
@@ -84,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)
|
||||
@@ -94,45 +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.Atom{Name: l.Name}
|
||||
case lambda.Abstraction:
|
||||
return &saccharine.Abstraction{
|
||||
Parameters: []string{l.Parameter},
|
||||
Body: decodeExression(l.Body)}
|
||||
case lambda.Application:
|
||||
return &saccharine.Application{
|
||||
Abstraction: decodeExression(l.Abstraction),
|
||||
Arguments: []saccharine.Expression{decodeExression(l.Argument)}}
|
||||
default:
|
||||
panic(fmt.Errorf("unknown expression type: %T", l))
|
||||
}
|
||||
}
|
||||
|
||||
// Lambda2Saccharine converts a pure lambda calculus expression into its
|
||||
// Saccharine counterpart.
|
||||
func Lambda2Saccharine(l lambda.Expression) (saccharine.Expression, error) {
|
||||
return decodeExression(l), nil
|
||||
}
|
||||
|
||||
// Saccharine2Lambda desugars a saccharine expression into pure lambda calculus.
|
||||
func Saccharine2Lambda(s saccharine.Expression) (lambda.Expression, error) {
|
||||
return encodeExpression(s), nil
|
||||
}
|
||||
|
||||
6
pkg/deltanet/deltanet.go
Normal file
6
pkg/deltanet/deltanet.go
Normal file
@@ -0,0 +1,6 @@
|
||||
// Package "deltanet" is a reduction strategy using ∆-nets.
|
||||
package deltanet
|
||||
|
||||
type Graph struct {
|
||||
Nodes []Node
|
||||
}
|
||||
80
pkg/deltanet/node.go
Normal file
80
pkg/deltanet/node.go
Normal file
@@ -0,0 +1,80 @@
|
||||
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{} }
|
||||
54
pkg/emitter/emitter.go
Normal file
54
pkg/emitter/emitter.go
Normal file
@@ -0,0 +1,54 @@
|
||||
package emitter
|
||||
|
||||
import "git.maximhutz.com/max/lambda/pkg/set"
|
||||
|
||||
type Observer struct {
|
||||
fn func()
|
||||
message string
|
||||
emitter *Emitter
|
||||
}
|
||||
|
||||
type Emitter struct {
|
||||
listeners map[string]*set.Set[*Observer]
|
||||
}
|
||||
|
||||
func Ignore[T any](fn func()) func(T) {
|
||||
return func(T) { fn() }
|
||||
}
|
||||
|
||||
func (e *Emitter) On(message string, fn func()) *Observer {
|
||||
observer := &Observer{
|
||||
fn: fn,
|
||||
message: message,
|
||||
emitter: e,
|
||||
}
|
||||
|
||||
if e.listeners == nil {
|
||||
e.listeners = map[string]*set.Set[*Observer]{}
|
||||
}
|
||||
|
||||
if e.listeners[message] == nil {
|
||||
e.listeners[message] = set.New[*Observer]()
|
||||
}
|
||||
|
||||
e.listeners[message].Add(observer)
|
||||
return observer
|
||||
}
|
||||
|
||||
func (o *Observer) Off() {
|
||||
if o.emitter.listeners[o.message] == nil {
|
||||
return
|
||||
}
|
||||
|
||||
o.emitter.listeners[o.message].Remove(o)
|
||||
}
|
||||
|
||||
func (e *Emitter) Emit(message string) {
|
||||
if e.listeners[message] == nil {
|
||||
return
|
||||
}
|
||||
|
||||
for listener := range *e.listeners[message] {
|
||||
listener.fn()
|
||||
}
|
||||
}
|
||||
@@ -1,18 +0,0 @@
|
||||
// Package engine defines a general process of reducing a lambda calculus
|
||||
// expression.
|
||||
package engine
|
||||
|
||||
// A Process handles the reduction of a single expression.
|
||||
type Process[T any] interface {
|
||||
// Get the current state of the process.
|
||||
// Returns an error if the current state cannot be represented.
|
||||
Get() (T, error)
|
||||
|
||||
// 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 Engine[T any] = func(T) (Process[T], error)
|
||||
@@ -1,42 +0,0 @@
|
||||
// Package normalorder contains an engine that reduces a 'lambda.Expression'
|
||||
// in the normal order.
|
||||
package normalorder
|
||||
|
||||
import (
|
||||
"git.maximhutz.com/max/lambda/pkg/engine"
|
||||
"git.maximhutz.com/max/lambda/pkg/lambda"
|
||||
)
|
||||
|
||||
type process struct {
|
||||
expr lambda.Expression
|
||||
}
|
||||
|
||||
func (e process) Get() (lambda.Expression, error) {
|
||||
return e.expr, nil
|
||||
}
|
||||
|
||||
func (e *process) Set(l lambda.Expression) error {
|
||||
e.expr = l
|
||||
return nil
|
||||
}
|
||||
|
||||
func (e *process) Step(i int) bool {
|
||||
for range i {
|
||||
next, reduced := ReduceOnce(e.expr)
|
||||
if !reduced {
|
||||
return false
|
||||
}
|
||||
|
||||
e.expr = next
|
||||
}
|
||||
|
||||
return true
|
||||
}
|
||||
|
||||
// NewProcess creates a new redution process.
|
||||
func NewProcess(expression lambda.Expression) (engine.Process[lambda.Expression], error) {
|
||||
return &process{expr: expression}, nil
|
||||
}
|
||||
|
||||
var _ engine.Process[lambda.Expression] = (*process)(nil)
|
||||
var _ engine.Engine[lambda.Expression] = NewProcess
|
||||
@@ -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
|
||||
}
|
||||
}
|
||||
35
pkg/fifo/fifo.go
Normal file
35
pkg/fifo/fifo.go
Normal file
@@ -0,0 +1,35 @@
|
||||
package fifo
|
||||
|
||||
import "fmt"
|
||||
|
||||
type FIFO[T any] []T
|
||||
|
||||
func New[T any](items ...T) *FIFO[T] {
|
||||
f := FIFO[T](items)
|
||||
return &f
|
||||
}
|
||||
|
||||
func (f *FIFO[T]) Push(item T) {
|
||||
*f = append(*f, item)
|
||||
}
|
||||
|
||||
func (f *FIFO[T]) Empty() bool {
|
||||
return len(*f) == 0
|
||||
}
|
||||
|
||||
func (f *FIFO[T]) MustPop() T {
|
||||
var item T
|
||||
|
||||
*f, item = (*f)[:len(*f)-1], (*f)[len(*f)-1]
|
||||
return item
|
||||
}
|
||||
|
||||
func (f *FIFO[T]) Pop() (T, error) {
|
||||
var item T
|
||||
|
||||
if f.Empty() {
|
||||
return item, fmt.Errorf("stack is exhausted")
|
||||
}
|
||||
|
||||
return f.MustPop(), nil
|
||||
}
|
||||
@@ -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()
|
||||
if err != nil {
|
||||
panic(fmt.Errorf("cannot get current token: %w", err))
|
||||
var null T
|
||||
if i.Done() {
|
||||
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
|
||||
// incremented.
|
||||
// Create a new iterator, over a set of items.
|
||||
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
|
||||
// the slice, this is a no-op.
|
||||
// Create a new iterator, over a set of items.
|
||||
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
|
||||
// predicate. The first item that does not match is left unconsumed.
|
||||
func (i *Iterator[T]) While(fn func(T) bool) {
|
||||
for !i.Done() {
|
||||
if !fn(i.MustGet()) {
|
||||
return
|
||||
}
|
||||
i.Forward()
|
||||
}
|
||||
}
|
||||
func Do[T any, U any](i *Iterator[T], fn func(i *Iterator[T]) (U, error)) (U, error) {
|
||||
i2 := i.Copy()
|
||||
|
||||
// Try attempts to perform an operation using the iterator. If the operation
|
||||
// succeeds, the iterator keeps its new position. If the operation fails, the
|
||||
// iterator is rolled back, and an error is returned.
|
||||
func Try[T any, U any](i *Iterator[T], fn func(i *Iterator[T]) (U, error)) (U, error) {
|
||||
saved := i.index
|
||||
|
||||
out, err := fn(i)
|
||||
if err != nil {
|
||||
i.index = saved
|
||||
out, err := fn(i2)
|
||||
if err == nil {
|
||||
i.Sync(i2)
|
||||
}
|
||||
|
||||
return out, err
|
||||
|
||||
@@ -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)
|
||||
62
pkg/lambda/expression.go
Normal file
62
pkg/lambda/expression.go
Normal file
@@ -0,0 +1,62 @@
|
||||
package lambda
|
||||
|
||||
type Expression interface {
|
||||
Accept(Visitor)
|
||||
Copy() Expression
|
||||
}
|
||||
|
||||
type Abstraction struct {
|
||||
Parameter string
|
||||
Body Expression
|
||||
}
|
||||
|
||||
func (a *Abstraction) Copy() Expression {
|
||||
return NewAbstraction(a.Parameter, a.Body.Copy())
|
||||
}
|
||||
|
||||
func (a *Abstraction) Accept(v Visitor) {
|
||||
v.VisitAbstraction(a)
|
||||
}
|
||||
|
||||
func NewAbstraction(parameter string, body Expression) *Abstraction {
|
||||
return &Abstraction{Parameter: parameter, Body: body}
|
||||
}
|
||||
|
||||
type Application struct {
|
||||
Abstraction Expression
|
||||
Argument Expression
|
||||
}
|
||||
|
||||
func (a *Application) Copy() Expression {
|
||||
return NewApplication(a.Abstraction.Copy(), a.Argument.Copy())
|
||||
}
|
||||
|
||||
func (a *Application) Accept(v Visitor) {
|
||||
v.VisitApplication(a)
|
||||
}
|
||||
|
||||
func NewApplication(function Expression, argument Expression) *Application {
|
||||
return &Application{Abstraction: function, Argument: argument}
|
||||
}
|
||||
|
||||
type Variable struct {
|
||||
Value string
|
||||
}
|
||||
|
||||
func (v *Variable) Copy() Expression {
|
||||
return NewVariable(v.Value)
|
||||
}
|
||||
|
||||
func (v *Variable) Accept(visitor Visitor) {
|
||||
visitor.VisitVariable(v)
|
||||
}
|
||||
|
||||
func NewVariable(name string) *Variable {
|
||||
return &Variable{Value: name}
|
||||
}
|
||||
|
||||
type Visitor interface {
|
||||
VisitAbstraction(*Abstraction)
|
||||
VisitApplication(*Application)
|
||||
VisitVariable(*Variable)
|
||||
}
|
||||
@@ -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))
|
||||
|
||||
|
||||
@@ -1,27 +1,20 @@
|
||||
package lambda
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
import "git.maximhutz.com/max/lambda/pkg/set"
|
||||
|
||||
"git.maximhutz.com/max/lambda/pkg/set"
|
||||
)
|
||||
|
||||
// GetFree returns the set of all free variable names in the expression.
|
||||
// This function does not mutate the input expression.
|
||||
// The returned set is newly allocated and can be modified by the caller.
|
||||
func GetFree(e Expression) set.Set[string] {
|
||||
func GetFreeVariables(e Expression) *set.Set[string] {
|
||||
switch e := e.(type) {
|
||||
case Variable:
|
||||
return set.New(e.Name)
|
||||
case Abstraction:
|
||||
vars := GetFree(e.Body)
|
||||
case *Variable:
|
||||
return set.New(e.Value)
|
||||
case *Abstraction:
|
||||
vars := GetFreeVariables(e.Body)
|
||||
vars.Remove(e.Parameter)
|
||||
return vars
|
||||
case Application:
|
||||
vars := GetFree(e.Abstraction)
|
||||
vars.Merge(GetFree(e.Argument))
|
||||
case *Application:
|
||||
vars := GetFreeVariables(e.Abstraction)
|
||||
vars.Merge(GetFreeVariables(e.Argument))
|
||||
return vars
|
||||
default:
|
||||
panic(fmt.Errorf("unknown expression type: %v", e))
|
||||
return nil
|
||||
}
|
||||
}
|
||||
|
||||
@@ -1,18 +1,14 @@
|
||||
package lambda
|
||||
|
||||
import "fmt"
|
||||
|
||||
// IsFree returns true if the variable name n occurs free in the expression.
|
||||
// This function does not mutate the input expression.
|
||||
func IsFree(e Expression, n string) bool {
|
||||
func IsFreeVariable(n string, e Expression) 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)
|
||||
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:
|
||||
panic(fmt.Errorf("unknown expression type: %v", e))
|
||||
return false
|
||||
}
|
||||
}
|
||||
|
||||
@@ -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() {}
|
||||
@@ -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
|
||||
}
|
||||
27
pkg/lambda/reduce.go
Normal file
27
pkg/lambda/reduce.go
Normal file
@@ -0,0 +1,27 @@
|
||||
package lambda
|
||||
|
||||
import "git.maximhutz.com/max/lambda/pkg/fifo"
|
||||
|
||||
func ReduceOnce(e *Expression) bool {
|
||||
stack := fifo.New(e)
|
||||
|
||||
for !stack.Empty() {
|
||||
top := stack.MustPop()
|
||||
|
||||
switch typed := (*top).(type) {
|
||||
case *Abstraction:
|
||||
stack.Push(&typed.Body)
|
||||
case *Application:
|
||||
if fn, fnOk := typed.Abstraction.(*Abstraction); fnOk {
|
||||
Substitute(&fn.Body, fn.Parameter, typed.Argument)
|
||||
*top = fn.Body
|
||||
return true
|
||||
}
|
||||
|
||||
stack.Push(&typed.Argument)
|
||||
stack.Push(&typed.Abstraction)
|
||||
}
|
||||
}
|
||||
|
||||
return false
|
||||
}
|
||||
@@ -1,31 +1,19 @@
|
||||
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 Rename(e Expression, target string, substitute string) {
|
||||
switch e := e.(type) {
|
||||
case Variable:
|
||||
if e.Name == target {
|
||||
return Variable{Name: newName}
|
||||
case *Variable:
|
||||
if e.Value == target {
|
||||
e.Value = substitute
|
||||
}
|
||||
|
||||
return e
|
||||
case Abstraction:
|
||||
newParam := e.Parameter
|
||||
case *Abstraction:
|
||||
if e.Parameter == target {
|
||||
newParam = newName
|
||||
e.Parameter = substitute
|
||||
}
|
||||
|
||||
newBody := Rename(e.Body, target, newName)
|
||||
|
||||
return Abstraction{Parameter: newParam, Body: newBody}
|
||||
case Application:
|
||||
newAbs := Rename(e.Abstraction, target, newName)
|
||||
newArg := Rename(e.Argument, target, newName)
|
||||
|
||||
return Application{Abstraction: newAbs, Argument: newArg}
|
||||
default:
|
||||
panic(fmt.Errorf("unknown expression type: %v", e))
|
||||
Rename(e.Body, target, substitute)
|
||||
case *Application:
|
||||
Rename(e.Abstraction, target, substitute)
|
||||
Rename(e.Argument, target, substitute)
|
||||
}
|
||||
}
|
||||
|
||||
@@ -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)
|
||||
}
|
||||
@@ -1,17 +1,32 @@
|
||||
package lambda
|
||||
|
||||
import "fmt"
|
||||
import "strings"
|
||||
|
||||
// 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))
|
||||
}
|
||||
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()
|
||||
}
|
||||
|
||||
@@ -1,41 +1,27 @@
|
||||
package lambda
|
||||
|
||||
import "fmt"
|
||||
|
||||
// Substitute replaces all free occurrences of the target variable with the
|
||||
// replacement expression. Alpha-renaming is performed automatically to
|
||||
// avoid variable capture.
|
||||
func Substitute(e Expression, target string, replacement Expression) Expression {
|
||||
switch e := e.(type) {
|
||||
case Variable:
|
||||
if e.Name == target {
|
||||
return replacement
|
||||
func Substitute(e *Expression, target string, replacement Expression) {
|
||||
switch typed := (*e).(type) {
|
||||
case *Variable:
|
||||
if typed.Value == target {
|
||||
*e = replacement.Copy()
|
||||
}
|
||||
case *Abstraction:
|
||||
if typed.Parameter == target {
|
||||
return
|
||||
}
|
||||
|
||||
return e
|
||||
case Abstraction:
|
||||
if e.Parameter == target {
|
||||
return e
|
||||
if IsFreeVariable(typed.Parameter, replacement) {
|
||||
replacementFreeVars := GetFreeVariables(replacement)
|
||||
used := GetFreeVariables(typed.Body)
|
||||
used.Merge(replacementFreeVars)
|
||||
freshVar := GenerateFreshName(used)
|
||||
Rename(typed, typed.Parameter, freshVar)
|
||||
}
|
||||
|
||||
body := e.Body
|
||||
param := e.Parameter
|
||||
if IsFree(replacement, param) {
|
||||
freeVars := GetFree(replacement)
|
||||
freeVars.Merge(GetFree(body))
|
||||
freshVar := GenerateFreshName(freeVars)
|
||||
body = Rename(body, param, freshVar)
|
||||
param = freshVar
|
||||
}
|
||||
|
||||
newBody := Substitute(body, target, replacement)
|
||||
return Abstraction{Parameter: param, Body: newBody}
|
||||
case Application:
|
||||
abs := Substitute(e.Abstraction, target, replacement)
|
||||
arg := Substitute(e.Argument, target, replacement)
|
||||
|
||||
return Application{Abstraction: abs, Argument: arg}
|
||||
default:
|
||||
panic(fmt.Errorf("unknown expression type: %v", e))
|
||||
Substitute(&typed.Body, target, replacement)
|
||||
case *Application:
|
||||
Substitute(&typed.Abstraction, target, replacement)
|
||||
Substitute(&typed.Argument, target, replacement)
|
||||
}
|
||||
}
|
||||
|
||||
@@ -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]
|
||||
@@ -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)
|
||||
45
pkg/saccharine/expression.go
Normal file
45
pkg/saccharine/expression.go
Normal file
@@ -0,0 +1,45 @@
|
||||
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}
|
||||
}
|
||||
@@ -5,89 +5,123 @@ import (
|
||||
"fmt"
|
||||
|
||||
"git.maximhutz.com/max/lambda/pkg/iterator"
|
||||
"git.maximhutz.com/max/lambda/pkg/token"
|
||||
"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 passSoftBreaks(i *tokenIterator) {
|
||||
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'", token.Name(expected), tok.Value)
|
||||
} else {
|
||||
return &tok, nil
|
||||
}
|
||||
})
|
||||
}
|
||||
|
||||
func passSoftBreaks(i *TokenIterator) {
|
||||
for {
|
||||
if _, err := token.ParseRawToken(i, TokenSoftBreak); err != nil {
|
||||
if _, err := parseRawToken(i, token.SoftBreak); err != nil {
|
||||
return
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
func parseToken(i *tokenIterator, expected TokenType, ignoreSoftBreaks bool) (*Token, error) {
|
||||
if ignoreSoftBreaks {
|
||||
passSoftBreaks(i)
|
||||
}
|
||||
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)
|
||||
}
|
||||
|
||||
return token.ParseRawToken(i, expected)
|
||||
return parseRawToken(i, expected)
|
||||
})
|
||||
}
|
||||
|
||||
func parseString(i *tokenIterator) (string, error) {
|
||||
if tok, err := parseToken(i, TokenAtom, true); err != nil {
|
||||
return "", fmt.Errorf("no variable (col %d): %w", i.Index(), err)
|
||||
func parseString(i *TokenIterator) (string, error) {
|
||||
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 := token.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 := token.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)
|
||||
}
|
||||
}
|
||||
|
||||
func parseAbstraction(i *tokenIterator) (*Abstraction, error) {
|
||||
if _, err := parseToken(i, TokenSlash, true); err != nil {
|
||||
return nil, fmt.Errorf("no function slash (col %d): %w", i.MustGet().Column, err)
|
||||
} else if parameters, err := token.ParseList(i, parseString, 0); err != nil {
|
||||
return nil, err
|
||||
} else if _, err = parseToken(i, TokenDot, true); err != nil {
|
||||
return nil, fmt.Errorf("no function dot (col %d): %w", i.MustGet().Column, err)
|
||||
} else if body, err := parseExpression(i); err != nil {
|
||||
return nil, err
|
||||
} else {
|
||||
return &Abstraction{Parameters: parameters, Body: body}, nil
|
||||
func 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 parseApplication(i *tokenIterator) (*Application, error) {
|
||||
if _, err := parseToken(i, TokenOpenParen, true); err != nil {
|
||||
return nil, fmt.Errorf("no openning brackets (col %d): %w", i.MustGet().Column, err)
|
||||
} else if expressions, err := token.ParseList(i, parseExpression, 1); err != nil {
|
||||
return nil, err
|
||||
} else if _, err := parseToken(i, TokenCloseParen, true); err != nil {
|
||||
return nil, fmt.Errorf("no closing brackets (col %d): %w", i.MustGet().Column, err)
|
||||
func parseAbstraction(i *TokenIterator) (*Abstraction, error) {
|
||||
return iterator.Do(i, func(i *TokenIterator) (*Abstraction, error) {
|
||||
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, 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
|
||||
} else {
|
||||
return NewAbstraction(parameters, body), nil
|
||||
}
|
||||
})
|
||||
}
|
||||
|
||||
func parseApplication(i *TokenIterator) (*Application, error) {
|
||||
return iterator.Do(i, func(i *TokenIterator) (*Application, error) {
|
||||
if _, err := parseToken(i, 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, 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
|
||||
}
|
||||
})
|
||||
}
|
||||
|
||||
func parseAtom(i *TokenIterator) (*Atom, error) {
|
||||
if tok, err := parseToken(i, token.Atom, true); err != nil {
|
||||
return nil, trace.Wrap(err, "no variable (col %d)", i.Index())
|
||||
} else {
|
||||
return &Application{Abstraction: expressions[0], Arguments: expressions[1:]}, nil
|
||||
return NewAtom(tok.Value), nil
|
||||
}
|
||||
}
|
||||
|
||||
func parseAtom(i *tokenIterator) (*Atom, error) {
|
||||
if tok, err := parseToken(i, TokenAtom, true); err != nil {
|
||||
return nil, fmt.Errorf("no variable (col %d): %w", i.Index(), err)
|
||||
} else {
|
||||
return &Atom{Name: tok.Value}, nil
|
||||
}
|
||||
}
|
||||
|
||||
func parseStatements(i *tokenIterator) ([]Statement, error) {
|
||||
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,9 +131,9 @@ 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 {
|
||||
if _, err := parseToken(i, token.OpenBrace, true); err != nil {
|
||||
return nil, err
|
||||
}
|
||||
}
|
||||
@@ -118,59 +152,59 @@ 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
|
||||
}
|
||||
}
|
||||
|
||||
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) {
|
||||
passSoftBreaks(i)
|
||||
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)
|
||||
case TokenSlash:
|
||||
return parseAbstraction(i)
|
||||
case TokenAtom:
|
||||
return parseAtom(i)
|
||||
case TokenOpenBrace:
|
||||
return parseClause(i, true)
|
||||
default:
|
||||
return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
|
||||
}
|
||||
switch peek := i.MustGet(); peek.Type {
|
||||
case token.OpenParen:
|
||||
return parseApplication(i)
|
||||
case token.Slash:
|
||||
return parseAbstraction(i)
|
||||
case token.Atom:
|
||||
return parseAtom(i)
|
||||
case token.OpenBrace:
|
||||
return parseClause(i, true)
|
||||
default:
|
||||
return nil, fmt.Errorf("expected expression, got '%v' (col %d)", peek.Value, peek.Column)
|
||||
}
|
||||
})
|
||||
}
|
||||
|
||||
func parseLet(i *tokenIterator) (*LetStatement, error) {
|
||||
if parameters, err := token.ParseList(i, parseString, 1); err != nil {
|
||||
return nil, err
|
||||
} else if _, err := parseToken(i, TokenAssign, true); err != nil {
|
||||
return nil, err
|
||||
} else if body, err := parseExpression(i); err != nil {
|
||||
return nil, err
|
||||
} else {
|
||||
return &LetStatement{Name: parameters[0], Parameters: parameters[1:], Body: body}, nil
|
||||
}
|
||||
func 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, token.Assign, true); err != nil {
|
||||
return nil, err
|
||||
} else if body, err := parseExpression(i); err != nil {
|
||||
return nil, err
|
||||
} else {
|
||||
return NewLet(parameters[0], parameters[1:], body), nil
|
||||
}
|
||||
})
|
||||
}
|
||||
|
||||
func parseDeclare(i *tokenIterator) (*DeclareStatement, error) {
|
||||
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) {
|
||||
if let, letErr := iterator.Try(i, parseLet); letErr == nil {
|
||||
func parseStatement(i *TokenIterator) (Statement, error) {
|
||||
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)
|
||||
@@ -178,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)
|
||||
|
||||
@@ -1,60 +1,22 @@
|
||||
// Package saccharine defines the AST for the Saccharine language, a sugared
|
||||
// lambda calculus with let bindings and multi-statement clauses.
|
||||
// Package "saccharine" provides a simple language built on top of λ-calculus,
|
||||
// to facilitate productive coding using it.
|
||||
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()
|
||||
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)
|
||||
}
|
||||
|
||||
// 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
|
||||
// Convert a parsed saccharine expression back into source code.
|
||||
func Stringify(expression Expression) string {
|
||||
return stringifyExpression(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() {}
|
||||
|
||||
@@ -1,24 +0,0 @@
|
||||
package saccharine
|
||||
|
||||
import "git.maximhutz.com/max/lambda/pkg/token"
|
||||
|
||||
// scanner is the declarative lexer for the Saccharine language.
|
||||
var scanner = token.NewScanner(
|
||||
token.On(`:=`, TokenAssign, 1),
|
||||
token.On(`\(`, TokenOpenParen, 0),
|
||||
token.On(`\)`, TokenCloseParen, 0),
|
||||
token.On(`\{`, TokenOpenBrace, 0),
|
||||
token.On(`\}`, TokenCloseBrace, 0),
|
||||
token.On(`;`, TokenHardBreak, 0),
|
||||
token.On(`\n`, TokenSoftBreak, 0),
|
||||
token.On(`\\`, TokenSlash, 0),
|
||||
token.On(`\.`, TokenDot, 0),
|
||||
token.On(`[a-zA-Z0-9_]+`, TokenAtom, 0),
|
||||
token.Skip[TokenType](`#[^\n]*`, 0),
|
||||
token.Skip[TokenType](`[^\S\n]+`, 0),
|
||||
)
|
||||
|
||||
// scan tokenizes a string into Saccharine tokens.
|
||||
func scan(input string) ([]Token, error) {
|
||||
return scanner.Scan(input)
|
||||
}
|
||||
26
pkg/saccharine/statement.go
Normal file
26
pkg/saccharine/statement.go
Normal file
@@ -0,0 +1,26 @@
|
||||
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}
|
||||
}
|
||||
@@ -1,65 +0,0 @@
|
||||
package saccharine
|
||||
|
||||
import (
|
||||
"fmt"
|
||||
|
||||
"git.maximhutz.com/max/lambda/pkg/token"
|
||||
)
|
||||
|
||||
// A TokenType is an identifier for any token in the Saccharine language.
|
||||
type TokenType int
|
||||
|
||||
// All official tokens of the Saccharine language.
|
||||
const (
|
||||
// TokenOpenParen denotes the '(' token.
|
||||
TokenOpenParen TokenType = iota
|
||||
// TokenCloseParen denotes the ')' token.
|
||||
TokenCloseParen
|
||||
// TokenOpenBrace denotes the '{' token.
|
||||
TokenOpenBrace
|
||||
// TokenCloseBrace denotes the '}' token.
|
||||
TokenCloseBrace
|
||||
// TokenHardBreak denotes the ';' token.
|
||||
TokenHardBreak
|
||||
// TokenAssign denotes the ':=' token.
|
||||
TokenAssign
|
||||
// TokenAtom denotes an alpha-numeric variable.
|
||||
TokenAtom
|
||||
// TokenSlash denotes the '\\' token.
|
||||
TokenSlash
|
||||
// TokenDot denotes the '.' token.
|
||||
TokenDot
|
||||
// TokenSoftBreak denotes a new-line.
|
||||
TokenSoftBreak
|
||||
)
|
||||
|
||||
// Name returns the type of the TokenType, as a string.
|
||||
func (t TokenType) Name() string {
|
||||
switch t {
|
||||
case TokenOpenParen:
|
||||
return "("
|
||||
case TokenCloseParen:
|
||||
return ")"
|
||||
case TokenOpenBrace:
|
||||
return "{"
|
||||
case TokenCloseBrace:
|
||||
return "}"
|
||||
case TokenHardBreak:
|
||||
return ";"
|
||||
case TokenAssign:
|
||||
return ":="
|
||||
case TokenAtom:
|
||||
return "ATOM"
|
||||
case TokenSlash:
|
||||
return "\\"
|
||||
case TokenDot:
|
||||
return "."
|
||||
case TokenSoftBreak:
|
||||
return "\\n"
|
||||
default:
|
||||
panic(fmt.Errorf("unknown token type %v", t))
|
||||
}
|
||||
}
|
||||
|
||||
// Token is the concrete token type for the Saccharine language.
|
||||
type Token = token.Token[TokenType]
|
||||
115
pkg/saccharine/token/parse.go
Normal file
115
pkg/saccharine/token/parse.go
Normal file
@@ -0,0 +1,115 @@
|
||||
package token
|
||||
|
||||
import (
|
||||
"errors"
|
||||
"fmt"
|
||||
"unicode"
|
||||
|
||||
"git.maximhutz.com/max/lambda/pkg/iterator"
|
||||
"git.maximhutz.com/max/lambda/pkg/trace"
|
||||
)
|
||||
|
||||
// isVariables determines whether a rune can be a valid variable.
|
||||
func isVariable(r rune) bool {
|
||||
return unicode.IsLetter(r) || unicode.IsNumber(r)
|
||||
}
|
||||
|
||||
func parseRune(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 parseCharacter(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 getToken(i *iterator.Iterator[rune]) (*Token, error) {
|
||||
index := i.Index()
|
||||
|
||||
if i.Done() {
|
||||
return nil, nil
|
||||
}
|
||||
|
||||
letter, err := i.Next()
|
||||
if err != nil {
|
||||
return nil, trace.Wrap(err, "cannot produce next token")
|
||||
}
|
||||
|
||||
switch {
|
||||
case letter == '(':
|
||||
return NewOpenParen(index), nil
|
||||
case letter == ')':
|
||||
return NewCloseParen(index), nil
|
||||
case letter == '.':
|
||||
return NewDot(index), nil
|
||||
case letter == '\\':
|
||||
return NewSlash(index), nil
|
||||
case letter == '\n':
|
||||
return NewSoftBreak(index), nil
|
||||
case letter == '{':
|
||||
return NewOpenBrace(index), nil
|
||||
case letter == '}':
|
||||
return NewCloseBrace(index), nil
|
||||
case letter == ':':
|
||||
if _, err := parseCharacter(i, '='); err != nil {
|
||||
return nil, err
|
||||
} else {
|
||||
return NewAssign(index), nil
|
||||
}
|
||||
case letter == ';':
|
||||
return NewHardBreak(index), nil
|
||||
case unicode.IsSpace(letter):
|
||||
return nil, nil
|
||||
case isVariable(letter):
|
||||
atom := []rune{letter}
|
||||
|
||||
for {
|
||||
if r, err := parseRune(i, isVariable); err != nil {
|
||||
break
|
||||
} else {
|
||||
atom = append(atom, r)
|
||||
}
|
||||
}
|
||||
|
||||
return NewAtom(string(atom), index), nil
|
||||
}
|
||||
|
||||
return nil, fmt.Errorf("unknown character '%v'", string(letter))
|
||||
}
|
||||
|
||||
// Parse a string into tokens.
|
||||
func Parse(input string) ([]Token, error) {
|
||||
i := iterator.Of([]rune(input))
|
||||
tokens := []Token{}
|
||||
errorList := []error{}
|
||||
|
||||
for !i.Done() {
|
||||
token, err := getToken(i)
|
||||
if err != nil {
|
||||
errorList = append(errorList, err)
|
||||
} else if token != nil {
|
||||
tokens = append(tokens, *token)
|
||||
}
|
||||
}
|
||||
|
||||
return tokens, errors.Join(errorList...)
|
||||
}
|
||||
91
pkg/saccharine/token/token.go
Normal file
91
pkg/saccharine/token/token.go
Normal 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)
|
||||
}
|
||||
@@ -1,41 +1,29 @@
|
||||
// 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) {
|
||||
func (s *Set[T]) Add(items ...T) {
|
||||
for _, item := range items {
|
||||
s[item] = true
|
||||
(*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) {
|
||||
func (s *Set[T]) Remove(items ...T) {
|
||||
for _, item := range items {
|
||||
delete(s, item)
|
||||
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 {
|
||||
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,21 +34,8 @@ func (s Set[T]) ToList() []T {
|
||||
return list
|
||||
}
|
||||
|
||||
// Items returns a sequence of all items present in the set. The order of the
|
||||
// items is not guaranteed.
|
||||
func (s Set[T]) Items() iter.Seq[T] {
|
||||
return func(yield func(T) bool) {
|
||||
for item := range s {
|
||||
if !yield(item) {
|
||||
return
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// New creates a set of all items as argument.
|
||||
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,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)
|
||||
}
|
||||
}
|
||||
}
|
||||
@@ -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 + `)`)
|
||||
}
|
||||
@@ -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()
|
||||
}
|
||||
25
pkg/trace/trace.go
Normal file
25
pkg/trace/trace.go
Normal file
@@ -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)
|
||||
}
|
||||
@@ -1,8 +1,7 @@
|
||||
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 0)))))
|
||||
|
||||
(print (exp N N))
|
||||
(exp N N)
|
||||
16
samples/simple.txt
Normal file
16
samples/simple.txt
Normal file
@@ -0,0 +1,16 @@
|
||||
(\0.
|
||||
(\inc.
|
||||
(\add.
|
||||
(\mult.
|
||||
(\exp.
|
||||
(exp (inc (inc (inc (inc 0)))) (inc (inc (inc (inc (inc 0))))))
|
||||
\n m.(m n)
|
||||
)
|
||||
\m n f.(m (n f))
|
||||
)
|
||||
\n m.(m inc n)
|
||||
)
|
||||
\n f x.(f (n f x))
|
||||
)
|
||||
\f x.x
|
||||
)
|
||||
File diff suppressed because one or more lines are too long
@@ -1 +0,0 @@
|
||||
VALUE
|
||||
@@ -1,17 +0,0 @@
|
||||
# This is a full-line comment at the start
|
||||
# The following defines the identity function
|
||||
identity := \x.x # This is an end-of-line comment
|
||||
|
||||
# Define a simple function that applies a function twice
|
||||
twice := \f.\x.(f
|
||||
# Comments can be anywhere!
|
||||
(f x))
|
||||
|
||||
# Test that comments don't interfere with expressions
|
||||
result := (twice identity VALUE) # Should just return VALUE
|
||||
|
||||
# Multiple comments in a row
|
||||
# can appear anywhere
|
||||
# without breaking the code
|
||||
|
||||
result # Final comment at the end
|
||||
@@ -1 +0,0 @@
|
||||
(0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (1 END)))))))))))))))))))))))))))))))
|
||||
@@ -1 +0,0 @@
|
||||
(0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (0 (1 END)))))))))))))))))))))))))))))))
|
||||
@@ -1 +0,0 @@
|
||||
VALUE
|
||||
Reference in New Issue
Block a user