1 Кубенский А.А. Функциональное программирование. Глава 6. Введение в редукцию графов. Глава 6. Введение в редукцию графов 6.1. Представление лямбда-выражений в виде графов Будем исходить из представления программ в виде структур данных расширенного лямбда- исчисления. Наша основная задача – корректно представить концепцию разделения переменных. Константа c.c Примитивная функция f.f Лямбда-выражение λx.E. λ xE Применение функции E 1 E E1E1 E2E2 Применение конструктора C x y z. C xzy

2 Кубенский А.А. Функциональное программирование. Особенности представления некоторых типов выражений. Представление лябда-выражений в виде графов (продолжение). Глава 6. Введение в редукцию графов. Частичное применений примитивных функций и конструкторов : lst : 1 lst : 1lst : : 1 или : 1t λ t

3 Кубенский А.А. Функциональное программирование. Представление лямбда-выражений в виде графов (продолжение). Глава 6. Введение в редукцию графов. Блоки let x = E1 in E2 и letrec x1 = E1;... xk = Ek in E. let x = E1 in E2(λx.E2) E1 E2 λ E1E1 letrec x1 = E1;... xk = Ek in E – моделируется с помощью циклических графов.

4 Кубенский А.А. Функциональное программирование. let twice = λf.λx.f (f x) in twice (λx.+ x 1) 2 Пример представления выражения в виде графа. Глава 6. Введение в редукцию графов. (λf.λx.f (f x)) (λx.+ x 1) 2 2 λ x λ f @ +x t

5 Кубенский А.А. Функциональное программирование. Нахождение самого левого из самых внешних редексов: проход по «левому гребню» графа. Правила редукции графов. Глава 6. Введение в редукцию графов. 2 x succ Копирование тела лямбда-выражения. succ Подстановка аргумента вместо свободных вхождений переменной лямбда-выражения в тело. Замещение в результатом «вычислений». Некоторые особенности этой процедуры: Тело лямбда-выражения копируется, чтобы его можно было переиспользовать; «мусор» удаляется Подстановка аргументов производится с помощью установки ссылок; тем самым производится эффективное разделение переменных Результат редукции замещает редуцируемое выражение, тем самым все ссылки на этот результат будут иметь новое значение

6 Кубенский А.А. Функциональное программирование. Пример редукции графов. Глава 6. Введение в редукцию графов. (λf.λx.f (f x)) (λx.+ x 1) 2 2 λ x λ f @ +x 1

7 Кубенский А.А. Функциональное программирование. Глава 6. Введение в редукцию графов. @ + x 1 Пример редукции графов. (λf.λx.f (f x)) (λx.+ x

8 Кубенский А.А. Функциональное программирование. δ-редукция в графовом представлении Глава 6. Введение в редукцию графов. Если при проходе по левому гребню находим константу, то это – примитивная функция 2 - сначала выполняем редукцию всех строгих аргументов; - потом формируем результат в соответствии с правилами этой примитивной функции; - результат замещает собой * 6 12

9 Кубенский А.А. Функциональное программирование. Общий алгоритм редукции графов (пока без учета рекурсии) Глава 6. Введение в редукцию графов. while (выражение не находится в СЗНФ) { спуск от корня по левому гребню до первой вершины, отличной switch (тип вершины) { case (примитивная функция): if (число аргументов k > числа выражение находится в СЗНФ; else { редуцировать все строгие аргументы; сформировать результат согласно правилам примитивной функции; заменить этим результатом; } break; case (λ-вершина): if (выше выражение находится в СЗНФ; else { создать копию тела с подстановкой (разделяемого) аргумента вместо свободных вхождений переменной λ-выражения; подставить результат вместо вершины редекса вверх по гребню); } break; default: // константа-значение или конструктор if (выше выражение находится в СЗНФ; else ошибка типа ! break; } }

10 Кубенский А.А. Функциональное программирование. Использование вершин-синонимов Глава 6. Введение в редукцию графов. При выполнении редукций есть одна проблема, связанная с копированием: в теле функции переменная может быть в корне. Тогда вместо подстановки ссылки на аргумент придется делать копию вершины, представляющей аргумент. x 1 2 Можно вместо копирования вершины создавать «вершину-синоним» - «прозрачную» по ссылкам. Θ При прохождении вершины-синонима можно оптимизировать их количество, убирать двойные синонимы, заменять ссылки на синоним ссылками на саму вершину.

11 Кубенский А.А. Функциональное программирование. Использование вершин-синонимов (продолжение) Глава 6. Введение в редукцию графов. Аналогичная проблема возникает при применении примитивных функций-селекторов, которые не преобразуют, а просто выдают аргумент или его часть (например, head или : : 1 nil head (cons (head (cons 1 nil)) nil) Θ