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

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

с)

(DEFUN

MF2 (N)

(PROG (А В С X)

(SETQ A 1)

(SETQ В 0)

(SETQ С 1)

LAB

( (>= С N) (RETURN A) )

(SETQ X A)

(SETQ A (+ A

)

(SETQ В X)

(SETQ С (+ С

)

(GO

LAB)

))

(DEFUN MF2 (N)

(PROG (А В С X)

(SETQ A 1)

(SETQ В 1)

(SETQ С 2)

LAB

(IF(>=

С N) (RETURN A) NIL)

(SETQ X A)

(SETQ A (+ A

)

(SETQ В X)

(SETQ С (+ С

)

(GO

LAB)

(DEFUN MF2 (N)

(SETQ A 1)

(SETQ В 0)

(LOOP

(

(>=

1 N) (RETURN

(SETQ X A)

(SETQ A (+ A

)

(SETQ В X)

(SETQ N (- N

)

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

эквивалент?

(COND

(DEFUN

FUN1

(X Y)

((=

X 1) Y)

((=

Y 1) X)

(Т (+

(FUN1

(- X 1) Y)

(DEFUN

FUN2

(X Y) (COND

((=

X 1) Y)

(Т (+ Y (FUN2 (- X 1)

(DEFUN

FUN3

(X Y) (COND

(

(AND

XI)

(= Y 1)

((=

X 1)

(+1

(FUNS

((=

Y 1) (FUN3 Y

X))

(T (+ 1

(FUNS

(- X 1)

Y)))))

FUN1

X (- Y

Y)))))

(+ X Y)

(-Y1))

ни для какой

для всех

только для fonl

d) только для fonl и fim2

только для fon2 и

fun3

3. Что делает приведенная ниже функция?

(DEFUN

MYFUN(X)

(PROG

I A)

(SETQ

Y NIL) (SETQ I 0)

(SETQ

A NIL)

LABEL

(IF (NULL X) Y NIL)

(IF (NULL X) I 0)

(IF (NULL X) A NIL)

ISETQ A

(CAR

x)]

(SETQ I

(+11))

(SETQ X (CDR

X))

(GO LABEL)

(SETQ Y (APPEND Y (LIST

A)))

))

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

b) переворачивает список произвольной структуры

возвращает последний элемент списка

d) считает количество элементов в списке

возвращает NIL для любого списка X

4. Что выведет система

muLisp,

если в ответ на приглашение ввести следующее

выражение. (PRINT

(EVAL

'(CAR

(LIST (* 8 5)

(EVAL

(+ 3 (PRINT

2)))))))?

a) 2

b) 2

(+ 3 2)

• 45

c) 2

d) (CAR (LIST

e) 2

(CAR (LIST

8 5) (EVAL (+ 3 (PRINT

2))))

8 5) (EVAL (+ 3 (PRINT 2]

Каков будет результат оценки s-выражения (EVAL

'(LIST

(CONS A (EVAL

'(LIST

С)))

(CDR

'(EVAL

(LIST А

В)))))?

система выдаст сообщение об ошибке

b) (LIST (CONS A (EVAL

'(LIST

С)))

(CDR

'(EVAL

(LIST A B))))

((А

С)

((LIST

В)))

((А

С)

(В))

(А

В)

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

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

заданной свойством FUN, если такое свойство определено, и присвоить

полученное значение свойству

VAL

того же атома С помощью какой из

приведенных функций можно выполнить требуемые

действия?

(DEFUN

(X) (COND

((NULL

X) NIL)

((ATOM

(CAR

X})

(IF

(GET (CAR

'FUN)

(PUT (CAR X)

'VAL

(EVAL (GET

(CARX)

'FUN)))

(CONS (CAR X) (Fl (CDR

X)))))

(T (CONS (CAR X) (Fl (CDR X) ) ) ) ) )

b) (DEFUN Fl (X) (COND

((NULL

X) NIL)

((AND

(ATOM (CAR

X))

(GET (CAR X)

'FUN))

(PUT (CAR X)

'VAL

(EVAL (GET (CAR X)

'FUN))))

(T (CONS (CAR X) (Fl (CDR

X))))))

c) (DEFUN Fl (X) (COND

( (NULL X) NIL)

( (ATOM (CAR X)

(IF

(GET (CAR

'FUN)

(PUT (CAR X)

'VAL

(GET (CAR X) 'FUN))

(CONS (CAR X) (Fl (CDR

X)))))

(T (CONS (CAR X) (Fl (CDR X) ) ) ) ) )

d) (DEFUN Fl (X) (COND

((NULL

X) NIL)

( (ATOM (CAR X) )

(PUT (CAR X)

'VAL

(GET (CAR X)

'FUN)))

(T (CONS (CAR X) (Fl (CDR X) ) ) ) ) )

e) (DEFUN Fl (X) (COND

((NULL

X) NIL)

((AND

(ATOM (CAR

X))

(GET (CAR X)

'FUN))

(SETQ (GET (CAR X)

'VAL)

(GET (CAR X)

'FUN)))

(T (CONS (CAR X) (Fl (CDR X) ) ) ) ) )

Ответы:

l.b,d;

2-е;

3.e; 4.a;

S.c;

6.a,b.

4 ОБРАБОТКА МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИИ

В СИСТЕМЕ REDUCE-3

4.1 ВВЕДЕНИЕ

Система Reduce создана в 1969 году профессором Херном

(Неагп)

и является

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

компьютерной

алгебры - науки, изучающей алгоритмические методы решения

математических задач.

Reduce-З

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

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

операций,

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

упрощение алгебраических выражений (приведение подобных, раскрытие

скобок)*

решение уравнений (алгебраических, трансцендентных, дифференциальных), а также

производить многие другие математические действия. Кроме этого, Reduce-3

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

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

системы, предназначенные для математиков-профессионалов, такие как Mathcad и

Mathematica,

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

Особенностью системы Reduce-З является внутреннее представление

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

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

языком Reduce-З для обработки списков является диалект Лиспа - rLisp, или

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

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

В данной главе рассмотрены принципы работы системы Reduce-З,

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

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

4.2 ВНЕШНИЙ ЯЗЫК СИСТЕМЫ REDUCE-3

4.2.1 Числа

Целые числа в Reduce-З могут быть произвольной длины, и при выполнении

арифметических

действий над ними не происходит переполнения. Длина чисел

ограничена лишь оперативной памятью компьютера. Такое представление чисел

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

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

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

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

или отношения двух целых чисел. Можно также использовать числа с плавающей

точкой.

Пример:

1: 123456789*987654321; -,

121932631112635269

Из примера видно, что система Reduce-З является диалоговой, и приглашением к

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

завершается

символом";"

(точка с запятой).

4.2.2 Переменные

Кроме стандартных типов данных (integer, real и string) в системе Reduce-3

имеются специальные величины, называемые скалярными (scalar). Скалярный тип

данных является основным, он

назначается

переменной

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

явного ее описания. Назначение переменной

типа

по умолчанию допускалось в

некоторых ранних языках программирования (Фортран,

ПЛ-1),

современные же языки

программирования (Паскаль, C++) требуют явного задания типа каждой переменной

(например, real, integer в

Паскале).

Значением скалярной переменной является математическое выражение в

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

встроенной функции

AEVAL,

выполняющей упрощение выражения. При

инициализации переменной ее значение равно самой переменной, как и в

rnuLisp.

Пример диалога:

1:х:=а+Ь;

X := А

В -

2:у:=а-Ь;

Y := А - В

3:z:=x*y*a;

Z := ,А*

(А

)

В данном

примере,в

третьей команде происходит замена переменной х на ее

значение а+b, переменной у на

а-b,

переменная а при этом

равна

самой себе, так как ей

не было ранее присвоено значений. После обращения к функции

AEVAL

происходит

упрощение выражения (a+b)*(a-b)*a, что и приводит к выводимому результату.

Заглавные и малые буквы в

Reduce-З

неразличимы. Нельзя использовать

следующие зарезервированные переменные: Е - основание натуральных логарифмов;

I - квадратный корень из

-1,

NIL - синоним

нуля:;

PI - константа

п;

Т - "истина".

Особенностью скалярных переменных является то, что их нельзя "очистить"

присваиванием. Так выражение

"Х.=Х;

заменит в правой части переменную X на ее

значение и присвоит X то же самое значение. Такое присваивание все же иногда

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

функции

AEVAL.

Для очистки переменных используется оператор CLEAR.

Пример:

1:х:=а

X :=

2:х:=х;

X :=

3:Clear

х;

4:х:=х;

X := X

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

в виде списков Список во внешнем языке Reduce-З представляет собой

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

скобки Список может иметь произвольную вложенность.

1:х:={1,{2,3},4);

X := {1,{2,3},4}

4.2.3 Встроенные функции в Reduce-З

Для обычных математических функций, таких как sin, cos, arctg и др., система

Reduce-З не производит числовых

вычислений,

даже если их аргументом является

число

Например

1:а:=1;

А := 1

2:sin(а);

SIN(l)

Тем не менее, многие свойства элементарных функций встроены в систему.

Например, всегда выполняется замена

sin(0)=0,

и если в приведенном диалоге

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

Математические функции в Reduce-З называются операторами, и можно ввести

новые функции командой operator. Например, строка в диалоге "operator

cosec;"

позволяет в дальнейшем использовать в формулах выражения вида cosec(a),

cosec(a,l)

т д , без ограничений на тип и количество

аргументов.

Встроенные функции DF и

INT

позволяют выполнять соответственно символьное

дифференцирование и интегрирование Например, для вычисления выражения

- можно использовать команду

DF(sin(x*y

2),x,2,y,l),

а для вычисления

со.

иу

неопределенного интеграла

|х

- команду

1МТ(х

3,х).

Система

Reduce-З

вычислит

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

итоговом выражении останется оператор

INT

с "упрощенным" аргументом.

Функция SUB позволяет выполнять замену переменных в выражении

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

Примеры:

1:sub(а=1,х=2,а+x+b);

В +3

2:sub(x=x+l,x+l);

Х+2

Последним аргументом функции SUB должно быть выражение, и подстановка

выполняется один раз. Так, в приведенном выше примере в результат Х+2 снова можно

вместо X подставить

Х+1,

чего не происходит.

4.3 СИСТЕМА ФЛАГОВ В

REDUCE-3

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

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

выражения

А(В+С)

и АВ+АС или

sin(2x)

2sin(x)cos(x)

математически полностью

эквивалентны, хотя внешне различны. При проверке скалярных величин Reduce-3

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

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

двух эквивалентных выражений будет

'истина',

а двух других

'ложь'

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

выражений невозможно однозначно выбрать "наилучшее". Для решения одних задач

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

лучше вынести общий множитель за скобку

Для управления представлениями значений скалярных величин в Reduce-3

имеется набор флагов. Для включения любого флага следует набрать команду ON <имя

флага>, а для выключения - OFF <имя флага>.

а) Флаг ЕХР обеспечивает раскрытие скобок в произведениях и в степенях и по

умолчанию включен.

Пример:

1:on

exp;

2: (а+Ь)

+ 2*А*В +

(а+b)*(а-Ь);

4:off exp;

5: (а+Ь)

(А +

В)

б:

(а+Ь)*(а-Ь);

(А + В) * (А - В)

б) Флаг GCD вынуждает систему сокращать рациональные выражения на их

наибольший общий делитель. Этот флаг по умолчанию выключен, так как данная

операция требует продолжительного времени.

Пример:

1:on

gcd;

(а

2-Ь

2)/

(а+Ь)

(А - В )/ (А + В)

в) Флаг MCD, включенный по умолчанию, приводит суммы рациональных

выражений к общему знаменателю

Пример'

1:on

mcd;

2: a/b+c/d;

A*D + B*C

B*D

3:off

mcd;

4:a/b+c/d;

A*B~

г) Флаг

ALLFAC,

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

общего множителя произвольной суммы.

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

4.4 КОМАНДЫ ВНЕШНЕГО ЯЗЫКА

REDUCE-3

Команды ветвления (IF) и цикла (WHILE, REPEAT) системы

Reduce-З

полностью

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

имеют числовые значения, для них имеют смысл операции сравнения - ,

">=",

"=",

"о". Символьные значения можно сравнивать лишь на равенство и

неравенство

Команда FOR имеет несколько отличный от Паскаля синтаксис и аналогична

соответствующей команде популярного в 70-х годах языка АЛГОЛ.

FOR

<переменная>

.= <нач значение> STEP

<шаг>

UNTIL <кон.

значение>

<выражение>

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

BEGIN,END,

как и в

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

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

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

вычисляющую n первых членов ряда Тейлора для произвольной гладкой функции в

окрестности нуля

«t

Procedure

Tailor(f,x,n);

% процентом обозначается комментарий до конца

% строки, аналогично символам

"//"в

C++

% f - разлагаемая в ряд функция

% х - аргумент функции

% n - число слагаемых в

отрезке

ряда

begin

scalar

fi,xi,s;

% fi - i-я производная исходной функции f

- величина равна значению

x^i/i!

на

л-м

шаге

% s - итоговая сумма - отрезок степенного ряда

integer

off

mcd;

off allfac;

:=sub

(x=0,

)

:=1;

fi:=f;

for

i:=l

step 1 until n do

begin

xi:=xi*x/i;

:=DF

s:=s+sub

(x=

end;

return s;

end;

% счетчик цикла

% вид итогового выражения нагляднее без

% суммирования дробей

аналогично,

общий множитель лучше

% не выносить за скобки

s:=f(0)

% fi - i-я производная от f по х

fi)

*xi;

% к s добавляется

fi(0)*x"i/i!

% возвращаемое значение

% завершение процедуры

Рассмотрим применение процедуры Tailor.

Известна следующая формула для

sin(x)'

--..

Обратившись к процедуре Tailor, получим такой же результат:

Tai

lor

(sin

(х)

х,

;

1/120*Х

1/6*Х

+ X

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

полиномиальные уравнения или системы линейных уравнений,

например:

solve

(

{х-3*у=2,х-у=1},

{х,у})

;

{{

X=l/2,

Y=-l/2

}}

и команду

РАСТОККЕ(<выражение>),

разлагающую полиномы на простые

множители.

' Кроме этого, имеется команда LET, выполняющая глобальные подстановки. Ее

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

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

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

х=х+1",

поскольку после первой замены х на

х+1

в заменяемом выражении снова

останется

х,

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

Пример:

1: let

sin(x)

2+соз

(х)

2=1;

a*sin(x)

2+а*соз

(х)

sin(x)

3+cos(x)

2*sin(x)

;

SIN(X)

4: cos (z)

зш(г)

COS(Z)

SIN(Z)

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

действует

лишь на аргумент X,

кроме

того,

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

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

команду. FOR ALL X LET

SIN(X)

2+COS(X)

2=1.

4.5 ЗАГРУЗКА ВНЕШНИХ МОДУЛЕЙ

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

"<имя_файла

расширение>".

Расширение обязательно, потому что в

Reduce-З

нет

общепринятого расширения для программ, как, например, pas для программ на Паскале

или

Isp

для muLisp Обычно для программ в Reduce-З используется расширение red