KRIEGSSPIELE!
Вы хотите отреагировать на этот пост ? Создайте аккаунт всего в несколько кликов или войдите на форум.

Что такое FORTH?

Перейти вниз

Что такое FORTH? Empty Что такое FORTH?

Сообщение автор Gudleifr Ср Мар 29, 2017 11:46 am

ЙОДЫ МАГИСТРА РЕЧИ ТАЙНА ОТКРЫТА: НА ФОРТЕ ПРОГРАММЕР СТАРЫЙ ОН ПРОСТО ЕСТЬ.

FORTH - это простейший интерпретатор, простейшая надстройка над машинным языком, позволяющая начать программистский диалог с компьютером:
Что такое FORTH? Jasyki10

Устроен он примерно так:
Что такое FORTH? G9110
Процедура ОК - простейший доступ к Операционной Системе (консоли) компьютера; СИМВОЛ - простейший распознаватель команд, ВЫПОЛНИТЬ - тупая команда, исполняющая другие команды, КОМПИЛИРОВАТЬ - тупая команда записи команд для последующего исполнения, СЛЕДУЮЩИЙ - тупой переход к следующей команде из скомпилированных. ПОТОК, ЗНАЧЕНИЕ, СТЕК, СЛОВАРЬ - только самые простые форматы данных для передачи между перечисленными процедурами (причем, совершенно не обязательные).

Т.е. FORTH - это простейший способ реализовать цикл разработки (рисунок из книжки "TF" Броуди, см. далее):
Что такое FORTH? G9b18710
Главные советы этой книги можно свести всего к двум: "Не пишите интерпретатора более мощного, чем нужен для реализации этого цикла" и "Используйте в программе процедуры интерпретатора, а не программируйте их более мощные или более правильные аналоги".
***

А что может дать такая простота?

Все очень просто. Запустите визуальное приложение, над которым Вы сейчас работаете... Ну, например, вот так:

Что такое FORTH? 2p10
У Вас, конечно, красивее.

Что мы тут видим? Программисту совершенно пофигу, что и в каком порядке пользователь будет вводить в окошки и в каком порядке нажимать кнопки. Это проблемы пользователя,  который сам должен превратить решение своей задачи в выбор правильной последовательности нажатий кнопок и заполнения окошек. Т.е. вместо "полного алгоритма решения задачи" программист снабжает пользователя "машиной, решающей подобные задачи". А как говорил Дейкстра, где "машина", там и "язык". Здесь - язык состоящий из глаголов-кнопок, существительных-окошек ввода, прилагательных-опций...

Однако, внутри программы аналогия исчезает. В мешание "елочек" ветвящихся выборов и "матрешек" вложенных циклов трудно найти процедуры обработки пользовательских "фраз". А что, если и внутри программы мы продолжим общаться на "языке пользователя"? Чтобы программа не опрашивала тупо весь "пульт управления", выясняя, за какую "пимпочку" дернул пользователь, а сразу понимала, что он "хотел сказать"? Чтобы программист тоже мог говорить с программой почти на том же языке (постепенно переходя на программистский жаргон), передавая свои фразы тому же "исполнителю", что и пользователь? Это и будет FORTH. Программа не просто делающая вид, что понимает язык пользователя, но сама на нем написанная.

Что это стоит? Две недели, без отрыва от основной работы, перед началом проекта - на написание своего FORTH на том языке, на котором планировали писать проект изначально (при обязательном условии, что вы знаете язык программирования, на котором пишете).

Почему так не делают? По единственной причине. Не могут сделать шага от "машины" к "языку".


Последний раз редактировалось: Gudleifr (Пн Май 03, 2021 2:23 am), всего редактировалось 5 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Пт Мар 31, 2017 9:58 am

ИНТЕРПРЕТАТОР ИНТЕРПРЕТАТОРОВ
* "FORTH - язык: изобретен в 1971 году Чарльзом Муром для управления телескопом /lurkmore/".
Во-первых, Мур работал в обсерватории не в 71-м, а в 58-м; во-вторых даже версия-прародитель FORTH 58-го года не была предназначена для управления телескопом; в-третьих, похоже, Мур реализовал FORTH, но никак не изобрел, и, наконец, FORTH - не язык!
* Что же такое FORTH?
По Муру, метод написания "хороших" программ. Не язык, не операционная система, не среда программирования... Метод! Однако, что это за метод, если его "каждый понимает по-своему"? Если он практически не имеет обязательных рекомендаций?
* Я предлагаю следующее "определение": имеем A (язык машины), пишем на нем на коленке за неделю язык F (FORTH), затем на нем - P (проблемно-ориентированный язык), отдаем последний пользователю для решения своих задач. (Концепция тупого программиста и умного пользователя).
* Отсюда: F должен быть максимально прост (если он сравним по сложности с P, то проще сразу P и реализовать) и настолько универсален, что бы его можно реализовать для любого A.
* Что можно выиграть от A=F (FORTH-процессор)? Почти ничего. Вот от процессора, ориентированного сразу на P выигрыш велик...
* Соглауется ли мое определение с принципами Мура?
Термин "проблемно-ориентированный язык" (P), по крайней мере, Мур использовал.
Основным Принципом (с большой буквы) Мур считает простоту. Так что мое "за неделю, на коленке" вполне соответствует Муру.
Следствием Основного Принципа Мур считал отказ от написания программ заранее, от предвосхищения будущих задач. У меня, очевидно, тоже самое: нет потребности в P - нет и F.
* "FORTH очень быстр и компактен" - любят говорить фортеры. Однако, забывают уточнить, что подразумевается не столько ресурсопотребление FORTH-программ, сколько быстрота их написания/правки и малый объем программных текстов.
Последнее особенно важно - чем компактнее наши программы, тем больше мы успеем написать до того момента, когда сложность программного текста превысит нашу способность его осмыслить.
* Мур говорил: "Сделай сам!" (и считал это еще одним следствием Основного Принципа). Это и давало упоминаемую "простоту компактности": FORTH-программы состоят только из того, что в них понапихал сам программист.
Ему не нужно обеспечивать совместимость с чужим кодом, наследовать/настраивать его, использовать навязанные парадигмы...
Программа на FORTH - это, по-сути, объяснение программиста самому себе решения задачи в свободной форме.
(Однако, когда FORTH-метод реализуется не на "голом железе", возникает проблема: жертвовать долей простоты, явно предоставляя программе интерфейсы с чужим кодом, либо спрятать эти интерфейсы внутрь FORTH-машины, жертвуя "всемогуществом" программиста).
* А как быть со сложностью интерфейса "машина-пользователь"? Мы же привыкли, что "только жутко тормозная и заумно навороченная ОС Windows обладает всеми необходимыми драйверами и визуальными инструментами для обеспечения пользователю хоть какого-то комфорта".
А, никак! Простейший интерпретатор на то и простейший, что сводит общение программы с пользователем до необходимого минимума. А его обеспечить просто.

Сколько слов, а о FORTH еще ничего и не сказано! Что же это такое?

Фортеры обычно говорят: во-первых, создаем некоторую структуру данных (СТЕК) предназначенную для обмена данными между процедурами-СЛОВАМИ. Теперь нам не надо долго описывать параметры и возвращаемые значения функций. Любое СЛОВО берет со СТЕКА то, что ей надо, и запихивает туда же результат. Второй плюс - теперь не надо изобретать имена для локальных переменных - кидаем на СТЕК значение, а когда понадобится - снимаем.
Во-вторых, создаем другую структуру данных (обычно, список) - СЛОВАРЬ, в которую вписываем код процедур СЛОВ в некотором определенном (называется ШИТЫМ КОДОМ) формате. Так как списка параметров нет, то единственное, что нужно знать компилятору о СЛОВЕ - адрес процедуры в памяти. Так, что ШИТЫЙ КОД, обычно,- просто последовательность адресов процедур СЛОВ.
В-третьих, механизмы доступа к обоим структурам ПРОШИВАЮТСЯ согласно пункту "во-вторых" и объявляются общедоступными.
Все!

FORTH ли это?
Вернемся к общей теории интерпретаторов. Интерпретатор читает откуда-то (здесь и далее ПОТОК) текст программы (СЛОВА) и, по мере прочтения, законченных команд, последние исполняет (процедура ВЫПОЛНИТЬ).
Прочтенная информация в общем случае накапливается в жуткой древообразной структуре (ср. дерево грамматического разбора). А процедура ВЫПОЛНИТЬ занимается тем, что в этом дереве производит какие-то "свертки и развертки".
Например, "ВЫПОЛНИТЬ выражение" означает взять всю "ветку", на которой "висят" все операции и операнды выражения, и свернуть ее в один несчастный "лист" - значение полученное при вычислении.
А в FORTH? Как мы заменили дерево на СТЕК? Очень просто: отказались от грамматики, т.е., грубо говоря, от "забегания вперед".
Нельзя вводить СЛОВА, которых интерпретатор еще не знает, нельзя вводить имя вычисляемой функции раньше значений параметров, нельзя, наконец, вводить арифметические операции раньше чисел, над которыми они выполняются.
И назвали это "обратной польской записью"... (И поняли, что это хорошо, что бы ни говорили любители "нормальных" языков).
Но как будет ориентироваться в СТЕКЕ процедура ВЫПОЛНИТЬ? Никак! Она может всего две вещи - помещать на стек значения и выполнять "СЛОВА по адресу" (значение от СЛОВА она отличить способна).
Т.е. любая обработка значений на СТЕКЕ должна быть явно прошита в СЛОВАРЕ. Но, т.к. грамматики нет, то вариант обработки всего один: взять со СТЕКА параметры, обработать, положить результат на СТЕК. О том, чтобы результаты одной обработки были правильными параметрами для следующей, должен заботиться сам программист (и/или пользователь).
Примерно это и изложил Дейкстра за 8 лет до официального явления FORTH. (Понятно, гораздо литературнее меня). Причем, он установил три железных принципа, которые нельзя нарушать без того, чтобы FORTH перестал быть самим собой.
* Во-первых, ячейка СТЕКА должна быть способна содержать значение любого из "системных" типов, минимум - числовые значения и адреса СЛОВ.
* Во-вторых, каждое известное FORTH-системе СЛОВО (в смысле - строка литер) однозначно переводится в адрес его кода в СЛОВАРЕ.
* В-третьих, процедура ВЫПОЛНИТЬ должна уметь различать адреса СЛОВ, которые надо обработать, от СЛОВ, которые надо исполнить немедленно.

"А какого уровня должен быть язык FORTH?"
"Дурацкий вопрос",- отвечают фортеры: "Он позволяет, как напрямую работать с железом, так и понимать практически человеческую речь".
Это не совсем правда. В зависимости от того, на каком A написан F и насколько фортер понимает высокоуровневость P, заявленный диапазон может быть как широким, так и очень узким. (Сейчас очень часто нижняя граница - библиотеки языка C, а верхняя - C++ -подобный текст).
Но, зато, уникальное отсутствие синтаксиса (просто СЛОВА/литералы, разделенные пробелами) позволяют на FORTH естественно говорить о самых разных вещах: запуске программных процессов, машинных кодах, грамматическом разборе, документировании, "капусте, королях"...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Пт Мар 31, 2017 10:02 am

КОМПИЛЯТОР КОМПИЛЯТОРОВ
* Обычно фортеры очень любят рассуждать о том, что FORTH "на самом деле" компилятор.
И что он умеет "расти" и "самообучаться"...
Как будто другие интерпретаторы не умеют определять функции и подпрограммы.
И как будто мало интерпретаторов умеют "компилировать" программы в байт-код.
И как будто они не умеют это делать, не прерывая диалога с пользователем...
Отличие FORTH-компиляции от "обычной для интерпретаторов" только в одном - он это делает простейшим образом (ШИТЫМ КОДОМ), пытаясь всю работу переложить на средства A.
* Увлечение языковыми нюансами FORTH часто приводит к идее построения для FORTH "правильного" компилятора. И сведения языка P к одному единственному СЛОВУ - "GO" (и даже целевой компиляции FORTH-системы вместе с программой в исполняемый файл).
В этом случае теряется сама идея метода - игра "программист-пользователь" превращается в игру программиста самого с собой. Интересно, забавно, но непродуктивно...
* Компиляция FORTH существует в трех ипостасях: во-первых, сборка новых СЛОВ как "макросов" из уже определенных, во-вторых, создание низкоуровневых "кодовых" СЛОВ на языке A (некоторые фортеры терпеть этого не могут), в третьих, создание СЛОВ, которые могут создавать другие СЛОВА.
Последнее позволяет несколько разнообразить примитивный F-язык замысловатыми грамматическими "оборотами" и "предложениями", но может вконец запутать начинающего фортера этакой "рекурсией": что происходит в период компиляции СЛОВА, создающего компилирующие СЛОВА?
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Пт Мар 31, 2017 10:21 am

МОЯ ИСТОРИЯ  
Когда мне в первый раз показали FORTH (на Spectrum), мне показалось, что это та самая простота, которая хуже воровства.
Вскоре свалился с простудой и от нечего делать прочел книгу Броуди (для начинающих) - зацепило. Оказалось, что я могу написать компилятор сам, а не пользоваться убожеством, доступным мне сейчас (1989 год - в моем распоряжении польский клон IBM XT с установленным Basic, затем добавился Turbo Pascal).
Попробовал писать прямо в кодах (в DOS debug). Получалось, но муторно. Раздобыл masm. Работа пошла быстрее и скоро моя FORTH система (FOBOS), являющаяся неким клоном системы, предложенной в книге Баранова и Ноздрунова, была готова.
Больших проектов я на FOBOS не писал, но, играя с ним, получил массу удовольствия.
Затем проект был надолго заброшен.
***
В начале 2000-х столкнулся с проблемой. Создав свою Internet-страницу, понял, что, кроме текстов и картинок, хочу выкладывать и некоторые алгоритмы и программы. Правилами бесплатного хостинга обычно запрещается выкладывать исполняемые файлы и архивы. Значит, готовые к употреблению win-exe-файлы выложить не удастся.
Перешел к созданию CGI-файлов. Неудобно - играть с моими программками можно только в режиме online, тратя свой Internet-трафик. Плюс, правила выкладывания CGI-программ на бесплатных хостингах имеют свойство "плавать", что приводит к необходимости постоянно отслеживать их работоспособность и, даже, иногда переписывать их с языка на язык.
Гнаться за новыми версиями Internet-browser-ов, используя все возможности Java-script, Flash и прочих встроенных Basic-ов? Это значит а) ограничивать свою аудиторию только "продвинутыми" пользователями и б) погрузиться в изучение этих убогих языков.
***
Решил следующее. Написать минимальное FORTH-ядро и откомпилировать его в win-exe. Остальную часть FORTH-системы оформить в виде обычного текстового файла. Exe-ядро превратить в текстовый файл (содержащий текстовое представление бинарных кодов), из которого можно собрать исполняемый при помощи простейшего DOS-овского debug. Выложить оба текстовых файла (плюс файл с исходным текстом ядра на языке ассемблера) в Сеть.
Плюс такого подхода очевиден - полная свобода просмотра и редактирования кода пользователем. Дополнительно, доведя до ума свой FORTH, я смогу больше не мучиться с выбором: быстренько слепить что-то в Borland или MS Studio, или лучше - на Perl под Tcl/Tk?
Минус тоже вполне очевиден. Я заведомо ограничил себя Win-32. Сначала хотел переписать и под Linux. Но, там проблема стоит не столь остро - исходные тексты на C, Perl и Tcl/Tk понимаются всеми nix-ами однозначно. Да и способов создать проблемно-ориентированный язык там пруд-пруди.
***
Постепенно создание красивого интерфейса с Win32 превратилось в самоцель.
***
Когда-нибудь, это войдет в третий том моих заметок о старых играх...


Последний раз редактировалось: Gudleifr (Пт Июн 30, 2017 5:40 pm), всего редактировалось 2 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Пт Июн 30, 2017 11:56 am

ЧАРЛЬЗ Х. МУР / ПРОГРАММИРОВАНИЕ ПРОБЛЕМНО-ОРИЕНТИРОВАННОГО ЯЗЫКА

ЧАРЛЬЗ Х. МУР
ПРОГРАММИРОВАНИЕ ПРОБЛЕМНО-ОРИЕНТИРОВАННОГО ЯЗЫКА
Написано ок. июня 1970

PROGRAMMING A PROBLEM-ORIENTED-LANGUAGE
CHARLES H.MOORE
written ~ June 1970
Что такое FORTH? Leaf10PDF, 0.7МбЧто такое FORTH? Leaf10

ПРИМЕЧАНИЕ ПЕРЕСКАЗЧИКА
Это не перевод, я слишком плохо знаю английский. Это, скорее, построчный пересказ. Причем, абсолютно сырой - почти без вычитки и редактирования. Единственно, подправил оглавление и переставил перепутанные абзацы в 7-й главе. (Только сейчас обнаружил, что и с 4-й главой у меня не все было в порядке - 2019).

1. Стиль книги очень архаичен. Современным программистам многое покажется непонятным и странным.
2. Мысли Мура в некоторых местах до неприличия совпадают с моими. Поэтому, я, возможно где и передернул (в смысле - поторопился принять желаемое за действительное).
3. Книга так и не ответила на самый главный для меня вопрос: откуда взялись идеи, лежащие в основе устройства FORTH? Некоторых компьютерных баек тех времен и здравых, и местами замечательных, идей хватило только на первые две главы. В третьей главе, вдруг, откуда ни возмись, является FORTH сразу во всей своей красе. Сам Мур, понимая, что здесь у него образовался пробел, долго извиняется необходимостью забежать вперед и зациклить изложение. Однако, и после этого продолжает всерьез обсуждать только частности, хотя, иногда, и изящно реализованные. Автор, правда, еще в некоторых местах пытается рассуждать задним числом, но довольно бессвязно. (Позднее я нашел ответ в работе Дейкстры - см. следующий пост).
4. Буквально воспринимать изложенные здесь идеи - значит подрывать общепринятые устои современного программирования. В том числе, в области современного FORTH. Поэтому советую успокаиваться при чтении мыслью, что, мол, все это давно устарело и отмерло за ненадобностью. Тем более, что, во многом, особенно в мелочах, так оно и есть.
5. Вообще же, интересны не столько конкретные технические идеи (хотя, тому, кто будет писать свой FORTH, они будут полезны), сколько выбор автором вопросов для рассмотрения и занятая им позиция.

/Gudleifr, март 2012/

***

ПРЕДИСЛОВИЕ

Это - неопубликованная книга, которую я написал давно. Сразу после того, как я написал первые версии FORTH. Возможно, это - обоснование FORTH задним числом. Она интересна, но не опубликовывать же ее, поэтому я выкладываю ее на сайте. Имеется машинописный текст, сохранившийся в Forth, Inc. Я напечатал его на моей портативной Smith-Corona, с множеством правок. Он был настолько неразборчив, что мне пришлось перенабрать его на компьютере.

Кроме того, я нашел это упражнение полезным для моего стареющего навыка машинописи.

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

/Чак Мур, 2011/

1. ВВЕДЕНИЕ

Я не знаю, зачем вы читаете эту книгу. Зачем тогда я ее пишу? Давайте прочтем название: "Программирование проблемно-ориентированного языка". Ключевое слово здесь "программирование". Я написал много программ за эти годы. Я пробовал писать хорошие программы, и я достаточно критически относился к своему стилю. Хотелось уменьшить затраты на писание и повысить качество написанного. Заметил, что определенные ошибки совершаю неоднократно. Ошибки, очевидные при повторном чтении программы, но трудно избегаемые в контексте писания. Я подумал, что мог бы составить сам для себя предписание, напоминающее об этих проблемах. И если оно будет полезно для меня, то должно быть полезно и другим: если вы не знакомы с предметом - узнаете что-то новое, если знакомы - познакомитесь с новой точкой зрения.

Также, меня волнует общее пренебрежение некоторыми существенными проблемами. Это - безразличие к качеству, вера в то, что работающая программа хороша уже сама по себе. Я убежден, что эта вера неуместна. Ситуация усугубляется увлечением неэффективными языками высокого уровня. Зачем писать хороший алгоритм, если компилятор его все равно испортит?

Так что, я написал книгу по программированию. Я не имею никакого особенного стремления непременно вас убедить. Возможно, это грубо. Возможно, вам многое не понравится. Пожалуйста! Я хочу документировать подход, который я нашел полезным, и, возможно, стимулировать его применение в программировании. Если вы заинтересуетесь, я буду рад.

Вернемся к названию. Что за проблемно-ориентированный язык? Я не уверен, что термин выбран правильно. Но я обнаружил, что он очень подходит для обозначения того, что я делал.

Проблемно-ориентированный язык - язык, созданный для решения специфической задачи. Синоним - прикладной язык. Очень часто никто даже не замечает, как такой язык появляется. Например, если ваша программа читает символ в 80-й колонке перфокарты, чтобы идентифицировать входные данные, вы используете прикладной язык. Очень сырой и очень неуклюжий. Главным образом потому, что вы об этом не думали. Я уверен, что разобравшись в проблеме, вы можете предложить лучшее решение. Эта книга покажет вам, как.

1.1. ОСНОВНОЙ ПРИНЦИП

Обсудить надо многое. Я собираюсь предложить вам для использования много методов. Они основываются на свойствах цифрового компьютера - инструмента для обработки информации. Компьютер может что-то делать. Я надеюсь, что вы позволите мне уточнить это "что-то" и обосновать мои слова. Я подразумеваю - обосновать строго, математически. Компьютер не может делать все. Это я тоже могу доказать. Но наиболее важно, что многого мы с вами просто не можем запрограммировать. Это эмпирический факт.

Итак я определяю Основной Принцип:

ПУСТЬ БУДЕТ ПРОСТО

При увеличении возможностей программы ее сложность растет по экспоненте. Согласованность составляющих или даже внутренняя логика программы может легко выйти из-под контроля. Основной Принцип нужен для того, чтобы избежать этой проблемы. Все знакомы с операционной системой, которая его игнорировала.

К ней очень трудно приноровиться. Большая часть вашей программы нужна для соблюдения соглашений операционной системы и соглашений вашего языка. В конце концов, требуется всего полдюжины операций, так зачем же писать лишнее? Единственная ваша возможность противостоять росту сложности под давлением внешних соглашений - Основной Принцип.

Чтобы облегчить применение Основного Принципа, я собираюсь предложить вам несколько инструкций. Увеличит ли их применение размер программы? Нет, размер программы зависит только от сложности задачи. За это я могу поручиться, т.к. проверил на себе. Все, о чем мы будем говорить, прекрасно поместится в 4k слов ОЗУ.

Основной Принцип имеет следствие:

НЕ ПРЕДПОЛАГАЙТЕ!

Не пишите код, который может пригодиться когда-то в будущем. Не оставляйте заплаток для будущих расширений. Вещей, которые вы можете захотеть сделать, бесконечное множество; это означает, что каждая из них имеет нулевую вероятности осуществления. Если вам что-то понадобится позже, вы это и запрограммируете позже - и, вероятно, лучше, чем сделали бы это теперь. И если кто-нибудь будет расширять вашу программу, он заметит оставленные вами для этого заплатки? Все ли из них вы аккуратно задокументируете?

Основной Принцип имеет еще следствие:

СДЕЛАЙТЕ ЭТО САМИ!

Теперь мы спускаемся на уровень практики. Это - наш первый вызов сообществу. Общепринято, что вы должны использовать стандартные подпрограммы. Я говорю, что вы должны писать ваши собственные подпрограммы. Конечно, вы должны уметь это делать. Т.е. надо научиться, а это трудно. Хотя бы, попытайтесь. По прошествии лет перебора языков и компьютеров станет легче. Если вы не собираетесь уделять программированию столько времени, эта книга не для вас.

Какие подпрограммы вы должны писать сами? Я уважаю подпрограмму SQRT. Она написана хитро и талантливо. Вы можете использовать библиотечные подпрограммы с большим успехом. А подпрограммы ввода? Они тупы до безобразия. Я не могу поверить, что последнее слово в этом вопросе было сказано изобретением 15 лет назад оператора FORMAT.

Как я разъясню позднее, подпрограммы ввода - наиболее важный код вашей программы. В конце концов, никто не видит вашу программу, но каждый видит ваш ввод. И разрешать заниматься этим стандартным подпрограммам - глупо. Тот же самое можно сказать о подпрограммах вывода и доступа к диску.

Более того, задача не такая уж и сложная. Хотя требуются сотни инструкций, чтобы написать общую подпрограмму, вам - для написания частной - понадобятся только десятки. Я, вообще, против написания подпрограмм длиннее сотни инструкций.

Так, если вам нужны комплексные целые двойной точности, придется либо написать свою подпрограмму, либо подождать, пока производители COBOL до подобного дорастут. Проще самому.

Но что будет, если каждый будет писать свои подпрограммы? Это шаг назад; скоро миллениум, когда программы станут машинно независимы, когда все мы будем писать на одном и том же языке, возможно, даже на одном и том же компьютере? Что сказать? Я не могу решить все проблемы мира. Если повезет, я могу написать хорошую программу.

1.2. ОБЗОР

Я собираюсь рассказать вам, как написать программу. Это - определенная программа; т.е. программа с определенной структурой и возможностями. В частности, это - программа, которая может быть строго определенным способом расширена до целого комплекса, и, соответственно, стать способной решать комплексные проблемы. Одна из проблем, которые придется рассмотреть - проблема сложности. Как вы можете управлять вашей программой так, чтобы она осталась простой? Сначала я попробую абстрагироваться от проблем ввода. Правда, так как эти проблемы очень важны, долго рассматривать программы без ввода не получится.

Допуская ввод, программа получает язык, позволяющий пользователю управлять ее работой. Естественно, это увеличивает гибкость программы, но требуют ли этого условия применения программы? Есть возможность достичь значительного упрощения программы, используя ввод для управления ее выполнением.

Следующий шаг - проблемно-ориентированный язык. Разрешая программе динамически изменять свой язык управления, мы получаем качественное изменение способностей. Так мы переключаем наше внимание с программы на язык управления. Это и важно, и опасно. Здесь очень легко потерять из виду проблему, увлекшись красотой решения.

В некотором смысле, наша программа превратилась в метаязык, описывающий язык, на котором написано приложение. Но метаязык термин для нас неподходящий. Мы тут не философией занимаемся. Для точного описания нашей ситуации двух уровней - язык и метаязык - не хватит, нужно не меньше четырех. Разделить их очень трудно. Кроме того, в различных случаях, встречающихся на практике, уровни могут перепутываться очень замысловато.

Проблемно-ориентированный язык может описать любую проблему, из тех, с которыми я сталкивался. И помните, мы занимаемся не языком, но программой, которая реализует язык. Изменяя язык, мы можем применять ту же самую программу для других целей. Однако имеется класс расширений языка, которые дают новое качество. Они не увеличивают применимость программы, но расширяют способности языка. Делают язык более выразительным. Мы рассмотрим некоторые из таких расширений в Главе 8. Я собрал их вместе, в основном, потому, что одинаково их недопонимаю. Например, я думаю, что язык нужно обсуждать в концепциях человеческих языков.

Наконец, я хочу описать процесс реализации программы на языке машины. Т.е. процесс загрузки и саморазвертывания программы.

Я надеюсь, что вам понравятся изложенные идеи. В частности, я надеюсь, что Вы согласитесь, что программа, которую я описываю, в каком-то смысле оптимальна, т.к. следует объективным закономерностям.

Пытаясь говорить просто, я затянул свои объяснения. Я надеюсь, что вы не сочтете это злостным нарушением Основного Принципа. Легче было сказать обо всем этом сейчас, чем возвращаться потом. Если вам действительно удобно, вы можете использовать мои подпрограммы. Но, если вы путаете то, что полезно, с тем, что необходимо, ваши программы будут расти бесконечно.

Я не использую блок-схемы. Я никогда не любил их, поскольку считаю, что они местами избыточны, а местами недостаточны. Кроме того, они подразумевают большую жесткость в структуре программы, чем существует реально. Я буду давать конкретные рекомендации, но я буду использовать слова, а не блок-схемы. Блок-схемы лишь отняли бы время - и у меня, и у вас.

...

Прежде, чем читать дальше, посмотрим, какие еще книжки стоит посмотреть.- G.


Последний раз редактировалось: Gudleifr (Сб Окт 05, 2019 9:19 am), всего редактировалось 5 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Вт Авг 29, 2017 6:59 pm

Раз уж, разговор зашел о первоисточниках, то:

Это альфа и омега. Читать обязательно. Все что я встречал, кроме этого - в лучшем случае, рассуждения "а я бы сделал вот так".

