Алексей Махоткин

домашняя страница

Функции высшего порядка — критика Standard ML

Andrew W. Appel, «Критика Standard ML», оглавление

В ML, как и в Scheme и в других языках, порожденных от λ-исчисления, функции являются значениями первого класса, и их можно передавать в качестве аргументов, возвращать в качестве результатов, и помещать в структуры данных.

Конечно, в языке C тоже есть «функции первого класса», но между ними и функциональными значениями в ML есть существенная разница. В ML можно делать вложенные определения функций с лексической областью видимости; внутренние функции могут обращаться к локальным переменным и формальным параметрам внешних функций. Таким образом, каждый раз, когда внешняя функция вызывается с различными аргументами, как бы создается «новая версия» внутренней функции. Вот простой пример:

fun add(x: int) =
  let fun f(y) = x+y
    in f
  end

val smallinc = add(1)
val biginc   = add(10)

val twelve = smallinc(biginc(1))

Ключевое слово fun служит для объявления функции. Синтаксическая конструкция let dec in exp end задает локальную декларацию dec, которая видна только в выражении exp. Таким образом, если применить функцию add к единице, то создается и возвращается в качестве результата функция f1(y) = 1 + y. Когда вычисляется add 10, то в результате образуется функция f10(y) = 10 + y.

Эту функцию, add можно короче записать в виде
fun add x y = x+y:int
где ограничитель типа :int обязателен из-за перегрузки; см. раздел 3

Представим на мгновение язык программирования, в котором значения типа «строка символов» можно хранить в переменных, передавать в качестве аргументов, возвращать в качестве результата; предположим, что строки символов можно записывать в виде литерала, и что можно извлекать из строки отдельные символы. Но: нет ни одного оператора вроде concatenate, которые могут создавать новые значения типа «строка символов» во время выполнения! Такие строки символов будут иметь слишком ограниченную область применения; их можно будет использовать для печати интерактивных сообщений, объявленных на стадии компиляции, и т. д., но не больше. Тип данных, который существует только в виде литералов на стадии компиляции, с трудом можно назвать «типом данных первого класса».

Именно такова ситуация с указателями в C! Существуют только те значения-функции, которые были определены на стадии компиляции; никак нельзя создать функции типа f1 или f10 из вышеприведенного примера. Это из-за того, что C не позволяет создавать вложенные функции с лексической областью видимости. Подобным образом, несмотря на то, что Modula-3 позволяет создавать вложенные функции с лексической областью видимости, только функции, определенные на самом верхнем уровне вложенности, можно передавать в качестве аргументов.

С другой стороны, Pascal позволяет передавать вложенные функции (с лексической областью видимости) в качестве аргументов, но не возвращать их в качестве результатов или хранить в структурах данных. Это ограничение резко сокращает область применимости значений-функций. Ограничения C и ограничения Pascal появились из-за желания избежать необходимости сборки мусора: функции первого класса с вложенными областями видимости нельзя реализовать с помощью обычного стека записей активации. С другой стороны, когда в системе уже есть сборщик мусора, вложенные функции первого класса не так уж сильно увеличивают сложность реализации языка.

Возможно, каждому следует написать несколько программ с использованием функций первого класса, чтобы оценить их выразительные средства. Однако, вот несколько примеров их использования:

Функции сведения списков:
Возьмем бинарный оператор, например + или ×, и применим его к последовательности значений, чтобы получить
a1 × a2 × … × an × 1
(Мы добавляем × 1, чтобы должным образом обрабатывать случай, когда n = 0.) Такую операцию очень легко можно обобщить: при заданном операторе opr и единичном элементе I для этого оператора, функция reduce(opr, I) — это функция, которая применяет оператор к целому списку значений. Таким образом, функция sum, которая подсчитывает сумму элементов списка — это просто $reduce(+, 0)$, а функция product — это reduce(×, 1). В ML можно написать просто:
fun reduce(opr,I) =
  let fun f(nil) = I
        | f(a::rest) = opr(a, f(rest))
   in f
  end

val sum     = reduce(op +, 0)
val product = reduce(op *, 1)
fun min(a, b:int) = if a<b then a else b
val infinity = 1000000000
val minlist = reduce(min, infinity)
val fifteen = sum(1::2::3::4::5::nil)
Ключевое слово op позволяет использовать инфиксные операторы типа * в качестве обычных идентификаторов.
Оконный менеджер:
Можно организовать оконный интерфейс так, что приложение, выполняемое в окне, представляется клавиатурой и мышью.
Интересная и полезная оконная библиотека была реализована на ML Ганснером и Реппи в виде очень элегантного интерфейса к X-серверу. Приведенный пример не описывает их систему.
Для того, чтобы передать приложению символы, печатаемые в окне, вызывается его функция keyboard; чтобы передать щелчки мышью, вызывается функция mouse. Итак:
type window_app =
     {keyboard: string->unit,
      mouse: int*int->unit}
Эта запись означает, что window_app — это запись, содержащая два поля: keyboard и mouse. keyboard — принимает строковый параметр, и возвращает «unit» (это тип данных вроде «void» в C), а функция mouse принимает в качестве аргументов пару координат. Итак, теперь оконный менеджер может передавать нажатия клавиш и щелчки мышью приложению, вызывая эти функции. Все это выглядит довольно «объектно-ориентированно»; приватные данные приложения (т. е. «self» в терминах OOP) спрятаны в свободных переменных этих двух функций. В C необходимо было бы добавить в запись window_app явное поле «self», и передавать его в функции keyboard и mouse в виде дополнительного аргумента.

Многие интересные методы использования функций первого класса объединяют использование вложенной лексической области видимости (где свободные переменные внутренних функций привязаны во внешней функции) с функциями, возвращаемыми в качестве результата или сохраненными в структурах данных. Итак, как раз та комбинация, которую исключили из C и Pascal, потому что её сложно реализовать (она требует сборки мусора для записей активации), и является самой полезной.

Comments