Função ML do tipo 'a ->' b

19

Nosso professor nos pediu para pensar em uma função no OCaml que tem o tipo

'a -> 'b

isto é, uma função de um argumento que pode ser qualquer coisa e que pode retornar algo diferente.

Pensei em usar raiseuma função que ignora seu argumento:

let f x = raise Exit

Mas o professor disse que havia uma solução que não requer nenhuma função na biblioteca padrão. Estou confuso: como você pode fazer um 'bse não possui um em primeiro lugar?

Estou perguntando aqui, e não no Stack Overflow, porque quero entender o que está acontecendo, não quero apenas ver um programa sem explicação.

Gilles 'SO- parar de ser mau'
fonte
2
Alveje a programação de aprendizado do aluno CS101 em sua resposta, não o teórico do tipo que sua resposta possa inspirá-lo a se tornar mais tarde.
Gilles 'SO- stop be evil'
Ajudaria se você explicasse como descobriu que raisefuncionaria, portanto sabemos como explicar melhor por que a solução que seu professor está procurando (que funcionará pelos mesmos motivos que raisefunciona) funciona.
sepp2k
@ sepp2k raise : exn -> 'apara que eu possa obter o valor de retorno, eu simplesmente ignoro o argumento.
Gilles 'SO- stop be evil'
1
Pergunta de acompanhamento: Funções de ML de listas polimórficas para listas polimórficas
Gilles 'SO- deixa de ser mau'
2
Veja também Por que o algoritmo Hindley-Milner nunca produzirá um tipo como t1 -> t2? discutindo um cenário mais teórico.
Gilles 'SO- stop be evil' em

Respostas:

18

O esqueleto é let f x = BODY. Em BODY, você deve usar x somente de maneiras genéricas (por exemplo, não o envie para uma função que espera números inteiros) e você deve retornar um valor de qualquer outro tipo. Mas como a última parte pode ser verdadeira? A única maneira de satisfazer a instrução "para todos os tipos 'b, o valor retornado é um valor do tipo 'b" é garantir que a função não retorne. Existem exatamente duas possibilidades: Falhas no CORPO ou não terminam. A função raisefalha, o seguinte não termina:

let rec f x = f x
rgrig
fonte
19

Primeiro, algumas observações. Não é possível obter apenas o cálculo lambda do tipo tipado, 'a -> 'bporque o sistema de digitação está em correspondência (via isomorfismo de Curry Howard ) com lógicas intuicionistas, e a fórmula correspondente A → Bnão é uma tautologia.

Outras extensões, como tuplas e correspondências / condicionais, ainda preservam alguma consistência lógica, adicionando tipos de produtos *que correspondem ao conectivo lógico e , e tipos de soma |que correspondem ao ou . Novamente, não espere que eles produzam esse 'a -> 'btipo, pois isso permitiria provar uma fórmula que não é uma tautologia.

Portanto, suas únicas chances são usar outras construções que escapam da lógica, como raise(mas você não tem permissão para fazê-lo) ... ou let rec! A recursão permite criar programas que nunca terminam e seus resultados podem receber um tipo de retorno arbitrário, pois nunca serão produzidos. Agora, se você pensar na função mais trivial e sem terminação (aquela que se chama diretamente para retornar um resultado):

let rec f x = f x

Você notará que seu tipo é exatamente 'a -> 'b: qualquer que seja o argumento fornecido, o resultado (que nunca será computado) pode ser assumido como tendo qualquer tipo.

Claro que essa fnão é uma função interessante, mas esse é o ponto. No OCaml, qualquer função cujo tipo não se parece com uma fórmula válida é uma função suspeita.

Stéphane Gimenez
fonte
O autor da pergunta não entendeu uma palavra dos seus dois primeiros parágrafos, mas eu gosto da sua frase "os resultados podem receber um tipo de retorno arbitrário, pois nunca serão produzidos".
Gilles 'SO- stop be evil'
1

Usando uma primitiva do compilador, você pode escrever isto:

external magic: 'a -> 'b = "%identity"

(e, de fato, a distribuição do compilador fornece isso, embora não faça parte do idioma). Este é um elenco de identidade inseguro.

Seu professor quase certamente não quer isso. No entanto, essa também é a única função útil com o tipo 'a -> 'bque eu conheço e, de fato, é usada na própria distribuição OCaml.

Demi
fonte