Кичкайло Т.А., Тушев А.Н. Функциональное и Логическое Программирование

Подождите немного. Документ загружается.

список и символьный атом Непосредственная обработка выполняется в том случае,

когда искомое выражение попадает на верхний уровень скобок В этом случае

обрабатываемый список должен иметь вид (QUOTIENT (SIN A) (COS

А)),

причем в

качестве А может быть выражение произвольной сложности. Для возможности замены

этого списка на (TG А) определяемая функция должна проверить следующие условия:

а) на соответствующих местах списка находятся QUOTIENT, SIN, COS, а не

другие

s-выражения,

б) аргументы у SIN и COS совпадают.

Если условия а) и б) выполнены, исходный список заменяется на построенный

(TG А), причем аргумент А извлекается из SIN или из COS.

SYMBOLIC;

NIL

PROCEDURE SINCOS X;

IF NULL X THEN NIL % терминальные ветви

ELSE IF ATOM X THEN X % общей рекурсии

ELSE IF CAR X EQ

'QUOTIENT

AND CAADR X EQ

'SIN

AND CAADDR X EQ

'COS

% проверка условия а)

AND CADADR X = CADAR CDDR X % проверка условия б)

THEN

LIST('TG,CADADR

X) % построение списка

% с

арг.

из SIN

ELSE SINCOS CAR

X.SINCOS

CDR X; % общая рекурсия

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

функций CAR и CDR пришлось разбить на две функции, так как максимальная глубина

последовательных вызовов

CxxxxR

равна 4 (раздел 1.3.4).

Переопределим теперь функцию

AEVAL

для проверки правильности работы

функции SINCOS (раздел 4.7).

PROCEDURE AEVAL

SINCOS CADR X;

OPERATOR SINCOS;

NIL

ALGEBRAfC;

6: SINCOS((SIN(A*B)/COS(A*B))

3);

TG(A*B)

В приведенном определении имеется один "скрытый дефект". Обратимся к

функции SINCOS следующим образом:

7:SINCOS

(SIN(SIN(A)/COS(A))/COS(SIN(A)/COS(A)));

SIN

(A)

TG(

)

COS

(A)

Причина дефекта состоит в том, что при построении списка аргумент TG не

проверяется на возможность выполнить внутри него замену. Для исправления функции

SINCOS достаточно заменить команду

LIST('TG,CADADR

X) на

LIST(TG,

STNCOS

CAD

ADR X), то есть проверить и преобразовать аргумент до построения списка. После

этого исправления функция

SINCOS

выполняет замену всегда!

8:SINCOS

(SIN

(A) /COS (A) ) /COS

(SIN

(A) /COS (A) ) )

;

TG(TG(A)

)

Определить

функцию, выполняющую простейшее символьное

дифференцирование.

Реализовать правила:

а) производная константы равна

нулю;

б) производная переменной по этой же переменной равна 1;

e)dln(x)/dx

l/x;

г) производная суммы равна сумме

производных.

Пример:

(ln(z)+a*c+z+b)'

=l/z+0+l+0.

Для решения задачи сначала определим функцию-предикат, позволяющую

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

считается

формула,

в которой отсутствует переменная дифференцирования. Поскольку

все формулы представляются в виде списков, определяемая функция должна проверять,

содержится ли данный атом в заданном списке.

Проверка выполняется на всех уровнях

вложенности,

поэтому функция

определяется методом общей рекурсии. Предельными случаями общей рекурсии

являются пустой список и символьный атом. В пустом списке искомый символьный

атом, очевидно, не

содержится,

а в случае символьного атома его необходимо сравнить

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

должна давать ответ Т, если искомый атом находится в голове ИЛИ в хвосте.

Вышеизложенное дает возможность полностью определить функцию.

SYMBOLIC;

NIL

PROCEDURE

MEMBR(A,X);

А-список,

Х-искомый

атом

NULL

THEN

NIL % в

пустом

списке

нет

атомов

ELSE

ATOM

THEN

IF A EQ X

THEN

является

ли

ELSE NIL % атом Искомым

ELSE

MEMBR(CAR

A,X)

MEMBR(CDR

A,X);

% рекурсивная

ветвь,

связующей функций является OR.

MEMBR

MEMBR('(А

В(С

(DE)F)),

'E);

Запись дифференцирования для переменной и логарифма не представляет

сложности, поэтому рассмотрим подробнее дифференцирование суммы выражений.

