# Programming challenge

Discussion in 'C Programming' started by annalissa, Dec 14, 2009.

1. ### annalissaGuest

annalissa, Dec 14, 2009

2. ### Dann CorbitGuest

In article <hg68kr\$8c5\$>, says...
>
> Hi all,
>
> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
>
> my question is can this be done in C ?

You can perform factorial calculation without recursion or iteration in
any language.

The best answer is table lookup. You can also use Sterling's
approximation. Anything that expands in size at factorial rate will
result in a small table, no matter how precise your number format is.

There are no nameless functions in C, but you could probably do some
lame preprocessor trick or something of that nature if you want to look
especially clever.

Any of the functions used to calculate the gamma function can also be
used, since the factorial function is just the gamma function at
integral points shifted by 1.

Dann Corbit, Dec 14, 2009

3. ### Beej JorgensenGuest

On 12/14/2009 12:54 PM, annalissa wrote:
> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
>
> my question is can this be done in C ?

I'm not a LISP guy, but that non-recursive solution reeks of recursion,
even if it's not strictly recursive. (It looks like, "Let's recursively
produce a series of lambda functions that we multiply together to
produce a factorial"--but I'm not a LISP guy so I could be totally
wrong.) Or to put it another way, you're going to be looping through
those values one way or another, whether you like it or not.

My short painful answer would be: write a C program that interprets LISP
and feed it the LISP program. So, yes, it can be done in C. But can
the same structure be used in the C language? No, not really--unless
there's some clever solution I'm overlooking. Can the preprocessor be
abused into generating the factorial code?

-Beej

Beej Jorgensen, Dec 14, 2009
4. ### Ben BacarisseGuest

annalissa <> writes:

That pages does not have a "factorial without recursion or iteration"
function on it. It links to a page that does have one -- by using
a fixed point combinator.

> my question is can this be done in C ?

Not directly, but the answer to all such questions is, at some level,
always "yes". You could build a combinator reduction engine in C and
you'd then be doing the same in C if you fed in the right combinator
form (in fact, it is surprisingly little code).

If, however, by "this" you mean write almost any function but without
using iteration or recursion then the answer is no.

[I have to add that serious pre-processor abuse might be able to
come close, though I suspect some of the worst tricks would probably
count as recursion.]

--
Ben.

Ben Bacarisse, Dec 14, 2009
5. ### Hallvard B FurusethGuest

Beej Jorgensen writes:
> On 12/14/2009 12:54 PM, annalissa wrote:
>> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
>>
>> my question is can this be done in C ?

>
> I'm not a LISP guy, but that non-recursive solution reeks of recursion,
> even if it's not strictly recursive. (It looks like, "Let's recursively
> produce a series of lambda functions that we multiply together to
> produce a factorial"--but I'm not a LISP guy so I could be totally
> wrong.)

That's right. Maybe a Python solution (without Python lambda
expressions) will look more readable to C programmers:

def U(f):
return f(f)

def fact_nr(f):
def step(n):
return (1 if n == 0 else n * f(f)(n - 1))
return step

print U(fact_nr)(3), U(fact_nr)(5) # prints 6 120

> My short painful answer would be: write a C program that interprets LISP
> and feed it the LISP program. So, yes, it can be done in C. But can
> the same structure be used in the C language?

That use of functions, no: No functions inside functions, and local
variables fact_nr:f and step:n) die when a function exits.

The same program structure more grossly, yes: You can create structs
representing a called function (i.e. a closure), a call to a function
(with a function pointer and maybe arguments), etc, and then some
machinery to call that kind of function -- but you already said that,
"write a C program which interprets LISP"

> No, not really--unless
> there's some clever solution I'm overlooking. Can the preprocessor be
> abused into generating the factorial code?

Nope. It's explicitly defined to not do recursive expansion. You can
write preprocessor macros with the same structure as a recursive call or
iteration, but by spelling out each round/call for as many rounds as you
are intersted in supporting.

/* Factorial macro, works for arguments 0..5 */
#define FACTORIAL(n) (ASSERTZ((n) <= 5) + F5(n))
#define F5(n) ((n) <= 1 ? 1 : (n) * F4((n)-1))
#define F4(n) ((n) <= 1 ? 1 : (n) * F3((n)-1))
#define F3(n) ((n) <= 1 ? 1 : (n) * F2((n)-1))
#define F2(n) ((n) <= 1 ? 1 : (n) * F1((n)-1))
#define F1(n) 1

/* Return 0, but try to force a compile error if !c */
#define ASSERTZ(c) (sizeof(struct { \
int Assert1_[(c) ? 9 : -9]; int Assert2_: (c) ? 9 : -9; }) && 0)

Watch out for "recursive" expansion expanding the previous round's macro
several times though - that can quickly give you a gigabyte-sized
macroexpansion. In that case, you'd have to write a macro which expands
to a set of declarations which declares the local variables for each
iteration/recursive call - and hope the compiler optimizes all that
away. Or expand to an enum declaration, if you can keep the locals in
the range of INT_MIN..INT_MAX.

Of course, all of this as well as the original example is vast overkill
for factorial, but it illustrates the point.

--
Hallvard

Hallvard B Furuseth, Dec 14, 2009
6. ### Eric SosmanGuest

On 12/14/2009 4:26 PM, Dann Corbit wrote:
> In article<hg68kr\$8c5\$>, says...
>>
>> Hi all,
>>
>> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
>>
>> my question is can this be done in C ?

>
> You can perform factorial calculation without recursion or iteration in
> any language.
>
> The best answer is table lookup. You can also use Sterling's
> approximation.[...]

Just in case someone wants to look it up: "Stirling," with
two ayes and no ease.

--
Eric Sosman
lid

Eric Sosman, Dec 14, 2009
7. ### Hallvard B FurusethGuest

I wrote:
> Beej Jorgensen writes:
>> Can the preprocessor be
>> abused into generating the factorial code?

>
> Nope. It's explicitly defined to not do recursive expansion.

....and to detect tricks like calling macros indirectly in order to try
for recursion. (So the halting problem is not a problem for the compiler.)

> You can
> write preprocessor macros with the same structure as a recursive call or
> iteration, but by spelling out each round/call for as many rounds as you
> are intersted in supporting.
>
> (...example snipped...)
> Watch out for "recursive" expansion expanding the previous round's macro
> several times though - that can quickly give you a gigabyte-sized
> macroexpansion. In that case, you'd have to write a macro which expands
> to a set of declarations which declares the local variables for each
> iteration/recursive call - and hope the compiler optimizes all that
> away. Or expand to an enum declaration, if you can keep the locals in
> the range of INT_MIN..INT_MAX.

I mean, to eliminate exponential growth of the macroexpansion. Instead
of expanding the macro twice to compute the same value, expand it once
and stuff the result into a variable or enum constant.

> Of course, all of this as well as the original example is vast overkill
> for factorial, but it illustrates the point.

--
Hallvard

Hallvard B Furuseth, Dec 14, 2009
8. ### GeneGuest

On Dec 14, 3:54 pm, annalissa <> wrote:
> Hi all,
>
>
> my question is can this be done in C ?

On Dec 14, 3:54 pm, annalissa <> wrote:
> Hi all,
>
>
> my question is can this be done in C ?

Of course it can. As is often the case with C, you merely need to pay
attention to a few more details to get the job done:

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

// (define (fact-nr f)
// (lambda (n) (if (zero? n) 1
// (* n ((f f) (- n 1))))))

// activation record for fact
typedef struct fact_s {
struct lambda_s *(*code)(struct fact_s *);
struct fact_s *f;
} FACT;

// activation record for lambda
typedef struct lambda_s {
int (*code) (struct lambda_s *);
struct fact_s *env;
int n;
} LAMBDA;

// forward declarations
int lambda_code(LAMBDA *env);
LAMBDA *fact_code(FACT *env);

// return a fresh lambda activation
LAMBDA *new_lambda(FACT *env)
{
LAMBDA *lambda = malloc(sizeof *lambda);
lambda->code = lambda_code;
lambda->env = env;
return lambda;
}

// call a lambda with given argument n
int call_lambda(LAMBDA *lambda, int n)
{
lambda->n = n;
return lambda->code(lambda);
}

// return a fresh fact activation
FACT *new_fact(void)
{
FACT *fact = malloc(sizeof *fact);
fact->code = fact_code;
return fact;
}

