Кодировка Могенсена – Скотта - Mogensen–Scott encoding

В Информатика, Кодирование Скотта это способ представить (рекурсивные) типы данных в лямбда-исчисление. Церковная кодировка выполняет аналогичную функцию. Данные и операторы образуют математическую структуру, которая встроенный в лямбда-исчислении.

В то время как кодирование Черча начинается с представления основных типов данных и строится на нем, кодирование Скотта начинается с простейшего метода составления алгебраические типы данных.

Кодировка Могенсена – Скотта расширяет и немного изменяет кодировку Скотта, применяя кодировку к Метапрограммирование. Эта кодировка позволяет представить лямбда-исчисление термины, как данные, которые будут использоваться метапрограммой.

История

Кодировка Скотта впервые появляется в наборе неопубликованных лекций автора Дана Скотт^[1]чья первая цитата встречается в книге Комбинаторная логика, том II^[2]. Мишель Париго дал логическую интерпретацию и решительно нормализация рекурсор для чисел в кодировке Скотта,^[3] ссылаясь на них как на представление чисел «Тип стека».Торбен Могенсен позже расширил кодировку Скотта для кодирования лямбда-терминов как данных.^[4]

Обсуждение

Лямбда-исчисление позволяет хранить данные как параметры функции, которая еще не имеет всех параметров, необходимых для приложения. Например,

{ displaystyle (( lambda x_ {1} ldots x_ {n}. lambda c.c x_ {1} ldots x_ {n}) v_ {1} ldots v_ {n}) f}

Может рассматриваться как запись или структура, где поля ${ displaystyle x_ {1} ldots x_ {n}}$ были инициализированы значениями ${ displaystyle v_ {1} ldots v_ {n}}$ . Затем к этим значениям можно получить доступ, применив термин к функции ж. Это сводится к

{ Displaystyle е v_ {1} ldots v_ {п}}

c может представлять конструктор для алгебраического типа данных на функциональных языках, таких как Haskell. Теперь предположим, что есть N конструкторы, каждый с ${ displaystyle A_ {i}}$ аргументы;

{ displaystyle { begin {array} {c | c | c} { text {Constructor}} & { text {Заданные аргументы}} & { text {Result}} hline (( lambda x_ { 1} ldots x_ {A_ {1}}. Lambda c_ {1} ldots c_ {N} .c_ {1} x_ {1} ldots x_ {A_ {1}}) v_ {1} ldots v_ {A_ {1}}) & f_ {1} ldots f_ {N} & f_ {1} v_ {1} ldots v_ {A_ {1}} (( lambda x_ {1} ldots x_ {A_ {2}}. Lambda c_ {1} ldots c_ {N} .c_ {2} x_ {1} ldots x_ {A_ {2}}) v_ {1} ldots v_ {A_ { 2}}) & f_ {1} ldots f_ {N} & f_ {2} v_ {1} ldots v_ {A_ {2}} vdots & vdots & vdots (( lambda x_ { 1} ldots x_ {A_ {N}}. Lambda c_ {1} ldots c_ {N} .c_ {N} x_ {1} ldots x_ {A_ {N}}) v_ {1} ldots v_ {A_ {N}}) & f_ {1} ldots f_ {N} & f_ {N} v_ {1} ldots v_ {A_ {N}} end {array}}}

Каждый конструктор выбирает другую функцию из параметров функции. ${ displaystyle f_ {1} ldots f_ {N}}$ . Это обеспечивает ветвление в потоке процесса на основе конструктора. У каждого конструктора может быть свой арность (количество параметров). Если конструкторы не имеют параметров, то набор конструкторов действует как перечислить; тип с фиксированным количеством значений. Если у конструкторов есть параметры, можно создавать рекурсивные структуры данных.

Определение

Позволять D быть типом данных с N конструкторы, ${ Displaystyle {c_ {я} } _ {я = 1} ^ {N}}$ , такой что конструктор ${ displaystyle c_ {i}}$ имеет арность ${ displaystyle A_ {i}}$ .

Кодирование Скотта

Кодировка конструктора Скотта ${ displaystyle c_ {i}}$ типа данных D является

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} x_ {1} ldots x_ {A_ {i}} }

Кодировка Могенсена – Скотта

Mogensen расширяет кодировку Скотта для кодирования любого нетипизированного лямбда-термина как данных. Это позволяет представить лямбда-член в виде данных в рамках лямбда-исчисления. мета программа. Мета-функция mse преобразует лямбда-член в соответствующее представление данных лямбда-члена;

{ displaystyle { begin {align} operatorname {mse} [x] & = lambda a, b, ca x operatorname {mse} [M N] & = lambda a, b, cb operatorname {mse} [M] operatorname {mse} [N] operatorname {mse} [ lambda xM] & = lambda a, b, cc ( lambda x. operatorname {mse} [ M]) конец {выровнено}}}

«Лямбда-член» представлен как помеченный союз с тремя корпусами:

Конструктор а - Переменная (арность 1, не рекурсивный)
Конструктор б - применение функции (арность 2, рекурсивно в обоих аргументах),
Конструктор c - лямбда-абстракция (арность 1, рекурсивная).

Например,

{ displaystyle { begin {array} {l} operatorname {mse} [ lambda xf (x x)] lambda a, b, cc ( lambda x. operatorname {mse} [f (x x)]) lambda a, b, cc ( lambda x. lambda a, b, cb operatorname {mse} [f] operatorname {mse} [x x] ) lambda a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) operatorname {mse} [x x]) лямбда a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) ( lambda a, b, cb operatorname {mse} [x] operatorname {mse} [x])) lambda a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) ( lambda a, b, cb ( lambda a, b, ca x) ( lambda a, b, ca x))) end {array}}}

Сравнение с церковной кодировкой

Кодировка Скотта совпадает с Церковная кодировка для логических значений. Парное кодирование Чёрча можно обобщить на произвольные типы данных путем кодирования ${ displaystyle c_ {i}}$ из D выше как^{[нужна цитата ]}

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} (x_ {1} c_ {1} ldots c_ {N }) ldots (x_ {A_ {i}} c_ {1} ldots c_ {N})}

сравните это с кодировкой Могенсена Скотта,

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} x_ {1} ldots x_ {A_ {i}}}

При таком обобщении кодировки Скотта и Черча совпадают для всех перечисленных типов данных (таких как логический тип данных), поскольку каждый конструктор является константой (без параметров).

Что касается практичности использования кодировки Черча или Скотта для программирования, существует симметричный компромисс.^[5]: Цифры в кодировке Чёрча поддерживают операцию сложения с постоянным временем и имеют не лучше, чем операция предшественника с линейным временем; Числа в кодировке Скотта поддерживают операцию предшественника с постоянным временем и имеют не лучше, чем операция сложения с линейным временем.

Определения типов

Данные в кодировке Чёрча и операции над ними можно вводить в система F, но данные и операции в кодировке Скотта явно не типизируются в системе F. По-видимому, требуются универсальные, а также рекурсивные типы,^[6].Так как сильная нормализация не выполняется для неограниченно рекурсивных типов^[7]для установления завершения программ, манипулирующих данными в кодировке Скотта, путем определения правильной типизации требуется, чтобы система типов обеспечивала дополнительные ограничения на формирование рекурсивно типизированных терминов.

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

Заметки

^ Скотт, Дана, Система функциональной абстракции (1968). Лекции, прочитанные в Калифорнийском университете в Беркли (1962 г.)
^ Карри, Хаскелл (1972). Комбинаторная логика, Том II. Издательская компания Северной Голландии. ISBN 0-7204-2208-6.
^ Париго, Мишель (1988). «Программирование с доказательствами: теория типа второго порядка». Европейский симпозиум по программированию. Конспект лекций по информатике. 300: 145–159. Дои:10.1007/3-540-19027-9_10. ISBN 978-3-540-19027-1.
^ Могенсен, Торбен (1994). «Эффективная самоинтерпретация в лямбда-исчислении». Журнал функционального программирования. 2 (3): 345–364. Дои:10.1017 / S0956796800000423.
^ Париго, Мишель (1990). «О представлении данных в лямбда-исчислении». Международный семинар по компьютерной логике. Конспект лекций по информатике. 440: 209–321. Дои:10.1007/3-540-52753-2_47. ISBN 978-3-540-52753-4.
^ См. Примечание «Типы чисел Скотта» Мартин Абади, Лука Карделли и Гордон Плоткин (18 февраля 1993 г.).
^ Мендлер, Накс (1987). «Рекурсивные типы и ограничения типов в лямбда-исчислении второго порядка». Симпозиум по логике в компьютерных науках (2): 30–36.

использованная литература

Непосредственно рефлексивное метапрограммирование
Торбен Могенсен (1992). Эффективная самоинтерпретация в лямбда-исчислении^{[постоянная мертвая ссылка ]}. Журнал функционального программирования.

[1] Скотт, Дана, Система функциональной абстракции (1968). Лекции, прочитанные в Калифорнийском университете в Беркли (1962 г.)

[2] Карри, Хаскелл (1972). Комбинаторная логика, Том II. Издательская компания Северной Голландии. ISBN 0-7204-2208-6.

[3] Париго, Мишель (1988). «Программирование с доказательствами: теория типа второго порядка». Европейский симпозиум по программированию. Конспект лекций по информатике. 300: 145–159. Дои:10.1007/3-540-19027-9_10. ISBN 978-3-540-19027-1.

[4] Могенсен, Торбен (1994). «Эффективная самоинтерпретация в лямбда-исчислении». Журнал функционального программирования. 2 (3): 345–364. Дои:10.1017 / S0956796800000423.

[5] Париго, Мишель (1990). «О представлении данных в лямбда-исчислении». Международный семинар по компьютерной логике. Конспект лекций по информатике. 440: 209–321. Дои:10.1007/3-540-52753-2_47. ISBN 978-3-540-52753-4.

[6] См. Примечание «Типы чисел Скотта» Мартин Абади, Лука Карделли и Гордон Плоткин (18 февраля 1993 г.).

[7] Мендлер, Накс (1987). «Рекурсивные типы и ограничения типов в лямбда-исчислении второго порядка». Симпозиум по логике в компьютерных науках (2): 30–36.

[1]

[2]

[3]

[4]

[5]

[6]

[7]