Функциональное программирование в Icon/ObjectIcon

Не так давно, один из авторов этого блога высказал мне свое мнение относительно кода моей библиотеки extmath. Ничего плохого в мнении не было, но он своей фразой «код похож на функциональный стиль» (точную формулировку не вспомню) сподвиг меня на написание этой статьи, чего бы никогда не пришло мне в голову… Так что, добро пожаловать в экскурс в функциональное программирование в Icon !

Начну я с того, что в Icon процедуры являются величинами первого класса, что позволяет присваивать переменным сами процедуры, а не результаты их выполнения. Это утверждение легко проиллюстрировать следующим кодом:

procedure main()
local p
p := cube
write(p(3))
end

procedure cube(x)
return x * x * x
end

Нетрудно понять, что в переменной p оказывается сама процедура cube, и поэтому в результате выполнения этого кода на выходе мы получим куб числа 3. Но и это еще не все.

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

Однако, не следует думать, что все процедуры в Icon являются чистыми — Icon не является чисто функциональным, да и программисту ничто не мешает определить процедуру с побочным эффектом.

Не одними чистыми процедурами (=функциями) жив функциональный стиль. В функциональном стиле присутствует также определенный набор техник.

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

procedure factorial(x)
if x < 2 then return 1 else return factorial(x-1) * x
end

procedure fibbonacci(x)
if x = 0 | x = 1 then return 1 else return fibbonacci(x-1) + fibbonacci(x-2)
end

Примеры по моему ясны и говорят сами за себя, кроме того рекурсию можно использовать для того, чтобы в Icon ввести некоторые функции (в том числе и функции высшего порядка):

procedure mapf(f,l)
local i,acc
acc := []
every i:= 1 to *l do {
    if type(l[i]) ~== "list" then put(acc,f(l[i])) else {
       put(acc,mapf(f,l[i]))
    }
}
return acc
end

Этот код, позволит ввести в Icon процедуру аналогичную функции map из функциональных языков (напоминаю, функция map(f,l) возвращает список, построенный в результате применения процедуры f к каждому элементу из списка l). Стоит заметить, что процедура mapf работает для функций одного аргумента, однако, в принципе можно построить реализацию для map с двумя аргументами.

Кроме функции map можно и реализовать другие функции высшего порядка, например, очень полезной может быть функция filter(f,l), которая возвращает список элементов списка l для которых функция истинна (дает хоть какой-то результат, отличный от fail). Эта функция известна многим программистам, использующим Python и ее легко можно реализовать, используя код, похожий на код процедуры mapf:

procedure filter(f,l)
local i,acc
acc := []
every i:= 1 to *l do {
     if type(l[i]) ~== "list" then {
       if f(l[i]) then put(acc,l[i])
     } else put(acc,filter(f,l[i]))
}
return acc
end

Эту процедуру испытать можно таким образом:

procedure f1(x)
if x % 2 = 0 then return 1 else 0
end

procedure f2(x)
if x % 2 = 0 then return
end

procedure f3(x)
if x % 2 = 0 then return 1 else fail
end

procedure main()
local a,b,c,d
a := [1,2,3,4,5,6,7,8,9,10]
b := filter(f1,a)
c := filter(f2,a)
d := filter(f3,a)
every write(!b)
every write(!с)
every write(!d)
end

В результате работы программы получиться несколько списков, в которых присутствуют только четные числа. Процедуры f1,f2,f3 — абсолютно идентичны друг другу и показывают тот факт, что фильтрующую функцию можно описать по-разному.

Во многих функциональных языках присутствует функция свертки списка с помощью некоторой функции (обычно именуется как reduce или accumulate). Иногда эта функция бывает и не одна, а как минимум две: foldl — лево-ассоциативная свертка и foldr — право-ассоциативная свертка. Но к сожалению, в Icon отсутствуют эти функции :(

Однако, обе функции легко реалезуемы с помощью чисто императивного кода:

procedure foldl(f,start,l)
local i
every i := 1 to *l do {
     if type(l[i]) ~== "list" then start := f(start,l[i]) else start := f(start,foldl(f,start,l[i]))
}
return start
end

procedure foldr(f,start,l)
local i
every i := *l to 1 by -1 do {
     if type(l[i]) ~== "list" then start := f(start,l[i]) else start := f(start,foldl(f,start,l[i]))
}
return start
end

Эти процедуры принимают три аргумента — функцию, стартовое значение (по сути дела, начальное значение внутреннего аккумулятора функции) и список. foldl и foldr в большинстве бинарных операций дают один и тот же результат, однако, это выполнимо не всегда (в частности, для функций, где позиции аргументов имеют значение).

Благодаря этим процедурам можно элегантно решать некоторые задачи, например можно осуществить суммирование элементов списка вот таким образом:

procedure plus(a,b)
return a + b
end

procedure summ(l)
return foldl(plus,0,l)
end

Причем, это будет работать и для вложенных списков.

Icon, как мультипарадигменный язык, позволяет использовать и функциональную парадигму (правда, приходиться вводить некоторые расширения) и активно сочетать ее с императивной.

Не стоит воспринимать описанное в статье как полный обзор, поскольку рассмотрены далеко не все возможности ФП в Icon, однако, были показаны основные идеи по его введению в свои программы.

Добавить комментарий