The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Chad
27  2108 
"Chad" <cd*****@gmail.comwrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Because it can easily be done using simple iteration, so recursion is
overkill and could (though it's unlikely) fail due to lack of stack
space where an iterative solution wouldn't.
Richard
I think the phrase "it's completely needless" comes to mind
Richard Bos wrote:
"Chad" <cd*****@gmail.comwrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Because it can easily be done using simple iteration, so recursion is
overkill and could (though it's unlikely) fail due to lack of stack
space where an iterative solution wouldn't.
Richard
Chad wrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Chad
Recursion is bad for string reversal because it is increases the
stack depth to K*n, where n is the length of the string. A much
better method is described in Bentley's "Programming Pearls",
where you set pointers beg, end to the ends of the string, swap
those characters, increment beg and decrement end, then repeat.
You also test whether beg>=end and in that case do not swap but
exit. This algorithm uses n/2 swaps. The loop is iterative and
does not increase the stack.
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia as****@purdue.edu wrote:
I think the phrase "it's completely needless" comes to mind
Kind of like top-posting?
Brian
Julian V. Noble wrote:
Chad wrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Chad
Recursion is bad for string reversal because it is increases the
stack depth to K*n, where n is the length of the string. A much
better method is described in Bentley's "Programming Pearls",
where you set pointers beg, end to the ends of the string, swap
those characters, increment beg and decrement end, then repeat.
You also test whether beg>=end and in that case do not swap but
exit. This algorithm uses n/2 swaps. The loop is iterative and
does not increase the stack.
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
Don't we also increase the stack depth on a Binary Search Tree
everytime we add a node to the tree? If I remember correctly, we use
recursion to add a node to a Binary Search Tree. How would this be much
more different than using a recursive version of reversing a string in
place?
Chad
Chad said:
<snip>
>
Don't we also increase the stack depth on a Binary Search Tree
everytime we add a node to the tree?
Yes, but.
If I remember correctly, we use
recursion to add a node to a Binary Search Tree.
Yes, but.
How would this be much
more different than using a recursive version of reversing a string in
place?
If you naively add nodes to a binary search tree without taking due account
of the "shape" of that tree, and if you use recursion to add or search for
nodes (which is not a given - IIRC Ben Pfaff's libavl does not use
recursion), then you do run the risk of exceeding the machine's ability to
cope with that kind of call depth. But of course you can be mildly clever,
and balance the tree as you go. Also, if you do choose to use recursion,
you gain in expressive power - it's easy to write a set of recursive
functions to handle a binary tree, but rather harder to write an iterative
set.
Here's a string reversing routine that uses iteration:
void reverse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
char tmp = *p;
while(p < q)
{
*p++ = *q;
*q-- = tmp;
tmp = *p;
}
}
}
Here's a version that uses recursion:
void recurse(char *p, char *q)
{
if(p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
recurse(p + 1, q - 1);
}
}
void recerse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
recurse(p, q);
}
}
As you can see, I've wrapped the recursive function inside another function
that calculates the length of the string. I'm sure it's possible to avoid
calling strlen over and over again without writing a wrapper, but this was
the quickest, most obvious way I could find. As you can see, the recursive
version is slightly longer and rather less obvious than the iterative
version. And if the string is, say, a description of a DNA strand 5,000,000
bases long, then you're looking at a call depth of 2.5 million - whereas
the iterative version will have a call depth of just 1. And it won't need
the overhead of 2.5 million function calls, either.
--
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)
Richard Heathfield wrote:
Chad said:
<snip>
>Don't we also increase the stack depth on a Binary Search Tree
everytime we add a node to the tree?
Yes, but.
>If I remember correctly, we use
recursion to add a node to a Binary Search Tree.
Yes, but.
>How would this be much
more different than using a recursive version of reversing a string in
place?
If you naively add nodes to a binary search tree without taking due account
of the "shape" of that tree, and if you use recursion to add or search for
nodes (which is not a given - IIRC Ben Pfaff's libavl does not use
recursion), then you do run the risk of exceeding the machine's ability to
cope with that kind of call depth. But of course you can be mildly clever,
and balance the tree as you go. Also, if you do choose to use recursion,
you gain in expressive power - it's easy to write a set of recursive
functions to handle a binary tree, but rather harder to write an iterative
set.
Here's a string reversing routine that uses iteration:
void reverse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
char tmp = *p;
while(p < q)
{
*p++ = *q;
*q-- = tmp;
tmp = *p;
}
}
}
Here's a version that uses recursion:
void recurse(char *p, char *q)
{
if(p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
recurse(p + 1, q - 1);
}
}
void recerse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
recurse(p, q);
}
}
As you can see, I've wrapped the recursive function inside another function
that calculates the length of the string. I'm sure it's possible to avoid
calling strlen over and over again without writing a wrapper, but this was
the quickest, most obvious way I could find. As you can see, the recursive
version is slightly longer and rather less obvious than the iterative
version. And if the string is, say, a description of a DNA strand 5,000,000
bases long, then you're looking at a call depth of 2.5 million - whereas
the iterative version will have a call depth of just 1. And it won't need
the overhead of 2.5 million function calls, either.
Isn't it true though that a respectable compiler would optimize the tail
recursion out of existence?
Ark said:
<snip>
Isn't it true though that a respectable compiler would optimize the tail
recursion out of existence?
It certainly could, yes. It is not required to by the language spec,
however.
--
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)
Chad wrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
There's no inherent reason why recursion isn't a good
way to reverse a string. It can be just as easy to
understand, just as easy to program, and perform as
well as an iterative solution.
If there is a reason not to use a recursive solution,
it is that using recursion here will surprise many
programmers who have done most of their programming
in C or C-like languages and don't have much experience
doing functional programming. A recursive solution
isn't a good match to current C culture. That may
be changing, but it is changing only slowly.
Julian V. Noble wrote:
Chad wrote:
The problem is:
Write a recursive version of the function reverse(s), which reverses
the string s in place.
In "The C Answer Book", Second Edition, near the bottom of page 95, the
authors say
"This is not a good application of recursion". Just for the record, I
did make an attempt at the solution before I broke down and looked at
the solution in the book.
I'm sort of mystified why reversing a string in place recursively is
not a good application of recurson.
Chad
Recursion is bad for string reversal because it is increases the
stack depth to K*n, where n is the length of the string. A much
better method is described in Bentley's "Programming Pearls",
where you set pointers beg, end to the ends of the string, swap
those characters, increment beg and decrement end, then repeat.
You also test whether beg>=end and in that case do not swap but
exit. This algorithm uses n/2 swaps. The loop is iterative and
does not increase the stack.
Any decent compiler will optimize a tail-recursive
call so a recursive solution can take a constant
amount of stack space just like an iterative solution.
Richard Heathfield wrote:
Chad said:
<snip>
Don't we also increase the stack depth on a Binary Search Tree
everytime we add a node to the tree?
Yes, but.
If I remember correctly, we use
recursion to add a node to a Binary Search Tree.
Yes, but.
How would this be much
more different than using a recursive version of reversing a string in
place?
If you naively add nodes to a binary search tree without taking due account
of the "shape" of that tree, and if you use recursion to add or search for
nodes (which is not a given - IIRC Ben Pfaff's libavl does not use
recursion), then you do run the risk of exceeding the machine's ability to
cope with that kind of call depth. But of course you can be mildly clever,
and balance the tree as you go. Also, if you do choose to use recursion,
you gain in expressive power - it's easy to write a set of recursive
functions to handle a binary tree, but rather harder to write an iterative
set.
Here's a string reversing routine that uses iteration:
void reverse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
char tmp = *p;
while(p < q)
{
*p++ = *q;
*q-- = tmp;
tmp = *p;
}
}
}
Here's a version that uses recursion:
void recurse(char *p, char *q)
{
if(p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
recurse(p + 1, q - 1);
}
}
void recerse(char *s)
{
if(s && *s)
{
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
recurse(p, q);
}
}
As you can see, I've wrapped the recursive function inside another function
that calculates the length of the string. I'm sure it's possible to avoid
calling strlen over and over again without writing a wrapper, but this was
the quickest, most obvious way I could find. As you can see, the recursive
version is slightly longer and rather less obvious than the iterative
version.
Except you've written the recursive version incompetently.
The temporary variables p and q are necessary in the
iterative version, but most competent functional
programmers wouldn't use them in recerse(). A more
appropriate comparison would look like this:
void reverse(char *s)
{
if(s && *s){
size_t len = strlen(s) - 1;
char *p = s;
char *q = p + len;
char tmp;
while(p < q) tmp = *p, *p++ = *q, *q-- = tmp;
}
}
void recurse(char *p, char *q)
{
char tmp;
if(p < q) tmp = *p, *p = *q, *p = tmp, recurse(p+1,q-1);
}
void recerse(char *s)
{
if(s && *s) recurse(s, s+strlen(s)-1);
}
And if the string is, say, a description of a DNA strand 5,000,000
bases long, then you're looking at a call depth of 2.5 million - whereas
the iterative version will have a call depth of just 1. And it won't need
the overhead of 2.5 million function calls, either.
I'm not looking at a call depth of 2.5 million;
the compilers I use will optimize the tail recursive
call. And, I suspect, so will compilers that you use.
Richard Heathfield wrote:
Ark said:
<snip>
Isn't it true though that a respectable compiler would optimize the tail
recursion out of existence?
It certainly could, yes. It is not required to by the language spec,
however.
That's true, but neither does the language spec require
that a while loop be compiled as a jump rather than
a recursive call. en******@yahoo.com said:
>
Richard Heathfield wrote:
<snip>
>As you can see,
the recursive version is slightly longer and rather less obvious than the
iterative version.
Except you've written the recursive version incompetently.
No, I've written it clearly. Had I written it less clearly, it would have
indeed have been shorter, but it would also have been even less obvious.
--
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)
On 2006-07-31, en******@yahoo.com <en******@yahoo.comwrote:
>
Richard Heathfield wrote:
>Ark said:
<snip>
Isn't it true though that a respectable compiler would optimize the tail
recursion out of existence?
It certainly could, yes. It is not required to by the language spec,
however.
That's true, but neither does the language spec require
that a while loop be compiled as a jump rather than
a recursive call.
Clever argument, but it /does/ require that code behave as it (meaning
both the Standard and the code in question) say it does, and the simplest
solution is for the compiler to compile loops as loops, and recursive
functions as recursive functions.
Still not guaranteed, but a lot more likely than it is for a given
compiler to optimize tail recursion.
--
Andrew Poelstra <website down>
To reach my email, use <email also down>
New server ETA: 42
Richard Heathfield wrote:
en******@yahoo.com said:
Richard Heathfield wrote:
<snip>
As you can see,
the recursive version is slightly longer and rather less obvious than the
iterative version.
Except you've written the recursive version incompetently.
No, I've written it clearly. Had I written it less clearly, it would have
indeed have been shorter, but it would also have been even less obvious.
You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent. I expressed an opinion that I believe is
representative of the opinion of practitioners in the
functional programming community.
Andrew Poelstra wrote:
On 2006-07-31, en******@yahoo.com <en******@yahoo.comwrote:
Richard Heathfield wrote:
Ark said:
<snip>
Isn't it true though that a respectable compiler would optimize the tail
recursion out of existence?
It certainly could, yes. It is not required to by the language spec,
however.
That's true, but neither does the language spec require
that a while loop be compiled as a jump rather than
a recursive call.
Clever argument, but it /does/ require that code behave as it (meaning
both the Standard and the code in question) say it does, and the simplest
solution is for the compiler to compile loops as loops, and recursive
functions as recursive functions.
It wasn't an argument, just an observation.
Still not guaranteed, but a lot more likely than it is for a given
compiler to optimize tail recursion.
Yes, and that comment is on point. I think it's better
to take issues straight on, rather than arguing by innuendo. en******@yahoo.com said:
Richard Heathfield wrote:
>en******@yahoo.com said:
Richard Heathfield wrote:
As you can see,
the recursive version is slightly longer and rather less obvious than
the iterative version.
Except you've written the recursive version incompetently.
No, I've written it clearly. Had I written it less clearly, it would have
indeed have been shorter, but it would also have been even less obvious.
You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could use
a class in diplomacy. (Probably so could I.)
I expressed an opinion that I believe is
representative of the opinion of practitioners in the
functional programming community.
C is not a functional programming language. (I can imagine a few people
making hay with that statement, but I know /you/ know what I mean by
"functional" in this context.)
--
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)
Richard Heathfield <in*****@invalid.invalidwrites:
en******@yahoo.com said:
[...]
>You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could use
a class in diplomacy. (Probably so could I.)
But who around here could teach it? 8-)}
--
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.
Keith Thompson said:
Richard Heathfield <in*****@invalid.invalidwrites:
>en******@yahoo.com said:
[...]
>>You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could
use a class in diplomacy. (Probably so could I.)
But who around here could teach it? 8-)}
Chris Torek as head of department, Steve Summit as principal lecturer, and
Stefan Wilms (if he ever manages to find his way back here after his
somewhat extended lunch break) as TA.
--
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)
Richard Heathfield wrote On 08/01/06 17:57,:
Keith Thompson said:
>>Richard Heathfield <in*****@invalid.invalidwrites:
>>>en******@yahoo.com said:
[...]
>>>>You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could
use a class in diplomacy. (Probably so could I.)
But who around here could teach it? 8-)}
Chris Torek as head of department, Steve Summit as principal lecturer, and
Stefan Wilms (if he ever manages to find his way back here after his
somewhat extended lunch break) as TA.
Orals administered by Dan Pop.
-- Er*********@sun.com
Richard Heathfield wrote:
en******@yahoo.com said:
Richard Heathfield wrote:
en******@yahoo.com said:
Richard Heathfield wrote:
As you can see,
the recursive version is slightly longer and rather less obvious than
the iterative version.
Except you've written the recursive version incompetently.
No, I've written it clearly. Had I written it less clearly, it would have
indeed have been shorter, but it would also have been even less obvious.
You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could use
a class in diplomacy. (Probably so could I.)
"Yes sir, Mr. Pot," said Mr. Kettle.
If you read my other postings you'll see that my diplomacy
varies according to what, and sometimes who, I'm responding
to. I can be tactful, or not. A posting/poster showing
tact usually gets tact from me in return. And frequently
vice versa.
I expressed an opinion that I believe is
representative of the opinion of practitioners in the
functional programming community.
C is not a functional programming language. (I can imagine a few people
making hay with that statement, but I know /you/ know what I mean by
"functional" in this context.)
Your comments were about (among other things) writing an
algorithm in a functional programming style. It's
reasonable to judge those comments by the standards of the
community that does functional programming. The distance
between C and functional programming is not as big as you
seem to think it is.
<en******@yahoo.comwrote in message
news:11**********************@m79g2000cwm.googlegr oups.com...
>
Richard Heathfield wrote:
C is not a functional programming language. (I can imagine a few people
making hay with that statement, but I know /you/ know what I mean by
"functional" in this context.)
Your comments were about (among other things) writing an
algorithm in a functional programming style. It's
reasonable to judge those comments by the standards of the
community that does functional programming. The distance
between C and functional programming is not as big as you
seem to think it is.
It has state (variables, memory allocation).
It has control flow operations (while loops, gotos, breaks, the humble
semicolon)
It does not have anonymous functions.
It does not have function types.
It does not have polymorphism to the extent required by functional
languages.
I think these are pretty fundamental reasons for C to be considered "not a
functional language".
Philip en******@yahoo.com said:
>
Richard Heathfield wrote:
>en******@yahoo.com said:
<snip>
You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could
use a class in diplomacy. (Probably so could I.)
"Yes sir, Mr. Pot," said Mr. Kettle.
If you read my other postings
I have done so.
you'll see that my diplomacy varies according to what, and sometimes who,
I'm responding to. I can be tactful, or not.
I've seen a lot of the latter, and almost none of the former. It's why I
hardly ever bother responding to you. And now I will resume that policy.
Ciao.
--
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)
Philip Potter wrote:
<en******@yahoo.comwrote in message
news:11**********************@m79g2000cwm.googlegr oups.com...
Richard Heathfield wrote:
C is not a functional programming language. (I can imagine a few people
making hay with that statement, but I know /you/ know what I mean by
"functional" in this context.)
Your comments were about (among other things) writing an
algorithm in a functional programming style. It's
reasonable to judge those comments by the standards of the
community that does functional programming. The distance
between C and functional programming is not as big as you
seem to think it is.
It has state (variables, memory allocation).
It has control flow operations (while loops, gotos, breaks, the humble
semicolon)
It does not have anonymous functions.
It does not have function types.
It does not have polymorphism to the extent required by functional
languages.
Lisp is a functional language. Lisp has state (variables, setq).
Lisp has control flow operations (while loops, sequencing,
sometimes others depending on which Lisp). Lisp does have
functions but it doesn't have function types, or almost any type
other than list or atom. Lisp does not have polymorphism.
Also, C does have function types, and more importantly pointer to
function, which acts as a first-class function value. It's true,
C doesn't have closures (anonymous functions), but a lot of
functional programming can be done without using closures. It's
also not too difficult to construct C data values that behave
like closures.
I think these are pretty fundamental reasons for C to be considered "not a
functional language".
You'll notice I didn't say C is a functional language, only that
C can be used effectively to write in a functional programming
style. At least to the degree necessary to express the functions
that have been discussed in this thread.
Richard Heathfield wrote:
en******@yahoo.com said:
Richard Heathfield wrote:
en******@yahoo.com said:
<snip>
You're entitled to your opinion of what's clear, just
as other people are entitled to their opinion of what's
competent.
Quite so. Incidentally, I don't doubt /your/ competence - but you could
use a class in diplomacy. (Probably so could I.)
"Yes sir, Mr. Pot," said Mr. Kettle.
If you read my other postings
I have done so.
you'll see that my diplomacy varies according to what, and sometimes who,
I'm responding to. I can be tactful, or not.
I've seen a lot of the latter, and almost none of the former. It's why I
hardly ever bother responding to you. And now I will resume that policy.
Ciao.
I'm sorry my sometimes strong language offends you. But
I'm not writing it just for your benefit.
On 2 Aug 2006 23:31:46 -0700, en******@yahoo.com wrote:
Lisp is a functional language. Lisp has state (variables, setq).
Lisp has control flow operations (while loops, sequencing,
sometimes others depending on which Lisp). Lisp does have
Actually I'd call LISP is a mixture or hybrid of imperative and
functional, for precisely this reason. Classically its functional
parts got more emphasis and IINM use precisely because there were
(plenty of) other choices for imperative.
functions but it doesn't have function types, or almost any type
other than list or atom. Lisp does not have polymorphism.
Even classical LISP has lists (really conses) and two kinds of atoms:
number (integer) and symbol (name). Later ones, including the standard
Common LISP, have several distinguishable number kinds, character
strings, and more. Primitive arithmetic functions are usually
polymorphic over number types, EQUAL effectively is over all types,
and some others have special handling or special cases that are
arguably polymorphic like (CAR NIL) =NIL. Not to mention optional OO
dispatching which provides 'true' polymorphism among OO types.
Although user functions are canonically (and importantly) 'just
lists', primitive or compiled functions are usually a distinct type,
something like #EXPR, and closures at least sometimes are.
Also, C does have function types, and more importantly pointer to
function, which acts as a first-class function value. It's true,
C doesn't have closures (anonymous functions), but a lot of
functional programming can be done without using closures. It's
also not too difficult to construct C data values that behave
like closures.
Well, you can capture the data (needed) for a closure, as indeed you
can in almost any language, but it doesn't have any behavior.
<OTIn C++ you can get behavior with a 'function object', that is, of
a class containing the data and having operator().
I think these are pretty fundamental reasons for C to be considered "not a
functional language".
You'll notice I didn't say C is a functional language, only that
C can be used effectively to write in a functional programming
style. At least to the degree necessary to express the functions
that have been discussed in this thread.
Agree there. Although I'd have to be under severe stress to think it's
worth the trouble when languages designed for it are available.
- David.Thompson1 at worldnet.att.net
Dave Thompson wrote:
On 2 Aug 2006 23:31:46 -0700, en******@yahoo.com wrote:
Lisp is a functional language. Lisp has state (variables, setq).
Lisp has control flow operations (while loops, sequencing,
sometimes others depending on which Lisp). Lisp does have
Actually I'd call LISP is a mixture or hybrid of imperative and
functional, for precisely this reason. Classically its functional
parts got more emphasis and IINM use precisely because there were
(plenty of) other choices for imperative.
Lisp surely has accreted many imperative constructs over the
years. But essentially Lisp started with just the Lambda Calculus,
widely acknowledged as the original basis for functional
programming. The direction was the opposite of what's suggested
above - Lisp started as almost completely functional, and
imperative features were added and got more use because of
other imperative languages.
functions but it doesn't have function types, or almost any type
other than list or atom. Lisp does not have polymorphism.
Even classical LISP has lists (really conses) and two kinds of atoms:
number (integer) and symbol (name). Later ones, including the standard
Common LISP, have several distinguishable number kinds, character
strings, and more.
Yes, maybe it's an oversimplification to lump those
all together under just "atom". But no user defined
types.
Primitive arithmetic functions are usually
polymorphic over number types, EQUAL effectively is over all types,
and some others have special handling or special cases that are
arguably polymorphic like (CAR NIL) =NIL.
Operators in C apply to multiple types, but that doesn't
make C polymorphic.
When I say Lisp doesn't have polymorphism what I mean is
that there are no linguistic mechanisms to support defining
polymorphic functions. Saying Lisp is polymorphic is like
saying C is polymorphic because a function can switch() on
one member of a struct and cast another member to one type
or another.
Not to mention optional OO
dispatching which provides 'true' polymorphism among OO types.
Lisp object systems are layered on top of Lisp, not part
of Lisp. An OO language can be implemented in C, but
that doesn't make C an OO language.
Although user functions are canonically (and importantly) 'just
lists', primitive or compiled functions are usually a distinct type,
something like #EXPR, and closures at least sometimes are.
Probably an important implementation detail, but it
doesn't seem like much more than that.
Also, C does have function types, and more importantly pointer to
function, which acts as a first-class function value. It's true,
C doesn't have closures (anonymous functions), but a lot of
functional programming can be done without using closures. It's
also not too difficult to construct C data values that behave
like closures.
Well, you can capture the data (needed) for a closure, as indeed you
can in almost any language, but it doesn't have any behavior.
Behavior can be included with the data by means of
a function pointer, which is the key point. This
often can't be done in other languages, when they
lack first class function values -- as in Pascal, for
example.
I think these are pretty fundamental reasons for C to be considered "not a
functional language".
You'll notice I didn't say C is a functional language, only that
C can be used effectively to write in a functional programming
style. At least to the degree necessary to express the functions
that have been discussed in this thread.
Agree there. Although I'd have to be under severe stress to think it's
worth the trouble when languages designed for it are available.
In my experience most programs have some parts that are better
done functionally, and other parts that are better done
imperatively, no matter what language they're written in.
I think people who do no functional programming in C
"because it isn't a functional language" are missing out
on an important part of program construction. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Hajo Molegraaf |
last post by:
Hi,
I'm doing my first steps in Qt programming and there is something that
I don't know how to do. As an excercise I want to write some
filemanager like application and I'm trying to implement...
|
by: Suki |
last post by:
Hi all,
I'm facing a rather strange design problem. Let me explain it.
I'm writing an application, which deals with strings extensively. So
decided to write a new string class (CXString say) for...
|
by: Shawn B. |
last post by:
Greetings,
With a Managed class, if I'm #including a Windows SDK header file, and call
an API, it appears (according to .NET Reflector) that it automatically
generates a for each API call that...
|
by: Hari Sekhon |
last post by:
Is it better to do:
message = """This is line1.
This is line2
This is line3\n"""
or
message = "This is line1.\n
message = message + "This is line2\n"
|
by: sbowman |
last post by:
I have a completely lame string parsing question, but I need an answer
fast and I know this is where to get it...I'm not completely familiar
with the Len, Right, Left, and mid functions and I have...
|
by: Ant |
last post by:
I have a home-grown Wiki that I created as an excercise, with it's own
wiki markup (actually just a clone of the Trac wiki markup). The wiki
text parser I wrote works nicely, but makes heavy use of...
|
by: viv342 |
last post by:
i am a beginner in c,c++.i wanted to know that what is the benifit of
declaring the prototype of a function earlier and defining it later
rather than defining it earlier
|
by: Trent |
last post by:
Running this I see that on first run, both bubble and selection sort have 9
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?
Also bsort and Ssort have...
|
by: Chad |
last post by:
Excercise 6-5
Write a functon undef that will remove a name and defintion from the
table maintained by lookup and install.
Code:
unsigned hash(char *s);
void undef(char *s)
|
by: tshad |
last post by:
Using VS 2003, I am trying to take a class that I created to create new
variable types to handle nulls and track changes to standard variable types.
This is for use with database variables. This...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
