Этюды для программистов

Муэрс (Mooers С. N.). Computer Software and Copyright, Computing Surveys, 7, I, pp. 45—72, 1975.

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

Муэрс (Mooers С. N.). How Some Fundamental Problems are Treated in the Design of the TRAC Language. In Symbol Manipulation Languages and Techniques, edited by D. G. Bobrow. North-Holland Publishing Co., Amsterdam, pp. 178—190, 1968.

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

Муэрс (Mooers С. N.). TRAC, A Procedure-Describing Language for the Reactive Typewriter. CACM, 9, 3, pp. 215—219, 1966.

Нельсон (Nelson Т. Н.). Computer Lib or Dream Machines. Hugo's Book Service, Chicago, IL, 1974.

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

Стрейчи (Strachey С). A General Purpose Macrogenerator. Comput. J. 8, 3, pp. 225—241, 1966.

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

Вегнер (Wegner P.). Programming Languages, Information Structures, and Machine Organization. McGraw-Hill, New York, NY, 1978.

И Браун, и Вегнер с позиций общей информатики обсуждают Трак наряду с другими макропроцессорами.

РЕШЕНИЯ

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

29. Красьте с нами, или... ПОЛНОЕ РЕШЕНИЕ ЗАДАЧИ

В данной главе в полном виде приводится программа для задачи о раскраске карты (см. гл. 3). Читатели, которым довелось испытать это на собственной шкуре, знают как трудно описывать программу, излагая алгоритм прозрачно и просто. Когда решение головоломки рассказано, обычной реакцией бывает: «Как я не догадался!» вместо: «Как здорово!» Ну а программа — это, конечно, тоже решение головоломки. Из описаний всегда устраняют дух исследования, историю неудавшихся подходов и отступлений, упоминание о глупых ошибках, сбивавших с правильного пути. Если бы мы попытались полностью изложить процесс разработки программы, вы бы не знали, плакать вам или смеяться над тупостью автора. Так что лучше пойдем уже проторенной дорогой от задачи к решению, лишь изредка поглядывая по сторонам. [61]

По условию задачи требуется раскрасить карту или неориентированный граф в минимальное число цветов так, чтобы никакие два соседних региона (никакие две смежные вершины) не были одного цвета. Хотя в данный момент не требуется точно специфицировать формат исходной и выводимой информации, а также внутреннее представление данных, можно сообразить, какие свойства графа будут существенны для любой программы. Очевидно, нужно знать число вершин графа, уметь регулярным образом обращаться к вершинам, уметь раскрашивать вершины и узнавать их цвет, определять, являются ли две вершины смежными, и, наконец, нужно уметь порождать много различных цветов. Проще всего удовлетворить перечисленным требованиям, обозначив вершины натуральными числами 1, 2, ..., n, где n — общее количество вершин. Аналогично и цвета обозначим натуральными числами (ясно, что при этом в нашем распоряжении окажется много цветов). Вопрос о конкретном способе определения смежности вершин целесообразно отложить.