Function Wrapper: Opinions and Critique Desired

[I.M. !Knuth]

A while back, I was mucking around with a recursive function. For
brevity's sake, I'll define it like this:

int func_recurs(int arg1, int arg2, int prev_pos)
{
int crnt_pos = 0;
int result;

/* stuff happens to arg1, arg2, and crnt_pos */

func_recurs(arg1, arg2, (prev_pos + crnt_pos) );

return result;
}

The critical part here (as I'm sure you've figured out already) is that
prev_pos (the previous position) of the last recursion is combined with
crnt_pos (the current positon) of the present recursion and passed along
to become the prev_pos of the next recursion.

But written this way, I had to remember that any call to func_recurs()
always had to look like this:

func_recurs(arg1, arg2, 0);

Frankly, I thought that constant 0 dangling at the end was rather
inelegant. Then it struck me that maybe I could "hide" func_recurs
inside another function so that I wouldn't have to strain my brain
remembering about that pesky third argument; something like:

func_lazymemory(int arg1, int arg2)
{
func_recurs(arg1, arg2, 0);
}

Being new to C, I felt pretty clever for coming up with this all on my
own. But then I thought: "Bah! Smells of kludge. There must be a
better way."

So I changed it to:

int func_recurs(int arg1, int arg2)
{
-- static int prev_pos; /* conveniently init'd to 0 on 1st call */
int crnt_pos = 0;
int result;

/* stuff happens to arg1, arg2, and crnt_pos */

-- prev_pos += crnt_pos; /* adjust for next recursion */
-- func_recurs(arg1, arg2);
-- prev_pos -= crnt_pos; /* restore for current recursion */

return result;
}

Drawing your attention to the four "-->" lines, I then thought: "Boy is
that ugly", but I no longer felt I'd somehow cheated inside my code. I
packed away the function and forgot about it ... until tonight.

Tonight I was browsing through some months' old threads on clc and came
across one that discussed function wrappers. "Cool," I thought. A
response referenced the FAQ, so I pulled it up and had a read. So, my
clever idea is old hat. Figures! :-D

I started thinking again about how I dealt with that function and came
up with some questions and concerns:

1a) Is my use of a wrapper appropriate (or am I ignorant of some wrapper
rule or style convention)?

1b) Wouldn't the wrapper be improved (and the program conserve some
storage) if it were re-written to pass pointer values like this?

func_lazymemory(int *arg1, int *arg2)
{
func_recurs(arg1, arg2, 0);
}

2a) Is one of my solutions better/cleaner/preferable over the other?

2b) Or are they equivalent, and picking one is a matter of (my) personal
style?

3) Is there some other (maybe obvious) solution to ditching that third
argument that I've somehow overlooked?
Thanks for your attention.
--
I.M. (definitely) !Knuth

[Morris Dovey]

I.M. !Knuth (in Xn*********************@81.174.50.80) said:

| 3) Is there some other (maybe obvious) solution to ditching that
| third argument that I've somehow overlooked?

There is usually some other method (no matter what you're doing) :-)

I have two short pieces of recursive code that you might find
interesting:

http://www.iedu.com/mrd/c/getsm.c and
http://www.iedu.com/mrd/c/getsmx.c that deal with a similar situation.

The two are functionally equivalent; but the second module "cheats" in
that it uses a gcc extension to allow embedding one function
declaration inside another. It's non-standard but may have some value
as a thought-provoking device.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

[Barry Schwarz]

On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

>A while back, I was mucking around with a recursive function. For
brevity's sake, I'll define it like this:

int func_recurs(int arg1, int arg2, int prev_pos)
{
int crnt_pos = 0;
int result;

/* stuff happens to arg1, arg2, and crnt_pos */

func_recurs(arg1, arg2, (prev_pos + crnt_pos) );

return result;
}

The critical part here (as I'm sure you've figured out already) is that
prev_pos (the previous position) of the last recursion is combined with
crnt_pos (the current positon) of the present recursion and passed along
to become the prev_pos of the next recursion.

But written this way, I had to remember that any call to func_recurs()
always had to look like this:

func_recurs(arg1, arg2, 0);

Frankly, I thought that constant 0 dangling at the end was rather
inelegant. Then it struck me that maybe I could "hide" func_recurs
inside another function so that I wouldn't have to strain my brain
remembering about that pesky third argument; something like:

func_lazymemory(int arg1, int arg2)
{
func_recurs(arg1, arg2, 0);
}

Being new to C, I felt pretty clever for coming up with this all on my
own. But then I thought: "Bah! Smells of kludge. There must be a
better way."

So I changed it to:

int func_recurs(int arg1, int arg2)
{
-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.
Remove del for email

[Keith Thompson]

Barry Schwarz <sc******@doezl.netwrites:

On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

[...]

>>So I changed it to:

int func_recurs(int arg1, int arg2)
{
-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.

True -- but, by the as-if rule, an implementation conceivably *could*
delay the initialization until the first call. (Nothing outside the
function can see the variable before that and detect that it hasn't
been initialized. Local static variables can be seen via pointers
outside the function that defines them, but there's no way to
initialize such a pointer before calling the function.)

But I can't think of a good reason for an implementation to do such a
silly thing.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[I.M. !Knuth]

Morris Dovey <mr*****@iedu.comwrote:

<snip>

I have two short pieces of recursive code that you might find
interesting:

http://www.iedu.com/mrd/c/getsm.c and
http://www.iedu.com/mrd/c/getsmx.c that deal with a similar situation.

The two are functionally equivalent; but the second module "cheats" in
that it uses a gcc extension to allow embedding one function
declaration inside another. It's non-standard but may have some value
as a thought-provoking device.

My, what large comment blocks you have. :-D

I found a number of (even trivial) things thought-provoking. The
imbedded function (getsmx.c) is outright trippy; it would have taken me
a while just to find it without your comments marking its start and end,
and even more time to figure out was going on.

Where you comment like this:

#include <stdio.h /* fgetc() */

I've been commenting in the reverse:

fgetc(foo); /* <stdio.h*/

I haven't yet noodled much with structures, nor braved malloc at all, so
I'm a bit lost on how you entirely eliminated...

typedef struct {...} getstr; /* getsm.c */

....from getsmx.c. Though I can see where the structure's contents moved
to. I'll take another look after I get some sleep...

Why have some local variables been explicitly declared with automatic
storage duration?

Having an #ifdef encapsulated "in-line" test main() is frickin' cool. I'll
have to borrow this idea. ;-)

I note you use **argv as a parameter to main() instead of the conventional
*argv[]. I like that. The latter confused and frightened me when I was
first learning pointers. Even now, the former seems clearer to me.

I note also that you don't make use at all of argc. This made me laugh. I
recently finished a program that made extensive use of **argv, but I
couldn't find a use for argc. Everytime I re-compiled it I got the
message:

Warning: 'argc' initialized but never used.

....or some such. I contemplated putting in some dummy code just to make
the warning go away. Does gcc not spit out a similar warning?
Thank you most kindly for letting me peek inside your code.
--
I.M. (definitely) !Knuth

[I.M. !Knuth]

Barry Schwarz <sc******@doezl.netwrote:

On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

<snip>

>>-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.

D'oh! I knew that. Really, I did.
--
I.M. (definitely) !Knuth

[I.M. !Knuth]

Keith Thompson <ks***@mib.orgwrote:

Barry Schwarz <sc******@doezl.netwrites:

>On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

<snip>

>>>-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.

True -- but, by the as-if rule, an implementation conceivably *could*
delay the initialization until the first call. (Nothing outside the
function can see the variable before that and detect that it hasn't
been initialized. Local static variables can be seen via pointers
outside the function that defines them, but there's no way to
initialize such a pointer before calling the function.)

But I can't think of a good reason for an implementation to do such a
silly thing.

So, hypothetically, I only look dumb under some implementation-specific
circumstances. :-D

BTW, what's the "as-if rule"?
--
I.M. (definitely) !Knuth

[Keith Thompson]

"I.M. !Knuth" <no*******@yoyodyne.comwrites:

Keith Thompson <ks***@mib.orgwrote:

>Barry Schwarz <sc******@doezl.netwrites:

>>On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

<snip>

>>>>-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.

True -- but, by the as-if rule, an implementation conceivably *could*
delay the initialization until the first call. (Nothing outside the
function can see the variable before that and detect that it hasn't
been initialized. Local static variables can be seen via pointers
outside the function that defines them, but there's no way to
initialize such a pointer before calling the function.)

But I can't think of a good reason for an implementation to do such a
silly thing.

So, hypothetically, I only look dumb under some implementation-specific
circumstances. :-D

Um, sure. 8-)}

BTW, what's the "as-if rule"?

The general idea is that the standard describes the behavior of an
abstract machine, but the actual generated code is allowed to behave
differently as long as the result is *as if* it followed the semantics
described in the standard. It allows for optimizations such as
eliminating calculations whose results are never used.

C99 5.1.2.2.3p3:

In the abstract machine, all expressions are evaluated as
specified by the semantics. An actual implementation need not
evaluate part of an expression if it can deduce that its value is
not used and that no needed side effects are produced (including
any caused by calling a function or accessing a volatile object).

C99 5.1.2.2.3p5:

The least requirements on a conforming implementation are:

-- At sequence points, volatile objects are stable in the sense
that previous accesses are complete and subsequent accesses
have not yet occurred.

-- At program termination, all data written into files shall be
identical to the result that execution of the program according
to the abstract semantics would have produced.

-- The input and output dynamics of interactive devices shall take
place as specified in 7.19.3. The intent of these requirements
is that unbuffered or line-buffered output appear as soon as
possible, to ensure that prompting messages actually appear
prior to a program waiting for input.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[jaysome]

On Thu, 20 Jul 2006 06:29:49 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

>Keith Thompson <ks***@mib.orgwrote:

>Barry Schwarz <sc******@doezl.netwrites:

>>On Wed, 19 Jul 2006 06:33:14 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

<snip>

>>>>-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Just a nit. Static variables are initialized prior to your program
beginning execution and independent of your function.

True -- but, by the as-if rule, an implementation conceivably *could*
delay the initialization until the first call. (Nothing outside the
function can see the variable before that and detect that it hasn't
been initialized. Local static variables can be seen via pointers
outside the function that defines them, but there's no way to
initialize such a pointer before calling the function.)

But I can't think of a good reason for an implementation to do such a
silly thing.

So, hypothetically, I only look dumb under some implementation-specific
circumstances. :-D

BTW, what's the "as-if rule"?

The intention was to provide direction through example. The examples
were meant to be unambiguous. I think the committee achieved that for
the most part.

Best regards
--
jay

[Keith Thompson]

jaysome <ja*****@spamcop.netwrites:

On Thu, 20 Jul 2006 06:29:49 +0000 (UTC), "I.M. !Knuth"
<no*******@yoyodyne.comwrote:

[...]

>>BTW, what's the "as-if rule"?

The intention was to provide direction through example. The examples
were meant to be unambiguous. I think the committee achieved that for
the most part.

Um, what does that have to with the "as-if" rule?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Michael Wojcik]

In article <Xn*********************@81.174.50.80>, "I.M. !Knuth" <no*******@yoyodyne.comwrites:

A while back, I was mucking around with a recursive function. For
brevity's sake, I'll define it like this:

int func_recurs(int arg1, int arg2, int prev_pos)
...

But written this way, I had to remember that any call to func_recurs()
always had to look like this:

func_recurs(arg1, arg2, 0);

Frankly, I thought that constant 0 dangling at the end was rather
inelegant. Then it struck me that maybe I could "hide" func_recurs
inside another function so that I wouldn't have to strain my brain
remembering about that pesky third argument; something like:

func_lazymemory(int arg1, int arg2)
{
func_recurs(arg1, arg2, 0);
}

Being new to C, I felt pretty clever for coming up with this all on my
own. But then I thought: "Bah! Smells of kludge. There must be a
better way."

There are other ways, certainly. But this style - the recursive
function that includes parameters for current state, and a wrapper
that passes the initial state - is very common in functional
programming. You'll often find it in programs written in Lisp, SML,
and other functional languages.

So it's a common idiom. I wouldn't consider it a kluge at all.

One change I would make is to give func_recurs internal linkage (by
adding the "static" sc-specifier), since the public interface to this
operation is now func_lazymemory.

--
Michael Wojcik mi************@microfocus.com

I would never understand our engineer. But is there anything in this world
that *isn't* made out of words? -- Tawada Yoko (trans. Margaret Mitsutani)

[Morris Dovey]

My ISP is dropping over half of the clc postings. I took a quick look
through Google's archive to see what I've missed and found IM!Knuth's
reply with questions and comments. Sorry I'm so late responding.

| My, what large comment blocks you have. :-D

Deteriorating eyesight. They're easier for me to find if I draw a box
around 'em. :-)

| I haven't yet noodled much with structures, nor braved malloc at
all, so I'm
| a bit lost on how you entirely eliminated...
|
| typedef struct {...} getstr; /* getsm.c */
|
| ...from getsmx.c. Though I can see where the structure's contents
moved
| to. I'll take another look after I get some sleep...

The variables defined in the containing function are known in the
contained function.

| Why have some local variables been explicitly declared with
automatic
| storage duration?

Good question. In writing/reading recursive functions it's generally a
good idea to be aware of how much 'baggage' is being carried with each
recursion. It's really just there to call attention to the fact that
"here's some baggage".

| Having an #ifdef encapsulated "in-line" test main() is frickin'
cool. I'll
| have to borrow this idea. ;-)

Actually, it's laziness. It's a way for me to always have a unit test
module handy when I need one - without having to remember where I
saved it. It's also one more way for me to remind myself how I planned
to use/invoke the function when I wrote it. I have a really powerful
memory - but it's all short-term. :-)

| I note you use **argv as a parameter to main() instead of the
conventional
| *argv[]. I like that. The latter confused and frightened me when I
was
| first learning pointers. Even now, the former seems clearer to me.

It's one of those "six of one, half dozen of the other" kinds of
things. Probably an indicator that my wheels are in a rut.

| I note also that you don't make use at all of argc. This made me
laugh. I
| recently finished a program that made extensive use of **argv, but I
| couldn't find a use for argc. Everytime I re-compiled it I got the
| message:
|
| Warning: 'argc' initialized but never used.
|
| ...or some such. I contemplated putting in some dummy code just to
make
| the warning go away. Does gcc not spit out a similar warning?

I think so (no gcc on this machine) but you can pacify it by adding a
statement (which is probably discarded during compilation) something
like:

(void) argc;

| Thank you most kindly for letting me peek inside your code.

You're entirely welcome. Most of that stuff came out of discussions
here on clc and everything except 'snuf' is benign. The snuf program
is a Linux executable used to kill the first instance of a process by
name (rather than by PID number). It's handy for dealing with
non-terminating loops and similar "oops!" situations.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

[I.M. !Knuth]

Morris Dovey <mr*****@iedu.comwrote:

My ISP is dropping over half of the clc postings. I took a quick look
through Google's archive to see what I've missed and found IM!Knuth's
reply with questions and comments. Sorry I'm so late responding.

No apology necessary. As it happens, your predicament presents me with
an opportunity to repay your kindness. My ISP has good completion but
only 2 months retention. This has been annoying me greatly since I
started following clc. I tried backtracking on Google, but (because my
eyesight isn't worth writing home about either) enlarging the font size
just causes those annoying ads to get in the way; so I searched around
for a good free text server and found:

news.cambrium.nl /* may I plug open NNTP servers here? */

As of this post, it's got over 44,000 messages in clc dating back to mid
October of last year with -- as far as I can tell -- rock solid
completion. I've been reading off it for about a week now. Hope this
helps you out. ;-)

And now back to our program....

<snip>

>| ...I'm a bit lost on how you entirely eliminated...
|
| typedef struct {...} getstr; /* getsm.c */
|
| ...from getsmx.c. Though I can see where the structure's contents
| moved to. I'll take another look after I get some sleep...

The variables defined in the containing function are known in the
contained function.

Oh hey, I never noticed that ... and that isn't even the part that was
messing with me. :-D

>| Why have some local variables been explicitly declared with automatic
| storage duration?

Good question. In writing/reading recursive functions it's generally a
good idea to be aware of how much 'baggage' is being carried with each
recursion. It's really just there to call attention to the fact that
"here's some baggage".

Sound advice noted.

<snip>

Thanks again for broadening my horizons (even if ever so slightly).
--
I.M. (definitely) !Knuth

[I.M. !Knuth]

I.M. !Knuth <no*******@yoyodyne.comwrote:

<snip>

...so I searched around for a good free text server and found:

news.cambrium.nl /* may I plug open NNTP servers here? */

Oops! I should have added that it doens't allow posting.
--
I.M. (definitely) !Knuth

[I.M. !Knuth]

Michael Wojcik <mw*****@newsguy.comwrote:

<snip>

>...I thought: "Bah! Smells of kludge. There must be a better way."

There are other ways, certainly. But this style - the recursive
function that includes parameters for current state, and a wrapper
that passes the initial state - is very common in functional
programming. You'll often find it in programs written in Lisp, SML,
and other functional languages.

So it's a common idiom. I wouldn't consider it a kluge at all.

Cool. And reassuring. It felt like a kludge because it just seemed
*too* easy. :-)

One change I would make is to give func_recurs internal linkage (by
adding the "static" sc-specifier), since the public interface to this
operation is now func_lazymemory.

Now here you had me scratching my head (and searching the FAQ).

So if I read you correctly, your recommending that I define the
functions like this:

int func_lazymemory(int arg1, int arg2)
{ ... }

....and...

int func_recurs(static int arg1, static int arg2, int prev_pos)
{ ... }

....so that storage will only be allocated once for both arg1 and arg2.
Correct?

If so, this handily provides and alternate answer to question 1b from my
original post (which I just now noticed I bungled) where I was trying to
pass pointers to conserve storage:

/* Let the prototypes be: */

int func_lazymemory(int, int);
int func_recurs(int *, int *, int);
/* And the definition of func_lazymemory() be */

int func_lazy memory(int arg1, int arg2)
{
/* stuff happens, etc. */

func_recurs(&arg1, &arg1, 0);

return result;
}

Ultimately, this would have the same net effect, no?
--
I.M. (definitely) !Knuth

[I.M. !Knuth]

Morris Dovey <mr*****@iedu.comwrote:

>| I note also that you don't make use at all of argc. This made me
| laugh. I recently finished a program that made extensive use of
| **argv, but I couldn't find a use for argc. Everytime I re-compiled
| it I got the message:
|
| Warning: 'argc' initialized but never used.
|
| ...or some such. I contemplated putting in some dummy code just to
| make the warning go away. Does gcc not spit out a similar warning?

I think so (no gcc on this machine) but you can pacify it by adding a
statement (which is probably discarded during compilation) something
like:

(void) argc;

Just tried it, and yep, it does the trick. Casting to void never would
have occurred to me.

Thanks again.
--
I.M. (definitely) !Knuth

[Keith Thompson]

"I.M. !Knuth" <no*******@yoyodyne.comwrites:

Michael Wojcik <mw*****@newsguy.comwrote:

[...]

>One change I would make is to give func_recurs internal linkage (by
adding the "static" sc-specifier), since the public interface to this
operation is now func_lazymemory.

Now here you had me scratching my head (and searching the FAQ).

So if I read you correctly, your recommending that I define the
functions like this:

int func_lazymemory(int arg1, int arg2)
{ ... }

...and...

int func_recurs(static int arg1, static int arg2, int prev_pos)
{ ... }

...so that storage will only be allocated once for both arg1 and arg2.
Correct?

No, that's not even legal. He's suggesting that you make the
*functions* static, not their parameters.

int func_lazymemory(int arg1, int arg2)
{ ... }

static int func_recurs(int arg1, int arg2, int prev_pos)
{ ... }

The only effect of the "static" keyword here is that the function name
"func_recurs" is not visible outside the current translation unit.
(Making it more globally visible would probably be harmless, but it
clutters the namespace.) There's no effect on allocation.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[I.M. !Knuth]

Keith Thompson <ks***@mib.orgwrote:

<snip>

>Now here you had me scratching my head (and searching the FAQ).

So if I read you correctly, your recommending that I define the
functions like this:

int func_lazymemory(int arg1, int arg2)
{ ... }

...and...

int func_recurs(static int arg1, static int arg2, int prev_pos)
{ ... }

...so that storage will only be allocated once for both arg1 and arg2.
Correct?

No, that's not even legal. He's suggesting that you make the
*functions* static, not their parameters.

int func_lazymemory(int arg1, int arg2)
{ ... }

static int func_recurs(int arg1, int arg2, int prev_pos)
{ ... }

D'oh! <slaps forehead>

Thanks.

The only effect of the "static" keyword here is that the function name
"func_recurs" is not visible outside the current translation unit.
(Making it more globally visible would probably be harmless, but it
clutters the namespace.) There's no effect on allocation.

So this *does* come down to Q1.29 in the FAQ. I skimmed over the
namespace stuff to get to the "juicy bits" I thought pertained to me.
I'll reread it more slowly. I better flip open K&R too. I thought
"static" just kept a variable's storage alive within file scope. So by
"the current translation unit" you mean inside the function wrapper?

I'm so confused....
--
I.M. (definitely) !Knuth

[Richard Heathfield]

[much apparently random snippage, in an attempt to clarify exactly what I'm
answering and why]
I.M. !Knuth said:

Keith Thompson <ks***@mib.orgwrote:

<snip>

>>
[...] He's suggesting that you make the *functions* static, not their
parameters.

int func_lazymemory(int arg1, int arg2)
{ ... }

static int func_recurs(int arg1, int arg2, int prev_pos)
{ ... }

[...]

>The only effect of the "static" keyword here is that the function name
"func_recurs" is not visible outside the current translation unit. [...]

[...] I thought
"static" just kept a variable's storage alive within file scope. So by
"the current translation unit" you mean inside the function wrapper?

No.

Imagine a C source file. Got that? Just one. Now imagine that the C
preprocessor has done its thing, and #included every #include it's been
told about, recursively, until there is no more #including to be done. Once
that's out of the way, we have a single unit of the program that is waiting
to be translated. We call this a "translation unit". And so does the
Standard. In the following quote from the Standard, I have marked off one
sentence with *** *** marks because it is particularly relevant to you
right now.
2.1.1.1 Program structure

A C program need not all be translated at the same time. The text
of the program is kept in units called source files in this Standard.
A source file together with all the headers and source files included
via the preprocessing directive #include , less any source lines
skipped by any of the conditional inclusion preprocessing directives,
is called a translation unit. Previously translated translation units
may be preserved individually or in libraries. ***The separate
translation units of a program communicate by (for example) calls to
functions whose identifiers have external linkage***, by manipulation of
objects whose identifiers have external linkage, and by manipulation
of data files. Translation units may be separately translated and
then later linked to produce an executable program.
If a function is static, it doesn't have external linkage, and can't be
called-by-name from other translation units.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[I.M. !Knuth]

Richard Heathfield <in*****@invalid.invalidwrote:

<snip>

Imagine a C source file. Got that?....

<snip>

Ouch! You do carry a big stick, Sir.

Yeah, I got it. For one thing, I was messing up my own definitions of
global vs. static, and the FAQ's glossary filled me in on "translation
unit". Upon re-reading, Mr. Thompson clearly stated everything I needed
to know.

It's getting into the wee hours in my time zone, and I've had a long
day. I'd better just go sleep on it before I cause any more trouble.
:-)

Thanks all, and g'night.
--
I.M. (definitely) !Knuth

[Chris Torek]

In article <ln************@nuthaus.mib.org>
Keith Thompson <ks***@mib.orgwrote:

static int func_recurs(int arg1, int arg2, int prev_pos)
{ ... }

The only effect of the "static" keyword here is that the function name
"func_recurs" is not visible outside the current translation unit.
(Making it more globally visible would probably be harmless, but it
clutters the namespace.) There's no effect on allocation.

Indeed.

For what it is worth, the "static" and "extern" keywords are rather
squirrelly. I have an in-progress HTML article on this but it is
not yet done and may contain errors:

http://web.torek.net/torek/c/tmp.html

Incidentally, in Lisp-y languages, one tends to write the
"helper function" entirely within the "external-interface function",
using lambda or similar to write the internal function without
even bothering with a name. This method is not available in C,
but using a "static" function, we can fake it.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Michael Wojcik]

In article <Xn********************@81.174.50.80>, "I.M. !Knuth" <no*******@yoyodyne.comwrites:

Michael Wojcik <mw*****@newsguy.comwrote:

One change I would make is to give func_recurs internal linkage (by
adding the "static" sc-specifier), since the public interface to this
operation is now func_lazymemory.

Now here you had me scratching my head (and searching the FAQ).

So if I read you correctly, your recommending that I define the
functions like this:

int func_lazymemory(int arg1, int arg2)
{ ... }

...and...

int func_recurs(static int arg1, static int arg2, int prev_pos)
{ ... }

...so that storage will only be allocated once for both arg1 and arg2.
Correct?

No, I just meant:

static int func_recurs(int arg1, int arg2, int prev_pos)
{ ... }

int func_lazymemory(int arg1, int arg2)
{ ... }

That way, the identifier func_recurs is only visible to other functions
in the same source file - in fact, to other functions below the first
declaration of it in that source file, which is why I moved it above
func_lazymemory.

The "static" will catch any places where you try to call func_recurs
from another source file. In effect, you're saying "func_lazymemory
is what you call when you want this functionality".

You can't declare a parameter with the "static" storage-class
specifier. (The only storage-class specifier you can use with a
parameter is "register", IIRC, and "register" is rarely useful in
modern C implementations.)

If so, this handily provides and alternate answer to question 1b from my
original post (which I just now noticed I bungled) where I was trying to
pass pointers to conserve storage:

You're probably not conserving any storage in this case. It would
depend on how your C implementation passes parameters and various
other things outside the scope of the C language, but it's unlikely
to be worth doing.

On the other hand, if func_recurs changes the values of arg1 and
arg2, and you want func_lazymemory to see those changes, then you
would want to pass their addresses so that func_recurs actually
updates the objects that func_lazymemory sees.

--
Michael Wojcik mi************@microfocus.com

Unfortunately, as a software professional, tradition requires me to spend New
Years Eve drinking alone, playing video games and sobbing uncontrollably.
-- Peter Johnson

[websnarf]

I.M. !Knuth wrote:

A while back, I was mucking around with a recursive function. For
brevity's sake, I'll define it like this:

int func_recurs(int arg1, int arg2, int prev_pos)
{
int crnt_pos = 0;
int result;

/* stuff happens to arg1, arg2, and crnt_pos */

func_recurs(arg1, arg2, (prev_pos + crnt_pos) );

return result;
}

The critical part here (as I'm sure you've figured out already) is that
prev_pos (the previous position) of the last recursion is combined with
crnt_pos (the current positon) of the present recursion and passed along
to become the prev_pos of the next recursion.

But written this way, I had to remember that any call to func_recurs()
always had to look like this:

func_recurs(arg1, arg2, 0);

Frankly, I thought that constant 0 dangling at the end was rather
inelegant. Then it struck me that maybe I could "hide" func_recurs
inside another function so that I wouldn't have to strain my brain
remembering about that pesky third argument; something like:

func_lazymemory(int arg1, int arg2)
{
func_recurs(arg1, arg2, 0);
}

Being new to C, I felt pretty clever for coming up with this all on my
own. But then I thought: "Bah! Smells of kludge. There must be a
better way."

What? This is the way to do it. This is not a kludge, this is just
how you have to do it sometimes. Try implementing mergesort some time
-- this is just the way you do it. Nothing kludgy about it. If you
want to make it have less overhead or something do it like this:

#define func_lazymemory(arg1,arg2) func_recurs(arg1, arg2, 0)

So I changed it to:

int func_recurs(int arg1, int arg2)
{
-- static int prev_pos; /* conveniently init'd to 0 on 1st call */

Yes ok, so you can only ever call this function once. In general, you
should not declare static elements in your stack unless 1) they are
read-only, 2) you can guarantee that your function will not be called
in a multithreaded environment, 3) their relevant life-time is only
inline and in a multi-threaded environment they are guarded by some
critical section anyhow.

int crnt_pos = 0;
int result;

/* stuff happens to arg1, arg2, and crnt_pos */

-- prev_pos += crnt_pos; /* adjust for next recursion */
-- func_recurs(arg1, arg2);
-- prev_pos -= crnt_pos; /* restore for current recursion */

return result;
}

Drawing your attention to the four "-->" lines, I then thought: "Boy is
that ugly", but I no longer felt I'd somehow cheated inside my code. I
packed away the function and forgot about it ... until tonight.

Whenever you rely on statics to retain state from multiple contexts you
should always be wary. If I ever saw this, I would by default assume
it was a bug, and I would rewrite it in the wrapper style you referred
to above.

Tonight I was browsing through some months' old threads on clc and came
across one that discussed function wrappers. "Cool," I thought. A
response referenced the FAQ, so I pulled it up and had a read. So, my
clever idea is old hat. Figures! :-D

I started thinking again about how I dealt with that function and came
up with some questions and concerns:

1a) Is my use of a wrapper appropriate (or am I ignorant of some wrapper
rule or style convention)?

Yes, in fact that is the way I would recommend. (Or using the macro,
but it depends on how you want to expose the interface.)

1b) Wouldn't the wrapper be improved (and the program conserve some
storage) if it were re-written to pass pointer values like this?

func_lazymemory(int *arg1, int *arg2)
{
func_recurs(arg1, arg2, 0);
}

No. Just copy the parameters.

2a) Is one of my solutions better/cleaner/preferable over the other?

Yes, the wrapper method is far better, because you are not using
writable function-local statics.

2b) Or are they equivalent, and picking one is a matter of (my) personal
style?

They are not equivalent, because the second solution has a high failure
risk (through multithreading, or your wrong assumption about how the
static is initialized.)

3) Is there some other (maybe obvious) solution to ditching that third
argument that I've somehow overlooked?

No, just leave it.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Ben Pfaff]

we******@gmail.com writes:

I.M. !Knuth wrote:

>The critical part here (as I'm sure you've figured out already) is that
prev_pos (the previous position) of the last recursion is combined with
crnt_pos (the current positon) of the present recursion and passed along
to become the prev_pos of the next recursion.

But written this way, I had to remember that any call to func_recurs()
always had to look like this:

func_recurs(arg1, arg2, 0);

Frankly, I thought that constant 0 dangling at the end was rather
inelegant. Then it struck me that maybe I could "hide" func_recurs
inside another function so that I wouldn't have to strain my brain
remembering about that pesky third argument; something like:

func_lazymemory(int arg1, int arg2)
{
func_recurs(arg1, arg2, 0);
}

What? This is the way to do it. This is not a kludge, this is just
how you have to do it sometimes. Try implementing mergesort some time
-- this is just the way you do it. [...]

Hmm? That might be one way to do it. But there's no reason that
a merge sort even has to be recursive. For example, take a look
at the merge sort in my linked list library:

/* Sorts R0...R1 into ascending order
according to COMPARE given auxiliary data AUX.
In use, keep in mind that R0 may move during the sort, so that
afterward R0...R1 may denote a different range.
(On the other hand, R1 is fixed in place.)
Runs in O(n lg n) time in the number of nodes in the range. */
void
ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
{
struct ll *pre_r0;
size_t output_run_cnt;

if (r0 == r1 || ll_next (r0) == r1)
return;

pre_r0 = ll_prev (r0);
do
{
struct ll *a0 = ll_next (pre_r0);
for (output_run_cnt = 1; ; output_run_cnt++)
{
struct ll *a1 = ll_find_run (a0, r1, compare, aux);
struct ll *a2 = ll_find_run (a1, r1, compare, aux);
if (a1 == a2)
break;

a0 = ll_merge (a0, a1, a1, a2, compare, aux);
}
}
while (output_run_cnt 1);
}

There's a lot that goes unsaid here, but you can find the whole library at
http://cvs.savannah.gnu.org/viewcvs/...=pspp&view=log
if you're curious.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}