title: lambda-calculus in C: Booleans and NOT operator
body: <p>I wanted to give implementations in different programming languages of the lambda-calculus construction of the booleans and the NOT operator.</p>
  
  <p>These are:</p>
  
  <pre><code>TRUE = lx.ly. x
  FALSE = lx.ly. y
  NOT = lx. x FALSE TRUE
  </code></pre>
  
  <p>It's trivial to do in Javascript and Python say, like</p>
  
  <pre><code>var TRUE = function(x,y){ return x;} 
  var FALSE = function(x,y){ return y;}
  var NOT = function(b){ return b(FALSE,TRUE) ; } 
  </code></pre>
  
  <p>but I can't figure out how to do it in C. </p>
  
  <p>The naive idea of implementing something like this</p>
  
  <pre><code>lambda true(lambda x, lambda y){ return x ; }
  lambda false(lambda x, lambda y){ return x ; }
  
  lambda not(lambda (b)(lambda, lambda) ){ return b(false,true) ;}
  </code></pre>
  
  <p>doesn't seem possible in C, as <code>typedef</code> doesn't allow a recursive definition</p>
  
  <pre><code>typedef void (*lambda)(lambda,lambda) ;not valid in C
  </code></pre>
  
  <p>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...</p>
  
  <p>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</p>
  
  <p>I may be expecting too much of C. </p>
  
  <p>EDIT:
  Following the suggestion by Tom in the comments, the following definitions do compile</p>
  
  <pre><code>typedef void *(*bol)() ;
  
  bol true(bol x, bol y){ return x ; }
  bol false(bol x, bol y){ return x ; }
  
  bol not(bol b ){ return b(false,true) ;}
  
  
  
  int main(){
   bol p = not((bol)true);
  
   return 0;
  }
  </code></pre>
  
  <p>EDIT2: This, however, is not strictly conforming as Tom and others have pointed out. </p>
  
  <p>Furthermore, as @Antti Haapala, and @n.m point out, this may be asking too much of C. </p>
  
  <p>At this point I'm skeptical that there could be a simple enough implementation in C++.</p>