Детализированная разработка/решение задачи
`Тривиально`: Я вижу, как это можно сделать. Я только не знаю, сколько это займет времени.
`Нетривиально`: У меня нет `ключа к пониманию` того, как это сделать.
`Операционная философия, разработанная в группе лабораторной автоматизации и инструментального проектирования на химическом факультете Политехнического института и Университета штата Вирджиния.`
Когда Вы приняли решение по составу компонентов в задаче, Вашим следующим шагом является разработка этих компонентов. В этой главе мы применим технику решения задач для детализированной проработки проблемы на Форте. Это - время чистого творчества, та часть, которую большинство из нас находят наиболее занятной. Есть особое моральное удовлетворение в том, чтобы выйти на ринг с нетривиальной проблемой и уйти оттуда победителем.
Трудно на естественном языке отделить идею от слов, используемых для ее описания. При написании задачи на Форте трудно отделить детализированную разработку от реализации, поскольку мы стараемся проектировать на Форте. По этой причине мы немного обгоним самих себя в этой главе, не только представляя проблему, но также проектируя решение для нее, прямо ведущее к кодированию реализации.
ТЕХНИКА РЕШЕНИЯ ЗАДАЧ
Даже неофиты могут решать программные задачи без малейших размышлений по поводу проблемы решения задач. Так почему же надо изучать такую технику? Для ускорения процесса. Думая о `путях`, по которым мы решаем проблемы, отдельно от собственно проблем, мы обогащаем наш подсознательный технологический багаж.
Г. Полиа написал насколько книг на тему решения задач, в особенности математических. Наиболее подходящей из них является `Как ее решить` [1]. Хотя решение математических задач не совсем то же самое, что и решение программных, Вы найдете здесь некоторые ценные предложения.
Следующая серия советов суммирует несколько приемов, рекомендуемых наукой о решении задач:
------------------------------------------------------------ СОВЕТ Определите Вашу цель. ------------------------------------------------------------
Знайте, что Вы пытаетесь сделать. Как мы видели в главе 2, этот шаг может быть детализирован и дальше:
Определите интерфейсы данных: проследите, какие данные понадобятся для достижения цели и убедитесь, что эти данные доступны (вход). Для одного определения это означает написание стекового комментария.
Определите правила: проверьте все известные Вам факты. В главе 2 мы описывали тарифы для вычисления стоимости телефонного вызова с помощью правил для применения тарифов.
------------------------------------------------------------ СОВЕТ Обрисуйте проблему в целом. ------------------------------------------------------------
В фазе `анализа` мы разделили задачу на части для выяснения нашего понимания каждой из этих частей. Теперь мы входим в фазу `синтеза`. Мы должны визуализировать проблему в целом.
Попытайтесь удержать в голове столько информации о проблеме, сколько это возможно. Используйте слова, фразы, рисунки и таблицы или любой вид графического представления данных и/или правил для того, чтобы помочь себе одним взглядом охватывать как можно больше информации. Ощущайте, как распухает Ваша голова от требований, которые вы должны выполнить в задаче, подобно тому, как ощущаете наполнение своих легких воздухом.
Теперь задержите Ваш мысленный образ, так же, как вы задерживаете дыхание.
Случится одно из двух:
Вы можете увидеть решение во вспышке озарения. Прекрасно! Испустите вздох облегчения и приступайте прямо к реализации. Или ... задача слишком сложна или незнакома, чтобы ее можно было решить так легко. В этом случае Вам следует обратить свое внимание на аналоги и частичные решения. При этом важно то, что вы уже сконцентрировались на требованиях задачи в целом.
------------------------------------------------------------ СОВЕТ Разработайте план. ------------------------------------------------------------
Если решение не очевидно, следующим шагом является определение подхода, который Вам следует принять для его выработки. Установите направление действий и остерегайтесь ловушек бесцельного шатания.
Следующие советы предлагают несколько подходов, которые Вам стоило бы принять.
------------------------------------------------------------ СОВЕТ Подумайте об аналогичной задаче. ------------------------------------------------------------
Нет ли чего-то знакомого в этой проблеме? Не писали ли Вы подобного определения раньше? Выделите знакомые участки проблемы и то, в чем может отличаться данная задача. Попытайтесь вспомнить, как Вы решили ее раньше или как Вы решили раньше что-то похожее.
------------------------------------------------------------ СОВЕТ Работайте назад. ------------------------------------------------------------
Нормальный, очевидный путь для атаки на проблему начинается с области известного и продолжается в неизвестном. В решении о том, на какую лошадь ставить, Вы бы начали с их недавнего прошлого, с их текущего здоровья и так далее, применяя разные веса для этих различных факторов и приближаясь к фавориту.
------------------------------------------------------------ СОВЕТ Работайте назад. ------------------------------------------------------------
Более сложные проблемы предоставляют множество возможных путей для обращения с поступающими данными. Как узнать, какой маршрут приведет Вас ближе к решению? Неизвестно. Этот класс задач лучше решается при проработке назад (рисунок 4-1).
Рис.4-1. Задача, которую проще решать назад, чем вперед.
____________________________________ | ___________________________ | |__| | __________ | _________| | Начало __ __________ | |_________ | | | | ___ | |_________ |____| | | | | | |_________ | | __ Конец | | | |_ | | | | |____| | | | |______| | _| | | | |__|____________|______|_____________|
------------------------------------------------------------ СОВЕТ Верьте. ------------------------------------------------------------
Вера является обязательной составляющей для успешной проработки назад. Мы проиллюстрируем это с помощью знаменитой математической задачи. Предположим, у нас есть две бочки.
На них нет градуировочных отметок, однако одна имеет емкость в девять ведер, а другая - четыре ведра. Нашей задачей является отмеривание ровно шести ведер воды из рядом текущего источника в одну из бочек (рисунок 4-2).
Рис.4-2. Две бочки.
_________ / \ | | ______ | 9 | / \ | | | 4 | | | | | \_________/ \______/
Попытайтесь решить задачу сами, прежде чем читать дальше.
Как мы можем получить "шесть" из "девяти" и "четырех"? Мы можем начать проработку вперед, переливая в уме воду из одной бочки в другую. К примеру, если мы наполним большую бочку дважды из маленькой, то получим восемь ведер. Если мы наполним доверху девятиведерную, затем перельем из нее достаточно воды, чтобы заполнить четырехведерную, у нас будет ровно пять ведер в большой бочке.
Это интересные идеи, однако они не принесли нам шести ведер. И не ясно, как они могут это сделать.
Давайте попытаемся пойти назад. Договоримся, что мы намеряли шесть ведер воды, и она содержится в большей бочке (она не влезет в меньшую!). Теперь, как мы этого достигли? Каково было состояние наших бочек один шаг назад?
Имеются лишь две возможности (рисунок 4-3):
1. Четырехведерная была полна, и мы лишь добавили ее в большую. Это предполагает, что мы уже имели два ведра в большой бочке. Или ... 2. Девятиведерная бочка была полна, и мы попросту перелили из нее три ведра в маленькую.
Рис.4-3. Достижение конечного результата.
ПРЕДПОСЛЕДНИЙ ШАГ ПОСЛЕДНИЙ ШАГ ___________ _____\/__ | _________ / \ | / \ | | ___|__ | | ______ ВЕРСИЯ | | /~~~~~~\ |~~~~~~~~~| / \ А | | | | | | | | |~~~~~~~~~| | | | | | | 2 \_________/ 4 \______/ 6 \_________/ 0 \______/
2 + 4 = 6 ______________________________________________________ _________ ______|__ | _________ /~~~~~~~~~\ | / \ | | __\/__ | | ______ ВЕРСИЯ | | / \ |~~~~~~~~~| /~~~~~~\ Б | | | | | | | | | | |______| | | | | 9 \_________/ 1 \______/ 6 \_________/ 4 \______/
9 - 3 = 6
Что выбрать? Давайте поразмыслим. Выбор первого варианта требует двухведерного измерения, второй требует трехведерного.
При нашем начальном проигрывании ситуации мы не встречались с такой единицей, как два. Однако мы видели разницу в один, и один из четырех есть три. Давайте остановимся на версии Б.
Теперь начинается настоящий фокус. Мы должны заставить себя `поверить` без малейшего сомнения в то, что мы достигли описанной ситуации. Мы перелили три ведра в малую бочку. Отбрасывая все свое неверие, мы концентрируемся на том, как мы это сделали.
Как мы смогли перелить три ведра в бочонок? Если там уже было одно такое ведро! Неожиданно мы перевалили через гору. Теперь остался простой вопрос о том, как мы получили одно ведро в маленькой бочке? Мы должны были начать с полной девятиведерной, отлить дважды по четыре ведра и получить одно. Затем мы перелили это ведро в маленькую бочку.
Наш последний шаг должен будет заключаться в проверке нашей логики проигрыванием задачи вперед опять.
Вот еще одно преимущество проработки назад: если задача нерешаема, проработка назад помогает Вам быстро доказать отсутствие ее решения.
------------------------------------------------------------ СОВЕТ Обнаруживайте внешние проблемы. ------------------------------------------------------------
До тех пор, пока мы не порешали проблему, у нас имелось лишь смутное представление о том, какие шаги - или даже сколько шагов - может понадобиться. По мере того, как мы больше проникаемся задачей, мы начинаем понимать, что она содержит одну или более подзадач, которые выглядят несколько отличными от главной линии преполагаемых действий.
В только что решенной задаче мы обнаружили две подзадачи: заливку бочонка одним ведром воды и затем наполнение большой бочки шестью ведрами.
Распознавание таких маленьких проблем, иногда называемых "внешними задачами", является важной частью техники решения задач. Определяя подзадачу, мы можем допускать, что она имеет прямое решение. Не останавливаясь для поиска этого решения мы устремляемся вперед по нашей главной задаче.
(Форт, как мы увидим, идеально приспособлен для применения такой техники.)
------------------------------------------------------------ СОВЕТ Отступите от проблемы. ------------------------------------------------------------
Так легко поддаться чувствам и привязаться к одному конкретному решению, что мы забываем держать ум открытым.
Литература по решению задач часто использует пример девяти точек. В свое время она поставила меня в тупик, так что я приведу ее. Имеются девять точек, расставленных, как показано на рисунке 4-4. Надо нарисовать прямые линии так, чтобы они прошли через все девять точек, не отрывая при этом перо от бумаги. Ограничение состоит в том, что сделать это нужно всего четыремя линиями.
Рис.4-4. Задача о девяти точках.
* * *
* * *
* * *
Вы можете хорошенько посидеть и получить что-то не лучшее, нежели почти правильный рисунок 4-5. Если Вы действительно сильно сконцентрируетесь, то можете заключить, что задача шуточная - у нее нет решения.
Рис.4-5. Не совсем правильно.
*----*----* | \ * - *_ * | \ *----*----*
Но если Вы отсядете от нее и спросите себя,
"Не обманываю ли я себя удобным маневром из-за узости своего мышления? Не учитываю ли я некоторые ограничения, которых нет в описании проблемы? Каковы могут быть эти ограничения?"
тогда Вы сможете догадаться вывести некоторые линии за периметр квадрата девяти точек.
------------------------------------------------------------ СОВЕТ Используйте мышление на полную катушку. ------------------------------------------------------------
Когда проблема загнала Вас в тупик и Вы оказываетесь ни с чем, расслабьтесь, перестаньте беспокоиться об этом, быть может, даже забудьте об этом на время.
Творческие люди всегда отмечали, что лучшие идеи приходят к ним в постели или под душем. Множество книг по решению задач предлагают полагаться на подсознание для разрешения действительно сложных проблем.
Современные теории о функциях мозга исследуют различия между рациональным, сознательным мышлением (которое опирается на манипуляции с символами) и подсознательным мышлением (которое проводит корелляцию между новыми познаниями и ранее усвоенной информацией, перекомбинируя и переделывая связи новым и полезным образом).
Лесли Харт [2] объясняет трудность решения больших задач с помощью логики:
Огромная нагрузка ложится на ту маленькую функцию мозга, на которой может быть сосредоточено внимание в данный момент. Возможно озарение, подобное цирковому фокусу, и больше похоже на то, что при этом ... используются все ресурсы нашей великолепной подкорки, ... многомиллиардная нейронная емкость мозга.
... Рабочая часть лежит в снабжении мозга рядами входных данных, таких, как наблюдение, чтение, сбор сведений и просмотр того, что достигли другие. Когда все это введено, приходит время [подсознательных] процедур, суммарных, автоматических, лежащих вне зоны внимания.
... Кажется очевидным, ... что поиск производится за некоторый интервал времени, хотя и необязательно непрерывный, что во многом напоминает работу большого компьютера. Я бы рискнул предположить, что поиск ветвится, начинается, оканчивается, достигает тупиков и возвращается назад и в конце концов собирает ответ, который оформляется и затем всплывает в сознательном внимании - зачастую в удивительно проработанном виде.
------------------------------------------------------------ СОВЕТ Сформируйте Ваше решение. Поищите другие решения. ----------------------------------------------------------------
Вы смогли найти один способ. Могут быть и другие, и некоторые из них могут быть лучше.
Не вкладывайте слишком много усилий в свое первое решение, пока не попытаетесь выработать в себе иное мнение.
ИНТЕРВЬЮ С ИЗОБРЕТАТЕЛЕМ-ПРОГРАММИСТОМ
----------------------------------------------------------------
Дональд А. Барджисс, владелец и президент фирмы Scientek Instrumentation, Inc.:
У меня есть несколько приемов, которые я с пользой применял многие годы при проектировании чего бы то ни было, и которые позволяют мне сохранять гибкость. Моим первым правилом является: "Ничто не невозможно". Мое второе правило - "Не забывать, что главное - добиться желаемого".
Вначале исследуйте проблему, набрасывая на бумаге два или три подхода к ней.
Затем попробуйте кажущийся наиболее подходящим из них, чтобы посмотреть, работает ли он. Проведите его. Затем вдумчиво проделайте весь путь назад и начните заново.
Начинать заново хорошо по двум причинам. Во-первых, это дает вам свежий подход. Вы можете быть притянуты назад тем путем, с которого начинали, либо Ваше начинание притянется к новому пути.
Во-вторых, новый подход может продемонстрировать все виды мощных возможностей. Вы имеете теперь средство измерения. Можете взглянуть на оба подхода и сравнить преимущества обоих. Вы оказываетесь в лучшей позиции для суждения. Попадание в тупик происходит от слишком уж настойчивых попыток следовать единственному подходу. Напоминайте себе: "Я хочу изменить эту зубодробильную штуку. Отбросим традиционный подход как не представляющий интереса. Попробуем безумные идеи."
Лучше всего начать рисовать картинки. Я рисую мелких человечков. Это позволяет вещам не выглядеть как "данные" и не идет вразрез с моим мыслительным процессом. Человеческий мозг исключительно хорошо работает на аналогиях.
Представление вещей в контексте удерживает Вас от замыкания в пределах условностей любого языка, даже Форта. Когда я хочу сконцентрироваться на чем-то небольшом, я разрисовываю маленькие кусочки бумаги. Когда я хочу думать широкими мазками, чтобы понять общее направление, я разрисовываю большие куски бумаги. Это все некоторые дурацкие штучки, которые я использую для того, чтобы не застаиваться.
Когда я программирую на Форте, то провожу день только в грезах, бродя вокруг идей. Обычно перед тем, как сесть за клавиатуру, я набрасываю их в общих выражениях. Не код, только слова. Заметки для себя.
Затем я начинаю с последней строки программы. Я описываю, что мне хотелось бы сделать, на языке, как можно более близком к английскому. Затем я использую редактор для смещения этого определения к концу экрана и начинаю кодирование внутренних слов. Далее я осознаю, что такой путь не подходит. Может быть, я разобью свое основное слово на два и перемещу одно из них в более ранний блок так, что смогу его использовать раньше.
Я работаю с аппаратурой, если она есть в наличии, иначе я ее симулирую.
Форт требует самодисциплины. Вы должны перестать тыкаться в клавиатуру. Форт хочет делать то, что я ему приказываю, а я приказываю ему делать различные виды нелепых вещей, не имеющих ничего общего с тем, куда мне нужно идти. В такие моменты мне нужно убираться от клавиатуры.
Форт позволяет Вам играть. Это здорово, у Вас есть шансы на то, чтобы получить кое-какие идеи. До тех пор, пока Вы удерживаетесь от игры в качестве привычки. Ваша голова гораздо лучше компьютера приспособлена для изобретений.
----------------------------------------------------------------
ДЕТАЛИЗИРОВАННАЯ РАЗРАБОТКА
Теперь мы находимся в той точке цикла разработки, когда уже принято решение о том, что нам нужен компонент (или конкретное слово). Компонент будет состоять из нескольких слов, некоторые из которых (те, что составляют лексикон) будут использоваться другими компонентами, другие же (внутренние слова) будут использованы лишь внутри этого компонента.
Создавайте столько новых слов, сколько нужно для выполнения следующего совета:
------------------------------------------------------------ СОВЕТ Каждое определение должно выполнять простую, хорошо определенную задачу. ------------------------------------------------------------
Вот шаги, обычно предпринимаемые при разработке компонента:
1. Основываясь на требуемых функциях, примите решения об именах и синтаксисе для внешних определений (определите интерфейсы). 2. Разверните концептуальную модель, описав алгоритм(ы) и структуры данных. 3. Очертите круг внешних используемых определений. 4. Установите, какие из внешних определений и приемов уже доступны. 5. Опишите алгоритм с помощью псевдокода, 6. Разработайте его, двигаясь назад от существующих определений к входным данным, 7. Реализуйте все недостающие внешние определения. 8. Если лексикон содержит много имен, имеющих массу общих элементов, разработайте и закодируйте эти общие части как внутренние определения, а затем реализуйте внешние имена.
Мы обсудим глубже два первых шага, затем же рассмотрим пример полной разработки лексикона.
СИНТАКСИС ФОРТА
В этой точке цикла разработки Вы должны решить, как слова в Вашем новом лексиконе будут использоваться в контексте. При этом надо держать в уме то, как лексикон будет использоваться последующими компонентами.
------------------------------------------------------------ СОВЕТ При разработке компонента целью является создание лексикона, который сделает Ваш последующий код читаемым и легко управляемым. ------------------------------------------------------------
Каждый компонент должен разрабатываться с мыслью об использующих его компонентах. Вам надо проектировать синтаксис лексикона так, чтобы слова имели смысл при их появлении в контексте. Упрятывание внутренней информации, как мы уже видели, обеспечит при этом управляемость.
В то же время имейте в виду собственный синтаксис Форта. Вместо того, чтобы внедрять определенный синтакис только потому, что он кажется подходящим, Вы можете уберечь себя от написания большого количества ненужного кода, только выбирая синтаксис, который Форт может поддерживать без какого-либо специального напряжения с Вашей стороны.
Вот некоторые элементарные правила естественного синтаксиса Форта:
------------------------------------------------------------ СОВЕТ Пусть числа предшествуют словам. ------------------------------------------------------------
Слова, требующие числового аргумента, должны, естественно, находить его на стеке. С точки зрения синтаксиса это значит, что число должно предшествовать имени. К примеру, синтаксис слова SPACES, которое выдает "N-ное" количество пробелов, есть:
20 SPACES
Иногда такое правило нарушает тот порядок, к восприятию которого привыкло наше ухо. К примеру, слово Форта + должно быть предварено двумя аргументами, как в выражении
3 4 +
Такой порядок, при котором числа предшествуют операторам, называется "постфиксной записью".
Форт, по своему великодушию, не `настаивает` на такой постфиксной нотации.
Вы можете переопределить + и получать одно из чисел из входного потока:
3 + 4
написав:
: + BL WORD NUMBER DROP + ;
(где WORD - слово из стандарта Форт-79/83, возвращающее адрес; NUMBER же дает число двойной длины - как это указано в списке слов нерегламентированного употребления стандарта-83).
Отлично. Однако Вы не можете использовать это определение внутри других определений через двоеточие или передавать ему аргументы, теряя таким образом одно из основных преимуществ Форта.
Зачастую слова вида "существительное" передают свои адреса (или другой тип указателя) через стек словам типа "глагол". Фортоподобный синтаксис фразы
"существительное" "глагол"
в общем случае реализовать легче всего вследствие использования стека.
В неоторых ситуациях такой порядок слов звучит неестественно. К примеру, предположим, у нас есть файл по имени ИНВЕНТАРЬ. Мы, в частности, можем ПОКАЗАТЬ его, форматируя информацию симпатичными колонками. Если ИНВЕНТАРЬ передает указатель слову ПОКАЗАТЬ, которое с ним работает, синтаксис становится таким:
ИНВЕНТАРЬ ПОКАЗАТЬ
Если Ваше задание предусматривает английский (русский) порядок слов, в Форте имеются способы достижения и его. Однако при этом обычно увеличивается уровень сложности. Иногда лучшее, что можно сделать - это использовать более подходящие имена. Как насчет
ИНВЕНТАРНЫЙ СПИСОК
(Мы сделали "указатель" прилагательным, а "исполнителя" - глаголом.)
Если же задание настаивает на синтаксисе
ПОКАЗАТЬ ИНВЕНТАРЬ
то мы имеем несколько возможностей. ПОКАЗАТЬ могло бы устанавливать флаг и ИНВЕНТАРЬ при этом мог бы работать в соответствии с этим флагом. У такого подхода есть определенные недостатки, в особенности тот, что ИНВЕНТАРЬ должен быть достаточно "умен" для того, чтобы знать все возможные действия, которые могут быть с ним произведены. (Мы будем рассматривать эти проблемы в главах 7 и 8.)
Или ПОКАЗАТЬ могло бы выбирать следующее слово из входного потока.
Мы обсудим этот вопрос в совете "избегайте упреждающих выборок" позже в этой главе.
Или, что рекомендуется, ПОКАЗАТЬ может устанавливать "исполняемую переменную", которую ИНВЕНТАРЬ затем будет вызывать. (Мы обсудим векторизованное исполнение в седьмой главе.)
------------------------------------------------------------ СОВЕТ Пусть текст идет после имен. ------------------------------------------------------------
Если Форт-интерпретатор обнаруживает строку текста, не являющуюся ни числом, ни предварительно определенным словом, это вызовет аварийный останов с выдачей сообщения об ошибке. По этой причине неопределенная строка должна быть предваряема заранее определенным словом.
Примером является ." (точка-кавычка), предваряющая текст, который должен быть впоследствии напечатан. Другой пример - CREATE (так же, как и все определяющие слова), предваряющее имя, которое на данный момент еще не определено.
Это правило также применимо к определенным словам, на которые Вам нужно сослаться, но не исполнить их. Пример - слово FORGET:
FORGET TASK
Синтаксически FORGET должно стоять перед TASK, так что TASK не исполняется.
------------------------------------------------------------ СОВЕТ Пусть определения поглощают свои аргументы. ------------------------------------------------------------
Это синтаксическое правило больше относится к соглашению о хорошем стиле программирования на Форте, чем к требованиям самого Форта.
Предположим, Вы пишете слово ЗАПУСТИТЬ, которое требует номер пусковой установки и стреляет нужной ракетой. В целом Вы хотели бы, чтобы оно выглядело как-то вроде:
: ЗАПУСТИТЬ ( ракета#) ЗАРЯДИТЬ ЦЕЛИТЬ СТРЕЛЯТЬ ;
Каждое из трех внутренних определений потребует один и тот же аргумент - номер установки. Вам где-то понадобится поставить два слова DUP. Вопрос только: где? Если Вы введете их внутрь ЗАРЯДИТЬ и ЦЕЛИТЬ, то сможете не употреблять их внутри ЗАПУСТИТЬ, как в вышеприведенном определении. Если Вы их извлечете из ЗАРЯДИТЬ и ЦЕЛИТЬ, Вам нужно будет определить:
: ЗАПУСТИТЬ ( ракета#) DUP ЗАРЯДИТЬ DUP ЦЕЛИТЬ СТРЕЛЯТЬ ;
В соответствии с соглашением, последняя версия предпочтительней, поскольку ЗАРЯДИТЬ и ЦЕЛИТЬ получаются чище. Если бы Вам понадобилось написать слово ГОТОВ, Вы могли бы это сделать так:
: ГОТОВ ( ракета#) DUP ЗАРЯДИТЬ ЦЕЛИТЬ ;
а не
: ГОТОВ ( ракета#) ЗАРЯДИТЬ ЦЕЛИТЬ DROP ;
------------------------------------------------------------ СОВЕТ Используйте ноль в качестве точки начала отсчета. ------------------------------------------------------------
По привычке люди нумеруют вещи, начиная с первой: "первая, вторая, третья," и т.д. С другой стороны, математические модели более естественно работают при начале отсчета от нуля. Поскольку компьютеры являются процессорами чисел, программное обеспечение становится легче писать при использовании нуля в качестве точки отсчета.
Для иллюстрации предположим, что у нас есть таблица 8-байтовых записей. Первая запись занимает первые восемь байтов таблицы. Для вычисления ее начального адреса мы добавляем "0" к адресу ТАБЛИЦА. Для вычисление начального адреса "второй" записи мы добавляем "8" к адресу ТАБЛИЦА.
Рис.4-6. Таблица 8-байтовых записей.
ТАБЛИЦА +--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | П Е Р В А Я З А П И С Ь | +--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | В Т О Р А Я З А П И С Ь | +--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
Легко написать формулу для получения таких результатов:
первая запись начинается на: 0 Х 8 = 0 вторая запись начинается на: 1 Х 8 = 8 третья запись начинается на: 2 Х 8 = 16
Мы можем легко написать слово, которое преобразует номер записи в ее стартовый адрес:
: ЗАПИСЬ ( #записи -- адрес) 8 * ТАБЛИЦА + ;
Так в терминах компьютера имеет смысл называть "первой записью" 0-вую запись.
Если постановка Вашей задачи предполагает начало отсчета с единицы, то все нормально. Используйте счет относительно нуля по всей Вашей задаче и затем, только в "лексиконе пользователя" (наборе слов, которые будет употреблять конечный пользователь) сделайте преобразование из одной привязки в другую:
: ТЕМА ( n -- адрес) 1- ЗАПИСЬ ;
------------------------------------------------------------ СОВЕТ Пусть адреса предшествуют отсчетам. ------------------------------------------------------------
Опять-таки, это соглашение, а не требование Форта, которое способствуют читаемости кода. Вы найдете примеры применения этого правила в словах TYPE, ERASE и BLANK.
------------------------------------------------------------ СОВЕТ Пусть источник стоит перед приемником. ------------------------------------------------------------
Еще одно соглашение для удобочитаемости. К примеру, в некоторых системах фраза
22 37 COPY
копирует блок 22 в блок 37. Синтаксис слова CMOVE включает в себя как это, так и предыдущее соглашение:
источник приемник количество CMOVE
------------------------------------------------------------ СОВЕТ Остерегайтесь упреждающих выборок (из входного потока). ------------------------------------------------------------
В общем случае старайтесь не создавать определений, подразумевающих, что во входном потоке для них будут подготовлены другие слова.
Предположим, в Вашем компьютере с цветным дисплеем синий представлен числом 1, а светло-синий - числом 9. Вы хотите определить два слова: СИНИЙ будет возвращать 1; СВЕТЛО может предварять СИНИЙ для преобразования его в 9.
На Форте можно определить СИНИЙ как константу, так что при исполнении оно будет всегда возвращать требуемую 1.
1 CONSTANT СИНИЙ
А теперь определим СВЕТЛО так, чтобы оно искало следующее слово во входном потоке, исполняло его и делало логическое "ИЛИ" с восьмеркой (логика этого процесса станет ясной, когда мы вернемся к этому примеру позже в нашей книге):
: СВЕТЛО ( предшествует цвету) ( -- число цвета) ' EXECUTE 8 OR ;
(для FIG-Форта: : СВЕТЛО [COMPILE] ' CFA EXECUTE 8 OR ; )
(Для новичков: апостроф в определении СВЕТЛО - это слово Форта (по-другому - "штрих"). Штрих используется для поиска по словарю; он выбирает имя и ищет его в словаре, возвращая адрес начала определения.
При использовании внутри определения он будет искать слово, следующее за СВЕТЛО - например, СИНИЙ - и передавать этот адрес слову EXECUTE, которое исполняет СИНИЙ, при этом на стеке остается число 1. "Отработав" оператор СИНИЙ, СВЕТЛО теперь делает "ИЛИ" с числом 8, получая 9.)
Это определение будет работать при вызове из входного потока, но понадобятся специальные меры, если мы захотим использовать СВЕТЛО внутри другого определения, как например:
: РЕДАКТИРОВАНИЕ СВЕТЛО СИНИЙ БОРДЮР ;
Даже при работе со входным потоком использование EXECUTE приведет к катастрофе, если после СВЕТЛО случайно будет указано что-нибудь, отличное от нужного определенного слова.
Предпочтительный подход заключается в том, что, если мы вынуждены использовать именно такой синтаксис, то СВЕТЛО должно устанавливать флаг для СИНИЙ, а СИНИЙ должен определять наличие такого флага; это мы позже еще будем рассматривать.
Случается, что заглядывание вперед по входному потоку желательно, даже обязательно. (Предлагаемое далее слово TO часто реализуется именно так [3].)
Но, в общем случае, опасайтесь упреждающих заглядываний. Вам иначе придется готовиться к разочарованиям.
------------------------------------------------------------ СОВЕТ Пусть команды исполняют сами себя. ------------------------------------------------------------
Это правило соотносится с предыдущим. Позволять словам самим делать свою работу - это один из философских кульбитов Форта. Свидетельство тому - компилятор Форта (функция, компилирующая определения через двоеточие), карикатура на который представлена на рисунке 4-7. В нем всего несколько правил:
Брать следующее слово во входном потоке и искать его в словаре.
Если это обычное слово, `компилировать` его адрес.
Если это слово "немедленного исполнения", `исполнить` его.
Если это слово не определено, попытаться преобразовать его в цифру и скомпилировать как литерал.
Если это не число, выполнить аварийный выход с сообщением об ошибке.
Ничего не сказано о специальных компилирующих словах типа IF, THEN, ELSE и т.д. Компилятор определения через двоеточие ничего не знает об этих словах. Он просто распознает определенные слова как "немедленные" и исполняет их, позволяя им проделывать свою собственную работу. (Смотрите "Начальный курс ...", главу 11.)
Рис.4-7. Традиционный компилятор против Форт-компилятора.
ТРАДИЦИОННЫЙ КОМПИЛЯТОР +-----------------------------+ | IF = #$%&"#$-ku.,"#K | | ELSE = 3"!#$578('%#"!"2" | | THEN = "$64ami%$46#E!Ey!" | | BEGIN = 2!"#$12%$%$%67 | | REPEAT = "!#$$&$$&$%[][] | | WHILE = !"#$+++#"$" | | AGAIN = <><>$&&$&** | / \>~_ IF BOOP THEN BEEP | INTEGER = "#$~*?KACU~"#K?
ФОРТ-КОМПИЛЯТОР +----+ +------+ +--------------------+ | IF | | THEN | | НЕ-IMMEDIATE | /$#!&| |&'&%<>| | = КОМПИЛИРОВАТЬ | / /+----+ +/-----+ | IMMEDIATE |/ / / | = ИСПОЛНИТЬ IF BOOP THEN BEEP | ЧИСЛО
Компилятор даже не "контролирует" появление точки-запятой для завершения компиляции. Вместо этого он `исполняет` ее, позволяя ей проделать работу по завершению определения и выключению компилятора.
Имеются два огромных преимущества такого подхода. Первое, компилятор настолько прост, что может быть записан всего в несколько строк программы. Второе, нет ограничений на число компилирующих слов, которые Вы в любой момент можете добавлять, просто делая их "немедленными". Итак, даже компилятор определений Форта может наращиваться!
Текстовый интерпретатор Форта и его адресный интерпретатор также подчиняются этому правилу.
Следующий совет - быть может, самый важный в этой главе:
------------------------------------------------------------ СОВЕТ Не пишите свой собственный интерпретатор/компилятор, если можно использовать готовый из Форта. ------------------------------------------------------------
Один из классов задач состоит в определении языков специального назначения - самодостаточном наборе команд для выполнения определенной работы.
Примером является ассемблер машинного кода. Это большая группа мнемоник команд, с помощью которых можно описывать необходимые инструкции. И здесь подход Форта также радикально отличается от обычной философии.
Традиционные ассемблеры являются интерпретаторами специального назначения - то есть сложными программами, которые могут просматривать текст на ассемблерном языке для распознавания мнемоник типа ADD, SUB, JMP, и т.п. и собирать машинные инструкции соответственно. В то же время Форт-ассемблер - это просто лексикон Форт-слов, каждое из которых само собирает соответствующую машинную инструкцию.
Можно указать еще множество языков специального назначения. К примеру:
1. Если Вы строите приключенческую игру, Вам может захотеться написать язык, позволяющий описывать чудовищ, комнаты и т.д. Вы могли бы создать определяющее слово КОМНАТА для использования в виде:
КОМНАТА ТЕМНИЦА
Затем создать набор слов для описания атрибутов комнаты, строя невидимые структуры данных, связанные с комнатой:
К-ВОСТОКУ ЛОГОВО-ДРАКОНА К-ЗАПАДУ МОСТ СОДЕРЖИТ ГОРШОК-С-ЗОЛОТОМ и т.д.
Команды этого языка для построения игр могут быть просто словами Форта, с Фортом же в качестве интерпретатора. 2. Если Вы работаете с программируемыми логическими матрицами (ПЛМ), Вам может понадобиться форма описания поведения выходных сигналов в логических терминах, основанных на состояниях входных сигналов. Программатор ПЛМ был замечательно просто написан на Форте Майклом Столовицем [4]. 3. Если Вы должны создать ряд пользовательских меню для управления Вашей задачей, то Вам может вначале захотеться разработать язык-компилятор меню. Слова этого нового языка позволяют программисту быстро программировать необходимые меню - при этом упрятывая информацию о том, как рисуются рамочки, двигается курсор и т.д.
Все эти примеры могут быть закодированы на Форте в качестве лексиконов, с использованием обычного Форт-интерпретатора, без необходимости написания специализированного интерпретатора или компилятора.
----------------------------------------------------------------
Мур:
Простое решение не загораживает проблему тем, что к делу не относится. Допустим, что нечто в задаче требует уникального интерпретатора. Но раз уж Вы видете такой уникальный интерпретатор, то это предполагает, что в самой проблеме есть нечто определенно ужасное. И почти никогда в ней на самом деле этого нет.
Если Вы пишете свой собственный интерпретатор, то он почти наверняка получается самой сложной, трудоемкой частью всей задачи. Вам приходится переключаться с решения проблемы на его написание.
Мне кажется, что программисты любят писать интерпретаторы. Они обожают делать эти сложные, трудоемкие вещи. Но в конце концов наступает время, когда приходится заканчивать с программированием нажатий на клавиши или преобразованием чисел в двоичный вид и приступать к решению проблем.
----------------------------------------------------------------
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
В главе второй мы изучили способы описания задачи в терминах интерфейсов и правил. В этом разделе мы детализируем концептуальную модель для каждого из компонетов до уровня четко определенных алгоритмов и структур данных.
Алгоритм - это процедура, описанная как конечное количество правил и для выполнения определенной задачи. Правила должны быть однозначными и должны гарантированно приводить к завершению решения через конечное число шагов. (Алгоритм назван так в честь персидского математика IX века Аль-Хорезми.)
Алгоритм лежит посередине между неточными директивами человеческой речи, такими, как "Пожалуйста, рассортируйте письма в хронологическом порядке", и точными директивами компьютерных языков, таких, как "BEGIN 2DUP < IF ..." и т.д. Алгоритм хронологической сортировки писем может быть таким:
1. Взять неотсортированное письмо и посмотреть его дату. 2. Найти соответствующий скоросшиватель для этого месяца и года. 3. Пролистать письма в нем, начиная с первого, до тех пор, пока не обнаружится письмо с более поздней, чем у Вашего, датой. 4.
Вложить Ваше текущее письмо перед письмом с более поздней датой. (Если скоросшиватель пуст, просто вложить письмо.)
Может быть несколько возможных алгоритмов для одной и той же работы. Приведенный выше алгоритм работал бы хорошо для скоросшивателей с десятком или меньшим количеством писем, но для скоросшивателей с сотнями писем Вам, возможно, пришлось бы обратиться к более эффективному алгоритму, такому, как:
1. (то же) 2. (то же) 3. Если дата попадает на первую половину месяца, открыть скоросшиватель на его трети. Если находящееся здесь письмо датировано позже Вашего, искать вперед до тех пор, пока не найдется письмо с той же или более ранней датой. Здесь втавить свое письмо. Если открытое письмо датировано раньше Вашего, искать назад ...
... надоело. Этот второй алгоритм сложнее первого. Однако при исполнении он потребует в среднем меньшее количество шагов (поскольку Вам не надо каждый раз начинать поиск от начала скоросшивателя) и таким образом будет проходить быстрее.
Структура данных - это собрание данных или мест для хранения этих данных, организованное специально для потребностей задачи. В последнем примере полка со скоросшивателями и сами скоросшиватели, содержащие индивидуальные письма, могут рассматриваться как структуры данных.
Новая концептуальная модель содержит полки и скоросшиватели (структуры данных) плюс шаги для производства сортировки (алгоритмы).
РАСЧЕТЫ ИЛИ СТРУКТУРЫ ДАННЫХ ИЛИ ЛОГИКА
Мы постановили, что лучшим решением задачи является самое простое из адекватных; для каждой проблемы мы должны стремиться к самому простому подходу.
Предположим, мы должны написать код, удовлетворяющий следующим требованиям:
если входной аргумент равен 1, на выходе - 10 если входной аргумент равен 2, на выходе - 12 если входной аргумент равен 3, на выходе - 14
Мы могли бы выбрать один из трех подходов:
`Расчет` ( n) 1- 2* 10 +
`Структура данных` CREATE ТАБЛИЦА 10 C, 12 C, 14 C, ( n) 1- ТАБЛИЦА + C@
`Логика` ( n) CASE 1 OF 10 ENDOF 2 OF 12 ENDOF 3 OF 14 ENDOF ENDCASE
Для данной задачи вычисление результата - самое простое решение. Предполагая, что оно также адекватно (скорость работы некритична), принимаем, что расчет - это наилучшее из решений.
Задача преобразования углов в синусы и косинусы может быть решена более просто (по крайней мере, в терминах строк текста программы и объема объектного кода) с помощью вычисления ответов, нежели при применении структур данных. Однако для многих быстрых приложений лучше извлекать ответ из таблицы, хранимой в памяти. В этом случае простейшим `адекватным` решением является применение таблицы.
Во второй главе мы представили задачу вычисления телефонных тарифов. Эти последние казались близки к произвольным, поэтому мы спроектированли структуру данных:
`Полный тариф` `Средний тариф` `Низкий тариф` ---------------------------------------------------------- Первая мин. .30 .22 .12 ---------------------------------------------------------- Дополнит. мин. .12 .10 .06 ----------------------------------------------------------
Использование структуры данных было проще, чем попытки придумать формулу, с помощью которой эти величины могли быть вычислены. И формула могла позже оказаться неверной. В этом случае управляемый таблицей код легче сопровождать.
В третьей главе мы спроектировали интерпретатор клавиш для нашего Крошечного редактора с использование таблицы решений:
`Клавиша` `Не-вставка` `Вставка` Ctrl-D СТЕРЕТЬ ВЫКЛ-ВСТАВКУ Ctrl-I ВКЛ-ВСТАВКУ ВЫКЛ-ВСТАВКУ Забой НАЗАД ВСТАВИТЬ<
и т.д.
Мы могли бы достигнуть того же результата с помощью логики:
CASE CNTRL-D OF 'ВСТАВКА @ IF ВЫКЛ-ВСТАВКУ ELSE СТЕРЕТЬ THEN ENDOF CNTRL-I OF 'ВСТАВКА @ IF ВЫКЛ-ВСТАВКУ ELSE ВКЛ-ВСТАВКУ THEN ENDOF ЗАБОЙ OF 'ВСТАВКА @ IF ВСТАВКА< ELSE НАЗАД THEN ENDOF ENDCASE
однако логика более запутана. И использование логики для выражения таких содержащих множество условий алгоритмов становится еще более запутанным, если таблица была применена при начальном проектировании.
Использование логики можно рекомендовать, когда результат невычисляем или когда решение не слишком сложно для применения таблицы решений.
Глава 8 посвящена вопросу минимизации использования логики в Ваших программах.
------------------------------------------------------------ СОВЕТ При выборе того, какой подход применить к решения задачи, отдавайте свое предпочтение в следующем порядке: 1. вычисления (кроме случаев, когда существенна скорость) 2. структуры данных 3. логика ------------------------------------------------------------
Конечно, одной из славных черт модульных языков типа Форта является то, что действительная реализация компонента - использует ли он вычисления, структуры данных или логику - не обязана быть видимой для остальной задачи.
РЕШЕНИЕ ЗАДАЧИ: ВЫЧИСЛЕНИЕ РИМСКИХ ЦИФР
В этом разделе мы попытаемся продемонстрировать процесс разработки лексикона. Вместо того, чтобы просто представлять эту задачу и ее решение, мне хотелось бы вместе с Вами с ней разобраться. (Я сохранил запись процесса своего мышления с тех пор, как решал ее впервые.) Вы увидите уже рассмотренные элементы путей решения проблем при их применении в кажущемся случайным порядке - как раз так, как это происходит в действительности.
Вот она: Задача состоит в написании определения, которое получает число со стека и отображает его в виде римской цифры.
Эта задача, вероятнее всего, представляет собой компонент большой системы. Мы, видимо, определим несколько слов при ее решении, включая структуры данных. Однако конкретно лексикон будет включать в себя только одно слово - ПО-РИМСКИ, которое будет получать аргумент со стека. (Иные слова будут внутренними для компонента.)
Мы воспользуемся научным методом - посмотрим на реальность, смоделируем решение, сверим его с реальностью, изменим решение и т.д. Начнем с воспоминаний о том, что представляют собой римские цифры.
Реально мы не помним никаких формальных правил об этих цифрах. Однако если нам дадут число, мы сумеем представить его в римской форме. Мы знаем, как это делается - но не можем пока установить алгоритм этой процедуры.
Так, давайте посмотрим на первые десять римских цифр:
I II III IV V VI VII VIII IX X
Можно сформулировать несколько наблюдений. Первое, имеется некоторое совпадение - когда число представлено количеством символов (3 = III). С другой стороны, используются специальные символы для представления групп (5 = V). Видимо, мы не можем иметь более, чем три символа "I" в ряду до использования следующего символа.
Второе, имеется симметрия вокруг числа пять. Есть символ для пятерки (V), и символ для десятки (Х). Последовательности I, II, III повторяются во второй половине, но с предшествующей V.
На-еденицу-меньше-пяти записывается как IV, а на-единицу-меньше-десяти - как IX. Похоже, что помещение I перед символом большего значения звучит как "на-еденицу-меньше-чем..."
Это смутные, беспорядочные наблюдения. Но все в порядке. Мы просто пока не имеем полной картины.
Давайте изучим, что происходит после десяти:
XI XII XIII XIV XV XVI XVII XVIII XIX XX
Это та же последовательность, что и представленная выше, с добавленным в начале символом "X". Так что имеется также повторяющийся цикл для десяти чисел.
Если мы посмотрим на двадцатые числа, то будет то же, но с двумя "XX" в начале. Таким образом, количество "Х" - то же самое, что и число в разряде десяток исходного десятичного числа.
Это выглядит как важное наблюдение: мы можем разбить наше десятичное число на десятичные цифры, и толковать каждую по отдельности. К примеру, 37 может быть записано как
XXX (тридцать)
и после него
VII (семь)
Это может оказаться преждевременным, однако мы уже видим метод, по которому Форт позволяет нам разбить число на десятичные цифры - делением с остатком на десять. К примеру, если мы напишем
37 10 /MOD
то получим 7 и 3 на стеке (три - как частное - на вершине).
Однако при этом возникает вопрос: как насчет чисел, меньших десяти? Не исключительный ли это случай? Ну, если мы предполагаем, что каждый "Х" представляет десятку, то отсутствие "Х" представляет ноль.
Это - `не` исключительный случай. Наш алгоритм работает даже при числах, меньших десяти.
Давайте продолжим наблюдения, уделяя особое внимание циклам десяти. Мы отмечаем, что сорок будет "XL". Это аналогично тому, как 4 является "IV", только сдвинутое на десять. "Х" перед "L" говорит "на-десять-меньше-пятидесяти". Точно так же,
L (50) аналогично V (5) LX (60) VI (6) LXX (70) VII (7) LXXX (80) VIII (8) XC (90) IX (9) C (100) X (10)
Те же самые последовательности применимы к любым десятичным цифрам - меняются только сами символы. В любом случае ясно, что мы имеем дело с существенно десятичной системой.
Если было бы нужно, мы даже смогли бы написать модель системы для показа римских цифр от 1 до 99, использующую комбинацию алгоритма со структурой данных.
Структура данных:
Таблица единиц Таблица десятков ~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~ 0 0 1 I 1 X 2 II 2 XX 3 III 3 XXX 4 IV 4 XL 5 V 5 L 6 VI 6 LX 7 VII 7 LXX 8 VIII 8 LXXX 9 IX 9 XC
Алгоритм:
Разделить на 10. Частное является числом десятков; остаток - это число единиц. Найти строку для десятков в таблице десятков и напечатать соответствующую последовательность символов. Найти строку для единиц в таблице единиц и напечатать соответствующую последовательность символов.
К примеру, если число равно 72, частное равно 7, остаток - 2. 7 в таблице десятков соответствует "LXX", печатаем это. 2 в таблице единиц дает "II", так что печатаем эти символы.
Результат таков:
LXXII
Мы сконструировали модель, которая работает для чисел от одного до 99. Любое большее число потребует таблицу сотен при начальном делении на 100.
Описанная логическая модель может оказаться удовлетворительной, поскольку выполняет свои функции. Однако как-то не видно, что мы полностью разрешили проблему. Мы не выделяли вопрос о том, как получить основную последовательность, записав все возможные комбинации в многочисленных таблицах. Ранее в данной главе упоминалось о том, что вычисление ответа, если оно возможно, может быть более легким, чем использование структур данных.
Поскольку мы в этой секции изобретаем алгоритмы, давайте проделаем весь путь до конца. Поищем общий алгоритм для составления произвольного числа, с использованием лишь элементарного набора символов. Наша структура данных должна была бы содержать лишь следующую толику информации:
I V X L C D M
При составлении этой таблицы мы также `организовали` символы так, как это кажется правильным. Символы в левой колонке кратны десяти; символы в правой кратны пяти. Далее, символы в каждом ряду ровно в десять раз отличаются от символов над ними.
Другое различие состоит в том, что все символы в первой колонке могут быть скомбинированы, например "XXXIII". Однако нельзя объединять символы в правой колонке, типа "VVV". Полезно ли это наблюдение? Как знать?
Условимся называть символы в первой колонке ЕДИНИЧКИ, а в правой - ПЯТЕРКИ. ЕДИНИЧКИ представляют значения 1, 10, 100 и 1000, то есть значения всех возможных десятичных позиций. ПЯТЕРКИ представляют 5, 50 и 500, то есть значения пятерок во всех возможных десятичных позициях.
Используя эти термины вместо самих символов, мы смогли бы выразить алгоритм для представления любых чисел. (Мы ведь выделили настоящие символы из `подобия` символов.) В частности, мы можем сформулировать следующий начальный алгоритм:
Для любой цифры напечатать столько символов из ЕДИНИЧКИ, сколько необходимо для суммы числа.
Так, для 300 получаем "CCC", для 20 имеем "XX", для одного - "I". И для 321 выходит "CCCXXI".
Такой алгоритм работает вплоть до цифры 4. Теперь давайте расширим его для следующего исключения:
Печатать столько ЕДИНИЧЕК, сколько необходимо для суммы числа, однако если цифра равна 4, напечатать сначала ЕДИНИЧКУ, затем ПЯТЕРКУ.
Таким образом, 40 - это "XL"; 4 - это "IV".
Новый вариант правила работает до числа 5. Как мы заметили раньше, цифры от пяти и выше начинаются с ПЯТЕРКИ. Вновь расширяем наше правило:
Если цифра больше 5, начинать с ПЯТЕРКИ и вычитать пять из числа; иначе этого не делать.
Затем печатать столько из ЕДИНИЧКИ, сколько необходимо для суммы числа. Однако если число равно 4, печатать только ЕДИНИЧКУ и ПЯТЕРКУ.
Такое правило работает до цифры 9. В этом случае мы должны напечатать ЕДИНИЧКУ до - чего? До ЕДИНИЧКИ из следующего десятичного уровня (в ряду под ним). Давайте назовем ее ДЕСЯТКОЙ. Полная наша модель тогда будет:
Если цифра - 5 или более, начинать с ПЯТЕРКИ и вычитать пять из числа; иначе - не делать этого. Затем печатать столько ЕДИНИЧЕК, сколько необходимо для суммы числа. Однако если цифра равна 4, печатать только ЕДИНИЧКУ и ПЯТЕРКУ, а если цифра равна 9, печатать только ЕДИНИЧКУ и ДЕСЯТКУ.
Теперь у нас есть русскоязычная версия алгоритма. Однако осталось еще несколько шагов, которые надо сделать прежде, чем мы сможем запустить эту версию на компьютере.
А именно, нам следует уточниться насчет исключений. Нельзя просто сказать
Сделать А, Б и В. `Но` в таких-то и таких-то случаях сделать что-то другое.
поскольку ЭВМ сделает А, Б и В до того, как рассмотрит их получше.
Вместо этого нам следует проверить наличие исключений `до` того, как что-нибудь делать.
------------------------------------------------------------ СОВЕТ При прокладывании алгоритма вначале примите во внимание исключительные случаи. При написании кода вначале опишите исключения. ------------------------------------------------------------
Это дает нам дополнительное представление об общей структуре нашего числопечатающего слова. Слово должно начинаться с проверки исключений на 4/9. В каждом из таких случаев оно должно сработать соответственно. Если ни одно из исключений не появляется, оно должно выполнять "нормальный" алгоритм. На псевдокоде:
: ЦИФРА ( n ) 4-ИЛИ-9? IF особые случаи ELSE обычный случай THEN ;
Опытный Форт-программист не выписывал бы в действительности этот псевдокод, но скорее сформировал бы мысленное представление о способе устранения особых случаев. Менее опытному могли бы оказаться полезными рисунки структуры в виде диаграмм или в коде, как мы сделали это здесь.
Мы пытаемся минимизировать зависимость программы на Форте от логики. Однако в этом случае нам нужен условный оператор IF, поскольку имеются исключительные ситуации, которые нужно учитывать. Впрочем, мы все равно минимизировали сложность управляющей структуры, ограничив число конструкций IF THEN в данном определении до одной.
Да, нам все еще приходится различать случай 4-х от случая 9-ти, однако мы перепоручили это структурное определние определению более низкого уровня - проверку "4-или-9" и обработку "особого случая".
Что в действительности ясно из нашего определения, так это то, что `любое` из исключений - 4 или 9 - должно запрещать исполнение обычного случая. Недостаточно просто проверять на каждое из исключений, как в такой версии:
: ЦИФРА ( n) 4-СЛУЧАЙ? IF ЕДИНИЧКА ПЯТЕРКА THEN 9-СЛУЧАЙ? IF ЕДИНИЧКА ДЕСЯТКА THEN обычный случай... ;
поскольку без обычного случая никогда не обходится. (Нет способа поместить ELSE перед обычным случаем, поскольку часть ELSE должна находиться между IF и THEN.)
Если мы настаиваем на раздельной обработке обоих исключений, то должны сформировать в каждом из них передачу дополнительного флага о том, что исключение возникло. Если один из этих флагов установлен, тогда обычный случай исключается:
: ЦИФРА ( n) 4-СЛУЧАЙ? IF ЕДИНИЧКА ПЯТЕРКА THEN 9-СЛУЧАЙ? IF ЕДИНИЧКА ДЕСЯТКА THEN OR NOT IF обычный случай THEN ;
Однако этот подход неоправданно усложняет определение, добавляя новые структуры управления. Оставим все как было.
Теперь у нас есть общая идея о структуре нашего главного определения.
Мы сказали: "если цифра - 5 или более, начинать с ПЯТЕРКИ и вычитать пять из числа; иначе ничего не делать. Затем напечатать столько ЕДИНИЧЕК, сколько необходимо для суммы числа".
Прямое преобразование этих правил в Форт может выглядеть как:
( n) DUP 4 > IF ПЯТЕРКА 5 - THEN ЕДИНИЧКИ
Такая запись технически корректна, однако мы знакомы с техникой деления по модулю, а ведь это - типовая ситуация для использования деления по модулю 5.
Если мы поделим число на пять, частное будет нулем (логическая ложь) когда число меньше пяти и единицей (истина) если оно находится между 5 и 9. Мы можем использовать это как булевский флаг для определения того, нужна ли ПЯТЕРКА:
( n) 5 / IF ПЯТЕРКА THEN ...
Частное-флаг становится аргументом для IF.
Далее, остаток от деления на 5 всегда представляет собой число от 0 до 4, что означает возможность (кроме случая исключений) использования остатка непосредственно в качестве аргумента для единичек. Мы перепишем фразу в виде:
( n) 5 /MOD IF ПЯТЕРКА THEN ЕДИНИЧКИ
Возвращаясь к нашим исключениям, мы теперь отмечаем, что на 4 и на 9 можно проверить в единственном месте - а именно, если остаток равен 4. Очевидно, что мы можем сделать наше 5 /MOD вначале, после чего проверить на исключения. Что-то вроде:
: ЦИФРА ( n) 5 /MOD OVER 4 = IF особый случай ELSE IF ПЯТЕРКА THEN ЕДИНИЧКИ THEN ;
(Отметьте, что мы проделали OVER с остатком, поэтому не потеряли его при сравнении с 4.)
Выходит, что мы в конце концов `сделали` IF THEN двойного вложения. Однако это, кажется, правильно, поскольку такой IF THEN обслуживает особый случай. Другой же IF THEN - столь короткая фраза, как "IF ПЯТЕРКА THEN", вряд ли заслуживает того, чтобы делать под нее отдельное определение. Вы, впрочем, можете. (Но мы не будем.)
Давайте сфокусируемся на коде для особых случаев. Вот его алгоритм: "Если цифра - четыре, то напечатать ЕДИНИЧКУ и ПЯТЕРКУ. Для девятки дать ЕДИНИЧКУ и ДЕСЯТКУ".
Можно положить, что цифра обязательно будет либо той, либо другой, иначе мы бы это определение не исполняли. Вопрос в том, как узнать, которая?
Опять же, можно использовать остаток от деления на пять. Если он равен нулю, то цифра была четверкой; иначе - девяткой. Так что мы разыграем ту же партию и используем частное как булевский флаг. Напишем:
: ПОЧТИ ( частное ) IF ЕДИНИЧКА ДЕСЯТКА ELSE ЕДИНИЧКА ПЯТЕРКА THEN ;
При повторном взгляде отметим, что ЕДИНИЧКУ мы исполняем в любом случае.
Можно упростить определение до:
: ПОЧТИ ( частное ) ЕДИНИЧКА IF ДЕСЯТКА ELSE ПЯТЕРКА THEN ;
Мы считаем, что на стеке у нас имеется частное. Давайте вернемся к определению ЦИФРА и подумаем о том, что там происходит:
: ЦИФРА ( n) 5 /MOD OVER 4 = IF ПОЧТИ ELSE IF ПЯТЕРКА THEN ЕДИНИЧКИ THEN ;
Выходит, что у нас имеется не только частное, но под ним и остаток. Мы их оба храним на стеке для случая перехода на часть ELSE. Слово ПОЧТИ, однако, употребляет только частное. Поэтому для сохранения симметрии мы обязаны написать для остатка DROP:
: ЦИФРА ( n) 5 /MOD OVER 4 = IF ПОЧТИ DROP ELSE IF ПЯТЕРКА THEN ЕДИНИЧКИ THEN ;
У нас получилось полное определение в коде для печати одной римской цифры. Если бы мы спешили срочно проверить его до написания необходимых внешних определений, то могли бы легко набросать лексикон слов, нужных для печати группы символов, скажем, ЕДИНИЧЕК:
: ЕДИНИЧКА ." I" ; : ПЯТЕРКА ." V" ; : ДЕСЯТКА ." Х" ; : ЕДИНИЧКИ ( #-единичек) ?DUP IF 0 DO ЕДИНИЧКА LOOP THEN ;
до загрузки наших слов ПОЧТИ и ЦИФРА.
Но мы не столь нетерпеливы. Нет, мы озабочены тем, чтобы слова ЕДИНИЧКА, ПЯТЕРКА и ДЕСЯТКА давали символы, зависящие от положения цифры в числе.
Давайте вернемся к таблице символов, которую рисовали раньше:
ЕДИНИЧКИ ПЯТЕРКИ
единицы I V десятки X L сотни C D тысячи M
Мы встретились также с необходимостью иметь "ДЕСЯТКИ" - т.е. ЕДИНИЧКИ на один ряд ниже. Как если бы на самом деле написать таблицу в виде:
ЕДИНИЧКИ ПЯТЕРКИ ДЕСЯТКИ единицы I V Х десятки X L C сотни C D M тысячи M
Однако это кажется избыточным. Нельзя ли избежать этого? Может быть, попытаться нарисовать другую таблицу, например, линейную:
единицы I V десятки X L сотни C D тысячи M
Можно представить себе, что имя каждого заголовка ("единицы", "десятки" и др.) указывает на позицию соответствующей ЕДИНИЧКИ. Отсюда можно также получить ПЯТЕРКУ, опускаясь на одну строку ниже текущей ЕДИНИЧКИ, и ДЕСЯТКУ, опускаясь на две строки.
Это похоже на создание указателя с тремя стрелками. Мы его можем подсоединить к ряду единиц, как на рис. 4-8б, или к любой другой десятичной степени.
Рис.4-8. Механистическое представление доступа к структуре данных.
единицы -----> -+- ЕДИНИЧКИ --> I |- ПЯТЕРКИ ---> V десятки -----> |- ДЕСЯТКИ ---> X L сотни -----> C D тысячи -----> M
-----------------------------------------
единицы -----> I V десятки -----> -+- ЕДИНИЧКИ --> X |- ПЯТЕРКИ ---> L сотни -----> |- ДЕСЯТКИ ---> C D тысячи -----> M
Опытный фортист вряд ли воображает себе такие указатели или что-нибудь в этом духе. Однако сильный внутренний образ должен присутствовать - как основа для правильного хода мысли - до того, как будет предпринята попытка перенести модель в код.
Новичкам, развивающим в себе правильный метод мышления, может оказаться полезным такое замечание:
------------------------------------------------------------ СОВЕТ Если у Вас возникают проблемы с представлением концептуальной модели - визуализируйте ее, т.е. нарисуйте, в виде механического приспособления. ------------------------------------------------------------
Наша таблица - это просто массив символов. Поскольку на каждый из них нужен всего байт, то давайте в качестве одной "позиции" примем этот один байт. Таблицу мы назовем РИМСКИЕ (*):
CREATE РИМСКИЕ ( единицы) ASCII I C, ASCII V C, ( десятки) ASCII X C, ASCII L C, ( сотни) ASCII C C, ASCII D C, ( тысячи) ASCII M C,
(*) - В некоторый системах применение байтовой компиляции и слова C, запрещено. В этом случае используйте слово , и размер "позиции" в таблице, равный 2-м байтам.
Примечание: такое использование слова ASCII требует, чтобы оно было определено как зависящее от STATE (см. приложение В). Если у Вас слова ASCII нет или оно определено по-иному, пишите:
CREATE РИМСКИЕ 73 C, 86 C, 88 C, 76 C, 67 C, 68 C, 77 C,
Нужный символ из таблицы можно выбрать, одновременно применяя два различных смещения.
Одно измерение представляет десятичное место: единицы, десятки, сотни и т.д. Его устанавливают "текущим", и оно сохраняет свое состояние до тех пор, пока мы его не изменим.
Другое измерение выбирает желаемый тип символа - ЕДИНИЧКУ, ПЯТЕРКУ или ДЕСЯТКУ - внутри текущей десятичной позиции. Это измерение - случайное, то есть мы каждый раз указываем, какой из символов хотим получить.
Давайте начнем с создания "текущего" измерения. Нам нужен способ для указания текущей десятичной точки отсчета. Создадим переменную по имени #ПОЗИЦИИ (произносится "номер-позиции") и пусть в ней хранится смещение в таблице:
VARIABLE #ПОЗИЦИИ : ЕДИНИЦЫ 0 #ПОЗИЦИИ ! ; : ДЕСЯТКИ 2 #ПОЗИЦИИ ! ; : СОТНИ 4 #ПОЗИЦИИ ! ; : ТЫСЯЧИ 6 #ПОЗИЦИИ ! ;
Теперь можно изыскать путь для задания положения "стрелки" - добавляя содержимое #ПОЗИЦИИ к начальному адресу таблицы, оставляемому словом РИМСКИЕ:
: ПОЗИЦИЯ ( -- адр-позиции ) РИМСКИЕ #ПОЗИЦИИ @ + ;
Посмотрим, нельзя ли реализовать одно из слов для печати символа. Начнем с ЕДИНИЧКИ.
Мы хотим, чтобы оно выдавало (через EMIT) символ.
: ЕДИНИЧКА EMIT ;
Работая назад, обнаруживаем, что слово EMIT требует наличия на стеке кода ASCII символа. Откуда он там возьмется? С помощью слова C@.
: ЕДИНИЧКА C@ EMIT ;
Слово же C@ требует `адрес` ячейки, которая содержит нужный символ. Как мы его получим?
ЕДИНИЧКА - это первая "стрелка" перемещаемого указателя - позиция, на которую сразу и показывает слово ПОЗИЦИЯ. Поэтому нужный нам адрес получается просто:
: ЕДИНИЧКА ПОЗИЦИЯ C@ EMIT ;
Теперь давайте напишем слово ПЯТЕРКА. Оно вычисляет тот же адрес ячейки, но потом добавляет к нему единицу для перемещения к следующей ячейки перед получением символа:
: ЕДИНИЧКА ПОЗИЦИЯ 1+ C@ EMIT ;
А ДЕСЯТКА получается так:
: ЕДИНИЧКА ПОЗИЦИЯ 2+ C@ EMIT ;
Три эти определения избыточны. Поскольку единственным различием между ними является смещение, то можно выделить смещение из остальных определений:
: .СИМВОЛ ( смещение) ПОЗИЦИЯ + C@ EMIT ;
Теперь можно определить:
: ЕДИНИЧКА 0 .СИМВОЛ ; : ПЯТЕРКА 1 .СИМВОЛ ; : ДЕСЯТКА 2 .СИМВОЛ ;
Все, что нам остается - это разбить наше полное десятичное число на последовательность десятичных цифр. Благодаря уже сделанным наблюдениям это сделать несложно. На рисунке 4-9 показан наш законченный вариант.
Ура! От проблемы, через концептуальную модель - и к коду.
Замечание: это решение не оптимально. Данная книга не рассматривает фазу оптимизации.
Еще одно соображение: В зависимости от того, где используется эта задача, нам может понадобиться проверка на ошибочные ситации. Действительно, максимальная известная нам цифра - это М, и самое большое число, которое мы способны представить - это 3999 или MMMCMXCIX.
ПО-РИМСКИ можно было бы переопределить таким образом:
: ПО-РИМСКИ ( n) DUP 3999 > ABORT" Слишком велико" ПО-РИМСКИ ;
----------------------------------------------------------------
Мур:
Когда все сделано правильно, появляется вполне определенное ощущение этой правоты. Быть может, такое ощущение и отличает Форт от других языков, в которых никогда не почувствуешь, что действительно все сделано как надо. В Форте восклицаешь "Ага!", и хочется побежать и кому-нибудь об этом рассказать. Разумеется, никто другой не воспримет это так же, как Вы.
----------------------------------------------------------------
Рис.4-9. Решение задачи о римских цифрах.
Блок # 20 0 \ Римские цифры. 8/18/83 1 CREATE РИМСКИЕ ( единицы) ASCII I C, ASCII V C, 2 ( десятки) ASCII X C, ASCII L C, 3 ( сотни) ASCII C C, ASCII D C, 4 ( тысячи) ASCII M C, 5 VARIABLE #ПОЗИЦИИ 6 : ЕДИНИЦЫ 0 #ПОЗИЦИИ ! ; 7 : ДЕСЯТКИ 2 #ПОЗИЦИИ ! ; 8 : СОТНИ 4 #ПОЗИЦИИ ! ; 9 : ТЫСЯЧИ 6 #ПОЗИЦИИ ! ; 10 11 : ПОЗИЦИЯ ( -- адр-позиции) РИМСКИЕ #ПОЗИЦИИ @ + ; 12
Блок # 21 0 \ Римские цифры ... 8/18/83 1 : .СИМВОЛ ( смещение) ПОЗИЦИЯ + C@ EMIT ; 2 : ЕДИНИЧКА 0 .СИМВОЛ ; 3 : ПЯТЕРКА 1 .СИМВОЛ ; 4 : ДЕСЯТКА 2 .СИМВОЛ ; 5 6 : ЕДИНИЧКИ ( #-единичек -- ) 7 ?DUP IF 0 DO ЕДИНИЧКА LOOP THEN ; 8 : ПОЧТИ ( частное-от-5-/ -- ) 9 ЕДИНИЧКА IF ДЕСЯТКА ELSE ПЯТЕРКА THEN ; 10 : ЦИФРА ( цифра -- ) 11 5 /MOD OVER 4 = IF ПОЧТИ DROP ELSE IF ПЯТЕРКА THEN 12 ЕДИНИЧКИ THEN ; 13
Блок # 22 0 \ Римские цифры ... 8/18/83 1 : ПО-РИМСКИ ( число -- ) 1000 /MOD ТЫСЯЧИ ЦИФРА 2 100 /MOD СОТНИ ЦИФРА 3 10 /MOD ДЕСЯТКИ ЦИФРА 4 ЕДИНИЦЫ ЦИФРА ;
ИТОГИ
В этой главе мы научились разрабатывать отдельные компоненты, начав с размышлений над их синтаксисом, затем продолжив определением их алгоритма(ов) и структур данных, и завершив все реализацией на Форте.
Этой главой мы завершаем обсуждение стадии проектирования. В оставшейся части книги мы рассмотрим стиль и технику программирования.
ЛИТЕРАТУРА
1. G. Polya. `How To Solve It: A New Aspect of Mathematical Method,` (Princeton, New Jersey, Princeton University Press). 2. Leslie A. Hart, `How the Brain Works,` (c) 1975 by Leslie A. Hart, (New York, Basic Books, Inc., 1975). 3. Evan Rosen, "High Speed, Low Memory Consuption Structures," `1982 FORML Conference Proceedings,` p.191. 4. Michael Stolowitz, "A Compiler for Programmable Logic in FORTH," `1982 FORML Conference Proceedings,` p.257.
ДЛЯ ДАЛЬНЕЙШИХ РАЗМЫШЛЕНИЙ
Спроектируйте компонент и опишите алгоритм(ы), необходимые для имитации тасования колоды карт. Этот алгоритм должен давать массив чисел от 0 до 51, сформированный случайным образом.
Разумеется, специальным ограничением здесь является то, что ни одна карта не может встречаться в колоде дважды.
Можно положить, что у Вас имеется генератор случайных чисел по имени CHOOSE. Он берет со стека аргумент "n" и дает случайное число в диапазоне от нуля до n-1 включительно. (См. "Генератор бессмысленных сообщений", глава 10 из "Начального курса...")
Сможете ли Вы спроектировать алгоритм перетасовки так, чтобы избежать утомительных проверок неопределенного количества ячеек памяти при каждом прохождении цикла? Можете ли Вы этого достичь, используя всего один массив?
