Functions and functional programming.

M

Malcolm McLean

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?
 
S

Stefan Ram

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

In which application of C is this a problem?
 
M

Malcolm McLean

In which application of C is this a problem?
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.
 
K

Kaz Kylheku

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;
}

This isn't really functional programming. Functions in functional programming
are capsules of code plus lexical environment, not simply pointers to code.
There's no way in C to guarantee that foo shall return the same value as bar,
which is awful.

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).
 
S

Stefan Ram

Malcolm McLean said:
When you're trying to support a functional programming
paradigm in C

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.
 
M

Malcolm McLean

C indeed supports functional programming, because many
implementations of functional languages are written in C!
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.
 
B

Ben Bacarisse

Malcolm McLean said:
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();

(Note that this is the better syntax for an indirect call -- the other
one comes from a version of C of purely archaeological interest).
return a + b;
}

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

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.
How's the best way to enforce this property?

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.
 
K

Kleuske

You can implement any language in any other.

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.
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.

Hmmm.... I'm not sure if that's true even theoretically.
That's what I mean by trying to support a functional
programming paradigm in C.

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.
 
B

Ben Bacarisse

Malcolm McLean said:
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.

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.
 
B

BartC

Stefan Ram said:
C indeed supports functional programming, because many
implementations of functional languages are written in C!

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...
 
M

Malcolm McLean

(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.
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.
 
B

Ben Bacarisse

Malcolm McLean said:
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.

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.
 
M

Malcolm McLean

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.
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?
 
K

Keith Thompson

Ben Bacarisse said:
(Note that this is the better syntax for an indirect call -- the other
one comes from a version of C of purely archaeological interest).

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 "()".
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.

Right, and C provides no way to state that a function, or a particular
call to a function, has no side effects.
 
S

Stefan Ram

Malcolm McLean said:
You can implement any language in any other.

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!
 
S

Stefan Ram

Ben Bacarisse said:
It's almost impossible without a full-blown interpreter.

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!
 
K

Kaz Kylheku

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!

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.
 
B

Ben Bacarisse

Malcolm McLean said:
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?

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.)
 
B

Ben Bacarisse

Keith Thompson said:
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.

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.
On the other hand, the fact that the compiler doesn't enforce the
distinction makes the convention less useful than it might otherwise
be.

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.)

Right, and C provides no way to state that a function, or a particular
call to a function, has no side effects.

A new use for restrict-qualified pointers, maybe?
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top