7 ms·

Functional C Programming: Higher order functions, closures, lifted types

106 points by cioc 14y ago

dkhenry 14y ago
When reading this title my default reaction was "Oh God Why" I am happy to see the author agrees with me. As an intelectual excersize I think this is great showing that yes C is very very flexable ( You can do the same stuff with C++ and it will look nicer BTW[0]) but please don't do this, Its messy and hard to trace. [0: http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/range/reference/adaptors/introduction.html http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/ran...
- ArchD 14y ago
  Yes, and very type-unsafe. You could do all this using C++ templates in a type-safe way.
ExpiredLink 14y ago
Of course, this skips negligible parts of C programming like memory management.
- ScottBurson 14y ago
  Oh, just throw the Boehm conservative collector on it and be done with it.
  - ExpiredLink 14y ago
    done with C, yep
wildranter 14y ago
1) imperative programming 2) functional programming 3) OOP 4) etc programming They're jus programming paradigms. Take what you need and get the job done. Anything else is just a buzzword.
- derleth 14y ago
  This little homily adds nothing. That's why it's getting downvoted. (It's also wrong, or over-simplified, in that all programming doesn't really fit into those little boxes.)
  - wildranter 14y ago
    Those little boxes are all boxes there are (except for prolog). BTW, downvotes are as meaningless as i--.
    - icebraining 14y ago
      Those little boxes are all boxes there are (except for prolog). No, they aren't, and a simple web search would've revealed others, such as Dataflow[1]. [1]: https://en.wikipedia.org/wiki/Dataflow_programming https://en.wikipedia.org/wiki/Dataflow_programming
shared4you 14y ago
Doing functional programming in C reminds me of Greenspun's tenth rule: Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp
- BadDesign 14y ago
  Great point! :-) I lol'd
deleted 14y ago
[deleted]
mappu 14y ago
Here's my variation on bind() - generating executable code on the heap allows you to treat the bound function as a raw ordinary function pointer; https://gist.github.com/3154939 https://gist.github.com/3154939
- cioc 14y ago
  I really like this.
- RodgerTheGreat 14y ago
  I've used a very similar trick for adding partial function application to Forth: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorithms/Curry.fs https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith... If I understand correctly, though, your implementation leaks memory. In my case I use a GC to free the thunks when they are no longer accessible.
  - mappu 14y ago
    Indeed, in typical C fashion all the created stubs must be freed manually. Adding a GC is a separate task and several exist for C. Though if you were using C++, you could put together some RAII sugar or smart pointers around it all, but in that case you have std::bind1st and functors available anyway (although this is still the only way to meet the raw-pointer use case).
- asveikau 14y ago
  There's also libffi, which I'm pretty sure also works by generating stub functions in executable pages, but has the advantage of having been ported to a bunch of platforms already, and hides the ugliness in a library.
GIFtheory 14y ago
... and I can wipe my ass with pine cones. Toilet paper is masturbatory nonsense for the weak of anus.
iskander 14y ago
I'm not really sure if this counts a functional programming in C but it does serve as a decent basis for teaching the implementation of functional languages on top of C. As always, the distinction between a library and a whole new language is never quite clear...
tantalor 14y ago
I wasn't sure what a "lifted type" was so I looked it up, A type is lifted iff it has bottom as an element. Closures always have lifted types: i.e. any let-bound identifier in Core must have a lifted type. Operationally, a lifted object is one that can be entered. Only lifted types may be unified with a type variable. http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/TypeType http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler...
- Snoptic 14y ago
  ... Which is an arcane way of saying "pointer / reference"; i.e., not a primitive or C-style struct.
