recursion - teoria - teorema del punto fijo en economia

Escribir la función de punto fijo en Rust

Question

Acabo de comenzar el tutorial de Rust y finalicé con dicho código utilizando recursión

extern crate rand;

use std::io;
use rand::Rng;
use std::cmp::Ordering;
use std::str::FromStr;
use std::fmt::{Display, Debug};

fn try_guess<T: Ord>(guess: T, actual: T) -> bool {
    match guess.cmp(&actual) {
        Ordering::Less => {
            println!("Too small");
            false
        }
        Ordering::Greater => {
            println!("Too big");
            false
        }
        Ordering::Equal => {
            println!("You win!");
            true
        }
    }
}

fn guess_loop<T: Ord + FromStr + Display + Copy>(actual: T)
    where <T as FromStr>::Err: Debug
{
    println!("PLease input your guess.");

    let mut guess = String::new();

    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");

    let guess_int: T = guess.trim()
        .parse()
        .expect("Should enter integer number");

    println!("You guessed {} !", guess_int);

    if !try_guess(guess_int, actual) {
        guess_loop(actual)
    }
}

fn main() {
    println!("Guess the number!!!");

    let secret_number = rand::thread_rng().gen_range(1, 51);

    guess_loop(secret_number);

}

Esperaba descartar la recursión de la función guess_loop e introduje un operador de punto fijo:

fn guess_loop<T: Ord + FromStr + Display + Copy>(actual: T, recur: fn(T) -> ()) -> ()
    where <T as FromStr>::Err: Debug
{
    println!("PLease input your guess.");

    let mut guess = String::new();

    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");

    let guess_int: T = guess.trim()
        .parse()
        .expect("Should enter integer number");

    println!("You guessed {} !", guess_int);

    if !try_guess(guess_int, actual) {
        recur(actual)
    }
}

fn fix<T, R>(func: fn(T, fn(T) -> R) -> R) -> fn(T) -> R {
    fn fixed(val: T) -> R {
        func(val, fixed)
    }
    fixed
}

fn main() {
    println!("Guess the number!!!");

    let secret_number = rand::thread_rng().gen_range(1, 51);

    fix(guess_loop)(secret_number);
}

pero esto condujo a numerosos errores, como

error[E0401]: can''t use type parameters from outer function; try using a local type parameter instead
  --> src/main.rs:49:19
   |
