Some homies they be sayin’ recursion is Teh Evulz. Well, check this
out. This program be recursing to the max, yo.

Peace.

----
/*
Generate permutations of a list of items.
Pass a list of arbitary words as command arguments, and this
program will print out all possible orderings of them.
*/

#include <iso646.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

typedef void (*permute_action)
(
const char * const * words
);

void permute
(
unsigned int nrwords,
const char * const * words,
permute_action action
)
{
if (nrwords > 0)
{
const char ** const permbuf = (const char **)malloc(nrwords * sizeof(char *));
bool * const used = (bool *)malloc(nrwords);
for (unsigned int i = 0; i < nrwords; ++i)
{
used[i] = false;
} /*for*/

void permute1
(
unsigned int depth
)
{
if (depth < nrwords)
{
for (unsigned int i = 0; i < nrwords; ++i)
{
if (not used[i])
{
permbuf[depth] = words[i];
used[i] = true;
permute1(depth + 1);
used[i] = false;
} /*if*/
} /*for*/
}
else
{
action(permbuf);
} /*if*/
} /*permute1*/

permute1(0);

free(permbuf);
free(used);
} /*if*/
} /*permute*/

int main
(
int argc,
char ** argv
)
{
const unsigned int nrwords = argc - 1;
unsigned int count = 0;

void collect
(
const char * const * words
)
{
count += 1;
fprintf(stdout, "[%d](", count);
for (unsigned int i = 0; i < nrwords; ++i)
{
if (i != 0)
{
fputs(", ", stdout);
} /*if*/
fputs(words[i], stdout);
} /*for*/
fputs(")\n", stdout);
} /*collect*/

permute
(
/*nrwords =*/ nrwords,
/*words =*/ (const char * const * )(argv + 1),
/*permute_action =*/ (permute_action)collect
);

fprintf(stdout, "Nr found: %d\n", count);
} /*main*/

Lawrence D'Oliveiro wrote:
> Some homies they be sayin’ recursion is Teh Evulz. Well, check this
> out. This program be recursing to the max, yo.
>
> Peace.
>
> ----
> /*
> Generate permutations of a list of items.
> Pass a list of arbitary words as command arguments, and this
> program will print out all possible orderings of them.
> */
>
> #include <iso646.h>
> #include <stdbool.h>
> #include <stdlib.h>
> #include <stdio.h>
>
> typedef void (*permute_action)
> (
> const char * const * words
> );
>
> void permute
> (
> unsigned int nrwords,
> const char * const * words,
> permute_action action
> )
> {
> if (nrwords > 0)
> {
> const char ** const permbuf = (const char **)malloc(nrwords * sizeof(char *));
> bool * const used = (bool *)malloc(nrwords);
> for (unsigned int i = 0; i < nrwords; ++i)
> {
> used[i] = false;
> } /*for*/
>
> void permute1
> (
> unsigned int depth
> )
> {
> if (depth < nrwords)
> {
> for (unsigned int i = 0; i < nrwords; ++i)
> {
> if (not used[i])
> {
> permbuf[depth] = words[i];
> used[i] = true;
> permute1(depth + 1);
> used[i] = false;
> } /*if*/
> } /*for*/
> }
> else
> {
> action(permbuf);
> } /*if*/
> } /*permute1*/
>
> permute1(0);
>
> free(permbuf);
> free(used);
> } /*if*/
> } /*permute*/
>
> int main
> (
> int argc,
> char ** argv
> )
> {
> const unsigned int nrwords = argc - 1;
> unsigned int count = 0;
>
> void collect
> (
> const char * const * words
> )
> {
> count += 1;
> fprintf(stdout, "[%d](", count);
> for (unsigned int i = 0; i < nrwords; ++i)
> {
> if (i != 0)
> {
> fputs(", ", stdout);
> } /*if*/
> fputs(words[i], stdout);
> } /*for*/
> fputs(")\n", stdout);
> } /*collect*/
>
> permute
> (
> /*nrwords =*/ nrwords,
> /*words =*/ (const char * const * )(argv + 1),
> /*permute_action =*/ (permute_action)collect
> );
>
> fprintf(stdout, "Nr found: %d\n", count);
> } /*main*/
>
okay, there are some class of things that suit good for recursion - and
its probably good to spot whose they are

On 07.04.2024 11:52, fir wrote:
>>
> okay, there are some class of things that suit good for recursion - and
> its probably good to spot whose they are

