Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.math > #641142 > unrolled thread

C Question for P. Olcott

Back to article view | Back to sci.math

Contents

  C Question for P. Olcott Python <python@cccp.invalid> - 2025-11-26 03:02 +0000
    Re: C Question for P. Olcott Python <python@cccp.invalid> - 2025-11-26 03:50 +0000

#641142 — C Question for P. Olcott

You pretend to be a C software skilled developper.

Do you know why this code words (below) :

$ ./olcott 
Fixed-point style recursion in C (fact, fib, countdown)
------------------------------------------------------

fact( 0) = 1
fact( 1) = 1
fact( 2) = 2
fact( 3) = 6
fact( 4) = 24
fact( 5) = 120
fact( 6) = 720
fact( 7) = 5040
fact( 8) = 40320
fact( 9) = 362880
fact(10) = 3628800

fib( 0)  = 0
fib( 1)  = 1
fib( 2)  = 1
fib( 3)  = 2
fib( 4)  = 3
fib( 5)  = 5
fib( 6)  = 8
fib( 7)  = 13
fib( 8)  = 21
fib( 9)  = 34
fib(10)  = 55

Countdown: 5
Countdown: 4
Countdown: 3
Countdown: 2
Countdown: 1
Blast off!


--------------------


/*
 * olcott.c
 *
 * Demonstration of a fixed-point style construction in C,
 * equivalent in spirit to the lambda-calculus fixed-point
 * combinator (Y combinator) used to implement recursion.
 *
 * In lambda-calculus (untyped), a fixed-point combinator Y
 * satisfies:
 *
 *      Y F = f  such that  f = F f
 *
 * That is, given a transformation F that takes a function
 * and returns a "one-step" version, Y ties the knot and
 * produces a function f that is its own image by F.
 *
 * In C we cannot build new functions at runtime, but we can
 * reproduce the *pattern*:
 *
 *  1. Write a non-recursive "body" F that takes, as first
 *     argument, a function pointer `self` that it will use
 *     for recursive calls.
 *
 *     Example prototype:
 *
 *         int fact_body(int (*self)(int), int n);
 *
 *  2. Then define:
 *
 *         int fact(int n) {
 *             return fact_body(fact, n);
 *         }
 *
 *     This is exactly the fixed-point equation:
 *
 *         fact = F(fact)
 *
 * where F is "lambda self. lambda n. fact_body(self, n)".
 *
 * So:
 *
 *     Y(F) = fact
 *
 * In other words, the name `fact` plays the role of
 * "fixed point" of the higher-order operator F.
 *
 * Below we implement:
 *   - factorial using this pattern
 *   - fibonacci using the same pattern
 *   - a recursive "loop-like" countdown, also via a fixed point
 */

#include <stdio.h>

/**********************************************************************
 * 1. Factorial via fixed-point style
 **********************************************************************/

/*
 * fact_body(self, n)
 *
 * This is the NON-RECURSIVE "body" of factorial.
 * It does NOT call fact_body() directly.
 * Instead it calls `self`, which is a function pointer meant to be
 * the final recursive function (the fixed point).
 *
 * In lambda calculus notation, fact_body corresponds to:
 *
 *   F = λself. λn. if n == 0 then 1 else n * self(n-1)
 *
 */
int fact_body(int (*self)(int), int n) {
    if (n <= 0) return 1;
    return n * self(n - 1);
}

/*
 * fact(n)
 *
 * This is the fixed point:
 *
 *   fact = F(fact)
 *
 * i.e. in C:
 *
 *   fact(n) = fact_body(fact, n)
 *
 * This is exactly what the Y combinator gives you in lambda calculus:
 *
 *   Y F = fact
 */
int fact(int n) {
    return fact_body(fact, n);
}

/**********************************************************************
 * 2. Fibonacci via the same fixed-point style
 **********************************************************************/

/*
 * fib_body(self, n)
 *
 * Again, this is the NON-RECURSIVE "body" of fibonacci.
 * It uses the `self` function pointer for recursion.
 *
 * Lambda style:
 *
 *   F = λself. λn.
 *           if n <= 1 then n
 *           else self(n-1) + self(n-2)
 */
int fib_body(int (*self)(int), int n) {
    if (n <= 1) return n;
    return self(n - 1) + self(n - 2);
}

/*
 * fib(n)
 *
 * Fixed point of fib_body:
 *
 *   fib = F(fib)
 *   fib(n) = fib_body(fib, n)
 */
int fib(int n) {
    return fib_body(fib, n);
}

/**********************************************************************
 * 3. A "loop-like" countdown via fixed-point style
 *
 * This shows how recursion can emulate looping using the same pattern:
 *   - Define a body that calls `self` with n-1 until 0
 **********************************************************************/

/*
 * countdown_body(self, n)
 *
 * Prints n, then recurses with n-1, until n <= 0.
 */
void countdown_body(void (*self)(int), int n) {
    if (n <= 0) {
        printf("Blast off!\n");
        return;
    }
    printf("Countdown: %d\n", n);
    self(n - 1);
}

/*
 * countdown(n)
 *
 * Fixed point of countdown_body:
 *
 *   countdown = F(countdown)
 */
void countdown(int n) {
    countdown_body(countdown, n);
}

/**********************************************************************
 * 4. main: demonstrate everything
 **********************************************************************/

int main(void) {
    int i;

    printf("Fixed-point style recursion in C (fact, fib, countdown)\n");
    printf("------------------------------------------------------\n\n");

    /* Factorial via fixed-point style */
    for (i = 0; i <= 10; ++i) {
        printf("fact(%2d) = %d\n", i, fact(i));
    }
    printf("\n");

    /* Fibonacci via fixed-point style */
    for (i = 0; i <= 10; ++i) {
        printf("fib(%2d)  = %d\n", i, fib(i));
    }
    printf("\n");

    /* Countdown via fixed-point style recursion instead of a loop */
    countdown(5);

    return 0;
}

[toc] | [next] | [standalone]

#641173

Moreover, Peter, do you understand why this code works:

#!/usr/bin/env python3

# Combinateur de point fixe (Y adapté à Python, appel par valeur)
Y = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(
                  lambda x: f(lambda *args: x(x)(*args))
              )

# Exemple 1 : factorielle sans récursion directe
fact = Y(
    lambda rec: lambda n: 1 if n == 0 else n * rec(n - 1)
)

# Exemple 2 : Fibonacci sans récursion directe
fib = Y(
    lambda rec: lambda n: n if n < 2 else rec(n - 1) + rec(n - 2)
)

if __name__ == "__main__":
    for n in range(6):
        print(f"fact({n}) =", fact(n))

    for n in range(8):
        print(f"fib({n})  =", fib(n))

[toc] | [prev] | [standalone]

Back to top | Article view | sci.math

csiph-web