Полиморфизм строк

редактировать

В языке программирования теория типов полиморфизм строк является разновидностью полиморфизм, который позволяет писать программы, полиморфные по типам полей записи (также известные как строки, отсюда и полиморфизм строк). Строчная полиморфная система типов и доказательство вывода типов были введены Митчеллом Уандом.

Записи и типы записей

Значение записи записывается как ${ℓ 1 = e 1,…, ℓ N = ru} {\ displaystyle \ {\ ell _ {1} = e_ {1}, \ dots, \ ell _ {n} = e_ {n} \}}$ ${\ displaystyle \ {\ ell _ {1} = e_ {1}, \ dots, \ ell _ {n} = e_ {n} \}}$ , где запись содержит $n {\ displaystyle n}$ $n$ поля (столбцы), $ℓ i {\ displaystyle \ ell _ {i}}$ $\ ell_i$ - поля записи, а $ei {\ displaystyle e_ {i}}$ $e_ {i}$ - значения полей. Например, запись, содержащая трехмерную декартовую точку, может быть записана как $P oint 3 d = {x = 1, y = 2, z = 3} {\ displaystyle Point3d = \ {x = 1, y = 2, z = 3 \}}$ ${\ displaystyle Point3d = \ {x = 1, y = 2, z = 3 \}}$ .

Тип записи с полиморфной строкой записывается как ${ℓ 1: T 1,…, ℓ n: T n, отсутствует (f 1),…, отсутствует (fm), ρ} {\ displaystyle \ {\ ell _ {1}: T_ {1}, \ dots, \ ell _ {n}: T_ {n}, {\ text {absent}} (f_ {1}), \ точки, {\ text {absent}} (f_ {m}), \ rho \}}$ ${\ displaystyle \ {\ ell _ {1}: T_ {1}, \ dots, \ ell _ {n}: T_ {n}, {\ text {absent} } (f_ {1}), \ dots, {\ text {absent}} (f_ {m}), \ rho \}}$ , где возможно $n = 0 {\ displaystyle n = 0}$ $n = 0$ или $m = 0 {\ displaystyle m = 0}$ $m = 0$ . Запись $r {\ displaystyle r}$ $r$ имеет строковый полиморфный тип записи всякий раз, когда поле записи $ℓ i {\ displaystyle \ ell _ {i}}$ $\ ell_i$ имеет тип $T i {\ displaystyle T_ {i}}$ $T_ {i}$ (для $i = 1… n {\ displaystyle i = 1 \ dots n}$ ${\ displaystyle i = 1 \ dots n}$ ) и не имеет полей $fj {\ displaystyle f_ {j}}$ $f_ {j}$ (для $j = 1… m {\ displaystyle j = 1 \ dots m}$ ${\ displaystyle j = 1 \ dots m}$ ). Строчная полиморфная переменная $ρ {\ displaystyle \ rho}$ $\ rho$ выражает тот факт, что запись может содержать поля, отличные от $ℓ i {\ displaystyle \ ell _ {i}}$ $\ ell_i$ .

Полиморфные по строкам типы записей позволяют нам писать программы, которые работают только с разделом записи. Например, $transform2d: {x: Float, y: Float, ρ} → {x: Float, y: Float, ρ} {\ displaystyle {\ text {transform2d}}: \ {x: {\ text { Float}}, y: {\ text {Float}}, \ rho \} \ to \ {x: {\ text {Float}}, y: {\ text {Float}}, \ rho \}}$ ${\ displaystyle {\ text {transform2d}}: \ {x: {\ text {Float}}, y: {\ text {Float}}, \ rho \} \ to \ {x: {\ text {Float} }, y: {\ text {Float}}, \ rho \}}$ - это функция, выполняющая какое-то двумерное преобразование. Из-за полиморфизма строки функция может выполнять двумерное преобразование в трехмерной (фактически, n-мерной) точке, оставляя координату z неизменной. Более того, функция может выполняться с любой записью, содержащей поля $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ с типом $Float {\ displaystyle {\ text {Float}}}$ ${\ displaystyle {\ text {Float}}}$ . Обратите внимание, что не было потери информации: тип гарантирует, что все поля, представленные переменной $ρ {\ displaystyle \ rho}$ $\ rho$ , присутствуют в возвращаемом типе.

Полиморфизмы строк могут быть ограничены. Тип ${x: Float, y: Float, empty} {\ displaystyle \ {x: {\ text {Float}}, y: {\ text {Float}}, \ mathbf {empty} \}}$ ${\ displaystyle \ {x: {\ text {Float}}, y: {\ text {Float}}, \ mathbf {empty} \}}$ выражает тот факт, что запись этого типа имеет точно поля $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ и ничего больше. Таким образом, получается классический тип записи.

Операции ввода с записями

Операции с записями выбора поля $r. ℓ {\ displaystyle r. \ ell}$ ${\ displaystyle r. \ Ell}$ , добавление поля, $r [ℓ: = e] {\ displaystyle r [\ ell: = e]}$ ${\ displaystyle r [\ ell: = e]}$ и удаление Поле $r ∖ ℓ {\ displaystyle r \ backslash \ ell}$ ${\ displaystyle r \ backslash \ ell}$ может иметь строковый полиморфный тип.

$s e l e c t ℓ = λ r. (р. ℓ): {ℓ: T, ρ} → T {\ displaystyle \ mathrm {select _ {\ ell}} = \ lambda r. (r. \ ell) \;: \; \ {\ ell: T, \ rho \} \ rightarrow T}$ ${\ displaystyle \ mathrm {select _ {\ ell}} = \ lambda r. (r. \ ell) \;: \; \ {\ ell: T, \ rho \} \ rightarrow T}$

$добавить ℓ = λ r. λ е. р [ℓ: = е]: {отсутствует (ℓ), ρ} → T → {ℓ: T, ρ} {\ displaystyle \ mathrm {add _ {\ ell}} = \ lambda r. \ lambda er [\ ell: = e] \;: \; \ {\ mathrm {absent} (\ ell), \ rho \} \ rightarrow T \ rightarrow \ {\ ell: T, \ rho \}}$ ${\ displaystyle \ mathrm {add _ {\ ell}} = \ lambda r. \ Lambda er [\ ell: = e] \;: \; \ {\ mathrm {absent} (\ ell), \ rho \} \ rightarrow T \ rightarrow \ {\ ell: T, \ rho \}}$

$удалить ℓ = λ r. р ∖ ℓ: {ℓ: T, ρ} → {отсутствует (ℓ), ρ} {\ displaystyle \ mathrm {remove _ {\ ell}} = \ lambda rr \ backslash \ ell \;: \; \ {\ ell: T, \ rho \} \ rightarrow \ {\ mathrm {absent} (\ ell), \ rho \}}$ ${\ displaystyle \ mathrm {remove _ {\ ell}} = \ lambda rr \ backslash \ ell \;: \; \ {\ ell: T, \ rho \} \ rightarrow \ {\ mathrm {absent} (\ ell), \ rho \}}$

Примечания

^Wand, Mitchell (июнь 1989 г.). «Вывод типа для объединения записей и множественного наследования». Ход работы. Четвертый ежегодный симпозиум по логике в компьютерных науках. С. 92–97. doi : 10.1109 / LICS.1989.39162.
^Палочка, Митчелл (1991). «Вывод типа для объединения записей и множественного наследования». Информация и вычисления. 93 (Выборки из симпозиума IEEE 1989 г. по логике в компьютерных науках): 1–15. DOI : 10.1016 / 0890-5401 (91) 90050-C. ISSN 0890-5401.