¿Se puede representar todo el código como una serie de operaciones de Mapa / Filtro / Reducción?

16

Recientemente he estado refactorizando grandes fragmentos de código y reemplazándolos con consultas de Linq.

Eliminar el sesgo de idioma: Linq es esencialmente un conjunto de operaciones de Mapa / Filtro y Reducción que operan en una secuencia de datos.

Esto me hizo pensar, ¿hasta dónde podría llegar en teoría? ¿Podría reescribir todo el código base en una serie (o incluso una sola) de operaciones de Mapa / Filtro y Reducción.

Desafortunadamente, me pagan por hacer cosas útiles, por lo que no he podido experimentar mucho más, pero no puedo pensar en ninguna estructura de código que no se pueda reestructurar como tal. El código de efecto lateral puede tratarse a través de mónadas. Incluso la salida es esencialmente asignar direcciones de memoria a direcciones de pantalla.

¿Hay algo que no pueda (teóricamente) reescribirse como una consulta de Linq?

computer-science Mongus Pong
fuente
Para ver árboles, consulte aquí: stackoverflow.com/questions/250377/…
blueberryfields
Siempre pensé que "reducir" es suficiente para garantizar la finalización de Turing (el mapa y el filtro se pueden implementar como operaciones de reducción, ¿no?), Al menos, el equivalente en lenguaje funcional de reducir. No sé lo suficiente sobre Linq para estar seguro de cuán estrechamente la implementación sigue a la funcional.
blueberryfields
1
No lo sé, pero una regla general es que cualquier cosa que alguien considere escribir todo su código resultará ser Turing completo. Pero el corolario de eso es que estar Turing completo no es muy emocionante.
psr
1
Estoy de acuerdo con psr; Creo que una respuesta válida a esta pregunta debe abordar la integridad de Turing. Una prueba podría intentar implementar una máquina Turing utilizando solo estas operaciones.
Rob
Pensamiento inactivo: incluso si permitimos my_list.map(_ignored => a copy of my_list)cosas sin sentido , parece que el uso del espacio de dicho programa está limitado por algún polinomio (dependiendo de la duración del programa). Entonces, tal lenguaje ciertamente no podría calcular problemas que no están en PSPACE. Sin embargo, como muchos problemas en PSPACE se consideran invencibles, por no mencionar las clases más grandes, esto puede no ser una restricción muy seria.

Respuestas:

1

Se llama programación funcional, y muchos lo consideran un concepto fundamental. Aquí hay una buena introducción sobre Joel On Software . La respuesta más técnica es no, actualmente no existe una forma conocida de hacer preguntas a su computadora (de una manera bien definida) que no puedan responderse a través del cálculo de SKI.

JP Mcgrady
fuente
1
Hay mucho más en la programación funcional que las funciones map, filtery reduce(esto va tres veces si ignoramos la integridad completa y usamos lenguajes FP prácticos). De hecho, resultan ser bastante generales y, por lo tanto, generalmente útiles, pero en realidad son aplicaciones muy simples de programación funcional. El cálculo lambda mínimo desnudo puede definir esas funciones entre muchas otras, no al revés.
"Aquí hay una buena introducción sobre Joel On Software", que logra confundir Fortran con Basic, por lo que no confiaría mucho en otros hechos.
quant_dev