Кое-что о Лиспе на Атари-8

[ezswift]

Вообще говоря, история Лиспа - это просто фантасмагория какая-то.
Ну, не зря говорят, что Лисп - язык Искуственного Интеллекта.

Дело в том, что когда программируешь на Лиспе, всё время ощущаешь,
что ГОВОРИШЬ с машиной. Именно на её языке!

Все начинают обучение Лиспа с Факториала. Для начала и нам он подойдёт.

Факториал - это произведение всех неотрицательных целых чисел включая заданное.
Обратите внимание, что НОЛЬ тоже включён, только на него умножать не надо!

Математически, рекурсивное определение факториала следующее:

     /N=0, N! = 1
     \N>0, N! = N * (N-1)!

А вот - запись на Лиспе:

;;; Факториал
(DEFUN ! (N)
  (COND ((EQ N 0) ; При равенстве N нулю
         1)       ; будет единица
;; В противном случае N умножается на факториал от (N-1)
        (T (* N (! (SUB N 1))))))

Как говорится, ищите 10 отличий...

Вот трассировка:

(! 4)

-->!/ARGS: (4)
 -->!/ARGS: (3)
  -->!/ARGS: (2)
   -->!/ARGS: (1)
    -->!/ARGS: (0)
    <--!/VALUE: 1
   <--!/VALUE: 1
  <--!/VALUE: 2
 <--!/VALUE: 6
<--!/VALUE: 24
24

Стоит заметить, что на каждом этапе рекурсии происходит не только умножение на N, но и вызывается САМ факториал, подразумевающий, в свою очередь ещё одно умножение на N. Из-за того, что ВСЯ функция Факториала вычисляется на каждом этапе рекурсии при помощи ленивых(отложенных) вычислений, всё идёт медленно (Квадратичное замедление!).

Очевидно, что здесь лучшим был бы рекурсивный подход c накопительным аргументом.

Пусть наше N будет нумератором. Введём ещё один аргумент A - Аккумулятор, тогда, введя новую функцию !AUX, где счёт рекурсий будет от N до 1, и на каждой будет только умножение N-1 на A, а не рекурсивный вызов Факториала, получим быстрый алгоритм (Линейное замедление).

;;;Враппер - Вызывающая функция факториала для включения нуля в определение.
(DEFUN ! (N)
  (COND ((EQ N 0)        ; Если N=0
         1)              ; То !=1
;;; При ненулевом аргументе вызов вычисляющей функции с аргументами N и 1.
        (T (!AUX N 1))))

;;; Быстрая рекурсия факториала. Изначально в Нумераторе - N, в Аккумуляторе - 1.
(DEFUN !AUX (N A)
  (COND ((EQ N 1) ; Терминатор вычислений. Когда N станет 1,
         A)       ; Выводится накопленное содержимое Аккумулятора.
;;; В противном случае функция пошагово декрементирует Нумератор и
;;; умножает его на Аккумулятор. Результат помещается в Аккумулятор.
        (T (!AUX (SUB N 1) (* N A)))))
;;;              НУМЕРАТОР АККУМУЛЯТОР

Вот трассировка:

(! 4)

-->!/ARGS: (4)
 -->!AUX/ARGS: (4 1)
  -->!AUX/ARGS: (3 4)
   -->!AUX/ARGS: (2 12)
    -->!AUX/ARGS: (1 24)
    <--!AUX/VALUE: 24
   <--!AUX/VALUE: 24
  <--!AUX/VALUE: 24
 <--!AUX/VALUE: 24
<--!/VALUE: 24
24

Атарька говорит, что (! 40) = 8.159152512E+47
Без трассировки вычисляет за 1 секунду.

Чтобы показать мощь языка давайте напишем решение одной задачки, которая не поддалась Алонзо Чёрчу, но была решена его учеником Стивеном Клини через 12 лет.

Вот математическое рекурсивное определение:

(X=1 + (-1)) = 0
((X + 1) + (-1)) = X

А вот вычислитель на Лиспе:

(DEFUN DCR1 (X Y Z)
  (COND ((EQ X 1) 0) ; По определению, если x=1 То DCR1=0 
        (T           ; При другом X ...
         (COND ((EQ (+ Y 1) X) ; Y - Инкрементный терминатор числа проходов
                Z)             ; Z - Накопительный аргумент
               (T    ; В противном случае рекурсия
                (DCR1 X (+ Y 1) (+ Z 1)))))))

LISP
(DCR1 5 0 0)
4

То есть в своём Декременте мы
свели вычитание единицы из натурального числа к прибавлению единицы !!!
Ни одного (SUB N 1) в программе НЕТ!