Alguma linguagem de programação usa funções recursivas gerais como base?

Esta é uma pergunta ingênua e, portanto, possivelmente malformada, portanto peça desculpas antecipadamente!

Minha opinião é que uma máquina de Turing pode ser vista como a base computacional para linguagens de programação procedurais / imperativas. Da mesma forma, o cálculo lambda é a base para linguagens de programação funcionais.

Aprendi recentemente que a tese de Church-Turing também mostra equivalência mútua com um terceiro modelo de computação: funções recursivas gerais . Existem linguagens de programação que usam isso como modelo de computação? Caso contrário, existe uma razão técnica para isso; ou seja, além de "Ninguém tentou ainda"?

Resposta direta à pergunta: sim, existem PLs esotéricos e altamente impraticáveis ​​baseados em funções recursivas (pense em espaço em branco), mas nenhuma linguagem de programação prática é baseada em funções recursivas μ devido a razões válidas.$\mu$$\mu$

Funções recursivas gerais (ou seja, recursivas) são significativamente menos expressivas que os cálculos lambda. Assim, eles formam uma base ruim para linguagens de programação. Você também não está certo de que a TM seja a base de PLs imperativos: na realidade, boas linguagens de programação imperativas estão muito mais próximas do λ- cálcio do que nas máquinas de Turing.$\mu$$\lambda$

Em termos de computabilidade, as funções recursivas , a máquina de Turing e o λ- cálcio não tipado são todos equivalentes. No entanto, o LC sem tipo tem boas propriedades que nenhum dos outros dois possui. É muito simples (apenas 3 formas sintáticas e 2 regras computacionais), é altamente composicional e pode expressar construções de programação com relativa facilidade. Além disso, equipado com um sistema de tipo simples (por exemplo, Sistema F ω estendido com f i x ), o λ- cálcio pode ser extremamente expressivo, pois pode expressar muitas construções complexas de programação com facilidade, correção e composição. Você também pode estender o $\mu$$\lambda$$F\omega$$\mathsf{fix}$$\lambda$$\lambda$-calculus facilmente para incluir construções que não são lambdas. Nenhum dos outros modelos computacionais mencionados acima fornece essas boas propriedades.

A máquina de Turing não é composicional nem universal (você precisa ter uma TM para cada problema). Não existem conceitos de "funções", "variáveis" ou "composição". Também não é exatamente verdade que as TMs sejam a base dos PLs imperativos - FWIW, os PLs imperativos estão muito, muito mais próximos do cálculo lambda com operadores de controle do que das máquinas de Turing. Veja "Uma correspondência entre o ALGOL 60 e a Notação Lambda da Igreja", de Peter J. Landin, para uma explicação detalhada. Se você programou no Brainf ** k (que realmente implementa uma máquina de Turing bastante simples), você saberá que as máquinas de Turing não são uma boa idéia para programação.

$\mu$As funções recursivas são semelhantes às TMs a esse respeito. Eles são composicionais, mas não tão composicionais quanto o LC. Você também não pode codificar construções de programação úteis em funções recursivas . Além disso, as funções μ- recursivas apenas computam sobre N e para calcular sobre qualquer outra coisa, você precisa codificar seus dados em números naturais usando algum tipo de numeração de Gödel, o que é doloroso.$\mu$$\mu$$\mathbb{N}$

Portanto, não é coincidência que a maioria das linguagens de programação seja de algum modo baseada no -calculus! O $\lambda$$\lambda$ cálcio tem boas propriedades: expressividade, composicionalidade e extensibilidade, que outros sistemas não possuem. No entanto, as máquinas de Turing são boas para estudar a complexidade computacional e as funções recursivas são boas para estudar a noção lógica de computabilidade. Ambos possuem excelentes propriedades que o λ- calculus não possui, mas no campo da programação o λ- calculus vence com clareza.$\mu$$\lambda$$\lambda$

De fato, existem muitos outros sistemas completos de Turing por aí, mas eles não possuem nenhuma propriedade pendente. O Jogo da Vida de Conway, as macros LaTeX e até mesmo o DNA (alguns afirmam) são todos de Turing completos, mas ninguém programa (por exemplo, faz programação séria) com Conway ou estuda a complexidade computacional usando macros LaTeX. Eles simplesmente não têm boas propriedades. Turing completo por si só é quase sem sentido quando se trata de programação.

Além disso, muitos sistemas computacionais completos não-Turing são muito úteis quando se trata de programação. Expressões regulares e yacc não são completas de Turing, mas são extremamente poderosas na solução de uma certa classe de problemas. Coq também não é Turing completo, mas é incrivelmente poderoso (na verdade, é considerado muito mais expressivo do que seu primo completo de Turing, OCaml). Quando se trata de programação, a integridade de Turing não é a chave, pois muitos sistemas (quase) inúteis são desinteressantemente completos. Você não vai afirmar que Brainf ** k ou Whitespace são linguagens de programação mais poderosas que Coq, não é? Uma base expressiva é a chave para linguagens de programação poderosas, e é por isso que as linguagens de programação modernas quase sempre se baseiam no $\lambda$-cálculo.

Digitar µ-recursive function programming languageno Google me levou a este repositório do GitHub , então a resposta para sua pergunta é:

Sim, e se chama miopia

Está escrito em Haskell, a propósito.