|
|
Часть 2
Г Л А В А 2
============
ВВЕДЕНИЕ В СИСТЕМУ ПРОГРАММИРОВАНИЯ JPI Modula-2
================================================
Modula-2 - это современный язык программирования общего назначения. Он был создан Ник-
лаусом Виртом и является прямым наследником языка Pascal, который также был разработан Вир-
том. Вы можете думать о языке Modula-2, что он "лучше", чем Pascal. Вирт создавал язык, ко-
торый можно было бы использовать для программирования функций очень низкого уровня (доступ
к дискам, ввод/вывод через порты и т.п.), наряду с высокоуровневым программированием, та-
ким, как базы данных, компиляторы, процессоры слов и расчетные системы. (Система программи-
рования JPI Modula-2 в настоящее время написана на языке Modula-2 фирмы JPI).
Данная глава содержит краткое описание некоторых основных особенностей JPI Modula-2. В
следующих разделах вы сможете найти более полное описание интересующих вас вещей.
Модули
------
Программа на Modulа-2 обычно содержит набор модулей. Каждый модуль представляет собой
набор соответствующих процедур и данных, представляющих изолированную секцию всей програм-
мы. Модуль состоит из двух частей: модуля описаний (definition module), описывающего, что
данный модуль может делать, и модуля реализаций (implementation module), который описывает
способ осуществления данных функций.
Модуль описаний содержит список всех процедур и данных, к которым вы имеете доступ.
Все процедуры и данные, не включенные в модуль описаний, остаются локальными в модуле реа-
лизаций и, следовательно, не "видимы" из остальных частей программы. Модуль, использующий
другой модуль, называется "клиент". Модуль, предоставляющий функции другому модулю, называ-
ется "сервер". Модуль может одновременно быть и клиентом, и сервером.
Точно так же, как процедура является абстракцией для скрытия деталей, так и модуль мо-
жет использоваться для скрытия деталей целого ряда связанных с ним процедур и любых общих
структур данных.
Раздельная компиляция
---------------------
Модули могут транслироваться независимо и сохраняться в виде объектного кода, который
позднее может стать частью полной программы. Система JPI Modula-2 поставляется с развитым
набором модулей для ввода/вывода, управления окнами, управления процессами, обработкой
строк и т.д.
Автоматические библиотеки
-------------------------
Modula-2 имеет встроенные средства управления автоматическими библиотеками. Компилятор
в ходе компиляции модуля генерирует библиотечный файл. Такой подход делает возможным вклю-
чение системой только тех процедур и структур данных, которые действительно используются в
конечной программе.
Автоматический поиск в библиотеках
----------------------------------
Поскольку каждый модуль содержит спецификации ресурсов, используемых им из других мо-
дулей, то программа-компоновщик (linker) требует только указания имени главной main прог-
раммы. Если различные библиотечные модули имеют одинаковое назначение, то система позволяет
вам указать последовательность, в которой библиотеки будут просматриваться.
Определение (указание) модулей, которые всегда будут
------------------------------------------------------
перекомпилироваться
-------------------
Поскольку компилятор JPI Modula-2 весьма высокоскоростной (более 20000 строк в мину-
ту), то все видимые модули определений, используемые в программе, всегда перекомпилируются.
Такой подход имеет следующие преимущества:
- позволяет перекомпиляцию модулей реализации в любом порядке;
- позволяет избежать проблем, связанных с управлением версиями, связанных с модулями
определений. Вы могли сталкиваться с такими проблемами, если ранее использовали другие ком-
пиляторы Modula-2;
- уменьшает число необходимых файлов за счет того, что становятся не нужны "символь-
ные" файлы (symbol files) для модулей определений.
Возможность автоматического MAKE
--------------------------------
В больших программах зависимости между модулями могут стать весьма запутанными; JPI
Modula-2 обеспечивает возможность автоматического MAKE (построения программ), что позволяет
проводить высокоскоростной анализ всех зависимостей между модулями и проверку времени соз-
дания модулей. После этого система перекомпилирует только модули, исходные тексты которых
претерпели изменения после последней компиляции.
Расширенные структуры данных
----------------------------
Поддерживаются полностью все структуры данных, с которыми вы могли познакомиться, ис-
пользуя языки С или Pascal. В число их входят: знаковые и беззнаковые целые различных раз-
меров, числа с плавающей точкой, многоразмерные массивы, записи с вариантами, 64-Кбайтные
множества, короткие и длинные указатели, переменные процедур и прочие.
Полное управление сегментами
----------------------------
JPI Modula-2 располагает уникальной особенностью, позволяющей вам использовать сегмен-
тированную память процессоров 80x86. Ваши программа и данные могут достигать размера в 1
Мбайт и в то же время использовать "короткие вызовы" для выбранных процедур как внутри, так
и за пределами модулей. Вы можете также использовать "короткие указатели" для повышения
скорости выполнения. В отличие от ряда других языков, позволяющих использовать короткие
указатели только в выбранных сегментах, JPI Modula-2 позволяет одновременно использовать
короткие указатели в любых выбранных вами сегментах. Вы можете даже циклически перемещать
сегменты в ходе выполнения программы, чтобы добиться оптимального использования доступной
памяти (см. ГЛАВУ 6 для получения дополнительной информации).
Контроль типов
--------------
Для того, чтобы обеспечить повышенную надежность в программировании, Modula-2 имеет
даже более строгий контроль типов, чем ее предшественник Pascal. В то же время, Modula-2
дает возможность обойти при необходимости контроль типов. Это дает возможность реализовать
любые "хитрости", которые вы захотите, чтобы достигнуть своих целей наилучшим путем.
Процедуры
---------
Тип "Процедуры" позволяет производить динамическое назначение процедур переменным.
Modula-2 располагает возможностями расширенной обработки параметров процедур. Вы можете пе-
редать массив любого размера в одну и ту же процедуру либо даже передать процедуру в ка-
честве параметра. JPI Modula-2 также располагает средствами, позволяющими просто реализовы-
вать процедуры обработки прерываний.
Расширенные операторы управления
--------------------------------
Modula-2 содержит все операторы управления, реализованные в Pascal. Вдобавок Modula-2
содержит, помимо прочих вещей, конструкцию типа LOOP...END, выйти из которой вы можете, ис-
пользуя так много точек выхода, как вам будет необходимо (см. ГЛАВУ 6 для получения полного
множества операторов управления). Поскольку вычисление логических условий завершается, как
только значение условия становится определено, то использование операторов управления в
Modula-2 становится более простым и более эффективным, чем в языках, не обеспечивающих этой
возможности.
Многозадачность
---------------
Modula-2 имеет встроенную поддержку многозадачности. Библиотека JPI Modula-2 включает
программу-планировщик, использующую временное квантование, и облегчающую реализацию парал-
лельных процессов в системе.
Управление программой
---------------------
Вы имеете возможность полностью управлять всеми аспектами своей программы. Это осу-
ществляется небольшим количеством "встроенных" процедур, а также отсутствием скрытых преоб-
разований типов, что не позволяет вам запутаться.
JPI Modula-2 поддерживает только полный исходный текст
в библиотеке и системе времени исполнения.
Среда разработки программ
-------------------------
Система JPI Modula-2 - это система разработки программ, которую вы можете настроить
под свои собственные требования.
Отладка
-------
В силу того, что Modula-2 - это сильно типизированный язык, множество потенциальных
ошибок обнаруживается на этапе компиляции. Все "стандартные" ошибки времени выполнения
(превышение размера массива, использование пустого (NIL) указателя и т.д.) могут быть прер-
ваны системой. При запуске программы из среды, система установит курсор в позиции вашего
исходного текста, соответствующей положению ошибки. Это происходит практически мгновенно,
без рекомпиляции вашей программы.
* * *
Данная глава содержит только чрезвычайно сжатое описание языка Modula-2; ГЛАВА 4 со-
держит описание ряда возможностей путем приведения нескольких интересных примеров, а если
вы нуждаетесь в более полной и точной информации, ГЛАВЫ 6 и 7 описывают язык Modula-2 в де-
талях.
Г Л А В А 3
============
НАЧАЛО
======
Содержимое дистрибутивных дисков
--------------------------------
Вы получили три дискеты. Одна из них помечена JPI Modula-2 System, другая - JPI Modula
-2 Library Objects (объектные коды библиотек) и третья - JPI Modula-2 Library Source (ис-
ходные тексты библиотек).
Диск, помеченный System, содержит следующие файлы:
M2.EXE Главная программа;
M2.OVL Оверлейный файл главной программы;
M2.ERR Сообщения компилятора об ошибках;
M2.MNU Переконфигурированное описание меню;
M2.HLP Текст режима "Помощь";
М2.XXX Используется в системе без жесткого диска
(см. позднее).
Только три первых файла являются необходимыми при запуске JPI Modula-2.
Диск, помеченный Library Objects, содержит:
*.DEF Модули определений;
*.OBJ Объектные коды библиотечных модулей;
DEMO.MOD Короткая демонстрационная программа;
PROG*.MOD Примеры;
PROG*.DEF Примеры.
Для использования JPI Modula-2 библиотеки необходимы только файлы *.DEF и *.OBJ.
Диск, помеченный Library Source содержит исходный текст библиотеки.
Этот диск не нужен для запуска системы!
Система на жестком диске
------------------------
Система на жестком диске стартуется четырьмя простыми шагами:
1. Создайте каталог на своем жестком диске, например, C:\JPIM2;
2. Скопируйте содержимое дисков "SYSTEM" и "LIBRARY OBJECTS" в созданный каталог;
3. Войдите в созданный каталог и запустите систему, введя М2 в ответ на подсказку ДОС;
4. Нажмите <ДОП+R> (Alt+R) и ответьте DEMO, когда JPI
Modula-2 запросит имя главного (Мain) файла. Нажмите <ВВОД> (Enter) и пронаблюдайте компи-
ляцию, связывание и выполнение демонстрационной программы.
Система на двух флоппи-дисках
-----------------------------
Флоппи-дисковая система устанавливается и запускается пятью простыми шагами:
1. Создаются копии дисков, помеченных "SYSTEM" и "LIBRARY OBJECTS".
2. Копия диска "SYSTEM" помещается на дисковод А:, а копия диска "LIBRARY OBJECTS" -
на дисковод В:.
3. Переименовывается файл А:М2.XXX в A:M2.RED.
4. Войдите на диск А: и стартуйте систему вводом М2 в ответ на подсказку ДОС.
5. Нажмите <ДОП+R> (Alt+R) и ответьте DEMO на запрос JPI Modula -2 имени главного
(Main) файла. Нажмите <ВВОД> (Enter) и проследите компиляцию, связывание и выполнение де-
монстрационной программы.
Следует отметить важность корректного выполнения шага 3, в противном случае система не
будет знать, где находится библиотека.
ПРОДОЛЖЕНИЕ
===========
Если вы терпеливы
-----------------
Если вы обладаете достаточным терпением, то познакомьтесь с ГЛАВОЙ 4, содержащей при-
меры. Перед дальнейшим использованием среды небесполезно будет просмотреть ГЛАВУ 5.
Если вы не любите читать руководства
------------------------------------
В таком случае мы думаем, что вы найдете полезной для себя клавишу .
Нажмите и самостоятельно разберитесь, как компилировать и выполнять програм-
мы-примеры, названные PROG*.MOD.
Г Л А В А 4
============
ВЫБОРОЧНОЕ ИЗУЧЕНИЕ Modula-2
============================
Эта глава содержит ряд программ выборочного обучения, которые являются неформальным
введением в язык Modula-2. Полное понимание того, как работают программы, не является необ-
ходимым; каждый пример является иллюстрацией отдельных аспектов языка, а не конструирования
сложных алгоритмов. Тем не менее, мы попытались сделать примеры интересными. Следует также
отметить, что уровень знания о программировании, как нам кажется, резко возрастает от при-
мера к примеру.
Ниже представлена первая программа.
Hello
-----
MODULE prog1;
(* Эта программа пишет "hello" на экране. *)
FROM IO IMPORT WrStr;
BEGIN
WrStr('hello');
END prog1.
Xотя это весьма простая программа, она содержит ряд интересных моментов, которые сле-
дует понять, прежде чем двигаться далее.
Буквы верхнего и нижнего регистров не эквивалентны. Слова, имеющие специальное значе-
ние в компиляторе, всегда записываются в верхнем регистре (прописные буквы).
MODULE prog1 сообщает, что программа называется prog1. Файл, в котором текст программы
запоминается, должен иметь имя prog1.mod, чтобы совпадать с именем модуля.
Комментарии начинаются с (* и заканчиваются *). Они не влияют на содержимое программы,
а содержат подсказки, предназначенные человеку-читателю. (Однако комментарии, начинающиеся
со знака (*$, интерпретируются как инструкции компилятору).
FROM IO IMPORT WrStr организует доступ к процедуре WrStr в библиотечном модуле IO, что
делает эту процедуру доступной для использования в остальной части программы. IO - это
стандартный библиотечный модуль, поставляемый вместе с системой JPI Modula-2.
BEGIN помечает начало выполняемых операторов. Операторы являются частями программы,
которые выполняют действия при запуске программы.
Оператор WrStr('hello') выводит строку 'hello' на устройство вывода. В Modula-2 нет
встроенного оператора 'print', вместо этого ввод/вывод организуется вызовами библиотечных
процедур.
END prog1. помечает конец программы (объявление полного завершения).
Конечно же, эта первая программа не является полезной.
С этой точки зрения другие примеры более полезны.
Пифагоровские вычисления
------------------------
MODULE prog2;
(* Эта программа выводит Пифагоровы тройки. *)
FROM IO IMPORT WrStr, WrLngCard, WrLn;
VAR a,b,c:LONGCARD;
BEGIN
FOR c := 1 TO 100 DO
FOR b := 1 TO c DO
FOR a := 1 TO b DO
IF a*a + b*b = c*c THEN
WrLngCard(a,1);
WrStr(', ');
WrLngCard(b,1);
WrStr(', ');
WrLngCard(c,1);
WrLn;
END;
END;
END;
END;
END prog2.
Программа находит положительные числа а, в, с, удовлетворяющие формуле а*а + в*в =
с*с. Например, 3*3 + 4*4 = 9+16 = 25 = 5*5, так что решением является: а=3, в=4, с=5. Если
стороны треугольника имеют такие значения, то треугольник является прямоугольным. Согласно
легенде (возможно, и неверной), древние египтяне использовали этот факт при строительстве
пирамид.
Метод, используемый программой, - это подход "грубой силы" - берутся числа а, в и с и
проверяется, удовлетворяется ли заданное условие. а, в и с должны быть представлены пере-
менными: это объекты, принимающие различные значения в ходе выполнения программы. Каждая
переменная должна быть объявлена, прежде чем она будет использоваться.
Предложение
VAR a,b,c:LONGCARD
объявляет переменные а, в, с, и извещает, что они могут принимать любые числовые значения:
0,1,2,3...
Оператор FOR c := 1 TO 100 DO ... END вызывает повторяющееся (циклическое) выполнение
операторов, заключенных между DO и END с переменной с, принимающей последовательно значения
1,2,...,100.
Прочие операторы FOR подобны первому и, поскольку они "вложены", то переменные получа-
ют всевозможные сочетания
( a<=b<=c ).
Чтобы сделать более легким понимание, какой END соответствует какому FOR, мы используем
соглашение, что END записывается прямо под соответствующим FOR, и операторы между ними
сдвигаются. Такое соглашение применимо и к другим операторам, требующим END.
Оператор IF a*a+b*b=c*c THEN ...END объявляет, что операторы между THEN и END выполня-
ются только в том случае, если текущие значения а, в, с удовлетворяют равенству. Таким об-
разом, на выводное устройство попадают только интересующие нас тройки.
В порядке упражнения вы можете попытаться найти решения для уравнения а*а*а + в*в*в +
с*с*с = d*d*d.
Музыка
------
MODULE prog3;
(* Эта программа исполняет музыкальные ряды (гаммы). *)
FROM Lib IMPORT Sound, NoSound, Delay;
FROM MATHLIB IMPORT Exp, Log;
CONST MiddleC = 131.0;
TYPE NoteType = SHORTINT;
TYPE ScaleType = ARRAY [1..8] OF NoteType;
CONST major = ScaleType(0,2,4,5,7,9,11,12);
CONST minor = ScaleType(0,2,3,5,7,8,11,12);
PROCEDURE PlayScale(mode:ScaleType; key:NoteType);
VAR
i:[1..8];
note:NoteType;
freq:LONGREAL;
BEGIN
FOR i:=1 TO 8 DO
note:=key+mode[i];
freq:=MiddleC*Exp(LONGREAL(note)*(Log(2.0)/12.0));
Sound(CARDINAL(freq));
Delay(200);
END;
NoSound;
Delay(500);
END PlayScale;
BEGIN
PlayScale(major,0); (* до мажор *)
PlayScale(minor,2); (* ре минор *)
END prog3.
Программа использует встроенный динамик вашего компьютера для исполнения пар музыкаль-
ных гамм. Процедура, вызываемая как PlayScale, определена как имеющая 2 параметра. Первый
параметр определяет интервалы гамм, второй определяет первую ноту гаммы.
Определения процедур похожи по форме на определения программ: они содержат объявления,
за которыми следует список операторов. В программе используются два вызова PlayScale:
PlayScale(major,0) - исполняет гамму до мажор, a PlayScale(minor,2) - гамму ре минор.
Оператор вида
variable:=expression
(переменная:=выражение)
извещает, что значение переменной устанавливается равным значению выражения. В выражениях,
где встречается переменная, используется ее текущее значение.
Типы данных используются для указания, какие значения может принимать переменная. В
языке Modula-2 определены стандартные типы, такие как: SHORTINT, LONGREAL, CARDINAL,
LONGCARD, CHAR, BOOLEAN. Помимо этого, существуют различные способы создания новых типов
данных. Следует отметить, что существует много способов представления значений чисел.
Представление должно выбираться таким образом, чтобы значение каждого выражения попадало бы
в заданные границы.
Modula-2 - это "сильно типизированный" язык. Это означает, что тип каждого выражения
должен быть корректным для контекста, в котором он встречается. Как правило, типы операндов
бинарного оператора (оператора, имеющего два операнда) должны совпадать. Выражение может
быть преобразовано в другой тип заключением его в круглые скобки () и помещением имени тре-
буемого типа перед ними. В примере переменная note преобразуется из SHORTINT в LONGREAL.
Предложение
TYPE ScaleType = ARRAY[1..8] OF NoteType
объявляет новый тип данных, называемый ScaleType, значения которого состоят из восьми неза-
висимых компонент, пронумерованных 1,2,...,8. В программе mode объявляется являющейся типа
ScaleType. Доступ к компонентам можно получить при помощи конструкции mode[e], где е - не-
которое выражение. Т.о., присваивание note := key+mode[i] устанавливает значение note рав-
ным сумме значений переменной key и i-й компоненты переменной mode.
Помимо этого в программе имеются несколько определений констант.
CONST MiddleC = 131.0
извещает, что всюду, где встретится имя MiddleC следует подставлять значение 131.0.
CONST major = ScaleType(0,2,4,5,7,9,11,12)
извещает, что всюду, где встретится имя major, следует использовать тип ScaleType с пере-
численными значениями компонент.
Следующая программа также использует массив, но более сложным способом.
Анаграмма
---------
MODULE prog4;
(* Эта программа выводит перестановки в строках в алфа-
витном порядке. *)
IMPORT IO,Str;
TYPE StringType = ARRAY [0..9] OF CHAR;
PROCEDURE NextPerm(n:CARDINAL;
VAR s:StringType;
VAR wrap:BOOLEAN);
(* Данная процедура модифицирует s путем последовательных перестановок первых n симво-
лов в s. Последовательность перемещений, генерируемая последовательными вызовами, создается
в "алфавитном" порядке. Если s является последней строкой в последовательности, то возвра-
щается первая. Логическая переменная результата wrap используется для сигнализации об этом
событии. *)
VAR
i:CARDINAL; (* s[i-1] - текущий символ - кандидат
на изменение. *)
j:CARDINAL; (* s[j] - символ, меняемый местами
с s[i-1]. *)
tmp:CHAR;
BEGIN
IF n = 0 THEN
wrap := TRUE;
RETURN;
END;
i := n-1;
LOOP
IF i = 0 THEN
wrap := TRUE;
EXIT;
END;
IF s[i-1] < s[i] THEN
j := n-1;
WHILE s[j] <= s[i-1] DO
j := j-1;
END;
tmp := s[j]; s[j] := s[i-1]; s[i-1] := tmp;
(* перестановка *)
wrap := FALSE;
EXIT;
END;
i := i-1;
END;
(* s[i]..s[n-1] находятся в обратном порядке, требуется произвести их перестановку за
минимальное число перемещений. *)
j := n-1;
WHILE i 0; (* Заполнить, используя два
цвета. *)
radius := 2 + RANDOM(5);
WHILE NOT IO.KeyPressed() DO
bounce(x);
bounce(y);
Disc(x.q, y.q, radius, color);
Circle(x.q, y.q, radius, color MOD 4);
END;
Disc(0,0,Width+Depth, 0); (* Очистить экран. *)
END;
TextMode;
End prog6.
Модуль Graph предоставляет ряд основных процедур для доступа к экрану в графическом
режиме 200x320 точек. Отметим, что в данном примере Width и Depth - это константы, импорти-
рованные из Graph. Modula-2 позволяет импортировать процедуры, константы, переменные и ти-
пы.
Программа объявляет тип ЗАПИСЬ (RECORD), с именем FunnyType. Записи полезны для свя-
занных переменных. Доступ к компонентам переменной типа ЗАПИСЬ, называемым "ПОЛЯ", осущест-
вляется либо использованием символа '.' и именем поля, как в процедуре init, либо использо-
ванием WITH, как в процедуре bounce. Xотя операторы WITH могут облегчить работу с типами в
программе, но они могут сделать текст трудным для чтения, поэтому лучше воздерживаться от
их использования.
Приведенная программа использует "низкоуровневый" клавиатурный ввод - IO.KeyPressed()
сообщает, была ли нажата клавиша, IO.RdCharDirect() читает один символ с клавиатуры без вы-
вода его на эхо или выполнения любой другой обработки. (Примечание. Функции, не имеющие па-
раметров, должны вызываться с использованием пустого списка параметров).
Функция RANDOM(n) возвращает "псевдо-случайное" число в диапазоне 0..n-12.
RANDOMIZE инициализирует различные последовательности чисел для генерации каждый раз
при запуске программы (в зависимости от времени и даты).
Программа сортировки строк текста в порядке возрастания.
Сортировка
----------
MODULE prog7;
(* Сортировка строк в файле в порядке возрастания, уда-
ляя повторяющиеся. *)
IMPORT IO, FIO, Lib, Storage, Str;
TYPE
StringType = ARRAY [0..255] OF CHAR;
StringPointerType = POINTER TO StringType;
VAR
p : ARRAY [1..10000] OF StringPointerType;
PROCEDURE Less(i,j:CARDINAL):BOOLEAN;
BEGIN
RETURN Str.Compare(p[i]^, p[j]^) < 0;
END Less;
PROCEDURE Swap(i,j:CARDINAL);
VAR tmp:StringPointerType;
BEGIN
tmp := p[i]; p[i] := p[j]; p[j] := tmp;
END Swap;
VAR s: StringType;
len:CARDINAL;
i,n:CARDINAL;
InFile,OutFile:FIO.File;
buffer:ARRAY [1..512+FIO.BufferOverhead] OF BYTE;
BEGIN
(* Контроль параметров. *)
IF Lib.ParamCount() <> 2 THEN
IO.WrStr('Try again :prog7 input-file output-file');
IO.WrLn;
HALT;
END;
(* Читать строку в *)
Lib.ParamStr(s, 1); InFile := FIO.Open(s);
FIO.AssignBuffer(InFile, buffer);
n :=0;
LOOP
FIO.RdStr(InFile, s);
IF FIO.EOF THEN
EXIT;
END;
IF n = HIGH(p) THEN
IO.WrStr('Too many lines!');
IO.WrLn;
EXIT;
END;
INC(n);
len := Str.Length(s);
Storage.ALLOCATE(p[n], len + 1);
Lib.Move(ADR(s), ADR(p[n]^), len + 1;
END;
FIO.Close(InFile);
(* Сортировать файл в памяти. *)
Lib.HSort(n, Less, Swap);
(* Выдать файл. *)
Lib.ParamStr(s, 2); OutFile := FIO.Create(s);
FIO.AssignBuffer(OutFile, buffer);
FOR i := 1 TO n DO
IF (i = 1) OR (Str.Compare(p[i]^, p[i-1]^) <> 0) THEN
FIO.WrStr(OutFile, p[i]^);
FIO.WrLn(outFile);
END;
END;
FIO.Close(OutFile);
END prog7.
Lib.ParamCount() возвращает количество параметров в командной строке при вызове прог-
раммы.
Lib.ParamStr(s,n) копирует n-й параметр в s. Если программа запускается из среды JPI
Modula-2, то командная строка может быть установлена при помощи Options-Command-Line.
Для представления файла программа использует массив указателей. Если х - это перемен-
ная-указатель, то х^ представляет объект, на который указывает х. Каждая строка файла свя-
зывается с блоком памяти требуемого размера. Модуль FIO (файловый ввод/вывод) используется
для чтения/записи дисковых файлов. Вызов процедуры FIO.AssignBuffer может быть опущен, но
программа тогда будет работать значительно медленнее. Размер буфера выбирается так, чтобы
оптимизировать работу с диском. Заметим, что необходимо закрывать открытый файл, используя
FIO.Close; в противном случае буфер не будет записан в файл.
Прямое копирование не может быть использовано для копирования в выделенную память,
т.к. только len+1 байтов было выделено, а p[n]^:=s будет копировать 256 байтов, поэтому
вместо него следует использовать библиотечную процедуру Lib. Move. Встроенную функцию ADR,
возвращающую адрес переменной, следует применять очень аккуратно, поскольку ее параметры не
контролируются на тип.
Процедура Lib.HSort имеет в качестве параметров количество в массиве, который должен
быть отсортирован, и два параметра типа "Процедура" (Procedure), являющихся подпрограммами
для сравнения и перестановки элементов.
QSort - это альтернативная процедура, которая также может быть использована и которая
представляет другой алгоритм (Quicksort вместо Heapsort), который является более быстрым в
среднем, но более медленным в наихудшем случае. Ниже подробно описывается реализация
Lib.QSort, т.к. она использует рекурсивную процедуру.
Фрагменты файлов Lib.def и Lib.mod:
-----------------------------------
DEFINITION MODULE LIb;
...
TYPE
CompareProc = PROCEDURE(CARDINAL, CARDINAL):BOOLEAN;
SwapProc = PROCEDURE(CARDINAL, CARDINAL);
PROCEDURE QSort(n:CARDINAL; Less:CompareProc;
Swap:SwapProc);
...
END Lib.
IMPLEMENTATION MODULE Lib;
...
PROCEDURE QSort(n:CARDINAL; Less:CompareProc;
Swap:SwapProc);
PROCEDURE Sort(l,r:CARDINAL);
VAR i,j:CARDINAL;
BEGIN
WHILE r > l DO
i := l+1;
j := r;
WHILE i <= j DO
WHILE (i <= j) AND NOT Less(l,i) DO INC(i) END;
WHILE (i <= j) AND Less(l,j) DO DEC(j) END;
IF i <= j THEN Swap(i,j); INC(i); DEC(j) END;
END;
IF j # l THEN Swap(j,l) END;
IF j+j > r+l THEN (* Рекурсивные вызовы. *)
Sort(j+1,r);
r := j-1;
ELSE
Sort(l,j-1);
l := j+1;
END;
END;
END sort;
BEGIN
Sort(1,n);
END QSort;
...
END Lib.
Процедура Sort объявляется в процедуре QSort. Следует отметить, что она имеет доступ
как к своим параметрам и локальным переменным охватывающей процедуры.
QuickSort - алгоритм функционирует по методу деления файла на основе выбранного эле-
мента (в данном случае первого), и затем рекурсивного вызова себя самого для сортировки
двух получившихся массивов. Вызов для сортировки старшей половины заменяется на циклический
возврат в начало процедуры (производится "остаточно-рекурсивная" оптимизация), что обеспе-
чивает потребность в небольшом размере стека, необходимом для рекурсивной активации. Одной
из проблем использования рекурсии является то, что размер необходимого стека будет изме-
няться в зависимости от размера входа (size of the input(?)). Директива компилятора "конт-
роль стека" (* $S+ *) может использоваться для проверки переполнения стека (что производит,
если его не контролировать, весьма непредсказуемый эффект), хотя, конечно, и будет иметь
следствием некоторое увеличение времени исполнения.
В заключение приводится более длинный пример, иллюстрирующий ряд особенностей языка
Modula-2, которые еще не упоминались: переменные типы, записи с вариантами и операторы вы-
бора CASE.
Калькулятор
-----------
MODULE prog8;
IMPORT IO,Str,Storage;
TYPE
TokenType = (number, add, sub, mul, div, LeftParen,
RightParen, end);
SyntacticType = (main, exp, term, factor);
TreeType = POINTER TO TreeRecordType;
TreeRecordType = RECORD
CASE kind:TokenType OF
| number:
NumberValue : LONGREAL;
| add,sub,mul,div :
left : TreeType;
right : TreeType;
END;
END;
VAR
c:CHAR;
token:TokenType;
TokenNumberValue:LONGREAL;
PROCEDURE error(s:ARRAY OF CHAR);
BEGIN
IO.WrStr(s);
IO.WrLn;
HALT;
END error;
PROCEDURE readtoken;
VAR
s:ARRAY[0...99] OF CHAR;
i:[0..99];
done:BOOLEAN;
oldc:CHAR;
BEGIN
LOOP
oldc := c;
c := IO.RdChar();
CASE oldc OF
| ' ' :
| '+' : token := add; EXIT;
| '-' : token := sub; EXIT;
| '*' : token := mul; EXIT;
| '/' : token := div; EXIT;
| '(' : token := LeftParen; EXIT;
| ')' : token := RightParen; EXIT;
| CHAR(10),CHAR(13),CHAR(26) :token := end; EXIT;
| '0'..'9' : (* читает действительное число *)
i := 1; s[0] := oldc;
WHILE (c >= '0') AND (c <= '9') DO
s[i] := c;
INC(i);
c := IO.RdChar();
END;
IF c<>'.' THEN (* добавляет десятичную точку, если
нет ничего на входе *)
s[i] := '.';
INC(i);
ELSE
REPEAT (* читает дробную часть *)
s[i] := c;
INC(i);
c := IO.RdChar();
UNTIL (c < '0') OR (c > '9');
END;
s[i] := CHAR(0);
TokenNumberValue := Str.StrToReal(s, done);
IF NOT done THEN
error('Bad number?');
END;
token := number;
EXIT;
ELSE
error('Bad character');
END;
END;
END readtoken;
PROCEDURE read(what:SyntacticType):TreeType;
VAR t,t1:TreeType;
BEGIN
CASE what OF
| factor :
IF token = LeftParen THEN
readtoken;
t := read(exp);
IF token = RightParen THEN
readtoken;
ELSE
error("Missing ')'");
END;
ELSIF token = number THEN
Storage.ALLOCATE(t, SIZE(t^));
t^.kind := number;
t^.NumberValue := TokenNumberValue;
readtoken;
ELSE
error('Missing number?');
END;
| term:
t := read(factor);
WHILE (token = mul) OR (token = div) DO
t1 := t;
Storage.ALLOCATE(t, SIZE(t^));
t^.kind := token;
readtoken;
t^.left := t1;
t^.right := read(factor);
END;
| exp:
t := read(term);
WHILE (token = add) OR (token = sub) DO
t1 := t;
Storage..ALLOCATE(t, SIZE(t^));
t^.kind := token;
readtoken;
t^.left := t1;
t^.right := read(term);
END;
| main :
c := IO.RdChar();
readtoken;
t := read(exp);
IF (token <> end) THEN
error('Missing operator?');
END;
END;
RETURN t;:
END read;
PROCEDURE eval(t:TreeType):LONGREAL;
BEGIN
CASE t^.kind OF
| number : RETURN t^.NumberValue;
| add : RETURN eval(t^.left) + eval(t^.right);
| sub : RETURN eval(t^.left) - eval(t^.right);
| mul : RETURN eval(t^.left) * eval(t^.right);
| div : RETURN eval(t^.left) / eval(t^.right);
END;
END eval;
VAR
t:TreeType;
result:LONGREAL;
BEGIN
LOOP
IO.WrStr('Enter expression : ');
t := read(main);
result := eval(t);
IO.WrStr(' = ');
IO.WrLngReal(result, 4, 0);
IO.WrLn;
END;
END prog8.
Программа представляет собой простой интерактивный калькулятор, запрашивающий выраже-
ние, преобразующий его в "дерево" и затем вычисляющий его и печатающий результат. Выражения
обычно представляются в виде деревьев, например, выражение (5-9)*(4+7) представляется в ви-
де диаграммы дерева:
*
/ \
- +
/ \ / \
5 9 4 7
(по ряду причин диаграммы-"деревья" обычно изображаются растущими вниз, с "корнем" в верши-
не).
Объявления
TokenType = (number,add,sub,mul,div,LeftParen,
RightParen,end);
SyntacticType = (main,exp,term,factor);
объявляют перечислимые типы данных. Значениями перечислимых типов являются перечисли-
мые в списках величины.
Объявления
TreeType = POINTER TO TreeRecordType;
TreeRecordType = RECORD
CASE kind:TokenType OF
| number:
NumberValue:LONGREAL;
| add,sub,mul,div:
left:TreeType;
right:TreeType;
END;
END;
объявляют "рекурсивный" тип данных. Это означает, что дерево создается в зависимости от
kind, и содержит либо действительное число, либо левое и правое поддеревья. Ключевое слово
CASE обозначает вариантное предложение. Конечно, это может быть обьявлено посредством
TreeType = POINTER TO TreeType;
TreeRecordType = RECORD
king:TokenType;
NumberValue:LONGREAL;
left:TreeType;
right:TreeType;
END;
Но такое определение гораздо хуже представляет смысл предложения и, к тому же, требует
больше памяти.
В представленной программе имеются несколько операторов CASE, используемых для выбора
одной из групп операторов для выполнения в зависимости от выражения, следующего за ключевым
словом CASE.
Метки вариантов должны быть константами, но допускаются диапазоны, например, '0'..'9'.
Оператор CASE в процедуре readtoken имеет дополнительную часть ELSE, которая выполня-
ется, если не обнаруживается совпадения ни с одной из меток выбора.
На этом мы завершаем раздел обучения. Мы надеемся, что приведенные в нем примеры ока-
зались интересными для вас. Конечно же, мы не осветили здесь многих пунктов. Другие главы
руководства дают более сжатую, но полную информацию, которую вы можете использовать как
справочную. Кроме того, выпущено большое количество хороших книг по Modula-2, в том числе
книга Никлауса Вирта "Программирование на языке Modula-2" (третье издание).
|
|