Functions and functional programming.


B

Ben Bacarisse

<snip>

(GC = garbage collecton)
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!".

Some garbage collectors (many? most? all? I don't know) provide a way to
manually "free" a pointer's memory.

<snip>
 
Ad

Advertisements

A

August Karlstrom

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?

As you mention it cannot be enforced by the language. The programmer can
however adhere to the sound principle of "command query separation"
which states that a subroutine should be either

* a procedure which is invoked for its side effects only and which does
not return a result or

* a function which computes a result and has no side effects.

As far as I understand this principle is not too popular in the C
programming community.


-- August
 
J

James Kuyper

On 06/03/2014 02:48 PM, August Karlstrom wrote:
....
As you mention it cannot be enforced by the language. The programmer can
however adhere to the sound principle of "command query separation"
which states that a subroutine should be either

* a procedure which is invoked for its side effects only and which does
not return a result or ...

Many subroutines that have side-effects can fail. In the C standard
library, all such subroutines return values that can be tested to
determine whether or not they might have failed. How would a programmer
following the principle that you describe design such routines?

As far as I understand this principle is not too popular in the C
programming community.

I can imagine why.
 
P

Phil Carmody

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

"Better" is a judgement call, based on personal tastes,
rather than an absolute. I personally quite like that
anachronism, as it implies more strongly that it's a
call via a function pointer. (And AFAIK, I've never used
any archaic dialect of C where such a syntax was actually
necessary, so I've not been tainted by being forced to use
it, a la Stroustrup^H^H^H^H^H^H^H^Hockholm Syndrome.)

Phil
(Hi Ian!)
 
J

Jorgen Grahn

On 06/03/2014 02:48 PM, August Karlstrom wrote:
...

Many subroutines that have side-effects can fail. In the C standard
library, all such subroutines return values that can be tested to
determine whether or not they might have failed. How would a programmer
following the principle that you describe design such routines?

Googling suggests Bertrand Meyer coined the term "command query
separation", so maybe she's supposed to use Eiffel's exception
mechanism ...

/Jorgen
 
A

August Karlstrom

Many subroutines that have side-effects can fail. In the C standard
library, all such subroutines return values that can be tested to
determine whether or not they might have failed. How would a programmer
following the principle that you describe design such routines?

The programmer would add an output parameter to the parameter list which
indicates success or failure, for instance

void foo(int x, int *error);

which would be used as

int error;

foo(37, &error);
if (! error) {
/*do something*/
} else {
/*do something else*/
}


-- August
 
Ad

Advertisements

A

August Karlstrom

Googling suggests Bertrand Meyer coined the term "command query
separation", so maybe she's supposed to use Eiffel's exception
mechanism ...

Yes, the term was coined by Bertrand in the context of Eiffel and object
oriented programming but it is equally applicable to procedural programming.

-- August
 
R

Richard Bos

Some garbage collectors (many? most? all? I don't know) provide a way to
manually "free" a pointer's memory.

Yeah. But requiring you to _manually_ GC your memory, even (or perhaps I
should say, especially) only some times, does IMO constitute "fairly
unfriendly". The point about GC is that you should be able to forget
about it. If you can't, IMAO, 90% of the point of GC is lost.

Richard
 
J

James Kuyper

As you mention it cannot be enforced by the language. The programmer can
however adhere to the sound principle of "command query separation"
which states that a subroutine should be either

* a procedure which is invoked for its side effects only and which does
not return a result or

* a function which computes a result and has no side effects.


The programmer would add an output parameter to the parameter list which
indicates success or failure, for instance

void foo(int x, int *error);

which would be used as

int error;

foo(37, &error);
if (! error) {
/*do something*/
} else {
/*do something else*/
}

And what is the advantage that is achieved by doing this rather than
returning a value?
 
I

Ike Naar

Yeah. But requiring you to _manually_ GC your memory, even (or perhaps I
should say, especially) only some times, does IMO constitute "fairly
unfriendly". The point about GC is that you should be able to forget
about it. If you can't, IMAO, 90% of the point of GC is lost.

Setting

ptr = NIL;

in order to let the garbage collector free the memory pointed to by ptr
may be considered _manually_ GC-ing your memory as well.
 
R

Reinhardt Behm

Richard said:
Yeah. But requiring you to _manually_ GC your memory, even (or perhaps I
should say, especially) only some times, does IMO constitute "fairly
unfriendly". The point about GC is that you should be able to forget
about it. If you can't, IMAO, 90% of the point of GC is lost.

Richard

And this would add unpredictability to the program. The GC can step at any
inappropriate time, rendering real time behavior a total mess.
In real world applications there are more requirements than just computing
the correct results.
Even if no hard real time constraints have to be met having an application
"hang" at undefinable moments for unpredictable time is a at least annoying
for the user.
 
Ad

Advertisements

R

Richard Bos

August Karlstrom said:
The programmer would add an output parameter to the parameter list which
indicates success or failure, for instance

void foo(int x, int *error);

A rose by any other name would smell as sweet, but this one stinks of
horse manure.

Richard
 
M

Malcolm McLean

A rose by any other name would smell as sweet, but this one stinks of
horse manure.
In C you're not capturing anything special in the distinction between

void foo(int x, int *error);

and

int foo(int x)

That's not true in other languages which make it easy to return multiple results and don't
have pointers.
 
A

August Karlstrom

And what is the advantage that is achieved by doing this rather than
returning a value?

One advantage is that the emphasis is put on the program state changing
function rather than on the assignment of the return value. Another
advantage is that the error status cannot be completely ignored. A third
advantage is that the function return value (of which there is none)
cannot be used in an expression, which as mentioned by the original
poster can give rise to unexpected behavior.


-- August
 
A

August Karlstrom

In C you're not capturing anything special in the distinction between

void foo(int x, int *error);

and

int foo(int x)

That's not true in other languages which make it easy to return multiple results and don't
have pointers.

Regarding the error status the former function declaration is self
explaining whereas the latter is not.


-- August
 
J

James Kuyper

One advantage is that the emphasis is put on the program state changing
function rather than on the assignment of the return value. ...

That's a fairly subjective issue; and not one I'd consider important
enough to outweigh the substantially greater convenience of using the
return value, rather than a pointer argument.
... Another
advantage is that the error status cannot be completely ignored. ...

It seems to me to be perfectly feasible to drop the if-else statement
from the above code.
... A third
advantage is that the function return value (of which there is none)
cannot be used in an expression, which as mentioned by the original
poster can give rise to unexpected behavior.

I find the ability to use the return value in an expression to be one of
the advantages of that approach. This has been a fairly long thread, and
during a quick review backwards through the thread, I didn't recognize
any of the earlier messages in this thread as having demonstrated any
such problem. Could you identify more precisely the problem you're
talking about?
 
Ad

Advertisements

K

Kaz Kylheku

Regarding the error status the former function declaration is self
explaining whereas the latter is not.

Even if the declaration is clearer, declarations tend to be outnumbered
by uses. If the calls are clear, we don't have to look at declarations.
Uses not only have to be clear, but convenient.

Is the int *error version clearer from its declaration? Hardly.

- Is it okay for error to be null if I'm not interested in the error,
or must it always point to a valid location?

- Does foo always store a result in *error, or only if there is an error?
I.e. must I initialize foo to some value (say zero) and then test
for nonzero? Or can I leave it uninitialized and test it afterward?

nobody in their right mind would prefer this interface when the
function returns nothing.

Then there is the minor point that when you're developing foo, perhaps the
compiler has a useful diagnostic like "not all paths return a value"
or "return with no value in a fucntion returning int".

No compiler I know of will tell you "not all paths store a value into *error".
 
K

Kaz Kylheku

Yeah. But requiring you to _manually_ GC your memory, even (or perhaps I
should say, especially) only some times, does IMO constitute "fairly
unfriendly".

That workaround was inapplicable in the situation where I ran into
the error, ebcause I had no assurance that the variable in question
was the last reference to the object. Just that there were cases when
it in fact was, and the compiler optimized away the "var = nil"
dead assignment, leading to spurious retention.

The fix was not "gc_free(var)", but "gc_hint(&var)": a hint to the
compiler that the assignment is not dead, but visible to some
outside agency (the garbage collector).
The point about GC is that you should be able to forget
about it. If you can't, IMAO, 90% of the point of GC is lost.

Once you take the object lifetime computation into your own hands, you have the
responsibility to get it right. There are cases where it is obvious, so it
could be a useful optimization, but you don't want ot be sprinking unsafe
things throughout the code to compensate for what the C compiler is or isn't
doing.
 
K

Kaz Kylheku

Setting

ptr = NIL;

in order to let the garbage collector free the memory pointed to by ptr
may be considered _manually_ GC-ing your memory as well.

No, it may not, because if there are other copies of the object,
it is not reclaimed. The ptr = nil assignment is innocent; it doesn't
take on the full responsibility of computing the lifetime of the object;
it only contributes to that information.

Also, the C compiler may also cause spurious retention in cases like this:

{
var ptr = big_object();
}

computation();

here instead of ptr = nil, we ended the scope of ptr, so it doesn't exist.
(Is that also considered manual GC?)

But the C compiler may well leave a memory location on the stack which
still contains a pointer to big_object across computation.

In a garbage collected (by design, from the ground up) language, the garbage
collector has information from the compiler about where the live objects are;
it doesn't have to just scan every location in the stack conservatively. Or
else, if the collector does just scan the stack, the compiler generates code
which tidies up dead references.
 
Ad

Advertisements

K

Kaz Kylheku

And this would add unpredictability to the program. The GC can step at any
inappropriate time, rendering real time behavior a total mess.

This isn't much different from an interrupt. An interrupt can happen at any
time, adding hundreds of cycles to some operation that should take a
predictable number of microseconds. Solution: disable interrupts.
Or prioritize everything with real time threads.

The same thing can be applied to GC. GC can be momentarily disabled,
and prioritized.

There are techniques for real time GC also; don't implement naive full mark and
sweep, if there is a real time requirement.
In real world applications there are more requirements than just computing
the correct results.

There are scads of applications where this doesn't matter. Garbage collection
is everywhere.
Even if no hard real time constraints have to be met having an application
"hang" at undefinable moments for unpredictable time is a at least annoying
for the user.

All modern interactive applications and systems hang in this manner.
I can't remember the last time I used anything that didn't have variable
response time. Certain dedicated devices are responsive like that, for sure;
microwave ovens or alarm systems don't hang when you punch buttons.

If you want hard real time constraints, you don't do dynamic memory
allocation, period. The accurate computation of object lifetimes and their
disposal introduces unpredictable pauses, no matter how it is done.

Manual freeing is predictable? Hardly:

void free_tree(tree *tree)
{
if (tree == NULL)
return;

free_tree(tree->left);
free_tree(tree->right);
free_data(tree->data);
free(tree);
}

How long does this take? Depends on the size of the tree.
 

Similar threads

M
Replies
2
Views
262
Parth_Munjpara
P
X
Replies
3
Views
1K
James Kuyper
J
P
2 3
Replies
45
Views
2K
Seebs
S
M
Replies
6
Views
867
Nobody
N
R
Replies
6
Views
475
Tim Rentsch
T
F
2 3
Replies
52
Views
2K
Tim Rentsch
T
S
Replies
8
Views
873
Gerhard Fiedler
G
I
Replies
23
Views
1K
Ian Collins
I
Top