M.V. Hutz
9c7fb8ceba
## Description The codebase previously used "interpreter" terminology and standalone functions for expression operations. This PR modernizes the architecture by renaming to "runtime" and converting operations to receiver methods. - Rename `pkg/interpreter` to `pkg/runtime`. - Move `ReduceOnce` to new `pkg/normalorder` package for reduction strategy isolation. - Convert standalone functions (`Substitute`, `Rename`, `GetFree`, `IsFree`) to receiver methods on concrete expression types. - Change `Set` from pointer receivers to value receivers for simpler usage. - Update all references from "interpreter" to "runtime" terminology throughout the codebase. ### Decisions - Operations like `Substitute`, `Rename`, `GetFree`, and `IsFree` are now methods on the `Expression` interface, implemented by each concrete type (`Variable`, `Abstraction`, `Application`). - The `normalorder` package isolates the normal-order reduction strategy, allowing future reduction strategies to be added in separate packages. - `Set` uses value receivers since Go maps are reference types and don't require pointer semantics. ## Benefits - Cleaner API: `expr.Substitute(target, replacement)` instead of `Substitute(expr, target, replacement)`. - Better separation of concerns: reduction strategies are isolated from expression types. - Consistent terminology: "runtime" better reflects the execution model. - Simpler `Set` usage without needing to manage pointers. ## Checklist - [x] Code follows conventional commit format. - [x] Branch follows naming convention (`<type>/<description>`). Always use underscores. - [x] Tests pass (if applicable). - [x] Documentation updated (if applicable). Reviewed-on: #39 Co-authored-by: M.V. Hutz <git@maximhutz.me> Co-committed-by: M.V. Hutz <git@maximhutz.me>
109 lines
2.6 KiB
Go
109 lines
2.6 KiB
Go
package convert
|
|
|
|
import (
|
|
"fmt"
|
|
|
|
"git.maximhutz.com/max/lambda/pkg/lambda"
|
|
"git.maximhutz.com/max/lambda/pkg/saccharine"
|
|
)
|
|
|
|
func convertAtom(n *saccharine.Atom) lambda.Expression {
|
|
return lambda.NewVariable(n.Name)
|
|
}
|
|
|
|
func convertAbstraction(n *saccharine.Abstraction) lambda.Expression {
|
|
result := SaccharineToLambda(n.Body)
|
|
|
|
parameters := n.Parameters
|
|
|
|
// If the function has no parameters, it is a thunk. Lambda calculus still
|
|
// requires _some_ parameter exists, so generate one.
|
|
if len(parameters) == 0 {
|
|
freeVars := result.GetFree()
|
|
freshName := lambda.GenerateFreshName(freeVars)
|
|
parameters = append(parameters, freshName)
|
|
}
|
|
|
|
for i := len(parameters) - 1; i >= 0; i-- {
|
|
result = lambda.NewAbstraction(parameters[i], result)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func convertApplication(n *saccharine.Application) lambda.Expression {
|
|
result := SaccharineToLambda(n.Abstraction)
|
|
|
|
arguments := []lambda.Expression{}
|
|
for _, argument := range n.Arguments {
|
|
convertedArgument := SaccharineToLambda(argument)
|
|
arguments = append(arguments, convertedArgument)
|
|
}
|
|
|
|
for _, argument := range arguments {
|
|
result = lambda.NewApplication(result, argument)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func reduceLet(s *saccharine.LetStatement, e lambda.Expression) lambda.Expression {
|
|
var value lambda.Expression
|
|
|
|
if len(s.Parameters) == 0 {
|
|
value = SaccharineToLambda(s.Body)
|
|
} else {
|
|
value = convertAbstraction(saccharine.NewAbstraction(s.Parameters, s.Body))
|
|
}
|
|
|
|
return lambda.NewApplication(
|
|
lambda.NewAbstraction(s.Name, e),
|
|
value,
|
|
)
|
|
}
|
|
|
|
func reduceDeclare(s *saccharine.DeclareStatement, e lambda.Expression) lambda.Expression {
|
|
freshVar := lambda.GenerateFreshName(e.GetFree())
|
|
|
|
return lambda.NewApplication(
|
|
lambda.NewAbstraction(freshVar, e),
|
|
SaccharineToLambda(s.Value),
|
|
)
|
|
}
|
|
|
|
func reduceStatement(s saccharine.Statement, e lambda.Expression) lambda.Expression {
|
|
switch s := s.(type) {
|
|
case *saccharine.DeclareStatement:
|
|
return reduceDeclare(s, e)
|
|
case *saccharine.LetStatement:
|
|
return reduceLet(s, e)
|
|
default:
|
|
panic(fmt.Errorf("unknown statement type: %v", s))
|
|
}
|
|
}
|
|
|
|
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)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func SaccharineToLambda(n saccharine.Expression) lambda.Expression {
|
|
switch n := n.(type) {
|
|
case *saccharine.Atom:
|
|
return convertAtom(n)
|
|
case *saccharine.Abstraction:
|
|
return convertAbstraction(n)
|
|
case *saccharine.Application:
|
|
return convertApplication(n)
|
|
case *saccharine.Clause:
|
|
return convertClause(n)
|
|
default:
|
|
panic(fmt.Errorf("unknown expression type: %T", n))
|
|
}
|
|
}
|