Recursividad observable (o vinculante) en Flechas

Question

Estoy tratando de encontrar una forma de traducir la notación recursiva normal como como | fib | función debajo de una flecha, conservando la mayor cantidad posible de la estructura de la notación recursiva. Además, me gustaría como para inspeccionar la flecha. Por esta creé un tipo de datos que contiene un constructor para cada Flecha clase {..}:

Fib:

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-2) + fib (n-1) 

Mi R tipo de datos, las instancias de este tipo de datos consisten en el mapeo al constructor apropiado :

data R x y where 
    -- Category 
    Id  :: R a a 
    Comp  :: R b c -> R a b   -> R a c 
    -- Arrow 
    Arr  :: (a -> b) -> R a b 
    Split :: R b c -> R b' c'  -> R (b,b') (c,c') 
    Cache :: (a -> a -> Bool) -> R a a 
    -- ArrowChoice 
    Choice :: R b c -> R b' c' -> R (Either b b') (Either c c') 
    -- ArrowLoop 
    Loop  :: R (b, d) (c, d) -> R b c 
    -- ArrowApply 
    Apply :: R (R b c, b) c 

Traduciendo el | fib | la función de arriba primero dio como resultado la siguiente definición . Sin embargo, no está permitido debido al proceso en el RHS de la declaración para | fibz |. Sé que la gramática de la notación de flecha impide esto, pero ¿cuál es la razón subyacente de esto?

fib' :: (ArrowChoice r, ArrowLoop r) => r Int Int 
fib' = proc x -> do 
    rec fibz <- proc n -> case n of 
          0 -> returnA -< 0 
          1 -> returnA -< 1 
          n' -> do l <- fibz -< (n'-2) 
            r <- fibz -< (n'-1) 
            returnA -< (l+r) 
    fibz -<< x 

Reescribiendo la función anterior para usar una compilación de enunciados let. Sin embargo, aquí surge mi segundo problema. Quiero poder inspeccionar la recursión donde ocurre. Sin embargo, en este caso | fibz | es un árbol infinito . Me gustaría capturar la recursión en fibz, I esperaba que el rec me ayudara con eso en combinación con | loop | pero tal vez estoy equivocado?

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib'' = proc x -> do 
    let fibz = proc n -> case n of 
          0 -> returnA -< 0 
          1 -> returnA -< 1 
          n' -> do l <- fibz -< (n'-2) 
            r <- fibz -< (n'-1) 
            returnA -< (l+r) 
    fibz -<< x 

Básicamente, ¿es posible observar este tipo de recursividad? (Tal vez incluso dentro de los límites de la notación de flecha) podría agregar otro constructor como fix. Tal vez debería ser capaz de observar el enlace de variables para que sea posible hacer referencia a ellas. Sin embargo, esto quedaría fuera del alcance de Arrows.

¿Alguna idea de esto?

Actualización 1: Se me ocurre este formulario, fuera de la notación de flecha. Esto oculta la recursividad dentro del app y, por lo tanto, termino con una representación finita de la flecha. Sin embargo, aún deseo poder, p. Ej. reemplace la llamada a fib dentro de app a una versión optimizada de fib.

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib 
    = (arr 
     (\ n -> 
      case n of 
       0 -> Left() 
       1 -> Right (Left()) 
       n' -> Right (Right n')) 
     >>> 
     (arr (\() -> 0) ||| 
      (arr (\() -> 1) ||| 
      (arr (\ n' -> (n', n')) >>> 
       (first (arr (\ n' -> app (fib, n' - 2))) >>> 
        arr (\ (l, n') -> (n', l))) 
        >>> 
        (first (arr (\ n' -> app (fib, n' - 1))) >>> 
        arr (\ (r, l) -> (l + r)))))))         

Este código corresponde a lo siguiente en la flecha de la notación:

fib :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib = proc n -> 
    case n of 
    0 -> returnA -< 0 
    1 -> returnA -< 1 
    n' -> 
      do l <- fib -<< (n'-2) 
       r <- fib -<< (n'-1) 
       returnA -< (l+r) 

Answer 1

Puede escribir fib en términos de bucle, por ejemplo, así:

fib'' :: (ArrowChoice r, ArrowLoop r, ArrowApply r) => r Int Int 
fib'' = loop $ proc (i, r) -> do 
    i' <- r -<< i 
    returnA -< (i', proc j -> case j of 
     0 -> returnA -< 0 
     1 -> returnA -< 1 
     _ -> do 
      a <- r -< j-2 
      b <- r -< j-1 
      returnA -< a + b) 

Pero esto es realmente sólo introduciendo un lazo artificial a un problema que no lo necesita, y en realidad tampoco te compra mucho en términos de observabilidad. Se puede ver que existe algún tipo de bucle, pero creo que es imposible determinar realmente dónde se produce la recursión.

En la representación reificada, cualquier llamada a otras flechas estará esencialmente "en línea" y esto incluye llamadas a la misma flecha. Realmente no se puede detectar estos sitios de llamadas para empezar, sin mencionar qué flecha se está llamando. Otro problema con la reificación de flechas es que mucha de la información interesante acerca de cómo se pasan las entradas se pierde dentro del agujero negro Arr.

Definitivamente no soy experto en flechas y espero que alguien me demuestre que estoy equivocado, pero me inclino a pensar que lo que está tratando de lograr es imposible de hacer de manera fiable o al menos altamente práctico. Un recurso que puedo pensar que podría ayudarlo a reenviar es el documento Type-Safe Observable Sharing in Haskell y el paquete data-reify.

Answer 2

Puede reificar completamente fib con una Categoría, en la medida en que pueda definir funciones para guardar el código en el disco y volver a cargarlo. Aunque es un poco feo.

{-# LANGUAGE GADTs, RankNTypes #-} 

module Main where 

import Control.Category 

data RRef s1 s2 = RRef Int 

data R s1 s2 where 
    Id :: forall s. R s s 
    Compose :: forall s1 s2 s3. R s2 s3 -> R s1 s2 -> R s1 s3 
    Lit :: forall s a. a -> R s (a,s) 
    Dup :: forall s a. R (a,s) (a,(a,s)) 
    Drop :: forall s b. R (b,s) s 
    Add :: forall s a. Num a => R (a,(a,s)) (a,s) 
    Decrement :: forall s. R (Int,s) (Int,s) 
    Deref :: forall s1 s2. RRef s1 s2 -> R s1 s2 
    Rec :: forall s1 s2. (RRef s1 s2 -> R s1 s2) -> R s1 s2 
    IsZero :: forall s. R (Int,s) (Bool,s) 
    If :: forall s1 s2. R s1 s2 -> R s1 s2 -> R (Bool,s1) s2 
    Swap :: forall s a b. R (a,(b,s)) (b,(a,s)) 
    Over :: forall s a b. R (a,(b,s)) (a,(b,(a,s))) 
    Rot :: forall s a b c. R (a,(b,(c,s))) (b,(c,(a,s))) 

instance Category R where 
    id = Id 
    (.) = Compose 

fib :: R (Int,()) (Int,()) 
fib = 
    Lit 0 >>> 
    Lit 1 >>> 
    Rot >>> 
    Rot >>> 
    Rec (\ref -> 
    Dup >>> IsZero >>> (
     If 
     (Drop >>> Swap >>> Drop) 
     (Decrement >>> Rot >>> Rot >>> Over >>> Add >>> Rot >>> Rot >>> (Deref ref)) 
    ) 
) 

R Aquí se presenta una Monoid indexada, que resulta ser el mismo que un Category. Los dos parámetros de tipo R representan la firma de tipo de la pila antes y después de una operación. Una pila como una pila de programas, como en el código de ensamblaje. Las tuplas en los tipos de pila forman una lista heterogénea para escribir cada uno de los elementos en la pila. Todas las operaciones (excepto If) toman cero parámetros y simplemente manipulan la pila. El If toma dos bloques de código y devuelve código que no toma parámetros y solo manipula la pila.

Rec se utiliza para recursividad. Un intérprete localizaría un nombre único (como un entero) para la función recursiva, luego la función recursiva se referiría a ese nombre con Deref para conectarse a sí mismo formando una recursión.

Esto puede ser considerado como un lenguaje de programación concatenativo (como un EDSL) como Forth, excepto que tiene seguridad de tipo para los valores en la pila.