// call a fact with given argument f
LAMBDA *call_fact(FACT *fact, FACT *f)
{
fact->f = f;
fact->code(fact);
}

// code for lambda activation
int lambda_code(LAMBDA *env)
{
return (env->n == 0) ? 1 :
env->n * call_lambda(call_fact(env->env->f,
env->env->f),
env->n - 1);
}

// code for a fact activation
LAMBDA *fact_code(FACT *env)
{
return new_lambda(env);
}

// U-combinator for fact activations
LAMBDA *U(FACT *f)
{
return call_fact(f, f);
}

// try it out
int main(void)
{
FACT *fact = new_fact();
LAMBDA *lambda = U(fact);
printf("fact(3) ==> %d\n", call_lambda(lambda, 3));
printf("fact(5) ==> %d\n", call_lambda(lambda, 5));
return 0;
}

C:\>a.exe
fact(3) ==> 6
fact(5) ==> 120

Gene, Dec 17, 2009
9. ### GeneGuest

On Dec 16, 11:33 pm, Gene <> wrote:
> On Dec 14, 3:54 pm, annalissa <> wrote:
>
> > Hi all,

>

>
> > my question is can this be done in C ?

>
> On Dec 14, 3:54 pm, annalissa <> wrote:
>
> > Hi all,

>

>
> > my question is can this be done in C ?

>
> Of course it can. As is often the case with C, you merely need to pay
> attention to a few more details to get the job done:
>
> #include <stdio.h>
> #include <stdlib.h>
>
> // (define (fact-nr f)
> //   (lambda (n) (if (zero? n) 1
> //                   (* n ((f f) (- n 1))))))
>
> // activation record for fact
> typedef struct fact_s {
>   struct lambda_s *(*code)(struct fact_s *);
>   struct fact_s *f;
>
> } FACT;
>

Rest of code deleted...

If you get the previous post, then try this "optimization," which
notes that no activation record is required for the factorial
function:

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

// with no free variables, fact is just a function
typedef struct lambda_s *FACT();

// the inner lambda needs an activation record (sort of)
typedef struct lambda_s {
int (*code) (struct lambda_s *);
FACT *f;
int n;
} LAMBDA;

int lambda_code(LAMBDA *env);

// fact returns a lambda bound to f
LAMBDA *fact(FACT *f)
{
LAMBDA *lambda = malloc(sizeof *lambda);
lambda->code = lambda_code;
lambda->f = f;
return lambda;
}

int call_lambda(LAMBDA *lambda, int n)
{
lambda->n = n;
return lambda->code(lambda);
}

int lambda_code(LAMBDA *env)
{
return (env->n == 0) ? 1 :
env->n * call_lambda(env->f(env->f), env->n - 1);
}

// U combinator for type FACT
LAMBDA *U(FACT *f)
{
return f(f);
}

int main(void)
{
LAMBDA *lambda = U(fact);
printf("fact(3) ==> %d\n", call_lambda(lambda, 3));
printf("fact(5) ==> %d\n", call_lambda(lambda, 5));
return 0;
}

Gene, Dec 17, 2009
10. ### Beej JorgensenGuest

On 12/16/2009 08:33 PM, Gene wrote:
> Of course it can. As is often the case with C, you merely need to pay
> attention to a few more details to get the job done:
>
> #include <stdio.h>
> [... snip ...]

Terrifyingly awesome.

-Beej

Beej Jorgensen, Dec 17, 2009
11. ### Phil CarmodyGuest

Beej Jorgensen <> writes:
> On 12/16/2009 08:33 PM, Gene wrote:
>> Of course it can. As is often the case with C, you merely need to pay
>> attention to a few more details to get the job done:
>>
>> #include <stdio.h>
>> [... snip ...]

>
> Terrifyingly awesome.

But lambda_code calls code which calls lambda_code, so it's
just recursion via structures containing function pointers.
I thought the purpose was to avoid recursion? (And be completely
pointless.)

Use lisp for lisp, and C for C, that's what I say.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody, Dec 17, 2009
12. ### Antti-Juhani KaijanahoGuest

Gene <> kirjoitti 17.12.2009:
> // activation record for fact
> // activation record for lambda

I'm pretty sure those were actually closures, not activation records. A more
common synonym for the latter is "stack frame", but an activation record can
also reside on the heap.

