ND-récursion

Exemples d'utilisation de la ND-récursion (~~, ~>, ~[]).

La ND-récursion permet d'exprimer des computations récursives qui peuvent être exécutées en parallèle sans syntaxe async/await. Le runtime choisit le mode d'exécution.

~~ ND-récursion

Forme combinateur

La forme combinateur applique la lambda avec une seed initiale:

# Countdown récursif
~~(5, (v, recur) => {
    if v > 0 {
        recur(v - 1)
    } else {
        v
    }
})
# → 0

Explication: La lambda reçoit (v, recur) où:

• v = valeur courante
• recur = fonction pour continuer la récursion

Factorielle

~~(5, (n, recur) => {
    if n <= 1 { 1 }
    else { n * recur(n - 1) }
})
# → 120

Forme déclaration

Créer une fonction ND-récursive réutilisable:

countdown = ~~(n, recur) => {
    if n > 0 { recur(n - 1) }
    else { "done" }
}

countdown(10)
# → "done"

À ce stade, la lambda wrappée s'exécute comme une fonction normale. Une fois appelée avec une seed, elle déclenche la récursion.

~> ND-Map

Forme lift

Lifter une fonction dans le contexte ND:

f = ~> abs
f(-5)
# → 5

Forme applicative

Appliquer une fonction en contexte ND:

~>(list(-1, -2, -3), abs)
# → [1, 2, 3]

Broadcast ND-map

Mapper une fonction sur chaque élément:

list(-1, -2, 3).[~> abs]
# → [1, 2, 3]

Avec lambda:

list(1, 2, 3).[~> (x) => { x * 2 }]
# → [2, 4, 6]

~[] Empty Topos

Littéral représentant le topos vide (élément neutre):

empty = ~[]

Propriétés:

# Falsy en contexte booléen
if ~[] { 1 } else { 2 }
# → 2

# Égalité
~[] == ~[]
# → True

# Longueur
len(~[])
# → 0

Le topos vide sert d'élément identité pour les opérations ND. Il marque la terminaison dans les graphes de calcul.

Broadcast ND

Les opérateurs ND fonctionnent avec le broadcast sur collections.

data.[~> f] Broadcast ND-map

Applique une fonction à chaque élément en contexte ND:

# Map abs sur liste
list(-1, -2, 3).[~> abs]
# → [1, 2, 3]

# Map lambda inline
list(1, 2, 3).[~> (x) => { x * 2 }]
# → [2, 4, 6]

# Préserve le type tuple
tuple(-1, -2, 3).[~> abs]
# → (1, 2, 3)

data.[~~ lambda] Broadcast ND-récursion

Applique la ND-récursion à chaque élément:

# Factorielle sur liste
list(3, 5).[~~(n, recur) => {
    if n <= 1 { 1 }
    else { n * recur(n - 1) }
}]
# → [6, 120]

# Countdown sur chaque élément
list(3, 5, 2).[~~(v, recur) => {
    if v > 0 { recur(v - 1) }
    else { v }
}]
# → [0, 0, 0]

# Préserve le type tuple
tuple(3, 2, 4).[~~(n, recur) => {
    if n <= 1 { 1 }
    else { n * recur(n - 1) }
}]
# → (6, 2, 24)

Note: Le broadcast ND préserve automatiquement le type de la collection (list, tuple, set).

Chaînage

Les opérateurs ND se chaînent naturellement avec le broadcasting standard:

data = list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
result = data.[if > 3].[* 2].[if < 15].[+ 1]
# > 3: [4,5,6,7,8,9,10]
# * 2: [8,10,12,14,16,18,20]
# < 15: [8,10,12,14]
# + 1: [9,11,13,15]

Mode d'exécution

Par défaut, exécution séquentielle. Le mode "thread" utilise rayon (Rust) pour distribuer les éléments sur un pool de threads natifs, en relâchant le GIL pendant l'exécution.

Pragmas ND

Les pragmas permettent de contrôler le mode d'exécution :

# Mode parallèle (rayon)
pragma("nd_mode", ND.thread)

~~(huge_dataset, (data, recur) => { … })

Modes disponibles :

• "sequential" (défaut) : exécution séquentielle, pas de overhead
• "thread" : distribution rayon avec py.detach() / Python::attach() par thread
• "process" : vrais processus séparés (ProcessPoolExecutor), pour un parallélisme sans GIL

Le parallélisme repose sur rayon (Rust), pas sur des threads Python. Le GIL est relâché pendant le dispatch et réacquis par chaque worker pour les callbacks Python. La mémoïsation reste thread-safe via Arc<Mutex>.

Repli et diagnostic

Un mode ne garantit pas qu'il s'exécutera. Quand un élément ne peut pas honorer le mode demandé — une capture qui ne traverse pas la frontière d'un process, un worker qui échoue — le runtime retombe sur un mode plus simple (thread, puis sequential) et rejoue l'élément. Le résultat reste correct ; seul le parallélisme demandé n'a pas eu lieu.

