combinators.scm - A Small Combinator Calculus Evaluator

combinators.scm is a very small combinator calculus evaluator written in Scheme. To run it, you will need to have Chez Scheme installed on your machine.

Usage

Running an expression

$ ./combinators.scm "S K K 1"
=> 1

Running an expression and converting it to an integer

$ ./combinators.scm "SUCC ZERO" as number
=> 1

Supported Combinators

Here is a list of supported combinators. Please ensure that their names are CAPITALIZED in the expression.

1. S
2. K
3. I
4. Y
5. C1
6. C2
7. PAIR
8. ZERO
9. SUCC
10. ADD
11. MUL
12. FIRST
13. SECOND
14. M
15. I2
16. ONE
17. FAC

Additionally, users can use (TO-CHURCH <integer>) to get the church numeral representation of a number.

$ ./combinators.scm "ADD (SUCC ONE) (TO-CHURCH 1)" as number
=> 3

Known Issues

The church numeral to number conversion fails for some expressions due to type errors.

Acknowledgements

I primarily used this lecture’s slides for the definitions of the advanced combinators.

License

This program is licensed under GPL v3 or later. © 2023 Sarthak Shah (cel7t)