49 |     fn fixed(val: T) -> R {
   |                   ^ use of type variable from outer function

error[E0401]: can''t use type parameters from outer function; try using a local type parameter instead
  --> src/main.rs:49:25
   |
49 |     fn fixed(val: T) -> R {
   |                         ^ use of type variable from outer function

error[E0434]: can''t capture dynamic environment in a fn item; use the || { ... } closure form instead
  --> src/main.rs:50:9
   |
50 |         func(val, fixed)
   |         ^^^^

Mi siguiente intento fue cambiar la definición de guess_loop a

fn guess_loop<T: Ord + FromStr + Display + Copy, F>(actual: T, recur: F) -> ()
where <T as FromStr>::Err: Debug,
      F: Fn(T) -> ()
{ ... }

y redefinir la fix como

fn fix<T, R, F>(func: fn(T, F) -> R) -> F
    where F: Fn(T) -> R
{
    let fixed = |val: T| func(val, fix(func));
    fixed
}

esto llevó a

error[E0308]: mismatched types
  --> src/main.rs:53:5
   |
53 |     fixed
   |     ^^^^^ expected type parameter, found closure
   |
   = note: expected type `F`
   = note:    found type `[closure@src/main.rs:52:17: 52:46 func:_]`

error: the type of this value must be known in this context
  --> src/main.rs:61:5
   |
61 |     fix(guess_loop)(secret_number);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

¿Cómo puedo escribir una función de fix similar?

Answer 1

En primer lugar, los nombres de las variables no existen hasta después de que se hayan inicializado. No puede haber fixed referirse a sí mismo así.

En segundo lugar, no puede devolver los cierres por valor de una función, punto. La persona que llama elige los parámetros genéricos y la persona que llama no tiene idea de cuál será el tipo de cierre dentro de la función.

No pretendo que lo que sigue sea la mejor manera de hacerlo, pero fue lo más simple que pude hacer ese tipo de verificaciones.

fn guess_loop<T>(actual: T, recur: &Fn(T)) -> ()
    where T: Ord + FromStr + Display + Copy,
          <T as FromStr>::Err: Debug
{
    // ...
}

fn fix<T, R, F>(func: F) -> Box<Fn(T) -> R>
    where T: ''static,
          R: ''static,
          F: Fn(T, &Fn(T) -> R) -> R + ''static
{
    use std::cell::RefCell;
    use std::rc::Rc;

    let fixed = Rc::new(RefCell::new(None));
    let fixed_fn = {
        let fixed = fixed.clone();
        move |val: T| -> R {
            let fixed_ref = fixed.borrow();
            let fixed_ref: &Box<_> = fixed_ref.as_ref().unwrap();
            func(val, &**fixed_ref)
        }
    };
    *fixed.borrow_mut() = Some(Box::new(fixed_fn));

    Box::new(move |val: T| -> R {
        let fixed_ref = fixed.borrow();
        let fixed_ref: &Box<_> = fixed_ref.as_ref().unwrap();
        fixed_ref(val)
    })
}

Para que fixed_fn refiera a sí mismo, tenemos que crear algo para que lea antes de que exista. Desafortunadamente, esto significa tener un ciclo, y Rust odia los ciclos. Entonces, hacemos esto mediante la construcción de una RefCell<Option<_>> contada por referencia que comienza con None , y que será mutada más tarde para contener el cierre del punto fijo.

En segundo lugar, no podemos usar este identificador como invocable, por lo que tenemos que extraer explícitamente un puntero al cierre para que podamos pasarlo a func .

En tercer lugar, el compilador no parece ser capaz de inferir el tipo de fixed correctamente. Esperaba que fuera capaz de resolver que es Rc<RefCell<Option<{closure}>>> , pero se negó a hacerlo. Como resultado, tenemos que recurrir al almacenamiento de un Box<Fn(T) -> R> , ya que no podemos nombrar explícitamente el tipo del cierre.

Finalmente, tenemos que construir un nuevo cierre que tome un segundo identificador para repararlo, descomprimirlo y llamarlo. Una vez más, no podemos usar fixed como un invocable directamente. Tampoco podemos reutilizar el cierre interno , porque para hacerlo tendríamos que ponerlo dentro de su propio Rc y en ese punto, las cosas están empezando a volverse locas.

... más loco.

Finalmente, tenemos que devolver este segundo cierre en una Box porque, como dije antes, no podemos devolver cierres por valor porque no podemos nombrar sus tipos en la firma.

* respiración profunda *

Si alguien tiene una solución más simple, me encantaría verla. :PAG

Answer 2

Comenzando en donde lo dejaste:

fn fix<T, R, F>(func: fn(T, F) -> R) -> F
    where F: Fn(T) -> R
{
    |val: T| func(val, fix(func))
}

El objeto devuelto tiene un tipo de cierre anónimo. Usar un tipo genérico no ayudará aquí, ya que el tipo de cierre lo decide el destinatario, no el que llama. Aquí es donde los rasgos de impl son útiles:

fn fix<T, R, F>(func: fn(T, F) -> R) -> impl Fn(T) -> R
    where F: Fn(T) -> R
{
    |val: T| func(val, fix(func))
}

No podemos pasar fix(func) a func porque espera un tipo de nombre para F Tendremos que conformarnos con un objeto de rasgo en su lugar:

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> impl Fn(T) -> R {
    |val: T| func(val, &fix(func))
}

Ahora es el momento de luchar contra el verificador de por vida. El compilador se queja:

only named lifetimes are allowed in `impl Trait`, but `` was found in the type `…`

Este es un mensaje algo críptico. Como los rasgos impl son siempre ''static por defecto, esta es una forma indirecta de decir: "el cierre no vive lo suficiente para ''static ''. Para obtener el mensaje de error real , agregamos + ''static a la impl Fn(T) -> R y recompilamos:

closure may outlive the current function, but it borrows `func`, which is owned by the current function

Entonces ese era el problema real. Está tomando prestado func . No necesitamos tomar prestado el func porque fn es Copy , entonces podemos duplicarlo tanto como queramos. Premoniciemos el cierre con move y eliminemos el + ''static de antes:

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> impl Fn(T) -> R {
    move |val: T| func(val, &fix(func))
}

Y voila, ¡funciona! Bueno, casi ... tendrás que editar guess_loop y cambiar fn(T) -> () a &Fn(T) -> () . Estoy realmente sorprendido de que esta solución no requiera ninguna asignación.

Si no puede usar rasgos impl , puede escribir en su lugar:

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> Box<Fn(T) -> R>
    where T: ''static,
          R: ''static
{
    Box::new(move |val: T| func(val, fix(func).as_ref()))
}

que lamentablemente no está libre de asignación.

Además, podemos generalizar el resultado un poco para permitir cierres y tiempos de vida arbitrarios:

fn fix<''a, T, R, F>(func: F) -> impl ''a + Fn(T) -> R
    where F: ''a + Fn(T, &Fn(T) -> R) -> R + Copy
{
    move |val: T| func(val, &fix(func))
}

En el proceso de encontrar una solución para su problema, terminé escribiendo una versión más simple de la fix , que en realidad terminó guiándome hacia una solución para su función de fix :

type Lazy<''a, T> = Box<FnBox() -> T + ''a>;

// fix: (Lazy<T> -> T) -> T
fn fix<''a, T, F>(f: F) -> T
    where F: Fn(Lazy<''a, T>) -> T + Copy + ''a
{
    f(Box::new(move || fix(f)))
}

Aquí hay una demostración de cómo esta función de fix podría usarse para calcular el factorial:

fn factorial(n: u64) -> u64 {
    // f: Lazy<u64 -> u64> -> u64 -> u64
    fn f(fac: Lazy<''static, Box<FnBox(u64) -> u64>>) -> Box<FnBox(u64) -> u64> {
        Box::new(move |n| {
            if n == 0 {
                1
            } else { 
                n * fac()(n - 1)
            }
        })
    }
    fix(f)(n)
}

Answer 3

Esto se puede hacer con un costo de tiempo de ejecución cero si está dispuesto a usar funciones inestables (es decir, un compilador nocturno) y dispuesto a ... ofuscar levemente su código.

Primero, debemos convertir el resultado de la fix en una estructura con nombre. Esta estructura necesita implementar Fn , por lo que la implementaremos manualmente (esta es una característica inestable).

    #![feature(fn_traits)]
    #![feature(unboxed_closures)]

extern crate rand;

use rand::Rng;
use std::cmp::Ordering;

fn try_guess<T: Ord>(guess: T, actual: T) -> bool {
    match guess.cmp(&actual) {
        Ordering::Less => {
            println!("Too small");
            false
        }
        Ordering::Greater => {
            println!("Too big");
            false
        }
        Ordering::Equal => {
            println!("You win!");
            true
        }
    }
}

struct Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    func: F,
}

impl<F> FnOnce<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32,)) -> Self::Output {
        self.call(args)
    }
}

impl<F> FnMut<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    extern "rust-call" fn call_mut(&mut self, args: (i32,)) -> Self::Output {
        self.call(args)
    }
}

impl<F> Fn<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    extern "rust-call" fn call(&self, (val,): (i32,)) -> Self::Output {
        (self.func)(val, self);
    }
}

fn fix<F>(func: F) -> Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    Fix { func: func }
}

fn guess_loop<F>(actual: i32, recur: &F)
    where F: Fn(i32)
{
    let guess_int = rand::thread_rng().gen_range(1, 51);

    if guess_int != actual {
        recur(actual)
    }
}

fn main() {
    let secret_number = rand::thread_rng().gen_range(1, 51);

    fix(guess_loop)(secret_number);
}

Sin embargo, aún no hemos terminado. Esto no se puede compilar con el siguiente error:

error[E0281]: type mismatch: the type `fn(i32, &_) {guess_loop::<_>}` implements the trait `for<''r> std::ops::Fn<(i32, &''r _)>`, but the trait `for<''r> std::ops::Fn<(i32, &''r Fix<fn(i32, &_) {guess_loop::<_>}>)>` is required (cyclic type of infinite size)
  --> src/main.rs:77:5
   |
77 |     fix(guess_loop)(secret_number);
   |     ^^^
   |
   = note: required by `fix`

