last day (15 days later) » 

5:46 PM
4
Q: lambda-calculus in C: Booleans and NOT operator

MASLI 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){ ret...

 
So, you want to pass around functions? Use pointer to functions.
 
How exactly would you do it? That's what I tried with the typedef above. I don't see it being that easy. But maybe I'm just not seeing it...
 
Have you checked this: cprogramming.com/tutorial/function-pointers.html ? You may safely leave out the section on C++.
 
The way I see it, my problem lies in the fact that the return type of say TRUE, has to be the same as that of each of its arguments.
 
It sounds like you want to define a function type that takes that same type as an argument. Interesting, I don't think I've encountered that before. You could of course use an incomplete prototype, e.g. typedef void (*lambda)(); which would work, but it's not what you really want. (Usually I encounter this issue with self-referential structs, but that case has a simple solution.)
 
5:46 PM
@TomKarzes well, maybe I could settle for that incomplete type if it compiles/works, as that seems an easy way out, and simplicity here is a big bonus. EDIT: wait, that void I think breaks things, isn't? TRUE does return something...
 
Of course, the return type is void, so such a function would not be able to return anything. You could make it return a void * as a generic pointer type, which you could use to return function pointers. E.g. typedef void *(*lambda)(); Again, it's not ideal, but it works.
 
uhm...that leads me to incompatible pointer type warning at b(false,true)...I'll need to give it another try later
 
It shouldn't if you use () for the typedef and the actual arguments for the functions. Although strict ISO C doesn't like function pointers to be cast to void *.
 
Indeed! I didn't realize I had modified the code for not in a previous try. Thanks!
 
@TomKarzes You could write a proper answer...
 
5:46 PM
oops...It did compile with those definitions, but not when I call not(true)...
I failed to add, now it is lambda not(lambda b){ return b(false, true); }, and it's that b argument where the incompatible pointer problems arise...
 
Sorry, but I'm not sure what code you're running at this point. Did you change the return type from void to void *?
 
I just edited the question to include my test following your suggestion. Did I misunderstand you?
 
Ok I see the problem. A pointer to a function returning lambda is incompatible with a pointer to a function returning void *. You can circumvent the problem by casting the argument: r = not((lambda)true);
Alternatively, you could define all of the functions to return void * rather than lambda, detaching even further from the type system. And note that using void * for function pointers isn't strictly conforming.
 
First: awesome! it worked. Second: I'm fighting I cold here at the same time and I'm a bit slow, if you could explain to me that two pointers you mention and who's who, that would be much appreciated.
Good to know it's not strictly conforming. Not sure though there is any better solution as simple as this one. I think it's good at least for showcasing those lambda constructs with functions in an actual programming language.
 
Well, void * is a generic object pointer in C. It can "usually" hold a function pointer, but strictly speaking it's not guaranteed to be compatible. If you really wanted to be compliant, you could create a generic function pointer type and cast back and forth, e.g. void (*fptr)(void) would work. You could use a typedef for it and then use (fptr) in place of (void *) when dealing with function pointers.
 
5:46 PM
ah, but isn't that what I initially tried with the void (*lambda)()? So, you mean I could use this but I'd need to be more careful when passing it around and use casting to glue things properly together?
 
Go to chat, I'll reply there.
 
The last iteration is still not conforming (check with gcc -pedantic).
 
There are those things that are absolutely pointless. Demonstrating lambda calculus, which uses functions (and closures) as the only object type, in C, where the functions are not objects and closures do not exist is among those.
 
@AnttiHaapala Maybe...You might as well be reading too much into it: the point is to showcase the functional model of computation that lambda calculus constitutes: the concept of a function allows to define all what you need; no state variables required. And that with languages they may have seen before. Maybe there is no simple enough solution in C, then I'd totally agree with you.
 
It is easier to teach Python or JavaScript and show the concepts in them than to attempt to demonstrate the stuff in a language that can't do it. The functions in lambda calculus do not have state but they have bound variables that you cannot do in C.
 
5:46 PM
"the concept of a function allows to define all what you need" if you concept of "function" is powerful enough. C functions are not powerful enough.
 
Note: b(false,true) is actually undefined behavior and could lead to stack smashing issues because b is defined as void *(*bol)() which, in C, says that a function who has the same signature can take any number of arguments .. So you could define a function as such: int blah() { return 10; } and call it like so blah("this goes in", 231231, blah); and it will compile and run.
 
@txtechhelp there's no undefined behaviour simply because you can do something bad. You need to actually do that to invoke UB.
 
@n.m. this is true .. the safest, most bug free code I've seen is code that's never compiled and run ;) .. However, OP does invoke in bol p = not((bol)true); :(
 
@txtechhelp Posted code simply won't compile with a strictly conforming compiler. However if one assumes an extension that makes void* compatible with void(*)(), which is the case with most implementations, then the code is OK.
 
@AnttiHaapala I already have examples in Javascript (shown in my question), Python and Haskell
@n.m. That's part of my question. As I said, maybe I was asking too much from our old friend Mr. C. That said, as @Tom Karzes and you pointed out, the code shown is not strictly conforming, although in my case it compiles. It still leaves me with the problem of using it in any way that I could make the code show something like false == not(true).
 
6:27 PM
Sorry guys, I have profited from your generous contributions, but with the whole discussion moved to chat, I'm afraid all those good points of yours will be lost -how many really dig further to look into the chat discussions, especially when all comments have been removed!?
 

last day (15 days later) »