Функция ML типа 'a ->' b

19

Наш профессор попросил нас подумать о функции в OCaml, которая имеет тип

'a -> 'b

т.е. функция одного аргумента, которая может быть чем угодно, и которая может возвращать что угодно другое.

Я думал об использовании raiseв функции, которая игнорирует ее аргумент:

let f x = raise Exit

Но профессор сказал, что есть решение, которое не требует каких-либо функций в стандартной библиотеке. Я в замешательстве: как вы можете сделать это, 'bесли у вас его нет вообще?

Я спрашиваю здесь, а не о переполнении стека, потому что я хочу понять, что происходит, я не хочу просто видеть программу без объяснения причин.

Жиль "ТАК - перестань быть злым"
источник
2
В своем ответе, пожалуйста, нацелитесь на обучение студентов программированию CS101, а не на теоретика типов, которым ваш ответ мог бы вдохновить его в дальнейшем.
Жиль "ТАК - перестань быть злым"
Было бы полезно, если бы вы объяснили, как вы выяснили, как это raiseбудет работать, поэтому мы знаем, как лучше всего объяснить, почему работает решение, которое ищет ваш профессор (которое будет работать по тем же причинам, что и raiseработает).
sepp2k
@ sepp2k, raise : exn -> 'aчтобы я мог получить возвращаемое значение, я просто игнорирую аргумент.
Жиль "ТАК - перестань быть злым"
1
Дополнительный вопрос: ML функционирует от полиморфных списков до полиморфных списков
Жиль "ТАК - перестань быть злым"
2
См. Также Почему алгоритм Хиндли-Милнера никогда не даст такой тип, как t1 -> t2? обсуждая более теоретический сеттинг.
Жиль "ТАК - перестань быть злым"

Ответы:

18

Скелет есть let f x = BODY. В BODY вы должны использовать x только общими способами (например, не отправлять его функции, ожидающей целые числа), и вы должны возвращать значение любого другого типа. Но как последняя часть может быть правдой? Единственный способ удовлетворить утверждение «для всех типов 'b, возвращаемое значение - это значение типа 'b» - это убедиться, что функция не возвращает. Существует ровно две возможности: либо неисправность ТЕЛА, либо она не прекращается. Функция не работает raise, следующее не завершается:

let rec f x = f x
rgrig
источник
19

Сначала несколько замечаний. Использование только лямбда-исчисления с типизированным ядром невозможно получить, 'a -> 'bпотому что система типизации соответствует (через изоморфизм Карри Ховарда ) интуиционистской логике, и соответствующая формула A → Bне является тавтологией.

Другие расширения, такие как кортежи и сопоставления / условия, все еще сохраняют некоторую логическую согласованность, добавляя типы продуктов, *которые соответствуют логическим связям, и , и типы сумм, |которые соответствуют или . Опять же, не ожидайте, что они произведут этот 'a -> 'bтип, поскольку это позволит доказать некоторую формулу, которая не является тавтологией.

Таким образом, ваши единственные возможности - использовать другие конструкции, которые выходят из логики, например raise(но в этом случае вы не можете)… или let rec! Рекурсия позволяет создавать программы, которые никогда не завершаются, и их результатам может быть присвоен произвольный тип возврата, поскольку они никогда не будут созданы. Теперь, если вы думаете о самой тривиальной не завершающей функции (той, которая непосредственно вызывает себя, чтобы вернуть результат):

let rec f x = f x

Вы заметите, что его тип точно 'a -> 'b : какой бы ни был предоставленный аргумент, можно предположить, что результат (который никогда не будет вычислен) имеет любой тип.

Конечно, это fне интересная функция, но в этом суть. В OCaml любая функция, тип которой не похож на правильную формулу, является подозрительной функцией.

Стефан Хименес
источник
Запрашивающий не понял ни слова из ваших первых двух абзацев, но мне нравится ваше предложение «их результатам может быть присвоен произвольный тип возврата, поскольку они никогда не будут получены».
Жиль "ТАК - перестань быть злым"
1

Используя примитив компилятора, вы можете написать это:

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

(и действительно, дистрибутив компилятора обеспечивает это, хотя и не является частью языка). Это небезопасный актерский состав.

Ваш профессор почти наверняка не хочет этого. Однако это также единственная полезная функция с типом, 'a -> 'bо которой я знаю, и она действительно используется в самом дистрибутиве OCaml.

Деми
источник