Deux familles de repli, traitées différemment :

• Préventif : le runtime sait d'avance que l'élément n'est pas distribuable (lambda ou seed non sérialisable, binaire worker absent). C'est un choix, pas une panne — silencieux.
• Réactif : le worker a démarré puis échoué. Le runtime émet alors un CatnipNDFallbackWarning (une fois par batch) nommant le mode demandé, le mode effectif et la cause.

Le repli réactif se promeut en erreur fatale — utile, côté hôte Python, pour vérifier qu'un mode s'exécute bien tel que demandé :

import warnings
from catnip.exc import CatnipNDFallbackWarning

warnings.filterwarnings('error', category=CatnipNDFallbackWarning)

Un mode qui ne dit pas qu'il a échoué ment sur ce qu'il a fait. Le repli reste une bonne réponse ; le silence, non.

Mémoïsation

Le pragma nd_memoize active un cache automatique des résultats :

# Activer la mémoïsation
pragma("nd_memoize", True)

# Fibonacci avec mémoïsation - 11x speedup sur fib(25)
~~(25, (n, recur) => {
    if n <= 1 { n }
    else { recur(n - 1) + recur(n - 2) }
})
# → 75025

# Désactiver la mémoïsation (défaut)
pragma("nd_memoize", False)

Principe : Le scheduler cache les résultats par valeur seed. Si recur(n) est rappelé avec la même valeur n, le résultat en cache est retourné au lieu de recalculer.

Cas d'usage optimal :

• Algorithmes avec redondance (Fibonacci, DP)
• Calculs coûteux sur mêmes valeurs
• Broadcast sur collections avec valeurs dupliquées

Performance :

• Fibonacci sans mémoïsation : O(2^n) appels
• Fibonacci avec mémoïsation : O(n) appels
• Speedup mesuré : 11x sur fib(25), plus élevé pour n plus grand

Batching (Phase 6)

Le pragma nd_batch_size contrôle la granularité du parallélisme en regroupant plusieurs items avant de les soumettre à ThreadPoolExecutor :

# Configuration explicite
pragma("nd_mode", ND.process)
pragma("nd_workers", 8)
pragma("nd_batch_size", 10)  # 10 items par batch

# Large collection - batching réduit l'overhead
range(1, 101).[~~(n, recur) => {
    if n <= 1 { 1 }
    else { n * recur(n - 1) }
}]

# Auto-calcul (défaut avec 0)
pragma("nd_batch_size", 0)   # batch_size = ceil(len / (workers * 4))

Principe : Au lieu de soumettre chaque item individuellement à l'executor, on groupe batch_size items ensemble. Cela réduit le nombre de submits et l'overhead de synchronisation.

Auto-calcul : Si batch_size = 0 (défaut), le scheduler calcule automatiquement pour obtenir ~4 batches par worker.

Détection intelligente : Pour les petites collections (< workers*2 items), le batching est automatiquement désactivé pour éviter l'overhead.

Cas d'usage optimal :

• Collections grandes (100+ items)
• Mode parallèle avec plusieurs workers
• Items avec temps de calcul variable

Combinaison avec mémoïsation :

pragma("nd_mode", ND.process)
pragma("nd_memoize", True)
pragma("nd_batch_size", 5)

# Broadcast sur collection avec doublons
# Batching: réduit overhead ThreadPoolExecutor
# Mémoïsation : évite les recalculs des valeurs déjà vues
list(10, 12, 10, 15, 12, 20).[~~(n, recur) => {
    if n <= 1 { n }
    else { recur(n - 1) + recur(n - 2) }
}]

Limites de récursion

La récursion ND est limitée à 200 appels imbriqués via recur(). Au-delà, une RecursionError est levée :

# Récursion infinie : déclenche RecursionError
~~(0, (v, recur) => { recur(v + 1) })
# RecursionError: maximum ND recursion depth exceeded

Cette limite est un garde-fou uniforme sur les runtimes, pas la mesure d'un mur atteint partout. Sous l'extension Python, la réentrée de recur est interceptée dans la boucle de dispatch et empilée sur le tas : un niveau ne coûte pratiquement pas de pile native, et 299 niveaux tiennent dans une pile de 96 Ko. Le runtime pur Rust, lui, réentre réellement sur la pile native, et c'est là que la limite protège d'un débordement.

Pour les cas légitimes nécessitant plus de profondeur, préférer la récursion classique (fonctions =>) qui utilise le frame stacking de la VM sans limite de stack Rust.

Principe : La sémantique du code reste identique, seul le mode d'exécution change. Le déterminisme est préservé - résultat identique en séquentiel et parallèle.

Les optimisations (mémoïsation, batching) réduisent le temps d'exécution sans changer le résultat.