По счастливой случайности у меня в распоряжении оказались сразу три вещи: книжка Practical Common Lisp, пробник Corman Lisp 3.0 и свободное время. До этого серьезно Лиспом я никогда не занимался, так что, как честный человек, я просто обязан был написать факториал. Желательно восемь раз. Надо сказать, занятие это оказалось намного увлекательнее, чем выглядело в начале.
Итак, вот все восемь вариантов.
1. Поднадоевший
;;; recursive
(defun f1 (n)
(if (= n 0)
1
(* n (f1 (- n 1)))))
Тут все просто. Объявляем функцию состоящую из одного ветвления и рекурсивного вызываем ее же. Ну да, в Лиспе немного непривычный префиксный синтаксис, но про это и так все знают. Единственное, что тут действительно может быть неочевидным — это if. У него первый аргумент условие, второй — собственно тело, а третий — тело else. Без слова else, чего непривыкшему глазу может и не хватать.
Проблема в рекурсивном факториале одна — он рекурсивный. Google Common Lisp Style Guide рекомендует предпочитать итерацию рекурсии и на то есть одна хорошая причина. Стандарт CL не гарантирует оптимизации хвостовой рекурсии. На практике она, конечно же, поддерживается реализациями, но не всеми. Для сохранения портабельности лучше не рисковать.
2. Поднадоевший еще в школе
;;; iterative
(defun f2 (n)
(let
((ret 1))
(loop for i from 2 to n do
(setq ret (* ret i)))
ret))
Тут появляются две новые конструкции и одна функция. Конструкция let позволяет объявить в локальном контексте переменные и делать с ними все что угодно. Первый аргумент — список инициализаций, остальные — все что угодно. Результат последнего аргумента будет возвращен из конструкции.
Конструкция loop намного интересней и разнообразней. Это макрос со своим микро-языком, позволяющий делать самые разнообразные циклы на все случаи жизни. Швейцарский нож программиста, от которого в данном примере нам нужен только штопор. Мы указываем переменную цикла предлогом for. Используя предлоги from и to устанавливаем диапазон значений этой переменной. Глаголом do запускаем на исполнение то, что после do стоит.
Переменные в Лиспе читаются как и везде по имени. А пишутся через специальные функции. Там все достаточно интересно с переменными, лучше почитать про них отдельно. Сейчас нас интересует просто возможность что-то куда-то записать, и setq для этого подходит достаточно хорошо. setq пишет в первый аргумент то, что считается во втором.
Этот факториал чуть-чуть получше, но все равно какой-то скучный. Да и с подвохом. Сложность его вроде как O(n), но числа в лиспе не нативные, как int32 или double, а рациональные. Причем, и числитель и знаменатель — условно бесконечные целочисленные. То есть чем больше число, тем дольше оно считается. Поэтому O(n) не O(n), а оптимизировать расчет не помешало бы.
3. Оптимизированный
;;; prime based
(defconstant +primes-1000+ '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997))
(defun f3 (n)
(defun pow-of (n q)
(let ((d (truncate (/ n q))))
(if (= d 0)
0
(+ d (pow-of d q)))))
(let
((res 1))
(loop for p in +primes-1000+ do
(progn
(when (> p n) (return))
(setq res (* res (expt p (pow-of n p))))))
res))
Допустим, у нас есть достаточно большой список простых чисел. Его никто трогать не будет, так что определим его как константу. В CL константы принято выделять плюсами. Вообще, нечеловечески гибкий синтаксис в Лиспе постоянно приводит к появлению разных человеческих соглашений, поэтому для чтения чужого кода просто знать язык мало. Надо еще знать, что означают всякие плюсики, звездочки и знаки вопроса, например.
Теперь подумаем, что такое факториал. Произведение, ок. То есть, как любое произведение, его можно разложить на множители. А множители — на простые множители. Разложим, например, факториал 6.
6! = 2*3*4*5*6 = 2 * 2 * 2 * 2 * 3 * 3 * 5
В нем 4 двойки, 2 тройки и пятерка одна. Две тройки понятно откуда взялись. Каждое третье число натурального ряда имеет в себе хотя бы одну. 6/3 = 2.
Четыре четверки взялись примерно оттуда же. Каждое второе число имеет в себе одну двойку. А каждое второе из этих вторых — еще одну. 6/2 = 3, 3 / 2 = 1, 3 + 1 = 4.
Ну и пятерка тут одна как была, так и есть.
То есть разложить факториал на простые множители несложно. Факториал содержит в себе все простые числа, которые не превышают подфакториальное значение: каждое сколько-то раз. Чтобы найти сколько именно раз, надо делить подфакториальное значение на каждое простое до тех пор, пока есть что делить, и складывать результат. Вложенная функция pow-of как раз этим и занимается. Ей помогает truncate, который отсекает целую часть от результата деления. Числа-то рациональные, так что без него ничего не получится. А вот называется она pow-of, потому что для расчета факториала как раз и надо собрать его из простых чисел возведением каждого в соответствующую степень.
Этим занимается остальное тело f3. Тут loop уже с другими предлогами и работает немного по-другому. in присваивает переменной p все значения из списка +primes-1000+ подряд. do все еще выполняет аргумент после себя, но нам уже не хватит одной команды, так что мы используем конструкцию progn. Очень простая и понятная конструкция, она просто выполняет подряд все что мы запишем после нее в список. Можно представить ее себе как let без переменных.
Далее when. Это тоже макрос и тоже создан для удобства. if хочет чтобы ему дали два аргумента: собственно тело и тело для else, when довольствуется одним только собственным телом, но работает точно так же. Очень легко читается.
return организовывает выход из цикла. Вообще в CL можно выходить из чего угодно используя разные виды return, но сейчас нам из цикла выйти вполне достаточно.
expt — это просто возведение в степень.
Такой способ работает быстрее предыдущего, но имеет серьезный дефект. Что такое «достаточно большой список простых чисел»? Достаточно большой для чего? Раз уж мы все равно храним его в памяти, не проще ли хранить там же сразу посчитанные факториалы и вообще ничего не считать? Конечно проще.
4. Тупой
Вооружившись топором и безрассудством, можно написать следующее решение:
(defun f4 (n)
(cond
((= n 0) 1)
((= n 1) 1)
((= n 2) 2)
((= n 3) 6)
((= n 4) 24)
((= n 5) 120)
((= n 6) 720)
((= n 7) 5040)
((= n 8) 40320)
((= n 9) 362880)
((= n 10) 3628800)
((= n 11) 39916800)
((= n 12) 479001600)
((= n 13) 6227020800)
((= n 14) 87178291200)
((= n 15) 1307674368000)
((= n 16) 20922789888000)
((= n 17) 355687428096000)
((= n 18) 6402373705728000)
((= n 19) 121645100408832000)
((= n 20) 2432902008176640000)))
Очевидно, cond — это просто такой макрос, который позволяет писать сразу много when без лишних букв. Не будем на нем останавливаться.
Зато остановимся на 21 члене последовательности. 22 член попросту не влезет в int64, поэтому в языках с нативными типами, как правило, и особого смысла считать его нет. Для Лиспа это, конечно, не существенно, но надо где то же и остановиться, почему бы не здесь.
Такое решение, обладая очевидными недостатками, провоцирует на хорошее: зачем писать вот это вот зубило руками, если можно писать его автоматически?
Самый тупой способ: написать программку, которая выведет f4 в консоль, и скопировать результат из консоли. Пожалуйста:
;;; console meta
(progn
(format t "(defun f4 (n)~%~T(cond~%")
(loop for i from 0 to 20 do
(format t "~T~T((= n ~D) ~D)~%" i (f3 i)))
(format t "))~%")
NIL)
Тут появляется format. format — это функция форматированного вывода в куда-нибудь. Когда «куда-нибудь» задан как t, это по умолчанию стандартное устройство вывода. Еще можно писать в поток и строку, но об этом позже.
В CL используются собственные ескейп-последовательности. Самые ходовые: ~% — конец строки, ~T — табуляция. Для того, чтобы вставить в форматируемую строку, например, число, достаточно в строке написать ~D, а к вызову format приписать само значение. Язык формата очень широкий, включает в себя всевозможные размеры, отступы, выравнивания. Впрочем, пока нам многого от него не надо. Достаточно просто получить кусок кода в виде строки. С разметкой, но без излишеств.
5. Еще тупее
Раз уж мы можем написать программу программой, то стоит попробовать ее не просто написать, а еще и запустить. Это можно сделать, например, так.
;;; string meta
(eval (read-from-string
(let
((f5-code (make-array 0 :element-type 'character :fill-pointer 0)))
(format f5-code "(defun f5 (n)~%~T(cond~%")
(loop for i from 0 to 20 do
(format f5-code "~T~T((= n ~D) ~D)~%" i (f1 i)))
(format f5-code "))~%")
f5-code)))
Тут из интересного только создание строки с fill pointer. Этот поинтер позволяет дописывать данные в конец структуры, в нашем случае — строки. Дописываем мы уже знакомой функцией format, просто указывая ей заранее подготовленную строку.
Ну а остальное тривиально. Мы делаем строку, превращаем ее в код с помощью read-from-string, и отдаем на исполнение eval. Получаем на выходе готовую функцию.
Способ этот плох по двум причинам. Во-первых, eval в принципе до добра не доводит. Практически каждое руководство по стилю и книжка по программированию, причем на любом практически языке, рекомендует любить его не более чем дизентерию.
Во-вторых, ну это же Лисп! Зачем заниматься самопальным метапрограммированием, когда есть метапрограммирование очень даже штатное.
6. Лиспообразный
У Лиспа, не только у Common Lisp, есть одна очень приятная особенность. Он позволяет и практически поощряет метапрограммирование штатными средствами. Вот есть такое страшное слово «макрос». У макросов есть масса недостатков, про которые, наверное, все программисты и так знают очень хорошо. В С++ их принято не любить и не использовать. В С — не любить, но использовать по назначению. В ассемблере — любить, но не теряя голову. А в Лиспе слово «макрос» означает совершенно не то же, что во всех вышеупомянутых языках.
Лисповый макрос можно представить себе как функцию, которая возвращает некоторый список. Если этот список запустить как бы через eval, получится какая-то польза. Но при этом сам список расчитывается и привязывается к имени макроса так, что для стороннего программиста большой разницы, вызывает он функцию или макрос, нет.
В нашем случае макрос будет похож на пятый факториал по форме, но на четвертый по содержимому.
;;; real meta
(defmacro f6 (n)
(append
(list 'cond)
(mapcar
#'(lambda (i)
(list (list '= n i) (f1 i)))
(loop for i from 0 to 20 collect i))))
Появляется несколько новых слов, но они не очень страшные. Например, lambda — анонимная функция. Все и так знают, что такое лямбда, поэтому вкратце: первый аргумент — список параметров, второй — собственно тело, которое считается для параметров. Так как в нашем случае задача сгенерировать список, то тело — это некоторый list. Если не писать list перед выражением, выражение посчитается буквально. Так, например, (fi i) у нас превращается в 1, 1, 2, 6 и т. д. для каждого i, а (list '= n i) всего лишь в (= n 0), (= n 1) и так до (= n 20). Апостроф тут фактически делает то же самое, что и list — позволяет не считать выражения.
Еще mapcar. Тоже знакомая концепция — маппинг какой-то функции по какому-то списку. Так (loop for i from 0 to 20 collect i) генерирует список чисел от 0 до 20, а mapcar применяет нашу лямбду к каждому элементу этого списка. Получается ((= n 0) 1), ((= n 1) 1), ((= n 2) 2) и т. д.
Расчитав такой список выражений, мы «приклеиваем» его к cond посредством append. И получаем готовый f4, только такой, что он сам генерируется на лету. В зависимости от реализации это может быть как время компиляции, так и время исполнения, но в общем случае об этом можно не думать.
Вот это очень крутая возможность. Пример дурацкий, а возможность очень крутая. Настолько крутая, что Google Common Lisp Style Guide рекомендует использовать ее только по большим праздникам.
7. Быстрый
Вдумчивый читатель давно задался вопросом, а на кой черт делать функцию с функциональностью плохонького массива, если можно взять массив настоящий? Ну и правда.
;;; lookup
(defconstant +fact-21+ (make-array 21 :initial-contents '(
1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800
87178291200 1307674368000 20922789888000 355687428096000 6402373705728000
121645100408832000 2432902008176640000)))
(defun f7 (n) (aref +fact-21+ n))
Пример тут довольно самоочевидный. Для того, чтобы определить массив, надо воспользоваться функцией make_array. Параметров там довольно много, нам сейчас интересен простой одномерный массив с заранее определенными значениями. Эти самые значения мы потом будем брать функцией aref.
В Common Lisp есть не только массивы, но и хеш-таблицы. Разных приятностей вроде кортежей и множеств из коробки, правда, нет, но в принципе их можно свести к массивам и хеш-таблицам без большой потери в выразительности.
8. Безопасный
Прошлое решение всем хорошо, кроме одной вещи. Оно ограничено и ограничено нетривиально. Кроме того, тривиально оно тоже ограничено. Причем, первое ограничение: аргумент должен быть не больше двадцати, плохое, так как программист, использующий нашу функцию, должен про него знать и помнить; а второе — аргумент должен быть положительным целым — хорошее. Потому что, если программист поломает что-то до вызова нашей функции, у нас будет шанс ему об этом рассказать.
На этот случай в различных языках используются утверждения (assertions). В CL они, конечно же, тоже имеются.
;;; safe
(defun f8 (n)
(progn
(check-type n (integer 0 * ) "a positive integer")
(assert (<= n 20) () "Argument above 20")
(aref +fact-21+ n)))
Здесь check-type делает проверку типа входного значения. Спецификация типа вида (integer 0 *) указывает, что значение должно быть целочисленным и лежать в диапазоне от нуля включительно до бесконечности. Сообщение «a positive number» является частью гененриуемого сообщения "N = -123 is not a positive number", и поэтому имеет такой странный вид.
assert является классическим утверждением. Он проверяет условие (<= n 20) и, если оно не соблюдается, вызывает ошибку, останавливая выполнение функции, подписывая ее как "Argument above 20".
Все генерируемые подобным образом ошибки являются некоторым аналогом привычных исключений из сиобразных языков. Они так же могут быть пойманы и обработаны. Более того, в Common Lisp это можно делать по разному, в том числе и перезапуская, например, функцию подобно эрланговскому супервизору.
Выводы
Язык Common Lisp очень хорошо подходит для вычисления факториалов. Есть основания полагать, что и для всего остального он тоже хорош и годен. К синтаксису привыкаешь очень быстро, благо привыкать особо не к чему. Идиомы гуглятся. Контейнеры и удобные числа из коробки есть. Конечно, в процессе освоения приходится побиться головой в стену и немало, но лисповый процесс инкрементальной разработки в интекративной среде позволяет повысить частоту и снизить силу ударов до приемлемых.
Хороший язык.
Автор: akalenuk
