¿Se puede expresar * cualquier * tarea de programa sin estado?

13

Esta es una pregunta teórica, pero después de muchos años de programación en lo que ahora me doy cuenta es una técnica imperativa "normal", usando C ++ principalmente, descubrí este otro mundo de programación funcional, que me topé accidentalmente mientras aprendía JavaScript de manera casual.

Esto me ha llevado a preguntarme si técnicamente podría reemplazar cualquier programa completo orientado al estado con una implementación diferente que sea puramente funcional y sin estado.

Es una idea intrigante y debo admitir que hay una claridad y elegancia en la programación funcional que realmente me ha sorprendido.

javascript functional-programming haskell state turing-completeness johnbakers
fuente
1
Una respuesta relevante de StackOverflow: stackoverflow.com/questions/3722084/…
jfriend00
Que exista o no un estado que persista de un punto en el tiempo al siguiente no depende del paradigma de programación que utilice, sino de qué problema o tarea está codificando. Si está contando la cantidad de veces que se hace clic en un botón, entonces claramente hay un estado para registrar ese contador y no importa qué técnica de codificación use, tendrá que haber un estado para realizar un seguimiento del conteo durante el proceso. Por lo tanto, esa tarea en particular no se puede completar sin estado en el camino, sin importar cómo la codifique.
jfriend00
66
Si quieres hablar sobre el estado; se requiere claramente el estado, aunque solo sea para el programa en sí. Sin embargo, parece que está pensando en un estado mutable frente a un estado inmutable; es posible que desee indicar a qué se refiere en la pregunta.
Billy ONeal
1
Es como preguntar si todos los programas se pueden convertir en verdaderas máquinas de Turing. Técnicamente sí, incluso los programas que guardan y cargan desde una base de datos, sin embargo, se hace más difícil simular este comportamiento en una máquina Turing. Del mismo modo, podría tener un programa cuyo lado del controlador en la arquitectura MVC se elimine y realice todas las llamadas, aunque nuevamente, se vuelve más difícil manejar las magnitudes (esencialmente se convierte en el controlador para que el programa no tenga estado).
Neil

Respuestas:

17

Respuesta corta: sí. Según Wikipedia, Alan Turing demostró la equivalencia del cálculo lambda con las máquinas de Turing como modelo universal de cálculo en 1937. El modelo computacional de una máquina de Turing es lo que normalmente tiene en mente cuando habla de programación imperativa o con estado, y el cálculo lambda es una formalización matemática de la "programación funcional pura".

Se calcula que todo modelo efectivo de computación puede realizar los mismos cálculos que una máquina de Turing, y viceversa. Esto se llama tesis de Church-Turing . Sin embargo, esta conjetura no se puede probar debido al término más o menos intuitivo "modelo efectivo de cómputo" (¿tal vez alguien inventará un nuevo modelo en el futuro?)

Doc Brown
fuente
2
Su mismo argumento puede revertirse diciendo que, siendo el cálculo de lamba equivalente a las máquinas de turismo, cada cálculo debe tener un estado (más o menos oculto). Si se representa como externo al código (por medio de variables) o interno al flujo (por medio de una llamada de función basada en la pila), siempre se encuentra "estado".
Emilio Garavaglia
3
El cálculo lambda tiene estado; Su restricción es que el estado es inmutable. El estado inmutable sigue siendo el estado. Los parámetros de las funciones, incluidas las lambdas, siguen siendo estado; presumiblemente desea que una función tenga un comportamiento diferente dados parámetros diferentes.
Billy ONeal
@emilio Afirmar que existe una solución equivalente basada en estado para un problema (como usted describe) no es prueba de que no exista una versión sin estado de esa solución.
Billy ONeal
2
@ EmilioGaravaglia, se refiere al estado de un intérprete de cálculo lambda. Al razonar en el cálculo lambda, no hay necesidad de razonar sobre el estado. También el aspecto de "Mutabilidad" es diferente.
wirrbel
1
@EmilioGaravglia: El estado en la programación imperativa es la configuración de memoria a la vez, aquí el espacio de parámetros viene dado por todos los valores de memoria posibles y el estado es una configuración a la vez (banda de la máquina de turing). Al escribir un programa en el cálculo lambda, no hay una entidad directa como un campo de memoria. La ejecución del programa es la aplicación de transformaciones lambda. Los pasos intermedios pueden parecerse al "estado", pero son expresiones equivalentes del mismo valor. Nada cambia durante la evaluación, las expresiones simplemente se reescriben y procesan en una forma "más simple".
wirrbel
14

En cualquier sistema dinámico, el "estado" es lo que hace que su presente sea ​​influenciado por su pasado o futuro (la flecha del tiempo no es un problema matemático, solo una restricción física).

Si tiene algo que "recordar" o que depende de lo que hizo, tiene un estado.

Un sistema sin estado no es "dinámico": es solo una función combinatoria. Es posible que eso no tenga un estado, pero, para producir resultados diferentes, necesita un estado que se suministre de alguna manera.

Ahora, dependiendo del modelo computacional al que se refiera, un estado puede representarse explícitamente (en forma de variable) o implícitamente (en forma de "direcciones de retorno").

cuando lo haces, fna(fnb(x))estás dando un estado a fnb que a su vez producirá un estado para fna. Esto se debe al hecho de que xexiste antes de que se llame fnb (por lo tanto, proviene de su propio "pasado").

No es una cuestión de "estado existente" o "estado no existe". Es una cuestión de "me importa" o "no me importa".

Emilio Garavaglia
fuente
0

Estado significa la capacidad de responder a un estímulo presente de una manera que depende de estímulos pasados, no solo en función del estímulo presente.

Los programas puramente funcionales son solo funciones. Por lo tanto, para aplicaciones prácticas, el programa puramente funcional ingresa un par (old_state * present_stimulus) y genera un par (new_state * present_response). Se necesita un "bucle" externo con estado para esperar el próximo estímulo y propagar el estado.

Un programa puramente funcional no tiene un estado intrínseco y no puede usarse directamente para aplicaciones prácticas.

Por lo tanto, ningún programa orientado al estado puede ser reemplazado por una implementación diferente que sea puramente funcional y sin estado.

Atsby
fuente
0

Puede evitar el estado mutable explícito siempre que no tenga que interactuar con el mundo exterior.

En JavaScript para que su programa realmente tenga un efecto más allá de tomar ciclos de procesador, debe modificar el objeto Dom o Window, y estas API tienen estado. Pero supongo que podría crear un contenedor que pasara los objetos Dom y Window como parámetros al código JavaScript, y luego recibiera un nuevo Dom / Window como salida. Esto aislaría el código JavaScript del estado mutable.

Por supuesto, todavía depende del estado, ya que la ventana del navegador y el DOM tienen estado por naturaleza. Cualquier aplicación interactiva es inherentemente con estado, pero aún puede estructurar su código de manera tal que minimice el estado explícito.

Una pregunta diferente es si es una buena idea. Incluso Haskell, que es un lenguaje funcional puro por diseño, incluye la mónada 'estado', que le permite simular un estado mutable. Esto muestra que el estado mutable explícito a veces es realmente un patrón deseable.

JacquesB
fuente
0

Piense en cómo implementaría una "máquina de estado" en un lenguaje de programación sin estado.

Probablemente podría hacerlo, pero terminaría usando nombres de funciones como almacenamiento. Terminando con gobblyday gook como:

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()
James Anderson
fuente