Сколькими способами можно записать факториал на Scheme?19.01.2019 16:17

Злые языки утверждают, что функциональные языки программирования — «языки для написания факториалов». Чаще всего так определяют язык Haskell, мы же начнем с того функционального языка, который сильно повлиял и на Haskell, и на подмножество средств для функционального программирования многих других языков — язык Scheme. По-крайней мере, map и for-each, filter и reduce, а так же apply и eval пришли в наши любимые языки программирования если не именно из Scheme, то в том числе и оттуда.

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

У меня получилось 10 вариантов записи определений функций, которые можно свести к 3 основным способам вычисления: традиционному линейно-рекурсивному вычислительному процессу, итерации, генерации последовательности чисел с последующей сверткой умножением. Предлагаю рассмотреть эти варианты подробнее. Попутно мы рассмотрим: оптимизацию хвостовой рекурсии, функции высших порядков и метапрограммирование, отложенные вычисления, бесконечные списки, мемоизацию, способ создать статическую переменную в Scheme и гигиенические макросы.

Для экспериментов был использован старый добрый диалект Scheme R5RS и популярный принцип изобразительного искусства «минимум средств — максимум впечатлений».

Все примеры на Scheme были подготовлены в среде DrRacket 6.2 в режиме R5RS. Замеры времени выполнения были выполнены в Guile 2.0 в среде ОС OpenSUSE Leap 15.

Для начала можно взять рекурсивное определение факториала и просто переписать формулу на Scheme:

(define (factorial-classic n)
  (if (zero? n) 1 (* n (factorial-classic (- n 1)))))

Получилось определение функции (в терминах Scheme — процедуры, хотя по-сути она является функцией) для вычисления факториала, которое можно увидеть в бесчисленном множестве руководств по программированию, начиная с бессмертной книги Х. Абельсона и Д. Сассмана «Структура и интерпретация компьютерных программ».

Читать и понимать этот код можно так: факториал $n$ есть $1$ если $n = 0$ , иначе — $n \cdot (n-1)!$ . Таким образом, этот код соответствует рекурсивному определению факториала, принятому в математике. Единственное, мы не проверяем принадлежность $n$ неотрицательным числам.

Будучи рекурсивным, код выше содержит очевидное ограничение на величину $n$ : на стеке будут накапливаться данные рекурсивных вызовов, пока $n$ не достигнет 0. Это может вызвать переполнение стека при больших $n$ .

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

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

(define (factorial-classic-tco n)
  (define (iteration product counter)
    (if (> counter n)
        product
        (iteration (* product counter)
                   (+ counter 1))))
  (iteration 1 1))

Этот код является расхожим примером, и, начиная с книги «Структура и интерпретация компьютерных программ», именно на нем обычно объясняют оптимизацию хвостовой рекурсии.

Это была классика. Но Scheme — сама гибкость, нельзя ли записать то же самое принципиально иначе? И, желательно, еще короче? Например, согласно записи $n! = 1 \cdot 2 \cdot 3 \cdot~\cdots ~\cdot n$ сформировать последовательность от $1$ до $n$ (или от $n$ до $1$ ) и затем свернуть её умножением? Благо, в Scheme это сделать достаточно просто благодаря встроенной процедуре apply, которая применяет процедуру с произвольным числом аргументов к списку:

