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

23

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"?

Xophmeister
fonte
1
Eu diria que as máquinas de Turing ou as máquinas de registro universal são a base dos PLs de processadores (Assembly PLs). Eles não têm funções. As funções recursivas são uma base de PLs imperativos. Eles não têm funções de ordem superior. μ
beroal 30/07/19
1
Eu também recomendaria investigar a lógica de primeira ordem e o Prolog.
beroal 30/07
1
Antes dos C ++ 11, constexprvocê podia (/ tinha que) usar 'modelos' para realizar cálculos em tempo de compilação pelo compilador. As restrições nos modelos não permitem loops, mas você pode usar a recursão para emular qualquer loop, para que você termine com um recurso de Turing-complete (metaprogramação) como parte do padrão da linguagem C ++, consulte, por exemplo, stackoverflow.com/questions / 189172 / c-templates-turing-complete
JimmyB

Respostas:

45

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.μμ

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.μλ

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 λμλFωfEuxλλ-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.

μ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.μμN

Portanto, não é coincidência que a maioria das linguagens de programação seja de algum modo baseada no -calculus! O λλλ 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.μλλ

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 λ-cálculo.

xuq01
fonte
7
"Ninguém programas com Conway" ... alguns fazem construir um jogo de trabalho do Tetris no Jogo da Vida de Conway ... também na verdade, é tão prático como espaços em branco :)
Alexei Levenkov
λλ
@AlexeiLevenkov Isso é totalmente falso. O espaço em branco é essencialmente uma linguagem imperativa (simples), embora com uma sintaxe estranha. Ele tem facilidades para , o fluxo de controlo aritmética básica, pilha e manipulação pilha, e I / O . O projeto QFT, por outro lado, exigia a criação de um compilador de uma linguagem muito simples até um assembly RISC criado para uma CPU criada dentro de um autômato celular do tipo Wireworld emulado usando OTCA Metapixels .
Ortografia não-contextual
@AlexeiLevenkov O último compilador Cogol → CGoL exigiu o trabalho de muitas pessoas ao longo de quatro anos, enquanto existe um projeto chamado HaPyLi , que compila uma linguagem muito mais complexa para o Whitespace, que foi escrita por uma pessoa em seu tempo livre.
Ortografia não-contextual
4

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.

Kapol
fonte
μ
2
Claro. Eu presumi que OP quer encontrar uma tal linguagem para estudar a teoria ou algo assim, não para realmente conquistar o mundo com ele ;-)
Kapol