¿Cómo puede existir una función de tiempo en la programación funcional?

Tengo que admitir que no sé mucho sobre programación funcional. Lo leí de aquí y de allá, y entonces supe que en la programación funcional, una función devuelve la misma salida, para la misma entrada, sin importar cuántas veces se llame a la función. Es exactamente como una función matemática que evalúa la misma salida para el mismo valor de los parámetros de entrada que implica la expresión de la función.

Por ejemplo, considere esto:

f(x,y) = x*x + y; // It is a mathematical function

No importa cuántas veces use f(10,4), su valor siempre será 104. Como tal, donde sea que haya escrito f(10,4), puede reemplazarlo 104sin alterar el valor de toda la expresión. Esta propiedad se conoce como transparencia referencial de una expresión.

Como dice Wikipedia ( enlace ),

Por el contrario, en el código funcional, el valor de salida de una función depende solo de los argumentos que se ingresan a la función, por lo que llamar a una función f dos veces con el mismo valor para un argumento x producirá el mismo resultado f (x) las dos veces.

¿Puede existir una función de tiempo (que devuelve la hora actual ) en la programación funcional?

• En caso afirmativo, ¿cómo puede existir? ¿No viola el principio de programación funcional? Viola particularmente la transparencia referencial, que es una de las propiedades de la programación funcional (si la entiendo correctamente).

• O si no, ¿cómo se puede saber la hora actual en la programación funcional?

Otra forma de explicarlo es esta: ninguna función puede obtener la hora actual (ya que sigue cambiando), pero una acción puede obtener la hora actual. Digamos que getClockTimees una constante (o una función nula, si lo desea) que representa la acción de obtener la hora actual. Esta acción es la misma cada vez, sin importar cuándo se use, por lo que es una constante real.

Del mismo modo, digamos que printes una función que requiere algo de tiempo de representación y la imprime en la consola. Dado que las llamadas a funciones no pueden tener efectos secundarios en un lenguaje funcional puro, en su lugar imaginamos que es una función que toma una marca de tiempo y devuelve la acción de imprimirla a la consola. Nuevamente, esta es una función real, porque si le da la misma marca de tiempo, devolverá la misma acción de imprimirla cada vez.

Ahora, ¿cómo puede imprimir la hora actual en la consola? Bueno, tienes que combinar las dos acciones. Entonces, ¿cómo podemos hacer eso? No podemos pasar getClockTimea print, ya que print espera una marca de tiempo, no una acción. Pero podemos imaginar que hay un operador, >>=que combina dos acciones, una que recibe una marca de tiempo y otra que toma una como argumento y la imprime. Aplicando esto a las acciones mencionadas anteriormente, el resultado es ... tadaaa ... una nueva acción que obtiene la hora actual y la imprime. Y esto es, por cierto, exactamente cómo se hace en Haskell.

Prelude> System.Time.getClockTime >>= print
Fri Sep  2 01:13:23 東京 (標準時) 2011

Entonces, conceptualmente, puede verlo de esta manera: un programa funcional puro no realiza ninguna E / S, define una acción , que luego ejecuta el sistema de tiempo de ejecución. La acción es la misma cada vez, pero el resultado de ejecutarla depende de las circunstancias de cuándo se ejecuta.

No sé si esto fue más claro que las otras explicaciones, pero a veces me ayuda a pensarlo así.

Si y no.

Diferentes lenguajes de programación funcional los resuelven de manera diferente.

En Haskell (uno muy puro), todo esto tiene que suceder en algo llamado la Mónada de E / S , mira aquí .

Puede pensar en ello como obtener otra entrada (y salida) en su función (el estado mundial) o más fácil como un lugar donde ocurre "impureza", como obtener el cambio de tiempo.

Otros lenguajes como F # solo tienen algo de impureza incorporada, por lo que puede tener una función que devuelve diferentes valores para la misma entrada, al igual que los lenguajes imperativos normales .

Como Jeffrey Burka mencionó en su comentario: Aquí está la buena introducción a la I / O Monad directamente de la wiki de Haskell.

En Haskell se usa una construcción llamada mónada para manejar los efectos secundarios. Una mónada básicamente significa que encapsula valores en un contenedor y tiene algunas funciones para encadenar funciones de valores a valores dentro de un contenedor. Si nuestro contenedor tiene el tipo:

