feat: add debruijn engine #26

New Issue

mvhutz · 2026-01-13T02:18:50Z

mvhutz commented

2026-01-13 02:18:50 +00:00

Context

The lambda calculus reduction engine is limited by the IsFreeVariable() function. This is not a problem with De Bruijn indices, which do not require renaming.

Proposed Solution

Add a De Bruijn engine that the user can specify.

Acceptance Criteria

Research the De Bruijn indices, and understand how they work.
Add an additional flag -i in the config, which can either be lambda or debruijn. Any other option will return an error. By default, it should use lambda.
- This flag will identify the reduction strategy.
Update the program to switch the engine based on the interpreter flag.
Create a new debruijn package.
- This package will contain the Expression interface, which will define Variable, Abstraction, and Application much like the lambda package.
  - Variable will instead contain an integer index, and an string label.
  - Abstraction will only contain a body, no parameter.
  - Application will stay mostly the same.
- The package will minimally contain a Reducer engine, will mirror the function from lambda.
- The expression will also contain the String() function, to print the De Bruijn expressions.
Finally, the convert package should contain functions to convert to and from De Bruijn indices.
Use the test samples in the test/ directory to test the De Bruijn engine. All tests must pass in the end.
USE BEST CODING PRACTICES.

## Context The lambda calculus reduction engine is limited by the `IsFreeVariable()` function. This is not a problem with De Bruijn indices, which do not require renaming. ## Proposed Solution Add a De Bruijn engine that the user can specify. ## Acceptance Criteria - Research the De Bruijn indices, and understand how they work. - Add an additional flag `-i` in the config, which can either be `lambda` or `debruijn`. Any other option will return an error. By default, it should use `lambda`. - This flag will identify the reduction strategy. - Update the program to switch the engine based on the interpreter flag. - Create a new `debruijn` package. - This package will contain the `Expression` interface, which will define `Variable`, `Abstraction`, and `Application` much like the `lambda` package. - `Variable` will instead contain an integer index, and an string label. - `Abstraction` will only contain a body, no parameter. - `Application` will stay mostly the same. - The package will minimally contain a `Reducer` engine, will mirror the function from `lambda`. - The expression will also contain the `String()` function, to print the De Bruijn expressions. - Finally, the `convert` package should contain functions to convert to and from De Bruijn indices. - Use the test samples in the `test/` directory to test the De Bruijn engine. All tests must pass in the end. - USE BEST CODING PRACTICES.

mvhutz referenced this issue from a commit

2026-01-13 02:27:46 +00:00

feat: add De Bruijn index reduction engine

mvhutz referenced a pull request that will close this issue

2026-01-13 02:28:00 +00:00

feat: add De Bruijn index reduction engine #27

mvhutz referenced this issue from a commit

2026-01-17 00:36:20 +00:00

feat: add De Bruijn indexed reduction engine

mvhutz referenced a pull request that will close this issue

2026-01-17 00:36:29 +00:00

feat: add De Bruijn indexed reduction engine #33