How to test lambda-calculus?

user_15572466 0
Viewed 104

I implemented the lambda-calculus in C++, but now I don't know how to get out of it. I would like to test if my functions return the right thing, but I cant compare the result, since it is a funtion. Does anyone have an idea how I could test my code?

    #include <functional>
    
    class function :
            public std::function<function (function)> {
        public: using type =
                std::function<function (function)>;
        public: using type::function;
    };
    
    
    function True = [](function x) {
        return [&](function y) {
            return x;
        };
    };
    
    function False = [](function x) {
        return [&](function y) {
            return y;
        };
    };
    
    
    function If = [](function x) {
        return [&](function y) {
            return [&](function z) {
                return x(y)(z);
            };
        };
    };
    
    
    function And = [](function x) {
        return [&](function y) {
            return x(y)(x);
        };
    };
    
    function Or = [](function x) {
        return [&](function y) {
            return x(x)(y);
        };
    };
    
    // ...
    
    
    int main()
    {
        // ?
    }
lambda-calculus purely-functional function functional-programming c++
2 Answers

I solved my problem with the following test code.

#include <cassert>
#include <exception>

template <typename E, typename F>
bool throws(F f)
try {
    f();
    return false;
}
catch (E const &) {
    return true;
}


auto main() -> int
{
    function Null;
    assert(throws<std::bad_function_call>([&] { True(Null)(True)(True); }));
    assert(throws<std::bad_function_call>([&] { False(True)(Null)(True); }));
}

The test for False worked, but the test for True didn't. The first assert did not pass and I don't know why. When I capture x by value instead of by reference ([&] -> [=]) everything works.

New code for True:

function True = [](function x) {
    return [=](function y) {
        return x;
    };
};

Does anyone know why it doesn't work if I capture by reference?

user_155724660

My code looks now like this (I just replaced all [&] by [=] and used private inheritance):

class function :
        private std::function<function (function)> {
    public: using type =
            std::function<function (function)>;
    public: using type::function;
    public: using type::operator();
    public: using type::operator bool;
};


function True = [](function t) {
    return [=](function f) {
        return t;
    };
};

function False = [](function t) {
    return [=](function f) {
        return f;
    };
};


function If = [](function x) {
    return [=](function t) {
        return [=](function f) {
            return x(t)(f);
        };
    };
};


function And = [](function x) {
    return [=](function y) {
        return x(y)(x);
    };
};

function Or = [](function x) {
    return [=](function y) {
        return x(x)(y);
    };
};

And the tests look like this:

auto main() -> int
{
    function Null;

    assert( True(True)(Null));
    assert(!True(Null)(True));

    assert( False(Null)(True));
    assert(!False(True)(Null));

    assert( If(True )(True)(Null));
    assert(!If(True )(Null)(True));
    assert( If(False)(Null)(True));
    assert(!If(False)(True)(Null));

    assert(And(False)(False) (Null)(True));
    assert(And(False)(True ) (Null)(True));
    assert(And(True )(False) (Null)(True));
    assert(And(True )(True ) (True)(Null));

    assert(Or(False)(False) (Null)(True));
    assert(Or(False)(True ) (True)(Null));
    assert(Or(True )(False) (True)(Null));
    assert(Or(True )(True ) (True)(Null));
}
user_155724660
Related