martinced 14y ago
TFA says that was done answering an Haskell programmer. Probably that an Haskell programmer values strong static typing just as much as functional programming. I someone think that turning C from a weakly static type system to a strongly static one would prove quite more difficult... (but my C days are long gone so don't quote me on that).
jerf 14y ago
Actually, the "closure" pattern shows up in real code; for instance I saw it a lot in libpurple. It's one of those things that's hard to do any sort of large-scale engineering without. As long as you can get the memory management right on it, it's great. (And I wouldn't say that's any more particularly difficult than a number of other useful C patterns.)
- deleted 14y ago
  [deleted]
- andrewcooke 14y ago
  if anyone is curious - http://hg.pidgin.im/pidgin/main/file/eb0eb02fce71/libpurple/value.c http://hg.pidgin.im/pidgin/main/file/eb0eb02fce71/libpurple/... tbh that's the first time i've seen something quite like that. i am not sure this is so common a pattern (usually, imho, you can be more explicit and have a struct that associates a known callback type with named, typed values).
  - jerf 14y ago
    No, I wouldn't expect it is "common", but it definitely shows up. libpurple doesn't use it because it does its own thing, but glib has library support for it: http://developer.gnome.org/gobject/stable/chapter-signal.html#closure http://developer.gnome.org/gobject/stable/chapter-signal.htm... Although a straight-up Google search for "g_closure_invoke" is amusing. I did add the "as long as you can get the memory management right on it" for a reason... page after page after page of "segmentation fault in g_closure_invoke" stack traces....
    - asveikau 14y ago
      I'm not sure why "getting the memory management right" is the hard part, or why it's any more or less hard than general C programming practice. For example a closure object with a reference count that releases references on its contained objects when destroyed seems like a perfectly workable pattern. (I'd be surprised if that's not how the glib closures are supposed to work, knowing that glib like many general-purpose C libraries is pretty big on reference counting.) NSInvocation in objc comes to mind, where IIRC the closure-like object can hold a reference to its arguments, though it's been years since I've used that...
yarou 14y ago
I saw a similar post a few months ago. You can program functionally (not really) in C. There are certain theoretical assumptions that go along with it. But at its heart, C is still an imperative language. I'm not sure what the point is in making C good at doing things "functionally".
ilaksh 14y ago
This illustrates the fundamental problems of C very well, which are the requirements to be very specific about types and manually manage memory. Of course those things aren't a problem in cases where you need to do those things, but that isn't the case for most applications.
dschiptsov 14y ago
Why not to read the code of various advanced CL and Scheme implementations?) MIT Scheme and SCM and CMUCL are good candidates.)

106 points by cioc 14y ago

When reading this title my default reaction was "Oh God Why" I am happy to see the author agrees with me. As an intelectual excersize I think this is great showing that yes C is very very flexable ( You can do the same stuff with C++ and it will look nicer BTW[0]) but please don't do this, Its messy and hard to trace. [0: http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/range/reference/adaptors/introduction.html http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/ran...

ArchD 14y ago
Yes, and very type-unsafe. You could do all this using C++ templates in a type-safe way.

ExpiredLink 14y ago

Of course, this skips negligible parts of C programming like memory management.

ScottBurson 14y ago
Oh, just throw the Boehm conservative collector on it and be done with it.
- ExpiredLink 14y ago
  done with C, yep

wildranter 14y ago

1) imperative programming 2) functional programming 3) OOP 4) etc programming They're jus programming paradigms. Take what you need and get the job done. Anything else is just a buzzword.

derleth 14y ago
This little homily adds nothing. That's why it's getting downvoted. (It's also wrong, or over-simplified, in that all programming doesn't really fit into those little boxes.)
- wildranter 14y ago
  Those little boxes are all boxes there are (except for prolog). BTW, downvotes are as meaningless as i--.
  - icebraining 14y ago
    Those little boxes are all boxes there are (except for prolog). No, they aren't, and a simple web search would've revealed others, such as Dataflow[1]. [1]: https://en.wikipedia.org/wiki/Dataflow_programming https://en.wikipedia.org/wiki/Dataflow_programming

shared4you 14y ago

Doing functional programming in C reminds me of Greenspun's tenth rule: Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp

BadDesign 14y ago
Great point! :-) I lol'd

deleted 14y ago

[deleted]

mappu 14y ago

Here's my variation on bind() - generating executable code on the heap allows you to treat the bound function as a raw ordinary function pointer; https://gist.github.com/3154939 https://gist.github.com/3154939

