Параметричность - Parametricity

В теория языков программирования, параметричность это свойство абстрактной однородности, которым пользуется параметрически полиморфный functions, который улавливает интуицию, что все экземпляры полиморфной функции действуют одинаково.

Идея

Рассмотрим этот пример на основе набора Икс и тип Т(Икс) = [Икс → Икс] функций из Икс себе. Функция высшего порядка дваждыИкс : Т(Икс) → Т(Икс) предоставлено дваждыИкс(ж) = ж ∘ ж, интуитивно не зависит от множества Икс. Семейство всех таких функций дваждыИкс, параметризованные наборами Икс, называется "параметрически полиморфная функция ". Мы просто пишем дважды для всего семейства этих функций и запишите его тип как Икс. Т(Икс) → Т(Икс). Отдельные функции дваждыИкс называются составные части или же экземпляры полиморфной функции. Обратите внимание, что все функции компонентов дваждыИкс действуют «одинаково», потому что они даны одним и тем же правилом. Остальные семейства функций, получаемые выбором по одной произвольной функции из каждого Т(Икс) → Т(Икс) не было бы такого единообразия. Они называются "для этого случая полиморфные функции ". Параметричность это абстрактное свойство, которым обладают одинаково действующие семьи, такие как дважды, что отличает их от для этого случая семьи. При адекватной формализации параметричности можно доказать, что параметрически полиморфные функции типа Икс. Т(Икс) → Т(Икс) взаимно однозначны с натуральными числами. Функция, соответствующая натуральному числу п дается правилом ж жп, т.е. полиморфный Церковная цифра за п. Напротив, сбор всех для этого случая семьи были бы слишком большими для множества.

История

В теорема о параметричности первоначально было заявлено Джон С. Рейнольдс, который назвал это теорема абстракции.[1] В своей статье «Теоремы бесплатно!»,[2] Филип Вадлер описал применение параметричности для вывода теорем о параметрически полиморфный функции в зависимости от их типов.

Реализация языка программирования

Параметричность - основа многих программные преобразования реализовано в компиляторах для Язык программирования Haskell. Эти преобразования традиционно считались правильными в Haskell из-за того, что Haskell нестрогий семантика. Несмотря на то, что ленивый язык программирования, Haskell поддерживает некоторые примитивные операции, такие как оператор seq- которые обеспечивают так называемую «избирательную строгость», позволяющую программисту принудительно вычислять определенные выражения. В своей статье «Бесплатные теоремы при наличии seq",[3] Патрисия Иоганн и Янис Фойгтлендер показал, что из-за наличия этих операций общая теорема о параметричности не выполняется для программ на Haskell; таким образом, эти преобразования в целом несостоятельны.

Зависимые типы

Смотрите также

Рекомендации

  1. ^ Рейнольдс, Дж. К. (1983). «Типы, абстракция и параметрический полиморфизм» (PDF). Обработка информации. Северная Голландия, Амстердам. С. 513–523.
  2. ^ Уодлер, Филипп (сентябрь 1989 г.). "Теоремы бесплатно!". 4-я Международная конф. по функциональному программированию и компьютерной архитектуре. Лондон.
  3. ^ Иоганн, Патрисия; Янис Фойгтлендер (январь 2004 г.). "Бесплатные теоремы при наличии seq". Proc., Принципы языков программирования.. С. 99–110.

внешняя ссылка