Полиморфизм высших порядков + типы значений - PullRequest
6 голосов
/ 05 апреля 2011

Я где-то читал, что полиморфизм высшего порядка не может быть использован / реализован в системах типов с типами значений (например, .NET).Это правильно и почему?

Ответы [ 2 ]

7 голосов
/ 06 апреля 2011

Проблема заключается в представлении значений.

Традиционные языки полиморфизма высшего порядка сделали упрощенный выбор, что все значения представлены единообразным способом, обычно одним словом, с некоторыми умными тегами, чтобы указать,это непосредственное целое число или указатель на структуру с общим представлением (некоторый тег и т. д.) для всех других значений, таких как структуры данных или функции.

Если у вас есть это предположение, вы можете скомпилировать каждую полиморфную функциюодин раз, и используйте его для всех аргументов всех типов: они имеют представление, принятое скомпилированной функцией.

Теперь допустим, что вы бросаете типы с другими представлениями, например.несколько непрерывных слов в стеке.Вы больше не можете использовать свою единственную скомпилированную функцию, потому что она ожидает одно слово, поэтому соглашение о вызовах неверно.Что-то сломано.

Это можно исправить различными способами, например:

  • передать значениям некоторую информацию об их представлении (вы можете рассмотреть эту информацию длябыть своего рода «типовой» информацией времени выполнения, но на самом деле вам не нужна полная информация о типе, только некоторая информация о представлении);это то, что исследовал компилятор TILT , например:

  • попытаться скомпилировать несколько специализированных версий вашей полиморфной функции для каждого возможного представления, а затем принять решение (также на основесвоего рода тег или некоторая статически доступная информация) какую версию вызывать.Это может быть разумно при использовании схемы оптимизации всей программы, такой как MLton.Это более или менее вариант первой идеи, основанный на выборе вызывающего абонента (а не на выбор вызываемого абонента).

  • ограничивает полиморфизмы, используя систему типов для различения «типов из одного слова», «типы кортежей ".Вместо обычного полиморфизма «для all type» у вас будет релятивизированная версия «для всех типов такого типа ...».Это позволяет программисту статически рассуждать о том, какая функция может принимать аргументы какого типа («ау, эта функция полиморфна, поэтому я должен указать свой тип значения здесь») вместо того, чтобы надеяться, что компилятор получит правильные приведения, но это такжеделает систему типов более тяжелой: вы не сохраняете иллюзию единообразия.

Короче говоря, комбинированный (некоторая форма) полиморфизм с богатым выбором представления данных возможен, но гораздо сложнее, чемв случае единообразного представления.

0 голосов
/ 05 апреля 2011

Нет, это неправильно. Вы можете достичь «полиморфизма более высокого порядка» (функции, которые ведут себя равномерно по всем типам), задав типы параметров либо как универсальные, так и типа object (типы значений автоматически «упаковываются» в объекты)

...