Матрица соответствия Хаскелла "расходится" и ⊥
Я пытаюсь понять раздел 3.17.2 отчета Haskell 2010 "Неформальная семантика сопоставления с образцом". Большинство из них, относящихся к успешному или неудачному сопоставлению с образцом, кажутся простыми, однако у меня возникают трудности с пониманием случая, который описывается как "расхождение" при сопоставлении с образцом.
Я полуубежден, это означает, что алгоритм соответствия не "сходится" к ответу (следовательно, функция соответствия никогда не возвращается). Но если не возвращается, то как он может вернуть значение, как указано в круглых скобках "т.е. вернуть ⊥ "? А что значит" вернуть ⊥ "В любом случае? Как справиться с этим результатом?
Пункт 5 имеет особенно запутанный (для меня) пункт "Если значение ⊥, матч расходится ". Это просто говорит о том, что значение ⊥ производит результат совпадения ⊥? (За исключением того, что я не знаю, что означает этот результат!)
Любое освещение, возможно, с примером, будет оценено!
Приложение после пары длинных ответов: Спасибо Тихону и всем за ваши усилия.
Кажется, моя путаница возникает из-за того, что существуют две разные области объяснения: сфера особенностей и поведения Хаскеля и сфера математики / семантики, и в литературе Хаскелла эти две вещи смешаны в попытке объяснить первое с точки зрения последнего без достаточных указателей (для меня), какие элементы принадлежат к какому.
Видимо "низ" ⊥ находится в домене семантики и не существует как значение в Haskell (то есть: вы не можете ввести его, вы никогда не получите результат, который выводится как " ⊥ ").
Итак, где объяснение говорит, что функция "возвращает ⊥ ", это относится к функции, которая выполняет любую из множества неудобных вещей, например, не завершает работу, генерирует исключение или возвращает" неопределенное ". Это правильно?
Далее те, кто прокомментировал это ⊥ на самом деле это значение, которое можно передать, действительно думают о привязках к обычным функциям, которые на самом деле еще не были призваны оценить (так сказать, "неразорвавшиеся бомбы") и, возможно, никогда, из-за лени, не так ли?
2 ответа
Значение ⊥, обычно произносится как "низ". Это значение в семантическом смысле - это не нормальное значение Хаскеля как таковое. Он представляет вычисления, которые не производят нормальное значение Haskell: исключения и бесконечные циклы, например.
Семантика - это определение "смысла" программы. В Haskell мы обычно говорим о денотационной семантике, где значение является математическим объектом некоторого вида. Самый тривиальный пример: выражение 10 (но также выражение 9 + 1) имеют обозначения числа 10 (а не значение Haskell 10). Мы обычно пишем, что ⟦9 + 1⟧ = 10 Это означает, что обозначение выражения Haskell 9 + 1 это число 10.
Однако, что мы делаем с таким выражением, как let x = x in x? Для этого выражения нет значения Haskell. Если бы вы попытались оценить это, оно бы никогда не закончилось. Более того, не ясно, какому математическому объекту это соответствует. Однако, чтобы рассуждать о программах, нам нужно дать некоторое обозначение для этого. Итак, по сути, мы просто составляем значение для всех этих вычислений и называем значение ⊥ (внизу).
Таким образом, just - это просто способ определить, что вычисление, которое не возвращает, "означает".
Мы также определяем другие вычисления, такие как undefined а также error "some message" как ⊥ потому что они также не имеют очевидных нормальных значений. Таким образом, исключение соответствует ⊥, Это именно то, что происходит при неудачном сопоставлении с образцом.
Обычный способ думать об этом состоит в том, что каждый тип Haskell "поднят"- он содержит ⊥, То есть, Bool соответствует {⊥, True, False} а не просто {True, False}, Это говорит о том, что программы на Haskell не гарантированно завершаются и могут иметь исключения. Это также верно, когда вы определяете свой собственный тип - тип содержит каждое значение, определенное для него, а также ⊥,
Интересно, что, поскольку Хаскелл не является строгим, ⊥ может существовать в обычном коде. Таким образом, вы могли бы иметь значение как Just ⊥и если вы никогда не оцените это, все будет работать нормально. Хороший пример этого const: const 1 ⊥ оценивает 1, Это работает и для неудачных сопоставлений с шаблоном:
const 1 (let Just x = Nothing in x) -- 1
Вы должны прочитать раздел о денотационной семантике в Haskell WikiBook. Это очень доступное введение в предмет, которое я лично нахожу очень увлекательным.
Денотационная семантика
Итак, кратко денотационная семантика, где ⊥ жизни, это отображение значений из Haskell в другое пространство значений. Вы делаете это, чтобы придать смысл программам более формальным образом, чем просто говорить о том, что программы должны делать - вы говорите, что они должны уважать свою денотационную семантику.
Поэтому для Хаскелла вы часто думаете о том, как выражения Хаскелла обозначают математические значения. Вы часто видите стрейчи скобки ⟦·⟧ обозначить "семантическое отображение" от Хаскеля до математики. Наконец, мы хотим, чтобы наши семантические скобки были совместимы с семантическими операциями. Например
⟦x + y⟧ = ⟦x⟧ + ⟦y⟧
где на левой стороне + это функция Haskell (+) :: Num a => a -> a -> a и на правой стороне это бинарная операция в коммутативной группе. Хотя это круто, потому что тогда мы знаем, что мы можем использовать свойства семантической карты, чтобы знать, как должны работать наши функции на Haskell. Для этого давайте напишем коммутативное свойство "в математике"
⟦x⟧ + ⟦y⟧ == ⟦y⟧ + ⟦x⟧
= ⟦x + y⟧ == ⟦y + x⟧
= ⟦x + y == y + x⟧
где третий шаг также указывает на то, что Haskell (==) :: Eq a => a -> a -> a должен иметь свойства отношения математической эквивалентности.
Ну, кроме...
В любом случае, это все хорошо, пока мы не вспомним, что компьютеры - это конечные вещи, и математика не особо заботится об этом (если вы не используете интуитивистскую логику, а затем получаете Coq). Итак, мы должны обратить внимание на места, где наша семантика не совсем соответствует математике. Вот три примера
⟦undefined⟧ = ??
⟦error "undefined"⟧ = ??
⟦let x = x in x⟧ = ??
Это где ⊥ вступает в игру. Мы просто утверждаем, что с точки зрения денотационной семантики Haskell каждый из этих примеров также может означать (недавно введенная математическая / семантическая концепция) ⊥, Каковы математические свойства ⊥? Ну, вот тут мы и начинаем действительно углубляться в семантическую область и начинаем говорить о монотонности функций, СРО и тому подобного. По сути, хотя, ⊥ является математическим объектом, который играет примерно в ту же игру, что и игра без прерывания. С точки зрения семантической модели, ⊥ токсичен и заражает выражения своим токсическим недетерминизмом.
Но это не концепция языка Хаскелла, а просто концепция языка семантики в области языка Хаскелла. В Хаскеле мы имеем undefined, error и бесконечный цикл. Это важно.
Внесемантическое поведение (примечание)
Так что семантика ⟦undefined⟧ = ⟦error "undefined"⟧ = ⟦let x = x in x⟧ = ⊥ ясно, когда мы понимаем математическое значение ⊥, но также ясно, что каждый из них имеет разные эффекты "в реальности". Это что-то вроде "неопределенного поведения" C… это поведение, которое не определено в том, что касается семантической области. Вы могли бы назвать это семантически ненаблюдаемым.
Так как же возвращается сопоставление с образцом ⊥?
Так что же значит "семантически" возвращать ⊥? Что ж, ⊥ является вполне допустимым семантическим значением, обладающим свойством заражения, которое моделирует недетерминизм (или асинхронное генерирование ошибок). С семантической точки зрения это вполне допустимое значение, которое может быть возвращено как есть.
С точки зрения реализации у вас есть несколько вариантов, каждый из которых соответствует одному и тому же семантическому значению. undefined не совсем правильно и не входит в бесконечный цикл, поэтому, если вы собираетесь выбрать семантически неопределенное поведение, вы можете также выбрать тот, который полезен, и выдать ошибку
*** Exception: <interactive>:2:5-14: Non-exhaustive patterns in function cheers