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

5 14

Кто здесь?

Функциональное программирование (далее ФП) – это парадигма, в которой процесс вычислений трактуется как вычисление значений функций в математическом понимании, т.е. без побочных эффектов. В отличие от императивного (процедурного) программирования, нам надо описать не последовательность действий, а формулы для преобразования входных данных в выходные. Простейшим примером применения ФП являются формулы Excel.

 

В чем соль?

Всё есть функция

Функциональное программирование рассматривает любую сущность программы как функцию. Например, константа – это функция, возвращающая константное значение.

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

 

«Нет!» циклам

Чистое ФП категорически отвергает любое применение циклов. Вместо них применяется либо рекурсия, либо функции обработки списков (например, функции для обработки диапазонов в Excel).

 

Анонимные функции

Поскольку в ФП часто передаются функции в качестве аргументов и возвращаемого значения, то очень ценной становится возможность конструирования функций прямо по ходу, без предварительного их объявления.

 

Pro et contra

Компактность, верифицируемость и сложность

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

T = {x*y | x,y ∈ [1..10)}

На Python это будет выглядеть следующим образом:

T = [x*y for x in range(1, 10) for y in range(1, 10)]

 

Производительность и масштабируемость

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

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

 

Да кому нужен этот неуловимый Джо?

В настоящее время ФП используется в основном для нишевых решений, например:

  • серверные решения с повышенной масштабируемостью (Erlang);
  • компиляторы и интерпретаторы (Haskell);
  • обучение (Lisp).

Однако, благодаря появлению смешанных языков (реализующих, среди прочих, и функциональную парадигму) в мейнстрим-платформах - F# (отдельные приемы доступны даже в C#) в .NET и Clojure/Scala в Java – ситуация может измениться в будущем.

 

А что у нас?

Мы будем рассматривать только некоторые приемы ФП: функции работы со списками (отказ от циклов) и анонимные функции (получаемые за счет применения динамического ISBL).

 

Соглашения

Основной тип данных, для которого применяются приемы ФП, это список. Под списком в случае разработки на IS-Builder могут пониматься:

  • массив, который можно интерпретировать, как одномерный;
  • любое foreach-выражение (IForEach).

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

При указании элементов обрабатываемых списков будет применяться следующее соглашение о синтаксисе:

_a – элемент первого списка;

_b – элемент второго списка и т.д.;

__Var – переменная окружения с именем Var.

 

Конструирование вызовов

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

 

Map – преобразование списка

Функция Map() предназначена для преобразования списка поэлементно. Имеет два параметра:

  1. Выражение, применяемое к элементу списка.
  2. Список.

Результатом функции является список, построенный путем применения указанного выражения к элементам исходного списка.

Примеры:

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

Map('_a*2'; ArrayOf(1; 2; 3; 4; 5))

Для возведения элементов списка в квадрат, достаточно поменять

Map('_a*_a'; ArrayOf(1; 2; 3; 4; 5))

Для того, чтобы передать в вычисления данные (реализовать аналог замыканий), используем переменные окружения:

Object.Environment.SetVar('Mul'; 3)
MapC('_a * __Mul'; ArrayOf(1; 2; 3; 4))

MapC ("Map with Closures") – функция, аналогичная Map, но распознающая ссылки на переменные окружения.

 

Reduce – сворачивание (редуцирование) списка

Функция Reduce() предназначена для сворачивания списка в скалярную величину. Имеет два параметра:

  1. Выражение, применяемое к двум скалярным величинам.
  2. Список.

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

Примеры:

Сумма элементов массива:

Reduce('_a + _b'; ArrayOf(1; 2; 3; 4; 5)) 

Произведение элементов массива:

Reduce('_a * _b'; ArrayOf(1; 2; 3; 4; 5))

Конкатенация элементов массива:

Reduce('_a & _b'; ArrayOf(1; 2; 3; 4; 5))

 

Filter – фильтрация списка

Функция Filter() предназначена для фильтрации списка. Имеет следующие параметры:

  1. Условие, которому должен удовлетворять элемент списка.
  2. Список.

Функция возвращает список составленный из тех элементов исходного списка, которые удовлетворяют указанному условию.

Примеры:

Отфильтровать положительные элементы массива:

Filter('_a > 0'; ArrayOf(1; -2; 3; -4; 5))  

 

Пример

Все вышеописанные арифметические вычисления любопытны, но хотелось бы, конечно, проверить работу ФП на чем-то более приближенном к действительности. Рассмотрим такую задачу:

Необходимо экспортировать выбранные пользователем "последние" документы. При этом:

  • экспортироваться должны только документы Microsoft Word;
  • экспортироваться должны только последние версии документов;
  • перед выполнением экспорта следует запросить подтверждение пользователя, при этом в тексте запроса следует указать суммарный объем файлов экспорта.

 

Решение

// Выбор документов.
DocumentExplorer = ServiceFactory.GetExplorer(False)
DocumentExplorer.Title = 'Выберите документы для экспорта'
DocumentExplorer.ShowTree = isHide
DocumentExplorer.ListContents = Filter('_a.Editor.Code=="WORD"'; 
  Searches.ExecuteByName('LAST_CHANGED_EDOCUMENT_SEARCH'))
SelectedDocInfos = DocumentExplorer.SelectFromList
if VarIsNull(SelectedDocInfos)
  Raise(CreateException('ECancelByUser'; 
    'Экспорт не будет выполнен.'; ecInformation))  
endif

// Выбор папки в файловой системе.
FolderDialog = CreateFolderDialog()
FolderDialog.Title = 'Выбор папки для экспорта'
if not FolderDialog.Execute
  Raise(CreateException('ECancelByUser'; 
    'Экспорт не будет выполнен.'; ecInformation))  
endif

// Проверка размера.
Documents = Map('_a.Document'; SelectedDocInfos)
TotalSize = Reduce('_a + _b'; 
  Map('_a.Versions.Values(_a.Versions.Count-1).Size'; Documents))
if MessageBox('Подтверждение'; 'Общий размер файлов составит: ' &
     Round(TotalSize/1024; 0) & ' Кб.' & CR & 'Продолжить экспорт?'; 
    'Да|Нет'; 'Да'; 'Нет') == 'Нет'
  Raise(CreateException('ECancelByUser'; 
    'Экспорт не будет выполнен.'; ecInformation))  
endif

// Экспорт.
Object.Environment.SetVar('ExportFolder'; 
  IncludeTrailingPathDelimiter(FolderDialog.Result))
MapC('_a.Export(_a.Versions.Count; ' &
  '__ExportFolder & _a.ID & ".doc"; False)'; Documents)  

ShowMessage('Документы успешно экспортированы.')

 

Вместо заключения

Применять ли подобные приемы в реальной разработке? Это решать разработчику, а не системе. И хорошо, что у него есть выбор.

Исходные тексты всех используемых функций прилагаются в виде пакета разработки.

 

fp.zip (6,04 Кб)

5
Авторизуйтесь, чтобы оценить материал.
2
Дмитрий Тарасов

Очень познавательно. Я так понимаю, это ответ на тему форума "Почему в DIRECTUM нет цикла for?" :)

Андрей Подкин
Я так понимаю, это ответ на тему форума "Почему в DIRECTUM нет цикла for?"

В том числе.

Дмитрий Абрамов

Как ISBuilder работает с рекурсией? Если я не ошибаюсь, то "функциональные" языки умеют компилировать рекурсию в некий оптимизированный безстековый код и могут "проваливаться очень глубоко" в рекурсии. ISBuilder так умеет?

Евгений Кочуров

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

1. Без задействования стека возможен только единственный рекурсивный вызов в теле функции.

2. После рекурсивного вызова в теле функции не должно быть никаких вычислений, влияющих на результат функции.

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

Андрей Подкин
Как ISBuilder работает с рекурсией?

Мягко говоря, не очень хорошо. Очень большие накладные расходы. Пара тройка вызовов работате еще вменяемо, а нормальной рекурсии уже нет (если я правильно помню, в интерпретаторе даже заложено ограничение на количество рекурсивных вызовов).

 

ISBuilder так умеет?

А надо такие навороты? Не проще найти реализацию функционального языка под Microsoft Script Control и спокойно писать на нем?

Константин Белов
в интерпретаторе даже заложено ограничение на количество рекурсивных вызовов

Превышен максимальный уровень рекурсивных вызовов (32 вызова) на ISBL.

Александр Гуртяков

Что то начиналось за здравие, а закончилось за упокой - все таки функциональное программирование это далеко не только работа со списками. Хотя очень бы хотелось видеть реализованные на уровне платформы функции map, range.

Андрей Подкин
Хотя очень бы хотелось видеть реализованные на уровне платформы функции map, range.

А надо это именно для ISBL? Не лучше ли поставить вопрос о поддержке в платформе других языков (имеется ввиду глубоко интегрированной поддержки, просто писать, например, на ActivePython, можно и сейчас).

Александр Гуртяков

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

А вот можно подробнее о последнем, о Active

Александр Гуртяков

А вот можно подробнее о последнем, о ActivePython?

Андрей Подкин
А вот можно подробнее о последнем, о ActivePython?

Вкратце: надо использовать Microsoft Script Control (через COM). Если интересуют подробности, давайте пример задачи и я постараюсь уговорить специалиста, изучавшего этот вопрос, опубликовать материал здесь.

Александр Гуртяков

Задачу вот так вряд ли сходу скажу, но если реально можно для прикладной разработки задействовать мощь другого языка, без потери в производительности, то действительно интересно почитать статью на эту тему.

Андрей Подкин

Тут как раз хотелось бы продемонстрировать возможности на каком-нибудь более-менее реальном решении, а не абстрактом.

Ладно, посмотрим, что можно придумать.

Денис Архипов

было бы интересно посмотреть все таки пример :)

Авторизуйтесь, чтобы написать комментарий