Programming challenge
annalissa
see this article,
http://pramode.net/2006/01/09/factorial-without-recursion-or-iteration-or-how-tc-can-be-fun/#more-219
my question is can this be done in C ?
Dann Corbit
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
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
> see this article,
> http://pramode.net/2006/01/09/factorial-without-recursion-or-iteration-or-how-tc-can-be-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
> On 12/14/2009 12:54 PM, annalissa wrote:
>> http://pramode.net/2006/01/09/factorial-without-recursion-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
Eric Sosman
> In article<hg68kr$8c5$1...@aioe.org>, aar...@gmail.com says...
>>
>> Hi all,
>>
>> see this article,
>> http://pramode.net/2006/01/09/factorial-without-recursion-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
Just in case someone wants to look it up: "Stirling," with
two ayes and no ease.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Hallvard B Furuseth
> 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.
Gene
> Hi all,
>
> see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
>
> my question is can this be done in C ?
On Dec 14, 3:54 pm, annalissa <aark...@gmail.com> wrote:
> Hi all,
>
> see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
>
> 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
> On Dec 14, 3:54 pm, annalissa <aark...@gmail.com> wrote:
>
> > Hi all,
>
> > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
>
> > my question is can this be done in C ?
>
> On Dec 14, 3:54 pm, annalissa <aark...@gmail.com> wrote:
>
> > Hi all,
>
> > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
>
> > 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)
{
Phil Carmody
> 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>
>
> 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
Antti-Juhani Kaijanaho
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
Ben Bacarisse
> annalissa <aar...@gmail.com> 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.
Richard Tobin
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.
Ben Bacarisse
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>>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!
>
> Yes, that's true. Now, I start to evaluate one expression from:
>
> http://okmij.org/ftp/Computation/fixed-point-combinators.html
>
> Namely ((U fact-nr) 3):
>
> ((U fact-nr) 3) =
> ((fact-nr fact-nr) 3) =
> ((lambda (n) (if (zero? n) 1 (* n ((fact-nr fact-nr) (- n 1)))))3) =
> (if (zero? 3) 1 (* 3 ((fact-nr fact-nr) (- 3 1)))) =
> (* 3 (((lambda (n) (if (zero? n) 1 (* n ((fact-nr fact-nr) (- n 1)))))3) (- 3 1)))
>
> In the last step, fact-nr has called fact-nr. It was called »f«
> in the source code of fact-nr, but it is still fact-nr that is
> being called.
>
> So the point is that there is no more direct recursion in
> the source code (static recursion), but for all these things
> to work, one can not exclude dynamic recursion - neither the
> author of fact-nr nor I.
I think we are saying the same thing but getting tied up in
terminology. The page you site does not claim that the eventual
function (U fact-nr) is not recursive. In fact the page starts by
saying:
"Self-application is often an elegant way to introduce recursion,
..."
What prompted by reply was your statement that your example eliminates
"direct recursion". To my mind g(1, g) when g calls its second
argument is direct recursion. I'd say that you have eliminated the
appearance of recursion or the syntactic signs of recursion.
All this was confused by the original question citing a page whose
name contained "factorial-without-recursion-or-iteration" but whose
content was not about that at all.
--
Ben.
Antti-Juhani Kaijanaho
> The page you site does not claim that the eventual
> function (U fact-nr) is not recursive. In fact the page starts by
> saying:
>
> "Self-application is often an elegant way to introduce recursion,
> ..."
Dunno about elegance.
The theoretical appeal of fixpoint combinators is that they allow writing
recursive functions in a language that lacks support for explicit recursion,
provided that the language is otherwise powerful enough[*]. In practical
programming, using fixpoint combinators is often just a stunt.
[*] Interesting factoid: a language that is powerful enough but untyped loses
its sufficient power when a simple type system is enforced.
janus
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, r...@zedat.fu-berlin.de (Stefan Ram) wrote:
> annalissa <aark...@gmail.com> 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
> */
Gene
juh...@kaijanaho.fi> wrote:
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
wrote:
> Beej Jorgensen <b...@beej.us> 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...
Ben Bacarisse
> janus <emeka...@gmail.com> 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; }
<snip>
>>>/* 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.
This point is a key one and may be why janus is confused. In C, your
Y is just a mild obfuscation. Writing
int factorial(int const i) { return g(i, g); }
I clearer and shows what is happening. In a language in which Y can be
a higher-order function it makes sense, but in C it just adds another
level to follow and brings no benefit (to my mind).
> Thus, I have a function g that is not statically recursive,
> and a transform functions Y that transforms a function into
> another function.
Except that, in C, it does not (as you have explained above)!
> 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 )); }
--
Ben.
Antti-Juhani Kaijanaho
> Antti-Juhani Kaijanaho <antti-...@kaijanaho.fi> writes:
>>The theoretical appeal of fixpoint combinators is that they allow writing
>
> the possibility to give the meaning of certain language
> elements as fixpoints
Certainly - the theory of fixpoints is the theory behind recursion. Fixpoint
*combinators*, on the other hand, are programming constructs.
io_x
"Stefan Ram" <r...@zedat.fu-berlin.de> ha scritto nel messaggio
news:fixpoints-20...@ram.dialup.fu-berlin.de...
>> while(x)s = if(x){s; if(x){s; if(x){s; ...
while(x)y = {lablel:; if(x) {y; goto label;} }