All iterations. (So, basically all code we typically write with 'for'
and 'while' loops.) For example. Plus all the things where emulation
with non-recursive means is cumbersome and complex. (Like operating
on recursive data structures like trees.)

Actually, you can formally derive the iterative constructs from [a
subset of] the recursive ones (by introducing variables and loops).

It makes a difference where one comes from. If folks learned coding
from imperative languages they have more problems with a functional
view (and also with recursion, it seems). Here, with "C", we're more
used to 'while' loops and variables, I think.

Janis

On Tue, 9 Apr 2024 10:25:46 +0200, Janis Papanagnou wrote:

> If folks learned coding from imperative languages they have more
> problems with a functional view (and also with recursion, it seems).

One of the first few books I ever read on Comp Sci (while still at school,
back when schools didn’t have computers) was “A Comparative Study Of
Programming Languages” by Bryan Higman. In one of the chapters, I came
across the concept of recursion. I also came across Ackermann’s Function.

Let’s just say that, after staring into that abyss, nothing about
recursion could possibly scare me, ever again ...

> /*
> Generate permutations of a list of items.
> Pass a list of arbitary words as command arguments, and this program
> will print out all possible orderings of them.
> */

Example run:

./permute a b c

Output:

[1](a, b, c)
[2](a, c, b)
[3](b, a, c)
[4](b, c, a)
[5](c, a, b)
[6](c, b, a)
Nr found: 6

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> On 07.04.2024 11:52, fir wrote:
>>>
>> okay, there are some class of things that suit good for recursion - and
>> its probably good to spot whose they are
>
> All iterations. (So, basically all code we typically write with 'for'
> and 'while' loops.) For example. Plus all the things where emulation
> with non-recursive means is cumbersome and complex. (Like operating
> on recursive data structures like trees.)
>
> Actually, you can formally derive the iterative constructs from [a
> subset of] the recursive ones (by introducing variables and loops).
>
> It makes a difference where one comes from. If folks learned coding
> from imperative languages they have more problems with a functional
> view (and also with recursion, it seems). Here, with "C", we're more
> used to 'while' loops and variables, I think.

The language used is key. I would not say that recursion is a good fit
for "all iterations" when using C. It's significant (or at least note
worthy) that the code in the original post was not ISO C and re-writing
it in ISO C would show up some of the issues involved, though this task
is still a good fit for an explicitly recursive solution.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>
>> On 07.04.2024 11:52, fir wrote:
>>>>
>>> okay, there are some class of things that suit good for recursion - and
>>> its probably good to spot whose they are
>>
>> All iterations. (So, basically all code we typically write with 'for'
>> and 'while' loops.) For example. Plus all the things where emulation
>> with non-recursive means is cumbersome and complex. (Like operating
>> on recursive data structures like trees.)
>>
>> Actually, you can formally derive the iterative constructs from [a
>> subset of] the recursive ones (by introducing variables and loops).
>>
>> It makes a difference where one comes from. If folks learned coding
>> from imperative languages they have more problems with a functional
>> view (and also with recursion, it seems). Here, with "C", we're more
>> used to 'while' loops and variables, I think.
>
> The language used is key. I would not say that recursion is a good fit
> for "all iterations" when using C. It's significant (or at least note
> worthy) that the code in the original post was not ISO C and re-writing
> it in ISO C would show up some of the issues involved, though this task
> is still a good fit for an explicitly recursive solution.

Though I want to say that for many application in standard C the use of
a "visitor function" makes the OP's code awkward. Instead, I would
probably iterate over the permutations like this:

#include <stdbool.h>
#include <stdio.h>

void swap(int *a, int *b)
{ int t = *a; *a = *b; *b = t;
}

bool next_perm(int n, int *p)
{ int i = n - 2;
while (i >= 0 && p[i] >= p[i+1]) i--;
// i is now -1 or the largest index with p[i] < p[i+1]
if (i < 0)
return false;
int j = n - 1;
while (p[j] <= p[i]) j--;
// j is now the largest index > i with p[j] > p[i]
swap(&p[i], &p[j]);
// reverse p[i+1] ... p[n-1]
int l = i, h = n;
while (++l < --h)
swap(&p[l], &p[h]);
return true;
}

int main(int argc, char **argv)
{ if (argc > 1) {
int n = argc - 1, idx[n];
for (int i = 0; i < n; i++)
idx[i] = i;
do for (int i = 0; i < n; i++)
printf("%s%s", argv[idx[i] + 1], i == n-1 ? "\n" : " ");
while (next_perm(n, idx));
}
}