Пусть уже определена функция

DIFF(A,X),

позволяющая дифференцировать по

любому правилу, кроме суммы. Определим теперь вспомогательную функцию

DIFLIST(A,X).

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

s-выражений

(Ai,A2,..

,AN)

Функция DIFLIST должна вернуть список из производных этих

выражений по переменной X:

(Ai',A

',...,AN').

Функция DIFLIST легко определяется

методом хвостовой рекурсии. Необходимо рекурсивно брать голову списка

А,

ее

дифференцировать (вызывать функцию

DIFF)

и ставить на место.

4: PROCEDURE DIFLIST (А, X)

;

IF NULL A THEN NIL

ELSE

DIFF(CAR

A,X)

DIFLIST(CDR

A,X);

DIFLIST

Теперь представим, что на вход функции DIFF подана сумма выражений, которая

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

Кг

... AN). Тогда,

поскольку производная суммы выражений равна сумме производных, для

дифференцирования суммы нужно выполнить следующие действия:

а) убрать из списка голову

PLUS;

б) обратиться к функции DIFLIST, которая согласно своему определению вернет

список производных:

(Ai',A2',...,AN'),

в) поставить голову PLUS на место.

Ниже приведено полное определение функции DIFF. Заметим, что в нем функции

DIFF и DIFLIST взаимно вызывают друг друга, то есть в определении используется

метод взаимной рекурсии. Обратите также внимание на переопределение функции

AEVAL

для случая главной функции (DIFF) с двумя аргументами.

5: PROCEDURE

DIFF(A,X);

IF NULL

MEMBR(A,X)

THEN 0 % проверка, что А является

% константой,

т.е.

X не содержится в А

ELSE IF ATOM A THEN 1

% сравнивать символьный атом А с X нет необходимости,

% т.к. при неравенстве выполняется первое условие

% проверки А на константу.

ELSE IF CAR A

'LN

AND ATOM CADR A

% проверка, что А является логарифмом с аргументом -

% символьным атомом. Также нет необходимости сравнивать

% аргумент логарифма с X,

т.к.

при неравенстве

% выполняется условие проверки А на константу

THEN

LIST('QUOTIENT,1,X)

% построение списка

1/Х

ELSE IF CAR A EQ

'PLUS

% проверка, что А является суммой выражений

THEN

'PLUS

DIFLIST(CDR

A,X)

% дифференцирование DIFLIST списка выражений

ELSE A;

% не подходят все правила, оставить А без изменений

DIFF

,72

PROCEDURE AEVAL X;

DIFF(CADR

X,CADDR

X);

**** AEVAL is redefined. **

ALGEBRAIC;

DIFF(X+A*B+LN(X)+LN(Z)

1 + 0 +

1/X

+ 0

переопределение AEVAL

4.10

ТЕСТЫ

ДЛЯ

САМОКОНТРОЛЯ

1 Что определяет приведенное ниже условие, если X - некоторый список?

IF CDR X THEN

Список пустой.

Список не пустой.

Список состоит из одного элемента.

d) Список состоит из более чем одного элемента.

Список одноуровневый.

2 В чем дефект приведенной ниже программы на r-Лиспе, заменяющей выражение

F(X) на

SIN(X)

для произвольного аргумента?

PROCEDURE

F(X)

;

IF ATOM X THEN X

ELSE IF CAR EQ 'F THEN

'SIN

. CDR X

ELSE F CAR X . F CDR X;

Отсутствует проверка на пустой список

NULL X.

b) Одинаковое название заголовка функции F и заменяемой функции

F(X).

Функция не работает для выражения вида:

F(F(X)).

d) Функция заменяет выражения F(X) на

SIN(X),

но не работает для других

переменных.

Замена выполняется только для переменных, но не для произвольных

выражений: F(Y)

-»

SIN(Y)

, но F(X*Z) не заменяется на

SIN(X*Z).

3. Используя операторы

г-Лиспа

и представление математических выражений в виде

списков,

записать замену выражения

-(X)

на -X, для произвольной формулы X.

Какая функция

правильная

a) PROCEDURE

ZAMENA(X);

IF CAR X EQ

'MINUS

THEN

'MINUS

. CADR X;

b) PROCEDURE

ZAMENA(X);

IF CAR X EQ

'MINUS

THEN

LIST('MINUS,CAADR

X);

c) PROCEDURE

ZAMENA(X);

IF CAR X EQ

'MINUS