data IO a = IO (RealWorld -> (a,RealWorld))

podemos implementar de manera segura acciones de IO Este tipo significa: Una acción de tipo IOes una función, que toma un token de tipo RealWorldy devuelve un nuevo token, junto con un resultado.

La idea detrás de esto es que cada acción de IO muta el estado exterior, representado por la ficha mágica RealWorld. Usando mónadas, uno puede encadenar múltiples funciones que mutan el mundo real juntos. La función más importante de una mónada es >>=, enlace pronunciado :

(>>=) :: IO a -> (a -> IO b) -> IO b

>>=toma una acción y una función que toma el resultado de esta acción y crea una nueva acción a partir de esto. El tipo de retorno es la nueva acción. Por ejemplo, supongamos que hay una función now :: IO String, que devuelve una Cadena que representa la hora actual. Podemos encadenarlo con la función putStrLnpara imprimirlo:

now >>= putStrLn

O escrito en do-Notación, que es más familiar para un programador imperativo:

do currTime <- now
   putStrLn currTime

Todo esto es puro, ya que mapeamos la mutación y la información sobre el mundo exterior a la RealWorldficha. Entonces, cada vez que ejecuta esta acción, obtiene, por supuesto, una salida diferente, pero la entrada no es la misma: el RealWorldtoken es diferente.

La mayoría de los lenguajes de programación funcionales no son puros, es decir, permiten que las funciones no solo dependan de sus valores. En esos idiomas es perfectamente posible tener una función que devuelva la hora actual. De los idiomas que etiquetó esta pregunta, esto se aplica a Scala y F # (así como a la mayoría de las otras variantes de ML ).

En idiomas como Haskell y Clean , que son puros, la situación es diferente. En Haskell, el tiempo actual no estaría disponible a través de una función, sino una llamada acción IO, que es la forma en que Haskell encapsula los efectos secundarios.

En Clean sería una función, pero la función tomaría un valor mundial como argumento y devolvería un nuevo valor mundial (además de la hora actual) como resultado. El sistema de tipos se aseguraría de que cada valor mundial se pueda usar solo una vez (y cada función que consume un valor mundial produciría uno nuevo). De esta manera, la función de tiempo debería llamarse con un argumento diferente cada vez y, por lo tanto, se le permitiría devolver una hora diferente cada vez.

"Hora actual" no es una función. Es un parámetro. Si su código depende de la hora actual, significa que su código está parametrizado por tiempo.

Se puede hacer absolutamente de una manera puramente funcional. Hay varias formas de hacerlo, pero la más simple es hacer que la función de tiempo devuelva no solo la hora, sino también la función que debe llamar para obtener la próxima medición de tiempo .

En C # podrías implementarlo así:

// Exposes mutable time as immutable time (poorly, to illustrate by example)
// Although the insides are mutable, the exposed surface is immutable.
public class ClockStamp {
    public static readonly ClockStamp ProgramStartTime = new ClockStamp();
    public readonly DateTime Time;
    private ClockStamp _next;

    private ClockStamp() {
        this.Time = DateTime.Now;
    }
    public ClockStamp NextMeasurement() {
        if (this._next == null) this._next = new ClockStamp();
        return this._next;
    }
}

(Tenga en cuenta que este es un ejemplo que pretende ser simple, no práctico. En particular, los nodos de la lista no se pueden recolectar basura porque están arraigados por ProgramStartTime).

Esta clase 'ClockStamp' actúa como una lista vinculada inmutable, pero en realidad los nodos se generan a pedido para que puedan contener el tiempo 'actual'. Cualquier función que quiera medir el tiempo debe tener un parámetro 'clockStamp' y también debe devolver su última medición de tiempo en su resultado (para que la persona que llama no vea las mediciones antiguas), así:

// Immutable. A result accompanied by a clockstamp
public struct TimeStampedValue<T> {
    public readonly ClockStamp Time;
    public readonly T Value;
    public TimeStampedValue(ClockStamp time, T value) {
        this.Time = time;
        this.Value = value;
    }
}

