6 ms·

A λ-calculus interpreter written in C preprocessor macros

85 points by Hirrolot 5y ago

tromp 5y ago
Nice demonstration of preprocessor powers. Compiling this file (cd examples; cmake .; make) took just under half a minute. Adding an exponentiation test #define POW LAM(LAM(APPL(VAR(1), VAR(2)))) #define TWO_TO_THE_FOUR APPL(APPL(POW, TWO), FOUR) #define FOUR_SQUARED APPL(APPL(POW, FOUR), TWO) ASSERT_REDUCES_TO(TWO_TO_THE_FOUR, FOUR_SQUARED); nearly doubles the time. Adding some Pythagoras #define FIVE APPL(SUCC, FOUR) #define SQUARE LAM(APPL(APPL(MUL, VAR(1)), VAR(1))) ASSERT_REDUCES_TO(APPL(APPL(ADD, APPL(SQUARE, THREE)), APPL(SQUARE, FOUR)), APPL(SQUARE, FIVE)); bumps the time to 3 minutes. Currying works fine too; one can simplify the definitions #define IF LAM(LAM(LAM(APPL(APPL(VAR(3), VAR(2)), VAR(1))))) #define MUL LAM(LAM(LAM(LAM(APPL(APPL(VAR(4), APPL(VAR(3), VAR(2))), VAR(1)))))) to #define I LAM(VAR(1)) #define IF I #define MUL LAM(LAM(LAM(APPL(VAR(3), APPL(VAR(2), VAR(1)))))) I tried to see at what point things break; perhaps at this point #define SEVENTEEN APPL(SUCC, APPL(SQUARE, FOUR)) #define FOUR_CUBED APPL(APPL(POW, FOUR), THREE) #define THREE_TO_THE_FOUR APPL(APPL(POW, THREE), FOUR) ASSERT_REDUCES_TO(APPL(APPL(ADD, FOUR_CUBED), SEVENTEEN), THREE_TO_THE_FOUR); that yields an error: pasting formed ';_IMPL', an invalid preprocessing token I like the choice of False for Nil, which I also made in my Binary Lambda Calculus [1] [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Delimited_versus_undelimited https://tromp.github.io/cl/Binary_lambda_calculus.html#Delim...
- Hirrolot 5y ago
  Yeah, the macro-based lambda calculus is pretty slow, since it's essentially an interpreter upon interpreter upon interpreter! The first one is preprocessor, which executes Metalang99, which executes the final calculus.
  - lisper 5y ago
    For the benefit of those like me who hadn't heard of Metalang99: https://news.ycombinator.com/item?id=27919448 https://news.ycombinator.com/item?id=27919448
- ngcc_hk 5y ago
  If this is example, I am not sure I want to learn. Lisp whilst is a high learning curve at least it is not verbose by nature (many writing is but not the language). This is hard to follow. More examples needed.
etaioinshrdlu 5y ago
This is truly quite insane. I'd like to note that there seems to be much more to it than the one file linked here, it references other macros defined in other files. Also, the author says that you can use this "to drastically improve quality of your code -- make it safer, cleaner, and more maintainable." I hope this is somewhat sarcastic, because I doubt just about anyone else would like to find your code using this.
- Hirrolot 5y ago
  This was not sarcastic; I've explained in more detail in my blog post: https://hirrolot.github.io/posts/macros-on-steroids-or-how-can-pure-c-benefit-from-metaprogramming.html https://hirrolot.github.io/posts/macros-on-steroids-or-how-c.... The linked code uses other macros too, that's right, since it's written in a metalanguage atop of the standard preprocessor.
dleslie 5y ago
Ha, I suspected this would be Hirrolot. Take a look at their GH; it's fully of handy, and not-so-handy, C preprocessor hacks.
yodsanklai 5y ago
> I’m a 17 y/o software engineer Pretty cool! wonder what brought him to lambda calculus.
- Hirrolot 5y ago
  I learnt it from "Type Theory and Formal Proof" when I wanted to understand type theory (I was in a community of functional programmers). BTW, nice book, I always recommend it to absolute beginners.