Nota: En caso de que no lo sepa, en Rust, cada función tiene su propio tipo de tamaño cero. Si una función es genérica, entonces cada instanciación de esa función tendrá su propio tipo también. Por ejemplo, el tipo de guess_loop::<X> será reportado por el compilador como fn(i32, &X) {guess_loop::<X>} (como se puede ver en el mensaje de error anterior, excepto con guiones bajos donde lo concreto tipo aún no se ha resuelto). Ese tipo puede ser forzado a un tipo de puntero a función implícitamente en algunos contextos o explícitamente con un molde ( as ).

El problema es que, en el fix(guess_loop) expresión fix(guess_loop) , el compilador necesita crear guess_loop instancia de guess_loop , que es una función genérica, y parece que el compilador no es capaz de encontrar el tipo adecuado para instanciarlo. De hecho, el tipo que nos gustaría establecer para el parámetro de tipo F referencia al tipo de guess_loop . Si tuviéramos que escribirlo en el estilo reportado por el compilador, el tipo se vería como fn(i32, &Fix<X>) {guess_loop::<Fix<&X>>} , donde X es reemplazado por el tipo mismo ( ahora puede ver de dónde viene el "tipo cíclico de tamaño infinito").

Podemos resolver esto reemplazando la función guess_loop por una estructura no genérica (lo llamaremos GuessLoop ) que implementa Fn refiriéndose a sí mismo. (No puede hacer esto con una función normal porque no puede nombrar el tipo de una función).

struct GuessLoop;

impl<''a> FnOnce<(i32, &''a Fix<GuessLoop>)> for GuessLoop {
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32, &Fix<GuessLoop>)) -> Self::Output {
        self.call(args)
    }
}

impl<''a> FnMut<(i32, &''a Fix<GuessLoop>)> for GuessLoop {
    extern "rust-call" fn call_mut(&mut self, args: (i32, &Fix<GuessLoop>)) -> Self::Output {
        self.call(args)
    }
}

impl<''a> Fn<(i32, &''a Fix<GuessLoop>)> for GuessLoop {
    extern "rust-call" fn call(&self, (actual, recur): (i32, &Fix<GuessLoop>)) -> Self::Output {
        let guess_int = rand::thread_rng().gen_range(1, 51);

        if !try_guess(guess_int, actual) {
            recur(actual)
        }
    }
}

fn main() {
    let secret_number = rand::thread_rng().gen_range(1, 51);

    fix(GuessLoop)(secret_number);
}

Observe que la implementación de Fn de GuessLoop ya no es genérica en el tipo de parámetro recur . ¿Qué pasaría si intentáramos hacer genérica la implementación de Fn (mientras aún dejamos la estructura en sí no genérica, para evitar tipos cíclicos)?

struct GuessLoop;

impl<''a, F> FnOnce<(i32, &''a F)> for GuessLoop
    where F: Fn(i32),
{
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32, &''a F)) -> Self::Output {
        self.call(args)
    }
}

