Недавно я работал над некоторыми экспериментальными новыми функциями и без того чрезвычайно мощной системы типов Цейлона. То, что я собираюсь объяснить в этом посте, технически известно как:
- универсальные типы более высокого порядка (или полиморфизм конструкторов типов , или более высокие виды ), и
- родовые типы более высокого ранга (или полиморфизм ранга N ).
Пожалуйста, не беспокойтесь об этом салате жаргон. (И, пожалуйста, не пытайтесь гуглить ни один из этих терминов, потому что объяснения, которые вы найдете, только заставят эти довольно простые понятия казаться запутанными.) Оставайтесь со мной, и я сделаю все возможное, чтобы объяснить концепции в интуитивно понятных терминах. без необходимости использования любой из вышеперечисленных терминов.
Но сначала давайте начнем с пары примеров, иллюстрирующих проблему мотивации.
Эта функция просто возвращает свой аргумент:
|
1
|
Object pipeObject(Object something) => something; |
Эта функция добавляет Float s:
|
1
|
Float addFloats(Float x, Float y) => x+y; |
Современный язык программирования позволяет нам рассматривать любую из этих функций как ценность и передавать ее по системе. Например, я могу написать:
|
1
|
Object(Object) pipeObjectFun = pipeObject; |
Или же:
|
1
|
Float(Float,Float) addFloatsFun = addFloats; |
Где Object(Object) и Float(Float,Float) представляют типы функций, а pipeObject и addFloats являются ссылками на функции. Все идет нормально.
Но иногда полезно иметь функцию, которая абстрагируется от конкретного типа данных с использованием обобщений. Мы вводим переменную типа для представления «неизвестного» типа вещей, с которыми мы имеем дело:
|
1
|
Any pipe<Any>(Any anything) => anything; |
И:
|
1
2
3
|
Number add<Number>(Number x, Number y) given Number satisfies Summable<Number> => x+y; |
Иногда, как в add() , неизвестный тип каким-то образом ограничен. Мы выражаем это, используя ограничение типа:
|
1
|
given Number satisfies Summable<Number> |
Это способ Цейлона обозначить, что Number может быть только типом, который является подтипом верхней границы Summable<Number> , то есть это тип, к которому мы можем применить оператор сложения + .
Теперь, что если я хочу передать ссылку на эту функцию. Ну, обычно я могу прибить неизвестный тип к конкретному значению:
|
1
|
Object(Object) pipeObjectFun = pipe<Object>; |
Или же:
|
1
|
Float(Float,Float) addFloatsFun = add<Float>; |
Но это немного разочаровывает — мы потеряли тот факт, что add() был универсальным. Теперь в объектно-ориентированных языках можно определить обобщенную функцию как член класса и передать экземпляр класса по системе. Это называется паттерном стратегии . Но неудобно писать целый класс только для инкапсуляции ссылки на функцию.
Было бы лучше иметь возможность написать:
|
1
|
TypeOfPipe pipeFun = pipe; |
И:
|
1
|
TypeOfAdd addFun = add; |
Где TypeOfPipe и TypeOfAdd являются типами универсальных функций. Проблема в том, что невозможно представить эти типы в системе типов большинства языков. Давайте посмотрим, как мы можем сделать это на Цейлоне 1.2.
Представляем функции типа
Я обещал избегать жаргона, и избегать жаргона я буду. Единственная терминология, которая нам понадобится, это идея функции типа . Функция типа, как следует из ее названия, — это функция, которая принимает ноль или более типов и создает тип. Поначалу функции типов могут показаться экзотическими и абстрактными, но есть одна вещь, которая поможет вам понять их:
Вы уже знаете почти все, что вам нужно знать о функциях типов, потому что почти все, что вы знаете об обычных функциях (значениях), верно и для функций типов.
Если вы будете придерживаться аналогии с обычными функциями, у вас не будет проблем с остальной частью этого поста, обещаю .
Итак, мы все знаем, как выглядит обычная функция:
|
1
|
function addFloats(Float x, Float y) => x+y; |
Давайте разберемся с этим, у нас есть:
- имя функции и список параметров слева от жирной стрелки и
- выражение справа от жирной стрелки.
Функция типа не выглядит по-другому. У него есть имя и (тип) параметры слева от жирной стрелки, а (тип) выражение справа. Это выглядит так:
|
1
|
alias Pair<Value> => [Value,Value]; |
Ага! Это то, что мы уже видели! Таким образом, функция типа — это не более чем псевдоним общего типа! Эта конкретная функция типа принимает тип и создает тип кортежа — пару, элементы которой имеют заданный тип.
На самом деле не каждая функция типа является псевдонимом типа. Универсальный класс или интерфейс является функцией типа. Например:
|
1
|
interface List<Element> { ... } |
Это объявление интерфейса принимает тип Element и создает тип List<Element> , так что это функция типа.
Я могу вызвать функцию, указав значения в качестве аргументов:
|
1
2
|
pipe("hello")add(1.0, 2.0) |
Эти выражения производят значения "hello" и 3.0 .
Я могу применить функцию типа, предоставив типы в качестве аргументов:
|
1
|
Pair<Float> |
Это выражение типа создает тип [Float,Float] , применяя функцию типа Pair к аргументу типа Float .
Точно так же я могу применить функцию типа List :
|
1
|
List<String> |
Это выражение типа буквально создает тип List<String> , применяя функцию типа List к аргументу типа String .
С другой стороны, я могу взять ссылку на функцию-значение, просто написав ее имя без каких-либо аргументов, например, pipe или add . Я могу сделать то же самое с функциями типа, написав Pair или List .
Вернувшись в мир обычных ценностей, я могу записать анонимную функцию :
|
1
|
(Float x, Float y) => x+y |
В платоническом мире типов я тоже могу это сделать:
|
1
|
<Value> => [Value,Value] |
Наконец, обычная функция значения может ограничить свои аргументы, используя аннотацию типа, такую как Float x . Функция типа может делать то же самое, хотя и с более громоздким синтаксисом:
|
1
2
3
4
5
6
|
interface List<Element> given Element satisfies Object { //define the type list ...} |
Даже функция анонимного типа может иметь ограничения:
|
1
2
|
<Value> given Value satisfies Object => [Value,Value] |
Наблюдение за жаргоном: большинство людей, включая меня, используют термин « конструктор типа» вместо «функция типа».
Типовые функции являются типами
Теперь мы собираемся сделать ключевой концептуальный скачок. Напомним, что в современных языках функции рассматриваются как значения. Я могу
- возьмите функцию и назначьте ее переменной, а затем
- вызвать эту переменную в теле функции.
Например:
|
1
2
3
4
5
6
7
8
9
|
void secondOrder(Float(Float,Float) fun) { print(fun(1.0, 2.0));}//apply to a function referencesecondOrder(addFloats);//apply to an anonymous functionsecondOrder((Float x, Float y) => x+y); |
Мы называем функции, которые принимают функции высшего порядка .
Точно так же мы собираемся объявить, что функции типов являются типами . То есть я могу:
- возьмите функцию типа и назначьте ее переменной типа, а затем
- применить эту переменную типа в теле объявления, которое она параметризует.
Например:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
interface SecondOrder<Box> given Box<Value> { shared formal Box<Float> createBox(Float float);}//apply to a generic type aliasSecondOrder<Pair> something;//apply to a generic interfaceSecondOrder<List> somethingElse;//apply to an anonymous type functionSecondOrder<<Value> => [Value,Value]> somethingScaryLookin; |
Ограничение типа, given Box<Value> указывает, что переменная типа Box принимает функции типа с одним аргументом типа.
Теперь есть одна вещь, чтобы принять к сведению здесь. На этом этапе представление о том, что функции типов являются типами, является чисто формальным утверждением. Аксиома, которая определяет, какие типы типов я могу записать, и ожидаю, что средство проверки типов моего языка программирования сможет рассуждать. Я еще не сказал, что существуют какие-либо фактические значения этих типов!
Jargon watch: способность обрабатывать функцию типа как тип называется дженериками высшего порядка .
Тип универсальной функции является функцией типа
Давайте вернемся к нашим мотивирующим примерам:
|
1
2
3
4
5
|
Any pipe<Any>(Any anything) => anything;Number add<Number>(Number x, Number y) given Number satisfies Summable<Number> => x+y; |
Если вы щуритесь, вы увидите, что это на самом деле функции с двумя списками параметров. Первые списки параметров:
|
1
|
<Any> |
И:
|
1
|
<Number> given Number satisfies Summable<Number> |
Которые оба принимают тип. Второй список параметров:
|
1
|
(Any anything) |
И:
|
1
|
(Number x, Number y) |
Следовательно, мы можем рассматривать каждую универсальную функцию как функцию, которая принимает тип и создает функцию обычного значения. Результирующие функции имеют тип Any(Any) и Value(Value,Value) соответственно.
Таким образом, мы можем записать тип нашей первой универсальной функции pipe() следующим образом:
|
1
|
<Any> => Any(Any) |
И тип add() :
|
1
2
|
<Number> given Number satisfies Summable<Number> => Number(Number,Number) |
Уф. Это выглядит немного страшно. Но в основном из-за ограничения типа. Поскольку типовые универсальные типы функций довольно многословны, мы можем назначить им псевдонимы:
|
1
2
3
|
alias AdditionLikeOperation => <Number> given Number satisfies Summable<Number> => Number(Number,Number); |
Или, что то же самое, но проще:
|
1
2
3
|
alias AdditionLikeOperation<Number> given Number satisfies Summable<Number> => Number(Number,Number); |
Это была сложная часть — мы почти закончили.
Ссылки на общие функции
Теперь мы можем использовать эти типы в качестве типов ссылок на универсальные функции:
|
1
2
3
|
<Any> => Any(Any) pipeFun = pipe;AdditionLikeOperation addFun = add; |
И мы можем применить эти ссылки на функции, предоставив аргументы типа:
|
1
2
3
4
5
|
String(String) pipeString = pipeFun<String>;Object(Object) pipeObject = pipeFun<Object>;Float(Float,Float) addFloats = addFun<Float>;Integer(Integer,Integer) addInts = addFun<Integer>; |
Или, в качестве альтернативы, мы можем просто немедленно применить ссылки на обобщенную функцию к аргументам- значениям и позволить Цейлону выводить аргументы типа, как это обычно делается при непосредственном вызове функции:
|
1
2
3
4
5
|
String hi = pipeFun("hello");Integer zero = pipeFun(0);Float three = addFun(1.0, 2.0);String helloWorld = addFun("Hello", "World"); |
И теперь мы решили проблему, поставленную в начале!
Теперь для кикера: типы <Any> => Any(Any) и AdditionLikeOperation являются функциями типов. Действительно, тип любой обобщенной функции является функцией типа этой общей формы:
|
1
|
<TypeParameters> => ReturnType(ParameterTypes) |
Точно так же каждая функция типа этой общей формы является типом некоторой универсальной функции.
Итак, теперь мы показали, что некоторые функции типов являются не только типами, но и типами значений — значения являются ссылками на универсальные функции, такие как pipe и add .
Jargon watch: способность обрабатывать обобщенную функцию как значение называется генериками более высокого ранга .
Абстракция над общими функциями
Наконец, мы можем использовать все это для чего-то полезного. Давайте рассмотрим библиотеку сканера, которая отделена от всех:
- тип персонажа,
- тип токена,
- тип контейнера, в котором находятся токены.
Тогда у нас может быть функция scan() с такой подписью:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
"Tokenize a stream of characters, producing a stream of tokens."Stream<Token> scan<Char,Token,Stream> (grammar, characterStream, newToken, newStream) //Note: Stream is a reference to a type function! given Stream<Element> satisfies {Element*} { //parameters: "The token grammar." Grammar grammar; "The character stream to tokenize." Stream<Char> characterStream; "Constructor for tokens, accepting a substream of characters." Token newToken(Stream<Char> chars); "Generic function to construct a stream of characters or tokens." //Note: newStream is a reference to a generic function! Stream<Elem> newStream<Elem>({Elem*} elements); //implementation: Stream<Token> tokenStream; //do all the hard work ... return tokenStream;} |
Вот:
-
Char— неизвестный тип символов, -
Token— это неизвестный тип токена, -
Stream— это функция типа, представляющая неизвестный тип контейнера, который может содержать символы или токены, -
newToken— это функция, которая принимает подпоток символов и создаетToken, -
characterStream— это поток символов, и, что наиболее важно, -
newStream— это универсальная функция, которая создает потоки любого типа элемента, используемые внутри для создания потоков символов и токенов.
Мы могли бы использовать эту функцию следующим образом:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
//Let's use String as the token type, Character as the//character type, and Iterable as the stream type.//input a stream of characters{Character*} input = ... ;//and some token grammarGrammar grammar = ... ;//get back a stream of Strings{String*} tokens = scan<Character, String, Iterable> (grammar, input, String, //Note: a generic anonymous function! <Elem>({Elem*} elems) => elems); |
Или вот так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
//use LinkedList as the stream typeimport ceylon.collection { LinkedList }//we don't need Unicode support, so let's use//Ceylon's 8-bit Byte as our character typealias Char => Byte;//define our own token typeclass BasicToken(LinkedList<Char> charList) { string => String { for (b in charList) b.unsigned.character };}//input a linked list of charactersLinkedList<Char> input = ... ;//and some token grammarGrammar grammar = ... ;//get back a linked list of BasicTokensLinkedList<BasicToken> tokens = scan<Char, BasicToken, LinkedList> (grammar, input, BasicToken, //Note: a generic function ref! LinkedList); |
Как видите, наш алгоритм синтаксического анализа теперь почти полностью отделен от конкретных типов, которые мы хотим использовать!
Компиляция этого кода
В Ceylon 1.2 программирование с использованием функций типов является экспериментальной функцией, которая работает только в сочетании с бэкэндом JavaScript. Таким образом, вы можете запускать код, который использует функции типов на виртуальной машине JavaScript, но не на JVM. Это то, с чем мы приглашаем вас поиграть, чтобы убедиться, что все сообщество согласится, что это полезно. Но сейчас он не описан в спецификации языка и не поддерживается бэкэндом Java.
Сам типограф проверяет чрезвычайно сложные рассуждения о типах высшего и более высокого ранга. Функции типов полностью интегрированы с мощной системой полиморфизма подтипов Цейлона, в том числе с типами объединения и пересечения, а также с выводом типа и выводом аргумента типа. Есть даже ограниченная поддержка вывода функций типа! И здесь нет произвольных верхних пределов; поддерживаются не только ранги 2, но и произвольные типы рангов.
Если будет достаточно интереса, я расскажу об этом материале в следующем посте.
| Ссылка: | Программирование с использованием функций типов на Цейлоне от нашего партнера JCG Гэвина Кинга в блоге команды Ceylon Team . |