// Times an empty loop.
public static TimeStampedValue<TimeSpan> TimeALoop(ClockStamp lastMeasurement) {
    var start = lastMeasurement.NextMeasurement();
    for (var i = 0; i < 10000000; i++) {
    }
    var end = start.NextMeasurement();
    var duration = end.Time - start.Time;
    return new TimeStampedValue<TimeSpan>(end, duration);
}

public static void Main(String[] args) {
    var clock = ClockStamp.ProgramStartTime;
    var r = TimeALoop(clock);
    var duration = r.Value; //the result
    clock = r.Time; //must now use returned clock, to avoid seeing old measurements
}

Por supuesto, es un poco incómodo tener que pasar esa última medición dentro y fuera, dentro y fuera, dentro y fuera. Hay muchas maneras de ocultar la repetitiva, especialmente en el nivel de diseño del lenguaje. Creo que Haskell usa este tipo de truco y luego oculta las partes feas usando mónadas.

Me sorprende que ninguna de las respuestas o comentarios mencionen coalgebras o coinducción. Por lo general, la coinducción se menciona al razonar sobre estructuras de datos infinitas, pero también es aplicable a un flujo interminable de observaciones, como un registro de tiempo en una CPU. Una coalgebra modela el estado oculto; y modelos de coinducción observando ese estado. (Modelos de inducción normales que construyen el estado).

Este es un tema candente en la Programación funcional reactiva. Si está interesado en este tipo de cosas, lea esto: http://digitalcommons.ohsu.edu/csetech/91/ (28 pp.)

Sí, es posible que una función pura devuelva el tiempo, si se le da ese tiempo como parámetro. Diferente argumento de tiempo, resultado de tiempo diferente. Luego, forme también otras funciones del tiempo y combínelas con un vocabulario simple de funciones (-de-tiempo) -transformadoras (de orden superior). Dado que el enfoque no tiene estado, el tiempo aquí puede ser continuo (independiente de la resolución) en lugar de discreto, lo que aumenta enormemente la modularidad . Esta intuición es la base de la Programación Reactiva Funcional (FRP).

¡Si! ¡Estás en lo correcto! Now () o CurrentTime () o cualquier firma de método de dicho sabor no exhibe transparencia referencial de una manera. Pero mediante instrucciones al compilador se parametriza mediante una entrada de reloj del sistema.

Por salida, Now () podría parecer que no sigue la transparencia referencial. Pero el comportamiento real del reloj del sistema y la función en la parte superior se adhiere a la transparencia referencial.

Sí, puede existir una función de tiempo de obtención en la programación funcional utilizando una versión ligeramente modificada en la programación funcional conocida como programación funcional impura (la predeterminada o la principal es la programación funcional pura).

En caso de obtener el tiempo (o leer el archivo o lanzar un misil), el código debe interactuar con el mundo exterior para hacer el trabajo y este mundo exterior no se basa en los fundamentos puros de la programación funcional. Para permitir que un mundo de programación funcional pura interactúe con este mundo exterior impuro, las personas han introducido programación funcional impura. Después de todo, el software que no interactúa con el mundo exterior no es más útil que hacer algunos cálculos matemáticos.

