I wanted to give implementations in different programming languages of the lambda-calculus construction of the booleans and the NOT operator.
These are:
TRUE = lx.ly. x
FALSE = lx.ly. y
NOT = lx. x FALSE TRUE
It's trivial to do in Javascript and Python say, like
var TRUE = function(x,y){ return x;}
var FALSE = function(x,y){ return y;}
var NOT = function(b){ return b(FALSE,TRUE) ; }
but I can't figure out how to do it in C.
The naive idea of implementing something like this
lambda true(lambda x, lambda y){ return x ; }
lambda false(lambda x, lambda y){ return y ; }
lambda not(lambda (b)(lambda, lambda) ){ return b(false,true) ;}
doesn't seem possible in C, as typedef
doesn't allow a recursive definition
typedef void (*lambda)(lambda,lambda) ;not valid in C
Is there a way to do it in C? and is there a way to do it that is meaningful to use as an educational example? That is, if the syntax starts getting to cumbersome it ends up defeating its purpose...
Finally, if C ends up being too limited in any way, an answer in C++ would also work for me, albeit with the same "complexity" constraint
I may be expecting too much of C.
EDIT: Following the suggestion by Tom in the comments, the following definitions do compile
typedef void *(*bol)() ;
bol true(bol x, bol y){ return x ; }
bol false(bol x, bol y){ return y ; }
bol not(bol b ){ return b(false,true) ;}
int main(){
bol p = not((bol)true);
return 0;
}
EDIT2: This, however, is not strictly conforming as Tom and others have pointed out.
Furthermore, as @Antti Haapala, and @n.m point out, this may be asking too much of C.
At this point I'm skeptical that there could be a simple enough implementation in C++.
The only way I know in C to declare recursive declarations is by using struct, like this:
#include <stdio.h>
#include <stdarg.h>
typedef struct LAMBDA {
struct LAMBDA * (*function)(struct LAMBDA *, ...);
} *lambda;
lambda trueFunction(lambda x, ...) {return x;}
lambda true = &(struct LAMBDA) {.function = trueFunction};
lambda falseFunction(lambda x, ...) {va_list argp; va_start(argp, x); lambda y = va_arg(argp, lambda); va_end(argp); return y;}
lambda false = &(struct LAMBDA) {.function = falseFunction};
lambda notFunction(lambda b, ...) {return b->function(false, true);}
lambda not = &(struct LAMBDA) {.function = notFunction};
int main() {
lambda p1 = not->function(true);
lambda p2 = not->function(false);
printf("%p %p %p %p", true, p1, false, p2);
return 0;
}
Its hard for me to judge whether such syntax is too cumbersome or not, obviously less clear than dynamic languages.