1. Э.В.ДЕЙКСТРА - 1962 -- Математическое обоснование (Что такое FORTH? Leaf10ТЕМА #38Что такое FORTH? Leaf10).
2. CHARLES H.MOORE PROGRAMMING A PROBLEM-ORIENTED-LANGUAGE -- Первый работающий вариант (см. предыдущий и последующие посты).
3. LEO BRODIE STARTING FORTH -- Учебник для начинающих (Что такое FORTH? Leaf10CHM, 1.47МбЧто такое FORTH? Leaf10). Что такое FORTH? Leaf10ТЕМА #122Что такое FORTH? Leaf10
4. LEO BRODIE THINKING FORTH -- Философское обоснование (Что такое FORTH? Leaf10DOC, 3.98МбЧто такое FORTH? Leaf10). Что такое FORTH? Leaf10ТЕМА #124Что такое FORTH? Leaf10
5. С.Н.БАРАНОВ И Н.Р.НОЗДРУНОВ ЯЗЫК ФОРТ И ЕГО РЕАЛИЗАЦИИ -- Техническое описание (Что такое FORTH? Leaf10DJVU, 1.32МбЧто такое FORTH? Leaf10). Что такое FORTH? Leaf10ТЕМА #120Что такое FORTH? Leaf10

Как я их читал сам? Сначала (5) и остался в недоумении. Зачем все это нужно? В чем смысл?
Потом попалась (3). Понял, что FORTH это - здорово. Срочно надо его где-то брать. Как где?! В (5) есть же полный рецепт изготовления! Потом читал много разного, но ничего особо интересного не попалось.
Вдруг нашел (4). Надо же! Я всегда это говорил! Автор связно и логично изложил то, что мне только смутно мерещилось. (Это позднее я понял, что автор остановился слишком рано).
Затем попалось (2). Вот, откуда ноги растут! Все эти модные рассуждения всего-лишь смутные тени того, что планировалось изначально. Но, чего-то не хватает. Как-то странно автор пропускает обоснование своих основных решений.
Наконец, нашлось (1). Вот, чьи это уши! Вот о чем в (2) скромно умалчивалось!
***

Ладно, продолжаем читать Мура:


Последний раз редактировалось: Gudleifr (Сб Май 01, 2021 12:56 am), всего редактировалось 1 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:19 am

...

2. ПРОГРАММЫ БЕЗ ВВОДА

Самая простая возможная программа - та, которая не имеет никакого ввода. Это - дурацкое заявление, но если вы дадите мне шанс, я попытаюсь объяснить, чтобы затем дать полезные определения. Сначала рассмотрите слово "ввод". Я хочу использовать его в определенном смысле:
- Ввод - информация, которая управляет программой.

В частности, я не рассматриваю как ввод:
- Перемещение данных между устройствами компьютера. Например,
- - копирование ленты на диск, или диска в ОЗУ.
- Считывание данных. Это - опять обмен между устройствами. Например,
- - с перфокарты в ОЗУ.

Однако, при считывании данных может осуществляться и управление - для опознания данных или указания способа их использования. Например, литера в 80-й колонке может идентифицировать перфокарту. Это - ввод, остальная часть карты, вероятно, данные. Множество программ имеют ввод вида, который я буду игнорировать: например, операционные системы используют управляющие карты, чтобы определить, какие файлы и подпрограммы нужно использовать, и т.д. Такая информация - определенно ввод для операционной системы. Но для вашей программы они не ввод, хотя они и влияют на ее работу.

Чтобы уточнить понятие ввода, позвольте мне привести пример программы. Рассмотрим программу, которая строит кривую по нескольким точкам. Требуется ввести много параметров: число точек, единица квантования, число итераций и т.д. Эта информация могла бы быть включена в программу; если этого не было сделано, ее надо ввести. Координаты точек - не ввод, но они должны быть снабжены вводом, чтобы было можно их интерпретировать.

Программа, которая не имеет никакого ввода, может быть чрезвычайно сложна. Отсутствие ввода просто означает, что программа знает, что делать без того, чтобы спрашивать об этом. Вся необходимая для этого информация уже присутствует в коде. Если вы желаете заново пресобрать программу, вы можете эту информацию изменить.

Я буду рассматривать программы, отталкиваясь от их ввода. И я покажу, что небольшое усложнение ввода может обеспечивать существенное уменьшение сложности программы. С этой точки зрения, программа без ввода проста.

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

2.1. ВЫБОР ЯЗЫКА

Мы будем меньше заинтересованы выбором языка, чем большинство программистов.
По трем причинам:
- Во-первых, мы, в конце концов, определим наш собственный проблемно-ориентированный язык. На чем он будет базироваться - уже второй вопрос.
- Во-вторых, вы, скорее всего, не свободны в выборе языка. Ваша практика, вероятно, уже уменьшила ваш выбор до нуля.
- В-третьих, мы не будем говорить о проблемах, возникающих на уровне языка.
О последнем - по-подробнее. Я предполагаю, что вы уже компетентный программист. Я не буду учить вас, как работает компьютер, или, как язык скрывает компьютер. Я буду говорить о машинно-независимых и языково-независимых проблемах. Детали реализации я оставлю вам. Я не собираюсь писать программу, я покажу вам, как писать программу.

Я надеюсь, что вы достаточно хороший программист, чтобы думать по-компьютерному. То есть сразу переводите сказанное в термины действий компьютера: здесь - цикл, там - вычисление, выбор... Детали несущественны, но, в основном, структура программы т.о. вырисовывается.

Углубляясь в проблему, начинаете привязываться к своему компьютеру: эти данные с ленты, это останов цикла..., это - ветвление на три альтернативы. Вы переводите проблему на язык своей машины.

Наконец, вы переводите программу окончательно. Появились новые проблемы: FORTRAN не имеет нужного цикла, COBOL - ветвления на три, доступ к некоторым данным невозможен... Существующие языки очень сильно ограничивают процесс окончательного кодирования своими структурами.

Я не буду обсуждать эти тонкости, но останусь на уровне общего компьютерного жаргона. Мы не будем говорить и исключительно на метаязыке. Я могу указать вам на необходимость загрузить что-то в индексный регистр или перейти, если значение отрицательно, а уж вы переводите это на свой язык.

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

Разделаюсь с тремя наиболее популярными языками в одну строчку:
- FORTRAN - хорошо считает сложные выражения.
- COBOL - хорошо обрабатывает упакованные десятичные данные.
- ALGOL - имеет развитые структуры управления.
Каждый язык эффективно справляется со своей работой. Но если вам надо все разом, у вас проблема. Нас волнует эффективность. Если нельзя сделать что-то эффективно, лучше вообще не делать. Большинство нужных нам вещей на языках высокого уровня не реализовать. Часто они требуют прямого доступа к аппаратуре, которого компилятор дать не может. Например, при входе в FORTRAN-подпрограмму регистры сохраняются. Это не нужно, если на них никто не покушается. В ALGOL - наоборот. Подобные неудобства не оправдываются простотой вызовов подпрограмм.

Кроме того, все эти языки грешат лишними пересылками данных. Посчитайте сами: большинство операторов в программе - перемещения (присваивания). Целая философия заключается в том, чего можно достичь, просто перемещая данные. Если мы можем перемещать несколько значений одной инструкцией или копировать регистр сразу в несколько мест - мы не должны отказываться от таких возможностей.

Вы будете должны писать на языке ассемблера! Не всю программу, но те важнейшие части, которые мы будем обсуждать. Вы можете реализовать некоторые из них на FORTRAN, но это не окупит усилий. Я покажу, где можно будет обойтись высокоуровневыми подпрограммами, и вы увидите, что этим и стоит ограничиться.

Меня, как и всех вас, раздражают недостатки языка ассемблера. Я, как и все, не люблю перенабивать по 10 раз огромное количество перфокарт.
Но он здесь необходим для дела. Между прочим, я буду, для общности, называть ассемблер компилятором.

Позже я покажу вам, как писать программы на забытом языке: в кодах. Щелкать тумблерами на пульте прямого доступа в память. Иногда так будет удобнее всего.

2.2. ВЫБОР КОМПЬЮТЕРА

Конечно я не надеюсь, что вы можете свободно выбрать себе компьютер. И при этом я не собираюсь обсуждать аппаратные средства вообще. Но я хочу описать некоторые общие идеи.

Большинство из обсуждаемого может быть вполне запрограммировано на маленьком компьютере: ОЗУ в 4k 16-битных слов, типичный набор инструкций, аппаратные средства поддержки вычислений с плавающей точкой, если необходимо. Дополнительную память, которой может быть оснащен компьютер, буду обобщенно называть диском. Емкость диска для нас практически несущественна. Однако, важна способность копировать его на ленту или другой диск. Т.о. я имею виду компьютер с двумя накопителями, клавиатурой или устройством для чтения перфокарт для ввода и принтером или экраном для вывода.

Безразлично, будете ли вы запускать приложения последовательно на маленьком компьютере или параллельно - на мощном. Безразлично, насколько велики ОЗУ и диск. Разница не в скорости, а в потребной операционной системе и стоимости компьютера. Нужно, по-прежнему, 4k ОЗУ, диски и устройства ввода/вывода.

2.3. МЕЛОЧЕВКА

Теперь я готов объяснять, как писать программу. Независимо от языка или компьютера. Но, вероятно, не совсем так, как вы ожидали. Начнем с мелочевки. Без нее не будет хорошей программы, которую мы хотим. Помните Основной Принцип! Если вы не читали Введение, сделайте это сейчас.

Объявите все переменные. Даже в FORTRAN, где это не обязательно. Это здорово помогает при чтении программы, сразу видно, что и как вы используете.

Определяйте ссылки до того, как их использовать. Даже в FORTRAN, где это не нужно. Почему нет? Никто не любит читать задом наперед. Скачки вперед лучше свести к минимуму.

Делайте переменные по возможности GLOBAL. Почему нет? Вы можете экономить место и имена. Например, сколько I, J, и K Вам нужно? В большинстве случаев достаточно иметь их в единственном экземпляре, засунутом в COMMON блок.

Делайте отступы! Современные языки высокого уровня совсем не требуют, чтобы вы начинали строку в колонке x. Но вы делайте именно так! Это красиво! Бумага двумерная. Используйте это! И циклы сразу видны. И - ветвления. И ошибки виднее. Всегда используйте одинаковый шаг отступов (3 сойдет). Будьте педантичны. Небрежность наказуема.

2.4. ИМЕНА

Вы заметите, что насколько я уверен относительно одних вещей, настолько же неуверен относительно других. Точнее, может и уверен, но доходчиво выразить не получается. Это оставляет вам пространство для проявления самостоятельности.

Используйте осмысленные слова. К сожалению, осмысленность всеми понимается по-своему; но я всегда прав. Также, к сожалению, чем слова осмысленнее, тем они длиннее, это противоречит следующему абзацу.

Используйте короткие слова. Длинные лень писать и читать. В COBOL это означает, надо избегать составных слов (хотя, они иногда и полезны).

Предлагаю компромисс: придумайте свою систему сокращений и строго ее придерживайтесь. Если система не очень заумная, к ней и другие привыкнут. Можете, на всякий случай, описать ее в комментариях.

Используйте слова в правильной форме: существительные для переменных, глаголы для подпрограмм, прилагательные для... Не используйте бессмысленные слова (GO TO HELL). Их очарование быстро проходит, а смысла не прибывает. К тому же, их применение отдает эксгибиционизмом.

Комментируйте экономно! (Держу пари, вы этого ждали). Припомните последнюю виденную откомментированную программу? Большая была польза от комментариев? Как скоро вам надоело их читать? Осмысленные имена помогают сократить комментарии до минимума. Поэтому нельзя писать:

LA B . Load A with B

Привыкнув к дурацким комментариям, я могу пропустить и полезные. Комментарий должен описывать действие программы по-человечески. Действие в компьютерных терминах уже описано самой инструкцией. Должно быть что-то вроде:

COMMENT SEARCH FOR DAMAGED SHIPMENTS

Нужно давать осмысленные имена переменным и меткам (Осмысленные номера строк в FORTRAN?). Осмысленные имена регистров? Можно даже придумать несколько имен одной вещи, чтобы обозначить цель ее текущего использования. Правда, есть вещи, которые не нуждаются в именах. Счетчики? I, J и K; придумывать какое-нибудь EXC-CNTR смысла нет.

2.5 ПОДПРОГРАММЫ

Я ввел два термина, которые нельзя путать: подпрограмма - возвращает управление туда, откуда ее вызвали. Программа - возвращает управление в стандартное место. Иначе говоря, подпрограмму вызывают, а к программе переходят. На языке высокого уровня: CALL или ENTER против GO TO.

И что? Для подпрограмм требуется поддержка рекурсии. Вызывая подпрограмму из подпрограммы, вы должны где-то сохранить адрес возврата. Я уверен, что вы знаете много аппаратных и программных способов это сделать. Все они дороги.

Переход к программе, т.о. экономит место и время. Но только, если вам действительно никуда не надо возвращаться. Вызывать программу как подпрограмму еще более накладно.

Языки высокого уровня скрывают и автоматизируют весь механизм сохранения адреса. Лучше было бы это делать только в том случае, если действительно необходимо из подпрограммы вызвать новую подпрограмму.

Очевидно? Возможно. Но как часто это делается неправильно! Часто возникает проблема в случае рекурсивных вызовов.

Так что можно брать за основу и программы, и подпрограммы. Как мы передаем параметры? Опять, очень много вариантов. Стандартно: то, что влезает - в регистрах, остальное - через стек.

Наша цель - эффективная связь программ. Я надеюсь, что вы знаете сколько весит FORTRAN вызов. Я считаю это основным недостатком данного языка. У нас будет очень много подпрограмм, значит, вызывать их надо будет быстро.

Важен также вопрос о необходимости подпрограмм. Обособить в подпрограмму расчет некой законченной функции или использовать подпрограмму для избежания повторения одинакового кода? Первое приемлемо только при минимальной стоимости. Второе тоже может быть невыгодгно: подпрограмма из одной инструкции смешна; из двух - должна вызываться минимум из трех мест, чтобы оправдаться. Будьте осторожны!

Наконец, важно использовать эффективно регистры. Назначьте регистрам определенные применения и будьте последовательны. Переназначьте, чтобы избежать конфликтов. Не перемешайте данные из одного регистра в другой; берите значение со старого места.

Когда я говорю регистр, я очевидно подразумеваю язык ассемблера. Однако, вы можете моделировать регистры массивом.

...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:21 am

...

3. ПРОГРАММЫ С ВВОДОМ

Программа без ввода - программа для одной задачи. Программа с вводом может решать много задач - столько, сколько сушествует вариантов ввода. Я полагаю, что ввод используется для управления программой, и существует язык управления. Проблема этой главы в ее зацикленности. Непонятно с чего начать. Я сделал, что мог, но ссылки вперед остались. Особенно в следующем разделе.

Эта глава полна неожиданными для меня деталями. Но они нужны. Я только предостерегаю вас, не потерять за деревьями леса; структура, концепция программы - вот, что важно.

Как наша программа должна работать? Вы сидите за клавиатурой, набиваете ввод. Вы напечатаете строку, которую компьютер разбивает на слова. Он находит каждое слово в словаре, и выполняет код, прописанный в словарной статье, возможно используя параметры, также указанные в статье. Процесс чтения слов и их интерпретации, конечно не является чем-то необычным. Я просто попробую разбить этот процесс на краеугольные функции и выполнить их наиболее эффективно.

3.1. СУЩЕСТВИТЕЛЬНЫЕ И ГЛАГОЛЫ

Я упомянул словарь, и мы скоро его рассмотрим. Но сначала я хотел бы поговорить немного об отдельных словарных статьях. Мы будем читать вводимые слова, находить их в словаре, и выполнять их код. Специфический вид слова - литерал, слово, которое обозначает само себя:

1 17 -3 .5

Мы не будем хранить такие слова в словаре, но мы можем идентифицировать их по их виду. Такие слова действуют, как будто бы они есть в словаре, и у них есть код, пропихивающий их значение в стек. Некоторые другие слова работают со значениями на стеке:

+ сложить два верхних значения на стеке, оставить там вместо них сумму.
, напечатать число на вершине стека и удалить его из стека.

Например:

1 17 + ,

Т.е. поместить на стек 1, затем - 17, сложить их и напечатать сумму. Каждое слово исполняет свою ограниченную функцию независимо от любого другого слова. В целом же, получается что-то полезное. Например:

4837 758 + -338 + 23 + 4457 + -8354 + ,

Надо же, каждое новое число добавляется к накопленной сумме его предшественников, и, в конце, результат печатается. В этом - основная ценность нашей программы. Мы можем комбинировать слова, чтобы в итоге получить решение задачи.

Давайте рассмотрим употребленные слова. В человеческом языке мы бы назвали их:
- существительными - те, что кладут значения на стек;
- глаголами - те, что работают со значениями на стеке.

Все слова имеют код исполнения. Однако, в случае существительных, код делает очень немного: просто размещает число на стеке. Глаголы значительно разнообразнее. Они складывают значения, печатают их,.. или, что там еще прописано в их коде.

Конечно, существительные готовят аргументы для глаголов. Но глаголы этого не ждут. Они надеются, что аргументы для них уже подготовлены. Мы могли бы определить глагол, который читает следующее слово и использует его как аргумент; но не стали так делать. Это - не дело глагола, заботиться о своих аргументах; для этого перед ними помещаются существительные. На самом деле, это существенно упрощает нашу программу.

Мы можем продолжить классификацию слов. Глаголы имеют различное число аргументов:
- одноместные глаголы изменяют значение на стеке;
- двухместные глаголы берут два аргумента, и кладут на их место результат.

Арифметические операции - двухместные, функции, обычно, одноместные. Однако, разновидностей глаголов намного больше. Например, глагол ",", который печатает значение, не одноместный, так как удаляет значение из стека. Хотя он и имеет единственный аргумент. Можно классифицировать и с другого конца:
- разрушающий глагол удаляет аргументы из стека;
- неразрушающий - нет.

Одноместные и двухместные глаголы, как и глаголы типа ",", являются разрушающими. Глагол DUP, дублирующий вершину стека, является неразрушающим. Чаще глаголы разрушающие. Я сделал так специально, чтобы не мучиться с запоминанием, которые какие. И вам советую. Литералы - существительные. Мы можем определять и другие существительные; слова, которые используют свое поле параметра, чтобы размещать значение на стеке:
- константы размещают значение из поля параметра;
- переменные размещают адрес поля параметра.
Например, если PI константа, кладущая 3.14 на стек, то:

1. PI 2. * / ,

- кладем 1. на стек, кладем 3.14 на стек, кладем 2. на стек, умножаем (2. на PI), делим (1. на произведение), печатаем.
Константы особенно полезны, когда вы используете числовые коды. Имена легче запомнить, чем значения.

Важных существительных немного - литералы да переменные. Переменная выдает адрес, а не значение, как и положено в теории программирования. Однако, языки высокого уровня скрывают, что переменные могут использоваться двувмя разными способами:
- дать адрес, откуда взять значение;
- дать адрес, куда записать значение.

Константы способны только на первое (и прячут адрес, чтобы предотвратить второе). Вместо того, чтобы, как компиляторы, понимать переменную в зависимости от контекста, мы определим для них два глагола:
@ - заменить адрес на стеке значением по этому адресу;
= - записать по адресу на вершине стека, значение, лежащее на стеке под ним.
Т.о., если X - переменная,

X @ ,

- положить адрес X на стек, заменить его его значением, напечатать значение. А если,

X @ Y @ + ,

- сложить значения X и Y, напечатать сумму. С другой стороны,

X @ Y =

- запомнить значение X в Y. Но, если я напечатаю

X Y =

- запомниь адрес X в Y. Возможно это то, что я и хочу сделать.

Еще немного объяснений. Имя глагола @ не очень-то осмысленно. Сначала я хотел использовать VALUE. Но глагол используется столь часто, что больше одного символа для него слишком длинно.

Я настаиваю на применении этого глагола. Хотя вы можете вызывать его нявно, это будет бесполезным осложнением. Такой полезный глагол не должен быть невидим. К тому же, он позволяет вам хранить адреса в переменных, организуя косвенную адресацию.

X Y = Y @ @ ,

- запомнить адрес X в Y; положить на стек адрес Y, заменить его его значением (адресом X), заменить и его его значением (значением X), напечатать.

Я надеюсь, что объяснил про стек и глаголы. Надеюсь понятно, что все эти переменные, константы, одноместные и двухместные глаголы - лишь примеры. Вы можете использовать совершенно другие, удобные для вас виды слов. В этом, надо думать, и заключается программирование. Как только мы напишем нашу программу целиком, сами поэкспериментируете.

3.2 ЦИКЛ УПРАВЛЕНИЯ

Наша программа имеет простейшую структуру - единственный охватывающий цикл. Однако, код, организующий этот цикл, размазан по всей программе. Локализовать его ключевые моменты достаточно трудно.

Мы собираемся читать слово из строки ввода, искать его в словаре, и переходить к его программе. Каждая программа после выполнения вернет нас в начало цикла, чтобы читать другое слово. Этот возврат управления буду называть RETURN; Вы должны создать в вашей программе соответствующий макрос или метку.

Во-первых, этим вы обозначаете конец программы. Во-вторых, вы утверждаете, что здесь имеет место программа, а не подпрограмма. Наш RETURN это не тот RETURN, что в FORTRAN. Возврат из подпрограмм я буду обозначать EXIT.

В цикл должна быть встроена проверка исчерпания стека. Ее лучше вставить после RETURN, и только для тех программ, которые используют стек. Т.о. имеются две точки RETURN (фактически - три).

Наш цикл должен быть вылизан до совершенства. Его размер - это размер нашей программы. Вы будете исполнять маленькие программы, и заводить для этого громоздкий механизм не хочется. В особенности, вы должны исключить все проверки, кроме проверки стека.

Отметим еще одну важную программу: программу ошибки. Всякий раз, когда обнаруживается ошибка, программа переходит на ERROR, к коду, который печатает ошибшееся слово и сообщение об ошибке. Затем последует очистка стеков и ввода и обычный RETURN.

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

Наличие человека-оператора здесь необходимо. Независимо от того, что за ошибка случилась, вам не надо думать. Спросите пользователя. Например, он напечатает слово, которого нет в словаре. Что делать? Спросите его: напечатайте слово и сообщение об ошибке (в этом случае "?"). Он пробует сложить два числа, а на стеке только одно: напечатайте слово и "STACK!". Он обращается к памяти за пределами выделенной ему области: напечатайте слово и "LIMIT!".

Конечно, вы не должны требовать от пользователя того, на что он не способен. Что он должен делать, получив сообщение "MEMORY PARITY"? Но он всяко лучше, чем ваша программа, знает, что делать в случае его ошибки. И, конечно, лучше вас решит, что является проблемой, а что - нет.

Между прочим. Т.к. вы проверяете стек только после возврата из программы, вы узнаете об его исчерпании слишком поздно. Т.о. переполнение или исчерпание стека не должно вызывать фатальной ошибки. Хорошее решение состоит в таком размещении областей памяти, чтобы при переполнени стека залезать в стек возвратов, а при исчерпании - в буфер сообщений. Стек возвратов исчерпаться не может.

3.3. ПОДПРОГРАММА WORD

Как же работает наш цикл управления? Обсудим первую из его задач - чтение слова. Что такое слово? Под словом можно подразумевать много чего. Здесь, слово - цепочка символов, ограниченная пробелом. Она извлекается из строки специальной программой.

Рассмотрим общепринятые способы реализации чтения. В FORTRAN, например, чтение производится не по словам, а по полям. Считываются литеры, расположенные в определенных столбцах. Для нас существенен порядок слов, а не их позиционирование. Однако, кое-что мы при этом и теряем, например, возможность считать слово из одних пробелов. Все наши данные должны быть явны, к этому надо привыкнуть. Не используйте соглашения о вводе, которые имеют неявные параметры.

Давайте напишем подпрограмму WORD. Ей нужны два указателя: текущего положения курсора чтения и места, куда будем писать прочтенное слово. Перемещение считанного слова обязательно из соображений выравнивания и редактирования.

Пропускайте литеры до появления первого не-пробела. Считывайте литеры до появления пробела. Перенесите считанное слово в нужное место с необходимым выравниванием. Если в вашей машине символьное выравнивание, вас может удивить мое требование выравнивания. Я делаю это для ускорения процедуры поиска; выровненные строки можно сравнивать не по-символьно, а по-словно. Если в компьютерное слово вмещается шесть символов (или даже два), намного эффективнее сравнивать их большими кусками.

Вы можете захотеть установить максимальную длину слов. Разумеется, равной длине самого длинного слова, которое может вам пригодиться. А вдруг кто-то введет еще более длинное слово? Можно просто обрезать, если не хотите делить слово на части (Глава 8 ). Можно выделять место с запасом. Можно разбивать длинные слова. Возможно, вы захотите обрабатывать части слов. Предельная длина должна быть достаточно большой - от 10 до 20 символов, чтобы это не сильно ограничивать ваш ввод. Нужно предусмотреть место для завершающего пробела.

Слова, ограниченные пробелами... Вам это может не понравиться. Например, арифметические выражения часто не имеют пробелов между словами. Мы обсудим это в Главе 9. Позвольте мне только заметить, что мы можем использовать в словах самые замысловатые символы. Мы хотели бы, чтобы нормальными словами считались:

1,000 1.E-6 I.B.M. B&O 4'3" $4.95

3.3.1. ВВОД-ВЫВОД СООБЩЕНИЙ

Подпрограмма WORD читает символы. Откуда она их берет? Я надеюсь, что у вас есть клавиатура, а не только читалка перфокарт. Существует два вида клавиатур - с буферизацией и без. Клавиатура с буферизацией ничего не передаст в компьютер, пока вы не нажмете клавишу конца ввода. Клавиатура без буферизации передает символы, как только их клавиши нажимаются. Ваше железо может также буферизировать или нет ваш ввод.

Мы можем хотеть читать каждый символ более, чем один раз, поэтому нам нужен буферизированный ввод. Даже если вы можете обрабатывать сиволы по мере поступления, не делайте этого. Храните их в буфере сообщений.

Выделите буфер сообщений на одну строку. Его размер - максимальная длина входного/выходного сообщения и, если вы планируете использовать принтер со строкой 132 символа, сделайте буфер не меньше.

Если вы организуете буферизацию, сделайте обработку забоя. Опечатки - вещь частая. Если ваше железо это не обеспечивает, сделайте сами. Возможно, придется добавить лишний просмотр ввода, но это меньшее зло.

Рассматривайте конец сообщения как слово. Такое же, как все слова, ограниченные пробелами. Конкретная реализация зависит от железа. Нужно, чтобы оно читалось и выполнялось как и обычные слова. Оно очень нужно.

Кроме клавиатуры, вам нужно иметь устройство вывода: принтер или дисплей. Оно тоже может быть буферизованным или нет. В отличие от ввода, здесь буферизация нам не нужна. Однако, если в наличии несколько конфликтующих устройств, она понадобится. В этом случае, для единообразия, моделируйте буферизацию там, где ее нет.

Одного буфера достаточно и для ввода, и для вывода. Значит, выделять второй не следует. Одновременно ввод и вывод не происходят. Имеются исключения, но редко. По крайней мере, они нежелательны.

Нам, однако, нужна логическая переменная (1 бит), показывающая остался ли еще в буфере необработанный ввод. Его полезно переустанавливать как можно чаще. Позже мы к этому вернемся.

Нам нужна подпрограмма, вызываемая достижением конца ввода. И подпрограмма вывода готового выходного сообщения. Если возможно, они должны опираться на возможности вашего железа. Совмещать вывод одного сообщения с подготовкой следующих? Выигрыш в скорости минимален, а проблем будет много.

3.3.2. ПЕРЕМЕЩЕНИЕ СИМВОЛОВ

Перемещение символов необходимая вещь, особенно при вводе и выводе. Например, WORD переносит символы из буфера сообщений в буфер слов. Проще сказать, чем сделать. Такая же проблема существует при переносе массивов. Но даже перенос массивов имеет смысл обсуждать только как перенос символов.

Определим два указателя: источника и приемника. О них нужно думать как об индексных регистрах, позже уточним. Определим две нужные подпрограммы (возможно, просто инструкции): FETCH загружает символ источника в регистр и продвигает указатель источника, DEPOSIT сохраняет символ из регистра в приемник и продвигает указатель приемника.

В зависимости от вашего компьютера, реализовать FETCH и DEPOSIT может быть очень просто или очень сложно. Если они весят больше, чем одну инструкцию, они должны быть оформлены в подпрограмму, поскольку используются часто. Комбинируя их, мы можем организовать перемещение. Однако, где-то между ними надо вставить анализ символа. Стандартная инструкция переноса, реализованная в железе, очень неудобна.

Указатели удобно хранить в индексных регистрах. Однако, надо обеспечить их неприкосновенность на время всего перемещения. Их нужно сохранять и восстанавливать, т.к. все время занимать регистры под указатели жалко.

3.4. ДЕСЯТИЧНОЕ ПРЕОБРАЗОВАНИЕ

Прочтя слово, мы ищем его в словаре. Если его там нет, значит это число. Число - слово специального вида, не нуждающееся в словаре, что с ним делать - очевидно. Код для числа просто размещает его значение на стеке. Стек обсудим дальше. Сначала определим, что такое число.

3.4.1 ЧИСЛА

Очень трудно точно сказать, что является числом, а что - нет. Вы напишете подпрограмму NUMBER для перевода чисел в двоичный вид, и эта подпрограмма и будет овеществленным определением числа. Если ей не удастся преобразовать слово в число, значит оно не является числом. Было бы глупостью сначала выяснять, число ли это, и только потом его преобразовывать. Эти два вопроса решаются в одном процессе.

Безусловно, являются числами цепочки из цифровых символов, возможно, с предшествующим минусом. Их обычно нужно преобразовать в двоичное значение. Например:

1 4096 -3 7777 0 00100 10000000 6AF2 -B

- десятичные, восьмеричные и шестнадцатеричные числа. Число не содержит в себе указания на основу счисления, но явно, что она должна быть больше, чем самая большая цифра числа. Т.е. основание счисления - первая трудность.

Есть числа и не такие простые: с фиксированной точкой, с плавающей точкой, целые двойной точности, сложные дроби и т.д. И такие числа могут иметь много различных форматов слова: с десятичной точкой, с подразумеваемый десятичной точкой, экспоненциальный, с суффиксами. Одно и то же слово может представлять различные числа в зависимости от контекста.

Одна из ваших главных задач - решить, какие числа вы будете использовать, как будете их форматировать, и как преобразовывать. Каждый вид должен однозначно распознаваться подпрограммой NUMBER, и для каждого вы должны обеспечить подпрограмму преобразования.

Я предлагаю руководствоваться следующими принципами: всегда нужны целые числа и отрицательные целые числа; запретите предшествующий плюс, он бесполезен в числе и полезен как слово; если вы имеете аппаратные средства для вычислений с плавающей точкой, разрешите и их; если такого железа нет, ограничьтесь числами с фиксированной точкой. Эти правила удобны для пользования и реализации.

Вам могут понадобиться и другие виды чисел:
45'6 = 45 футов 6 дюймов, целое число
1,000,000 - целое число
$45.69 - целое число.

Нельзя иметь форматы на все случаи жизни. Некоторые из них просто несовместимы:
3'9 = 3 фута 9 дюймов
12'30 = 12 минут 30 секунд угловой меры
12'30 = 12 минут 30 секунды, время
4'6 = 4 шиллинга 6 пенсов.

Основной Принцип! Числа с фиксированной точкой используются редко. Но они могут быть полезны. Но, если железо поддерживает вычисления с плавающей точкой, они избыточны. Однако, в противном случае, они позволяют минимальными средствами сделать очень много. Исключение - работа с числами в очень широком диапазоне.

Я убежден, экспоненты используются в компьютерах неправильно. Большинство обычно используемых чисел лежат в диапазоне от 1e-6 до 1e6. Такие числа могут быть представлены и в формате с фиксированной точкой. Т.о. плавающая точка здесь не необходима. Правда в физике бывают числа и 1e43, и 1e-13. Но это обычно бывает, когда выбраны неудобные единицы измерения или когда удобнее применять логарифмы.

Люди не используют вычисления с фиксированной точкой, потому что компиляторы им этого не разрешают. Мы пишем свой язык сами и можем себе позволить воспользоваться преимуществами этого подхода. Как это организовать? Выберите потребное число знаков после запятой. Вы сможете его, если надо, поменять, но не смешивайте числа с разными его значениями. Научите вашу подпрограмму NUMBER выравнивать числа по положению точки, дополняя с нужной стороны нулями. После того смело обращайтесь с ним, как с целым. Например (подразумевая три цифры после запятой):
1. = 1.000 = 1000
3.14 = 3.140 = 3140
2.71828 = 2.718 = 2718
-.5 = -.500 = -500

Я бы не беспокоился насчет округления, ну, если только вам оно сильно надо или ваше железо его легко делает. Складывать и вычитать такие выровненные числа можно без ограничений. А вот, после перемножения придется делить результат на степень десятки (в нашем случае - на 1000). Аппаратные средства обычно облегчают процесс; результат умножения - число двойной точности - уже в надлежащем положении для деления. Перед делением двух чисел, вы должны умножить делимое на степень десятки (у нас - на 1000). Это тоже легко.

Для хранения подобных чисел ячейка памяти лучше была бы побольше. Если ваше железо позволяет, можно использовать арифметику двойной точности. Легко. И намного легче реализации чисел с плавающей точкой. Вам, вероятно, придется писать собственные математические подпрограммы, но сейчас эти алгоритмы общедоступны. И они будут намного быстрее, чем их аналог с плавающей точкой.

Выравнивание десятичных знаков легко осуществить при вводе и выводе. Однако, вы можете предпочесть выравнивать двоичные разряды. Из расчета три десятичных позиции на десять двоичных. Выравнивающие деления и умножения тогда могут быть заменены гораздо более быстрыми сдвигами. Вы должны выбирать, что нужнее - скорость вычисления или простота преобразований. Или что труднее объяснить пользователю.

3.4.2. ПРЕОБРАЗОВАНИЕ ПРИ ВВОДЕ

Рассмотрим подпрограмму NUMBER подробно. Подпрограмму? Она вызывается всего один раз - в цикле управления. Т.о. это может быть просто фрагмент кода. Однако, она настолько сложна, что ее потребовалось логически обособить; нельзя также исключить возможность, что мне захочется ее вызвать и в другом месте. Подобные отклонения от канонов нужно описывать явно. Нормой для подпрограмм является большое число их вызовов.

Подпрограмма NUMBER имеет две входные точки: SIGNED - анализ первого символа на "минус" и обнуление накопителя, затем переход к NATURAL. NATURAL - цикл: проверить следующий символ на цифру, умножить накопитель на десять, добавить цифру. Повторять, пока не найдется не-цифра.

Итак NUMBER: установить указатель ввода на начало выровненного слова, вызвать SIGNED. Если символ - точка, сбросить счетчик и вызвать NATURAL для считывания дробной части, счетчик покажет, сколько цифр введено и как надо преобразовать число в форму с фиксированной или плавающей точкой. В любом случае применить результат, полученный в SIGNED, чтобы приписать числу правильный знак. EXIT.

Подпрограмма NUMBER должна останавливаться найдя:
- пробел - тогда, это число;
- что-то другое - это не число.

Числа:
0 3.14 -17 -.5

Не числа:
0- 3.14. +17 -.5Z X 6.-3 1.E3

В этих случаях NUMBER остановится не на пробеле. Накопитель будет правильно показывать распознанное на этот момент значение, но оно уже никому не нужно.

SIGNED/NATURAL здесь имеет право на звание подпрограммы, т.к. вызывается дважды. Кроме того, она может быть полезна и для других форматов чисел. Например (дюймы):
- После запроса SIGNED, если найден апостроф, умножить накопитель на 12, вызывает NATURAL. Если будет найдена точка - см. выше.
Если Вы хотите удостовериться, что число дюймов меньше 12, надо будет внести изменения.

В NATURAL накопитель умножается на 10. Используйте не константу 10, а значение переменной BASE. Тогда Вы сможете поменять BASE на 8 (или 16) и вводить восьмеричные (шестнадцатеричные) числа. Вы сможете даже записать там 2, чтобы работать с двоичными числами. NATURAL, проверяя на цифры, должен их сравнивать со значением BASE. Если BASE будет больше 10, то будет дополнительной проблемой распознать как цифры буквы A-Z. Но эта проблема местная и легко решаемая:
- Из номера символа вычитается номер символа 0. Если BASE - 16, символ-буква ищется в A-F.

NUMBER должна быть эффективной, по крайней мере, в распознании не-чисел. Уж очень много слов-не-чисел. Мы обсудим это в Главе 8. Также важно то, что вы исследуете выровненную копию слова. Имеются несколько причин для выравнивания: избегнуть неприятностей с указателем ввода, гарантировать место для завершающего пробела. Однако, тут тоже проблема: слишком длинное число может не поместиться. Потеряет свои правые цифры. Ошибка не будет выдана, но число распознается неверно. Впрочем, если об этом помнить, не такая это уж и проблема.

3.4.3. ПРЕОБРАЗОВАНИЕ ПРИ ВЫВОДЕ ТЕКСТ

Вывод чисел сложнее ввода на одну операцию. При вводе вы умножаете накопитель на 10 и добавляете цифру. Вы идете слева направо. При выводе вы делите на 10, выводите остаток и снова делите, пока число не уменьшится до нуля. Но вы получаете цифры справа налево, а печатать-то надо слева направо. Т.о. цифры надо где-то временно накапливать. Хорошее место - дальний конец буфера сообщений. Свободного места там хватит. Конечно, вы можете использовать стек. Заполнив свой временный буфер цифрами, вы сможете распечатать их подпрограммой TYPEB.

Вы захотите печатать отрицательные числа и дробные части. Запомните, что число отрицательное и работайте с его абсолютным значением. После того, как закончите, добавьте впереди минус. Для чисел с фиксированной точкой надо два цикла: сначала накопите столько цифр, сколько надо для дробной части, и добавьте десятичную точку; затем - цикл, описанный выше. Проверять исчерпание числа во время накопления дробной части не надо.

Имеет смысл, для красоты, проверить еще пару вещей:
- не печатать точку, если нет дробной части;
- не печатать нулевую целую часть.

Вы, наверное, создадите несколько словарных статей для вывода чисел в различных форматах. Например, для целых чисел, с плавающей точкой, комплексных. Однако, все фактическое преобразование должно быть сделано единственной процедурой, с параметрами для специальных случаев. Процедура, обратная NUMBER. Это возможно, т.к. у чисел гораздо больше общего, чем различий.

Если вы работаете с числами с фиксированной точкой, у вас уже есть переменная D для хранения размеров дробной части. Ее же можно использовать и при выводе дробной части. Дробная часть обрабатывается одинаково в обоих случаях. Даже для чисел с плавающей точкой хватит этого же буфера (если не предъявлять чрезмерных требований к точности).

Если вы хотите печатать отчеты - ровные колонки чисел - вы должны научиться выравнивать числа по правому краю. Что в нашем случае равносильно выравниванию по десятичной точке. Для этого нужна другая переменная - F, ширина поля. Это просто: после преобразования числа нужно посчитать нужное число пробелов и вызвать SPACE. Затем - TYPEB. При подсчете помните, что TYPEB всегда печатает после числа пробел. Т.о. между числами всегда будет минимум один пробел. Если одно из чисел не влезет в поле, оно все же напечатается целиком, отделенное пробелами - число важнее красоты отчета.

Конечно, можно было бы печатать все числа с выравниванием вправо, начиная с самой правой цифры. Но тогда вы будете нуждаться в буферизации вывода. Главное же возражение состоит в том, что вы не сможете печатать в свободном формате. Например, вставить число в текстовую строку. Свободный вывод без выравнивания - это то, что вам и надо.

Среди других словарных статей для печати: SPACE - снять со стека число и напечатать столько пробелов. Возможно даже отрицательное число - обратный сдвиг указателя вывода. Это полезно, если вы хотите забить выведенное TYPEB. Слово TAB - расчет количества пробелов, необходимых для достижения позиции указанной числом на стеке.

3.5. СТЕКИ

Вы должны будете организовать несколько стеков. Стеки работают по принципу "последним пришел - первым ушел". Он состоит из массива и указателя. Указатель указывает на последнее помещенное слово. Для размещения слова вы должны сначала увеличить указатель, а затем записать слово туда, куда он показывает. Чтобы взять слово из стека, вы должны, наоборот, сначала прочесть слово, а потом уменьшить указатель. Понятно, сам стек не сдвигается. Очевидно, указатель стека - индексный регистр, конечно, если вы сможете его на это выделить. Другое решение - использование косвенной адресации с автинкрементом/декрементом.

3.5.1. СТЕК ВОЗВРАТОВ

Здесь хранится информация для обеспечения возвратов. Например, адреса возврата для подпрограмм, если вызовы использовали индексный регистр. Стек идеально подходит для хранения адресов возвратов вложенных процедур. Позже мы приведем еще примеры информации для возврата. Объединить стек возвратов со стеком параметров нельзя. Они не синхронизированы. 8 слов, вероятно, для стека возвратов хватит.

3.5.2. СТЕК ПАРАМЕТРОВ

Или просто стек. Все числа, константы и переменные складывают сюда свои значения. Он для того и нужен - для обмена данными между программами. Каждая программа ожидает найти на стеке свои параметры, независимо от того, сколько их там всего и кто, и когда их туда положил. Стек явно должен быть не менее 16 слов.

Для указания на вершину стека нужен регистр. Обязательно:
- вы никогда не должны использовать этот регистр для других целей;
- этот регистр должен всегда содержать актуальное значение; никаких проверок и флагов его пустоты нет.
Это будет самая выгодная реализация стека.

Терминология:
- кладете слово на стек - стек растет;
- снимаете слово со стека - стек уменьшается;
- слово на вершине стека - верхнее слово.
- слово под вершиной стека - нижнее слово.

Слова, управляющие стеком. Очень полезные:
DROP - удаляет верхнее слово.
DUP - кладет копию верхнего слова на стек, т.е. дублирует верхнее слово.
SWAP - меняет местами верхнее и нижнее слово.
OVER - кладет копию нижнего слова на стек, т.е. поверх верхнего.

3.6. СЛОВАРЬ

Каждая программа с вводом должна иметь словарь. Даже программы без ввода часто имеют словари. Ведь последовательность операторов IF ... ELSE IF ... ELSE IF ... и есть такой псевдо-словарь. Если словарь маленький (статей на 8 ) и не растет, такая реализация выглядит даже разумной. Здесь важно утвердить понятие словаря, сосредоточить его код в одном месте и оговорить формат статей. Общее место плохих программ - их эквивалент словаря разбросан по всему коду, что увеличивает затраты времени, места и сложности.

Главное свойство словарных статей то, о котором вечно забывают. Каждая статья должна содержать программу для исполнения. Но, обычно, много статей делают одно и то же. Их число можно сильно сократить. Сделать каждую программу необходимой. А заодно, написать для каждой оптимальный код.

Конструкция IF ... ELSE IF - пример связи статей с программами.

3.6.1. ФОРМАТ СТАТЬИ

Имеются два различных способа организовать словарные статьи. Выбор между ними может зависеть от характеристики аппаратных средств, но я рекомендую второй. Главная особенность статей - то, что они бывают разной длины. Причем, различную длину имеют не только они, но и их отдельные поля.

Первая возможность: разбить статью на две части: одна фиксированного, вторая - произвольного размера. Фиксированные заголовки позволят ускорить поиск слов. Фиксированная часть должна содержать ссылку  на произвольную; конечно, вы так выбираете размер фикисованной части, чтобы сократить потребность в произвольной.

Однако, т.к. ввод имеет достаточно небольшой объем (даже с учетом определений), минимизировать время поиска введенных слов бесполезно. Вы можете получать большую гибкость, более простое распределение ОЗУ, и, в конечном счете, большуя скорость, храня статью как одно целое. Такой случай я и буду рассматривать.

В статье четыре поля: слово, исполняемый код, связь со следующей статьей и параметры. Обсудим.

Формат слова связан с процедурой его чтения. Поле для его размещения должно быть фиксированным, не больше, чем нужно NEXT (см. дальше), несколько машинных слов. Однако, некоторые приложения могут хотеть распечатывать слова из словаря. Тогда придется отказаться от усечения имен и хранить их в поле переменного размера. Лучше использовать строку с ограничивающим пробелом, чем строку со счетчиком. В статье слово должно расти назад, а поле параметров - вперед. Применять статьи фиксированной или произвольной длины - вопрос вашего понимания Основного Принципа.

Поле кода должно содержать, скорее, адрес программы, чем ссылку на таблицу или какой-либо идентификатор. Эффективность программы очень сильно зависит от того, как долго мы будем добираться до кода. Однако, небольшой размер вашей программы может позволить использовать не абсолютные, а более короткие - относительные - адреса.

Аналогично поле связи может быть короче, чем обычный для компьютера адрес. Но, все равно, лучше запоминать в нем абсолютный адрес следующей статьи, чем смещение до него.

Поле параметров обычно может содержать четыре вида информации:
- Число, постоянное или переменное, переменного размера. Природа этого числа определяется кодом слова.
- Массив. Размер массива может быть указан здесь же, но может быть прописан в коде.
- Определение: набор ссылок на другие словарные статьи.
- Машинный код, скомпилированный сюда при создании слова. Кроме того, что, вероятно, необходимо некое выравнивание, других ограничений нет.

3.6.2. СТРАТЕГИЯ ПОИСКА

Основной принцип поиска в словаре: он ведется назад - от самой последней до самых старых записей. Другого порядка в словаре просто нет. Это позволяет переопределять слова, вводя для них новые статьи. Нет никакого резона изобретать что-то иное.

Чтобы идентифицировать слово, разместите его (или его часть) в регистре, и сравнивайте на равенство с началом каждой статьи. Обычное арифметическое сравнение. Некоторые беспокоятся, что использование для этого сравнения с плавающей точкой может дать ложное совпадение. Вероятность этого ничтожна, игнорируйте.

Сравнение словами быстрее, чем по-символьное. Вероятность найти расхождение в начале слова гораздо больше, и концы слов можно сравнивать и с меньшей эффективностью.

Поиск в статьях фиксированной длины может быть реализован простым циклом. При применении связанного списка статей цикл поиска остается простым, но замедляется. Однако, скорость поиска может быть увеличена: использовать вместо списка хэш-таблицу. Находите хэш-функцию от слова и ищете не в полном списке, а только в одном из списков слов с совпадающими значениями хэш-функции. А последние заведомо очень короткие.

Число таких списков должно быть степенью двойки, 8 уже даст значительное ускорение. Хэш-функция может быть очень проста: сложите несколько первых символов слова и возьмите младшие разряды. Нормальное поле связи с предшествующим словом, все-таки, придется сохранить для обслуживания словаря. Подобная методика требует хранения таблицы ссылок на начала списков, но это маленькая цена за большую скорость.

Однако, оптимизация поиска не столь важна, и я против хэш-таблиц для небольших словарей (несколько сотен статей).

3.6.3. ИНИЦИАЛИЗАЦИЯ

Словарь заранее включается в вашу программу и, возможно, инициализируется вашим компилятором. Это особенно легко при использовании статей фиксированного размера. Правильно расставить ссылки, тем более при использовании хэш-списков, многим компиляторам не по силам.

В таком случае, надо написать простенький цикл для связывания. Он должен пробежать все пространство словаря, распознавая статьи по определенным сигнатурам (семерки в поле связи). Найдя, считает хэш-функцию и привязывает слово к спискам.

Это одноразовый код. Хотя он и может вызывать какие-то подпрограммы, но сам используется только при инициализации. Т.о. после выполнения, на его место вполне можно записать что-нибудь полезное. Например, буфер сообщений или дисковый буфер.

Возможно придется инициализировать и что-то еще, например нужные для чего-то определенного регистры. Весь код инициализации должен быть собран в одном месте.

3.7. ЯЗЫК УПРАВЛЕНИЯ, ПРИМЕР

Обычно, приложения становятся сложными быстрее, чем интересными. Но здесь может помочь язык управления. Сколь угодно сложное и гибкое поведение может быть доступно и простой программе.

Пусть, надо читать последовательный файл, выбирать некоторые записи, сортировать их, выдавать их - различными способами. Пусть, эти переменные определяют поля записей:

NAME AGE SALARY DEPT JOB SENIORITY

Определим глаголы:

LIST SORT EQUAL GREATER LESS

Каждое действие будет порождать временный файл, служащий исходным для следующего действия:

Список (в алфавитном порядке) всех служащих 6-го отдела:

6 DEPT EQUAL NAME SORT LIST

Сначала мы выбираем все записи 6-го отдела и копируем их во временный файл. Затем сортируем его по именам. Вносим результат в список.

Двойной список по старшинству, все служащие, работающие над проектом 17 в 3-ем отделе:

17 JOB EQUAL 3 DEPT EQUAL SENIORITY SORT LIST LIST

Список по возрасту, все служащие, чье жалованье большее $10,000 и/или чья выслуга меньше чем 3:

10000 SALARY GREATER AGE SORT LIST 3 SENIORITY LESS LIST

Несколько комментариев. Мы можем реализовать логическое "и", используя несколько глаголов выбора последовательно; но не логическое "или". Мы можем сортировать сразу по нескольким полям, если наша техника сортировки не будет избыточно перемешивать записи. Нам надо еще два глагола:

REWIND END

- вернуться к первоначальному файлу и закончить работу.

Можно придумать еще много чего, включая выбор и модификацию указанных записей. Это просто пример, я только хочу показать, как существительные и глаголы объединяются, чтобы обеспечить большую гибкость простой программы. Заметьте, как даже в таком простом примере мы использовали все наши инструменты: WORD, NUMBER, словарь, стек. Мы не размышляем на пустом месте, мы подкрепляем свои идеи написанием кода.

...


Последний раз редактировалось: Gudleifr (Ср Ноя 20, 2019 4:09 pm), всего редактировалось 1 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:25 am

...

4. ПРОГРАММЫ, КОТОРЫЕ РАСТУТ

Пока наш словарь был неизменным. Он заранее содержал все необходимые статьи, которые помещались в него при компиляции. Это не обязательно. Мы можем создать статьи, которые будут добавлять или удалять словарные статьи. Зачем?

Вы имеете программу, которая управляет приложением. Что вы печатаете, то она и делает. В Главе 3 мы научились печатать отчеты. Но вы могли бы хотеть видеть их в другом виде. Например, управлять выводом при помощи специального диалога.

Тут две проблемы. Во-первых, чтобы добавить новый код, вам надо перекомпилировать программу. Из-за немногих добавлений запускать заново компиляцию не хочется. Во-вторых, то, что мы добавим таким образом, будет в нашем словаре все время работы программы. Это порождает не столько проблему объема, сколько проблему сложности. Чем сложнее ваше приложение, тем сложнее делать его механизмы совместимыми. Например, чтобы выбрать уникальные имена для всех полей. В-третьих, если вы находите ошибку во вводе, вы должны повторно компилировать программу. Вы не имеете никакой возможности исправить ввод на ходу, хотя, конечно, вы могли бы определить статьи, чтобы ее обеспечить.

Если вы можете создавать словарные статьи:
- Вы можете легко изменять вашу программу - без пересборки, и не загромождая ее инструментарием;
- Вы можете тут же переопределить неправильную статью. Фактически, ваша программа приобретает новое качество. Вы начали с программы, которая управляла приложением. Теперь вы имеете программу, которая обеспечивает способность управлять приложением. Вы перешли с уровня языка на уровень мета-языка. Это - чрезвычайно важный шаг. Не делать, а управлять действием.

С другой стороны. Сначала были слова, которые выполняли куски кода, которые составляли вашу прикладную программу. Они вполне управляли процессом. Теперь добавились слова, позволяющие вам создавать прикладные программы. Они создают проблемно-ориентированный язык. Перемена небольшая, но она необратима. Из прикладного вы становитесь системным программистом.

Я не знаю, хорошо это или плохо. Вы уже конечно знаете - все зависит от приложения. Я думаю, что любое сложное приложение требует своего языка. Не языка управления, а языка, описывающего его действие.

Пример: симулятору не нужен язык управления. Важно уметь описать моделируемую систему. Непосредственно решаемая проблема нуждается в языке, который может описать проблему. Компилятор определяет язык программирования. Компилятор компиляторов описывает язык программирования компиляторов. Компилятор компиляторов компиляторов? Вот, в чем вопрос!

Позвольте мне теперь предположить, что перед вами проблема, которая требует описательного языка. В каких словарных статьях вы нуждаетесь?

4.1. ДОБАВЛЕНИЕ СЛОВАРНЫХ СТАТЕЙ

Допустим, вы хотите расширить ваш словарь; и что вам действительно это надо. Как создать словарную статью? Вспомните цикл управления: он читает слово и ищет его в словаре. Если вы хотите определить слово, вы не должны позволить управляющему циклу его увидеть. Вместо этого прочесть это слово и использовать его для создания словарной статьи - до выполнения RETURN для возврата в цикл управления. Т.о. цикл управления этого слова не увидит. Используем подпрограмму WORD. Такое слово, создающее статью, назовем словом, определяющем следующее слово.

По большому счету, создание словарной статьи - это связывание слова с его кодом. Вспомним, что для каждой статьи нужно создать четыре поля: слово, его адрес кода, связь, и (возможно) параметры. Слово мы получает от подпрограммы WORD; связь, это адрес предыдущего слова; параметры мы берем из стека. Мы могли также брать адрес со стека, но более удобно иметь отдельное слово для создания словарных статей определенного типа. Адрес кода новой статьи будем брать из поля параметров определяющего слова.

Как бы не запутаться. Мы имеем статью, которое записывает в поле адреса кода новой статьи содержимое своего поля параметров. Например, мы хотим определить константу:

0 CONSTANT ZERO

0 помещен в стек; код слова CONSTANT читает следующее слово - ZERO - и строит для него словарную статью: связывает его с предыдущей статьей, сохраняет 0 со стека в поле параметров, копирует в поле адреса из своего поля параметров адрес кода, который будет выполнен при обращении к ZERO. Скорее всего, этот код будет помещать на стек содержимое своего поля параметров. Таким образом для каждого вида статей нужно создать определяющее слово, хранящее адрес нужного вида кода. Так как все определяющие слова похожи, то напишем для них подпрограмму ENTRY. Она будет получать адрес кода в виде параметра, и создавать новую словарную статью (за исключением поля параметров, т.к. оно зависит от вида слова).

Примеры возможных определяющих слов:
0 INTEGER I - целая переменная, инициализируемая нулем, кладет на стек адрес своего поля параметров.
1. REAL X - вещественная переменная, инициализируемая 1.
8 ARRAY TEMP - 8-словный массив, заполняется нулями; крадет на стек адрес его первого слова.

Я должен подчеркнуть - "возможные". Различные приложения требуют различных определяющих слов; даже одни и те же слова в разных приложениях могут иметь разный смысл. Но вы можете создавать столько видов существительных, сколько вам надо, и при помощи них создать сами существительные. Создание универсального набора существительных бессмысленно. Это вечная проблема компилируемых языков, как ни пытаются они предусмотреть все случаи, все равно кому-то хочется большего.

Например:

0 8 INDEX J, где J - индекс, изменяющийся от 0 до 8. Кладет на стек текущее значение.

Если вы добавите соответствующие глаголы, чтобы увеличивать, проверять и сбрасывать J, вы получите мощное средство индексации.

Или:

3 VECTOR X 3 VECTOR Y 9 VECTOR Z

И арифметические глаголы, чтобы получить арифметику:

X Z = Z Y + - конкатенация X и Y в Z.

X Y Z *C - перемножение X и Y с записью в Z.

Все, что вам нужно, вы можете определить. Определить все Вы не сможете. Основной принцип!

4.2. УДАЛЕНИЕ СТАТЕЙ

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

Если вы научились добавлять статьи в словарь, то, захотите научиться и избавляться от них. Удалять ошибочные статьи или просто освобождать место. В конце концов, ваш словарь конечен. Вариант Закона Паркинсона: каждый словарь будет расширяться, пока не заполнит все доступное место.

Есть только один способ удалять статьи. Удалить все статьи начиная с какого-то места словаря. Удаление статей по одной породило бы кучу дырок в памяти. Упаковать словарь для закрытия этих дырок, значит получить кучу проблем с пересчетом абсолютных адресов. Не использовать абсолютные адреса - неэффективно и избыточно.

Удаление этой и всех последующих статей - вполне удовлетворительное решение. Доказано практикой. Обычно определения добавляются группами, нашли ошибку - исправили - перезагрузили группу. Добавляете по одному? Тоже работает - проверили - стерли - набили заново. Освободить память? Тоже, вроде, получается. В каждом случае, вы, скорее всего, хотите избавиться от всех последних статей.

Одно исключение - определяющие слова. Они слишком глубоко закопаны. Такое бывает. Но тут уж ничего не поделаешь.

Как происходит удаление? Просто отмечаете место словаря, начиная с какой-то точки, как свободное. Однако, вы должны переопределить начала цепочек поиска слов. Тут необходим маленький цикл, удаляющий из цепочек все адреса, пока не будет достигнут адрес, меньший адреса точки очистки.

Если вы используете статьи фиксированного размера, то нужно только переустановить указатель свободного места, связей никаких нет.

Удобный способ определить точку очистки, разместить там специальную статью. Ее код удалит себя и все, что введено позже. Например,

REMEMBER HERE

Когда вы напечатаете HERE, оно удалит себя и все, что за ним. HERE не нуждается в поле параметров, если вы не используете статьи фиксированной длины (тогда надо где-то хранить указатель на область хранения переменных частей). Это - наш первый пример определения глагола.

4.3. ОПЕРАЦИИ

Вспомните про стек. Нужны кое-какие слова простейшей арифметики. Язык управления в них не особо нуждается, но вычислительную мощность они повышают. В качеств логических используются значения TRUE (1) и FALSE (0). Вспомните определения стековых терминов.

Одноместные операторы: изменяют верхнее значение.
MINUS - изменение знака.
ABS - абсолютная величина.
ZERO - если ноль - TRUE, иначе - FALSE.
NONZERO - если ноль - TRUE, иначе - без изменения (т.е. FALSE).

Двухместные операторы: снимают со стека верхнее и заменяют нижнее результатом операции над обоими.
+ - сложить верхнее и нижнее.
* - умножить нижнее на верхнее.
- - вычесть верхнее из нижнего.
/ - разделить нижнее на верхнее, оставить частное.
MOD - разделить нижнее на верхнее, оставить остаток.
MAX - если верхний больше нижнего, заменяет нижнего верхним.
MIN - если верхний меньше нижнего, заменяет нижнего верхним.
** - возвести нижнего в степень, указанную верхним.

Это только примеры. Вы определяете те операции, которые полезны для вас. Имейте в виду, аргументы должны быть загружены на стек до выполнения операции. Числа загружаются на стек автоматически. Константы - тоже. Примеры:
1 2 +
PI 2. *
1 2 + 3 * 7 MOD 4 MAX
1 2 3 + *

Нотация - как у настольного калькулятора. Ее называют бесскобочной или обратной польской записью, но суть проще - такова специфика работы со стеком. Обычную алгебраическую нотацию осуществить сложнее (8.2).

Другие двухместные операции - отношения (оставляют на стеке логическое значение):
= - равны?
< - верхний больше нижнего?
> - верхний меньше нижнего?
>= - верхний не больше нижнего?
<= - верхний не меньше нижнего?

Логические операции включают одноместную и несколько двухместных:
NOT - если верхний FALSE, заменить TRUE; иначе заменить FALSE.
OR - логическое "или".
AND - логическое "и".
IMP - импликация.
XOR - логическое "исключитающее или".

Ваш стек должен иметь фиксированный размер слова. Однако, действия, упомянутые выше, могли бы работать и с целыми, и с фикированной точкой, и с плавающей точкой, и с числами двойной точности, и с комплексными, и с векторами... Логические переменные, вообще, вмещаются в один бит. Ясно, что размер слова стека должен вмещать самое длинное из нужных вам чисел. Совсем неясно, как различать какого типа число на стеке.

Один путь состоит в том, чтобы определить отдельные операции для каждого вида чисел:
+ - сложение целых и с фиксированной точкой (это одно и тоже).
+F - сложение чисел с плавающей точкой.
+D - сложение чисел двойной точности.

Другой выход - хранить в слове стека вместе с числом информацию о его типе. Это делает код операций намного сложнее и поднимает проблему ошибок типа. Я рекомендую не проверять аргументы и определить отдельные операции; так проще. Обычно вы одновременно работаете с числами только одного типа, и никакой проблемы не возникает.

Не пользуйтесь арифметикой со смешением типов. Это не нужно, не удобно и очень затратно. Для громоздких чисел (комплексных, двойной точности) вы можете помещать на стек не значение, а их адрес. Однако, это ведет к 3-адресным операциям с результатом, записываемым в один из аргументов. И это, в свою очередь, ведет к осложнениям с константами.

Вообще, тема арифметики неисчерпаема. И многие решения будут взаимно несовместимы. Основной Принцип!

4.4. ОПРЕДЕЛЕНИЕ СТАТЕЙ

Приступаем к более сложным вещам. Описываемый здесь механизм обязательно нужно реализовать. Он обеспечивает важнейшее свойство проблемно-ориентированного языка - определять одни вещи через другие. Т.е. придумывание аббревиатур, заменяющих целые предложения. Вы же помните, что я характеризовал слова как сами по себе простые, но мощные в комбинации. Как же они комбинируются?

Определение начинается со слова ":", затем следуют другие слова, и заканчивается определение словом ";". Слово ":" определяет следующее за ним слово через слова, которые идут дальше. Например:

: ABS DUP 0 LESS IF MINUS THEN ;

Определение слова ABS. Получение абсолютного значения верхнего числа. О чем и говорят идущие следом слова.

Определение довольно неуклюжее? Тем более, для выполнения этой операции есть специальная команда процессора. Вы совершенно правы, определения часто неуклюжи. Но они позволяют нам создавать слова, придуманные по ходу дела. Имея небольшой набор базовых слов мы сможем обработать ввод любой сложности. Наличие определений, это - главное различие между языком управления и прикладным языком: язык управления должен включать все свои инструменты изначально, прикладной язык может сам создавать свои инструменты.

Определение работает просто и тупо. Адреса слов, входящих в определения записываются в поле параметров создаваемого слова. А когда новое слово будет выполняться, куски кода по этим адресам будут вызваться. Этого достаточно для создания статьи с любым нужным поведением.

Прежде чем углубиться в детали, еще немного общих мест. Вспомните, что код слова - программа, а не подпрограмма. И все же, здесь последовательность слов работает, как последовательность подпрограмм, после выполнения одного слова цикл управления возвращает нас в точку вызова следующего. Ряд адресов подпрограмм, которые выполняются одна за другой?

Еще одна тонкость: я говорю "выполнение слова", хотя подразумевается выполнение кода, связанного со словом. Или даже более точно, выполнение кода, адрес которого записан в поле кода словарной статьи слова. Сокращение не только удобно, оно уравнивает слово с машинной командой, которая может быть выполнена. И действительно, полезно думать о слове как о машинной команде: команде для компьютера, который моделируется нашим реальным компьютером. Давайте называть этот мнимый компьютер виртуальным. Т.о. когда вы печатаете слова, вы печатаете инструкцию виртуальному компьютеру. Цикл управления описывает логику процессора виртуального компьютера.

Продолжая аналогию, получаем, что определение является подпрограммой виртуального компьютера. И процесс определения определения эквивалентен компилиляции этой подпрограммы. Мы возвратимся этой аналогии позже.

Ведение термина "виртуальной машины" упрощает понимание других определенияй. Именно он надоумил меня на применение в определениях техники компилирования. Однако, что полезно программистам, запутает не-программистов. Так что я предпочитаю термин "определение" для этого типа статей и фразу "определение одного слова через другие".

Механизм определений чрезвычайно мощен. Зато, труднообъясним. Их практическое удобство трудно предвидеть теоретически. Вы заканчиваете писать нелепо простое приложение, и обнаруживаете, что вы использовали дюжину определений а глубина их вложения может достигать восьми. Но писать было очень просто - благодаря определениям.

Имеются несколько свойств, которые происходят из аналогии между определениями и последовательностями подпрограмм. Во-первых, вас совершенно не интересует, как реализовано слово, также как вас не интересуют подробности реализации подпрограммы. Во-вторых, одно определение может использовать другое. То есть вы можете использовать механизм вложения подпрограмм без выяснения как организуются вызовы и возвраты. Вы можете даже использовать рекурсивные определения. В-третьих, вы можете легко передавать аргументы, так как они находятся на стеке. Вам не нужно волноваться о том, что какой-то из них пропадет. На стеке можно хранить и временные переменные текущей подпрограммы.

Конечно вы платите за это удобство, хотя намного меньше, чем вы платили за подпрограммы FORTRAN. Цена - цикл управления. И все. Выполнение кода происходит со скоростью компьютера; однако получение адреса следующего куска кода требует приблизительно восьми инструкций. Вот почему я призываю оптимизировать цикл управления.

Заметьте, что, чем длиннее куски кода слов, тем незначительнее потери. Это - принцип языка управления. При уменьшении фрагментов кода до размеров кода цикла управления потери достигают 50% и выше. Это - цена прикладного языка. Обратите внимание, однако, что 50%-потери обычны для операционных систем и для обычных компиляторов.

Я предлагаю компромисс. Закодируйте критические части вашей программы, и используйте определения для остального. Использование определений, скорее, для управления, чем для исполнения, делает вычисления недорогими. А т.к. легкость их написания сокращает траты времени и усилий, то все просто замечательно.

...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:26 am

...

4.4.1. ОПРЕДЕЛЕНИЕ ОПРЕДЕЛЕНИЯ

Определение статьи при помощи ":" проходит как и создание прочих статей. Предлагаем EXECUTE в качестве адреса кода и выполняем подпрограмму ENTRY для создания новой статьи. Про код расскажу позже. Затем устанавливаем переключатель STATE. Цикл управления должен быть изменен для проверки STATE: если он сброшен (0), слова исполняются, как было описано выше; если же он установлен (1), слова компилируются. Повторю: если вы хотите вводить определения, ваш цикл управления должен и выполнять, и компилировать слова. Если вы планируете использовать определения с самого начала, вы должны соответственно программировать цикл управления. Попытайтесь реализовать переключатель с наименьшими потерями; выполнять слова вы будете гораздо чаще, чем компилировать.

Компиляция проста. Проведя поиск в словаре, вы получаете адрес статьи. Добавьте этот адрес в поле параметров. Два замечания: мы уже имеем механизм создания словарных статей. ENTRY создает все поля статьи, кроме поля параметров. Указатель словаря DP указывает на свободное место словаря. Все, что вы должны сделать, чтобы скомпилировать слово, это сохранить его адрес туда, куда указывает DP и продвинуть DP. Также заметьте, что мы сохраняем адрес статьи, а не адрес кода. Так мы имеем доступ не только к коду, но также и к полю параметров, и, даже, к полю слова.

Про компиляцию слов хватит. Что с компиляцией чисел? Число, встретишееся в программе, относится к литералам. А литералы - проблема для любого компилятора. К счастью, мы можем определять наш виртуальный компьютер так, чтобы он мог обращаться с литералами. Вы должны снова изменить цикл управления, чтобы проверять STATE в момент, когда число успешно конвертировано.

Определим понятие псевдо-статьи. Псевдо-статья - это статья, которой нет в словаре. Т.е. статья есть, но в списках поиска ее нет. Т.о. ее никогда не удасться найти. Такое решение принято для того, чтобы добавить статьи, нужные для работы виртуального компьютера, но не замедлить процедуру поиска слов в словаре.

Как вы уже догадались, при компиляции литералов будет скомпилирована псевдо-статья. Следом записывается само число. Результат - инструкция виртуального компьютера двойной длины. Код псевдо-статьи должен взять число и положить его на стек. Т.о. скомпилированные литералы при выполнении будут работать так же, как и при их непосредственном исполнении.

Заметьте, что, если вы используете литералы различного размера, вам будут нужны различные псевдо-статьи; заодно обсудим размер компьютерного слова. Длина слова для виртуального компьютера должна быть около 12 бит. Этого хватит для прямой адресации словаря более, чем на 1000 статей. Если слово вашего компьютера длиннее 18 бит, вы должны будете упаковывать несколько инструкций вашего виртуального компьютера в одно машинное слово. Это, возможно, неудобно, т.к. DP должно будет адресовать что-то более мелкое, чем машинное слово. Но, зато, вы сэкономите много места.

Для экономии места Вы могли бы хранить наиболее часто встречающиеся литералы в виде констант:

1 CONSTANT 1

Эта константа будет найдена намного быстрее, чем уйдет на конвертирование числа. И будет компилироваться одинарной инструкцией. С другой стороны, вы потеряете место на создание новой статьи.

Слова будут компилироваться пока не встретится слово ";". Оно компилируется как обычно, но еще сбрасывает STATE, заканчивая компиляцию. Кроме того, оно делает кое-что еще.

Заметьте, что, когда мы компилируем определение, мы каждое слово ищем в словаре. Если мы поищем в словаре слово, которое сейчас определяем, мы его немедленно найдем. Т.о. получив рекурсию. Если именно это вы и хотели, прекрасныо. Однако, гораздо удобнее таким образом переопределять слова. Т.е. трактовать ссылку на определяемое имя, как ссылку на предыдущую статью с таким же именем. Например,

: = SWAP = ;

Здесь я переопределяю глагол "=", чтобы обрабатывать аргументы в обратном порядке. Я мог бы придумать новое слово для той цели, но "=" имеет удобное мнемоническое значение.

В любом случае, это легко реализовать. Пусть ":" блокирует поиск самой последней статьи. И пусть ";" его разблокирует. Если вы хотите использовать рекурсивные определения, вы можете вместо ":" использовать ":R" - тоже, но без блокировки, ";" будет подходить для обоих случаев. Позже я приведу другое решение.

4.4.2 ИСПОЛНЕНИЕ ОПРЕДЕЛЕНИЯ

Я назвал код исполнения определения EXECUTE. Он должен изменить порядок исполнения команд виртуальной машины.

Напомним структуру цикла управления: подпрограмма NEXTw предоставляет адрес словарной статьи; это слово исполняется; выполнившись, оно, в конечном счете, возвращает управление NEXTw. Та же процедура требуется для исполнения определения, за исключением того, что NEXTw заменяется на NEXTi. Если NEXTw читает слово и ищет его в словаре, NEXTi просто извлекает следующий адрес слова из поля параметра определения.

Таким образом, вам нужна переменная, которая идентифицирует способ поиска. Одной из реализаций является определение переменной NEXT, которое содержит адрес NEXTw или NEXTi. Если вы перейдете по адресу из NEXT, вы войдете в соответствующую процедуру. Поэтому одной из задач EXECUTE является сохранение адреса NEXTi в NEXT, в результате чего последующие записи будут получены другим способом.

Конечно, NEXTi должен знать, где найти следующий адрес. Здесь аналогия с виртуальной машиной расширяется добавлением счетчика команд. Если вы определяете переменную, предпочтительно индексный регистр, с именем IC, оно может действовать точно так же, как счетчик команд на реальном компьютере. Он указывает место, где записан адрес слова, которое будет исполнено следующим, и должен продвигаться по мере выполнения.

Теперь понятна работа NEXTi: получить адрес из IC, передвинуть IC на следующую позицию и вернуться к той точке NEXTw, которая исполняет код статьи (или компилирует его, в зависимости от обстоятельств). Если вы вообще будете определять свои статьи, то эта процедура будет использоваться постоянно. Поэтому NEXTi следует оптимизировать за счет NEXTw. В частности, код, который выполняет (компилирует) код, должен быть перенесен в NEXTi из NEXTw. Это сэкономит NEXTi один прыжок - 20% цикла управления, не считая исполнения кода самих слов.

Теперь вернемся к коду EXECUTE. Очевидно, что в дополнение к переключению на NEXTi он должен инициализировать IC. Но сначала он должен сохранить его старое значение. Процесс аналогичен вызову подпрограммы виртуального компьютера. Очевидным местом для сохранения IC является стек возвратов. Хотя он используется и для других целей, конфликтует не возникает. Если одно слово выполняется из другого, ясно, что текущий IC должна быть сохранен. В противном случае будет некуда возвращаться.

В этом процессе задействована еще одна программа. Код, выполняемый для ";" должен вернуться из определения. Это просто означает, что он должен восстановить IC из стека возврата. Однако он также должен восстановить значение NEXT, которое было установлено в NEXTi командой EXECUTE. Вы можете сохранить старое значение NEXT в стеке возврата и ";" может найти его там. Возможно, проще - позволить начальному значению IC быть нулевым и действовать как флаг для восстановления NEXT в NEXTw. Ибо при выполнении определений NEXT всегда будет содержать NEXTi. Только при возврате из определения, созданного в исходном тексте, NEXTw должна вернуться. Поскольку при чтении исходного текста IC не используется, такое вполне возможно.

Это все, что нужно сделать. Сочетание EXECUTE, NEXTi и ";" обеспечить мощный и эффективный механизм подпрограмм. Обратите внимание, что слово может не только исполняться, но и быть скомпилированным в другое определение, как было указано выше - в зависимости от значения STATE. Также обратите внимание, что выполнение слов, может породить компиляцию других слов. То есть может понадобиться доступ к DP. Таким образом, хотя IC и DP схожи в использовании - DP указатель записи адресов, IC - указатель чтения адресов - они могут потребоваться одновременно. Даже, если вам не хватает индексных регистров, не пытайтесь объединять их.

4.4.3. УСЛОВИЯ

Слово ":" устанавливает переключатель STATE цикла управления; теперь цикл будет компилировать слова, а не выполнять их. Слово ";" компилируется, но также вызывает сброс STATE, завершая процесс компиляции. Следующие слова теперь будут выполняться.

Таким образом, мы видим исключительность ";", потому что оно во время компиляции не только компилируется, но и исполняется. Конечно, его можно исполнить и в режиме исполнения (оно просто сбросит IC).

Tcnm и другие подобные слова, исполняющиеся во время компиляции. Эти слова управляют этой самой компиляцией. От них требуется нечто большее, чем просто компилируемый адрес. Например, таковы слова для ветвления программы.

Не буду плодить абстракции в этом тонком вопросе и просто приведу примеры слов, которые нашел полезными. Как всегда, вы можете выбирать свои собственные соглашения, но они, вероятно, будут напоминать мои по своим основным эффектам.

Определите слова IF, ELSE и THEN, чтобы разрешить следующий формат условного выражения:

логическое значение IF истинное утверждение ELSE ложное утверждение THEN продолжить

Слова имеют знакомую мнемонику, но, по сравнению с ALGOL, переставлены. Это выражение может использоваться только в определениях словТакое утверждение может появиться только в определении, поскольку IF, ELSE и THEN компилируют коды.

Во время компиляции определения слово IF выполняется. Компилирует прыжок вперед. Теперь я должен отвлечься и определить прыжки. Инструкция перехода для виртуальной машины похожа на литерал. Встроенный литерал - это инструкция двойной длины. Первая половина - адрес кода, вторая - параметр. В случае прыжка: код модифицирует IC значением параметра.

Значение параметра суммируется с IC: положительный означает скачок вперед, отрицательный - назад. Так работает относительная адресация в некоторых реальных компьютерах.

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

Хорошо, вернемся к IF. Встретившись во время определения, он компилирует адрес псевдо-статьи условного перехода, за которой кладет 0. Поскольку он не знает, как далеко прыгнуть. Адрес же того места, куда положен 0, запоминает на стеке. Помните, что стек в это время не используется, потому что мы в режиме определения. Позже стек будет использоваться теми словами, которые мы определяем, но в данный момент мы можем использовать его для нужд компиляции.

Теперь посмотрите на ELSE. Во время определения он компилирует адрес псевдо-статьи безусловного перехода, за которой следует 0. Но затем он сохраняет текущее значение DP - места куда будут компилироваться следующие слова - по адресу со стека. Таким образом, он разрешает условный переход, скомпилированный предшествующим IF. На самом деле, конечно, нужно записать не сам DP, а расстояние от команды прыжка до него - относительное смещение, но принцип ясен. В свою очередь, ELSE оставляет в стеке адрес своего прыжка.

Наконец, мы подошли к THEN. Он, подобно ELSE, разрешает прыжок, прописанный на стеке. И связка ... IF ... ELSE ... THEN работает! Причем, THEN безразличтно, разрешает ли он прыжок скомпилированный IF или ELSE. Значит, ELSE-часть можно опустить без каких-либо последствий. Кроме того, поскольку для хранения адресов прыжков используется стек, IF-ы могут быть вложенными. Единственное ограничение - все адреса, в конце концов, должны быть определены. Т.е. THEN-ов должно быть столько же, сколько IF-ов (ELSE-ов, понятно, может быть меньше.

Конечно, в этой технике нет ничего необычного. Все компиляторы генерируют скачки вперед таким способом. Несколько необычно применять его для составления инструкций для виртуального компьютера. Но, похоже, это лучший способ.

Рассмотрим сопутствующие конструкции. Очень часто логические выражения связываются операциями AND или OR.

Можно посчитать выражение заранее, до того, как предпринимать действия:

a b AND c AND IF ... THEN

где a, b, c - логические выражения; на Алголе это выглядело бы

if a and b and c then ...

Но можно и прерваться, если выражение уже заведомо ложно:

a IF b IF c IF ... THEN THEN THEN

Эффект тот же: если a, b и c истинны, то выполняется условный оператор. В противном случае - нет. Каждый IF компилирует скачок вперед, который разрешается соответствующим THEN. И, все равно, каждому IF должно соответствовать свое THEN. Это один из видов вложенных IF ... THEN. Очень эффективно.

Аналогично:

a b OR c OR IF ... THEN

на ALGOL:

if a or b or c then ...

Истинность всего выражения заведомо достигается при нахождении первого истинного:

a -IF b -IF c IF HERE HERE ... THEN

где надо как-то обеспечить:

: HERE SWAP THEN ;
: -IF NOT IF ;

Первый HERE разрешает прыжок от истинного b, второй - от a, THEN - от ложного c. Т.е. -IF перепрыгивают не нужные условия, а IF - само действие.

Это кажется неуклюжим, но я не нашел более простого решения. Если вам регулярно надо использовать что-то подобное, вы, несомненно, изобретете нужные инструменты. И даже - для более сложных конструкций.

4.4.4 ЦИКЛЫ

Я приведу еще пару примеров слов, исполняемых во время компиляции. На этот раз примеры прыжков назад, используемых для построения циклов.

Рассмотрим пару слов BEGIN и END, которые используются в выражении типа:

BEGIN ... условие END

BEGIN сохраняет DP в стеке, таким образом отмечая начало цикла. END генерирует условный обратный переход к месту, оставленному BEGIN. Таким образом, он компилирует адрес псевдо-статьи условного перехода, вычитает DP+1 из значения на стеке стеке и компилирует этот относительный адрес. Если условие ложно во время исполнения, вы остаетесь в цикле. Когда становится истинным - выходите.

BEGIN и END создают цикл, порождаемый логическим условием. Давайте определим еще один цикл - со счетчиком:

а б DO ... CONTINUE

a и b - параметры цикла загружаемые на стек. DO действует как BEGIN. Для CONTINUE требуется новая псевдо-статья, которая проверяет два верхних слова в стеке на равенство и выполняет переход, если они не равны. Во время компиляции CONTINUE компилирует адрес этой псевдо-статьи, а затем вычисляет расстояние прыжка, как это делал END. Т.о. CONTINUE использует другой условный переход: тот, который проверяет стек на равенство, а не на ложь. Это также неразрушающая операция, если ее аргументы не равны. Когда они становятся равными и заканчивают цикл, он их убирает.

Очевидно, a и b должны как-то модифицироваться в теле цикла, чтобы тот все-таки завершился. Например, цикл от 1 до 10:

10 0 DO 1 + ... CONTINUE

Где 10 - конечное значение, 0 - начальное значение счетчика. Счетчик, очевидно, доступен для использования в теле цикла (просто операцией DUP). При каждом прохождении цикла счетчик инкрементируется. Когда он достигнет 10 (и тело цикла выполнится), CONTINUE прервет цикл и уберет со стека обе десятки.

Или - так:

11 1 DO ... 1 + CONTINUE

Здесь счетчик увеличивается в конце цикла, а не в начале. При достижении 11 цикл сразу останавливается.

Естественно, счетчик может изменяться и другими способами. Но всегда сигналом остановки будет равенство. Конечно, надо быть осторожным.

Можно улучшить конструкцию, введя дополнительную проверку на равенство (и условный прыжок) в DO, если у вас ситуация избыточных циклов встречается часто.

4.4.5. РЕАЛИЗАЦИЯ

Я надеюсь, что вы поняли, зачем нужны слова, выполняющиеся во время компиляции. Ветвления и циклы всегда полезны. Причем метки для их реализации совершенно не нужны. На примере HERE мы видели, что управление стеком позволяет вкладывать конструкции самым разным образом. Однако, с другой стороны, меток у нас более, чем достаточно, ведь, словарные статьи - это они и есть.

Вернемся к проблеме, которую я замял. Как распознать те слова, которые должны выполняться на этапе определения? Т.е. IF, THEN, BEGIN, END и т.д. должны так или иначе прервать обычный цикл управления, стремящийся их откомпилировать. Я упомянул переключатель, значение которого отличало выполнение от компиляции. Давайте устанавливать подобный флаг (1 бит) в каждой словарной статье:
1: выполнить,
0: компилировать, анализируемый совместно с переключателем. Для данной статьи объединяем значение и переключатель по "или"; если любой из них 1, выполняем слово, иначе компилируем.

Это корректно и, даже, эффективно. Ведь мы же хотим сделать цикл управления эффективным! Работает для всех слов, включенных в словарь. К сожалению, это не работает для слов, которые я приводил в некоторых примерах, а, ведь, они были просты. Значит, будем устранять проблему. Обратите внимание, я пытаюсь объяснить то, что сам плохо понимаю.

Я сам не понял, что меня насторожило в SWAP. Cлово "!" мертворожденное. Не пытайтесь понять, что я написал. Я сам не понимаю.

Вспомните определение:

: HERE SWAP THEN ;

Это слово должно выполняться на этапе определения. Но само должно определяться нормально. При выполнении HERE, SWAP будет стремится откомпилироваться, вместо того, чтобы выполниться. C THEN нет никакой проблемы, или есть? Выполняя HERE, мы выполним и THEN. Однако мы имеем проблему во время определения HERE, ведь THEN не захочет просто так компилироваться. Т.о. иногда мы хотим компилировать слова обязательные для выполнения; а иногда мы хотим выполнить обычные слова - даже во время определения.

Так, что делать? Держу пари, вы думаете, что я знаю ответ. Ваша вера трогательна, но мой решение не очень красиво. Оно работает, но с ограничением: Вы не можете выполнять во время определения литералы. Впрочем, зачем? Литералы должны копилироваться. Как это работает?

Рассмотрим переключатель STATE. Нормально - 0; ":" делает устанавливает его в 1, указывая на компиляцию. Давайте определим новую определяющую статью ":!". Она работает подобно ":" с двумя исключениями:
- Устанавливает флаг статьи в 1 - отмечает обязательное для исполнения слово.
- Устанавливает STATE в 2; заставляя компилироваться все слова, т.к. слова исполняются, если значения переключателя и флага равны. ";" остается тем же самымм; он сбрасывая STATE в 0. Это решает все наши проблемы, кроме SWAP. Как мы выполним слово, которое обычно компилируется? Определим новую статью - "!". Пусть он исполняет последний скомпилированный адрес и удаляет его из скомпилированного кода. Теперь мы можем переписывать определение HERE

:! HERE SWAP ! THEN ;

Это будет работать. Правила:
- Все слова обычно выполняются.
- Только слова с установленным флагом могут исполняться в момент определения.
- Любое слово после которого стоит "!", исполняется.
- Слова с установленным флагом определяются через ":!" вместо ":".

С литералами это не проходит. Потому, что их инструкция состоит из двух слов. Конечно, можно было бы хранить где-то адрес последней инструкции, но не такая уж это важная проблема. Кроме того, в том случае не работала бы последовательность из нескольких "!".

4.5. КОДОВЫЕ СТАТЬИ

Я объяснил, как компилировать инструкции для виртуального компьютера. А как быть с компиляцией для настоящего компьютера? Конечно, вы можете это сделать. Но, вероятно, не будете.

Работает Основной Принцип. Если вы добавляете код в вашу программу, вы добавляете максимальную мощность и гибкость. Вы можете все, что может компьютер. Это прекрасно, но вам это очень редко надо. И затраты растут. Для этого вам понадобится штук десять статей, плюс мнемоники инструкций. Кроме того, вы еще должны будете изобретать прикладной язык компиляции.

Мы написали программу поддержки языка. Если нужен новый код проще добавить его в программу и перекомпилировать. Конечно, вашей целью может быть написание приложения, компилирующего код. Или ваши пользователи хотят иметь код по своему вкусу. Только тогда Основной Принцип оправдает такое усложнение.

С другой стороны, если вы научитесь компилировать код, вы сможете создавать новые арифметические операторы, новые типы существительных, компилирующие слова. В Главе 9 я покажу, как вы можете использовать код с пользой, достигая максималной эфективности. Но, все это крайние меры.

Как вы можете генерировать код? Сначала вы нуждаетесь в статье, создающей кодовую статью. Главное свойство кодовых статей - хранение кода в поле параметров. Адрес, попадающий в ENTRY, должен быть получен определением (назовем его CODE) и показывать на начало куска кода. DP не подходит, т.к. должно быть еще зарезервировано место под заголовок статьи.

Нужна статья для сохранения числа по адресу DP. Мы использовали эту подпрограмму уже несколько раз, строя переменные и определения, но мы не оформляли ее в виде статьи. Я предлагаю слово "," хотя так мы уже называли слово печати числа. Все что оно делает, это кладет верхнее число со стека в поле параметров. Наши коды, ведь, тоже числа. Вы будете строить их на стеке и затем записывать. Такое слово окажется полезным не только для компиляции кода. Им будет удобно инициализировать самые разные данные.

Теперь вы можете понять мои давнишние опасения. Вы будете должны создать множество словарных статей, которые компилируют полезный код, но не вызываются напрямую. Например, RETURN: когда программа закончена, она должна перейти в цикл управления. Однако, где в памяти входная точка цикла управления? Так что вы должны будете создать статью для RETURN, чтобы она связалась при компиляции.

Аналогично, если вы создаете компилирующие слова, вы должны создавать и статьи для хранения кода, адрес которого будет передаваться ENTER. Благодаря этому, к вашим WORD и NUMBER сможет получить доступ кто угодно. Кроме того, надо будет определить статьи для используемых переменных: D и F для вывода; STATE и BASE. Проблема состоит в том, что вы делаете доступными извне внутренние точки программы. Вы, поэтому, должны обосновать их доступность их полезностью.

Вот и поговорили. Теперь о том, как строить инструкцию. Она состоит из нескольких частей - код операции, индекс, адрес, которые надо как-то скомбинировать. Это легко делать, но трудно спроектировать. Просто так копировать ассемблер не интересно. Это будет работа по созданию полноценного компилятора. Но все необходимые для вас инструменты уже есть - определения.

Вы можете без проблем написать определение, объединяющее (по "или") код операции и адрес и размещающее их. Если надо, вы можете преобразовывать абсолютные адреса в относительные или использовать страничную организацию. Вы можете все. Компилятор, он и есть компилятор - серьезная программа.

Мы обсуждали условные и циклические конструкции виртуального компьютера. Подобные методы можно использовать и здесь. На самом деле, я впервые применил стековое разрешение переходов для написания кодов моего реального компьютера. Когда превращал ассемблер в компилятор. Помните Основной Принцип.

Компилятор позволит определять новые виды существительных. Т.е. строить новые определяющие слова. Рассмотрим пример описанного выше. Напишем слово, умножающее верхнее число стека на константу.

Как обычно, требуется совместно использовать несколько специальных слов. В этом случае - ENTER и ;CODE . Вот так:

: UNIT ENTER , ;CODE 1 V LDA , SP MPY , SP STA , NEXT ,
2.54 UNIT IN
4. IN

В первой строке определяется слово UNIT (т.е. единица измерения). В следующей строке оно используется, чтобы определить слово IN (в дюймах). В последней строке при помощи IN в сантиметры переводится 4 дюйма. Эквивалентное определение IN

: IN 2.54 * ;

оно, конечно же проще. Но, зато, при помощи UNIT вы можете эффективно определить много подобных слов.

Первое из новых слов - ENTER. Оно вызывает подпрограмму ENTRY как всякое определяющее слово, но пишет 0 в поле адреса. Смотрим на определение UNIT. Слово ENTER обязательно. Оно производит псевдо-инструкцию двойной длины; адрес псевдо-статьи и 0. Во время выполнения псевдо-статья вызовет ENTRY (чтобы построить новую словарную статью), передавая ему 0 из второй половины псевдо-инструкции. Слово ;CODE - комбинация слов ";" и CODE. Оно заканчивает определение UNIT и сохраняет DP в поле адреса, установленное ENTER. Т.о. код, который следует за ;CODE, будет выполняться для всех статей, созданных UNIT. ;CODE знает, куда сохранять DP потому, что ENTER обязательно первое слово в подобных определениях и ;CODE знает, какое определение оно заканчивает.

Ограничение на расположение ENTER в начале определения незначительно. "," в UNIT нужна для размнщения константы. Другие существительные могли бы нуждаться в более сложном коде для формирования поля параметров.

Вы видите код после ;CODE - инструкции и адреса, обращающиеся в т.ч. к константе, размещенной ",". Я не хочу объяснять язык своего ассемблирующего компилятора, т.к. для вашей машины будет нужен другой.

Еще одна полезная идея. Вы можете определить новый вид констант - инструкции. Когда они исполняются, снимают со стека адрес, комбинируют его с инструкцией, хранящейся в поле параметров, и размещают результат. Таких инструкций понадобится много. И статей, ими созданных, тоже будет много.

Боюсь, пример здесь не поможет. Если вы не поняли, как делать кодовые слова, забудьте. Приложение с кодовыми словами будет слишком машинно-зависимым. Обычные определения гораздо удобнее. Код нужен только для доступа к специфическим возможностям вашего компьютера.

...


Последний раз редактировалось: Gudleifr (Сб Окт 05, 2019 9:31 am), всего редактировалось 1 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:27 am

...

5. ПРОГРАММЫ С ПАМЯТЬЮ

Конечно, не хочется набивать большой объем ввода. И заново создавать сотни статей. Следовательно, надо их где-то хранить, например, на диске (или барабане, или другом устройстве произвольного доступа).

В какой форме хранить статьи? Тут работает Второй Принцип - всегда сохраняйте информацию в виде, пригодном для редактирования. Прямое копирование статей на диск нарушит и еще один принцип - никогда не сохраняйте адреса. Вам при редактировании программы пришлось бы все их пересчитывать.

К счастью, есть решение. Сохраняйте на диске ввод, который порождает построение ваших словарных статей. Затем можно будет переключить программу ввода с чтения буфера сообщений на чтение диска. Эта глава покажет, как.

5.1. ОРГАНИЗАЦИЯ ДИСКА

Есть только один способ организации диска. Как ОЗУ разбито на большое количество слов, так диск разбит на большое число блоков. Как слово - минимальный квант чтения из памяти, так и блок - минимальный квант чтения с диска. В блоке 256 слов.

Блок содержит 256 слов потому, что для адресации слова достаточно одного байта, и потому, что если слова по 4 байта, то получается 1024 символа, что вполне по силам обычным устройствам отображения информации.

Другая аппаратура - другие размеры. Некоторые диски имеют определенный размер блоков. Размер Ваших блоков должен быть ему кратен. Доза хранимой информации должна быть разумной. Я считаю - не менее 512 и не более 1024 символов. 128-словные блоки подходят для слов в 6 или 8 байт.

5.1.1. ПОЛУЧЕНИЕ БЛОКОВ

Очевидны и некоторые другие принципы организации наших файлов произвольного доступа. Понадобятся ссылки на блоки. Они удобны, если являются абсолютными адресами блоков; иначе - очень неудобны. Абсолютные адреса дают сбой только, если блоки перемещаются. Это значит, что диск нельзя упаковывать. Мы соглашаемся, потому что и не собирались это делать.

Это означает, что если надобность в каких-то блоках исчезнет, на диске появятся "дыры". Их надо как-то заполнять. Это значит, что мы должны распределять дисковое пространство блоками.

Все адреса считаются, начиная с 0, включая адреса блокок (иначе Вам бы пришлось постоянно прибавлять и вычитать единицу). Однако, мы не можем использовать блок 0. Туда очень легко попадает мусор при ошибках. Посмотрите и убедитесь. Блок 1 удобно использовать сохранения данных между сеансами работы. Там же хранятся номер первого блока в списке освободившихся (первоначально 0) и номер последнего использованного блока (первоначально 1).

Вы захотите иметь возможность копировать свой диск на другой или ленту (для сохранности). Копировать нужно только то число блоков, которые были использованы, обычно их не более половины диска, иначе начинаются проблемы с пространством. Если Вы испортите блок 1, то перезагрузить придется все блоки. Никогда не копируйте только блок 1, результат вас обескуражит.

Вы захотите поместить на диск вашу объектную программу. Прекрасно! Это не займет много блоков. Если нужен автозапуск, то начать надо с блока 0. Однако, надо оставить возможность загрузки с дублирующего диска, т.к. блок 0 Вы быстро испортите. Перезагружать все блоки при порче блока 1 надо потому, что в нем хранится число использованных блоков. Иначе вы потеряете много блоков. Выберите путь минимизирующий ошибки и затраты. Полная перезагрузка приведет к тому, что вы запутаетесь, что изменяли, а что нет. Уж лучше перенабить утраченное за несколько часов.

Когда вам нужен блок, вы вводите слово GET, которое читает блок 1, кладет на стек номер первого блока из списка освободившихся, читает этот блок, переписывает его первое слово в блок 1, и переписывает блок 1. Первое слово, конечно, содержит адрес следующего блока в списке освободившихся блоков. Если этот список пуст (как сначала) GET увеличивает номер последненго использованного блока, помещает его на стек, и перезаписывает блок 1. GET тогда затирает новый блок нулями и перезаписывает его.

Несколько комментариев: число, возвращаемое GET на стеке - номер блока, готового для использования. Т.о. более не нужные блоки используются повторно. Сломать, конечно, можно все, но делать этого не следует. Не перемещайте блоки! Это, в конце концов, память произвольного доступа. Не забывайте затирать новые блоки нулями.

5.1.2. ОСВОБОЖДЕНИЕ БЛОКОВ

Чтобы освободить блок, поместите его номер на стек и напечатайте RELEASE. Его действие обратно GET - в 1 блок записывается номер освобождаемого блока, а в первое слово того - старый номер первого блока из списка освободившихся. Возможно, блок, который вы освобождаете, связан с другими блоками. Вы должны освободить и их. Удобный путь состоит в том, чтобы использовать первое слово как поле связи. Список освободившихся - частный случай такого списка. Для связывания: вы запоминаете номер блока в блок 1, возвращаетесь к блоку и сохраняете в нем старый номер из блока 1.

Не пытайтесь поддерживать индекс освободившихся блоков. Оно того не стоит. Если хотите, можете хранить длину списка освободившихся.

Если у вас несколько разных видов блоков, может быть полезно хранить код, указывающий тип блока в первом или втором слове. Вы можете тогда перебирать все блоки некоторого вида. Свободные блоки должны иметь код 0.

Сколько блоков вы можете иметь, определяется размером диска и размером поля, отведенного для хранения номера блока. Будьте осторожны! Вы можете обойти первое ограничение, так изменив вашу подпрограмму чтения, чтобы иметь возможность выбора одного из нескольких дисков. Для обхода второго, надо будет переформировать все ссылки в блоках.

5.1.3. ЧТЕНИЕ И ЗАПИСЬ ДИСКА

Я уверен, что вы умеете читать диск. Не берите только размер блока, который будет неудобен аппаратно. Если вы посмотрите на GET, увидите, что одновременно надо держать в ОЗУ два блока. Это - разумный минимум, позволяющий также легкое копирование из одного блока в другой. Однако, при большом размере ОЗУ разумным будет создать еще буферов, особенно если время чтения значительно.

Нужна будет таблица, показывающая, какие блоки находятся в ОЗУ: ваша программа чтения будет проверять эту таблицу перед чтением.

Вы не должны стремиться сразу записывать измененный блок. Довольно пометить его, как "требующий записи", в таблице загруженных блоков. Когда соберетесь загружать в буфер новый блок, тогда и запишите старый. Дело в том, изменения блоков в одиночку не ходят. Запись в последний момент сэкономит много времени. Конечно, возможно, что программа закончится по ошибке раньше, чем успеет записать блоки. Вы должны быть способны перезагружать программу без стирания буферов.

Конечно, многократные основные буфера подразумевают проблему распределения. Простой циклический алгоритм подойдет не хуже любого другого.

Если вы просматриваете данные последовательно, вы можете сэкономить много времени, считывая разом последовательные блоки. Однако, такая последовательность может быть легко случайно разбита. Эффективное решение: хранить в подпрограмме чтения номер последнего блока в последовательности и число загруженных блоков. Если блок не находится в ОЗУ и лежит в пределах диапазона, считывайте подряд столько блоков, сколько влезет. Дальнейшая оптимизация смысла не имеет, разве только сделать побольше буферов. В общем, все зависит от аппаратуры.

Вы неизбежно потратите много усилий, на реализацию чтения/записи. Помните Основной Принцип!

5.2. ТЕКСТ НА ДИСКЕ

Вы будете хранить много текста на диске - сотни блоков - но это, вероятно, намного меньше емкости диска. Остальное место может быть использовано для хранения данных вашего приложения.

Блок, который содержит текст (я подразумеваю - текст, пригодный в качестве ввода) содержит одну длинную строку символов. Если первые слова заняты под служебную информацию, текст начинается от них, до специального слова-завершителя (возможно - ;S). Такое слово применять гораздо удобнее, чем постоянно делать проверку на конец блока. Вы быстро привыкните его ставить.

Блоку, содержащему текст, удобно придумать особое название. Я назвал такие блоки SHEET-ами и SCREEN-ами. Определите слово READ, сохраняющее адрес ввода, блок и положение курсора на стеке возвратов; установите указатель ввода на первую позицию блока, номер которого находится на стеке. Определите слово ;S, чтобы восстановить первоначальный указатель ввода. Вот как вы пополняете свою программу вводом из блока 123:

123 READ

Однако... Вы должны изменить вашу программу WORD, чтобы иметь возможность считать блок в ОЗУ. Это затратно, но необходимо (конечно, чтение блока необходимо не при чтении каждого слова). Чтение блока понадобится, например, если один блок требует читать другой. Никакое другое решение этой проблемы не подошло, так что, пишите нужный код. Вы увидите, что ввод теперь больше происходит с диска, чем с клавиатуры. Вы будете читать много слов и много искать в словаре. Однако, это только микросекунды.

5.2.1. РЕДАКТИРОВАНИЕ ТЕКСТА

Никогда не храните на диске того, что не умеете редактировать! Откуда берется текст на диске? Не грузите его с перфокарт! Долой их! Печатайте. Редактируйте текст SCREEN-ов.

Вы должны быть способны работать со строковыми литералами. Это важно для редактирования. Рассмотрим простой пример. Однако он требует внимания. Разберитесь!

Эти определения вам придется набить дважды. Один раз - для словаря; другой - для экрана автозагрузки. Но вам, наверное, двух раз не хватит.

Я собираюсь показать откомментированный код EDIT, который использовал в одной из программ. Он использует некоторые необъясненные статьи. Они заимствованы из других программ.

0 C1 42 # :R RECORD

Здесь я строю описание поля RECORD: 42 символа длиной, начинается с первой литеры нулевого слова текущего блока. Я использую блоки в 15 строк по 42 символа; в слово влезает 6 символов, т.е. - 15 строк по 7 слов.

: LINE 1 - 7 * RECORD + ;

Глагол, который преобразует номер строки (1-15) в адрес. Надо модифицировать описатель RECORD при изменении порядка битов в слове. Т.о. строка 1 начинается со слова 0; 2-ая - со слова 7; и т.д.

: T CR LINE ,C ;


Если я напечатаю 3 T - я выведу 3-ю строку. T переводит каретку (CR), выполняет LINE, чтобы вычислить адрес, и копирует поле в буфер сообщений (,C).

: R LINE =C ;

Если я напечатаю " NEW TEXT" 6 R - я заменю 6-ю строку символьным литералом (текстом в кавычках). Ведущая кавычка помещает описатель строки в стек. R выполняет LINE, а затем - =C, чтобы сохранить строку в поле. Блок помечается, как требующий записи.

: LIST 15 0 DO 1 + CR DUP LINE ,C DUP ,I CONTINUE ;

LIST выведет полный блок: 15 строк по 42 символов, сопровождаемые номерами строк. Цикл DO-CONTINUE пробегает от 1 до 15. Каждый раз он делает CR, дублирует переменную цикла и вызывает LINE; печатает поле (,C); снова дублирует переменную цикла и печатает ее как число (,I).

: I 1 + DUP 15 DO 1 - DUP LINE DUP 7 + =C CONTINUE R ;

Если я напечатаю " NEW TEXT" 6 I - я вставлю текст, после строки 6. I должен сначала сдвинуть строки 7-14 вниз на одну позицию (строка 15 пропадет) и затем заменить строку 7. Сначала добавляет 1 к номеру строки, запускает цикл, от 14 до этой строки, строит два описателя поля LINE и LINE+7, и сдвигает поле (=C). Когда цикл заканчивается, запускает R.

: D 15 SWAP DO 1 + DUP LINE DUP 7 - =C CONTINUE " " 15 R ;

Если я напечатаю 12 D - я удалю строку 12. D должен переместить строки 13-15 на одну позицию вверх и очистить строку 15: опять цикл - от номера на стеке +1 до 15. Теперь перенос идет между LINE и LINE-7. Затем 15-ю строка заменяется пустой.

Итак. 10 строк ввода - и редактор готов. Может, он и не очень эффективен, но вы можете себе позволить переложить на машину свою работу. Глагол LINE - чрезвычайно полезный; такие полезные глаголы - обычное эмпирическое открытие. Глаголы ,C и =C - самые важные, они работают со строками не длиннее 64 символов. Заметьте, как одно определение ссылается на другое (R используется в I и D; LINE используется всеми). Заметьте, что I и D в чем-то подобны, но все же различны. И обратите внимание, как удачные глаголы сократили объем бумажной работы.

...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:34 am

...

6. ПРОГРАММЫ С ВЫВОДОМ

Надеюсь, вы запомнили, что сердце вашей программы - цикл управления. Он не только управляет, но и определяет философию построения программы. Как помните, он читает слово, находит его в словаре и выполняет его код; если не удалось найти, он пытается преобразовать его в число и положить на стек, если и это не удалось, сообщить об ошибке.

Пока я не объяснял, как выводится сообщение об ошибке; не потому, что это слишком просто, но потому, что вывод еще не обсуждался. Конечно, логичнее было бы рассказать о нем уже давно, ведь в нем нуждается даже цикл управления. Но технической возможности не было, только теперь мы узнали все необходимые детали. Частности оставляю вашей изобретательности.

Большинство компиляторов (и поэтому - большинство программистов) расценивают вывод как инверсию ввода. Например, FORTRAN использует те же самые операторы FORMAT и там, и там. Так?

Вы тратите время на сочинение сложного входного текста, программа тратит усилия на его понимание. Вывод намного проще. Его основная функциональность заключена в слове OK. Вы говорите с компьютером, а он в ответ едва похрюкивает.

Я утверждаю, что два этих процесса не имеют ничего общего, что компьютер не сочиняет выходной текст так как вы сочиняете ввод. В Главе 8 я буду описывать путь, которым ваша программа может составлять сложные сообщения. Хотя такая техника могла бы поддерживать диалог, она еще меньше похожа на интерпретацию ввода.

6.1. ПРОГРАММЫ ВЫВОДА

Вам нужно три подпрограммы вывода, но хватило бы и двух:
- вывод некоторого числа пробелов;
- вывод некоторого числа символов (TYPEN);
- вывод символов до пробела включительно (TYPEB). Последняя программа зависит от вашего формата словаря, поскольку для их печати, в основном, и предназначается. Конечно, они должны использовать те слова, которые мы уже определили.

Рассмотрим как пример сообщение об ошибке. Вы только что напечатали входное сообщение, каретка стоит на последнем символе. Сначала вам надо напечатать пробел. Затем - TYPEB для печати текущего слова. Оно вызвало ошибку и вам надо добавить к нему сообщение об этом. Для устройства без буферизации это проще. Снова - TYPEB для печати описания ошибки. Используйте описания покороче. Т.к. ошибок у вас будет много, удобно будет придумать для сообщения о них отдельное слово.

После обнаружения ошибки вы все очищаете и начинаете с начала. Продолжать дальше смысла не имеет - все равно придется переделывать. Очистите стеки. Это иногда неудобно, так как состояние стека могло бы помочь с локализацией ошибки. Но это удобнее всего остального. А вот словарь стирать не стоит.

6.2. ПРИГЛАШЕНИЕ

Я упомянул в Главе 3, что вы должны написать подпрограммы, чтобы посылать и получать сообщения. Теперь я должен подробно остановиться на том, как вы должны использовать эти подпрограммы.

Помните, буфер сообщений у нас один: и для ввода, и для вывода? Теперь это неудобно. Однако, это значительно упрощает мощные программы вывода сообщений Главы 8. В итоге, один буфер удобнее.

Подпрограмма посылки сообщения - SEND. Она посылает одну строку, добавляя в нее все обходимые симолы для перевода строки. Программа, которая получает сообщения - QUERY. Это - программа, а не подпрограмма. QUERY вызывает SEND для посылки сообщения, а затем ждет ввода. Обрезает символы возврата каретки. Устанавливает указатель ввода IP и переходит к NEXTW. Заметьте, что ваша программа может выводить при помощи SEND везде, где вам захочется. Однако, вводит только в одном месте - QUERY. Вы не имеете никакой возможности считать сообщение без вывода приглашения. Это, конечно, именно то, что нам надо.

Теперь позвольте мне описывать использование QUERY. Каждое входа сообщение заканчивается словом конца сообщения - непечатным символом, окруженным пробелами. Это слово имеет статью словаря, которая печатает слово OK и переходит к QUERY. Т.о. после интерпретации каждого входного сообщения, ваша программа напечатает краткое подтверждение - OK, "получил и понял" - и ждет дальнейшего ввода.

Заметьте, что, если входное сообщение приводит к выводу, оно уничтожает себя. Т.к. буфер у нас один. Поэтому слово, которое требует вывода, должно быть последним словом во входном сообщении, остальные просто не прочитаются. В частности, не будет прочитано слово конца сообщения, и ответ OK не будет напечатан. Это - то, что вы хотите: OK нужен только тогда, кода нет другого вывода.

OK должен появиться в той же строке, где было входное сообщение, отделенный от последнего введенного слова не менее, чем одним пробелом. QUERY не должен подтверждать прием сообщения переводом каретки, как делает большинство систем. Единственное подтверждение - OK при завершении интерпретации. Размещение OK в той же строке разграничивает ввод и вывод, и экономит место. Пользователь не должен печатать ввод, пока он не получит вывод. В многопользовательских программах надо это обеспечить. См. Главу 7.

Чтобы определить, имеется ли в буфере сообщений ввод, используется переменная EMPTY. QUERY должно сбросить EMPTY, и каждый вывод должен ее устанавливать. Фактически, глаголы вывода имеют много общего, и каждый из них заканчивается переходом к программе, которая делает следующее:
- Удаляет значение со стека. Каждый глагол вывода должен иметь аргумент, который к этому времени уже выведен. Здесь его надо удалить и проверить стек на исчерпание.
- Устанавливает EMPTY.
- Если NEXT содержит NEXTW, и SCREEN - 0, переходит к QUERY. Дальнейший ввод если и был, то уже потерян.
- Переходит к NEXT.

Заметьте, что, если слова поступают из определения или SCREEN-а, никакого конфликта не возникает. Только, если слова вводятся из буфера сообщений.

Имеются 2 места, где источник ввода меняется. Это делается в коде для ";" и ";S". ";" устанавливает NEXT в NEXTW. ";S" сбрасывает SCREEN в 0. Поэтому мы это и проверяем выше.

Сложность - плата за общий буфер сообщений. Еще про EMPTY. Если она истинна, значит, ввод был разрушен; но это не гарантирует, что в буфере есть выходной текст. Вывод мог уже быть послан. Если буфер сообщений пуст, печатаем OK перед переходом к QUERY.

6.3. СТРОКИ

Для меня они очень трудны. Это не числа, которые легко положить на стек.

Мое решение. Оставьте строку, где нашли. Положите на стек описатель строки: адрес первого символа и длину строки. Пропустите строку, передвинув указатель на ее конец. На самом деле, он передвинется, пока вы будете считать символы.

На что похожа строка? Например, так:

"ABCDEF...XYZ"

Строка заключена в кавычки. Внутри может быть что угодно, кроме кавычек.

Неприятность! Как вы распознаете строку? Конечно, по открывающим кавычкам. То есть вы хотите так переопределить WORD? Но тогда вы не сможете использовать кавычки для других целей. Намного лучше, сделать открывающие кавычки отдельным словом. Но пробел вставлять после него очень не хотелось. Получилось:

" ABCDEF...XYZ"

Лишний пробел раздражает, но в Главе 8, я сообщу вам, как его можно устранить. Так, что строка будет просто символами в кавычках.

Помните, что мы оставили строку там, где нашли, просто запомнив место. Т.о. мы должны использовать строку раньше, чем ввод будет уничтожен. Лучше - немедленно.

Что мы можем сделать со строкой? Я нашел им только два применения. Они похожи, но не совсем. Вы можете напечатать строку, или вы можете переместить ее в текстовое поле.

Напечатать строку легко. Определите статью, которая использует описатель на стеке, чтобы установить параметры для подпрограммы TYPEN.

Переместить строку труднее, но ненамного. Вы имеете 2 описателя на стеке: на вершине - описатель поля; ниже - описатель строки. Установите указатели источника/получателя и пререносите символы до тех пор, пока не исчерпаете меньшей из двух длин. Остаток поля назначения заполните пробелами. Не переносите больше символов, чем влезет в поле. Размеры будут совпадать очень редко. Усечение строки - это совсем не ошибка!

Научившись перемещать строки в поле, вы сможете также премещать из поля в поле. Для этого описатели должны быть совместимы. Если вам нечего делать, можете предотвратить перемещение из поля в строку.

Проблема состоит в том, чтобы избегнуть противоречий. Написать не оптимальный код, но просто работающий.

Т.о. мы дошли до описателей полей. Они должны быть полностью совместимы со строковыми.

6.4. ПОЛЯ

Мы говорили о разных видах чисел, требующих для обработки разных статей. Однако, все они имели дело с вычислением. Другой вид статей полезен для вывода. Я назвал их полями, т.к. они удобны для определения полей в записях данных.

В дополнение к описателю, поле нуждается в дополнительных параметрах, которые определяют формат вывода. Чрезвычайно полезно определить ширину поля раз и навсегда, и затем использовать ее автоматически во всех сообщениях. Также полезно иметь возможность сослаться на поле имени статьи поля.

Полезно положить, что поле помещает на стек адрес своей словарной статьи. Вспомните, что переменная клала на стек только адрес поля параметров. Если вы хотите имя поля - это адрес статьи. Если вы хотите формат - адрес получается из статьи. Хотите адрес поля - тоже пожалуйста.

Для этого нужны специальные слова. Например:
,NM - печать имени;
F - ширина поля;
@F - адрес поля.

Можно сделать F@ совместимым с @. Или сделайте так, чтобы @ работало и для полей. Вы можете захотеть отличать адреса переменных от адресов полей. Подобно тому, как мы различаем числа, и по той же причине чтобы операции (те же @ и =) работали правильно. Примените Основной Принцип.

...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:38 am

...

7. ОБЩИЕ ПРОГРАММЫ

Это не очевидно, но наша программа организовалась так, что идеально подходит для работы нескольких пользователей одновременно. Все основные проблемы диалоговой обработки были решены для взаимодействия с одним пользователем. Все, что принадлежит пользователю может быть занесено в его словарь. Различение пользователей - различение словарей.

Конечно, многопользовательность нужна не везде. Кажется, чем сложнее приложение, тем больше потенциальных пользователей. Приложение, которое заслуживает проблемно-ориентированного языка будет постоянно востребовано.

Перепрофилирование нашей программы на другое приложение тоже труда не составит. Наша схема экран-словарь позволяет легкую организацию многопользовательской работы.

Т.к. основная работа делается оператором в диалоге, т.е. очень очень медленно, можно без проблем общаться одновременно со многими пользователями, сохраняя данные заснувших на диске.

Затраты на поддержку многопользовательской работы все же существуют. Дополнительный код для переключения, дополнительное место под буфера и словари...- проще сначала отладить в однопользовательском варианте. И добавить многопользовательский режим при возникновении спроса. Иначе, программу изначально придется сделать менее симпатичной. Или наши усилия могут, вообще, никому не понадобиться.

Поэтому обсудим расширение работающей однопользовательской программы до многопользовательской. Вы должны тщательно соблюдать некоторые предосторожности. Помните Основной Принцип!

7.1. ПОЛЬЗОВАТЕЛЬ

Много пользователей - проблема. Конечно, одного процессора хватит на много пользователей. Но нужен какой-то механизм переключения.

Когда возможно переключение? Ясно, что тогда, когда пользователь читает вывод и набивает ввод, компьютер отдыхает. Плюс, паузы на доступ к устройствам ввода-вывода. При посылке одного сообщения мы можем составлять следующее. Но намного проще не пытаться оптимизировать. Чтение диска пользователем - тоже простой компьютера.

Я хочу описать все эти ситуации одной фразой. Я буду говорить, что пользователь передает управление компьютеру каждый раз, когда он печатает сообщение или обращается к диску. Это его добровольное действие и единственное время, когда он отказывается от управления. В частности, не имеется никакого кванта времени, который бы ему выделялся. По этой причине код должен быть реентерабельным. Однако пользователь будет уверен, что у него не отберут управление в момент, когда он не успел что-то закончить. Программа должна только правильно обрабатывать их ввод-вывод.

Как же переходит передача управления? Компьютер просматривает таблицы пользователей в тоисках готового. Таблица содержит адрес словаря пользователя и флаг готовности. Прерывание ввод-вывода просто устанавливает этот флаг. И если никто не готов, компьютер опять посматривает таблицу - больше ему делать нечего. Естественно, сразу после запуска программы еще никто не готов.

7.1.1. ПОМИМО ПОЛЬЗОВАТЕЛЯ

Каждый пользователь имеет строку в таблице готовности. Компьютер проверяет таблицу в поисках готового. Вы можете добавить в эту таблицу строки для непользовательских процессов.

Например, вы можете опрашивать телефонные линии в поисках сообщений. Лучше производить все связанные с приемом операции не сразу по прерыванию, а поставить их в очередь. Т.к. это не очень срочно. Добавим этот процесс в таблицу. Когда делать будет нечего, дойдет дело и до него.

Каждый такой процесс должен иметь строку в таблице и маленький словарь, чтобы хранить параметры; адрес возврата, регистры и т.д., в том же самом формате как и пользователь. Такие процессы - полный аналог процессов пользователя. Единственное, им некому выдавать сообщения об ошибках и они должны обрабатывать ошибки сами.

Итак, начался разговор об операционных системах. Я не хочу знать ничего асинхронного, за исключением:
* Работа с прерыванием таймера - установка даты/времени и запуск процессов по будильнику.
* Сброс измененнных блоков на диск. (Однако, запись блока при освобождении буфера проще.)

Это просто и полезно, и ничего асинхронного более не требуется. Основной Принцип!

7.1.2. ОБРАБОТКА СООБЩЕНИЙ

Если вы умеете читать ввод одного пользователя, вы умеете читать ввод всех. Вы должны прерваться и определить, кто требует внимания. Вы просто читаете нужный буфер сообщений. Аналогично с выводом.

Это может быть сложно и, конечно, зависит от аппаратных средств. Опрашивать терминалы, конечно, интересно. Но это не наша проблема.

Очень сложно держать данные части пользователей в ОЗУ, а части - на диске. Это нарушает единообразие. Уж лучше держать всех на диске. Простота окупит неэффективность.

7.2. ОЧЕРЕДИ

Написав простой код диспетчера пользователя, можно избежать многих неприятностей. Две подпрограммы: QUE и UNQUE. Когда пользователь жаждет ресурсов, он вызывает QUE. Если ресурс доступен, он получает доступ. Если ресурс занят, он ставится в очередь. Когда подойдет его очередь, он получит доступ.

Например, он не может прочесть диск, когда его читает кто-то другой. Или воспользоваться каким-либо каналом или устройством. На время ожидания он разумеется теряет управление. Когда он освобождает ресурс, он вызывает UNQUE.

Это очень удобное средство для управления многими видами ресурсов, к которым нельзя обращаться всем одновременно, вплоть до нереентерабельных подпрограмм (например, SQRT). Его можно распространить даже на доступ к блокам.

Естественно, я имею в виду определенный способ осуществления QUE и UNQUE. И я предостерегаю вас, более настоятельно чем обычно, что модификации, вероятно, не будут работать. Я попробую упомянуть все причины этого.

В дополнение к адресу словаря пользователя и флагу готовности, каждый пользователь должен иметь поле связи - не в его словаре, а в таблице. Каждый защищаемый ресурс, должен иметь два поля - владелец и первый в очереди. Лучше всего иметь таблицу таких полей - по строке на каждый ресурс. Если ресурс свободен, его владелец - 0; иначе - номер пользователя, его занимающего. Номер пользователя - его строка в таблице пользователя, начиная с 1. Если очереди нет, поле очереди устройства - 0; иначе - номер первого пользователя в очереди.

Если я хочу ресурс и он свободен:
- Я помещаю свой номер в поле владельца и выхожу.
Если ресурс занят, но очереди нет:
- Я помещаю свой номер в поле очереди, и 0 в мое поле связи, и выхожу.
Если есть очередь:
- Я прохожу до конца цепочку, начинающуюся в поле очереди ресурса; помещаю мой номер в найденное нулевое поле связи, 0 - в мое поле связи и выхожу.

Когда я освобождаю ресурс (UNQUE):
- Если очереди нет, я помещаю 0 в поле владельца, и выхожу.
- Если очередь есть, я помещаю его номер в поле владельца, а его поле связи копирую в поле очереди, ставлю ему флаг готовности, и выхожу.

Процедура проста и эффективна. Она разрешает много потенциальных проблем. Несколько комментариев: Очередь, вероятно, будет очень короткой. Если компьютер не перегружен, ресурсы будут обычно свободны. Пользователь не может стоять больше, чем одной очереди. Однако, пользователь может владеть более, чем одним ресурсом. Следовательно, каждому ресурсу нужен свой набор полей. Вы должны добавить к программе цикл, чтобы освободить все ресурсы, занятые текущим пользователем. Так как пользователь должен знать свой номер, чтобы обратится к очереди, этот номер должен быть записан в его в его словаре при инициализации.

Это сложно и неприятно, но это плата за многопользовательность.

7.3. ЧАСТНЫЕ СЛОВАРИ

Ключ к многопользовательности - хранение всей информации пользователя в его словаре - маленьком непрерывном фрагменте ОЗУ. Он активно пользуется кодом, принадлежащем системе и хранимым в другом месте. Его же уникальный код - при нем. Что хранить в частном словаре пользователя?

Обсудим распределение ОЗУ. Вспомним формат словаря: каждая статья, содержит код для выполнения. Каждая статья связана с предыдущей, чтобы словарь можно было просмотреть назад. Некоторые статьи вызываются особенно часто: управления стеком, определяющие слова, содержащие важные переменные - BASE, CONTEXT и т.д. Другие менее важны: названия полей в отчетах, команды редактора, специализированный код (генератор случайных чисел, нахождение квадратного корня и т.д.). Где-то надо отделить общее от частного.

Если вы создаете несколько пользовательских словарей, первая статья в каждом должна быть связана (через поле связи) с определенной точкой в общем словаре. Т.о. пользовательские словари друг другу не видны.

7.3.1. ЗАЩИТА ПАМЯТИ

Если все пользователи получат одновременный доступ ко всему ОЗУ, нам конец. Вы выделяете им память для их словарей. Вы должны обеспечить защиту памяти одного пользователя от другого. Проверки размеров стеков и словаря, должны быть снабжены дополнительными проверками на переполнение, чтобы исключить выход пользователя за пределы своего блока памяти. Аппаратными методами защиты памяти воспользоваться бывает затруднительно. Пользователь может читать свой словарь, системный словарь и буфера блоков; он может писать в свой словарь и в буфера блоков. Несколько пользователей могут писать в один буфер блоков; если не одновременно, по крайней мере последовательно. Если ваши аппаратные средства могут все это реализовать, идеально. Но можно создать и адекватную программную защиту (если не учитывать злонамеренный взлом).

Хотя пользователь не сможет травмировать кого-либо еще, он может убиться сам. Т.о. вы должны иметь системную статью, который восстановления пользовательских областей. И она не будет простаивать.

Если вы используете словари со статьями фиксированной длины, у вас нет поля связи, и некуда вписать ссылку на системный словарь. Ваша программа поиска должна отдельно искать в словаре пользователя и в системном словаре. Это стоит всего несколько лишних инструкций, но это еще одна причина предпочесть связные списки статей.

Если вы используете в словарях таблицы расстановки, каждый список должен быть продолжен в системном словаре. Поэтому, для удобства инициализации, удобно хранить где-нибудь таблицу входов в списки системного словаря.

7.3.2. КОНТРОЛЬ ДОСТУПА

Конечно, хотелось бы, чтобы системный словарь не был избыточным. Кроме того, хочется запретить некоторым пользователям доступ к некоторым системным статьям. Например, к GET и DELETE, управляющим распределением диска. Неправильное употребление этих слов неосведомленным пользователем может ужасно повредить данные на диске. Лучшее решение состоит в том, чтобы разместить системный код вне статей. И использовать для доступа к нему таблицу. Тогда, если пользователь захочет использовать такой код, он должен сначала определить точку входа:

17 ENTRY GET 18 ENTRY RELEASE

т.е. определить слова GET и RELEASE, выполняющие код, адресуемый в 17 и 18 строках таблицы. Подобным образом можно было бы обращаться и с другими библиотеками (например, FORTRAN-овскими).

Это общий метод защиты: чтобы что-то вызвать, надо его корректно определить. Вы можете применять несколько уровней подобной защиты. Против злого умысла - сокрытие документации. Однако, даже без использования тайных знаний, кое-какая защита от дурака должна присутствовать.

7.4. ДИСКОВЫЕ БУФЕРА

То, что несколько пользователей могут читать диск одновременно, не влияет на подпрограмму доступа к диску. Поиск свободного блока не зависит от того, кто его требует. Конечно, каждому пользователю надо выделить хотя бы по буферу. Фактически, все неиспользуемое пространство ОЗУ может быть использовано под буфера. Однако, если блок кем-то читается, вы должны отметить этот буфер как занятый, чтобы не допустить одновременную запись в него. Если вы пытаетесь читать занятый блок, вас ставят в очередь.

Для разграничения доступа к диску, за исключением блока 1, удобнее всего использовать QUE-слова. Найдите свободный блок и обращайтесь с ним, как с ресурсом. Когда один освободит, другой сможет использовать. Это не оказывает никагого ущемления прав работы с блоком. Он может располагаться где угодно. Любой может его читать или писать. Но, никто не владеет им монопольно. Если все пользователи более-менее сотрудничают, затраты минимальны. Фактически, исключительное использование блока необходимо только при исключительных обстоятельствах. Например, блок 1: блок не может использоваться кем-либо еще, пока в него не будут прописаны результаты текущей операции по выделению/освобождению блоков.

7.5. ПЕРЕКЛЮЧЕНИЕ ПОЛЬЗОВАТЕЛЕЙ

Пока мы обсуждали случай нахождения всех пользовательских данных в ОЗУ. Это удобно, но работает только пока пользователей мало. Организовать работу, когда все пользователи в ОЗУ не помещаются - легче сказать, чем сделать. Предположим, что мы имеем место в ОЗУ для четырех пользователей, но хотим работать с сорока. Мы можем хранить все сорок пользовательских словарей на диске и загружать в ОЗУ, когда он станет активным. Все равно, работа с диском идет быстрее, чем цикл пользовательского ввода/вывода. Пока пользователь читает вывод, мы выгружаем его с диска. Когда он заканчивает сообщение, мы читаем его назад в ОЗУ. Естественно, мы не выгружаем его из ядра, когда он ожидает дискового ввода/вывода, т.к. дисковые задержки не так уж велики.

Пока без проблем. Проблема возникает там, где его надо читать обратно. Мы имеем 4 буфера: если мы должны загружать пользователя всегда в определенный буфер, мы имеем 4 класса пользователей, каждый из которых может войти только в свой буфер. В одном будут задержки, а другой будет простаивать.

Надо обеспечить загрузку пользователя в любой свободный буфер. Значит, пользовательский словарь должен быть перемещаемым. То есть любые ссылки в нем должны быть относительными - от начала, возможно хранящегося в индексном регистре. Это не слишком плохо, если мы спланировали все это с самого нашего однопользовательского начала, иначе надо будет полностью переписать программу, либо переиндексировать словари при каждой загрузке.

С относительными ссылками все просто. Почти. Мы теперь имеем реальное различие между нашими двумя словарями: системный словарь абсолютен, а пользовательский относителен. Поэтому надо обращаться с ними по-разному.

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

Т.е. вы сразу должны писать вашу однопользовательскую программу с учетом на расширение:
- Зарезервируйте индексный регистр для указания начала словаря и работайте с относительными адресами.
- Делайте весь код реентерабельным. По крайней мере весь код, который может быть прерван потерей пользователем контроля - т.е. почти весь.

Сделайте это, если есть хоть малейший намек на будущую многопользовательность. Это нарушение Основного Принципа, но тут ничего не поделать.

...
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Сб Окт 05, 2019 9:43 am

...

8. ПРОГРАММЫ, КОТОРЫЕ ДУМАЮТ

Тайна сознания волнует философов с давних пор. Это теперь кажется очевидным, что жизнь и сознание - результат сложной организации. Сложные взаимодействия сложных данных. Настолько сложные, что на них способны только наши мозги.

Поэтому, один из путей исследования разума состоит в том, чтобы экспериментировать с управлением данными. А для чего еще нужен компьютер? У нас теперь есть суперпрограмма. Почему бы не использовать ее для исследования разума? Я не предлагаю, чтобы вы занялись психологией. Но как не позабавиться с вещами, которые нам раньше были недоступны?

Я буду описывать необычные словарные статьи. Если у вас есть приложение, в котором они могли бы быть полезными - попробуйте. Однако, Основной Принцип запрещает вам, реализовывать их просто так, без цели. Сложность и специализация, это еще не ценность.

Я использовал все эти статьи в одной программе. Эта программа имела меньше чем 1500 инструкций, так что такое было вполне возможно. Никакого другого применения я им не нашел.

8.1. РАЗБОР СЛОВА

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

Не трудно изменить WORD, чтобы он распознавал еще что-то, кроме пробела. Но невозможно распознавать сразу все. Неизбежна чрезвычайная перегруженность подпрограммы специальными случаями. И вы будете тратить впустую свою изобретательность, пытаясь достичь общности. Например, не имеется никаких простых правил, которые могут распознать как отдельные слова:

HELLO GOOD-BYE 3.14 I.B.M. -.5 1.E-3

Аналогично, не имеется никаких простых правил разбиения следующих строк:

-ALPHA 1+ ALPHA+BETA +X**-3 X,Y,Z; X.OR.Y

Не отчаивайтесь! Имеется общее решение для всех этих случаев. Оно требует очень больших затрат времени. Но, зато, это окончательное решение. Кроме того, скорость обработки текста - не критический фактор. Мы можем себе это позволить, увеличивая скорость там, где это надо.

Если вы еще не догадались: Мы читаем слово, ограниченное пробелом, ищем в словаре, преобразуем в число. Если ничего не получилось, обрезаем последний символ и начинаем снова. В конечном счете, мы обрежем суффикс, оставив только слово.

Оценим стоимость. Мы делаем столько попыток распознавания, сколько букв нужно отбросить. Это требует ускорить поиск слова и конвертирование чисел. Это также поощряет сократить число отбрасываемых чисел. Будем практичными: это небольшая плата. За исключением процесса компилирования. Но я не пишу компилятор, а, если вы пишите, вы сделаете по-другому.

Имеются несколько трудностей: вы должны возвращать обрезаемые литеры обратно в вводимое сообщение. Требуется осторожность в работе с указателями.

Поддержка указателя входа невозможна при небуферизированном вводе. Это то, почему я ратовал за буферизацию в Главе 3. Иначе, примените Основной Принцип!

Вы должны также иметь способ обнаружить, что слово исчерпалось: например, используя счетчик. Или - иметь пробел и перед словом, и останавливаться на нем. Я предпочитаю второй способ, поскольку регистров под счетик не хватает. Это означает лишнюю проверку и лишние перемещения по буферу. Все зависит от аппаратных возможностей.

Имеются два способа что-то улучшить. Они несовместимы, и выбор зависит от вашего приложения: Мы не должны отбрасывать символы "по одному". Если в слове подряд несколько букв, или несколько цифр, или их комбинация, вы могли бы выкинуть их разом. Т.о. вы в качестве разделителей хотите видеть спецсимволы. Значаит, вы должны быть способны отличить обычный символ от необычного. Это требует таблицы в 64 ячеек - определителя необычности для всех 64 литер. Если аппаратура позволяет, используйте таблицу в 64 бита.

Однако, это означает, что вы не сможете рассекать буквенные последовательности. Например отрезать букву "s" от слова в множественном числе. С другой стороны, рассечение между букв чревато ошибками: я рассек SWAP - распознались S и W, а AP вызвало ошибку. Возможно, имеет смысл приучить себя отделять суффиксы дефисами. Впрочем, в этом случае, как распознать сами суффиксы?

Если вы отбрасываете литеры, вы не должны их потерять. Указатель ввода вам в помощь. Заметьте, что распознавать что-то длиннее максимальной длины слова бесполезно.

Другая оптимизация имеет отношение к размеру слов в словаре. Если вы храните слово порциями, то отбрасывайте этими порциями.

Что дает подобное распознавание слов программе? Как это помогает думать? Ваша программа учится понимать не то, что вы пишете, а то, что вы думаете. Это срабатывает не всегда, но если придерживаться некой системы, то более или менее.

Я хотел бы сказать, что эта способность впечатлит людей. Это впечатлит вас, по крайней мере, должно. Но обычные люди, подобно вашему боссу, ожидают что компьютер это и так умеет. Они, скорее, обидятся, если ваша программа этого не сможет.

8.2. ОПРЕДЕЛЕНИЯ ПРИОРИТЕТА

К сожалению, я не знаю терминологии того, что обсуждаю. Я никогда не встречал подобных обсуждений. Но, при разработке компиляторов этот вопрос должен был бы возникать. Если вы знаете терминологию, вы меня поймете.

Наши арифметические операторы ожидали, что их аргументы уже лежат на стеке. Обычная алгебраическая нотация - инфиксная. Следовательно, действие должно быть отсрочено, пока другой операнд не считается.

Кроме того, мы имеем приоритет операторов. Например:

A+B*C

Умножение должно быть выполнено перед сложением. Кроме того, чтобы изменить порядок вычислений, используются круглые скобки:

A*(B+C)

Такая нотация, в целом, эквивалентна нашей. Она ничем не лучше и имеет некоторые ограничения. Но люди к ней привыкли. Так что я покажу вам, как ее обеспечить.

Однако нет никакой причины ограничиваться только общепринятым арифметическим и/или логическими операторами. Я покажу вам как писать такую нотацию для любых операторов.

Введем новый тип словарных статей. Работают как определение, только добавляют к нему число - приоритет. Так что назовем их определениями приоритета. Принцип в том, что определенные слова будут не столько выполняться, сколько сохранятся на стеке в ожидании понижения приоритета. А уж тогда - выполняется весь фрагмент до того места, где приоритет так же низок.

Формат для определения приоритета:

2 :L word ... ;

Здесь 2 это номер приоритета. :L объявляет следующее слово как определение приоритета. ';' отмечает конец. Вот сложение и умножение:

0 :L , ;
1 :L + + ;
2 :L * * ;

Мы переопределили обычные опрераторы в приоритетные. Будем считать, что "," заканчивает действие наших соглашений. Теперь мы можем написать:

3 + 4 * 5 ,

Как это работает? 3 идет на стек параметров, + идет на стек приоритетов, 4 - на стек параметров, * - на стек приоритетов (т.к. его приоритет выше), 5 - на стек параметра. Теперь "," вынуждает * выполнится (приоритет "," ниже) и * находит 5 и 4 на стеке параметров. "," также вынуждает + выполнится (с аргументами 20 и 3) и затем выполняется сам и не делает ничего.

Ясно? Возможно, вы знакомы с такой техникой. Все, чем я жертвую - место под статьи с кодом, который присутствует в обычных компиляторах. Возможно вам такой подход покажется полезным. Помните что приоритетные операторы порождают выполнение друг друга, низкоуровневые - провоцируют высокоуровневые. Приоритеты операторов очевидны.

Что мы имеем? Зачем нам нужны определения приоритета? Вы видели простые определения. Но они позволят вам написать компилятор для любого языка! Определения приоритета могут работать с любой контекстно свободной грамматикой, не только LR-1, лежащей в основе современных языков. Я сам не знаю, как распорядиться этой мощью.

Теперь назад. Вы видели некоторые определения приоритета. Я надеюсь, что вы поиграли с некоторыми из них. Как мы их создаем? Плохо. Мы реализовали общее определение для определений приоритета. Когда я нашел применение для определений приоритета, я также понял, что их можно было сделать лучше.

Каждая статья словаря рассматриваться как инструкция виртуального компьютера, как было обсуждено в Главе 5. Мы рассматриваем приоритетную статью, как инструкцию, которая может быть отсрочена. Почему нет? Определение, в конце концов, только специфический вид инструкции. Если оно может быть с пользой отсрочено, то и другие инструкции - также.

Мне жаль, если это кажется сложным. Это так! Будет и сложнее - но оно того стоит. Однако, мы просто развиваем наши идеи.


Как вы выполняете приоритетное слово? Точно так же, как любой другой. Однако, первая вещь, которую оно делает - исполняет программы LEVEL, получающую параметр - приоритет. LEVEL сравнивает это число с числом на стеке приоритетов. 3 случая:
- разместить на стеке приоритетов приоритет (более высокий) и адрес статьи, RETURN.
- заменить адрес на вершине стека приоритетов на свой, и выполнить старый адрес.
- если стек приоритетов пуст, и приоритет - 0, выполнить свой адрес.
Четвертого не дано!

Перед тем, как выполнить адрес со стека, LEVEL должен установить SOURCE адрес на программу FORCE. Вы помните, что цикл управления берет слова либо из ввода, либо из определения. Теперь у нас третий источник - стек приоритетов. Значит, SOURCE и виртуальный IC должны быть сохранены на стеке возвратов.

Когда вы запускаете приоритетную статью, вы должны помнить, что это она уже выполнялась - выполнив LEVEL. Это новое выполнение должно начаться с другого места - на одну-две инструкции дальше начального адреса. Или вы могли бы держать на стеке приоритетов адрес повторного запуска.

Когда приоритетная статья отработает, выполнится RETURN, и цикл управления перейдет к FORCE. FORCE должно заканчивать выполнение приоритетной статьи. Его функция - проверить, нельзя ли выполнить еще что-либо со стека приоритетов. 3 случая:
- Оставить стек, как есть, и восстановить SOURCE и виртуальный IC со стека возвратов, RETURN.
- Выполнить и удалить адрес под вершиной стека приоритетов.
- Если в стеке нет адресов, кроме этого и приоритет - 0, это выполнить последний адрес, очищая стек приоритетов. Восстановить стек возвратов.

Позвольте мне подчеркнуть важность стека возвратов и сохранения SOURCE. Если приоритетная статья - фактически определение, SOURCE будет переустановлен. Пройдет немного времени и мы снова будем должны перейти к FORCE. Возможно, мы будем использовать определения уровня внутри определений или исполнять другие определения. Вложений может быть много. Но, благодаря сохранениям на стеке возвратов, все они разрешаются. Вы должны рассмотреть только простой случай при создании определения; сложные случаи получаются автоматически.

Теперь Вы должны уметь создавать приоритетные статьи. Что с ними делать?
- Вы можете определять общепринятые арифметические действия: + - * / MOD **.
- Вы можете определять общепринятые логические действия: OR AND NOT IMPL.
- Вы можете определять общепринятые отношения: = < > <= >= /=.
- Вы можете определять общепринятое присваивание: = :=.
- Вы можете определять все перечисленное.

В зависимости от от того, что требуется.
- Вы можете определить арифметику по-английски: PLUS MINUS TIMES DIVIDED-BY EQUALS.
- Вы можете определять арифметику по-COBOL-ски: MOVE .. TO .. или DIVIDE .. INTO .. или ADD .. TO .. .

Два специфических использования.

Запись условного оператора в виде

IF relation THEN statement ELSE statement ;

IF будет компилировать условный переходд и запускаться THEN. THEN будет разрешать переход от IF и запускаться ELSE. ELSE будет компилировать безусловный переход, разрешать переход от THEN и запускаться ";". ";" будет разрешать переход от ELSE и запускать его.

И готов компилятор!

Или так:

1800. FT / SEC ** 2

Такая, вот разновидность UNIT.

Теперь ваша очередь. Предложенного достаточно, чтобы, например, построить решатель школьных задач по физике.

Имейте в виду, что определения приоритета не увеличивают мощность компьютера. Они просто позволяют вам изменять порядок вычисления. Т.е. вы можете разнообразить свой язык управления.

8.3. БЕСКОНЕЧНЫЙ СЛОВАРЬ

Я предполагаю, что ваш словарь составит в среднем несколько сотен статей. Даже простые данные могут порождать значительно количество слов, для обозначения, например, полей. Однако некоторые приложения требуют значительно больших словарей. Допустим, вы должны идентифицировать одного из 10000 клиентов; или возможно вы хотите символы для 104 элементов; или названия 1000 одобренных пищевых добавок.

Ясно, такое надо хранить на диске. Также ясно, что искать что-то полным перебором на диске бессмысленно. Решение: Если вы не находите слово в основном словаре, и это - не число, то ищем блок на диске. Теперь проблема сокращается до: Который блок?

Введем переменную CONTEXT. Работает как адрес блока: оба идентифицируют блок и его предполагаемое место в ОЗУ. Изменяя CONTEXT, вы можете искать в различных словарях. Связывая несколько блоков вместе, вы можете искать на большом фрагменте диска; или в нескольких словарях подряд.

Вы можете позволить себе искать на изрядном куске диска, потому что, если вы не найдете слово, то это будет ошибка. Задержка печати сообщения об ошибке дает вам паузу. Но для тысяч статей такой подход неадекватен.

Для очень больших словарей используйте хэш-функцию, ассоциирующую со словом адрес блока. Как для поиска в словаре. Вы можете быть уверены, что если слово есть, оно в этом блоке. Поскольку помещали вы его по тому же алгоритму. В блок заведомо влезут все слова с одинаковым значением хэш-функции. Снова, также, как в ОЗУ. С таким большим словарем диска, вы должны быть осторожными в нескольких вещах. Вам нужна быстрая хэш-функция. Попытайтесь придумать алгоритм, держащий все блоки одинаково наполовину пустыми. Иначе есть возможность переполнения и блоки придется связывать.

Такой дисковый словарь может быть действительно внушителен - даже для некомпьютерщика - потому, что вы можете обеспечить быстрый доступ. До десятков тысяч статей.

Что напоминают статьи дискового словаря? Я нашел, что достаточно двух полей: поле слова, такая же, как в обычном словаря; и поле параметров, 1 слово. Если вы находите слово на диске, вы помещаете параметр в стек. Помните, что вы не можете позволять себе хранить абсолютные адреса на диске, так что вы не можете иметь поле адреса, как в ОЗУ. Вы могли перерасчитывать адрес, но лучше иметь дело с константами.

Например, вы можете поименовать блоки. Когда вы напечатаете имя блока, его адрес перемещается из поля параметров на стек. По идее, этого бы и ждете. Вы можете использовать номера блока и их имена попеременно. Или вы могли бы поименовать инструкции вашего компьютера.

Заметьте, что вы не можете именовать блоки их номерами. То есть имя статьи дискового словаря не может быть числом. Потому, что поиск на диске происходит только, если слово не удалось распознать как число. Или искать на диске все литералы? Можно использовать числа с каким-либо довеском, который не пройдет в NUMBER. Например, с суффиксом #.

Как создать статью на диске? Специальное определение:

0 NAME ZERO

аналогичное CONSTANT. Альтернативно вы могли бы устанавливать флаг и позволять подпрограмме ENTRY решать, использовать ли диск или ОЗУ. Это удобно, если хотите хранить на диске разные виды слов. Вам также нужен способ забыть статью на диске:

FORGET ZERO

FORGET вызывает WORD для чтения слова, которое нужно удалить, так, что это не типичный вызов ZERO. Статья просто удаляется, без всякой упаковки. Когда Вы будете создавать статью на диске, вы сначала ищете это слово на диске. Многократные переопределения полезны в обычном словаре, но не на диске, там их нет. Потом вы ищете дырку. А если слово уже на диске, или дырки нет? Придумайте сообщение об этой ошибке.

О реализации. С тысячей имен на диске легко исчерпать мнемонику. Переопределите CONTEXT: добавляйте его к номеру блока, полученного хэш-функцией. Если CONTEXT - 0, все как обычно. Но если CONTEXT отличен от нуля, вы получите другой блок. Если CONTEXT может измениться от 0 до 15, вы можете иметь 16 различных определений того же самого слова. Только надо помнить, с каким CONTEXT вы его определяли. Если не найдется никакого совпадения в блоке с данным CONTEXT, вы не найдете статью. Поиск в блоках с другим CONTEXT производится не будет.

Например, индексы можно просматривать для различных каталогов. Устанавливая CONTEXT, вы можете различать их. Вы можете использовать то же самое имя для SCREEN-а кода и SCREEN-а комментариев, различая их по CONTEXT. Чтобы не конфликтовать с хэш-функцией CONTEXT надо умножать на достаточную степень двойки. Вы можете использовать CONTEXT в обоих случаях, которые мы обсудили, одновременно. Как смещение блока, если маленький, или как номер блока, если большой. Так что ваша программа поиска может решать, считать хэш-функцию или нет.

Проблема возникает, если вы планируете обрезать слова. Задержка вырастет неимоверно. Несколько решений возможны: Хеширование по начальным символам. Или CONTEXT, равный 0, для запрета поиска на диске. Сделайте разбор и дисковый поиск взаимноисключающими. Главное, решите, что вам надо.

8.4. БЕСКОНЕЧНАЯ ПАМЯТЬ

Конечно, бесконечная память невозможна. Невозможна даже неограниченная память. Но вы можете иметь доступ ко всей памяти вашего компьютера, как к памяти произвольного доступа. Для этого можно усовершенствовать статьи полей, представленные в Главе 4. Я говорю об этом здесь потому, что такая техника ближе к разумному поведению, чем к процедурам вывода.

Проблему того, что делать с бесконечной памятью, я оставлю вам. Вы будете должны организовать ее так или иначе. Экспериментируйте. Все, что я могу делать - показать, как обойтись без ссылок на диск.

Давайте добавим к полю параметр - дисковый адрес. Поле будет располагаться в этом блоке на диске. Программа будет автоматически читать блок, чтобы получить поле. Конечно, в одном блоке может лежать много полей.

Прежде, чем вы начнете возражать, позволять мне объяснить. Программа помнит блоки, считанные последними. Так что, если блок уже в памяти, программа не будет его читать заново. Следовательно, повторные доступы к тому же самому блоку стоят недорого.

Конечно нужно достаточное число блоковых буферов, для минимизации перекачек. Нужен подходящий размер блоков. Конечно, некоторые потери будут, но удобство того стоит. Попробуйте сделать лучше!

Предположим, что вы хотите просмотреть часть диска. Все, что вы должны сделать - определить подходящие поля и перебирать их в цикле. Реальный выигрыш минимален. Все, что вы экономите - инструкция чтения. Но если блоки как-то связаны, то сделав связь отдельным полем, можно использовать ее в цикле не задумываясь. Чем сложнее организация ваших данных, тем больше выигрыш.

Конечно, тем же способом можно и писать блоки. В Главе 6 говорилось об отложенной записи блоков. Т.е. платить опять не надо! А если вы ничего не изменили, и записи не будет. Только удостоверитесь, что, когда вы покидаете вашу программу, все измененные блоки записываются.

Вы можете сделать полевые статьи универсальными, считая, что дисковый адрес 0 обозначает работу с ОЗУ.

Заметьте, что подобные полевые статьи определяет структуру данных очень похоже на уровни доступа COBOL: 01 уровень - диск; 02 - поля. Для других инструкций Вы можете добавлять более высокие уровни: указатель на поле в ОЗУ - 03 и т.д.

Как это работает. В полевой статье вы имеете параметр, означающий стартовый адрес. Если это поле ссылается на другое, вы складываете параметры. Когда вы находите основной адрес блока диска, вы добавляете полученное смещение и voila': вы нашли нужные данные. Нужны ли промежуточные поля (хранящие другие поля)? Почему нет? Так удобно получать доступ к разного рода таблицам и записям. Или к под-записям записей. Очень полезно! Все, как на COBOL, только проще и удобнее.

Предупреждение! Не пробуйте повысить эффективность, помещая адрес блока в индексный регистр. Слишком трудно будет отследить, на какой блок регистр показывает в данный момент. Немного кода и вы всегда получите то, что нужно. Конечно, аппаратные средства могут иметь некоторые специальные особенности: возможно при микропрограммировании? Даже косвенное адресация может быть полезна.

Вы можете использовать сложные способы адресации для отладки. Например, огранизовать защиту памяти. Добавьте в поля предельное значение адреса. И проверяйте при обращении к полям выход за их пределы. Верхний предел для последнего поля блока - конечно размер блока. Верхний предел для поля в ОЗУ тоже можно определить. Простое сообщение об ошибке OVERFLOW покажет вам, что что-то не так, раньше, чем все рухнет.

Возможен еще один вид полевой статьи. Со ссылкой. Когда вы будете выходить за пределы поля, будет выполнен переход по ссылке с целью удовлетворить запрос. Например, для поля записи в блок: если вы выходите за пределы блока, вы по связи можете переходить в следующий блоки и продолжать там. Автоматически! Это позволит создавать записи переменной длины из записей фиксированной длины.

Если вы хотите подобным способам обрабатывать переполнение, вы должны научиться работать с ссылками. Нужна статья, которая будет искать блок с подходящей дырой. Если не получиться, выполнить GET - получить и привязать новый пустой блок. Дыра в блоке должна идентифицироваться нулями в первом слове, чтобы новый блок (затираемый нулями) весь состоял из одних дыр. Естественно, вы не имеете никакой гарантии что блоки будут идти подряд. Почти никогда так не будет. Или вас это не волнует, или вы выделяете блоки целыми группами.

Запись легко удалить Вы создаете дыру, записывая 0 в первое слове. Освободился ли при этом целый блок, выяснить трудно. Если вы не стремитесь упаковывать данные, вас это не волнует. Использование абсолютных адресов блоков и записей важнее.

Так, мы можем иметь автоматический доступ к полям, рассеянным на всем протяжении диска и в записях переменной длины. Основной Принцип!

Замечание! Если полевые статьи могут адресовать другие полевые статьи, вы нуждаетесь в некотором способе отличить поле от адреса диска. Я такого способа не знаю.

***

Последнюю, 9-ю главу я оставлю там, где она уместнее - в рекомендациях по написанию своего FORTH - Что такое FORTH? Leaf10ТЕМА #30, АБЗАЦ #228Что такое FORTH? Leaf10
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Что такое FORTH? Empty Re: Что такое FORTH?

Сообщение автор Gudleifr Пт Янв 24, 2020 12:10 pm

САМЫЙ, САМЫЙ, САМЫЙ...

Не хотел писать этот огрызок. В нем нет никакой практической надобности. Кроме того, я (и не только я, см. например "FORTH-дебилизмы") уже во многих местах говорил о "свойствах FORTH" и даже, иногда, что-то, на первый взгляд, совершенно обратное тому, что собираюсь написать здесь. Это объясняется очень просто: и FORTH не язык, и оценка его свойств слишком сильно зависит от контекста его использования. "Микроскоп удобен? А для забивания гвоздей?"

FORTH БЫСТР? В каком месте? На нем быстро писать? Программы на нем быстры? Можно ли писать на нем быстрые программы?

Писать на FORTH можно быстро. Мне быстро. Важной характеристикой для меня является совпадения скорости писания на языке с моей. C++ и языки ассемблеров слишком медленные; Perl слишком быстрый; C и FORTH - в самый раз. И не отстаешь в выражении мыслей от их обдумывания, и не плодишь побочные эффекты быстрее, чем успеваешь их осмыслить. То же, кстати, относится к редакторам и "обезьянникам" (IDE).
Более того, на C я должен сначала хорошенько обдумать структуру программы и только потом начать писать. На FORTH можно начать писать сразу. И, главное, писать нужно только то, что нужно для решения задачи, никаких обязательных структурностей и парадигм...
По-сути, это следствие того, что FORTH - это не язык, а метод написания программ - метод постепенного создания проблемно-ориентированного языка. А C и C++, например, языки, ориентированные на метод масштабирования, а система lex/yacc ориентирована на заранее продуманное создание проблемно-ориентированных языков.
Подходит этот метод к вашей задаче? Пишете быстро. Нет? Пишете медленно.

Быстры ли программы на FORTH? За счет того, что нам не надо копировать в свою программу чужие решения схожих задач - быстры. За счет того, что программа разбита на слишком маленькие куски, переходы и передача данных между которыми занимают слишком много кода, медленны. Что перевешивает? Это определяется тем, где и для чего мы пишем. Но, обычно никакой роли не играет. Отмечу только, что опять эти свойства - свойства метода, а не языка.

Можно ли писать на FORTH быстрые программы? Можно. Даже очень быстрые. Можно включать в критических местах FORTH-программы куски оптимизированного машинного кода. Можно даже встроить в FORTH-систему целевой компилятор, порождающий быстрый машинный код автоматически. Но это относится не только к FORTH. На это способны почти все языки и системы, кроме избыточно высокоуровневых (читай - всех современных).

FORTH КОМПАКТЕН? Можно сказать практически то же самое, что и про скорость. Программы компактны, код избыточен, оптимизация возможна. Накладные расходы на включение интерпретатора в готовую программу минимальны.

FORTH ПОНЯТЕН? Я, по-крайней мере, не испытываю проблем с чтением собственных FORTH-программ, написанных десятки лет назад (чего не мог, например, сказать о C-программах). Метод же. Метод постепенного написания. Т.е. читается как постепенно разворачивающееся решение задачи. Однако, тут есть подводный камень - читаешь-читаешь, и вдруг понимаешь, что пошел не туда, и надо было сделать проще/лучше. И нет обычного утешения других методов - мол, работает же, быстро работает, отлажено-проверено... Эти оправдания в FORTH не работают - ведь, переписать все заново займет почти столько же времени, сколько само чтение старой программы. Конечно, это плохо для "программистов", мечтающих о написании "универсальных виртуальных машин FORTH", которые можно будет "только модифицировать" или, даже, продавать.
...

Так что, бросайте эти разговоры о скорости, компактности, красоте, применимости... Это свойства вашего стиля программирования, а не FORTH, тем более, не FORTH-языка или FORTH-виртуальных машин, являющихся фэнтезийными сущностями, а не чем-то полезным для FORTH-метода.
Gudleifr
Gudleifr
Admin

Сообщения : 3211
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения