¿Podríamos construir una computadora funcional?

12

Tan rápido como lo ha hecho FP, al final, todos nuestros programas están estructurados. Es decir, no importa cuán puro o funcional los hagamos, siempre se traducen al ensamblaje, por lo que lo que realmente funciona detrás de las campanas son instrucciones, estados y bucles. Somos una especie de emulación de FP.

Como novato en hardware, mi pregunta es: ¿por qué no estamos usando arquitecturas informáticas que realmente computan las cosas en un estilo funcional? Por ejemplo, una computadora podría consistir en "chips funcionales" primitivos como "concat", "map" y "reduce", y un programa simplemente le diría a la computadora cómo hacer fluir los datos entre esos chips para calcular el resultado deseado , como en lenguajes concatenativos.

boceto sin sentido

Esto realmente no tiene sentido, pero podría ilustrar lo que estoy pensando.

MaiaVictor
fuente
55
No tengo el enlace a mano, pero se hizo un chip Haskell, los sistemas expertos también tenían hardware especializado en lisp. Sin embargo, creo que podría estar más cerca del mapa / reducir el paradigma en hardware que cualquier otra cosa. El único beneficio de rendimiento para FP es la escalabilidad al paralelismo. En todas las demás formas, fp es menos eficiente porque tiene menos grano en sus instrucciones debido a que tiene un mayor nivel de abstracción. En el nivel de metal, el rendimiento es el rey, y además, incluso en el nivel de abstracción de las matemáticas, en la ejecución todo es imprescindible. Calcule 2 * 3 + 5 sin tomar dos pasos ordenados. Todo es imprescindible
Jimmy Hoffa
3
Enlace de chip de haskell de mano de JimmyHoffa : Reduceron .
Dan D.
1
También es posible que le interese Verity, que es un compilador para un cálculo Lambda llamado por nombre con una recursión afín y de orden superior que también tiene efectos locales imprescindibles para el hardware estático a través de VHDL.
Dan D.
55
@Dokkat: if we could make a specialized chip for Filter, for example, it would need just a single clock for a Filter operation. En realidad no, porque Filter no es "una operación"; Es una función de orden superior que aplica una operación externa arbitraria a una lista. No puede reducir eso a un solo ciclo de reloj.
Mason Wheeler
2
@Dokkat Es una función de orden superior, ya que toma como entrada una función. La especificidad ridícula es lo que hace que su ejemplo sea algo que se puede hacer "en una sola operación". La función de predicado específico es constante y, por lo tanto, no es realmente un filtro verdadero. Hacer un filtro que tome una función de predicado arbitrario no puede reducirse a un solo ciclo de reloj porque no tiene control sobre cuántos ciclos de reloj toma la función de entrada.
Chewy Gumball

Respuestas:

11

Hacen computadoras así. Se llama FPGA . Por supuesto, los FPGA son compatibles con la lógica secuencial y combinatoria, pero no hay nada que le impida simplemente usar la parte combinacional como sugiere.

En la práctica, sin embargo, la lógica secuencial (del tipo con estado) es extremadamente útil incluso a nivel de chip. Por un lado, reduce significativamente el número de puertas lógicas necesarias para resolver un problema. Por otro lado, resuelve muchos problemas de diseño relacionados con señales que tienen diferentes retrasos de propagación.

Si está interesado en ese tipo de cosas, vale la pena echarle un vistazo a los FPGA. Hay una tabla barata tipo arduino llamada papilio que es ideal para principiantes. La gente lo usa para todo, desde control de robots hasta minería de bitcoins.

Karl Bielefeldt
fuente
Gracias por la respuesta, estoy leyendo la página de Wikipedia, pero ¿no es FPGA un hardware programable genérico en lugar de un hardware especializado para la programación funcional, como en mi boceto?
MaiaVictor
1
Google "algoritmo de ordenación fpga" si desea ver cómo se hace. Lo que dibujó es un circuito lógico combinacional programable, que es precisamente para lo que está diseñado un FPGA.
Karl Bielefeldt
¡Espléndido, haré mi investigación!
MaiaVictor
si no tiene secuencia en absoluto, entonces realmente está buscando electrónica analógica
jk.
2
@jk Eso no es realmente cierto; Tomemos, por ejemplo, la unidad arithemética-lógica en una CPU simple que es digital y (pura) combinacional.
m3th0dman
8

Essentiall, sí, las computadoras analógicas funcionaban de esa manera: estabas cambiando los parámetros y una corriente eléctrica se modificó en consecuencia. Eso es lo que los hizo "más rápidos", durante un tiempo, en la década de 1950: no le importaba la lenta creación y modificación de "estados" separados como en los antiguos gigantes digitales.

Y podría decirse que las computadoras cuánticas también podrían funcionar de esa manera: si el estado de algunos fenómenos cuánticos depende del estado de otros, entonces cambiar algún estado "inicial" cambiará los siguientes estados simultáneamente, sin "estados" intermedios.

Eneas
fuente
3
+1 por mencionar las computadoras cuánticas, creo que la capacidad de hacer cosas como lo que sugiere el OP será el principal beneficio para ellos cuando realmente se materialicen
Jimmy Hoffa