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

    Злые языки утверждают, что функциональные языки программирования — «языки для написания факториалов». Чаще всего так определяют язык 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 Гб ОЗУ, меня получилось следующее:


    Процедура Проблема
    factorial-classic переполнение стека при $n > 10\,000$
    factorial-classic-tco нет ($n = 100\,000$)
    factorial-fold переполнение стека при $n > 10\,000$
    factorial-eval переполнение стека при $n > 8\,000$
    factorial-lazy при $n = 100\,000$ использует раздел подкачки и зависает
    factorial-memoized переполнение стека при $n > 10000$ только при первом запуске
    factorial-memoized-tco при $n > 1\,000$ использует раздел подкачки и зависает
    factorial-do нет ($n = 100\,000$)
    factorial-for нет ($n = 100\,000$)
    factorial-for-each нет ($n = 100\,000$)

    Отсюда, тесты производительности выполнялись при $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 позволил написать нам много вариантов реализации вычисления факториала, используя при этом весьма ограниченный набор примитивов (то самое «минимум средств — максимум впечатлений»). Поэтому, несмотря на почтенный возраст и не слишком широкую распространенность, этот язык всё ещё можно рекомендовать для исследовательского программирования: похоже, на нем можно реализовать всё что угодно и каким угоднокаким удобно) способом.

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 17

      +3
      Злые языки утверждают, что функциональные языки программирования — «языки для написания факториалов».

      Возмутительная ложь! Ещё для написания чисел Фибоначчи, а также метациклических интерпретаторов!


      Кроме того, в Scheme просто волшебно правильная макросистема. Злые языки скорее будут попирать его за динамическую типизацию. Впрочем, JavaScript тоже динамически типизирован. И если бы всё сложилось бы немного по-другому, то в браузерах исполнялась бы именно Схемка.

        0
        Было бы интересно пофантазировать на эту тему…
          +1

          Да, макросистема в Scheme восхитительна! Справедливости ради надо отметить, что гигиенические макросы имеются в Rust, преемственность заметна. Но, конечно, там макросы гораздо сложнее — из за куда более богатого синтаксиса языка.


          Динамическая типизация — не всегда зло. В скриптах, в сравнительно небольших проектах динамическая типизация бывает удобной и способствует краткости. Существует диалект Scheme со статической типизацией — Typed Racket. Кроме того, некоторые реализации Scheme поддерживающее статическую типизацию, например, Chicken Scheme.


          Современный JS по-своему хорош, гибок и выразителен. Впрочем, есть и компиляторы Scheme в JS. Сам пробовал писать компилятор Scheme в JS на Scheme же, получается достаточно кратко и красиво: лексический и синтаксический анализ не требуется, все действия выполняются со списками и символами (symbol).


          Наверное, Scheme (или его диалект) для Web-программирования был бы удобен. Тут важно согласовать функциональный подход языка и объектную моделью документа.

          0
          Предлагаю записать в виде лямбды(это лисп):
          > set 'fct (lambda (n f) (if (zerop n) 1 (* n (funcall f (- n 1) f))))

          И вызывать вот так
          > funcall fct 100 fct
            0

            В Scheme подход к функциям несколько отличается от Common Lisp. Не являясь знатоком последнего, могу предположить, что такое определение соответствует определению функции (процедуры) в Scheme, записанному «без сахара»:


            (define f (lambda (n) ...)
            0
            А производительность замерялась с холодного старта? Что-то времена GC уж очень большие.
            На SBCL с примерно той же реализацией функций GC на первом запуске довольно много времени забирает, но уже на втором — раз в 10 меньше, чем код расчёта (который выполняется, как и у вас в таблице, за порядка 13 мс для 8000 и порядка 1,5 секунды для 100 000).
              0

              Определение в REPL, затем несколько запусков подряд. Возможно, вы правы

              +1
              Можно ещё добавить версию с продолжениями.
                +2
                О, ну если упарываться, то можно добавить и вариант с хвостовой рекурсией без define и set!:

                (let ((fact (lambda (n)            
                              (((lambda (f)
                                  ((lambda (g) (g g))
                                   (lambda (g)
                                     (f (lambda a (apply (g g) a))) ) ) )
                                (lambda (rec)
                                  (lambda (n prod)
                                    (if (= n 0)
                                        prod
                                        (rec (- n 1) (* n prod)) ) ) ) )
                              n 1 ) )))
                  (display (fact 5))
                  (newline) )
                
                  +3
                  О, это ж комбинатор неподвижной точки! Да, тоже хорошо бы в статье смотрелся.
                0
                Спасибо — очень интересная статья. Но, к сожалению, не могу указать точные ссылки на книги, где авторитетные авторы утверждали, что факториал — неподходящий пример для рекурсии. М.б. в качестве примера стоит взять ханойские башни? Или что-то подобное. Правда не уверен, что там будет возможно такое разнообразие решений.
                  0
                  И факториале, и ханойских башнях используется метод математической индукции. Разница в чём?
                  –2

                  Пц синтаксис. Scheme вижу впервые. Надеюсь, и в последний раз.

                    +1

                    У языков семейства Lisp фактически нет синтаксиса — пользователь сразу пишет AST. (Ну а для записи AST достаточно простой рекурсивно-регулярной грамматики.)


                    Хорошо это или плохо — Holy War: лично я принадлежу к тем, кому нравятся языки с более богатым синтаксисом, другие же предпочитают «AST прямо в мозг».

                      +2

                      Синтаксис scheme божественнен!

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

                        «AST прямо в мозг» хорошо тогда, когда вам надо с ним работать. Собственно, это и обеспечивает удобство символьных вычислений в ЯП семейства Лисп. Читать код на них, особенно бегло, особенно если не практикуешься в этом регулярно — трудно. Пробовали реализовывать «сахар» в стиле Haskell, получалось наглядно (что-то вроде псевдокода в функциональном стиле). Но, конечно, с AST его все равно приходилось работать как со списком символов.
                        +1
                        Здесь не хватает ссылки полностью раскрывающей тему факториалов и способов их получения
                        www.cs.utexas.edu/~cannata/cs345/Class%20Notes/10%20Haskell%20Programmer%20Evolution.html

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое