[
Содержание
| 1
| 2
| 3
| 4
| 5
| 5.1
| 5.2
| 5.3
| 5.4
| 5.5
| 5.6
| 5.7
| 5.8
| 5.9
| 6
| 6.1
| 6.2
| 6.3
| 6.4
| 6.5
| 7
| 7.1
| Литература
]
© 2003 И.А. Дехтяренко
5.1.Введение в Лисп.
|
Мы можем сказать, что
все языки отличаются друг от друга, но некоторые
отличаются значительно больше, чем другие.
Эдуард Сепир |
С момента создания Лиспа прошло уже чуть ли не
полвека. За это время возникло множество
диалектов языка1. Мы будем
использовать Scheme, но большая часть сказанного
верна для любого диалекта (иногда особенности
Scheme будут оговариваться явно). Поскольку нашей
целью не является изучение языка, мы кратко
рассмотрим только те свойства, которые будут нам
полезны.
Выражения и значения выражений.
- Обычно работа с интерпретатором Лиспа
происходит по следующему сценарию.
- Пользователь вводит выражение.
Интерпретатор вычисляет значение этого
выражения
и печатает результат.
Начнем с простейших примеров (курсивом
выделены ответы интерпретатора).
10
10
10.5
10.5
Числовые константы обозначают числа, которые и
являются их значениями. Разнообразие доступных
типов чисел зависит от реализации языка, но все
реализации поддерживают целые и вещественные
числа, а многие ещё и рациональные и комплексные.
Hello
Error: undefined variable
Последовательность букв, цифр и специальных
знаков (!$%&*/:=<>?^_ ~ +-.@ ), отличающаяся от
числа называется символом. Главное их назначение
- именовать объекты. Поэтому, значением символа
является объект, поименованный этим символом. Но
поскольку с именем Hello пока не связано
никакого значения, получаем сообщение об ошибке.
+
#<procedure +>
А вот с именем + связана встроенная функция,
вычисляющая сумму чисел, которая и является
значением. Однако сама функция не отображается:
внутренние представления функций не очень
читаемы.
'Hello
hello
С помощью кавычки символы можно употреблять
автонимно. Значением выражения '<символ>
является сам этот символ. Это позволяет
использовать их, например, подобно значениям
перечислимых типов в Паскале. Обратите внимание,
Лисп нечувствителен к регистру букв и значение
символа приведено к стандартному виду.
"Hello"
"Hello"
Это пример строковой константы. Они
записываются в двойных кавычках и представляют
последовательности отображаемых знаков.
#f
#f
Две логические константы #t и #f
обозначают истину и ложь.
Константы и символы носят общее имя атомы,
поскольку представляют собой простейшие
элементы языка, из которых строятся выражения.
Комбинационные формы
Для записи выражений (форм в терминологии
Лиспа) используется единая префиксная форма: имя
функции стоит перед аргументами и записывается
внутри скобок.
(+ 2 2)
4
(* 1.1 2)
2.2
(= 1 2)
#f
Подобные выражения, описывающие применение
функции к аргументам, называются комбинационными
формами или комбинациями. Значение
комбинации - результат применения функции,
указанной первым элементом списка (оператором) к
параметрам, которые являются значениями
остальных элементов (операндов). В данном случае,
операторы - встроенные функции +,*,=.
Пример более сложного выражения.
(+ (* 3 5) (- 10 5))
20
- Общее правило вычисления значения комбинации
следующее:
- 1. Вычислить значение всех подвыражений.
2. Применить функцию, которая является значением
оператора к аргументам, которые являются
значениями операндов.
Таким образом, в Лиспе используется
аппликативный порядок вычислений
В традиционной математической нотации имя
функции стоит перед аргументами, заключенными в
скобках. Кроме того, используется инфиксная
запись арифметических выражений, разнообразные
индексы и специальные знаки.
| Математическая запись |
Запись на Лиспе |
| f(x) |
(f x) |
| g(x, y) |
(g x y) |
| h(x, g(y, z )) |
(h x (g y z)) |
| sin x |
(sin x) |
| x + y |
(+ x z) |
| x + y·z |
(+ x (* y z)) |
| xy |
(expt x y) |
| |x| |
(abs x) |
| x = y |
(= x y) |
| x + y < z |
(< (+ x y) z) |
В сравнении с этим многообразием и даже с
синтаксисом большинства языков
программирования префиксная форма кажется
несколько непривычной и громоздкой. Но она
обладает, по крайней мере, одним неоспоримым
достоинством - описание синтаксиса умещается на
одной строчке:
<выражение> ::= <атом> | ( <выражение>* ).
Чтобы сделать выражения более читаемыми,
многие реализации допускают использование
квадратных скобок.
(/ [+ (* 3 5) (- 10 5)] 2)
10
Однако эта возможность не отражена в стандарте
языка.
(1 2 3)
Error: attempt to apply a non-procedure
Конечно же, 1 не является функцией.
Поэтому попытка применить её приводит к ошибке.
(+ 1 (= 1 2))
Error in +: #f is not a number.
Несмотря на то, что Лисп - бестиповый язык и
любое сочетание аргументов является
синтаксически допустимым, в процессе выполнения
для каждого значения определяется его тип и
попытка применить + к логическому значению
вызывает ошибку. Поэтому Лисп называют
динамически типизированным языком. Заметим что
правила типизации соблюдаются гораздо более
строго, чем в Си или даже в Паскале - нет никакой
возможности подсунуть функции аргумент не того
типа.
Базовые функции.
В Лиспе определён большой набор базовых
функций, но нам потребуются немногие из них. Это
во-первых арифметические операции (+,-,*,/).
Функции + и * имеют произвольное количество
аргументов. В принципе, это не очень хорошая
практика, но в данном случае она себя
оправдывает.
(+ 1 2 3 4 5)
15
(+ 1)
1
(* 1 2 3 4 5)
120
Поскольку операции вычитания и деления не
ассоциативны, попытка расширить их определение
на произвольное количество аргументов может
привести к путанице. Однако, для одного аргумента
определено, что (- a)выдаёт -a , а (/
a)- 1/a.
(- 5)
-5
(/ 10 5)
2
(/ 2 3)
2/3
Неожиданность. Ожидалось скорее 0 или 0.666667 в
зависимости от любимого языка программирования.
Но для непредубежденного человека вполне
естественно2. Впрочем, если
реализация не поддерживает рациональных чисел
(что допускается для Scheme) получим 0.666667.
Для деления с остатком предназначены
функции quotient и remainder, возвращающие
целую часть и остаток от деления.
(quotient 2 3)
0
(remainder 2 3)
2
Значение (+ [* y (quotient x y)) (remainder x
y)]) всегда равно x.
Логические функции
Функции, возвращающие логические значения,
называются предикатами. В Scheme принято названия
предикатов (кроме распространённых
арифметических операций сравнения
=,>,<,<=,>= ) завершать вопросительным
знаком, в других диалектах Лиспа - буквой
"p"(от слова predicate).
(= 1 2)
#f
(< 1 2)
#t
(odd? 2)
#f
(even? 2)
#t
Подобно + и *, операции сравнения
допускают произвольное число аргументов (но,
конечно же, не менее двух). Это сделано всё с той
же целью - уменьшить сложность выражений.
Например (< x1 x2 …xn)вернёт
#t, только если аргументы упорядочены по
возрастанию.
Для символов единственная осмысленная
операция - сравнение на идентичность.
(eq? 'a 'a)
#t
Может показаться странным использование
специального предиката, а не символа равенства.
Но мы часто подразумеваем совершенно разные
вещи, когда говорим, что два объекта равны.
Предикат = сравнивает численные значения
двух выражений, а предикат eq? проверяет,
что эти выражения именуют один и тот же объект.
Поэтому:
(= 1 1.0)
#t
(eq? 1 1.0)
#f
(eq? 1 1)
#t
Поскольку переменные Лиспа могут принимать
значение любого типа, необходимо иметь
возможность определять этот тип. Для этого
предусмотрены типовые предикаты.
(boolean? 1)
#f
(number? 1)
#t
(integer? 1)
#t
(integer? 1.1)
#f
(real? 1.1)
#t
(procedure? +)
#t
(procedure? '+)
#f
(symbol? '+)
#t
Для представления логических связок
используются функции not, or и and.
(not x)- возвращает
#t, если значение аргумента
равно #f и #f в противном случае.
(or x1 x2 … xn)- возвращает значение первого аргумента, не
равного
#f. Если же все аргументы имеют
значение #f, то оно и возвращается.
(and x1 x2 … xn)- возвращает значение
#f, если оно
встречается среди значений аргументов. В
противном случае возвращается значение
последнего аргумента.
(not #f)
#t
(not 0)
#f
Ещё одна неожиданность и довольно
обескураживающая. Дело в том, что любое значение,
отличное от #f интерпретируется как
истина. Это наследие первых версий Лиспа. Хуже
того, в большинстве диалектов Лиспа вообще
нет логических констант, а в качестве ложного
значения используется атом nil, по
совместительству обозначающий пустой список и
некоторые реализации Scheme «для совместимости»
используют два ложных значения.
(or #f #t)
#t
(and #f #t)
#f
(and 0 1 2 3)
3
(or 0 1 2 3)
0
Вычисление значений функций and и or
выполняется необычным образом. Значения
аргументов вычисляются слева направо и, как
только значение функции определено, оно
возвращается. Значения остальных аргументов не
вычисляются. Это отступление от общего правила
вычисления комбинационных форм - аргументы
вычисляются до применения функции. Такие
операторы, имеющие собственные правила
вычисления называются специальными формами.
Условные выражения
Важная разновидность специальных форм -
условные выражения. Если зависимость значений
истинности от значений других типов
выражается предикатами, а зависимость значений
истинности от других значениях истинности
логическими связками, то условные выражения -
средство для выражения зависимости значений
произвольного типа от значений истинности.
(if p et ef)- возвращает значение ef, если значение p -
#f
, и et в противном случае.
(cond (p1 e1) (p2 e2) … (pn
en))- возвращает значение
ei , для первого
i при котором значение pi отлично от #f.
Условные выражения cond вычисляются
следующим образом. Сначала вычисляется предикат
p1. Если его значение ложно, то вычисляется p2.
Этот процесс продолжается, пока не встретится pi
принимающий истинное значение. В этом случае
значением условного выражения будет значение
соответствующего этому предикату выражения ei.
Если ни один из pi не даёт истинного
значения, значение cond не определено.
Часто в качестве последнего условия пишется #t,
соответствующее ему выражение будет вычисляться
в тех случаях, когда ни одно другое условие не
выполняется. Для наглядности вместо #t
можно использовать специальный символ else.
Очевидно, что (if p a b) эквивалентно (cond
(p a) (#t b)).
(if (= 1 2) 1 0)
0
Определения.
Для определения новых объектов, применяются определяющие
формы.
(define n e)- связывает имя
n со значением выражения
e.
(define (f a1…an) e)- определяет новую функцию с именем
f.
a1…an - формальные параметры,
т.е. имена, используемые внутри тела функции для
ссылок на соответствующие параметры.e -тело функции, выражение, определяющее
её значение.
Имя и формальные параметры определяемой
функции заключены в круглые скобки, так же, как
они будут использоваться при её вызове 3.
(define x 1)
x
1
(+ x x)
2
(define x 2)
(+ x x)
4
Выглядит подобно присваиванию значения
переменным, но это не так. Связывание выполняется
только в момент, когда система анализирует ввод.
Мы можем переписать определение, используя то же
самое название, но это не присваивание в обычном
смысле, так как последовательность значений,
принимаемых переменной, связана с процессом
трансляции, а не с динамикой выполнения
программы.
(define a 'a)
a
a
(define & and)
(& (< 1 2) (< 2 3))
#t
Значение and, то есть встроенная функция
связывается с именем &, после чего & можно
использовать вместо and.
(define (sqr x) (* x x))
sqr
#<procedure>
(sqr 5)
25
Теперь с именем sqr связана вновь
определённая функция и ее можно использовать для
возведения в квадрат. Подобно встроенным
функциям, она не отображается. Дело в том, что
интерпретатор не сохраняет определения как
синтаксические деревья, а компилирует их в
байт-код.
(define (sum-of-squares x y) (+ (sqr x) (sqr y)))
(sum-of-squares 3 4)
25
После определения новой функции её можно
использовать точно так же как примитивные
функции. Действительно, глядя на определение sum-of-squares,
нельзя сказать, была ли функция sqr
встроена в интерпретатор, подобно + и *, или
определена.
Лямбда-выражения и связывающие формы.
Мы говорим что форма (define (sqr x) (* x x))
определяет функцию sqr. Но на это можно
посмотреть и с другой точки зрения: мы определяем
функцию возведения в квадрат и даем ей имя sqr.
Во многих языках эти действия неразделимы, но в
Лиспе мы способны отделить два понятия -
определение функции, и её именование.
Дать имя функции можно все той же конструкцией define
(define sqr <функция возведения в квадрат>),
а определить - с помощью специальной формы: лямбда-выражения.
(lambda (a1…an) e)- возвращает функцию, вычисляющую значение
выражения
e при подстановке фактических
параметров вместо a1…an.
Функция, определенная с помощью
лямбда-выражения, ничем не отличается от функции
созданной посредством define, за исключением
того, что она не имеет имени. Фактически, (define (f a1…an) e)
полностью эквивалентно (define f (lambda (a1…an)e)4.
Например, sqr можно было бы определить и
так
(define sqr (lambda (x) (* x x)))
Лямбда-выражение может использоваться всюду,
где используется имя функции, например как
оператор в комбинации вида.
([lambda (x) (* x x)] 2)
4
Иногда выражение содержит повторяющиеся части.
Чтобы упростить запись таких выражений этим
частям можно присвоить локальные имена с помощью
связывающий формы let.
(let ((a1 e1)(a2 e2) … (an
en)) e)- Значением этой формы будет значение выражения
e,
в котором каждое ai заменено
значением выражения ei.
Например, функция для вычисления площади
треугольника по формуле Герона.
(define (square-triangle a b c)
(let ((p (/ 2 (+ a b c))))
(sqrt (* p (- p a) (- p b) (- p c))))
Того же эффекта можно было бы добиться применяя
лямбда-выражение.
(define (square-triangle a b c)
(lambda (p) (sqrt (* p (- p a) (- p b) (- p c)))
(/ 2 (+ a b c))))
Семантически это одно и то же, но, конечно,
запись с let намного нагляднее.
Составные данные
Любые два объекта можно объединить в новый
объект, называемый (точечной) парой с
помощью примитивной функции cons. Чтобы
получить составные части пары, используются
функции car и cdr.
(cons a b)- возвращает составной объект - пару
(a . b)
(car a)- возвращает первый элемент пары
(cdr a)- возвращает второй элемент пары
(define x (cons 1 2))
x
(1 . 2)
(car x)
1
(cdr x)
2
Полученные пары, мы можем объединять далее, и
таким образом, мы имеем стандартное
универсальное средство для создания
разнообразных структур данных.
(cons (cons 'a 1) 12 )
((a . 1) . 12)
При обработке таких структур необходимо иметь
возможность определить является ли выражение
атомом или парой. Это делается встроенным
предикатом pair?.
(pair? a)- возвращает
#t, если аргумент представляет
собой пару и #f в противном случае.
Выражения вида (a1 . (a2 . …(an . an+1)…))
кратко записывается (a1 a2 …an . an+1),
а если an+1представляет собой специальный
атом () (или nil) - то в виде (a1 a2 …an).
Такие вложенные цепочки пар называются списками.
(cons 1 (cons 2 (cons 3 4)))
(1 2 3 . 4)
(cons 1 (cons 2 (cons 3 () )))
(1 2 3)
Списки играют особую роль в
Лиспе. Чтобы упростить их формирование,
предусмотрена специальная функция list.
(list a1…an)- возвращает список объектов
(a1…an),
то есть (a1 .(a2 . …(an . nil)…)).
(list 1 2 3)
(1 2 3)
(car (list 1 2 3))
1
(cdr (list 1 2 3))
(2 3)
(list '+ 1 2)
(+ 1 2)
В действительности, выражения Лиспа
представляют собой ни что иное, как списки. Это
даёт возможность обрабатывать их как данные.
Чтобы получить выражение как таковое, а не его
значение используется специальная форма quote.
(quote a)- возвращает в качестве значения свой аргумент,
не вычисляя его.
Мы уже встречались с этой формой. Знак кавычки,
который мы ставили перед символами - всего лишь
«синтаксический сахар» для quote.
(quote a)
а
'а
а
''a
(quote a)
'(+ 1 2)
(+ 1 2)
(car '(+ 1 2))
+
Противоположность quote - функция eval,
вычисляющая значение выражения.
(eval '(+ 1 2))
3
(eval (list + 1 2))
3
Императивные особенности.
Конечно, в реальной работе потребуются и другие
возможности. Например, трудно обойтись без ввода
и вывода и Scheme, как и все варианты Лиспа,
предоставляет соответствующие процедуры.
Содержит он и операторы присваивания и довольно
тонкие средства управления процессом
вычислений. Но, поскольку их использование
выходит за рамки функционального
программирования, мы их рассматривать не будем5.
1 Некоторые склонны
относить к ним даже Smalltalk, хотя это далеко не
общепринятая точка зрения. Наиболее же
распространёнными в настоящее время являются
два диалекта: Common Lisp и Scheme. Они развивались
параллельно и при значительном влиянии друг на
друга. Один и аторов Scheme, Гай Стил - входит в
группу разработчиков Common Lisp.
2 Рассказывают, что
Джеральд Суссман, преподавая в MIT, решил что
просто глупо объяснять студентам, почему
10.0/4.0 = 2.5, но 10/4 = 2.
3 Это особенность Scheme. В
других диалектах Лиспа как правило используются
формы (set n e)и (defun f (a1…an) e).
4 В ранних версиях Scheme, где
упор делался на минимализм языка, применялась
только вторая форма.
5 Полное описание языка
можно найти в Revised5
Report on the Algorithmic Language Scheme.
Доступен в сети и неплохой учебник R. Kent Dybvig The Scheme Programming Language.
[
Содержание
| 1
| 2
| 3
| 4
| 5
| 5.1
| 5.2
| 5.3
| 5.4
| 5.5
| 5.6
| 5.7
| 5.8
| 5.9
| 6
| 6.1
| 6.2
| 6.3
| 6.4
| 6.5
| 7
| 7.1
| Литература
]
|