Velocity Reviews > Programming challenge

# Programming challenge

annalissa
Guest
Posts: n/a

 12-14-2009
Hi all,

http://pramode.net/2006/01/09/factor...-fun/#more-219

my question is can this be done in C ?

Dann Corbit
Guest
Posts: n/a

 12-14-2009
In article <hg68kr\$8c5\$(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed) says...
>
> Hi all,
>
> http://pramode.net/2006/01/09/factor...-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.

Beej Jorgensen
Guest
Posts: n/a

 12-14-2009
On 12/14/2009 12:54 PM, annalissa wrote:
> http://pramode.net/2006/01/09/factor...-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

Ben Bacarisse
Guest
Posts: n/a

 12-14-2009
annalissa <(E-Mail Removed)> writes:

> http://pramode.net/2006/01/09/factor...-fun/#more-219

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.

Hallvard B Furuseth
Guest
Posts: n/a

 12-14-2009
Beej Jorgensen writes:
> On 12/14/2009 12:54 PM, annalissa wrote:
>> http://pramode.net/2006/01/09/factor...-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

Eric Sosman
Guest
Posts: n/a

 12-14-2009
On 12/14/2009 4:26 PM, Dann Corbit wrote:
> In article<hg68kr\$8c5\$(E-Mail Removed)>, (E-Mail Removed) says...
>>
>> Hi all,
>>
>> http://pramode.net/2006/01/09/factor...-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
(E-Mail Removed)lid

Hallvard B Furuseth
Guest
Posts: n/a

 12-14-2009
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

Gene
Guest
Posts: n/a

 12-17-2009
On Dec 14, 3:54*pm, annalissa <(E-Mail Removed)> wrote:
> Hi all,
>
>
> my question is can this be done in C ?

On Dec 14, 3:54 pm, annalissa <(E-Mail Removed)> 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
Guest
Posts: n/a

 12-17-2009
On Dec 16, 11:33*pm, Gene <(E-Mail Removed)> wrote:
> On Dec 14, 3:54*pm, annalissa <(E-Mail Removed)> wrote:
>
> > Hi all,

>

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

>
> On Dec 14, 3:54 pm, annalissa <(E-Mail Removed)> 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;
}

Beej Jorgensen
Guest
Posts: n/a

 12-17-2009
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