Impressive, still.

--

Antti-Juhani Kaijanaho, Dec 17, 2009
13. ### Stefan RamGuest

annalissa <> writes:
>my question is can this be done in C ?

I have noticed this thread just 5 minutes ago:
Yes, you can remove direct recursion using
a Y-combinator like approach in C:

#include <stdio.h>

int g( int const i, int( *h )() )
{ return i ? i * h( i - 1, h ) : 1; }

/* This is not the Y combinator,
just a C function called "Y". */
int Y( int const i, int( *g )() )
{ return g( i, g ); }

int factorial( int const i ){ return Y( i, g ); }

int main( void ){ printf( "%d\n", factorial( 5 )); }

/* prints
120
*/

Stefan Ram, Dec 17, 2009
14. ### Ben BacarisseGuest

-berlin.de (Stefan Ram) writes:

> annalissa <> writes:
>>my question is can this be done in C ?

>
> I have noticed this thread just 5 minutes ago:
> Yes, you can remove direct recursion using
> a Y-combinator like approach in C:
>
> #include <stdio.h>
>
> int g( int const i, int( *h )() )
> { return i ? i * h( i - 1, h ) : 1; }
>
> /* This is not the Y combinator,
> just a C function called "Y". */
> int Y( int const i, int( *g )() )
> { return g( i, g ); }
>
> int factorial( int const i ){ return Y( i, g ); }
>
> int main( void ){ printf( "%d\n", factorial( 5 )); }

Y is not needed; it seems only there to complicate matters. If you
define

int factorial( int const i ){ return g( i, g ); }

then the code is a little clearer and it becomes clear that g calls g.
OK, it's called h at the time, but it is still g that is being called!

--
Ben.

Ben Bacarisse, Dec 17, 2009
15. ### Stefan RamGuest

(Richard Tobin) writes:
>>my question is can this be done in C ?

>So I conclude that it is not possible to solve the problem as
>constrained above in C.

I am not sure to which problem the word »this« as quoted
above refers to. Maybe someone can give a wording of the
problem, so that it is definitely defined about which
problem we are actually talking.

PS: In my preceding post, I inadvertently seem to have
deleted the reference header line as this sometime happen
when I edit my posts. Sorry, I will try to keep this line
intact in the future.

Stefan Ram, Dec 18, 2009
16. ### Richard TobinGuest

In article <hg68kr\$8c5\$>, annalissa <> wrote:
>http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
>
>my question is can this be done in C ?

Sorry I'm coming in to this late.

If you want to calculate N factorial by the natural method of
multiplying tigether the numbers from 1 to N, you're obviously going
to be doing a variable number of multiplications. If we are willing
to bound N (which is implicit, for a given C implementation, in any
solution using fixed-size integers), we can write a program with no
iteration or recursion simply by enumerating the possible values of N:

int fact=1;
if(N == 1)
return fact;
f *= 2;
if(N == 2)
return fact;
...

If we wish to write as if N is unbounded, we must have some construct
that provides an unbounded variable number of operations. Either we
will use this operation explicitly, or it will be concealed in the C
library. As far as I can see, the only operations of this nature in C
are the looping constructs, goto, and recursion. I cannot see any
standard library function that can be persuaded to do the required
multiplications.

(It might be possible to somehow set up an array in such a way that
calling, say, qsort on it would do something isomorphic to multiplication,
but we would then have the problem of setting up the array.)

Of course you could write a library that implemented, say, combinator
reduction, but that just moves the problem into your library.

So I conclude that it is not possible to solve the problem as
constrained above in C.

-- Richard

--
Please remember to mention me / in tapes you leave behind.

Richard Tobin, Dec 18, 2009
17. ### janusGuest

Stefan,

I understand the the flow of your code but not the "spirit" of it.
Could you explain it a little bit?

Regards,
Janus
On Dec 17, 6:23 pm, -berlin.de (Stefan Ram) wrote:
> annalissa <> writes:
> >my question is can this be done in C ?

>
>   I have noticed this thread just 5 minutes ago:
>   Yes, you can remove direct recursion using
>   a Y-combinator like approach in C:
>
> #include <stdio.h>
>
> int g( int const i, int( *h )() )
> { return i ? i * h( i - 1, h ) : 1; }
>
> /* This is not the Y combinator,
> just a C function called "Y". */
> int Y( int const i, int( *g )() )
> { return g( i, g ); }
>
> int factorial( int const i ){ return Y( i, g ); }
>
> int main( void ){ printf( "%d\n", factorial( 5 )); }
>
>   /* prints
> 120
>   */

janus, Dec 18, 2009
18. ### GeneGuest

On Dec 17, 12:42 pm, Antti-Juhani Kaijanaho <antti-
> wrote:
> Gene <> kirjoitti 17.12.2009:
>
> > // activation record for fact
> > // activation record for lambda

>
> I'm pretty sure those were actually closures, not activation records.  A more
> common synonym for the latter is "stack frame", but an activation record can
> also reside on the heap.
>
> Impressive, still.
>
> --
> Mr. Antti-Juhani Kaijanaho, Jyvaskyla, Finland

It's a fine point. You could call them closures, but a closure does
not normally include space for yet-to-be-bound arguments (represented
internally as Boehm number references or similar). The structures used
in this code do include argument space. So I called them activation
recordes.

Gene, Dec 18, 2009
19. ### GeneGuest

On Dec 17, 2:46 am, Phil Carmody <>
wrote:
> Beej Jorgensen <> writes:
> > On 12/16/2009 08:33 PM, Gene wrote:
> >> Of course it can. As is often the case with C, you merely need to pay
> >> attention to a few more details to get the job done:

>
> >> #include <stdio.h>
> >> [... snip ...]

>
> > Terrifyingly awesome.

>
> But lambda_code calls code which calls lambda_code, so it's
> just recursion via structures containing function pointers.
> I thought the purpose was to avoid recursion? (And be completely
> pointless.)
>
> Use lisp for lisp, and C for C, that's what I say.
>

Ta da! Yes. No surprise. This is one of the points of the
exercise. The lisp version is also "just recursion via structures
containing function pointers." You just don't get to see much of the
action...

Gene, Dec 18, 2009
20. ### Stefan RamGuest

janus <> writes:
>I understand the the flow of your code but not the "spirit" of it.
>Could you explain it a little bit?

>>#include <stdio.h>
>>int g( int const i, int( *h )() )
>>{ return i ? i * h( i - 1, h ) : 1; }

I do not exactly understand »spirit«, so I just talk a bit:

Above, a function »g« is defined that is not statically recursive,
that is, it does not contain its own name in its body. Since I did
not know the precise wording of the »challenge« in this thread,
I can not claim that this is a solution to the challenge. It
was posted in the spirit of »If this was the challenge, then
its ok, otherwise: sorry, and just ignore it.«

However, many functions in C are latently recursive, that
is, they might call themselves directly or indirectly even
if they do not contain their own name. This is nearly always
possible as soon as a functions g calls another function h,
because h might call other functions, and one of them might
possibly call g again.

(When talking about »recursive functions in C«, we first
need to define this term »recursive function in C«. I am not
aware of a single definition yet that comes to my mind now.)

»g« surely is latently recursive, because it even has a
parameter that might be »g« itself (»&g« in older C
dialects). But this does not have to be so. It is just a
possibility.

>>/* This is not the Y combinator,
>>just a C function called "Y". */
>>int Y( int const i, int( *g )() )
>>{ return g( i, g ); }

This Y was intended to be a »meta function«. That is, it takes
a function g (ignoring the other parameter i for a moment) and
then behaves as another function Yg, which depends on g:

Y: g :--> Yg

. And Yg happens to be the factorial.

>>int factorial( int const i ){ return Y( i, g ); }

The argument of the call also has to be passed through,
which is why »i« also appears above. This shows that I
cheated a little bit, because I do not actually generate a
»first-class function« Yg. For example, my function Yg could
not be passed as a function parameter to another function,
it has no specific address (»&Yg« in older C dialects).
But my definition was sufficient for the task at hand.

Thus, I have a function g that is not statically recursive,
and a transform functions Y that transforms a function into
another function. Until now both definitions are completely
independent. Then I apply Y to g to get the factorial, but
Y could also be applied to other int-functions to get other
transformed functions and g could also be used in other ways
than be the argument of Y.

>>int main( void ){ printf( "%d\n", factorial( 5 )); }

Stefan Ram, Dec 18, 2009