Alguém pode me apontar a referência para a não definibilidade do módulo de continuidade funcional no PCF? \ newcommand {\ bool} {\ mathsf {bool}}
Andrej Bauer escreveu um post muito bom no blog explorando alguns dos problemas com mais detalhes, mas vou resumir apenas um pouco do seu post para dar algum contexto a essa pergunta. O espaço de Baire é o conjunto de sequências de números naturais, ou equivalentemente o conjunto de funções do naturais para naturais . Para esta questão, restringiremos nossa atenção apenas aos fluxos que são computáveis.
Agora, uma função é contínua se, para cada , o valor de depende apenas de um número finito dos elementos de , e é computacionalmente contínua se, na verdade, pudermos calcular um valor superior limitado a quantos elementos de são necessários. Em alguns modelos de computação, é realmente possível escrever um programa que assume uma função computável no espaço Baire e um elemento do espaço Baire, e devolve o limite superior do número de elementos do fluxo.
Um truque para implementar isso é usar o armazenamento local para registrar o índice máximo no fluxo visto:
let modulus f xs =
let r = ref 0 in
let ys = fun i -> (r := max i !r; xs i) in
f ys;
!r
Obviamente, o ys
argumento não é mais um programa puramente funcional. Meu interesse neste programa vem do fato de que ele apenas utiliza lojas locais e, portanto, é extensionalmente puro. Trabalho (entre outras coisas) em programação imperativa de ordem superior e estou projetando teorias de tipos que poderiam classificá-la como uma função pura.
Também existem exemplos mais práticos, envolvendo coisas como memorização e pool de conexões, mas acho esse um exemplo particularmente bonito.
fonte