После длительного перерыва решил таки продолжить вести свои странные записи, теперь уже инженера по специальности 230101 “Вычислительные машины, комплексы, системы и сети” :)

Сегодня я расскажу о таком интересном расширении системы типов, как параметрический полиморфизм второго и более высоких рангов. Из известных мне языков, её поддерживает только Haskell (как минимум компилятор GHC, в качестве языкового расширения), а так же Scala со сложнейшей системой типов способна выразить данный тип полиморфизма. Думаю будет интересно немного исследовать данное расширение и эмулировать в рамках более простой системы типов (лично мне всегда легче понять какую-нибудь возможность/особенность языка программирования, если я понимаю как она реализована на более низком уровне).

Суть данной фичи достаточно проста. Обычно, в языках с параметрическим полиморфизмом, мы можем определять полиморфные функции, но не можем их передать в другие функции, предварительно не сделав их мономорфными, то есть мы вынуждены применить к ним какой-либо тип-аргумент. Параметрический полиморфизм второго ранга позволяет обойти это ограничение, допуская определения функции с типом вида foo: (f<’a>: ‘a -> int) -> string (это псевдосинтаксис, не настоящий F#). Тут функция foo не является полиморфной, но получает полиморфную функцию f типа 'a -> int (я дал аргументу имя лишь для большей наглядности) и может внутри себя сколько угодно применять к ней аргументы любого типа. Становится возможно как-бы вытащить <’a> (что есть forall a в Haskell) из левой стороны сигнатуры функции и разместить для любого из аргументов.

Однако существует несколько ограничений. Параметрический полиморфизм второго ранга разрешает аргументам иметь полиморфный тип, но не позволяет типам аргументов включать в себя полиморфные типы в виде типов-параметров (то есть нельзя написать функцию, получающую список полиморфных функций с типом List<(f<’a>: ‘a -> ‘a)> -> unit). Из-за этого появляется ограничение, не позволяющее использовать как значение первого класса функции, содержащие в сигнатуре типы второго ранга (то есть нельзя пользоваться ими как значениями, использовать с функциями высшего порядка). Мы просто не можем описать сигнатуру таких функций, не имея возможность указывать полиморфные типы в функциональном типе (справа или слева от “стрелочки”, ведь 'a -> 'b по сути это тип (->)<’a,’b> с двумя типами-аргументами, а значит мы упираемся в ограничение второго ранга).

Разрешить данное ограничение позволяет параметрический полиморфизм произвольного ранга (ранга N), допуская подобные сумасшедшие определения - foo< >: (f<’a>: ‘a -> (g<’b>: ‘b -> ‘b)) -> unit - функция foo, получающая первым аргументом полиморфную функцию, получающую аргумент произвольного типа 'a и возвращающая некую полиморфную функцию g типа 'b -> 'b, при этом сама функция foo опять же не получает типов-параметров, то есть не является полиморфной (в F# это можно подчеркнуть, используя синтаксис < >, означающий функцию без типов-параметров, то есть не полиморфную).

К сожалению, так как F# построен поверх системы типов .NET (а она не поддерживает параметрический полиморфизм высших рангов), описанной возможности в языке нет, однако её достаточно просто эмулировать. Допустим у нас есть полиморфная функция, умеющая печатать значения типа 'a на экран:

/// printAny : 'a -> unit
let printAny x = printfn "%A" x

А ещё есть некоторый тип данных и мы хотим написать функцию, выводящая содержимое этого типа данных в через некую функцию-принтер (это может быть вывод на экран или сериализация, например). Проблема в том, что тип данных может хранить в себе содержимого различного типа:

type Record = { id   : int
                name : string }

/// printRecord : Record -> (? -> unit) -> unit
let printRecord r printer = printer r.id
                            printer r.name

printRecord { id = 123; name = "Alex" } printAny

Тут мы сталкиваемся с тем, что не можем написать корректный тип вместо ? (obj не считается, так как мы не хотим терять информацию о типах, нужна именно полиморфная функция, которая потенциально может ещё и устанавливать какие-либо ограничения на тип-параметр). Параметрический полиморфизм второго ранга позволил бы задать корректный тип и передать функцию printAny без указания типа-параметра.

F# для представления функций как значений генерирует наследников специального абстрактного класса FSharpFunc<’T, ‘TResult>, определяющего единственный метод: this.Invoke: ‘T -> ’TResult. То есть когда мы применяем типы-параметры к функциональному типу 'a -> 'b, то на самом деле мы указываем типы-параметры CLI-типу FSharpFunc<’T, ‘TResult> и эти типы попадают во все сигнатуры функций высшего порядка.

Однако помимо generic-типов в CLI существуют ещё и generic-методы. Если создать абстрактный класс с generic-методом this.Invoke<’T, ‘TResult>: ‘T -> ‘TResult, то этот класс будет “скрывать” в себе типы-параметры этого generic-метода (получается некий type erasure) и экземпляр этого класса можно трактовать как значение так нужного нам полиморфного функционального типа. Давайте перепишем пример выше в валидный F# следующим образом:

type PolyFunc = abstract Invoke : 'a -> unit

/// printRecord : Record -> PolyFunc -> unit
let printRecord r (printer: PolyFunc) =
  printer.Invoke r.id
  printer.Invoke r.name

printRecord
  { id = 123; name = "Alex" }
  { new PolyFunc with member __.Invoke x = printAny x }

Абстрактный тип PolyFunc определяет generic-метод Invoke с нужной нам сигнатурой, функция printRecord теперь может быть корректно типизирована, а по месту вызова в качестве полиморфной функции мы передаём экземпляр наследника типа PolyFunc (который тут же определяем с помощью F# object expression), в переопределении метода Invoke которого мы вызываем метод printAny, передавая свой тип-параметр (явно это показано в коде ниже).

member __.Invoke<'a> (x: 'a) = printAny<'a> x

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