Skip to content

Instantly share code, notes, and snippets.

@Ferdi265
Created July 2, 2020 23:43
Show Gist options
  • Save Ferdi265/2226bea2cd2e5f40a5c0945d067219a7 to your computer and use it in GitHub Desktop.
Save Ferdi265/2226bea2cd2e5f40a5c0945d067219a7 to your computer and use it in GitHub Desktop.
Embedded Lambda Calculus in local C++ lambda expression templates
#include <type_traits>
#define LAMBDA(name, value) \
[](auto __t){ \
using name = std::remove_reference_t<decltype(__t)>; \
return value; \
}
#define TYPE_LAMBDA(name, ...) \
[](auto __t){ \
using name = std::remove_reference_t<decltype(__t)>; \
__VA_ARGS__ *__s = nullptr; \
return *__s; \
}
#define TYPEOF(...) decltype(__VA_ARGS__)
#define VALUEOF(...) std::declval<__VA_ARGS__>()
void wat() {
auto ident = TYPE_LAMBDA(A, A);
auto self_apply = TYPE_LAMBDA(F, TYPEOF(
VALUEOF(F)(VALUEOF(F))
));
auto delayed_self_apply = LAMBDA(F, TYPE_LAMBDA(X, TYPEOF(
VALUEOF(F)(VALUEOF(F))(VALUEOF(X))
)));
auto recursive_apply = LAMBDA(G, TYPE_LAMBDA(F, TYPEOF(
VALUEOF(G)(delayed_self_apply(VALUEOF(F)))
)));
auto y = TYPE_LAMBDA(G, TYPEOF(
self_apply(recursive_apply(VALUEOF(G)))
));
auto _true = LAMBDA(A, TYPE_LAMBDA(B, A));
auto _false = LAMBDA(A, TYPE_LAMBDA(B, B));
auto _not = TYPE_LAMBDA(A, TYPEOF(
VALUEOF(A)(_false)(_true)
));
auto pair = LAMBDA(A, LAMBDA(B, TYPE_LAMBDA(Sel, TYPEOF(
VALUEOF(Sel)(VALUEOF(A))(VALUEOF(B))
))));
auto _1st = TYPE_LAMBDA(P, TYPEOF(
VALUEOF(P)(_true)
));
auto _2nd = TYPE_LAMBDA(P, TYPEOF(
VALUEOF(P)(_false)
));
auto prepend = pair;
auto first = _1st;
auto rest = _2nd;
auto nil = _false;
auto empty_inner = LAMBDA(Head, LAMBDA(Tail, TYPE_LAMBDA(A, TYPEOF(
_false
))));
auto empty = TYPE_LAMBDA(List, TYPEOF(
VALUEOF(List)(empty_inner)(_true)
));
using list_of_integral_types = TYPEOF(
prepend(VALUEOF(char))(
prepend(VALUEOF(short))(
prepend(VALUEOF(int))(
prepend(VALUEOF(long))(
prepend(VALUEOF(long long))(
nil)))))
);
auto list_last_then = LAMBDA(List, TYPE_LAMBDA(X, TYPEOF(
first(VALUEOF(List))
)));
auto list_last_else = LAMBDA(ListLast, LAMBDA(List, TYPE_LAMBDA(X, TYPEOF(
VALUEOF(ListLast)(rest(VALUEOF(List)))
))));
auto list_last = y(LAMBDA(ListLast, TYPE_LAMBDA(List, TYPEOF(
empty(rest(VALUEOF(List)))
(list_last_then(VALUEOF(List)))
(list_last_else(VALUEOF(ListLast))(VALUEOF(List)))
(ident)
))));
using funny_long_long = TYPEOF(list_last(VALUEOF(list_of_integral_types)));
auto silly_pair = TYPE_LAMBDA(T,
struct {
T _1;
T _2;
}
);
using long_long_pair = TYPEOF(silly_pair(VALUEOF(funny_long_long)));
constexpr long_long_pair p{
42,
1337
};
static_assert(p._1 + p._2 == 1379);
}
int main() {
wat();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment