functions

[Tim Rentsch]

Your statement was, recursion without TCO can't be used and
won't be used in a functional style. That statement is false.

My statement was that, without TCO, recursion cannot realistically replace
iteration.

Obviously that statement is false for a large class of programs.

Most of which are uninteresting. Most useful programs have at least one
unbounded loop, typically processing an input file or stdin until EOF.

I'm sure that's true for some value of 'n', but that's beside
the point. Your claim was that it can't be used, and that
claim was made without qualification as to the size of the
input. It's wrong. If you had said "It can't be used for
programs that have lists with 100 trillion elements in them",
I expect I would have agreed with you.

Most programs don't know the size of their inputs until run-time.

Let's face it: if the language doesn't have TCO, it is going to provide an
iteration primitive and any sane program is going to use it instead of
(non-branching) recursion.

The alternative, i.e. using memory proportional to the size of the input
*for no good reason*, isn't really an alternative.

But that's not what you said.

What I said was:

[Note: "really" and "much". IOW, you don't have a choice if you're trying
to write actual software rather than engaging in pedantic arguments.]

And:

Personally, I would consider exhausting the stack in a simple
read-process-write program (e.g. "cat") to be "not working".

Of course, some people have a very loose definition for "works". But I
can't think of anyone who would set the bar quite this low, other than for
the sake of argument.

What you did say is an overstatement. Of course
you might have meant something different from what you said, but my
response was a reply to what you said, not what you might have been
thinking.

No, I meant what I said. I didn't necessarily mean any and all possible
interpretations of what I said, even including interpretations which would
only be assumed for the sake of argument.

OTOH, I'm stil not entirely sure that you understand the issue. E.g.
bringing up recursive-descent parsers suggests that you may not.

The commentary above reads like a political ad: always quoting
selectively, and offering quotes after removing the previously
supplied context.

The letter of what you said (quoted exactly in my last posting, but
snipped in your response):

IOW, it can't be used,
isn't expected to be used, and won't be used in a functional style.

(This is only one comment, and it is quoted here without context;
but I encourage anyone who hasn't seen the previous postings to
look them up to see the original context for this statement and
also my reply to the posting that contained it.)

The spirit of what you're saying: In the absence of TCO, recursion
without iteration is for all practical purposes unusable.

If anyone disagrees with either of these, I invite them to look
at the record. I'm happy to consider any serious comments that
I have misunderstood the remarks in previous postings.

So now I will put this as a question: are you saying that
(absent TCO), recursion without iteration is unusable for
/all/ practical purposes, or are you saying that recursion
without iteration is usuable for /some/ practical purposes?

If the answer is "some", I agree with you.

If the answer is "all", I don't agree, and say again that
such a pronouncement is an overstatement.

 

[Uno]

You have already shown the Plauger putc *function* before.
I wanted to see the Plauger putc *macro*.

int putc(int, FILE *);
int putchar(int);
int puts(const char *);
int remove(const char *);
int rename(const char *, const char *);
void rewind(FILE *);
int scanf(const char *, ...);
void setbuf(FILE *, char *);
int setvbuf(FILE *, char *, int, size_t);
int sprintf(char *, const char *, ...);
int sscanf(const char *, const char *, ...);
FILE *tmpfile(void);
char *tmpnam(char *);
int ungetc(int, FILE *);
int vfprintf(FILE *, const char *, char *);
int vprintf(const char *, char *);
int vsprintf(char *, const char *, char *);
long _Fgpos(FILE *, fpos_t *);
int _Fspos(FILE *, const fpos_t *, long, int);
extern FILE *_Files[FOPEN_MAX];
/* macro overrides */
#define fgetpos(str, ptr) (int)_Fgpos(str, ptr)
#define fseek(str, off, way) _Fspos(str, _NULL, off, way)
#define fsetpos(str, ptr) _Fspos(str, ptr, 0L, 0)
#define ftell(str) _Fgpos(str, _NULL)
#define getc(str) ((str)->_Next < (str)->_Rend \
? *(str)->_Next++ : (getc)(str))
#define getchar() (_Files[0]->_Next < _Files[0]->_Rend \
? *_Files[0]->_Next++ : (getchar)())
#define putc(c, str) ((str)->_Next < (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))
#define putchar(c) (_Files[1]->_Next < _Files[1]->_Wend \
? (*_Files[1]->_Next++ = c) : (putchar)(c))
#endif

What does this macro do? I'm missing the bigger (or smaller) picture here.

It is what we are discussing.
The standard describes output as though being done through fputc.

But when describing the behavior of the putchar function,
the standard refers to the behavior of putc.

I think that most programmers expect putc
to be at least as simple and fast as fputc,
otherwise the existance of putc serves no purpose at all.

Ok.

 

[Uno]

My "on the whole" was deliberately vague, as was my "significantly",
since I was well aware of quite a few counter-examples to my claim.
Nevertheless, /on the whole/, "divide and conquer" problems lend
themselves more easily to recursive techniques if the division is bold
and dynamic:

void foo(tree *p)
{
if(p->left) foo(p->left);
if(p->right) foo(p->right);
free(p);
}

whereas nibbling at the edges of a problem:

void bar(node *p)
{
if(p->next) bar(p->next);
free(p);
}

can lead to problems.

Sorry about your team. Who will you cheer for now?

When you're writing a library, why do you have macros **and** function
definitions for functions like fputc?

 

[Uno]

Taking a hint from another poster, I'd write

#include "defines.h"
#include S
I M(V){P("Hello, world!\n");R 0;}

W C B simpler?

I don't think this would compile, Eric. Have you been drinking the
water that Sharon Angle has?

 

[Uno]

I have changed my writing style over the years.
I have found that when I write in a similar style
to other programmers,
then their code becomes easier for me to read.
There is no one single style that everybody uses,
but I am a big fan of Indian Hill C Style.
I don't think anybody has trouble reading it.

Do you use indent? If so, with what on the command line?

 

[Ben Bacarisse]

My "on the whole" was deliberately vague, as was my "significantly",
since I was well aware of quite a few counter-examples to my
claim. Nevertheless, /on the whole/, "divide and conquer" problems
lend themselves more easily to recursive techniques if the division is
bold and dynamic:

void foo(tree *p)
{
if(p->left) foo(p->left);
if(p->right) foo(p->right);
free(p);
}

whereas nibbling at the edges of a problem:

void bar(node *p)
{
if(p->next) bar(p->next);
free(p);
}

can lead to problems.

Your "can lead to problems" is pretty vague once again. There are cases
where nibbling at the edges does not lead to problems (pete gave some
examples but there are others) and I am pretty sure we don't disagree
about this.

I think we just have a difference of emphasis. I am likely to consider
a recursive solution even when the division is a nibble. I'll reject it
if I see problem looming (no tail calls, unbounded growth and so on)
rather than base the decision on the size of the divided sub-problems.

 

[Nobody]

The spirit of what you're saying: In the absence of TCO, recursion
without iteration is for all practical purposes unusable.

Yes; for a more detailed answer, see below.

So now I will put this as a question: are you saying that
(absent TCO), recursion without iteration is unusable for
/all/ practical purposes, or are you saying that recursion
without iteration is usuable for /some/ practical purposes?

I'm saying that a general-purpose[1] language which doesn't implement
either TCO or iteration (which is just non-branching recursion with TCO)
would be of purely academic interest. It would be impossible to write a
program which processes an unlimited amount of input, as every "loop" will
require stack space proportional to the number of iterations.

The existence of some practical programs which could be written in
such a language (e.g. true, false, echo, ...) doesn't mean that the
language itself is practical.

[1] Some domain-specific languages forbid unbounded loops, although they
often evaluate the expression within a loop of their own making. E.g. GLSL
imposes limits on the number of iterations within a shader, but the shader
is executed for every vertex or fragment. SQL doesn't support loops, but
expressions are evaluated for each record.

 

[Uno]

int putc(int, FILE *);
int putchar(int);

#define putc(c, str) ((str)->_Next < (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))
#define putchar(c) (_Files[1]->_Next < _Files[1]->_Wend \
? (*_Files[1]->_Next++ = c) : (putchar)(c))
#endif

What does this macro do?
I'm missing the bigger (or smaller) picture here.

It does the same thing as what the putc function is supposed to do,
except that the putc function may only evaluate
its second argument once,
while you can see that the putc macro evaluates
its second argument two or three times.
This only makes a difference if the second
argument has side effects.

putc('x', Y());

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

If putc is implemented as both a macro and as a function, then
putc('x', Y());
will call the macro;
and the function version can be called this way:
(putc)('x', Y());

Can you show a little more source to illustrate?

 

[Malcolm McLean]

whereas nibbling at the edges of a problem:

void bar(node *p)
{
   if(p->next) bar(p->next);
   free(p);

}

can lead to problems.

However if a linked list is long enough to lead to stack space
problems when freeing, it's probably also long enough to lead to
problems in traversing whilst the list is live.

 

[Nick Keighley]

I'm not sure you can support this...

Sorry about your team.  Who will you cheer for now?

When you're writing a library, why do you have macros **and** function
definitions for functions like fputc?

what does this have to do with recursion? Are you asking why anyone
would do something like this? Macros may be faster (they are
essentially inline code) but are less safe- they may evaluate their
arguments more than once. You seem to be a fan of Plauger's library
book, doesn't he discuss this?

 

[Tim Rentsch]

The spirit of what you're saying: In the absence of TCO, recursion
without iteration is for all practical purposes unusable.

Yes; [elaboration snipped]

You're entitled to your opinion. To me it seems obvious that
this overstates the case: if something is unusable for _all_
practical purposes, there is _no_ _possible_ practical purpose
to which it can be put. That's an incredibly strong claim.
Moreover, the particular case just doesn't jibe with personal
experience. But you think what you want.

 

[Uno]

Uno wrote:
pete wrote:
Uno wrote:
pete wrote:
The parentheses around (putc) in that definition,
suggest that there is also a Plauger putc macro.
I would like to see that too,
if it's not too much trouble please.
You bet.

/* putc function */
#include "xstdio.h"

int (putc)(int c, FILE *str)
{ /* put character to stream */
return (fputc(c, str));
}
You have already shown the Plauger putc *function* before.
I wanted to see the Plauger putc *macro*.
int putc(int, FILE *);
int putchar(int);
#define putc(c, str) ((str)->_Next < (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))
#define putchar(c) (_Files[1]->_Next < _Files[1]->_Wend \
? (*_Files[1]->_Next++ = c) : (putchar)(c))
#endif

What does this macro do?
I'm missing the bigger (or smaller) picture here.
It does the same thing as what the putc function is supposed to do,
except that the putc function may only evaluate
its second argument once,
while you can see that the putc macro evaluates
its second argument two or three times.
This only makes a difference if the second
argument has side effects.

putc('x', Y());

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

If putc is implemented as both a macro and as a function, then
putc('x', Y());
will call the macro;
and the function version can be called this way:
(putc)('x', Y());

Can you show a little more source to illustrate?

/* BEGIN new.c */

#include "xstdio.h"

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

int main(void)
{
(putc)('A', Y());
puts("\n");
putc('B', Y());
putchar('\n');
return 0;
}

/* END new.c */

Translate it and execute it and see what happens.

$ gcc -Wall -Wextra p6.c -o out
$ ./out
YYYYY
A

YYYYY
B
$ cat p6.c


#include "CLIB/_HEADERS/XSTDIO.H"

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

int main(void)
{
(putc)('A', Y());
puts("\n");
putc('B', Y());
putchar('\n');
return 0;
}

// gcc -Wall -Wextra p6.c -o out
$

Hmmmm.... Not exactly sure what I'm to see here.

 

[Nobody]

The spirit of what you're saying: In the absence of TCO, recursion
without iteration is for all practical purposes unusable.

Yes; [elaboration snipped]

You're entitled to your opinion. To me it seems obvious that
this overstates the case: if something is unusable for _all_
practical purposes, there is _no_ _possible_ practical purpose
to which it can be put. That's an incredibly strong claim.

Sorry; I interpreted "for all practical purposes" as having the common
meaning, not the language-lawyer meaning. But that much should have been
clear from the "elaboration".

Moreover, the particular case just doesn't jibe with personal
experience. But you think what you want.

You lost me here. Which particular case?

 

[Uno]

If your program was using this definition of putc:

#define putc(c, str) ((str)->_Next< (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))

then, (str) would have been evaluated 3 times
and your output would have been:


YYYYY
A

YYYYY
YYYYY
YYYYY
B


On the C implementation that I am using,
there is a putc macro which evaluates its second argument twice
and the output of new.c on my machine is:

YYYYY
A

YYYYY
YYYYY
B

Here is new.c

/* BEGIN new.c */

#include<stdio.h>

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

int main(void)
{
(putc)('A', Y());
puts("\n");
putc('B', Y());
putchar('\n');
return 0;
}

/* END new.c */

And, once again, depending on my needs, I can either call the function
or use the macro, right?

Can you talk through the logic of the macro?

#define putc(c, str) ((str)->_Next< (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))

 

[Tim Rentsch]

The spirit of what you're saying: In the absence of TCO, recursion
without iteration is for all practical purposes unusable.

Yes; [elaboration snipped]

You're entitled to your opinion. To me it seems obvious that
this overstates the case: if something is unusable for _all_
practical purposes, there is _no_ _possible_ practical purpose
to which it can be put. That's an incredibly strong claim.

Sorry; I interpreted "for all practical purposes" as having the common
meaning, not the language-lawyer meaning. [snip]

If you have found my comments confusing it's because you
haven't been paying attention. I've been saying all along
that your remarks overstate the case. And now you're
surprised to find that what I meant is that your remarks
actually do overstate the case???

 

[Uno]

If your program was using this definition of putc:

#define putc(c, str) ((str)->_Next < (str)->_Wend \
? (*(str)->_Next++ = c) : (putc)(c, str))

I do not understand the logic in the above statement

then, (str) would have been evaluated 3 times
and your output would have been:


YYYYY
A

YYYYY
YYYYY
YYYYY
B


On the C implementation that I am using,
there is a putc macro which evaluates its second argument twice
and the output of new.c on my machine is:

YYYYY
A

YYYYY
YYYYY
B

Ok. Why would you want (str) to be evaluated twice or thrice?

Here is new.c

/* BEGIN new.c */

#include <stdio.h>

FILE *Y(void)
{
puts("YYYYY");
return stdout;
}

int main(void)
{
(putc)('A', Y());
puts("\n");
putc('B', Y());
putchar('\n');
return 0;
}

/* END new.c */

Why do you use puts in once instance and putchar in the other?

 

[Nobody]

Sorry; I interpreted "for all practical purposes" as having the common
meaning, not the language-lawyer meaning. [snip]

If you have found my comments confusing it's because you
haven't been paying attention. I've been saying all along
that your remarks overstate the case. And now you're
surprised to find that what I meant is that your remarks
actually do overstate the case???

No, I'm well aware of what you're claiming. The only thing I'm surprised
at is the extent to which you're willing to play semantic games in order
to "win" an argument.

 

[Uno]

Except that while all implementations supply the putc function,
supplying the macro is optional.

And so inconclusion,

(putc)('A', stdout);

always calls the function, but

putc('A', stdout);

will use the putc macro if the putc macro exists,
but if the putc macro does not exist, then

putc('A', stdout);

will call the function.

Alright, thx pete, let's leave it there.

 

[Tim Rentsch]

Sorry; I interpreted "for all practical purposes" as having the common
meaning, not the language-lawyer meaning. [snip]

If you have found my comments confusing it's because you
haven't been paying attention. I've been saying all along
that your remarks overstate the case. And now you're
surprised to find that what I meant is that your remarks
actually do overstate the case???

No, I'm well aware of what you're claiming. The only thing I'm surprised
at is the extent to which you're willing to play semantic games in order
to "win" an argument.

My comments were quite direct, simply literal and straightforward.
Your comments were much more of the "yes, repeat no" variety.
And now you want to accuse me of playing semantics games?
You definitely should consider running for political office.

 

[David Thompson]

As others have pointed out, C doesn't make this distinction. (No, it
really doesn't.)

Languages like Pascal and Ada that do distinguish between procedures
and functions usually don't make the same distinction you're making.
For example, a Pascal procedure is equivalent to a C void function,
and a Pascal procedure is equivalent to a C function that returns
something other than void. A Pascal function can perform I/O or
modify globals. I think it can also take modifiable parameters.

Pascal, yes. Ada makes one distinction: functions cannot have formals
(parameters) with mode 'out' or 'in out', so they cannot directly
store passed objects; but they can read and store package variables
visible to callers, and they can receive 'access' (pointer) formals
that can be used to store any variable that has an 'access, although
that is rather more limited than in C.

I think what you're referring to as "functions" are what I'd call
"pure functions". A pure function is one that has no (visible?) side
effects, that receives information only through its arguments,
and that sends data only through its return value.

Classic Fortran had FUNCTIONs and SUBROUTINEs, together subprograms,
with no limitations on side-effects. However, although the standard
wording was a bit vague, Fortran compilers were often aggressive about
optimization and in particular might 'combine' calls to the same
function with the same arguments, like local common subexpressions,
even if actual execution of a separate function would vary. So good
Fortran programmers (and programs) mostly stopped relying on that.

As a consequence that may surprise people coming from other 3GLs,
Fortran's (pseudo) RANDOM_NUMBER() is a subroutine not a function.
So is DATE_AND_TIME, but that passes-back multiple values
which couldn't have been a FUNCTION return pre-F90; CPU_TIME
and SYSTEM_CLOCK also are subroutines, though the former does
and the latter easily could pass-back only one scalar.

After F90 added whole-array operations and made many 'instrinsic'
(library) functions work elementwise and optionally in parallel, F95
added user ELEMENTAL subprograms: both functions and subroutines,
although subroutines appear to be much less useful; and also as a
'free' intermediate case PURE subprograms (which don't map).
All data formals of a PURE or ELEMENTAL function must be INTENT(IN)
except for POINTERs, and all side effects that would be visible
(stores to nonlocal variables and file I/O) are prohibited.