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

[ilammy]

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

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

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

[sshikov]

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

[qrcs]

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

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

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

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

[go-prolog]

Предлагаю записать в виде лямбды(это лисп):

> set 'fct (lambda (n f) (if (zerop n) 1 (* n (funcall f (- n 1) f))))

И вызывать вот так

> funcall fct 100 fct

[qrcs]

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

(define f (lambda (n) ...)

[Pand5461]

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

[qrcs]

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

[AnutaU]

Можно ещё добавить версию с продолжениями.

[ilammy]

О, ну если упарываться, то можно добавить и вариант с хвостовой рекурсией без 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) )

[AnutaU]

О, это ж комбинатор неподвижной точки! Да, тоже хорошо бы в статье смотрелся.

[third112]

Спасибо — очень интересная статья. Но, к сожалению, не могу указать точные ссылки на книги, где авторитетные авторы утверждали, что факториал — неподходящий пример для рекурсии. М.б. в качестве примера стоит взять ханойские башни? Или что-то подобное. Правда не уверен, что там будет возможно такое разнообразие решений.

[honor8]

И факториале, и ханойских башнях используется метод математической индукции. Разница в чём?

[SiliconValleyHobo]

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

[ikle]

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

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

[punzik]

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

[qrcs]

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

«AST прямо в мозг» хорошо тогда, когда вам надо с ним работать. Собственно, это и обеспечивает удобство символьных вычислений в ЯП семейства Лисп. Читать код на них, особенно бегло, особенно если не практикуешься в этом регулярно — трудно. Пробовали реализовывать «сахар» в стиле Haskell, получалось наглядно (что-то вроде псевдокода в функциональном стиле). Но, конечно, с AST его все равно приходилось работать как со списком символов.

[kkirsanov2]

Здесь не хватает ссылки полностью раскрывающей тему факториалов и способов их получения
— www.cs.utexas.edu/~cannata/cs345/Class%20Notes/10%20Haskell%20Programmer%20Evolution.html