.AND.

NULL ATOM CADR X THEN

'MINUS

. CAADR X;

d) PROCEDURE

ZAMENA(X);

IF CAR X EQ

'MINUS

.AND.

NULL ATOM CADR X THEN

'MINUS

. CADR X;

e) PROCEDURE

ZAMENA(X);

IF CAR X EQ

'MINUS

.AND.

NULL ATOM CADR X THEN LIST

('MINUS,CADR

X);

4 Пусть требуется написать программу преобразования

LN(Ai+

AN)=LN(AI)+

+LN(AN) всюду, где встречается сумма логарифмов Какой

тип рекурсии из рассмотренных ранее

понадобится

Достаточно хвостовой рекурсии, т к преобразуемое выражение

представляется в виде одноуровневого списка (LN

AN)

b) Необходима общая рекурсия, т к преобразуемое выражение может

встретиться как часть более сложного выражения

Необходим метод накапливающих параметров, обычной рекурсией

преобразование сделать

затруднительно

d) Необходима взаимная рекурсия, т к возможны случаи

LN(LN(A+B)+LN(C+D))

Для решения данной задачи применения рекурсии не требуется

5 Требуется выполнить некоторое преобразование над выражением вида а-b Какое из

приведенных ниже условий обеспечивает проверку, что X - выражение именно

такого

вида

a) IF CAR X EQ

'DIFFERENCE

OR (CAR X EQ

'PLUS

AND CADDR

X EQ

'MINUS

AND NULL CDDDR X)

b) IF CAR X EQ

'DIFFERENCE

OR (CAR X EQ

'PLUS

AND CAADDR

X EQ

'MINUS

AND NULL CDDR X)

c) IF CAR X EQ

'DIFFERENCE

t)R

(CAR X EQ

'PLUS

AND CAADDR

X EQ

'MINUS

AND NULL CDDDR X)

d) IF (CAR X EQ

'DIFFERENCE

AND NULL CDR X

)OR

(CAR X EQ-

'PLUS

AND CAADDR X EQ

'MINUS

AND NULL CDDDR X)

e) IF (CAR X EQ

'DIFFERENCE

AND NULL CDDR X

)OR

(CAR X

'PLUS

AND CAADDR X EQ

'MINUS

AND NULL CDDDR X)

Ответы:

l.d;

2.c; 3.c; 4.b;

S.c.

5 ПОСТРОЕНИЕ ЧЕРТЕЖЕЙ В СИСТЕМЕ

АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

АВТОКАД

Автокад

является наиболее распространенной в настоящее время системой по

автоматизации проектирования в машиностроении,

строительстве,

архитектуре и

других областях. Основой Автокада является мощный графический редактор,

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

графических примитивов. Изображения строятся в выбранной системе координат и с

высокой точностью отображаются на внешнем носителе (принтере, графопостроителе,

плоттере)

с заданным масштабом.

Особенностью Автокада является способ хранения чертежей в виде списков,

элементами которых являются графические примитивы, и внутренний язык для

обработки и анализа этих списков - Автолисп, являющийся диалектом стандартного

Лиспа.

В данной главе рассматриваются характеристики и основные команды

графического редактора системы Автокад версии

11.0,

автоматическое построение

новых чертежей и модернизация существующих с помощью программ на Автолиспе,

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

автоматическому построению

модернизации изображений Автокада.

5.1

ПОСТРОЕНИЕ ИЗОБРАЖЕНИЙ ГРАФИЧЕСКИМ

РЕДАКТОРОМ АВТОКАДА

5.1,1

Краткая характеристика графического редактора \

При загрузке Автокада на экране появляется главное

меню:

0. Exit

AutoCad

;

Выйти из Автокада

Begin

a NEW

drawing

;

Начать

НОВЫЙ

рисунок

Edit

EXISTING

drawing;

Отредактировать

СУЩЕСТВ,

рис.

9. Recover damaged drawing

;

Восстановление испорченного рис.

Для начала работы можно выбрать пункт построения нового рисунка или

загрузить существующий чертеж из списка файлов. Рисунки Автокада хранятся в

векторном виде в файлах с расширением

dwg.

В отличие от растровой

формы,

когда

хранится информация о каждой точке изображения, в векторной форме кодируется

последовательность команд для построения

чертежа,

что позволяет создавать очень

компактные файлы. В векторной форме также хранятся, например, шрифты

(*.chr)

системы Турбо-Паскаль.

После выбора пунктов 1 или 2 главного меню система Автокад загружает

графический редактор, который имеет следующий вид:

Рис. 7. Общий вид графического редактора

Автокода

В строке команд набираются команды Автокада. Если команда начинается с

символа

"(",

она считается функцией Автолиспа Например, набрав команду (CAR

'((A)

С)),

получим в строке подсказок ответ: (А). При этом если сообщение занимает

несколько строк, видны только последние. Чтобы увидеть все сообщение, следует

нажать клавишу

F1,

предназначенную для отключения панели графического редактора.

Команды,

не-

начинающиеся со скобки, считаются собственно командами

Автокада, предназначенными для построения и обработки чертежей. Кроме

йабора

команды в строке команд, ее можно выбрать из иерархического экранного меню. Вход

в экранное меню выполняется клавишей INS.

Клавиши со стрелками позволяют перемещать графический курсор (пересечение

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

клавиши PgUp и PgDn соответственно увеличивают или уменьшают величину шага

перемещения графического курсора.

Выход из графического редактора выполняется командой QUIT.

5.1.2

Основные команды графического редактора

Выполнить произвольную команду Автокада можно, набрав ее в строке команд.

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

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

точкам на

крнцах

диаметра, по трем точкам окружности и т.д. Кроме этого, любую

команду можно выполнить из программы на Автолиспе Для этого используется

встроенная функция Автолиспа COMMAND, которая имеет вид (COMMAND

"НАЗВАНИЕ КОМАНДЫ

АВТОКАДА"

"ПАРАМЕТР

2,"

)

Рассмотрим пример выполнения команды построения окружности После ввода в

строке команд команды рисования окружности CIRCLE на экране появится строка

выбора параметров этой команды

3P/2P/TTR/<Center

pomt>

2P означает изображение

окружности по двум противоположным точкам

диаметра,

ЗР - по трем точкам на

окружности, TTR - по двум касательным и радиусу и, наконец, параметр

<Center

pomt>

означает выбор центра окружности Выбор точки выполняется путем ввода ее

координат через запятую в строке команд или подведения графического курсора к

определенному положению на экране и нажатия клавиши <Ввод> Если выбрать

параметр 2Р, набрав эти символы в строке команд, появятся последовательно запросы

на ввод первой и второй точки противоположных концов диаметра При этом,

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

изменением положения изображаемой окружности Этот принцип "резиновой нити"

выполняется для всех команд Автокада Выполнить построение окружности по двум

точкам на концах диаметра с координатами 100,150 и 200,220 из программы на

Автолиспе можно строкой

(COMMAND "CIRCLE"

"2Р"

'(ЮО

150)

'(200

220))

Если же требуется построение окружности по центральной точке с координатами

100,120 и радиусу 50, то построение выполняется функцией (COMMAND "CIRCLE"

'(100

120)

50)

Из приведенных примеров видно, что точка на плоскости в Автолиспе

представлена списком из двух своих координат Ниже приведен ряд важных команд

Автокада с указанием их особенностей при вызове из Автолиспа

Команда LINE предназначена для построения последовательности отрезков,

причем началом последующего отрезка является конец предыдущего Для завершения

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

последнего отрезка, или ввести параметр "С" для соединения конца последнего

отрезка с началом всей последовательности Соответствующие команды Автолиспа

имеют вид

(COMMAND

"LINE"

'(XI

Yl)

...

'(XN

YN)

"")

(COMMAND

"LINE"

'(XI

Yl) ...

'(XN

YN)

"C"),

пустая строка в первой команде означает завершение последовательности построения

Команды

ELLIPSE,

DOUGHNUT, POLIGON предназначены соответственно для

построения эллипса, кольца и правильного

n-угольника

Каждая

*из

этих команд имеет

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

окружности, дает

вариантов ее построения

Команда PLINE (ПОЛИЛИНИЯ) позволяет рисовать последовательность

чередующихся отрезков и дуг, переключая их параметрами A (Arc) и L (Line) Кроме

этого, данная команда позволяет менять тип линий и их ширину Рассмотрим пример

использования этой команды на Автолиспе (COMMAND "PLINE"

'(30

40) "А" "СЕ"

'(20

45)

'(40

65)

"L"

'(100

65)

"W"

4 0

'(105

65)

"")

Сначала от точки с координатами

(30,40) до точки (40,65) проводится дуга (параметр А) с центром в точке с

координатами (20,45) (параметр СЕ) Затем из конечной

точки'дуги

в горизонтальном

направлении до точки с координатами (100,65) проводится отрезок прямой (параметр

L) Последний небольшой отрезок

(100,65)-(105,65)

является отрезком переменной

ширины (W) от 4 до 0 и выглядит как "уголок", а вместе эта пара отрезков изображает

"стрелку" Завершается команда PLINE также как и LINE.

Команда TEXT позволяет вывести строку заданной высоты и направления в

заданной точке Например, команда Автолиспа (COMMAND "TEXT"

'(100

200) "10"

"90" "AUTOCAD") выводит текст AUTOCAD, верхняя левая точка которого имеет

координаты (100,200), высота текста равна 10 и угол направления - 90° (вверх). Другие

параметры команды выравнивают текст по центру или правому краю, меняют стиль и

шрифт

Команда HATCH выполняет штриховку замкнутых объектов Обычно в

Автолиспе используется следующий формат этой команды (COMMAND "HATCH"

"U"

»45"

"4"

"N"

'(XI

Yl)

'(XN

YN) ) Параметр U означает, что штриховка выполняется

прямыми линиями, причем линии расположены под углом 45°, расстояние между ними

равно 4, и линии не перекрещиваются

(N)

Точки

(XI,Yl),

(XN

YN)

должны

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

Автокад распознает наличие замкнутой области, он выполняет ее штриховку с

указанными параметрами

Команда LIMITS устанавливает границы изображения После ввода команды

следует набрать новые координаты левого нижнего и правого верхнего угла При этом

заметим, что, во-первых, для того, чтобы увидеть результат действия команды LIMITS,

необходимо вслед за ней выполнить команду ZOOM (ПОКАЖИ) с параметром А

(АИ

Все) Из Автолиспа данная команда выполняется строкой (COMMAND "ZOOM"

"A").

Во-вторых, размеры изображения не устанавливаются произвольно Например, при

задании границ (COMMAND "LIMITS"

'(0

'(300

200) ) на самом деле

будут

установлены

границы'

(0,0) - (320-200), так как такой прямоугольник

пропорционален

размерам поля рисунка графического редактора. Команда ZOOM позволяет также

увеличивать выбранный фрагмент изображения на

все

поле рисунка, то есть

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

команды LIMITS и ZOOM ALL используются перед началом построения изображений.

Команда REDRAW (ОСВЕЖИ) выполняет перерисовку экрана. Когда

Автокад

создает изображения,

на

экране появляются различные

вспомогательные

пометки,

помогающие в процессе построения чертежей. Для их удаления и используется в конце

построения команда REDRAW, которая позволяет увидеть "очищенный" чертеж.

Команда GRCLEAR очищает поле рисунка графического редактора.

Перечисленных команд достаточно для построения простых чертежей.

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

обратиться к специальной литературе по

Автокаду

или к технической документации.

5.2 ОСОБЕННОСТИ ЯЗЫКА АВТОЛИСП

Язык Автолисп является диалектом стандартного Лиспа и по своему синтаксису

практически совпадает с muLisp, который был рассмотрен в первой главе. Вместе с тем

Автолисп имеет ряд

дополнительных

функций, которые связаны с его применением как

языка построения и анализа изображений. Эти особенности и рассмотрены в настоящем

разделе. Функция

Авто

лиспа COMMAND рассмотрена в предыдущем параграфе.

Прежде всего для построения чертежей необходимы точные расчеты, поэтому

вещественная арифметика является важной составной частью Автолиспа. Кроме

арифметических функций

"-ь",

"-",

"*",

"/",

выполняющих операции над числами с

плавающей точкой (например, (/ 1.5Е10

4.5Е-3)).,

в Автолиспе есть и элементарные

математические функции с вещественными аргументами. Перечислим некоторые из

них:

(ЕХРТ А В) - возведение в степень А ;

, (SIN A), (COS A), (ATAN А) - синус, косинус и арктангенс от вещественных

аргументов (Углы выражаются в

радианах)',

(SQRT A), (EXP A), (LOG A) - квадратный корень, экспонента и натуральный

логарифм от вещественных аргументов.

Важным типом данных в Автолиспе являются строки, использующиеся,

например, для вывода текста на изображениях. Строки в Автолиспе заключаются в

двойные кавычки (например, "Это строка") и для работы с ними используется ряд

функций, полностью аналогичных соответствующим функциям Си.