(define (iota n)
  (define (iteration sequence i)
    (if (> i n)
        sequence
        (iteration (cons i sequence) (+ i 1))))
  (iteration '() 1))

(define (factorial-fold n) (apply * (iota n)))

Scheme славится своим удобством для символьных вычислений в силу «единства кода и данных» (так иногда говорят о языках семейства Лисп). Используем эту особенность: сформируем выражение для вычисления факториала числа $n$ , а затем его вычислим:

(define (factorial-eval n)
  (define expression `(* ,@(iota n)))
  (eval expression (interaction-environment)))

Символ «обратная одиночная кавычка» означает квазицитирование (quasiquotation). Без квазицитирования получение выражение для последующего вычисления можно было бы получить с помощью кода (cons '* (iota n)). Одиночная кавычка (цитирование, quotation) означает, что * надо подставить в выражение именно как имя (символ), а не соответствующее ему значение (здесь — процедуру). Так, при $n=3$ получим (* 3 2 1). Этот список является выражением на языке Scheme. Его значение может быть выполнено в подходящем окружении, лучше всего — в окружении (interaction-environment), содержащем встроенные процедуры и процедуры, определенные нами в программе. Собственно, это мы и делаем в теле factorial-eval.

Scheme поддерживает отложенные вычисления. Haskell, который испытал значительное влияние Scheme, использует ленивую модель вычислений, т.е. не вычисляет значение выражения до тех пор, пока результат этих вычислений не будет востребован. Это позволяет иметь в программах такие своеобразные структуры данных, как бесконечные списки. Если из них брать только часть, необходимую для дальнейших вычислений, программа не будет зацикливаться:

ghci> take 4 [1 ..]
[1,2,3,4]

Выражение [1 ..] генерирует бесконечный список целых чисел. Выражение take 4 получает из этого списка 4 первых элемента. Поскольку последующие элементы списка остаются невостребованными, они не вычисляются.

На Haskell получение $n!$ из бесконечного списка можно записать так:

factorials :: [Integer]
factorials = next 0 1
  where next n fact = let n' = n + 1 in fact : next n' (fact * n')

factorial :: Integer -> Integer
factorial n = factorials !! fromIntegral n

ghci> take 7 $ factorials
[1,1,2,6,24,120,720]
ghci> factorial 6
720

Используя пару форм Scheme delay/force попробуем сделать нечто подобное. Ключевое слово delay создает обещание вычислить значение выражения. Ключевое слово force распоряжается осуществить эти вычисления, полученное значение вычисляется и запоминается. При повторном обращении новых вычислений не производится, а возвращается значение, вычисленное ранее.

В языках семейства Лисп списки строятся из пар. Для того, чтобы конструировать бесконечные списки, введем тип «ленивая пара» — пара, в которой первый элемент — вычисленное значение, а второй — обещание вычислить значение. Для этого нам надо дополнить «святую троицу» языков семейства Лисп (cons, car, cdr) их ленивыми версиями:

(define-syntax lazy-cons
  (syntax-rules ()
    ((_ first second) (cons first (delay second)))))

(define lazy-car car)

(define (lazy-cdr lazy-pair) (force (cdr lazy-pair)))

Конструктор ленивой пары lazy-cons реализован в виде макроса. Это сделано для того, чтобы избежать вычисления значения второго элемента пары при ее создании.

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

(define (lazy-list-ref lazy-list index)
  (if (zero? index)
      (lazy-car lazy-list)
      (lazy-list-ref (lazy-cdr lazy-list) (- index 1))))

(define (generate-factorials)
  (define (next n n!)
    (define n+1 (+ n 1))
    (lazy-cons n! (next n+1 (* n! n+1))))
  (next 0 1))

Здесь n! и n+1 — имена переменных. В Scheme, по-сравнению с другими языками, существует очень немного символов, которые нельзя использовать в идентификаторах.

Обратите внимание, что генератор бесконечного списка generate-factorials не содержит выхода из рекурсии. Тем не менее, он не будет зацикливаться, так как при его вызове будет вычисляться только голова списка, хвост же будет представлен обещанием вычислить значение.

Теперь можно определить $n!$ как получение $n$ -го элемента списка факториалов:

(define lazy-factorials (generate-factorials))

(define (factorial-lazy n) (lazy-list-ref lazy-factorials n))

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

Кстати, код на Scheme весьма близок к таковому на Haskell. Так, оператор получения !! примерно соответствует процедуре lazy-list-ref, конструктор списка : соответствует lazy-cons. Соответствует примерно, потому что Haskell, хотя и исповедует ленивую модель вычислений, однако, в отличие от delay/force в Scheme, вычисленные значения не запоминает.

Кстати, для повышения производительности можно применить запоминание уже вычисленных значений — мемоизацию. Будем хранить вычисленные значения в ассоциативном списке, в котором ключами будут числа, а значениями — их факториалы. При вызове, просмотрим список на предмет уже вычисленных значений. Если значение присутствует в списке, будем возвращать это сохраненное значение. Если значение в списке отсутствует, будем вычислять его, помещать в список, и только потом возвращать. Чтобы этот список всегда находился при вызываемой функции, а не в глобальном окружении, разместим его в статической переменной:

(define factorial-memoized
  (let ((memo '()))
    (lambda (n)
      (let ((memoized (assq n memo)))
        (if memoized
            (cadr memoized)
            (if (zero? n)
                1
                (let ((computed (* n (factorial-memoized (- n 1)))))
                  (set! memo (cons (list n computed) memo))
                  computed)))))))

Статические переменные в Scheme

Код вида

(define proc
  (let ((static-var initial-value))
    (lambda args ...)))

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

(define count
  (let ((n 0))
    (lambda () (set! n (+ n 1)) n)))

В одной сессии интерпретатора первый вызов (count) вернет 1, второй — 2, третий — 3 и т.д. Как это работает?

Без синтаксического сахара определение count выглядит так:

(define count
  ((lambda (n)
     (lambda () (set! n (+ n 1)) n)) 0))

Таким образом, с именем count связана процедура без аргументов (lambda () (set! n (+ n 1)) n), в которую свободно входит n. Получается, что n определена во внешнем окружении по отношению к (lambda () (set! n (+ n 1)) n), что означает, что значение n будет сохраняться между вызовами count. Значение n инициализируется нулем при запуске программы, так как (lambda (n) ...) применяется к аргументу 0. Поэтому n отсутствует в глобальном окружении, но всегда доступно из count.

Данная реализация также обещает прирост производительности при неоднократном вычислении факториалов различных чисел в одной сессии интерпретатора.

Разумеется, здесь также возможна оптимизация хвостовой рекурсии:

(define factorial-memoized-tco
  (let ((memo '()))
    (lambda (n)
      (define (iteration product counter)
        (cond
          ((> counter n) product)
          (else
           (set! memo (cons (list counter product) memo))
           (iteration (* product counter)
                      (+ counter 1)))))
      (iteration 1 1))))

«Зачем эти танцы с бубном?», — может сказать читатель. На императивных языках программирования то же самое пишется просто — через цикл, работает быстро и без лишних затрат памяти. В Scheme есть подмножество для императивного программирования, есть в нем и средство для организации циклов — специальная форма do. Процедура для вычисления факториала, записанная с её помощью, может выглядеть так:

(define (factorial-do n)
  (define product 1)
  (do ((i 1 (+ i 1))) ((> i n) product)
    (set! product (* product i))))

Конструкция do — достаточно универсальная, и именно поэтому — не слишком удобочитаемая. Не лучше ли организовать свой собственный цикл в императивном стиле? В этом помогут макросы:

(define-syntax for
  (syntax-rules ()
    ((_ (variable init test step) . body)
     (let loop ((variable init))
       (if test
           (begin
             (begin . body)
             (loop step)))))))

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

Определение факториала с использованием for:

(define (factorial-for n)
  (define product 1)
  (for (i 1 (<= i n) (+ i 1))
    (set! product (* product i)))
  product)

Как это работает

В данном примере выражение (for (i 1 (<= i n) (+ i 1)) (set! product (* product i))) будет сопоставлено с образцом (_ (variable init test step) . body) синтаксического правила. Будут выполнены следующие подстановки:

for  →  _
i  →  variable
1  →  init
(<= i n)  →  test
(+ i 1)  →  step
(set! product (* product i))  →  body

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

(define (factorial-for n)
  (define product 1)
  (let loop ((i 1))                                 ; этот фрагмент
    (if (<= i n)                                    ; кода
        (begin (begin (set! product (* product i))) ; сформирован
               (loop (+ i 1)))))                    ; макросом for
  product)

Возможен еще один вариант, внешне похожий на императивный цикл for — со встроенной процедурой for-each:

(define (factorial-for-each n)
  (define product 1)
  (for-each (lambda (i) (set! product (* product i))) (iota n))
  product)

Велик и могуч язык Scheme! А что с производительностью?

Для замеров производительности воспользуемся GNU Guile — в этой среде можно замерить время вычисления выражения наиболее просто.

Guile работает следующим образом: компилирует исходный текст программы в байт-код, который затем выполняется виртуальной машиной. Это — только одна из реализаций и один из нескольких возможных способов выполнения программы на Scheme, существуют и другие: Racket (использует JIT-компиляцию), Chicken Scheme (использует «честную» интерпретацию или компиляцию в подмножество C) и т.д. Очевидно, что и ограничения, и производительность программ в этих средах могут несколько отличаться.

Замеры будем производить при некотором значении $n$ . Каким должно быть это $n$ ? Таким, с каким наибольшим $n$ смогут «справиться» предложенные варианты. С настройками Guile 2.0 по-умолчанию, на ПК с Intel Core i5 и 4 Гб ОЗУ, меня получилось следующее:

Отсюда, тесты производительности выполнялись при $n = 8\,000$ . Результаты представлены в таблице ниже, где $t_{run}$ — время выполнения, $t_{GC}$ — время работы сборщика мусора в секундах.
Для всех процедур, кроме ленивых и мемоизованных, указаны наименьшие значения времени выполнения и соответствующее ему время работы сборщика мусора, полученные по итогам трех запусков при $n = 8\,000$ .
Для мемоизованных и ленивых процедур указано время выполнения первого вызова, далее — меньшее из трех вызовов.

Процедура	$t_{run}$ , с	$t_{GC}$ , с	Примечания
`factorial-classic`	0,051	0,034
`factorial-classic-tco`	0,055	0,041
`factorial-fold`	0,065	0,059
`factorial-eval`	0,070	0,040
`factorial-lazy`	0,076	0,036	первый вызов
`factorial-lazy`	0,009	—	последующие вызовы
`factorial-memoized`	0,077	0,041	первый вызов
`factorial-memoized`	0,002	—	последующие вызовы
`factorial-memoized-tco`	0,077	0,041	первый вызов
`factorial-memoized-tco`	0,002	—	последующие вызовы
`factorial-do`	0,052	0,025
`factorial-for`	0,059	0,044
`factorial-for-each`	0,066	0,042

У нас есть 4 варианта, которые могут работать с большими $n$ . При $n = 100\,000$ они имеют следующие времена вычисления и сборки мусора:

Процедура	$t_{run}$ , с	$t_{GC}$ , с
`factorial-classic-tco`	8,468	6,628
`factorial-do`	8,470	6,632
`factorial-for`	8,440	6,601
`factorial-for-each`	9,998	7,985

Можно видеть, что при не слишком больших $n$ наиболее быстрым и, одновременно, самым коротким и оказывается первый. Этот же вариант наиболее полно соответствует математическому определению факториала. Вариант с оптимизацией хвостовой рекурсии ему не сильно уступает в производительности. Оба этих варианта являются идиоматическими, рекомендованными авторами языка. Вывод во многом очевиден: если не оговорено иное, подход, являющийся для языка «типовым», является предпочтительным, по-крайней мере, для первой реализации алгоритма или метода.

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