A λ-calculus interpreter written in C preprocessor macros | Hacker News Reader

A λ-calculus interpreter written in C preprocessor macros

github.com

85 pointsHirrolot9 comments

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))))))

    #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#Delim...

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.

For the benefit of those like me who hadn't heard of Metalang99:

https://news.ycombinator.com/item?id=27919448

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.

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.

This was not sarcastic; I've explained in more detail in my blog post: 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.

> I’m a 17 y/o software engineer

Pretty cool! wonder what brought him to lambda calculus.

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.

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.

Reply on news.ycombinator.com