Como pode existir uma função de tempo na programação funcional?

Devo admitir que não sei muito sobre programação funcional. Eu li sobre isso daqui e dali e, assim, soube que na programação funcional, uma função retorna a mesma saída, para a mesma entrada, não importa quantas vezes a função seja chamada. É exatamente como uma função matemática que avalia a mesma saída para o mesmo valor dos parâmetros de entrada que envolvem a expressão da função.

Por exemplo, considere isso:

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

Não importa quantas vezes você use f(10,4), seu valor sempre será 104. Assim, onde quer que você tenha escrito f(10,4), você pode substituí-lo por 104, sem alterar o valor de toda a expressão. Essa propriedade é chamada de transparência referencial de uma expressão.

Como a Wikipedia diz ( link ),

Por outro lado, no código funcional, o valor de saída de uma função depende apenas dos argumentos introduzidos na função, portanto, chamar uma função f duas vezes com o mesmo valor para um argumento x produzirá o mesmo resultado f (x) nas duas vezes.

Pode uma função de hora (que retorna a hora atual ) existir na programação funcional?

• Se sim, então como pode existir? Não viola o princípio da programação funcional? Isso viola particularmente a transparência referencial, que é uma das propriedades da programação funcional (se bem entendi).

• Ou, se não, como saber a hora atual da programação funcional?

Outra maneira de explicar isso é: nenhuma função pode obter a hora atual (uma vez que continua mudando), mas uma ação pode obter a hora atual. Digamos que getClockTimeseja uma constante (ou uma função nula, se você preferir), que representa a ação de obter a hora atual. Essa ação é a mesma sempre, não importa quando é usada, portanto é uma constante real.

Da mesma forma, digamos que printé uma função que leva algum tempo para representar e imprime no console. Como as chamadas de função não podem ter efeitos colaterais em uma linguagem funcional pura, imaginamos que é uma função que leva um registro de data e hora e retorna a ação de imprimi-lo no console. Novamente, essa é uma função real, porque se você fornecer o mesmo carimbo de data / hora, ele retornará a mesma ação de imprimi-lo sempre.

Agora, como você pode imprimir a hora atual no console? Bem, você tem que combinar as duas ações. Então, como podemos fazer isso? Não podemos simplesmente passar getClockTimepara print, já que a impressão espera um carimbo de data e hora, não uma ação. Mas podemos imaginar que existe um operador, >>=que combina duas ações, uma que obtém um registro de data e hora e uma que aceita um como argumento e o imprime. Aplicando isso às ações mencionadas anteriormente, o resultado é ... tadaaa ... uma nova ação que obtém a hora atual e a imprime. E isso é exatamente como é feito em Haskell.

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

Portanto, conceitualmente, você pode visualizá-lo desta maneira: Um programa funcional puro não executa nenhuma E / S, define uma ação que o sistema de tempo de execução executa. A ação é a mesma sempre, mas o resultado da execução depende das circunstâncias de quando é executada.

Não sei se isso foi mais claro do que as outras explicações, mas às vezes me ajuda a pensar dessa maneira.

Sim e não.

Diferentes linguagens de programação funcional as resolvem de maneira diferente.

Em Haskell (muito puro), tudo isso precisa acontecer em algo chamado de I / O Monad - veja aqui .

Você pode pensar nisso como colocar outra entrada (e saída) em sua função (o estado mundial) ou mais fácil como um lugar onde "impurezas", como a mudança do horário, acontecem.

Outros idiomas, como o F #, possuem algumas impurezas incorporadas e, portanto, você pode ter uma função que retorna valores diferentes para a mesma entrada - assim como os idiomas imperativos normais .

Como Jeffrey Burka mencionou em seu comentário: Aqui está uma boa introdução à I / O Monad diretamente do wiki Haskell.

Em Haskell, usa-se uma construção chamada mônada para lidar com efeitos colaterais. Uma mônada basicamente significa que você encapsula valores em um contêiner e tem algumas funções para encadear funções de valores para valores dentro de um contêiner. Se nosso contêiner tiver o tipo:

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

podemos implementar com segurança ações de E / S. Este tipo significa: Uma ação do tipo IOé uma função que pega um token do tipo RealWorlde retorna um novo token, juntamente com um resultado.

A idéia por trás disso é que cada ação de IO muda o estado externo, representado pelo token mágico RealWorld. Usando mônadas, é possível encadear várias funções que mutam o mundo real. A função mais importante de uma mônada é a ligação>>= pronunciada :

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

