Functions and functional programming.

Discussion in 'C Programming' started by Malcolm McLean, Jun 2, 2014.

  1. Consider this.

    double foo( double (*callback_a)(), double (*callback_b)())
    {
    double a, b;

    a = (*callback_a)();
    b = (*callback_b)();

    return a + b;
    }

    double bar( double (*callback_a)(), double (*callback_b)())
    {
    double a, b;

    b = callback_b();
    a = callback_a();

    return a + b;
    }

    There's no way in C to guarantee that foo shall return the same value as bar, which is awful.

    How's the best way to enforce this property?
     
    Malcolm McLean, Jun 2, 2014
    #1
    1. Advertisements

  2. Malcolm McLean

    Stefan Ram Guest

    In which application of C is this a problem?
     
    Stefan Ram, Jun 2, 2014
    #2
    1. Advertisements

  3. When you're trying to support a functional programming paradigm in C, and so the callbacks
    no longer remain as fairly trivial bits of missing functionality (like the comparator to qsort()),
    but are passed to each other possibly multiple times, and the structure exists at another
    level than the call-tree.
     
    Malcolm McLean, Jun 2, 2014
    #3
  4. Malcolm McLean

    Kaz Kylheku Guest

    This isn't really functional programming. Functions in functional programming
    are capsules of code plus lexical environment, not simply pointers to code.
    Sure there is; don't have any side effects in the functions: an important
    attribute of functional programming.

    In functional languages, which banish most side effects, the evaluation order
    is even more loose than in C: not only can the constitutents of an expression
    be evaluated in multiple orders, the arguments of a function call do not have
    to be evaluated prior to that call taking place. An expression like f(g(x), y)
    can call f before g is called; f can call g. (And since g carries its lexical
    environment, x is properly resolved).
     
    Kaz Kylheku, Jun 2, 2014
    #4
  5. Malcolm McLean

    Stefan Ram Guest

    C indeed supports functional programming, because many
    implementations of functional languages are written in C!

    However, C is not a functional language itself. When
    someone expects C to be one, then I do not see this
    to be a problem with C.
     
    Stefan Ram, Jun 2, 2014
    #5
  6. You can implement any language in any other.
    You can also use most paradigms (state machines, structured programming,
    object-orientation, functional programming etc) in most languages, without
    actually building what s effectively an interpreter for another language.
    That's what I mean by trying to support a functional programming paradigm
    in C.
     
    Malcolm McLean, Jun 2, 2014
    #6
  7. (Note that this is the better syntax for an indirect call -- the other
    one comes from a version of C of purely archaeological interest).
    The same is true if the function calls are not indirect. I see no
    connection with callbacks. Why you call it awful, I don't know. It's
    how C does things with any function call.
    Ironically, the best solution is to do function programming (this isn't
    FP). In a purely function paradigm, the order of evaluation does not
    effect the value of the result (though it can be very significant in
    other ways).

    But you mean in C. I don't see how you can. Code order matters in C.
     
    Ben Bacarisse, Jun 2, 2014
    #7
  8. Malcolm McLean

    Kleuske Guest

    Probably true, theoretically. In practical terms it's probably not useful
    to implement C in BrainF*ck. The other way around, though, is not that
    difficult and may be a good exercise.
    Hmmm.... I'm not sure if that's true even theoretically.
    If that's your intent, it should show up more clearly in the code
    fragment you showed earlier. Depending on the functions provided, foo()
    and bar() could legitimately return anything.

    If you want constraints on that, using C, your should implement those
    constraints explicitly, or better, incorporate them in the basic design
    of your product.
     
    Kleuske, Jun 2, 2014
    #8
  9. It's almost impossible without a full-blown interpreter. C lacks the
    basic mechanisms to do the job. Take my posted fib list to see the
    scale of the problem.
     
    Ben Bacarisse, Jun 2, 2014
    #9
  10. Malcolm McLean

    BartC Guest

    By the same argument it also also supports keyword parameters, and
    practically any feature of any language that happens to be, or could be,
    implemented in C.

    And so does assembler...
     
    BartC, Jun 2, 2014
    #10
  11. If we are calling a and b directly, we know their properties. We know whether
    the order of calls matters or not. If we don't know the properties of a and b, it
    becomes difficult to ensure that foo() is correct, it's impossible to know if we will
    break it by replacing it with bar().
    So we can no longer "refactor" code.
     
    Malcolm McLean, Jun 2, 2014
    #11
  12. OK, then you are complaining about a normal property of arguments. You
    can't re-write a function without knowing what constraints, if any, may
    be assumed in regard to its arguments. If you know nothing at all about
    what may or may not be passed you have to assume the general case.
     
    Ben Bacarisse, Jun 2, 2014
    #12
  13. In C you can't actually check pointer arguments, but that's not true in most
    C-like languages, and it's usually pretty easy to say what the constraints
    on a pointer are, and usually if passed invalid arguments the function will
    crash or obviously fail.
    Other arguments are usually checkable within the function.

    But callback arguments?
     
    Malcolm McLean, Jun 2, 2014
    #13
  14. That's debatable. Both forms are valid in modern C, and one could argue
    that the explicit dereference, even though it's largely meaningless to
    the compiler, documents the fact that it's an indirect call.

    On the other hand, the fact that the compiler doesn't enforce the
    distinction makes the convention less useful than it might otherwise be.

    Also, the parameter declarations should use "(void)" rather than the
    obsolescent "()".
    Right, and C provides no way to state that a function, or a particular
    call to a function, has no side effects.
     
    Keith Thompson, Jun 2, 2014
    #14
  15. Malcolm McLean

    Stefan Ram Guest

    This is wrong, both from a theoretical POV and from
    a practical POV.

    In theory, you erroneously assumed that the concept of
    »language« implied Turing completeness. (I have posted
    references here recently.)

    In practice, people write LISP implementations in C,
    not C implementations in LISP. Yes, you could do the
    latter, but it's not done. And that's why I wrote:

    |C indeed supports functional programming, because many
    |implementations of functional languages are written in C!
     
    Stefan Ram, Jun 2, 2014
    #15
  16. Malcolm McLean

    Stefan Ram Guest

    One problem with functional programming in C is the lack of
    automatic dynamic memory management. In a functional
    language I can write,

    g( print( f( cons( 1, 2 ))))

    where »cons« creates a dotted pair

    ..---.---.
    | 1 | 2 |
    '---'---'

    . In C, however, I have to start thinking:
    »cons« uses malloc ... What if malloc, and thereby »cons«,
    returns 0, while »f« expects a dotted pair? And when and how
    exactly is the memory freed later? Above, it might be suited
    when some of the functions frees the pair, but what if such
    a function is being called in another context, where freeing
    its argument would not be appropriate, such as when it is
    being called with a dotted pair in automatic memory instead
    of dynamic memory at another place?

    Using C with a GC (there are GCs for C) might help in this
    regard. But then it's not C C anymore, but GC C!
     
    Stefan Ram, Jun 2, 2014
    #16
  17. Malcolm McLean

    Kaz Kylheku Guest

    I suspect that interpreted languages written C which are written in strictly
    conforming ISO C (or strictly conforming ISO C plus only library extensions)
    are few.

    Language projects use C as a high level assembly language.

    Their test cases are written in the language that is being processed, and if
    those pass on all supported platforms, nobody cares too much about undefined
    behavior in the underlying C. They have a working binary.

    As far as GC goes, C is fairly unfriendly toward garbage collectors,
    in sneaky ways---not just the obvious ways.

    Using your functional library for C (FCC?) suppose you do this:

    var = NIL; /* suitably defined NIL constant */

    your hope here is that the last reference to an object is held
    in var, and is being obliterated, so the object becomes garbage.

    Alas, the optimizing C compiler performs flow analysis and realizes, "hey,
    var has no next use at any node reachable from the assignment in
    the flow graph, in the flow graph; it is a dead assignment!".

    Poof, the assignment optimized away, no nowhere to be seen in the machine code.

    And so, you have a spurious retention bug: some memory or register still holds
    on to the object, preventing GC.

    The next line of code could be big_long_computation(); and so the object
    is held all across that.

    Perhaps volatile will solve the problem (but will you stick volatile
    everywhere? And there go useful optimizations!)

    Or, you can attack it on a case by case basis:

    variable = NIL; /* suitably defined NIL constant */
    dummy_external_function(&variable); /* does nothing */

    Properly, precisely implemented languages that have garbage collection have
    compilers which are aware of garbage collection.
     
    Kaz Kylheku, Jun 2, 2014
    #17
  18. No, in C all you know is the type (and that can changed with a cast).
    But this generality is also why the are so very useful (though less so
    in C due it's very understandable restrictions). With great power
    comes... careful coding.

    In portable code, int parameters have to be thought of as representing
    any value in a range of possible types (but always whole numbers). You
    need to take care with the code, but it's not that hard. If C had a
    "numeric" type it would would allow more abstract code to be written
    (summing ints, or floats or complex numbers, for example) but at the
    expense of having to be much more careful about the code, because you
    know less about the set of possible values. In C, function pointers are
    just about the most extreme example of this.

    Functional languages usually have very powerful type systems that permit
    much greater control over what functions can be passed and returned, but
    you can never get away from the fact that functions are more flexible
    than "smaller" data types. (Theoretically, when you introduce functions
    over some other type, you've introduced a power set with larger
    cardinality.)
     
    Ben Bacarisse, Jun 2, 2014
    #18
  19. That's true, but I find in practice that it's usually obvious from the
    name. Non-indirect functions will usually have rather specific names,
    but function pointers often have rather generic names (e.g.
    "add_numbers" vs. "binary_op"). This may be due to the kind of use I
    have typically made of them, but it feels like it might be a bit more
    general than that.
    The thing I don't like about is rather obsessive. The language (now)
    defines a call via a pointer -- a function designator decays to a
    pointer, so (*callback)() de-references a pointer only to have it be
    converted back. (I know this does not actually happen, and I know that
    it doesn't matter -- I did say it was rather obsessive.)

    A new use for restrict-qualified pointers, maybe?
     
    Ben Bacarisse, Jun 3, 2014
    #19
  20. Obviously what we need is a new meaning for "static". :cool:}
     
    Keith Thompson, Jun 3, 2014
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.