Pocos lenguajes de programación funcionales tienen esta característica de impureza incorporada de manera tal que no es fácil separar qué código es impuro y cuál es puro (como F #, etc.) y algunos lenguajes de programación funcional se aseguran de que cuando haces algunas cosas impuras ese código se destaca claramente en comparación con el código puro, como Haskell.

Otra forma interesante de ver esto sería que su función de obtener tiempo en la programación funcional tomaría un objeto "mundial" que tiene el estado actual del mundo como el tiempo, la cantidad de personas que viven en el mundo, etc. el objeto siempre sería puro, es decir, si pasas en el mismo estado mundial, siempre obtendrás el mismo tiempo

Su pregunta combina dos medidas relacionadas de un lenguaje de computadora: funcional / imperativo y puro / impuro.

Un lenguaje funcional define las relaciones entre entradas y salidas de funciones, y un lenguaje imperativo describe operaciones específicas en un orden específico para realizar.

Un lenguaje puro no crea ni depende de los efectos secundarios, y un lenguaje impuro los usa en todo momento.

Los programas cien por ciento puros son básicamente inútiles. Pueden realizar un cálculo interesante, pero como no pueden tener efectos secundarios, no tienen entrada ni salida, por lo que nunca sabría lo que calcularon.

Para que sea útil, un programa debe ser al menos un poco impuro. Una forma de hacer que un programa puro sea útil es ponerlo dentro de una envoltura delgada impura. Como este programa Haskell no probado:

-- this is a pure function, written in functional style.
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

-- This is an impure wrapper around the pure function, written in imperative style
-- It depends on inputs and produces outputs.
main = do
    putStrLn "Please enter the input parameter"
    inputStr <- readLine
    putStrLn "Starting time:"
    getCurrentTime >>= print
    let inputInt = read inputStr    -- this line is pure
    let result = fib inputInt       -- this is also pure
    putStrLn "Result:"
    print result
    putStrLn "Ending time:"
    getCurrentTime >>= print

Está abordando un tema muy importante en la programación funcional, es decir, realizar E / S. La forma en que lo hacen muchos lenguajes puros es mediante el uso de lenguajes específicos de dominio integrados, por ejemplo, un sublenguaje cuya tarea es codificar acciones , que pueden tener resultados.

El tiempo de ejecución de Haskell, por ejemplo, espera que defina una acción llamada mainque se compone de todas las acciones que componen mi programa. El tiempo de ejecución luego ejecuta esta acción. La mayoría de las veces, al hacerlo, ejecuta código puro. De vez en cuando, el tiempo de ejecución utilizará los datos calculados para realizar E / S y retroalimenta los datos en código puro.

Puede quejarse de que esto suena como trampa, y de alguna manera lo es: al definir acciones y esperar que el tiempo de ejecución las ejecute, el programador puede hacer todo lo que un programa normal puede hacer. Pero el sistema de tipo fuerte de Haskell crea una fuerte barrera entre las partes puras e "impuras" del programa: no puede simplemente agregar, digamos, dos segundos al tiempo actual de la CPU e imprimirlo, debe definir una acción que resulte en el actual Tiempo de CPU y pasar el resultado a otra acción que agrega dos segundos e imprime el resultado. Sin embargo, escribir demasiado sobre un programa se considera un mal estilo, porque hace que sea difícil inferir qué efectos se causan, en comparación con los tipos de Haskell que nos dicen todo lo que podemos saber sobre el valor.

Ejemplo: clock_t c = time(NULL); printf("%d\n", c + 2);en C, vs. main = getCPUTime >>= \c -> print (c + 2*1000*1000*1000*1000)en Haskell. El operador >>=se utiliza para componer acciones, pasando el resultado de la primera a una función que resulta en la segunda acción. Con un aspecto bastante arcano, los compiladores Haskell admiten el azúcar sintáctico que nos permite escribir el último código de la siguiente manera:

type Clock = Integer -- To make it more similar to the C code

-- An action that returns nothing, but might do something
main :: IO ()
main = do
    -- An action that returns an Integer, which we view as CPU Clock values
    c <- getCPUTime :: IO Clock
    -- An action that prints data, but returns nothing
    print (c + 2*1000*1000*1000*1000) :: IO ()

Este último parece bastante imperativo, ¿no?

En caso afirmativo, ¿cómo puede existir? ¿No viola el principio de programación funcional? Viola particularmente la transparencia referencial

No existe en un sentido puramente funcional.

O si no, ¿cómo se puede saber la hora actual en la programación funcional?

Primero puede ser útil saber cómo se recupera un tiempo en una computadora. Esencialmente, hay circuitos integrados que registran el tiempo (que es la razón por la cual una computadora generalmente necesitaría una batería de celda pequeña). Entonces podría haber algún proceso interno que establezca el valor del tiempo en un determinado registro de memoria. Que esencialmente se reduce a un valor que puede ser recuperado por la CPU.

Para Haskell, existe un concepto de una 'acción de IO' que representa un tipo que se puede hacer para llevar a cabo algún proceso de IO. Entonces, en lugar de hacer referencia a un timevalor, hacemos referencia a un IO Timevalor. Todo esto sería puramente funcional. No estamos haciendo referencia a timealgo como "leer el valor del registro de tiempo" .

Cuando realmente ejecutamos el programa Haskell, la acción IO realmente se llevaría a cabo.