cioc 14y ago
I really like this.
RodgerTheGreat 14y ago
I've used a very similar trick for adding partial function application to Forth: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorithms/Curry.fs https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith... If I understand correctly, though, your implementation leaks memory. In my case I use a GC to free the thunks when they are no longer accessible.
- mappu 14y ago
  Indeed, in typical C fashion all the created stubs must be freed manually. Adding a GC is a separate task and several exist for C. Though if you were using C++, you could put together some RAII sugar or smart pointers around it all, but in that case you have std::bind1st and functors available anyway (although this is still the only way to meet the raw-pointer use case).
asveikau 14y ago
There's also libffi, which I'm pretty sure also works by generating stub functions in executable pages, but has the advantage of having been ported to a bunch of platforms already, and hides the ugliness in a library.

GIFtheory 14y ago

... and I can wipe my ass with pine cones. Toilet paper is masturbatory nonsense for the weak of anus.

iskander 14y ago

I'm not really sure if this counts a functional programming in C but it does serve as a decent basis for teaching the implementation of functional languages on top of C. As always, the distinction between a library and a whole new language is never quite clear...

tantalor 14y ago

I wasn't sure what a "lifted type" was so I looked it up, A type is lifted iff it has bottom as an element. Closures always have lifted types: i.e. any let-bound identifier in Core must have a lifted type. Operationally, a lifted object is one that can be entered. Only lifted types may be unified with a type variable. http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/TypeType http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler...

Snoptic 14y ago
... Which is an arcane way of saying "pointer / reference"; i.e., not a primitive or C-style struct.

martinced 14y ago

TFA says that was done answering an Haskell programmer. Probably that an Haskell programmer values strong static typing just as much as functional programming. I someone think that turning C from a weakly static type system to a strongly static one would prove quite more difficult... (but my C days are long gone so don't quote me on that).

jerf 14y ago

Actually, the "closure" pattern shows up in real code; for instance I saw it a lot in libpurple. It's one of those things that's hard to do any sort of large-scale engineering without. As long as you can get the memory management right on it, it's great. (And I wouldn't say that's any more particularly difficult than a number of other useful C patterns.)

deleted 14y ago
[deleted]
andrewcooke 14y ago
if anyone is curious - http://hg.pidgin.im/pidgin/main/file/eb0eb02fce71/libpurple/value.c http://hg.pidgin.im/pidgin/main/file/eb0eb02fce71/libpurple/... tbh that's the first time i've seen something quite like that. i am not sure this is so common a pattern (usually, imho, you can be more explicit and have a struct that associates a known callback type with named, typed values).
- jerf 14y ago
  No, I wouldn't expect it is "common", but it definitely shows up. libpurple doesn't use it because it does its own thing, but glib has library support for it: http://developer.gnome.org/gobject/stable/chapter-signal.html#closure http://developer.gnome.org/gobject/stable/chapter-signal.htm... Although a straight-up Google search for "g_closure_invoke" is amusing. I did add the "as long as you can get the memory management right on it" for a reason... page after page after page of "segmentation fault in g_closure_invoke" stack traces....
  - asveikau 14y ago
    I'm not sure why "getting the memory management right" is the hard part, or why it's any more or less hard than general C programming practice. For example a closure object with a reference count that releases references on its contained objects when destroyed seems like a perfectly workable pattern. (I'd be surprised if that's not how the glib closures are supposed to work, knowing that glib like many general-purpose C libraries is pretty big on reference counting.) NSInvocation in objc comes to mind, where IIRC the closure-like object can hold a reference to its arguments, though it's been years since I've used that...

yarou 14y ago

I saw a similar post a few months ago. You can program functionally (not really) in C. There are certain theoretical assumptions that go along with it. But at its heart, C is still an imperative language. I'm not sure what the point is in making C good at doing things "functionally".

ilaksh 14y ago

This illustrates the fundamental problems of C very well, which are the requirements to be very specific about types and manually manage memory. Of course those things aren't a problem in cases where you need to do those things, but that isn't the case for most applications.

dschiptsov 14y ago

Why not to read the code of various advanced CL and Scheme implementations?) MIT Scheme and SCM and CMUCL are good candidates.)