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

Примеры -выражений

42

y.*2y

(f.a.b. f ab)(x.(y.x))

f.x.cond(=x1)x(*x(f(-x1)))

3.2. Вычисление -выражений

Простейший тип -выражения – это константа. Константы являются самоопределенными. Применение константных выражений при необходимом количестве аргументов определяется с помощью встроенных так называемых -правил. Например, выражение

+1 3

означает применение константы (встроенной арифметической функции +) к двум числам 1 и 3. Это выражение может быть преобразовано ы число 4 с помощью соответствующего -правила для функии +, которое записываем таким образом:

+ 1 3_ 4.

Такой процесс упрощения выражений называется редукцией. Приведенное выражение читается: " +1 3 а превращается в 4", а _ означает, что применено встроенное -правило.

В следующем примере -правило сразу применить невозможно, поэтому последовательное применение -правил дает:

*(+1 2)(-4 1) _ *(+1 2)3 _ *3 3 _ 9.

Наиболее интересное правило редукции описывает, как применять -абстракции. Рассмотрим следуюшее применение:

фактический параметр замещает все вхождения переменной. Например,

(х.*х х)2.

Здесь ситуация аналогична вызову процедуры или функции языка высокого уровня с фактическим параметром, замещающим ее формальный параметр. В -исчислении такая замена является чисто текстовой, и все вхождения связанной переменной х заменяются на выражение аргумента, 2, получая измененную форму тела абстракции. Поэтому

(х.*х х)2_*2 2 _ 4.

Ћ! Процесс копирования тела абстракции с заменой всех вхождений связанной переменной на выражение аргумента называется -редукцией.

Редуцируемое выражение называется редексом. Последовательное применение редукций к редексам до тех пор, пока выражение включает хотя бы один редекс называется редукцией -выражения.

Редукция понимается в том смысле, что упрощается -выражение устранением из него символа , связанной переменной и аргумента и получением измененной формы тела абстракции. Редукция абстракции, примененной к некоторому аргументу, может привести к новой абстракции:

((x..y. + x y)7)8)

Делается подстановка 7 в тело самой внешней абстракции:

(y. + 7 y)8_+ 7 8_ 15.

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

Пример 1.

х.(( у. х.+х у)х).

Во внутреннем -выражении аргумент х имеет одинаковое имя ссо связанной переменной в теле абстракции.

Чтобы обезопасить -редукцию, необходимо сначала модифицировать тело абстракции так, чтобы все имена связанных переменных были уникальными, т. е. Нужно переименовать связанную переменную (у.х'.+ х' у). Тогда х.((у.(х'.+х' у)х)х.(х'.+х' х).

Пример 2.

х.((х.х)(+1 х))1.

Внутренняя абстракция (х'.х')(+1 х)=+(1 х) и (х.(+1 х))1=2.

Последовательное преобразование -выражения использует очевидные -и -преобразования. Поэтому в дальнейшем будем опускать в цепочке преобразований индексы -и . Если в сложных -выражениях связанная переменная имеет такое же имя, как и заменяемая переменная, нужно такую внутреннюю абстракцию оставить без изменения. Переименование переменных называется -преобразованием, а преобразованные выражения алфавитно-эквивалентными.

Пример 3. (f.(x. f 4 x)(y.x. +x y)3.

Ш1. Единственный редекс (y.x +x y) подставляем вместо внешней абстракции f в тело абстракции (f.x. f 4 x):

(x.(y.(x +x y)4 x)3

Ш2. Подставим аргумент 3 в тело абстракции

(y.x +x y)4 x (y.x. +x y)4 3

Ш3. Преобразуем единственный редекс (y.x +x y):

( (x. +x 4) 3(

Ш4. Последнее преобразование  +3 47.

На шаге 2 мы могли бы сделать подстановку во внутренний редекс (подчеркнуто), имели бы:

(x.(y.x +x y)4 x)3x.((x. +x 4) x)3(x. +x 4)3+3 47.

Порядок редукций и нормальные формы

Мы установили, что вычисление (-выражения сводится к последовательности редукций. Однако в этом процессе важен и порядок редуцирования. В связи с этим следует дать еще одно, более строгое определение редукции:

Определение. Х сворачивается (редуцируетcя) к Y тогда и только тогда, когда Y реализует замены части X вида (х.М)N на [N|x]M. X редуцируется к Y тогда и только тогда, когда Y получается из Х с помощью конечной (возможно пустой) последовательности сворачиваний и замен связанных переменных. Всякий терм вида (х.М)N есть редекс, а терм [N|x]M – его сверткой (подстановкой).

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

(x.y.y)(( z.z z)(z.z z)). Имеем два редекса (x.y.y)((z.z z)(z.z z)) и (z.z z)(z.z z).

Выберем для редукции второй, тогда

(z.z z)(z.z z) (z.z z)(z.z z) (z.z z)(z.z z)...

Теперь выберем первый:

(x.y.y)(( z.z z)(z.z z)) y.y.

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

Самый внешний – редекс, у которого символ ( текстуально находится в (-выражении левее всех остальных редексов. (Аналогично определяется самый правый редекс).

Самый внешний – редекс, который не содержит внутри никакого редекса.

Самый внутренний – редекс, который не содержит других редексов.

В примере: самый левый из внутренних редексов является а) ((z.z z)((z.z z), самый левый из самых внешних редексов является б) (x. y.y)(( z.z z)( z.z z)).

В функциональном программировании существует два порядка редукции:

аппликативный (АПР), который предполагает преобразование сперва самых левых из самых внутренних редексов;

нормальный (НПР), который преобразует самый левый из самых внешних редексов.

Поэтому по АПР сперва преобразуется а), что приводит к зацикливанию, а по НПР – б), который за один шаг приводит к y.y.

Справедливы следующие теоремы:

Теорема Черча-Россера. Если выражение. Е может быть приведено двумя различными способами к двум нормальным формам, то эти нормальные формы являются алфавитно-эквивалентными.

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

Упражнения к теме 3

1. Укажите связанные и свободные переменные в каждом из следующих -выражений:

а) (х.х у)( у. у)

б) x. y.z(z.z(x.y))

в) x. x y(z. y.y)

2. Сколько вхождений у имеется в терме

Мх.х у(z.y. y)

3. Выполнить редукцию -выражений:

а) (х.ху)А

б) (х.у)F

в) (х.(у. у х)z)v

Тема 4. Основы языка Лисп

4.1. Символы и списки

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

Одним из основных отличий языка Лисп от традиционных языков программирования является запись в виде списков не только данных, но и функций (или программ). Например, список (+ 2 3) можно интерпретировать как список и как действие, результатом которого является число 5. Будем считать, что изучение языка мы проводим в рамка некоторой интерпретирующей Лисп-системы. Поэтому символ "$" перед вводимым выражением следует считать приглашением, с помощью которого интерпретатор дает знать, что он выполнил вычисление предыдущего s-выражения и ждет нового. Заметим, что в разных Лисп-системах символы приглашения различаются (:, >, _).

• Объекты языка

В программировании на Лиспе используются символы и построенные из них структуры. Символ – это имя, состоящее из букв , цифр и специальных знаков, и представляет какой-нибудь объект.

Наряду с символами в Лиспе используются числа, представляемых различными типами: целыми, с плавающей запятой. Числа не являются символами, так как не представляют другие лисповские объекты, кроме самих себя.

Логические значения Т и NIL обозначают логические константы, обозначающие логическую истину и ложь.

Числа и логические значения являются константами, остальные символы – переменные. С помощью директивы DEFCONSTANT символ может быть превращен в константу. При этом, определенный так символ, может обозначать только значение, которое ему предписано таким определением.

Символы и числа представляют простые объекты, поэтому их называют атомами. Из атомов образуются списки. Списки и атомы – основные типы данных Лиспа. Списки могут содержать простые атомы или подсписки. Простой список – это последовательность разделенных пробелами атомов, заключенная в скобки. Пустой список обозначается символом NIL или последовательностью скобок (). Атомы и списки называются символьными выражениями или s-выражениями.

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

(f x), (q x y), (h x (g y z)) и т.д.

Таким же образом записываются арифметические действия:

(+ х у), (- х у), (* х(+ y z)) и т.д.

Вычисляя значение выражения, интерпретатор Лиспа сначала пытается слева направо вычислить значения аргументов внешнего вызова. Если первый аргумент является константой или иным объектом, значение которого можно определить непосредственно, то вычисление аргументов вычисляемой функции можно продолжить. Если аргументом будет вложенный вызов функции или другая вычислимая форма, то перед ее вычислением определяется начение ее аргументов и т.д. Как и в математике, в Лиспе в первую очередь вычисляются выражения в скобках:

$ (* (+ 1 2)(+3 4))

21 ; =(1+2)*(3+4)

$ (* (+1 2))

3 ; =(* 1 (+ 1 2))=(1*(1+2))=3

• Блокирование вычисления выражения - quote (QUOTE).

В некоторых случаях не надо вычислять значение выражения, а нужно само выражение. Например, нас интересует выражение (+ 2 3) как список, а не как функциональный вызов этого выражения, значение которого есть 5. Для этого перед блокируемым выражением нужно поставить апостроф '. Апостроф перед выражением – это на самом деле сокращение лисповской формы quote. Quote можно рассматривать как функцию с одним аргументом, которая ничего с эти аргументом не делает, а возвращает в качестве значения вызова сам аргумент:

$ '(+ 2 3)

(+ 2 3)

$ (quote(+ 2 3))

(+ 2 3)

$ '(a b '(c d))

(A B (QUOTE (C D)))

$ ''y

(QUOTE Y) ;все апострофы преобразуются в вызов QUOTE

$ 'quote

QUOTE

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

$ '3.14

3.14

$ (+ '2 3)

5

Вопросы для самопроверки

1. Сколько значений может иметь функция?

2. Может ли функция иметь одно и то же значение при разных аргументах?

3. Определите значения следующих выражений:

a) '(+ 2(* 3 4))

б) '(+ 2 ('* 3 4))

в) (quote 2)

г) '(quote NIL)

4. Напишите выражение, вычисляющее среднее арифметическое чисел 23, 5, 43, 17.

4.2. Базовые функции

• Функции обработки списков

В разделе 2.2 мы изучили возможности элементарных функций обработки списков. Здесь мы приведем несколько примеров их использования в среде интерпретатора.

$ (car '(первый второй третий)

ПЕРВЫЙ

Замечание. Вызов функции car с аргументом (первый второй третий) без апострофа был бы воспринят интерпретатором как вызов функции ПЕРВЫЙ с аргументами ВТОРОЙ и ТРЕТИЙ, и было бы сообщение об ошибке.

$ (cdr '(a (b c)))

((B C))