Различная интерпретация списков

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

ЛАБОРАТОРНАЯ РАБОТА №1

 

1. Сколько элементов самого верхнего уровня в следующих списках:

а) ((1 2 3))

b) ((a b) c (d (e)))

c) (a ((())) nil nil)

d) ((((a (b (c d) e) f) g) h ((i (j) k) l) m) n)

 

 

2. Замените в следующих списках все пустые списки на символ пустого списка NIL:

a) (()) = (NIL)

b) (() (())) = (NIL (NIL))

c) ((() (() (())) ())) = ((NIL (NIL (NIL)) NIL))

 

 

3. Чем отличаются:

a) атомы и символы?

b) переменные и символы?

c) выражения и списки?

 

4. Как можно записать в виде списков выражения логики высказываний, образованные при помощи логических операций НЕ, ИЛИ, И, => и <=>.

 

 

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

 

 

ПОНЯТИЕ ФУНКЦИИ

Функция – отображение между множествами

Тип аргументов и функций

Определение и вызов функции

Единообразная префиксная нотация

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

Диалог с интерпретатором Лиспа

Иерархия вызовов

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

 

 

Функция – отображение между множествами

Функцией в математике называется отображение (mapping), которое однозначно отображает одни значения на другие. Например, запись

 

y = f(x)

ставит в соответствие каждому элементу х из множества определения (domain) единственный элемент y из множества значений (range, codomain) функции f. Это соответствие также можно записать в следующем виде:

 

f(x) → y

Будем говорить, что функция f от аргумента х имеет значение y=f(x) (value, image).

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

 

abs(-3) → 3; абсолютная величина числа

+(2, 3) → 5; сумма

union((a, b), (c, b)) → (a, b, c); объединение множеств

финский(John) → ложь; определение языка

дети(адам, ева) → (каин, авель); множество детей

 

Тип аргументов и функций

В общем случае функция может задавать отображение из нескольких множеств в множество значений. Для изображения типов (type) значений функции и ее аргументов позаимствуем еще одно принятое в математике обозначение. Пусть f – функция от двух аргументов:

 

f(x,y) → z; отображение пар элементов x, y в множество z

 

Типы аргументов х и y, а также тип значения z можно обозначить следующим образом:

 

f: A×B → C

Здесь знак «×» между А и В обозначает прямое произведение множеств. Приведенная запись означает, что тип первого аргумента функции f есть А (т.е. он принадлежит множеству А), тип второго аргумента – В и тип значения функции – С. Функция f ставит в соответствие упорядоченным парам, образованным из элементов множеств А и В, элемент из множества С. Приведем типы значений и аргументов функций из предыдущего примера:

 

ФУНКЦИЯ АРГУМЕНТЫ ЗНАЧЕНИЯ

abs: число → число

+: число×число → число

union: множ-во×множ-во → множество

финский: слово → логическое значение

дети: человек×человек → множество людей

 

Определение и вызов функции

Определение (definition) функции в языке Лисп позволяет задать произвольное вычислимое отображение. Например, функцию, вычисляющую сумму квадратов, можно определить с помощью сложения и умножения:

 

суммаквадратов:

Аргументы: x, y

значение: x*x+y*y

Здесь х и y переменные, представляющие произвольные числа.

Вызов (call) функции означает запуск, или применение (apply) определения функции к конкретным значениям аргументов. Например, применим функцию суммаквадратов к аргументам х =2 и y =3:

 

Суммаквадратов(2, 3) → 13

 

 

Единообразная префиксная нотация

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

 

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

 

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

 

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

 

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

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

 

Таким же образом записываются арифметические действия. Приведенные выше арифметические выражения в лисповской префиксной записи выглядели бы так:

 

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

 

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

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

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

 

 

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

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

 

(переведи английский (Знаю английский))

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

 

Диалог с интерпретатором Лиспа

Лисп напоминает естественный язык и тем, что он обычно используется в диалоге (интерактивно) и в режиме интерпретации (interpretation). Интерпретатор Лиспа функционирует следующим образом. Когда пользователь заканчивает ввод какого-либо вызова функции или другого выражения, то интерпретатор вычисляет (evaluate) и выдает значение этого выражения. Если мы хотим, например, вычислить выражение (+ 2 3), то введем его в машину и сразу получим результат:

 

_ (+ 2 3); пользователь вводит s-выражение

Интерпретатор вычисляет и выдает результат

Символ подчеркивания «_», показанный перед вводимым выражением, - это так называемое приглашение (prompt), при помощи которого интерпретатор дает знать, что он выполнил вычисление предыдущего выражения и ждет новое выражение:

 

_(- 3 2); вычитание

Результат

_; интерпретатор выдает на экран приглашение

; и ждет ввода очередного выражения

 

Иерархия вызовов

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

 

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

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

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

 

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

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

_(* (+ 1 2) (* 1 (+ 2 3)))

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