В OCaml
let sub x y = x - y
является сокращенной записью (syntacti c sugar) для
let sub = fun x -> fun y -> x - y
Чтобы получить его, давайте выберем еще более простой пример,
let succ x = x + 1
- это более короткая форма syntacti c для
let succ = fun x -> x + 1
, в которой говорится, что мы связываем имя succ с функцией fun x -> x + 1, где последняя является литералом функции. Литерал в языках программирования - это обозначение syntacti c для определения значений. Например, для целых чисел у нас есть конечный набор литералов 1, 2, 3, et c. Для строк у нас есть практически бесконечный набор литералов, например, "hello", "", "etc". Функция в OCaml также является значением, таким же, как целое число или строка, поэтому она имеет синтаксис для литералов функций, который равен
fun <arg> -> <body>
. Она создает функцию, которая оценивается как значение <body>, в котором все свободные вхождения <arg> подставляются в качестве фактически переданного параметра.
Как вы, наверное, заметили, мы действительно могли связать только один параметр в литерале функции. Действительно, все функции в OCaml одинарные. Возможно, вы уже знаете, что можете определять такие функции, как fun x y -> x - y, но это также просто syntacti c sugar для fun x -> fun y -> x - y. Так что же означает последняя запись? Давайте напишем скобки, чтобы получить представление о том, как эта функция оценивается:
fun x -> (fun y -> x - y)
Таким образом, мы можем распознать часть fun x -> <body>, где <body> является функцией самой себя, то есть <body> = fun y -> x - y. Это означает, что выражение fun x -> fun y -> x - y является функцией, которая принимает аргумент x и возвращает другую функцию, которая принимает аргумент y и возвращает x-y. Этот способ определения функций, т. Е. Когда вместо функций, принимающих кортежи, имеется функция, которая возвращает функцию и т. Д., Называется curry .
Теперь, когда нас устраивает идея карри и что все функции в OCaml действительно имеют один аргумент, мы можем go вернуться к исходному примеру функциональных словарей.
Функция добавления
let add (d : 'a dict) (k, v) : 'a dict = fun k' -> if k' = k then v else d k'
, лишенная (ненужных) аннотаций типа
let add d (k, v) = fun k' -> if k' = k then v else d k'
и затем представленная в форме, которая делает карри явным, равна
let add = fun d -> fun (k, v) -> fun k' -> if k' = k then v else d k'
Таким образом, это функция, которая для данного словаря d создает функцию, которая принимает пару (k,v) и возвращает функцию, которая для всех k', равных k, вернет d. А если ключи разные, то он применяет ключ к первому параметру d. Давайте глубже рассмотрим литерал
fun k' -> if k' = k then v else d k'
. Как мы видим, переменные d и k свободны в этой функции, то есть они не связаны параметром k. Когда функция ссылается на переменную из внешней области (которая не определена на уровне модуля), создается closure . Закрытие - это непрозрачный объект, который содержит указатель на код 1 (в нашем случае это if k' = k then v else d k' и указатели на каждую захваченную переменную (т. Е. На каждую переменную, которая берется из внешней области видимости.) В нашем случае он создает (примерно) запись, которая имеет три записи: d, k и код. После нескольких часов посредничества нетрудно увидеть, что функция словарь - это просто односвязный список замыканий, так как d является указателем на замыкание, которое, в свою очередь, содержит указатель на другое замыкание, пока мы не достигнем указателя на empty, который возвращает None независимо от того, имеет значение ключ (и в вашем примере он закодирован неверно, так как он должен ожидать любую клавишу, а не значение единицы типа).
Учитывая все сказанное и помня, мы можем написать сокращенную запись нотация для функции add:
let add d k k' = if k' = k then v else d k'
, которая имеет абсолютно ту же семантику (то есть значение, поведение), что и любые другие нотации, поскольку это просто syntacti c sugar.
1) Чтобы избежать путаницы, сам код никогда не сохраняется в куче памяти. Даже если у вас есть анонимная функция, которая не привязана ни к какому имени, например , (fun x y -> x + y) 2 3 компилятор сгенерирует код и сохранит его в текстовом разделе двоичного файла и присвоит ему забавное имя. Поэтому приведенный выше код будет обычным вызовом функции с искаженным именем, например, call Testing_fun001. Возвращаясь к примеру с функциональным словарем, каждая запись будет объектом с тремя словами, ключом, данными, указателем на следующую запись. В основном то же базовое представление, что и список ассоциаций.