Podemos construir um computador funcional?

12

Por mais que a FP tenha feito, no final, todos os nossos programas estão estruturados. Ou seja, não importa o quão puro ou funcional nós os tornemos - eles sempre são traduzidos para montagem, então o que realmente passa por trás dos capuzes são instruções, estados e loops. Estamos meio que emulando FP.

Como noob de hardware, minha pergunta é: por que não estamos usando arquiteturas de computadores que realmente computam as coisas em um estilo funcional? Por exemplo, um computador poderia consistir em "chips funcionais" primitivos, como "concat", "map" e "reduce", e um programa simplesmente informaria ao computador como fluir os dados entre esses chips para calcular o resultado desejado. , como em idiomas concatenativos.

esboço sem sentido

Isso realmente não faz sentido, mas pode ilustrar o que estou pensando.

MaiaVictor
fonte
5
Não tenha o link em mãos, mas foi feito um chip Haskell; os sistemas especialistas também possuíam hardware lisp especializado. Eu acho que você pode estar mais perto do mapa / reduzir o paradigma no hardware do que qualquer outra coisa. O único benefício de desempenho para FP é escalabilidade para paralelismo. De todas as outras formas, o fp tem menos desempenho porque é menos refinado nas instruções, devido a um nível mais alto de abstração. No nível do metal, o desempenho é rei e, além do nível de abstração da matemática, na execução, tudo é imperativo. Calcule 2 * 3 + 5 sem executar duas etapas ordenadas. É tudo imperativo
Jimmy Hoffa
3
@ Link de chip haskell fora de mão de JimmyHoffa : Reduceron .
Dan D.
1
Além disso, você pode estar interessado no Verity, que é um compilador para um cálculo lambda chamado por nome com recursão afim de ordem superior e que também tem efeitos locais imperativos no hardware estático via VHDL.
Dan D.
5
@Dokkat: if we could make a specialized chip for Filter, for example, it would need just a single clock for a Filter operation. Na verdade não, porque o Filter não é "uma operação"; é uma função de ordem superior que aplica uma operação externa arbitrária a uma lista. Você não pode reduzir isso a um único ciclo de relógio.
Mason Wheeler
2
@Dokkat É uma função de ordem superior, pois é usada como entrada para uma função. A especificidade ridícula é o que faz do seu exemplo algo que pode ser feito "em uma única operação". A função de predicado específico é constante e, portanto, não é realmente um filtro verdadeiro. Criar um filtro que utilize uma função predicada arbitrária não pode ser reduzido a um único ciclo de clock porque você não tem controle sobre quantos ciclos de clock a função de entrada leva.
Chewy Gumball

Respostas:

11

Eles fazem computadores assim. É chamado de FPGA . Obviamente, os FPGAs suportam lógica sequencial e combinacional, mas não há nada que o impeça de usar a parte combinatória conforme sugerido.

Na prática, no entanto, a lógica seqüencial (do tipo com estado) é extremamente útil, mesmo no nível do chip. Por um lado, reduz significativamente o número de portas lógicas necessárias para resolver um problema. Por outro lado, resolve muitos problemas de design relacionados a sinais com diferentes atrasos na propagação.

Se você está interessado nesse tipo de coisa, vale a pena conferir os FPGAs. Há uma placa barata, semelhante a um arduino, chamada papilio, que é ótima para iniciantes. As pessoas o usam para tudo, desde controle de robôs até mineração de bitcoin.

Karl Bielefeldt
fonte
Obrigado pela resposta, estou lendo a página da Wikipedia - mas o FPGA não é um hardware programável genérico em vez de um hardware especializado para Programação Funcional, como no meu esboço?
MaiaVictor
1
Google "algoritmo de classificação fpga" se você quiser ver como isso é feito. O que você desenhou é um circuito lógico combinacional programável, que é exatamente o que um FPGA é projetado.
Karl Bielefeldt
Esplêndido, vou fazer minha pesquisa!
MaiaVictor
se você não tem nenhuma sequência, então está realmente olhando para a eletrônica analógica
jk.
2
@jk Isso não é verdade; Tomemos, por exemplo, a unidade aritemático-lógica em uma CPU simples, que é digital e combinatória (pura).
M3th0dman
8

Essencialmente, sim, os computadores analógicos funcionavam dessa maneira: você estava alterando parâmetros e uma corrente elétrica foi modificada de acordo. Foi isso que os tornou "mais rápidos", durante algum tempo, na década de 1950 - você não se importava com a lenta criação e modificação de "estados" separados, como nos antigos gigantes digitais.

E, sem dúvida, os computadores quânticos também podem funcionar dessa maneira: se o estado de alguns fenômenos quânticos depende do estado de outros, a alteração de um estado "inicial" alterará os seguintes estados simultaneamente - nenhum "estado" entre eles.

Enéias
fonte
3
1 para mencionar os computadores quânticos, acho que a capacidade de fazer coisas como o OP está sugerindo vão ser o principal benefício para estes quando eles realmente se materializar
Jimmy Hoffa