Linguagem de programação funcional total sem um verificador de tipo estático

7

Todos os trabalhos com o assunto de programação funcional total utilizam algum tipo de verificação estática de tipo para garantir a totalidade. Isso faz sentido, considerando que facilmente é tornar uma linguagem completa de Turing. A pergunta é: existe algum formalismo não tipado / tipado dinamicamente que garante o total de funções?

Editar

Em outras palavras, existe algum formalismo que apenas permite construir funções totais, com a impossibilidade de construção de funções parciais, de modo que não há necessidade de um estágio de filtragem como um verificador de tipos ou uma análise de terminação?

functional-programming user3368561
fonte
3
Não há necessidade de manter o marcador "Editar" no histórico pós-revisões, portanto a edição deve ser contínua e, esperamos, não invalidar as respostas existentes.
Mal
2
Praticamente todas as linguagens são definidas como uma sintaxe nas strings, e esse já é um estágio de filtragem.
Gilles 'SO- stop be evil'

Respostas:

9

A questão é: como você elimina termos que são executados para sempre:

Em particular, coisas como e o combinador Y NÃO devem estar no seu idioma, pois podem ser usadas para construir cálculos que não param.(λx.x x)(λx.x x)

A digitação estática em coisas como o Sistema F elimina estas: elas começam com um cálculo lambda completo e depois filtram termos incorretos.

Mas, faça isso em uma configuração não digitada, você precisará eliminar esses termos por construção . Eles não podem ser expressáveis ​​no seu idioma.

Eu posso pensar em algumas maneiras tolas de fazer isso, como a linguagem de programas imperativos sem funções ou e apenas repetindo as listas. Mas, em geral, assim que você tem funções de ordem superior, essas construções problemáticas são construtíveis. Portanto, embora não diga que é impossível, provavelmente é muito difícil de fazer de uma maneira que faça muito sentido.

É possível filtrar estaticamente essas coisas com algo que não é um sistema de tipos, com verificadores de terminação, mas sempre geram falsos positivos e, embora não sejam de digitação estática, ainda são muito um filtro estático. seus programas.

Observe que, dependendo do que você considera "digitado dinamicamente", você pode eliminar programas como esse acompanhando os tipos usando inferência, mas apenas lançando erros em tempo de execução. Assim, algo como o combinador Y ainda é rejeitado, apenas mais tarde. Isso é digitado dinamicamente, mas provavelmente não é o que você está procurando.

jmite
fonte
Foi por isso que eu disse: "considerar hoy facilmente é tornar uma linguagem completa em Turing" ... Embora negativa, essa é uma resposta muito útil. Especialmente a terminologia de filtro / construção . É exatamente por isso que estou procurando, um formalismo que só permite criar funções totais sem a necessidade de um estágio de filtro.
precisa saber é o seguinte
11
@ user3368561 Existem também algumas maneiras de aplicar isso pela semântica, por exemplo, corrigir um número inteiro ke nunca execute mais do que etapas de redução. Mas a rescisão é realmente apenas porque você alterou a semântica, não que a tenha impedido no idioma. k
jmite
5

Absolutamente! Existe até uma implementação existente! Eu escrevi este loop.pyprograma em python:

while True:
    print "Hello world!"
    print "20 GOTO 10"

E ele correu como este: timeout 10 python loop.py. Tadaa!

Mais precisamente, o que você considera ser "análise estática"? Uma linguagem de programação que contém apenas loops for sempre terminará. A análise é "análise estática"? Que tal um compilador que compila um programa C e o executa por 10 segundos e retorna o código compilado apenas se o programa terminar?

No CS teórico, sempre temos a opção de executar um programa algumas etapas no "tempo de compilação" para ver o que acontece. No tempo de execução, você sempre tem a opção de sair antecipadamente de um programa, se estiver demorando muito. De fato, é isso que a grande maioria dos programas faz, em vez de "verificação de encerramento". Existe até esse recurso para scripts javascript no navegador (ou as infames mensagens "programa não está respondendo").

cody
fonte