85 points by Hirrolot 5y ago

Nice demonstration of preprocessor powers. Compiling this file (cd examples; cmake .; make) took just under half a minute. Adding an exponentiation test #define POW LAM(LAM(APPL(VAR(1), VAR(2)))) #define TWO_TO_THE_FOUR APPL(APPL(POW, TWO), FOUR) #define FOUR_SQUARED APPL(APPL(POW, FOUR), TWO) ASSERT_REDUCES_TO(TWO_TO_THE_FOUR, FOUR_SQUARED); nearly doubles the time. Adding some Pythagoras #define FIVE APPL(SUCC, FOUR) #define SQUARE LAM(APPL(APPL(MUL, VAR(1)), VAR(1))) ASSERT_REDUCES_TO(APPL(APPL(ADD, APPL(SQUARE, THREE)), APPL(SQUARE, FOUR)), APPL(SQUARE, FIVE)); bumps the time to 3 minutes. Currying works fine too; one can simplify the definitions #define IF LAM(LAM(LAM(APPL(APPL(VAR(3), VAR(2)), VAR(1))))) #define MUL LAM(LAM(LAM(LAM(APPL(APPL(VAR(4), APPL(VAR(3), VAR(2))), VAR(1)))))) to #define I LAM(VAR(1)) #define IF I #define MUL LAM(LAM(LAM(APPL(VAR(3), APPL(VAR(2), VAR(1)))))) I tried to see at what point things break; perhaps at this point #define SEVENTEEN APPL(SUCC, APPL(SQUARE, FOUR)) #define FOUR_CUBED APPL(APPL(POW, FOUR), THREE) #define THREE_TO_THE_FOUR APPL(APPL(POW, THREE), FOUR) ASSERT_REDUCES_TO(APPL(APPL(ADD, FOUR_CUBED), SEVENTEEN), THREE_TO_THE_FOUR); that yields an error: pasting formed ';_IMPL', an invalid preprocessing token I like the choice of False for Nil, which I also made in my Binary Lambda Calculus [1] [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Delimited_versus_undelimited https://tromp.github.io/cl/Binary_lambda_calculus.html#Delim...

Hirrolot 5y ago
Yeah, the macro-based lambda calculus is pretty slow, since it's essentially an interpreter upon interpreter upon interpreter! The first one is preprocessor, which executes Metalang99, which executes the final calculus.
- lisper 5y ago
  For the benefit of those like me who hadn't heard of Metalang99: https://news.ycombinator.com/item?id=27919448 https://news.ycombinator.com/item?id=27919448
ngcc_hk 5y ago
If this is example, I am not sure I want to learn. Lisp whilst is a high learning curve at least it is not verbose by nature (many writing is but not the language). This is hard to follow. More examples needed.

etaioinshrdlu 5y ago

This is truly quite insane. I'd like to note that there seems to be much more to it than the one file linked here, it references other macros defined in other files. Also, the author says that you can use this "to drastically improve quality of your code -- make it safer, cleaner, and more maintainable." I hope this is somewhat sarcastic, because I doubt just about anyone else would like to find your code using this.

Hirrolot 5y ago
This was not sarcastic; I've explained in more detail in my blog post: https://hirrolot.github.io/posts/macros-on-steroids-or-how-can-pure-c-benefit-from-metaprogramming.html https://hirrolot.github.io/posts/macros-on-steroids-or-how-c.... The linked code uses other macros too, that's right, since it's written in a metalanguage atop of the standard preprocessor.

dleslie 5y ago

Ha, I suspected this would be Hirrolot. Take a look at their GH; it's fully of handy, and not-so-handy, C preprocessor hacks.

yodsanklai 5y ago

> I’m a 17 y/o software engineer Pretty cool! wonder what brought him to lambda calculus.

Hirrolot 5y ago
I learnt it from "Type Theory and Formal Proof" when I wanted to understand type theory (I was in a community of functional programmers). BTW, nice book, I always recommend it to absolute beginners.