Важная информация

User Tag List

Страница 1 из 3 123 ПоследняяПоследняя
Показано с 1 по 10 из 27

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

  1. #1
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Кое-что о Лиспе на Атари-8

    Здравствуйте, дорогие друзья.

    Для 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)))      ; вывод результата
    Последний раз редактировалось ezswift; 20.12.2020 в 04:20.
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  2. Эти 2 пользователя(ей) поблагодарили ezswift за это полезное сообщение:

    Oleg N. Cher (09.12.2020), svofski (07.12.2020)

  3. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  4. #2
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

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

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

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

    Код:
         /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) в программе НЕТ!
    Последний раз редактировалось ezswift; 10.12.2020 в 15:00. Причина: Гы, надо поправить ...
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  5. #3
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Вообще говоря, математика - это нерадостное *****!
    Которое, ещё ВРЁТ!

    LISP
    (А в смысле Физики, так ГУСТО !!!)

    Но, - НАДО!
    Булькать!

    Для флуктуирования я всё время употребляю программу КОВРИК, которая на разных языках выводит ... КОВРИК.
    Прямо на экране.

    Вот Коврик на Лиспе:

    Код:
    (DEFUN PRAND NIL
      (COND ((> (PEEK 53770) 127)  ; Если содержимое RANDOM-регистра больше 127...
             (PROGN (POKE 128 0)   ; Запрещаем вывод значения функции
                    (PRIN1 '"/"))) ; Печатаем Слэш
            (T (PROGN (POKE 128 0) ; Иначе
                      (PRIN1 '"\"))))) ; Печатаем обратного СлэшА
    
    
    (DEFUN KOVRIK NIL
    ;; PROG is Iterator
      (PROG NIL
            (POKE 752 1)   ; Запрет курсора
            (POKE 82 0)    ; Установка левой границы
            LOOP           ; Просто метка
            (PRAND)        ; Случайная печать
            (GO LOOP)      ; Переход
            (POKE 752 0))) ; Восстановим курсор


    Может, кого и порадует ... Нажмите на изображение для увеличения. 

Название:	KOVRIK.png 
Просмотров:	120 
Размер:	11.1 Кб 
ID:	74156
    Последний раз редактировалось ezswift; 10.12.2020 в 00:34.
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  6. Этот пользователь поблагодарил ezswift за это полезное сообщение:

    Oleg N. Cher (09.12.2020)

  7. #4
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Добавил Видео https://youtu.be/giohCD0fGD4
    редактирования демо-программки.
    zen
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  8. Этот пользователь поблагодарил ezswift за это полезное сообщение:

    Oleg N. Cher (14.12.2020)

  9. #5
    Veteran Аватар для Raydac
    Регистрация
    16.08.2005
    Адрес
    Estonia,Tallinn
    Сообщений
    1,128
    Спасибо Благодарностей отдано 
    52
    Спасибо Благодарностей получено 
    227
    Поблагодарили
    179 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    на прологе все комбинации счастливого билета много проще
    in(X,[X|_]).
    in(X,[_|L]):-in(X,L).
    is_happy(A,B,C,D,E,F):-L is A+B+C,R is D+E+F, L = R.
    ?-Z=[0,1,2,3,4,5,6,7,8,9],in(A,Z),in(B,Z),in(C,Z),in(D,Z),in(E,Z),in(F,Z),i s_happy(A,B,C,D,E,F),write([A,B,C,D,E,F]),nl,fail.

  10. Этот пользователь поблагодарил Raydac за это полезное сообщение:

    ezswift (15.12.2020)

  11. #6
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Raydac
    Есть чо сказать?

    Я как раз ищу способ написать интерпердатор Пролога.
    Пока не нашел.

    А так, благодарю за сообщение ЧЕССНО!
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  12. #7
    Veteran Аватар для Raydac
    Регистрация
    16.08.2005
    Адрес
    Estonia,Tallinn
    Сообщений
    1,128
    Спасибо Благодарностей отдано 
    52
    Спасибо Благодарностей получено 
    227
    Поблагодарили
    179 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    дак а чего искать способ, штука несложная, я когда пролог изучал то сел да написал, лет 11 чтоль назад, японец один потом на айпад переделал версию

  13. #8
    Activist Аватар для ezswift
    Регистрация
    26.02.2011
    Адрес
    Москва
    Сообщений
    258
    Спасибо Благодарностей отдано 
    8
    Спасибо Благодарностей получено 
    25
    Поблагодарили
    18 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Есть ли код?
    Вроде паскаля или си.

    Я бы попробовал тогда на PL65 затуганить...
    Только я ни разу не программист... Укротитель я...

    У меня сейчас на нём пара наработочек: доступ ко всей расширенной памяти и библиотека списков.
    zen
    MAC и PC - это всего лишь периферия для Атари...
    130XE|XC12|CA2001|XF551|IDEPlus2.0|SIO2SD|SIO2IDE| RAM576XE+Covoх|SIO2PC|MAXFLASH8|MAXFLASH1|The Ultimate Cartridge|

  14. #9
    Veteran Аватар для Raydac
    Регистрация
    16.08.2005
    Адрес
    Estonia,Tallinn
    Сообщений
    1,128
    Спасибо Благодарностей отдано 
    52
    Спасибо Благодарностей получено 
    227
    Поблагодарили
    179 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от ezswift Посмотреть сообщение
    Есть ли код?
    Вроде паскаля или си.
    у меня только на Java, это уже гуглить надо, вроде исходники движков есть от JavaScript (TauProlog) до версий на clojure (считай на лиспе)

  15. #10
    Guru Аватар для andrews
    Регистрация
    20.04.2006
    Адрес
    Санкт-Петербург
    Сообщений
    2,651
    Спасибо Благодарностей отдано 
    407
    Спасибо Благодарностей получено 
    188
    Поблагодарили
    166 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Есть какие-то хрени, гуглящиеся на Java2pas, но приблизят ли они топикастера к его цели неизвестно. Надо пробовать. Был бы интересен Prolog и для всего, где реализован консольный uLisp.
    Последний раз редактировалось andrews; 15.12.2020 в 11:10.

Страница 1 из 3 123 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ocean Software кое что...
    от research в разделе Музыка
    Ответов: 55
    Последнее: 01.08.2013, 22:07
  2. Кое-что о микосхемах!
    от Alex_NEMO в разделе Несортированное железо
    Ответов: 9
    Последнее: 13.04.2009, 23:29
  3. Кое-что задаром
    от F0lken в разделе Барахолка (архив)
    Ответов: 0
    Последнее: 15.03.2009, 20:07
  4. кое что из недоделанного..
    от Sayman в разделе Музыка
    Ответов: 2
    Последнее: 09.04.2008, 15:21

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •