Как вывести принуждения? - PullRequest
4 голосов
/ 16 сентября 2008

Я хотел бы знать, как вывести принуждения (например, неявные преобразования) во время вывода типа. Я использую схему вывода типа, описанную в Сообщения об ошибках высшего качества Бастиана Херена, но я предполагаю, что общая идея, вероятно, одинакова во всех подходах Хиндли-Милнера.

Кажется, что принуждение можно рассматривать как форму перегрузки, но подход к перегрузке, описанный в этой статье, не учитывает (по крайней мере, так, как я мог бы следовать) перегрузку, основанную на требованиях, которые контекст помещает в возвращаемый тип , что является обязательным условием для принуждения. Я также обеспокоен тем, что такой подход может затруднить уделение первоочередного внимания принуждению личности, а также уважать переходное закрытие принуждения. Я вижу, как подслащивать каждое принудительное выражение, скажем e , принудительно ( e ), но подслащивать его принудительно (coerce (coerce (... coerce ( e * 1010) *) ...))) для некоторой глубины, равной максимальной вложенности принуждений, кажется глупым, и также ограничивает отношение принужденности чем-то с конечным транзитивным замыканием, глубина которого не зависит от контекста, который кажется (без необходимости?) ограничительным.

Ответы [ 3 ]

3 голосов
/ 16 сентября 2008

Надеюсь, вы получите хорошие ответы на этот вопрос.

Я еще не читал статью, на которую вы ссылаетесь, но звучит интересно. Вы смотрели на все, как специальный полиморфизм (в основном перегрузка) работает в Haskell? Система типов Хаскелла - H-M плюс некоторые другие вкусности. Одним из таких лакомств являются классы типов. Классы типов обеспечивают перегрузку, или, как ее называет Хаскеллер, специальный полиморфизм.

В GHC, наиболее широко используемом компиляторе Haskell, классы типов реализуются путем передачи словарей во время выполнения. Словарь позволяет системе времени выполнения выполнять поиск от типа к реализации. Предположительно, jhc может использовать супероптимизацию для выбора правильной реализации во время компиляции, но я скептически отношусь к тому, что она обрабатывает полностью полиморфные случаи, которые может допустить Haskell, и я не знаю никаких формальных доказательств или документов, подтверждающих правильность.

Похоже, что ваш вывод типа столкнется с теми же проблемами, что и другие полиморфные подходы ранга n. Возможно, вы захотите прочитать некоторые статьи здесь, чтобы получить дополнительную информацию: Прокрутите вниз до "Статьи о типах" Его статьи относятся к конкретному языку, но теоретические материалы должны быть значимыми и полезными для вас.

Я думаю, что эта статья о полиморфизме ранга n и вопросах проверки типов должна вызвать у вас некоторые интересные мысли: http://research.microsoft.com/~simonpj/papers/higher-rank/

Хотел бы я дать лучший ответ! Удачи.

1 голос
/ 12 января 2010

Мой опыт показывает, что подслащивание каждого термина интуитивно кажется непривлекательным, но его стоит продолжить.

Интерес к постоянному хранению побудил меня обходным путем рассмотреть проблемы смешивания выражения и атомарных значений. Чтобы поддержать это, я решил разделить их полностью в системе типов; таким образом, Int, Char и т. д. являются конструкторами типов только для целочисленных и символьных значений. Типы выражений формируются с помощью конструктора полиморфных типов Exp; например Exp Int относится к значению, которое уменьшается за один шаг до Int.

Соответствие этого вашему вопросу возникает, когда мы рассматриваем оценку. На нижележащем уровне существуют примитивы, которые требуют атомарных значений: COND, addInt и т. Д. Некоторые люди называют это принудительным выражением, я предпочитаю видеть его просто как приведение между значениями различных типов.

Задача состоит в том, чтобы посмотреть, можно ли это сделать, не требуя явных директив сокращения. Одно из решений точно такое, как вы предлагаете: то есть рассматривать принуждение как форму перегрузки.

Скажем, у нас есть входной скрипт: foo x

Затем, после подслащивания, это становится: (coerce foo) (coerce x)

Где неофициально:

coerce :: a -> b
coerce x = REDUCE (cast x) if a and b are incompatible
x                          otherwise

Таким образом coerce является либо идентификатором, либо приложением cast , где b является типом возврата для данного контекста.

cast теперь можно рассматривать как метод класса типов, например

class Cast a, b where {cast :: a -> b };
-- ¬:: is an operator, literally meaning: don’t cast
--(!) is the reduction operator. Perform one stage of reduction.

-- Reduce on demand
instance Cast Exp c, c where { inline cast = ¬::(!)(\x::(Exp c) -> ¬::(!)x) };

Аннотации ¬:: используются для подавления принудительного синтаксического подсахаривания.

Предполагается, что другие экземпляры Cast могут быть введены для расширения диапазона конверсий, хотя я не исследовал это. Как вы говорите, перекрывающиеся экземпляры кажутся необходимыми.

0 голосов
/ 16 сентября 2008

Не могли бы вы дать немного больше разъяснений относительно того, что именно вы спрашиваете?

У меня есть небольшая идея, и если моя идея верна, то этого ответа должно быть достаточно в качестве моего ответа. Я полагаю, что вы говорите об этом с точки зрения того, кто создает язык, и в этом случае вы можете взглянуть на такой язык, как ActionScript 3 в качестве примера. В AS3 вы можете типизировать два разных способа: 1) NewType (объект) или 2) объект как NewType .

С точки зрения реализации, я представляю, что каждый класс должен определить свои собственные способы преобразования в любой тип, который он может преобразовать в (Массив не может действительно преобразовать в целое число ... или может?) , Например, если вы попробуете Integer (myArrayObject) , а myArrayObject не определит способ конвертации в и Integer, вы можете либо сгенерировать исключение, либо разрешить его, и просто передать исходный объект без обработки.

Хотя весь мой ответ может быть совершенно неверным :-D Дайте мне знать, если это не то, что вы ищете

...