--
Ben.

On 09.04.2024 10:43, Lawrence D'Oliveiro wrote:
>
> One of the first few books I ever read on Comp Sci (while still at school,
> back when schools didn’t have computers) was “A Comparative Study Of
> Programming Languages” by Bryan Higman. In one of the chapters, I came
> across the concept of recursion. I also came across Ackermann’s Function.
>
> Let’s just say that, after staring into that abyss, nothing about
> recursion could possibly scare me, ever again ...

Well, Ackermann is a good example how to scare folks - especially
if folks implement it straightforward recursively, then running it
and waiting for termination. :-)

But there's also less complex algorithms, like Fibonacci, that have
a bad runtime complexity if implemented in a trivial way. Though that
depends on how you actually implement it[*] and it's not an inherent
[bad] property of recursion (as sometimes wrongly assumed).

Janis

[*] I once wrote (for an "obfuscated Awk" post) the usual definition
(with some nasty side-effects, granted), which basically was

func __(_){return _>2?__(--_)+__(--_):1}

The (for this thread) noteworthy detail is that you can transform the
function to

func ___(_) { return __(_,x^x,x^x^x) }
func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }

which is also very fast for larger arguments, while the implementation
still being within the (non-imperative) recursive functions paradigm.

PS: I hope *this* scared you at least a bit, since that was one of the
original purposes of the post. ;-)

PPS: Rewrite to "C" left as an exercise to the reader.

On 09/04/2024 09:43, Lawrence D'Oliveiro wrote:
> On Tue, 9 Apr 2024 10:25:46 +0200, Janis Papanagnou wrote:
>
>> If folks learned coding from imperative languages they have more
>> problems with a functional view (and also with recursion, it seems).
>
> One of the first few books I ever read on Comp Sci (while still at school,
> back when schools didn’t have computers) was “A Comparative Study Of
> Programming Languages” by Bryan Higman. In one of the chapters, I came
> across the concept of recursion. I also came across Ackermann’s Function.
>
> Let’s just say that, after staring into that abyss, nothing about
> recursion could possibly scare me, ever again ...

This one is a bit scarier:

https://en.wikipedia.org/wiki/Man_or_boy_test

Although normally requiring closures, there are many implementations
here that work around that, including for C:

https://rosettacode.org/wiki/Man_or_boy_test

There is also a C version that relies on gcc's (gnuC) extensions for
nested function, but when I tested it, it was nearly 200 times slower
than plain C.

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> On 09.04.2024 10:43, Lawrence D'Oliveiro wrote:
>>
>> One of the first few books I ever read on Comp Sci (while still at school,
>> back when schools didn’t have computers) was “A Comparative Study Of
>> Programming Languages” by Bryan Higman. In one of the chapters, I came
>> across the concept of recursion. I also came across Ackermann’s Function.
>>
>> Let’s just say that, after staring into that abyss, nothing about
>> recursion could possibly scare me, ever again ...
>
> Well, Ackermann is a good example how to scare folks - especially
> if folks implement it straightforward recursively, then running it
> and waiting for termination. :-)

Ackemann's function in FORTRAN (which had no recursion in those days)
used to be a student programming assignment. Not so much scary as a
good learning exercise.

> But there's also less complex algorithms, like Fibonacci, that have
> a bad runtime complexity if implemented in a trivial way. Though that
> depends on how you actually implement it[*] and it's not an inherent
> [bad] property of recursion (as sometimes wrongly assumed).

Yes. Haskell's

fib = 1 : 1 : zipWith (+) fib (tail fib)

is (in Haskell terms) quite efficient.

> [*] I once wrote (for an "obfuscated Awk" post) the usual definition
> (with some nasty side-effects, granted), which basically was
>
> func __(_){return _>2?__(--_)+__(--_):1}
>
> The (for this thread) noteworthy detail is that you can transform the
> function to
>
> func ___(_) { return __(_,x^x,x^x^x) }
> func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }

The trouble with AWK (without gawk's -M) is that functions like this
just start to give a wrong, but plausibly sized, result. For example
___(80) is 23416728348467684 when it should be 23416728348467685.

--
Ben.

On 09.04.2024 16:27, Ben Bacarisse wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>>
>> func ___(_) { return __(_,x^x,x^x^x) }
>> func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }
>
> The trouble with AWK (without gawk's -M) is that functions like this
> just start to give a wrong, but plausibly sized, result. For example
> ___(80) is 23416728348467684 when it should be 23416728348467685.

A general issue with functions and arithmetic producing "too large"
numbers with languages and systems that don't support them. Yes.

I'd prefer at least an error indication, though, and not a silent
overflow.

Janis

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
> On 09.04.2024 16:27, Ben Bacarisse wrote:
>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>>>
>>> func ___(_) { return __(_,x^x,x^x^x) }
>>> func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }
>>
>> The trouble with AWK (without gawk's -M) is that functions like this
>> just start to give a wrong, but plausibly sized, result. For example
>> ___(80) is 23416728348467684 when it should be 23416728348467685.
>
> A general issue with functions and arithmetic producing "too large"
> numbers with languages and systems that don't support them. Yes.
>
> I'd prefer at least an error indication, though, and not a silent
> overflow.

If I understand correctly, it's not overflow, it's quiet loss of
precision.

awk doesn't normally distinguish between integer and floating-point
numbers, and uses FP to represent integers. A computation that should
yield 23416728348467685 doesn't overflow, but it quietly yields
23416728348467684. (`gawk -M` supports arbitrary precision integer
arithmetic.)

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Medtronic
void Void(void) { Void(); } /* The recursive call of the void */

On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:

> It's significant (or at least note worthy) that the code in the
> original post was not ISO C ...

Interesting that GCC’s C compiler allows nested routine definitions,
but the C++ compiler does not.

> and re-writing it in ISO C would show up some of the issues involved
> ...

Ask and you shall receive ...

/*
Generate permutations of a list of items.
Pass a list of arbitary words as command arguments, and this
program will print out all possible orderings of them.
*/

#include <iso646.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

typedef void (*permute_action)
(
unsigned int nrwords,
const char * const * words,
void * arg
);

struct permute_ctx
{
unsigned int nrwords;
const char * const * words;
permute_action action;
void * action_arg;
const char ** permbuf;
bool * used;
} /*permute_ctx*/;

static void permute1
(
struct permute_ctx * ctx,
unsigned int depth
)
{
if (depth < ctx->nrwords)
{
for (unsigned int i = 0; i < ctx->nrwords; ++i)
{
if (not ctx->used[i])
{
ctx->permbuf[depth] = ctx->words[i];
ctx->used[i] = true;
permute1(ctx, depth + 1);
ctx->used[i] = false;
} /*if*/
} /*for*/
}
else
{
ctx->action(ctx->nrwords, ctx->permbuf, ctx->action_arg);
} /*if*/
} /*permute1*/

void permute
(
unsigned int nrwords,
const char * const * words,
permute_action action,
void * action_arg
)
{
if (nrwords > 0)
{
struct permute_ctx ctx;
ctx.nrwords = nrwords;
ctx.words = words;
ctx.action = action;
ctx.action_arg = action_arg;
ctx.permbuf = (const char **)malloc(nrwords * sizeof(char *));
ctx.used = (bool *)malloc(nrwords);
for (unsigned int i = 0; i < nrwords; ++i)
{
ctx.used[i] = false;
} /*for*/

permute1(&ctx, 0);

free(ctx.permbuf);
free(ctx.used);
} /*if*/
} /*permute*/

struct main_ctx
{
FILE * out;
unsigned int count;
} /*main_ctx*/;

void collect
(
unsigned int nrwords,
const char * const * words,
struct main_ctx * ctx
)
{
ctx->count += 1;
fprintf(ctx->out, "[%d](", ctx->count);
for (unsigned int i = 0; i < nrwords; ++i)
{
if (i != 0)
{
fputs(", ", ctx->out);
} /*if*/
fputs(words[i], ctx->out);
} /*for*/
fputs(")\n", ctx->out);
} /*collect*/

int main
(
int argc,
char ** argv
)
{
struct main_ctx ctx;
ctx.out = stdout;
ctx.count = 0;

permute
(
/*nrwords =*/ argc - 1,
/*words =*/ (const char * const * )(argv + 1),
/*permute_action =*/ (permute_action)collect,
/*action_arg =*/ (void *)&ctx
);

fprintf(stdout, "Nr found: %d\n", ctx.count);
} /*main*/

On 4/9/2024 6:50 PM, Lawrence D'Oliveiro wrote:
> On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:
>
>> It's significant (or at least note worthy) that the code in the
>> original post was not ISO C ...
>
> Interesting that GCC’s C compiler allows nested routine definitions,
> but the C++ compiler does not.
>
>> and re-writing it in ISO C would show up some of the issues involved
>> ...
>
> Ask and you shall receive ...
[...]

Are you an AI?

On 09.04.2024 22:31, Keith Thompson wrote:
> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>> On 09.04.2024 16:27, Ben Bacarisse wrote:
>>
>> A general issue with functions and arithmetic producing "too large"
>> numbers with languages and systems that don't support them. Yes.
>>
>> I'd prefer at least an error indication, though, and not a silent
>> overflow.
>
> If I understand correctly, it's not overflow, it's quiet loss of
> precision.

Yes, you are right.

Janis

On 10/04/2024 03:50, Lawrence D'Oliveiro wrote:
> On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:
>
>> It's significant (or at least note worthy) that the code in the
>> original post was not ISO C ...
>
> Interesting that GCC’s C compiler allows nested routine definitions,
> but the C++ compiler does not.

It is an old extension, going back to when gcc barely (if at all)
supported C++. The compiler middle-end had to have support for nested
functions for languages like Pascal, Module 2 and Ada (I believe Ada is
the only one of these that stuck around in gcc mainline, but other
language front-ends have been made outside the main tree). Someone
thought it might be a useful feature in C too, and perhaps something
that would catch on in the standards (several early gcc extensions ended
up standardised in C99).

It is not much used in practice, AFAIK. For some cases the code
generation for nested functions was fine and straight-forward. In other
cases, however, it required a trampoline generated on the stack, and
that became a real pain once non-executable stacks came into fashion.

Nested functions were never as interesting for C++ as you already have
better mechanisms for controlling scope and data access - classes and
their methods, including nested classes. And once lambdas joined the
party in C++11 there was absolutely no reason to have nested functions -
there is nothing (AFAIK) that you could do with nested functions that
you can't do at least as well, and often better, with lambdas.

On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:

> It is not much used in practice, AFAIK. For some cases the code
> generation for nested functions was fine and straight-forward. In other
> cases, however, it required a trampoline generated on the stack, and
> that became a real pain once non-executable stacks came into fashion.

That would be true of those other languages that require the feature, too.

> Nested functions were never as interesting for C++ as you already have
> better mechanisms for controlling scope and data access - classes and
> their methods, including nested classes.

Python does both. Just because you have classes doesn’t mean functions
can’t be first-class objects, too.

On 10/04/2024 09:52, Lawrence D'Oliveiro wrote:
> On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:
>
>> It is not much used in practice, AFAIK. For some cases the code
>> generation for nested functions was fine and straight-forward. In other
>> cases, however, it required a trampoline generated on the stack, and
>> that became a real pain once non-executable stacks came into fashion.
>
> That would be true of those other languages that require the feature, too.
>

There may be other differences in the languages that reduce that effect
- or it could be a problem there too. I don't know the details.
(Perhaps those on an Ada newsgroup would know better.)

The problem with trampolines comes about when you want to take the
address of the nested function and use that outside of the surrounding
function, while you also have variables captured by reference.

>> Nested functions were never as interesting for C++ as you already have
>> better mechanisms for controlling scope and data access - classes and
>> their methods, including nested classes.
>
> Python does both. Just because you have classes doesn’t mean functions
> can’t be first-class objects, too.

True. But Python is a very different language from C++. In Python, not
only are functions objects in themselves, but so are classes (the
definition of the classes, rather than just instances). Python is a lot
more "meta" than C++.

Basically, anything you could do with a nested function in gcc C you can
do in C++:

int sum_square(int x, int y) {
int square(z) {
return z * z;
}
return square(x) + square(y);
}

int sum_square(int x, int y) {
auto square = [](int z) {
return z * z;
}
return square(x) + square(y);
}

On 10/04/2024 10:18, David Brown wrote:
> On 10/04/2024 09:52, Lawrence D'Oliveiro wrote:
>> On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:
>>
>>> It is not much used in practice, AFAIK.  For some cases the code
>>> generation for nested functions was fine and straight-forward.  In other
>>> cases, however, it required a trampoline generated on the stack, and
>>> that became a real pain once non-executable stacks came into fashion.
>>
>> That would be true of those other languages that require the feature,
>> too.
>>
>
> There may be other differences in the languages that reduce that effect
> - or it could be a problem there too.  I don't know the details.
> (Perhaps those on an Ada newsgroup would know better.)
>
> The problem with trampolines comes about when you want to take the
> address of the nested function and use that outside of the surrounding
> function, while you also have variables captured by reference.
>
>>> Nested functions were never as interesting for C++ as you already have
>>> better mechanisms for controlling scope and data access - classes and
>>> their methods, including nested classes.
>>
>> Python does both. Just because you have classes doesn’t mean functions
>> can’t be first-class objects, too.
>
> True.  But Python is a very different language from C++.  In Python, not
> only are functions objects in themselves, but so are classes (the
> definition of the classes, rather than just instances).  Python is a lot
> more "meta" than C++.
>
> Basically, anything you could do with a nested function in gcc C you can
> do in C++:
>
> int sum_square(int x, int y) {
>     int square(z) { // int z ??
>         return z * z;
>     }
>     return square(x) + square(y);
> }

That's not an interesting use of a local function! You can move square()
outside, and it would still work, putting aside any clashes with
existing names called 'square'.

The challenges of local functions are to do with accessing transient
variables belonging to their enclosing function. Especially when a
reference to the local function is called from outside the lexical scope
of the enclosing function, with extra difficulties when the enclosing
function is no longer active.

> int sum_square(int x, int y) {
>     auto square = [](int z) {
>         return z * z;
>     }
>     return square(x) + square(y);
> }

What's the significance of the '[]' here?

On 10.04.2024 11:18, David Brown wrote:
> On 10/04/2024 09:52, Lawrence D'Oliveiro wrote:
>> On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:
>
> The problem with trampolines comes about when you want to take the
> address of the nested function and use that outside of the surrounding
> function, while you also have variables captured by reference.

Sounds like a C-issue (not one of nesting functions). Usually I use
nested functions to have and use them locally and not in surrounding
or global scope. - I'd expect a C compiler to notice such situations.

>
>>> Nested functions were never as interesting for C++ as you already have
>>> better mechanisms for controlling scope and data access - classes and
>>> their methods, including nested classes.
>>
>> Python does both. Just because you have classes doesn’t mean functions
>> can’t be first-class objects, too.

Indeed.

(You could also omit use of C++ templates completely and emulate them
with class inheritance; nonetheless they are useful and convenient to
have them supported as concept as well. - Just for another example.)

Janis

David Brown <david.brown@hesbynett.no> writes:
>On 10/04/2024 09:52, Lawrence D'Oliveiro wrote:
>> On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:
>>
>>> It is not much used in practice, AFAIK. For some cases the code
>>> generation for nested functions was fine and straight-forward. In other
>>> cases, however, it required a trampoline generated on the stack, and
>>> that became a real pain once non-executable stacks came into fashion.
>>
>> That would be true of those other languages that require the feature, too.
>>
>
>There may be other differences in the languages that reduce that effect
>- or it could be a problem there too. I don't know the details.
>(Perhaps those on an Ada newsgroup would know better.)
>
>The problem with trampolines comes about when you want to take the
>address of the nested function and use that outside of the surrounding
>function, while you also have variables captured by reference.

The Burroughs Algol systems used something called lex levels to
handle nested functions.

https://en.wikipedia.org/wiki/Burroughs_Large_Systems#Stack_architecture

On 10/04/2024 14:42, bart wrote:
> On 10/04/2024 10:18, David Brown wrote:
>> On 10/04/2024 09:52, Lawrence D'Oliveiro wrote:
>>> On Wed, 10 Apr 2024 09:11:49 +0200, David Brown wrote:
>>>
>>>> It is not much used in practice, AFAIK.  For some cases the code
>>>> generation for nested functions was fine and straight-forward.  In
>>>> other
>>>> cases, however, it required a trampoline generated on the stack, and
>>>> that became a real pain once non-executable stacks came into fashion.
>>>
>>> That would be true of those other languages that require the feature,
>>> too.
>>>
>>
>> There may be other differences in the languages that reduce that
>> effect - or it could be a problem there too.  I don't know the
>> details. (Perhaps those on an Ada newsgroup would know better.)
>>
>> The problem with trampolines comes about when you want to take the
>> address of the nested function and use that outside of the surrounding
>> function, while you also have variables captured by reference.
>>
>>>> Nested functions were never as interesting for C++ as you already have
>>>> better mechanisms for controlling scope and data access - classes and
>>>> their methods, including nested classes.
>>>
>>> Python does both. Just because you have classes doesn’t mean functions
>>> can’t be first-class objects, too.
>>
>> True.  But Python is a very different language from C++.  In Python,
>> not only are functions objects in themselves, but so are classes (the
>> definition of the classes, rather than just instances).  Python is a
>> lot more "meta" than C++.
>>
>> Basically, anything you could do with a nested function in gcc C you
>> can do in C++:
>>
>> int sum_square(int x, int y) {
>>      int square(z) {               // int z ??
>>          return z * z;
>>      }
>>      return square(x) + square(y);
>> }
>
> That's not an interesting use of a local function! You can move square()
> outside, and it would still work, putting aside any clashes with
> existing names called 'square'.

Sure. It was not intended to be anything other than a very simple
nested function written in gcc C extension syntax, and the same thing
written in standard C++, to demonstrate how you can write nested
functions in C++ without this extension. Local functions without
capturing local data are perhaps not interesting, but they can be neat
from the viewpoint of limiting the scope of identifiers.

>
> The challenges of local functions are to do with accessing transient
> variables belonging to their enclosing function.

Yes. And you can do that with the gcc extension, and also with C++ lambdas.

> Especially when a
> reference to the local function is called from outside the lexical scope
> of the enclosing function, with extra difficulties when the enclosing
> function is no longer active.
>

These are the kinds of situations where the gcc extension needs to use
trampolines. C++ lambdas are closures, and can hold more information -
each lambda is its own type, and the size of that type can be different
for different lambdas (it can include pointers to the variables captured
by reference, for example). This makes lambdas much easier, safer and
more efficient to use within a translation unit - but makes them a bit
more fiddly if they capture local variables and you need to pass them to
something defined outside the current TU.

(You can't use any local function outside the scope of the enclosing
code if the local function has reference captures - that applies to all
types of local functions.)

>
>
>> int sum_square(int x, int y) {
>>      auto square = [](int z) {
>>          return z * z;
>>      }
>>      return square(x) + square(y);
>> }
>
> What's the significance of the '[]' here?
>

It's the syntax for a C++ lambda. You can put captures in there, or
leave it empty for no captures.

Just for your entertainment, with C++ lambdas this is now legal code:

void foo(void) {
[](){}();
}

(It defines a lambda with no captures and no parameters, that does
nothing, then it invokes it.)

On 2024-04-10, David Brown <david.brown@hesbynett.no> wrote:
> On 10/04/2024 03:50, Lawrence D'Oliveiro wrote:
>> On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:
>>
>>> It's significant (or at least note worthy) that the code in the
>>> original post was not ISO C ...
>>
>> Interesting that GCC’s C compiler allows nested routine definitions,
>> but the C++ compiler does not.
>
> It is an old extension, going back to when gcc barely (if at all)
> supported C++. The compiler middle-end had to have support for nested
> functions for languages like Pascal, Module 2 and Ada (I believe Ada is
> the only one of these that stuck around in gcc mainline, but other
> language front-ends have been made outside the main tree). Someone
> thought it might be a useful feature in C too, and perhaps something
> that would catch on in the standards (several early gcc extensions ended
> up standardised in C99).
>
> It is not much used in practice, AFAIK. For some cases the code
> generation for nested functions was fine and straight-forward. In other
> cases, however, it required a trampoline generated on the stack, and
> that became a real pain once non-executable stacks came into fashion.
>
> Nested functions were never as interesting for C++ as you already have
> better mechanisms for controlling scope and data access - classes and
> their methods, including nested classes. And once lambdas joined the

Higher level languages like Common Lisp show that you want both;
even though theoretically you can implement OOP with lambdas, or
simulate some aspects of lambdas with OOP (particularly if your OOP
supports callable objects).

> party in C++11 there was absolutely no reason to have nested functions -
> there is nothing (AFAIK) that you could do with nested functions that
> you can't do at least as well, and often better, with lambdas.

GNU C nested functions don't require any special syntax (other than teh
fact of allowing a function definition inside a statement block). They
implicitly capture the actual variables in the surrounding scope using
ordinary C function syntax.

The address of a GNU C nested function is regular function pointer;
you can pass it to qsort and bsearch.

In fact, you can pass a GNU C nested function into a library that was
not even compiled with GCC. If it understand the calling conventions of
function pointers, it can call the function.

However, GNU C nested functions are "downward funarg" only, which
is a pretty severe limitation. (Worse, GNU C nested function can
escape from a scope in spite of being dowward funarg only,
causing undefined behavior when they are called.)

(The "downward funarg" terminology is from ancient Lisp or Algol
literature, means "downward (only) functional argument": a function that
can be used as an argument to function, but not returned; i.e. passed
downward only.)

The downward funarg restriction has benefits too; such functions do not
require any dynamic allocation at all. The closed-over variables are
referenced directly in their still-living stack frame.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

> On Tue, 09 Apr 2024 11:44:23 +0100, Ben Bacarisse wrote:
>
>> It's significant (or at least note worthy) that the code in the
>> original post was not ISO C ...
>
> Interesting that GCC?s C compiler allows nested routine definitions,
> but the C++ compiler does not.
>
>> and re-writing it in ISO C would show up some of the issues involved
>> ...
>
> Ask and you shall receive ...
>
> /*
> Generate permutations of a list of items.
> Pass a list of arbitary words as command arguments, and this
> program will print out all possible orderings of them.
> */
>
> #include <iso646.h>
> #include <stdbool.h>
> #include <stdlib.h>
> #include <stdio.h>
>
> typedef void (*permute_action)
> (
> unsigned int nrwords,
> const char * const * words,
> void * arg
> );
>
> struct permute_ctx
> {
> unsigned int nrwords;
> const char * const * words;
> permute_action action;
> void * action_arg;
> const char ** permbuf;
> bool * used;
> } /*permute_ctx*/;
>
> static void permute1
> (
> struct permute_ctx * ctx,
> unsigned int depth
> )
> {
> if (depth < ctx->nrwords)
> {
> for (unsigned int i = 0; i < ctx->nrwords; ++i)
> {
> if (not ctx->used[i])
> {
> ctx->permbuf[depth] = ctx->words[i];
> ctx->used[i] = true;
> permute1(ctx, depth + 1);
> ctx->used[i] = false;
> } /*if*/
> } /*for*/
> }
> else
> {
> ctx->action(ctx->nrwords, ctx->permbuf, ctx->action_arg);
> } /*if*/
> } /*permute1*/
>
> void permute
> (
> unsigned int nrwords,
> const char * const * words,
> permute_action action,
> void * action_arg
> )
> {
> if (nrwords > 0)
> {
> struct permute_ctx ctx;
> ctx.nrwords = nrwords;
> ctx.words = words;
> ctx.action = action;
> ctx.action_arg = action_arg;
> ctx.permbuf = (const char **)malloc(nrwords * sizeof(char *));
> ctx.used = (bool *)malloc(nrwords);
> for (unsigned int i = 0; i < nrwords; ++i)
> {
> ctx.used[i] = false;
> } /*for*/
>
> permute1(&ctx, 0);
>
> free(ctx.permbuf);
> free(ctx.used);
> } /*if*/
> } /*permute*/
>
> [...]

More complicated than it needs to be. Besides that, in a beauty
contest this coding style would lose out even to Frankenstein.

Simpler:

#include <stdlib.h>
#include <string.h>

typedef void *Voidp;
typedef struct array_CB_s ArrayCB;
struct array_CB_s {
void (*run)( ArrayCB *cb, unsigned n, const Voidp[ n ] );
};

static void permute_r( unsigned n, Voidp[n], unsigned, ArrayCB * );
static void voidp_exchange( Voidp [], unsigned, unsigned );

void
permute( unsigned n, const Voidp in_array[n], ArrayCB *cb ){
for( Voidp *pva = malloc( n * sizeof *pva ); pva; pva = 0 ){
memcpy( pva, in_array, n * sizeof *pva );
permute_r( n, pva, n, cb );
free( pva );
}
}

void
permute_r( unsigned n, Voidp values[n], unsigned k, ArrayCB *cb ){
for( unsigned i = 0; i < k; i++ ){
voidp_exchange( values, n-k, n-k+i );
permute_r( n, values, k-1, cb );
voidp_exchange( values, n-k, n-k+i );
}
if( k == 1 ) cb->run( cb, n, values );
}

void
voidp_exchange( Voidp values[], unsigned i, unsigned j ){
if( i != j ){
Voidp pi = values[i], pj = values[j];
values[i] = pj, values[j] = pi;
}
}

On 2024-04-10, David Brown <david.brown@hesbynett.no> wrote:
> Basically, anything you could do with a nested function in gcc C you can
> do in C++:

Except pass that lambda to another module that expects a simple function
pointer.

That's not just C libraries. There is a foreign function ecosystem based
on the conventions of C. If you have a function pointer, you can pass it
into any high level language that supports C interpo, and it can call
that thing.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca