Лекции в ворде, страница 2

33

Атомы представляются символьными и числовыми объектами. Простейшая форма S-выражения – это атом. Более сложное выражение – это список атомов. В приведенных выражениях (а)-(в) соответственно: 1 атом, 5 автомов, 4 атома; более сложная структура (г) представляет список списков, (д) – список списков и простые атомы. Итак,.

• атом – S-выражение;

• последовательность разделенных пробелом S-выражений, заключенная в скобки– S-выражение (список).

В соответствии с последним определением выражение (а) - список из одного элемента; (б) – список из 5-и элементов; (г) – список из 3-х подсписков, каждый из которых состоит из 2-х элементов; (д) – из двух подсписков и одного простого элемента (атома), причем первый подсписок состоит из двух элементов, второй – из одного простого элемента и подсписка.

2.2. Элементарные селекторы и конструкторы.

Пусть некоторый объект х – список. Введем следующие определения функций (селекторов):

car(х) – первый элемент списка

cdr(х) – список, полученный отбрасыванием первого элемента списка.

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

третий(х)car(cdr(cdr(х))); при. х=(a b c d) третий(х)=С

Примеры выполнения селекторов car и cdr приведены в следующей таблице:

х	car(x)	cdr(x)
(A B C)	A	(B C)
((A B) (C D))	(A B)	(C D)
(A)	A	NIL

Атом NIL, или nil, обозначает пустой список.

Введем определение примитивного конструктора cons(х,у). Эта функция соединяет два исходных S-выражения таким образом, чтобы исходные компоненты получались применением к результату функций car и cdr.

х	у	cons(x,y)
A	(B C)	(A B C)
(A B)	((C D))	((A B) (C D))
A	NIL	(A)

На основе cons можно сконструировать функцию

двучлен(х,у)(cons(x,cons(y,NIL))

2.3. Элементарные предикаты и арифметические функции

Предикат – логическая функция, принимающая значение И (истина) или Л (ложь) в зависимости от значение аргумента. Приведем несколько примеров предикатов.

Пример выполнения предиката атом(х):

х	атом(х)
А	И
(А)	Л
(А В С)	Л
словарь	И
127	И
(127)	Л

Если оба значения аргументов – списки, то результат не определен. Обычный способ использования этого предиката иллюстрирует следующее определение:

размер 0, если равно(х,nil), иначе

1, равно(cdr(x), nil), иначе

2.

Эта функция выдает 0, 1 или 2 соответственно тому, что ее аргумент является списком из 0, 1 или более атомов.

Арифметические функции могут быть определены аналогичным образом. Эти функции могут включать различные элементарные арифметические операции: +, -, *,  и ост. Операция ост определяется соотношением

х ост у=х–(ху)*у,

т.е. она дает остаток при делении нацело двух целых чисел. Функция же, возвращающая в качестве результат список из двух атомв – частного и остатока, определяется так:

частот(х,у)cons(xy, x ост у)

х	у	частост(х,у)
17	3	(5 2)
17	-3	(-5 -2)

Арифметические выражения, определяющие тело арифметической функции, должны иметь префиксную форму, при этом роль скобок очень велика: от их расстановки зависит результат.

расстояние(х,у)у–х, если ху, иначе

х–у.

Представим предикаты, определяющие отношение между числовыми объектами: <, >, =, , . Эти предикаты могут быть использованы в определении различных арифметических функций. Например,

2.4. Рекурсивные функции.

Функция называется рекурсивной, если в определяющем его выражении содержится хотя бы одно обращение к ней самой. Для определения рекурсивной функции необходимо сформулировать условие выхода из рекурсивного цикла. Пусть таким условием будет х=NIL. Следовательно, при хNIL рекурсия будет продолжаться. Определим рекурсивную функцию длина(x).

случай 1: если х=NIL, то длина=0

случай 2: если хNIL, пусть длина(cdr(x))=n, тогда

длина(x)=n+1.

Проследим трассу рекурсивной функции обратить(x), определенной так:

случай 1: если х=NIL, то обратить= NIL;

случай 2: если хNIL, пусть z=обратить(cdr(x)), тогда

обратить(х)=добавить(z,car(x)).

Функция добавить(x,y) помещает car(x) в конец обратить(cdr(х)), получает список х и элемент y и делает y новым последним членом списка х. Дадим определение функции добавить(х,у):

случай 1: если х=NIL, то добавить(х,у)=cons(y,NIL);

случай 2: если хNIL, пусть добавить(cdr(x),y)=z, тогда

добавить(х,у)=cons(car(x),z).

2.5. Функции высших порядков

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

Введем обозначение, которое в дальнейшем будет более формализовано:

lambda x (x+1).

Это выражение читается так: "lambda – функция от х, которая выдает ("") результат х+1 (т.е. функцию)". Определим некоторую функцию f(x): f(x)=E, где f не входит в Е, тогда lambda xE.

Рассмотрим примеры определения функций:

Пример 1.

увелич(х) NIL, если равно(х,NIL), иначе

cons(car(x)+1, увелич(cdr(x)))

Если х – список (1 2 3), то результат список (2 3 4).

Пример 2.

остаток(х) NIL, если равно(х,NIL), иначе

cons((car(x) ост а), остаток(cdr(x)))

Напомним, что х ост у=х-(х(у)у и деление – целочисленное. Пусть а=2, тогда для х=(1 2 3) имеем остаток=(1 0 1). Приведенные две функции могут быть описаны одной:

отобразить(х,f) NIL, если равно(х,NIL), иначе

cons(f(car(x)),отобразить(cdr(x),f)).

Введем обозначения ув1 z+1 и ост1z ост 2. Тогда

увелич(х)(отобразить(х,ув1),

остаток(х)(отобразить(х,ост1).

Заметим, что в приведенном определении lambda-функции отсутствует рекурсия. Мы же определили все функции в функциональном программировании как рекурсивные. Этого неудобства можно избежать, если ввести два определения let (пусть) и where (где).

let f==lambdaA...f...

(функция f используется в некотором выражении Е_f ) Это определение может быть переписано другим, эквивалентным образом Еf, где

f==lambdaA...f...

Пример.

Let f==lambdaxif x=0 then 0 else x+f(x-1) для f(х). Последнее уточнение ("для") записывают в таком виде: in f(3). Тогда в соответствии с этим определением для х=3 вычисляется сумма 3+2+1+0=6.

В качестве другого примера функции высшего порядка рассмотрим функцию редукция(x,f,a), где х – список c элементами x1,x2,...xn, f – бинарная функция, а – константа. Для того, чтобы увидеть, как "работает" эта функция, заметим, что выражение редукция(х,f,а) эквивалентно выражению

f(x1,f(x2,...f(xn,a)...)).

Положим, что f –префиксная функция +, а=0 и x=(1,3,5), тогда имеем

случай 1: x=NIL, редукция(х,+,0)=0;

случай 2: xNIL, редукция(х,+,0)=+(car(x),редукция(cdr(x))).

В соответствии с этими определениями имеем

редукция((1,3,5),+,0)+(1,редукция((3,5),+,0)

+(1,+(3, редукция(5),+,0) +(1+(3,+(5,0))9.

Связывание. Важно помнить, что значение переменных в lambda-выражении устанавливается тогда, когда выражение определяется, а не тогда, когда оно используется:

let x== in (let f==lambda y x+y in (let x==2 in f(x))),

в записи x+y переменная х имеет значение 1, т.е. значение х в точке определения функции f(x). Такое назначение переменным значений называется статическим связыванием. Динамическое связывание (определение переменных происходит в момент использования функции) в общем случае в функциональном программировании не используется.

Упражнения

1. Опишите рекурсивную функцию произв(х), которая вычисляет произведение списка целых чисел.

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

х=nil, уменьш(х)=nil

х=(1,2), уменьш(х)=(0,1)

3. Опишите функцию позиция(х,у), аргументами которой являются атом х и список атомов у. Ее результатом будет положение атома х в списке у, считая с первого по порядку элемента. Предполагается, что атом х встречается в списке у. Например, х=С, у=(В,А,С), позиция(х,у)=3.

4. Видоизмените описанную функцию так, чтобы она выдавала значение 0, если х не встречается в списке у.

5. Опишите функцию индекс(i,y), которая использует в качестве аргументов число i и список у и выдает элемент списка, имеющий номер i. Предполагается, что у имеет длину меньше i.

Тема 3. Математические основы -исчисления

Определения

-исчисление – это исчисление анонимных функций. Оно определяет:

• метод представления функций;

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

Пусть дано определение функции duble(x)=2*x; в -исчислении ее можно представить в следующем виде х.*2х

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

lambda x2*x.

Следовательно, lambda заменяется на , а  на ".". -выражение читается: "функция от..., которая (.) возвращает ...". Символ х – связанная переменная абстракции и соответствует формальному параметру, а выражение справа – тело функции (абстракции). Тело абстракции может быть любым допустимым -выражением, в том числе и содержать другую абстракцию:

x. y.*(+x y)2.

Это выражение читается так: "функция от х, которая возвращает функцию от y, которая возвращает (х+y)*2".

Существует соглашение, по которому функция применяется всегда к самому левому аргументу: (x1. x2... xn.E)x1x2...xn.

Более формально синтаксические правила можно записать в виде БНФ:

<выр>::=(<ид>.<выр>|<ид>|<выр><выр>|(<выр>)|<const>

<ид>::=любой идентификатор

<const>::=константа.

В дальнейшем будем использовать следующие предопределенные константы:

Константы	Значение
0,1,-1,2,-2.	Множество целых чисел
TRUE, FALSE	Булевы константы
+, -, *, ...	Арифметические операции
=, ,+, >, <,...	Булевы функции на множестве целых чисел
SUCC, PRED	Функции "следующий за" и "предшеству­ющий" на множестве целых чисел
EQ0	Функция, возвращает true, если заданное целое равно 0
COND	Условная функция
CONS	Конструктор списков
NIL (nil)	Пустой список
CAR	Функция, выдающая голову списка
CDR	Функция, выдающая хвост списка
NULL	Функция возвращающая true, если заданный список пуст
TUPLE-n	Функция, строящая n-кортеж выражений
INDEX	Функция индексирования кортежа

Реализации функциональных языков не различают написание имен прописными или строчными буквами, поэтому в предыдущей таблице, например, константы COND(cond, NULL(null, NIL(nill и т.д. Это замечание относится и к последующему тексту.