Здравствуйте, дорогие друзья.
Для 8-битной Атари существует единственная версия интерпретатора Лиспа
- Интерлисп/65.
Я заинтересовался Лиспом давно, но всё это было - чисто академический интерес,
так как я вообще не мог представить как его можно использовать на Атари.
Всё же, у меня для сравнения было три версии Интерлиспа и так или иначе, я засел за изучение языка.
Сначала об истории.
В 30-е годы прошлого века жил-был могучий математик Дэвид Гилберт.
После смерти Пуанкаре, его стали считать первым математиком планеты.
Он был вполне непоседлив и изъездил всю математику вдоль и поперёк.
Каждый вздрогнет, вспомнив теорему Коши-Буняковского и Гильбертовы пространства.
Вот с него-то всё и пошло...
Так вот, именно он внезапно перед своими сотрудниками залепил жуткую задачку:
Энтшайдунгс-проблЕм. Задачка эта касалась анализа и формализации вычислимости.
Спросил он следующее: Существует ли формальный аппарат, внутри которого можно
написать произвольное утверждение, которое можно будет доказать за конечное число шагов средствами самого этого аппарата?
Собственно он спросил: "Существуют ли алгоритмы?!!"
Все забегали и озаботились...
Там была ещё парочка шикарных математиков которые вкурили эту проблемку аж на
20-лет и в конце концов оба доказали, что в арифметической формализации - НЕ СУЩЕСТВУЕТ! В общем же случае - Существует.
Благодаря этим исследованиям, один из них с помощью АНАЛИЗА глобальной задачи придумал формализацию "Решающей машины" имени самого себя любимого...
- это был Алан Тюринг и придумал он машину Тюринга.
Второй же, с помощью СИНТЕЗА малых подзадач придумал формальный язык способов вычислений, а именно - теорию "Лямбда исчисления" и это был - Алонзо Чёрч.
В конце концов в 1957 году небезызвестные Джон Бэкус и Петер Наур реализовали язык Фортран,
а небезызвестный Джон Маккарти в 1958 году реализовал язык Лисп.
Разумеется, первый язык был воплощением аналитической тюриговской машины, а второй синтетического Лямбда исчисления.
Сам по себе Наур интересен фамилией, моральный ИНДУС, знаете, ли...
Он Бэкусу сказал, что на Санскрите вообще всё определено, Как, Что и Когда говорить ...
И озаботил Джона !!! И ВОТ Вам факт!
Ну, в общем, я родился в 1959 году и однажды тоже озаботился задачкой вычисления "Счастливого билета" на разных языках.
В случае Фортраноподобных языков, алгоритм будет следующим:
1. Так как на билете шестизнак, то следует построить убывающий цикл,
в котором надо будет делить сам шестизнак, а потом и его остатки на степень десятки (5->0), получая правильные частные значения.
2. Сложить три первых значения, затем три вторых.
Вычесть одну сумму от другой и если 0, то вуаля, вы слопали билет. :)
В случае Лиспоподобных языков, алгоритм выглядит по другому:
1. Распаковать шестизнак в список десятичных чисел.
2. Взять (Счёт ведётся от НУЛЯ) третий хвост списка
3. Найти сумму всех чисел в шестизнаке и вычесть из этой суммы сумму чисел третьего хвоста.
4. При нуле питаться! :)
Вам не показалось, что второй способ - это именно то, как мы-люди интуитивно подсчитываем съедобность билета?
Вот вычислимость билета на ЛИСПЕ:
Код:;;;; Проверка на счастливый билет
;;;; Интерлисп/65 Для Атари 8-бит
;;; Добавим предикат пустоты списка.
(DEFUN NULL (L) ; Зададим имя и параметр функции
(EQ L NIL)) ; Проверка на равенство NIL(Пуст по определению) списка L
;;; Добавим суммирование элементов списка L
(DEFUN SUM (L)
;; NIL это терминатор хвоста любого списка !
;; Используем наш предикат для проверки на исчерпание списка
;; COND проверяет СПИСОК предикатов останавливаясь при первом T !!!
(COND ((NULL L) ; При пустоте или исчерпании списка
0) ; Сумма = 0
(T ; В противном случае, (T - терминатор для COND)
;; рекурсивно, начиная от хвоста прибавляем все частные головы списка ...
;; (CAR L) - предыдущая голова
;; (SUM (CDR L)) - уже найденая сумма хвоста
(+ (CAR L) (SUM (CDR L))))))
;;; Вывод промпта и получение шестизнака
(DEFUN PROMPT NIL
;; PROGN задаёт итеративное исполнение форм
(PROGN (POKE 128 0) ; Отключение промпта Лиспа
(PRIN1 (QUOTE "Enter 6-digits ticket number> ")) ; Печать промпта
(SETQ NUM (READ)))) ; Присвоение переменной данных ввода с клавы
(DEFUN HAPPY-P NUM
(PROGN (SETQ LIS (UNPACK NUM)) ; Присваиваем распакованное число списку
(SETQ S (SUM LIS)) ; Вычисляем полную сумму списка
(SETQ R (SUM (@ LIS 3))) ; Вычисляем сумму элементов 3 хвоста
(SETQ L (SUB S R)))) ; Вычитаем из полной суммы
(DEFUN LUCKY NIL
(COND ((EQ L R) ; Если левая и правая суммы равны
(PROGN (POKE 128 0)
(PRINT (QUOTE "Eat me, Honey !"))))
(T ; В противном случае
(PROGN (POKE 128 0)
(PRINT (QUOTE "Bad-luck poor Yorick !"))))))
(DEFUN TICKET NIL
(PROGN (SETQ NUM 0) ; Инициализация переменных ...
(SETQ LIS NIL) ; ...
(SETQ L 0) ; ...
(SETQ R 0) ; ...
(PROMPT) ; Вывод промпта и ввод шестизнака
(HAPPY-P NUM) ; Проверка на счастливость
(LUCKY))) ; вывод результата
