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

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

При выполнении команды IN файл, содержащий программные модули,

загружается в систему. Сами модули набираются во внешнем редакторе. Если в файле

нет ошибок, то система выводит очередной номер приглашения к диалогу. Чтобы при

загрузке модуля не возникала ошибка "Encountered EOF unexpectedly" ("Неожиданно

встретился конец файла"), в конце загружаемого модуля следует добавить команду

"End;",

которая воспринимается системой как завершение файла.

Выход из системы Reduce-З выполняется командой QUIT.

4.6 ВНУТРЕННИЙ ЯЗЫК СИСТЕМЫ

REDUCE-3

4.6.1 Общая структура системы

Reduce-3

Ядром

системы Reduce-З является интерпретатор стандартного Лиспа. Все

команды внешнего языка системы транслируются в функции Лиспа, а затем

выполняются указанным интерпретатором Сам транслятор с внешнего языка Reduce-З

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

В системе имеется специальный флаг

DEFN,

включив который, можно отменить

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

команд в Лисп.

Пример'

х:=а+Ь;

(SETK

(AEVAL(LIST

'PLUS

'А

'В)))

Результатом оценки аргумента функции

AEVAL

будет список (PLUS А В),

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

AEVAL

выполняет

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

SETK

обеспечивает присваивание

Внутренний язык Reduce-З, который называется

г-Лисп,

используется в тех

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

неэффективно r-Лисп отличается от стандартного Лиспа лишь формой написания

команд, которая напоминает соответствующие команды Паскаля и проще для записи.

Перед выполнением команды

г-Лиспа

эта команда, как и команда внешнего языка,

транслируется в соответствующую команду стандартного Лиспа и выполняется

интерпретатором стандартного Лиспа. Транслятор с

г-Лиспа

в стандартный Лисп также

написан на стандартном Лиспе

Внешний язык Reduce-З называется алгебраическим режимом

системы,

внутренний язык - символьным режимом. При запуске система Reduce-З находится в

алгебраическом режиме Для перехода из алгебраического режима в символьный

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

алгебраический выполняется командой ALGEBRAIC. Команды символьного режима

завершаются точкой с запятой

Общая структура Reduce-З таким образом имеет

вид-

Алгебраический symbolic

режим

algebraic

Гранслятор на стандарт-

юм

Лиспе из алгебраи-

lecKoro

режима в стан-

дартный Лисп

^^^"

Символьный

режим

Транслятор на стан-

дартном Лиспе из

r-Лиспа в стандарт-

ный Лисп

••

Интерпретатор

стандартного

Лиспа

Рис. 6. Общая структура системы

Reduce-3

Таким образом, для установки системы Reduce-З на произвольном типе

компьютеров, достаточно иметь на этих компьютерах только интерпретатор

стандартного Лиспа

4.6.2 Синтаксические особенности

г-Лиспа

В приведенных ниже примерах показано большинство синтаксических

конструкций

г-Лиспа

в сравнении с

muLisp

и стандартным Лиспом

г-Лисп

MuLisp Стандартный Лисп

-23;

-23 -23

Числа во всех трех диалектах имеют одинаковый вид. Любая команда г-Лиспа

оканчивается точкой с запятой

А; А А

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

стандартном Лиспе и

г-Лиспе

только переменные Т и NIL равны изначально сами себе

Обращение к другим переменным, у которых нет значения,

^вызывает

сообщение об

ошибке

(A+B)/C-D*E;

(-(/(+

В)

С)

(difference (quotient

(* D E)) (plus А

В)С)

(times D

Е))

В r-Лиспе арифметические функции можно записывать в виде алгебраических

выражений, при этом сохраняется обычный приоритет операций В стандартном Лиспе

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

используются английские слова.

г-Лисп

MuLisp

Стандартный Лисп

'A;

(QUOTE А) или

'А

Только в самых первых интерпретаторах Лиспа не использовался апостроф для краткой

записи функции QUOTE В стандартном Лиспе существует такое обозначение

Х:=А;

(SETQ X A) (SETQ Z А)

Запись присваивания в

г-Лиспе

аналогична записи присваивания в Паскале, при этом

смысл операции полностью соответствует функции SETQ, в частности, она возвращает

в качестве значения оценку операнда

А,

как в языке Си

CAR(X)

или CAR X; (CAR X) (CAR X)

г-Лиспе

аргумент функции ставится в скобки, как принято в математике Более того,

если аргумент

единственный,

он может быть без скобок

CONS

(А,

В) или А . В (CONS А В) (CONS А В)

г-Лиспе

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

Для функции CONS имеется краткое обозначение в виде точки между аргументами

А<В

А В) (LESSP А В)

А>В

(> А В) (GREATERP А В)

А=В (EQUAL

А'В)

(EQUAL А В)

A EQ В (EQ А В) (EQ А В)

В r-Лиспе предикаты сравнения располагаются между операндами, и для функции

EQUAL имеется краткое обозначение в виде равенства В стандартном Лиспе для

неравенства используются

идентификаторы,

не содержащие символов, отличных от

букв и цифр

AND

. . . AND An

(AND

...

An)

(AND

...

An)

...

А„

(OR

...

An) (OR

...

А„)

г-Лиспе

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

IF A THEN В ELSE С (IF А В С) (COND (А В) (Т

С))

Запись условной функции в

г-Лиспе

аналогична соответствующему оператору Паскаля

muLisp

имеется как функция

EF,

так и функция COND, в стандартном Лиспе

используется только COND

PROCEDURE А В; С;

(DEFUN

ABC)

(DE А В С)

А - символьный атом, являющийся именем определяемой функции, В - список

формальных параметров, С -

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

являющееся телом определяемой функции.

При определении новых функций в muLisp допускается использование в теле

определяемой функции нескольких

s-выражений

(раздел 5), в стандартном Лиспе и г-

•Лиспе допустимо только одно

s-выражение.

г-

Лиспе

список формальных параметров,

состоящий из одного элемента, можно не заключать в скобки, если же элементов

несколько, они разделяются запятыми. Запишем на

г-

Лиспе

функцию, вычисляющую

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

разделе 2

PROCEDURE LAST

IF NULL CDR X THEN CAR X

ELSE LAST CDR X;

Обратите внимание на полное отсутствие скобок в данном определении!

Определим теперь функцию двух аргументов: списка X и числа К, функция

должна первый элемент списка увеличивать на К, второй - на

К+1

и т.д. до последнего

элемента.

PROCEDURE

F1(X,K);

IF NULL X THEN NIL

ELSE (K+ CAR X) .

(CDR

X,K+1);

Сравните данное определение с записью функции на muLisp, приведенной в

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

сложения.

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

г-

Лиспе

может содержать лишь одно s-

выражение,

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

BEGIN,END.

Ниже приведен пример записи итерационной процедуры на

г-

Лиспе

для

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

PROCEDURE F

BEGIN

SCALAR

I,K;

I:=l;

K:=l;

I=N

THEN RETURN

K:=K*I;

GOTO A;

END;

Сравните данную программу с программой на стандартном Лиспе, приведенной в

разделе 3.1 Можно заметить, что

BEGIN,END

соответствуют функции PROG, в

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

функция GO, а метки в

г-

Лиспе

аналогичны меткам Паскаля.

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

выше функции из

г-

Лиспа

в стандартный

Лисп.

4.6.3 Отладка программ в

г-Лиспе

Язык

г-Лисп

позволяет включить трассировку выбранных функций. Трассировка

включается функцией TRACE

А,

где А-список трассируемых функций. В момент

вызова произвольной функции из списка на экран выводится имя функции с

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

также выводится.

Пример: включим в трассировку все функции, входящие в функцию LAST,

приведенную в данном разделе и обратимся к ней со списком из двух элементов.

TRACE

'(LAST

CAR CDR

NULL);

NIL

LAST

'(1

;

- вызов функции с исходным списком

- это вызов функции в условии IF

- функция возвращает хвост списка (1 2)

NULL

применяется

результату

CDR

аргумент

NULL

не

равен

NIL

- этот вызов CDR внутри ELSE оператора IF

- функция CDR возвращает тот же результат

- рекурсивный вызов исходной функции

- функция CDR из условия оператора IF

- хвост списка из одного элемента - пустой

NULL

аргументом

NIL

- дает в результате Т

терминальная ветвь

рекурсии

(THEN)

- первый элемент списка

(2)

- значение LAST из терминальной ветви

- рекурсивное возвращение значения

LAST[(12)]

CDR[(1

]

CDR

(2)

NULL[(2)]

NULL = NIL

CDR[(1

2)]

CDR =

(2)

LAST[(2)]

CDR[(2)]

CDR = NIL

NULL[NIL]

NULL = Т

CAR[(2)]

CAR

LAST = 2

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

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

4.7 ПРЕДСТАВЛЕНИЕ МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИЙ

В ВИДЕ СПИСКОВ

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

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

режима было "известно" алгебраическому режиму. Аналогичный

подход

имеется в

системе Турбо-Паскаль. Чтобы некоторую процедуру из одного модуля можно было

вызвать из другого модуля, она должна быть объявлена в разделе

INTERFACE

системе Reduce-З роль указанного раздела выполняет команда символьного режима

OPERATOR,

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

запятыми.

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

математическими

выражениями,'эти

аргументы транслируются в списки (раздел

10.1).

Значение вызываемой функции, полученное в виде списка, переводится обратно в

математическое выражение.

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

г-Лиспе,

которая печатает свой единственный аргумент.

1: SYMBOLIC; % переход в символьный режим

NIL

PROCEDURE AR

PRINT X; % определение процедуры

3: OPERATOR AR; % передача имени в алгебраический режим

4: ALGEBRAIC; % возвращение в алгебраический режим

AR(A+B);

% вызов функции символьного режима

% из алгебраического

(PLUS

А В) %

результат

функции

А + В % результат AR транслирован в формулу

AR(A+B*C);

% еще один пример вызова

(PLUS A (TIMES В

С))

А+В*С

Таким образом, с помощью определенной функции

можно определить, как

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

функции,

определенной

в символьном режиме.

Рассмотрим еще пример обращения к функции

AR.

AR(A/B+C)

;

(QUOTIENT (PLUS A (TIMES В

С))

В)

А + В

Оказывается, перед обращением к функции

над математическим выражением

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

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

AEVAL,

и, следовательно, аргументом функции

является значение AEVAL от исходного аргумента. Для многих задач предварительное

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

вид выражения после преобразования. Желательно получить аргумент в

первоначальном виде. Для решения данной проблемы можно переопределить функцию

AEVAL, "переключив" ее на определяемую функцию F. Так как обращение к функции

F с аргументами

Х1,Х2,ХЗ,...

транслируется в

список,

и AEVAL применяется к

значению F (AEVAL (F

Х2 ХЗ

..)),

переопределение функции AEVAL должно

иметь вид.

PROCEDURE AEVAL

F (CADR X, CADDR X, CADDDR X,

...),'

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

формул выполняет функция F.

Для определенной выше функции

переопределение функции

AEVAL

приводит к результату:

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

% функция переопределена

% преобразования AEVAL

% отсутствуют

8: SYMBOLIC;

NIL

PROCEDURE AEVAL X;

AR CADR X;

**** AEVAL is redefined.

*****

ALGEBRAIC;

10:AR(A/B+C)

;

(PLUS (QUOTIENT А В)

С)

- + С

В заключении раздела приведем несколько примеров преобразований

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

А+В+С

(PLUS

ABC)

А-В

(DIFFERENCE А В)

А-В-С

(DIFFERENCE (DIFFERENCE А В) С)

-А

(MINUS A)

А*В*С

(TIMES

ABC)

А/В

(QUOTIENT А В)

А/В/С

(QUOTIENT (QUOTIENT А В) С)

(ЕХРТ А В)

COS (A)

(COS

F(X,Y)

(F X Y)

Идентификаторы PLUS,

DIFFERENCE,

TIMES, QUOTIENT, EXPT являются

арифметическими функциями стандартного Лиспа При переводе выражения в список

сохраняются приоритеты операций, принятые в математике и программировании.

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

помощью определенной выше функции

4.8 КОНТРОЛЬНЫЕ ВОПРОСЫ

1 Каково основное назначение системы

Reduce-3?

2 Каковы особенности представления чисел в системе Reduce-3?

3 Чем скалярные переменные в системе Reduce-З отличаются от переменных

других типов?

4 Какие имена переменных зарезервированы для внутреннего использования

системой

Reduce-3"?

5. Что называется оператором в

системе

Reduce-3?

6. Каково назначение флагов в системе

Reduce-3?

7. Какие флаги системы Reduce-З вы знаете?

Какие команды системы Reduce-З предназначены для организации циклов?

9. Каково назначение команды LET?

10. Каково основное отличие синтаксиса выражений языка

г-Лисп

от

стандартного Лиспа? Приведите примеры.

11.

Какие средства отладки программ предусмотрены в системе Reduce-3?

12. Чем отличаются алгебраический и символьный режимы работы системы

Reduce-3?

4.9 УПРАЖНЕНИЯ

1 Дано некоторое математическое

выражение.

Требуется преобразовать его

в произведение, если оно представляет собой сумму.

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

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

А В С ...). Поэтому необходимо голову списка заменить на символьный атом TIMES,

обозначающий операцию умножения.

Для определения процедуры переключимся в символьный режим:

1: SYMBOLIC;

NIL

Теперь определим процедуру

PLUSTIMES:

2: PROCEDURE PLUSTIMES

IF CAR X EQ

'PLUS

THEN

'TIMES

. CDR X

ELSE X;

PLUSTIMES

Тейерь

сделаем ее доступной из алгебраического режима:

3: OPERATOR PLUSTIMES;

NIL

Осталось переключиться в алгебраический режим и протестировать нашу

процедуру: • •

ALGEBRAIC;

5: PLUSTIMES(A+B+C);

А*В*С

6: PLUSTIMES(А/В);

А/В

2 Дано некоторое математическое выражение. Требуется

определить

количество

слагаемых в этом

выражении,

если оно является суммой, иначе

считать

количество слагаемых равным нулю

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

вида (PLUS

ABC

), поэтому количество слагаемых в нем равно количеству

элементов исходного списка без 1, или количеству элементов хвоста списка Задача

решается методом хвостовой рекурсии В главной функции

KOLSUM

выполняется

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

рекурсивная функция KOLELEM для вычисления количества элементов хвоста списка

Рекурсивная функция KOLELEM вычисляет количество элементов произвольного

списка (глава 2)

SYMBOLIC;

NIL

PROCEDURE KOLSUM X;

IF CAR X EQ

'PLUS

THEN KOLELEM CDR X

ELSE 0;

KOLSUM

PROCEDURE KOLELEM X;

IF NULL X THEN 0

ELSE

1+KOLELEM

CDR X;

KOLELEM

OPERATOR KOLSUM; % только имя

главной

функции

NIL % передается в алгебраический режим

ALGEBRAIC;

6: KOLSUM(A+B+C*D);

KOLSUM(A*B*C);

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

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

числами и расположены в произвольном

порядке.

Пример такого выражения:

+Х

+Х*+Х

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

определяет его степень, то есть максимальную степень переменной

основания.

Рассматриваемые в задаче математические выражения представляются в виде

следующих списков (PLUS (EXPT Z

Kl)

(EXPT Z

K2)

(EXPT

KN)),

причем Z

является основанием полиномов, a

Kl,

- числовыми показателями

стеаени,

требуется найти максимальное значение среди этих чисел Решим задачу

методом

накапливающихся параметров с использованием хвостовой рекурсии

Главная функция

STEPEN

просто вызывает функцию MAXSTEP с хвостом от

исходного списка, поскольку от головы (PLUS) нужно избавиться, и значением

накапливающего параметра равным нулю В функции MAXSTEP накапливающий

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

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

MAXSTEP список X опустеет, параметр К будет равен степени полинома Для

извлечения очередного KI из списка

((ЕХРТ

Z KI) ) необходим последовательный

вызов функций

(CAR(CDR(CDR(CAR

X)))),

или в сокращенном варианте -

CADDAR

SYMBOLIC;

NIL

PROCEDURE STEPEN X;

MAXSTEPtCDR

X,0);

STEPEN

3: PROCEDURE

MAXSTEP(X,K);

IF NULL X THEN К

ELSE IF CADDAR X > К

THEN

MAXSTEP(CDR

X,CADDAR

ELSE

MAXSTEP(CDR

X,K);

MAXSTEP

4: OPERATOR STEPEN;

NIL

ALGEBRAIC;

STEPEN(Z

2+Z

5+Z

3);

Заметим, что в решении задач 1-3 не было переопределения функции

UEVAL,

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

выражения функцией

AEVAL

определенные выше функции перестанут

работать'

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

формулы

вида

SIN(X)/COS(X)

заменяет

их на

TG(X).

качестве

может

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

любом уровне вложенности. Например:

(SIN(2*Z)/COS(2*Z))*3+A*(SIN(4)/COS(4))

(TG(2*Z))*3

+A*(TG(4)).

Данную задачу можно решить командой внешнего языка

FOR ALL X LET

SIN(X)/COS(X)=TG(X)

(раздел 4 4)

Мы рассмотрим ее определение на

г-Лиспе

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

уровнях, очевидно, что подходящим методом решения является общая рекурсия Как

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

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