Давид Кистаури: функциональное программирование

Y-комбинатор

Y-комбинатор — один из комбинаторов неподвижной точки — ключ к пониманию рекурсии и подсказка к тому, зачем вообще нужно функциональное программирование и в чем его особенность. В книгах объясняется сложно, поэтому я много раз перечитал, записал каждый шаг и прокоментировал его, чтоб самому понять. А потом отредактировал текст и делюсь со всеми.

Рассмотрим Y-комбинатор на примере Scheme — диалекта Lisp. Тестовой функцией будет length, которая измеряет длину списка. Для начала объясню как рабоатет сама функция.

(define length
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l)))))))

С каждым блоком кода открываются скобки, а потом они закрываются. Почти как {} в JavaScript. Разберем по строкам.

define length — define определяет называние функции, как если бы мы написали function length в JavaScript или def length в Python.
lambda (l) — определяет безымянную функцию и её аргументы. В данном случаи аргумент один — l — в функцию мы передадим список. Передавая безымянную функцию в первую строку, мы определяем для нее имя. Первые две строки — аналог function length(l) в JavaScript и def length(l) в Python.
cond — начало условия. Это как if, только туда передается много строк условий и действий подряд и в конце else.
В каждой следующей строке после cond идет блок кода с условием и действием. Как ((null? l) 0). Читается так: ((если это) то это). А null? — это функция, которая проверяет список, который мы ей передаём, на пустоту.
add1 — функция, которая добавляет 1; её надо писать самостоятельно. cdr — функция, которая возвращает список, который мы передаём, но без первого элемента.

В общем виде функция работает так:

проверяем список на пустоту,
если пустой — возвращаем 0, если нет, идем дальше,
добавляем 1 к рекурсивному запуску фукнции,
запускаем функцию со списком, который меньше на один элемент,

Пока список не будет пуст, мы будем добавлять единицу, когда он останется пуст, вернётся 0 из ((null? l) 0) и шаг за шагом в обратном направлении добавится по единице.

Если непонятно, то лучше пропустить какой-нибудь список через фукнцию. Например (lisp is great). Функция будет запускаться рекурсивно, удаляя по одному элементу из начала: (lisp is great), (is great), (great), (). Теперь можно приступать к комбинатору неподвижной точки.

Сперва попробуем избавиться от define. Функция будет безымянной. В Lisp есть синтаксис мгновенного объявления и вызова функции, как и в JavaScript. В скобки передается безымянная лямба-функция и следом аргумент:

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 eternity)

Две лямбды означают, что мы создаём функцию, которая возвращает функцию, готовую принять другой аргумент. eternity просто пустышка, которая подставляется вместо аргумента. Такая функция будет очень похожа на length, но рекурсивного вызова не будет, потому что у функции нет имени и мы не знаем, как ее вызвать. Но если передать туда пустой список, то сработает первое условие — (null? l) и функция вернёт 0. То есть для пустого списка всё ок.

((lambda (f)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (f (cdr l))))))) ; здесь будет вторая фукнция
 ((lambda (g)
    (lambda (l) ; здесь будет cdr l
      (cond
        ((null? l) 0)
        (else (add1 (g (cdr l))))))) ; здесь будет eternity
  eternity))

Теперь передадим вместо eternity другую функцию. В первую функцию передается вторая, а в неё — eternity. Теперь мы можем передать список с одним элементом. Выполнится else, вызовется вторая функция, которая такая же, как и первая, и там мы уже остановимся. А можно так добавлять бесконечно. Но код будет не универсальным, а писать так много неудобно. Перейдем к другому определению функции.

((lambda (mk-length) ; (1)
   (mk-length eternity))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

Теперь у нас есть отдельная функция (первая), которая возвращает похожую на length функцию. Функция (2) попадет в лямбду (1) как аругмент mk-length. Внутри происходит опять объявление с вызовом. В функцию (2) подставляется eternity вместо length.

Теперь повторим прошлый код с новым синтаксисом подстановки, передадим в функцию (2) вместо eternity саму функцию.

((lambda (mk-length) ; (1)
   (mk-length
     (mk-length eternity)))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

Здесь мы передаем eternity в функцию, как и в прошлый раз, и всю эту конструкцию снова передаем в функцию. Уберем eternity.

((lambda (mk-length) ; (1)
   (mk-length mk-length))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

Функция (2) передается в функцию (1) и получает там имя mk-length, а потом передается в себя в строке (mk-length mk-length). Вернем eternity, но теперь в другое место, положим его прямо внутрь функции.

((lambda (mk-length) ; (1)
   (mk-length mk-length))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((length eternity) (cdr l))))))))

Теперь опять заменим eternity на функцию, мы уже делали так.

((lambda (mk-length) ; (1)
   (mk-length mk-length))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((length length) (cdr l))))))))

В функциональном программировании используется прием eta-reduction. Он позволяет заменить (lambda (x) (function x)) на function, потому что в первом варианте мы передаем аргумент в функцию, которая находится в ожидании, во втором варианте функция также ждет аргумент, который можно ей передать. Если мы передадим любое число в оба варианта, то функция получит число и там, и там.

Сделаем обратную замену: подставим вместо (length length) функцию (lambda (x) ((length length) x)). Здесь (length length) просто функция.

((lambda (mk-length) ; (1)
   (mk-length mk-length))
 (lambda (length) ; (2)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((lambda (x) ((length length) x))
                    (cdr l))))))))

Вытащим новую конструкцию за функцию.

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length) ; новая функция-обертка
   ((lambda (length) ; подстановка аргумента
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))
    (lambda (x) ; аргумент
      ((mk-length mk-length) x)))))

На 4 строке появились двойные скобки: это значит, что мы в функцию передаем аргумент. Выделенный фрагмент — прошлая функция, куда мы передаем последние две строки. Если подставить (lambda (x) ((length length) x)) вместо length в четвертой строке, то получим функцию из предыдущего блока. Всю эту конструкцию мы обернули в новую фукнцию.

Вытащим выделенный фрагмент в отдельный аргумент.

((lambda (le)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x)
            ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

Выделенный фрагмент — функция, похожая на изначальный length. Она передается в первую функцию как le. Остальное — часть, которая выполняет рекурсию. Её можно определить с помощью define.

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

Здесь le — функция, которую мы хотим вызывать рекурсивно, x — ее аргумент, а f — внутреннее имя функция для применения функции к себе. Эта часть называется Y-комбинатор. Их существует несколько видов, но этот основной. Более сложное, но не менее интересное, объяснение есть в книге The Little Schemer, а еще один вид комбинатора есть во второй части — The Seasoned Schemer. Это интересные и веселые книги по функциональному программированию, которые стоит прочитать навичкам в этом разделе.

18 мая 2020код функциональное программирование