impl<''a, F> FnMut<(i32, &''a F)> for GuessLoop
    where F: Fn(i32),
{
    extern "rust-call" fn call_mut(&mut self, args: (i32, &''a F)) -> Self::Output {
        self.call(args)
    }
}

impl<''a, F> Fn<(i32, &''a F)> for GuessLoop
    where F: Fn(i32),
{
    extern "rust-call" fn call(&self, (actual, recur): (i32, &''a F)) -> Self::Output {
        let guess_int = rand::thread_rng().gen_range(1, 51);

        if !try_guess(guess_int, actual) {
            recur(actual)
        }
    }
}

Desafortunadamente, esto no se puede compilar con el siguiente error:

error[E0275]: overflow evaluating the requirement `<Fix<GuessLoop> as std::ops::FnOnce<(i32,)>>::Output == ()`
  --> src/main.rs:99:5
   |
99 |     fix(GuessLoop)(secret_number);
   |     ^^^
   |
   = note: required because of the requirements on the impl of `for<''r> std::ops::Fn<(i32, &''r Fix<GuessLoop>)>` for `GuessLoop`
   = note: required by `fix`

Básicamente, el compilador no puede verificar que Fix<GuessLoop> implemente Fn(i32) , porque para eso, necesita verificar que GuessLoop implementa Fn(i32, &Fix<GuessLoop>) , pero eso solo es cierto si se Fix<GuessLoop> implementa Fn(i32) (porque esa impl es condicional), lo cual solo es cierto si GuessLoop implementa Fn(i32, &Fix<GuessLoop>) (porque esa impl es condicional también), lo cual ... obtienes la idea. En otras palabras, las dos implementaciones de Fn dependen una de la otra y el compilador no puede resolver eso.

Answer 4

Esta es una respuesta a mi propia pregunta sobre la implementación del combinador Y, que es un subconjunto de esta pregunta. En la expresión lambda pura, se ve una versión del combinador Y

λf.(λw.w w)(λw.f (w w))

La solución en el Código Rosetta es demasiado complicada y se usa para asignar memoria en el montón. Quiero simplificar esto.

Primero, implementemos el tipo Mu<T> como un rasgo en su lugar.

trait Mu<T> {
    fn unroll(&self, &Mu<T>) -> T;
}

Tenga en cuenta que necesitamos que este rasgo sea seguro para los objetos, lo que significa que no podemos solicitar el valor Self en ninguna de sus definiciones, por lo que el segundo parámetro se escribe &Mu<T> y es un objeto de rasgo.

Ahora podemos escribir una implementación de trait genérico:

impl<T, F: Fn(&Mu<T>) -> T> Mu<T> for F {
    fn unroll(&self, o: &Mu<T>) -> T {
        self(o)
    }
}

Con esto, ahora podemos escribir el combinador y de la siguiente manera:

fn y<T, F: Fn(T) -> T>(f: &F) -> T {
    (&|w: &Mu<T>| w.unroll(w))(&|w: &Mu<T>| f(w.unroll(w)))
}

Lo anterior se compila en el área de juegos de Rust sin habilitar ninguna característica y utilizando solo el canal estable, por lo que esta es una muy buena respuesta a mi pregunta.

Sin embargo, lo anterior no funcionaría en la práctica porque Rust es llamada por valor, pero el código anterior es el combinador Y de llamada por nombre.

La solución call-by-value

Para trabajar con el canal estable sin requerir ninguna característica, no podemos devolver cierres (lo que requiere impl Trait ). En cambio, se me ocurrió crear otro tipo de Mu2 que toma dos parámetros de tipo:

trait Mu2<T, R> {
    fn unroll(&self, &Mu2<T, R>, t: T) -> R;
}

Como arriba, implementemos este nuevo rasgo.

impl<T, R, F> Mu2<T, R> for F
where
    F: Fn(&Mu2<T, R>, T) -> R,
{
    fn unroll(&self, o: &Mu2<T, R>, t: T) -> R {
        self(o, t)
    }
}

El nuevo combinador Y:

fn y<T, R, F>(f: &F, t: T) -> R
where
    F: Fn(&Fn(T) -> R, T) -> R,
{
    (&|w: &Mu2<T, R>, t| w.unroll(w, t))((&|w: &Mu2<T, R>, t| f(&|t| w.unroll(w, t), t)), t)
}

Ahora es el momento de probar nuestras nuevas instalaciones.

fn main() {
    let fac = &|f: &Fn(i32) -> i32, i| if i > 0 { i * f(i - 1) } else { 1 };
    println!("{}", y(fac, 10))
}

Resultados en:

3628800

¡Todo listo!

Puedes ver que la función y tiene una firma ligeramente diferente a la del fix , pero no debería importar.

La versión recurrente directa

La misma tecnología para evitar devolver un cierre también se puede utilizar para la versión recurrente directa normal:

fn fix<T, R, F>(f: &F, t: T) -> R
where
    F: Fn(&Fn(T) -> R, T) -> R,
{
    f(&|t| fix(f, t), t)        
}

fn fib(i: i32) -> i32 {
    let fn_ = &|f:&Fn(i32) -> i32, x| if x < 2 { x } else { f(x-1) + f(x-2) };
    fix(fn_, i)
}

Básicamente, cada vez que necesite devolver un cierre de una función, puede agregar el parámetro de cierre a la función y cambiar el tipo de retorno al tipo de retorno del cierre. Más adelante cuando necesites un cierre real, simplemente crea el cierre evaluando parcialmente esa función.

Discusiones adicionales

Compare con otros idiomas, en Rust hay una gran diferencia: la función dada para encontrar el punto fijo no debe tener ningún estado interno. En Rust este es un requisito para que el parámetro de tipo F de y deba ser Fn , no FnMut o FnOnce .

Por ejemplo, no podemos implementar un fix_mut que se usaría como

fn fib1(i: u32) -> u32 {
    let mut i0 = 1;
    let mut i1 = 1;
    let fn_ = &mut |f:&Fn(u32) -> u32, x| 
        match x {
            0 => i0,
            1 => i1,
            _ => {
                let i2 = i0;
                i0 = i1;
                i1 = i1 + i2;
                f(x)
            }
        };

    fix_mut(fn_, i)
}

sin código inseguro, mientras que esta versión, si funciona, funciona mucho mejor (O (N)) que la versión anterior (O (2 ^ N)).

Esto se debe a que solo puede tener uno &mut de un objeto a la vez. Pero la idea del combinador en Y, o incluso la función de punto fijo, requiere capturar / pasar la función al mismo tiempo cuando la llamas, eso son dos referencias y no puedes marcar cualquiera de ellas inmutable sin marcar otra cosa.

Por otro lado, me preguntaba si podríamos hacer algo que otros lenguajes usualmente no pueden pero Rust parece ser capaz. Estaba pensando en restringir el primer tipo de argumento de F de Fn a FnOnce (ya que la función y proporcionará la implementación, cambiar a FnMut no tiene sentido, sabemos que no tendrá estados, pero cambiar a FnOnce significa que queremos que se use solo una vez), Rust no lo permitiría en este momento, ya que no podemos pasar objetos no dimensionados por valor.

Entonces, básicamente, esta implementación es la solución más flexible que podríamos pensar.

Por cierto, el trabajo alrededor de la restricción inmutable es usar pseudo-mutación:

fn fib(i: u32) -> u32 {
    let fn_ = &|f:&Fn((u32,u32,u32)) -> u32, (x,i,j)| 
        match x {
            0 => i,
            1 => j,
            _ => {
                f((x-1,j,i+j))
            }
        };
    fix(&fn_, (i,1,1))
}