>>=executa uma ação e uma função que obtém o resultado dessa ação e cria uma nova ação a partir disso. O tipo de retorno é a nova ação. Por exemplo, vamos fingir que existe uma função now :: IO String, que retorna uma String representando a hora atual. Podemos encadear com a função putStrLnpara imprimi-lo:

now >>= putStrLn

Ou escrito em do-Notation, que é mais familiar para um programador imperativo:

do currTime <- now
   putStrLn currTime

Tudo isso é puro, pois mapeamos a mutação e as informações sobre o mundo externo para o RealWorldtoken. Portanto, toda vez que você executa esta ação, é claro que obtém uma saída diferente, mas a entrada não é a mesma: o RealWorldtoken é diferente.

A maioria das linguagens de programação funcional não é pura, ou seja, permite que as funções não dependam apenas de seus valores. Nesses idiomas, é perfeitamente possível ter uma função retornando a hora atual. Nos idiomas em que você marcou esta pergunta, isso se aplica ao Scala e ao F # (assim como à maioria das outras variantes do ML ).

Em idiomas como Haskell e Clean , que são puros, a situação é diferente. Em Haskell, o tempo atual não estaria disponível por meio de uma função, mas da ação de E / S, que é a maneira de Haskell de encapsular os efeitos colaterais.

Em Clean, seria uma função, mas a função usaria um valor mundial como argumento e retornaria um novo valor mundial (além do horário atual) como resultado. O sistema de tipos garantiria que cada valor mundial possa ser usado apenas uma vez (e cada função que consome um valor mundial produziria um novo). Dessa forma, a função de tempo teria que ser chamada com um argumento diferente a cada vez e, portanto, seria permitido retornar um tempo diferente a cada vez.

"Hora atual" não é uma função. É um parâmetro. Se o seu código depende da hora atual, isso significa que ele é parametrizado pelo tempo.

Pode absolutamente ser feito de uma maneira puramente funcional. Existem várias maneiras de fazer isso, mas a mais simples é fazer com que a função de tempo retorne não apenas a hora, mas também a função que você deve chamar para obter a próxima medição de hora .

Em C #, você poderia implementá-lo assim:

// 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;
    }
}

(Lembre-se de que este é um exemplo simples, não prático. Em particular, os nós da lista não podem ser coletados como lixo porque estão enraizados no ProgramStartTime.)

Essa classe 'ClockStamp' atua como uma lista vinculada imutável, mas, na verdade, os nós são gerados sob demanda para que possam conter o horário 'atual'. Qualquer função que queira medir o tempo deve ter um parâmetro 'clockStamp' e também deve retornar sua última medição de tempo em seu resultado (para que o chamador não veja medições antigas), assim:

// 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
}

Obviamente, é um pouco inconveniente ter que passar a última medida dentro e fora, dentro e fora, dentro e fora. Existem várias maneiras de ocultar o padrão, especialmente no nível do design do idioma. Acho que Haskell usa esse tipo de truque e depois oculta as partes feias usando mônadas.

Surpreende-me que nenhuma das respostas ou comentários mencione barras de carvão ou coindução. Geralmente, a coindução é mencionada ao raciocinar sobre estruturas de dados infinitas, mas também é aplicável a um fluxo interminável de observações, como um registro de tempo em uma CPU. A coalgebra modela o estado oculto; e modelos de coindução observando esse estado. (Modelos de indução normal construindo estado.)

Este é um tópico importante na Programação Funcional Reativa. Se você estiver interessado nesse tipo de coisa, leia o seguinte: http://digitalcommons.ohsu.edu/csetech/91/ (28 pp.)

Sim, é possível que uma função pura retorne a hora, se ela tiver esse tempo como parâmetro. Argumento de tempo diferente, resultado de tempo diferente. Em seguida, forme também outras funções do tempo e combine-as com um vocabulário simples de funções de transformação de funções (de tempo), de ordem superior. Como a abordagem é apátrida, o tempo aqui pode ser contínuo (independente da resolução) e não discreto, aumentando bastante a modularidade . Essa intuição é a base da Programação Reativa Funcional (FRP).

Sim! Você está certo! Now () ou CurrentTime () ou qualquer assinatura de método desse tipo não exibe transparência referencial de uma maneira. Mas, por instrução ao compilador, é parametrizado por uma entrada de relógio do sistema.

Por saída, o Now () pode parecer que não segue a transparência referencial. Mas o comportamento real do relógio do sistema e a função em cima dele aderem à transparência referencial.

Sim, uma função de obtenção de tempo pode existir na programação funcional usando uma versão ligeiramente modificada na programação funcional conhecida como programação funcional impura (a padrão ou a principal é a programação funcional pura).

No caso de obter tempo (ou ler arquivo ou lançar míssil), o código precisa interagir com o mundo exterior para realizar o trabalho e esse mundo exterior não se baseia nos fundamentos puros da programação funcional. Para permitir que um mundo de programação funcional puro interaja com esse mundo exterior impuro, as pessoas introduziram a programação funcional impura. Afinal, o software que não interage com o mundo exterior não é útil além de fazer alguns cálculos matemáticos.

Poucas linguagens de programação de programação funcional possuem esse recurso de impureza embutido, de forma que não é fácil separar qual código é impuro e o que é puro (como F #, etc.) e algumas linguagens de programação funcionais garantem que, quando você faz algumas coisas impuras esse código se destaca claramente em comparação com o código puro, como Haskell.

Outra maneira interessante de ver isso seria que sua função get time na programação funcional usaria um objeto "mundo" que possui o estado atual do mundo como tempo, número de pessoas que vivem no mundo etc. O objeto seria sempre puro, ou seja, se você passar no mesmo estado mundial, sempre terá o mesmo tempo.

Sua pergunta combina duas medidas relacionadas a uma linguagem de computador: funcional / imperativa e pura / impura.

Uma linguagem funcional define relacionamentos entre entradas e saídas de funções, e uma linguagem imperativa descreve operações específicas em uma ordem específica para executar.

Uma linguagem pura não cria ou depende de efeitos colaterais, e uma linguagem impura os usa por toda parte.

Programas 100% puros são basicamente inúteis. Eles podem executar um cálculo interessante, mas, como não podem ter efeitos colaterais, não têm entrada ou saída, portanto você nunca saberia o que eles calcularam.

Para ser útil, um programa deve ser pelo menos um pouco impuro. Uma maneira de tornar útil um programa puro é colocá-lo dentro de um invólucro impuro fino. Como este programa Haskell não testado:

-- 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

Você está abordando um assunto muito importante em programação funcional, ou seja, executando E / S. A maneira como muitas línguas puras realizam isso é usando linguagens específicas de domínio incorporadas, por exemplo, uma sub-linguagem cuja tarefa é codificar ações , que podem ter resultados.

O tempo de execução Haskell, por exemplo, espera que eu defina uma ação chamada mainque é composta por todas as ações que compõem meu programa. O tempo de execução então executa esta ação. Na maioria das vezes, ao fazer isso, ele executa código puro. De tempos em tempos, o tempo de execução usa os dados computados para executar E / S e retorna dados em código puro.

Você pode reclamar que isso parece trapaça, e de certa forma: ao definir ações e esperar que o tempo de execução as execute, o programador pode fazer tudo o que um programa normal pode fazer. Mas o sistema de tipo forte de Haskell cria uma forte barreira entre partes puras e "impuras" do programa: você não pode simplesmente adicionar, digamos, dois segundos ao tempo atual da CPU e imprimi-lo, é necessário definir uma ação que resulte no atual Tempo de CPU e passe o resultado para outra ação que adiciona dois segundos e imprime o resultado. Escrever um programa em excesso é considerado um estilo ruim, porque torna difícil inferir quais efeitos são causados, em comparação com os tipos de Haskell que nos dizem tudo o que podemos saber sobre o que é um valor.

Exemplo: clock_t c = time(NULL); printf("%d\n", c + 2);em C, vs. main = getCPUTime >>= \c -> print (c + 2*1000*1000*1000*1000)em Haskell. O operador >>=é usado para compor ações, passando o resultado do primeiro para uma função que resulta na segunda ação. Este compilador Haskell, que parece bastante misterioso, suporta açúcar sintático que nos permite escrever o último código da seguinte maneira:

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 ()

O último parece bastante imperativo, não é?

Se sim, então como pode existir? Não viola o princípio da programação funcional? Viola particularmente a transparência referencial

Não existe em um sentido puramente funcional.

Ou, se não, como saber a hora atual da programação funcional?

Pode ser útil primeiro saber como é recuperada uma hora no computador. Basicamente, existem circuitos integrados que acompanham o tempo (razão pela qual um computador normalmente precisa de uma pequena bateria de celular). Pode haver algum processo interno que define o valor do tempo em um determinado registro de memória. O que basicamente se resume a um valor que pode ser recuperado pela CPU.

Para Haskell, existe o conceito de uma 'ação de E / S' que representa um tipo que pode ser feito para executar algum processo de E / S. Então, em vez de referenciar um timevalor, fazemos referência a um IO Timevalor. Tudo isso seria puramente funcional. Não estamos referenciando, timemas algo como 'leia o valor do registro de horas' .

Quando realmente executamos o programa Haskell, a ação de E / S ocorreria.