ЛЕКЦИЯ 4
Основные понятия лиспа
Язык ЛИСП (LISP) был разработан в 1958 году американским ученым Джоном Маккарти как функциональный язык, предназначенный для обработки списков. ( LISt Processing). Lisp - означает "лепетать". С появлением этого языка машина стала пока лепетать, a не говорить по-человечески.
В основу языка положен серьезный математический аппарат:
- лямбда-исчисление Черча
- алгебра списочных структур
- теория рекурсивных функций
Долгое время язык использовался узким кругом исследователей. Широкое распространение язык получил в конце 70-х - начале 80-х годов с появлением необходимой мощности вычислительных машин и соответствующего круга задач. В настоящем - Лисп одно из главных инструментальных средств систем искусственного интеллекта. Он принят как один из двух основных ЯП для министерства обороны США и постепенно вытесняет второй ЯП - АДА. Система AutoCAD разработана на Лиспе
Основные особенности лиспа
До изучения языка трудно говорить об его особенностях, но тем не менее...
Представление программы и данных производится одинаково - через списки. Это позволяет программе обрабатывать другие программы и даже саму себя.
Лисп как правило является интерпретирующим языком, также как BASIC.
Лисп безтиповый язык, это значит что символы не связываются по умолчанию с каким-либо типом.
Лисп имеет необычный синтаксис. Из-за большего числа скобок LISP расшифровывают как Lots of Idiotic Silly Parentheses. Программы, написанные на Лиспе во много раз короче, чем написанные на процедурных языках.
Элементарные понятия
Символьные данные: выражения и представление данных
Выражения
Основу ЛИСПа составляют символьные выражения, которые называются S-выражениями и образуют область определения для функциональных программ.
S-выражение (Simbolic expresion) - основная структура данных в ЛИСПе.
S-выражения:
(ДЖОН СМИТ 33 ГОДА)
((МАША 21) (ВАСЯ 24) (ПЕТЯ 1))
S-выражение - это либо атом, либо список.
Атомы
Атомы - это простейшие объекты Лиспа, из которых строятся остальные структуры.
Атомы бывают двух типов - символьные и числовые.
Символьные атомы - последовательность букв и цифр, при этом должен быть по крайней мере один символ отличающий его от числа.
ДЖОН АВ13 В54 10А
Символьный атом или символ - это не идентификатор переменой в обычном языке программирования. Символ как правило обозначает какой либо предмет, объект вещь, действие.
Символьный атом рассматривается как неделимое целое.
К символьным атомам применяется только одна операция: сравнение.
В МCL в состав символа могут входить:
+ - * / @ $ % ^ _ \ <>
Числовые атомы - обыкновенные числа
124
-344
4.5 3.055Е8
Числа это константы. Типы чисел зависят от реализации ЛИСПа.
Атом - простейшее S-выражение.
Списки
В ЛИСПЕ список это последовательность элементов (list). Элементами являются или атомы или списки. Списки заключаются в скобки, элементы списка разделяются пробелами.
(банан) – 1 атом
(б а н а н) – 5 атомов
(a b (c d) e) – 4 элемента
Таким образом список – это многоуровневая или иерархическая структура данных, в которой открывающиеся и закрывающиеся скобки находятся в строгом соответствии.
(+ 2 3) – 3 атома
(((((первый) 2) второй) 4) 5) – 2 элемента
Список, в котором нет ни одного элемента, называется пустым списком и обозначается "()" или символом NIL.
NIL – это и список и атом одновременно.
Пустой список играет такую же важную роль в работе со списками, что и ноль в арифметике.
Пустой список может быть элементом других списков.
(NIL) – список состоящий из атома NIL
(()) – то же самое, что и (NIL)
((())) – ((NIL))
((NIL ()) – список из двух других списков
Логические константы
NIL обозначает кроме этого, в логических выражениях логическую константу "ложь" (false).
Логическое "да"(true) задается символом "Т".
Атомы и списки - это символьные выражения или S-выражения. Соотношение рассмотренных основных типов ЛИСПА поясняет диаграмма:
Функции. Базовые функции.
Понятие функции
В математике функция отображает одно множество в другое.
Записывается: Y = F (x)
Для х из множества определения (Domain) ставится в соответствие Y из множества значений (range) функции F:
Можно записать: Y=F(x); F(x)→ Y; F:x→Y
У функции может быть любое количество аргументов, в том числе их может не быть совсем. Функция без аргументов имеет постоянное значение.
Примеры функций:
abs( -3 ) → 3 абсолютная величина.
+ ( 2 , 3 ) → 5 сложение
union ( ( a , b ), ( c , b ) ) → ( a , b , c ) объединение множеств.
количество_букв ( слово ) → 5
Типы аргументов и функций
Функция в общем случае задает отображение из нескольких множеств в множество значений.
Можно записать: F(x, y) → Z; F : A 6B →C
Это функция двух аргументов: первый х принадлежит А, второй у принадлежит В, значение z принадлежит С. В этом случае говорят, что аргументы и значение имеют разные типы.
Префиксная нотация
В математике принята префиксная нотация, в которой имя функции стоит перед аргументами заключенными в скобках.
f ( x )
g ( x , y )
h ( x , g ( y , z ) )
В Лиспе для записи арифметических выражений и функций используется единая префиксная форма записи, в которой имя функции или действия стоит перед аргументами и записывается внутри скобок.
( f x )
( g x y )
( h x ( g y z ) )
( + x y )
( - x y )
( * x ( + x z ) )
В арифметических выражениях используется инфиксная запись:
x + y
x – y
x * ( x + z )
Достоинства:
-
упрощается синтаксический анализ выражений, так как по первому
символу текущего выражения система уже знает, с какой структурой
имеет дело;
-
появляется возможность записывать функции в виде списков, т.е. данные (списки) и программа (списки) представляются единым образом.
Диалог с интерпретатором ЛИСПА
Транслятор Лиспа работает, как правило в режиме интерпретатора.
Read-eval-print цикл
loop ( read evaluate print)
В Лиспе сразу читается, затем вычисляется (evaluate) значение функции и выдается значение.
Пример:
*( + 2 3 )
5
Иерархия вызовов
В вводимую функцию могут входить функциональные подвыражения
*(* ( + 1 2 ) ( + 3 4 ))
21
Блокировка quote
В некоторых случаях не требуется вычисления значений выражений, а требуются само выражение. Если прямо ввести * (+ 2 3 ) , то 5 получится как значение. Но можно понимать ( + 2 3 ) не как функцию, а как список. S-выражения, которые не надо вычислять, помечают для интерпретатора апострофом " ' " (quote).
QUOTE - специальная функция с одним аргументом, которая возвращает в качестве значения этот аргумент.
*' ( + 2 3 )
( + 2 3 )
Или
*' y
y
Вместо апострофа можно использовать функцию QUOTE
*( quote ( + 2 3 ) )
( + 2 3 )
*( quote y )
y
*' ( a b ' ( c d ) )
(a b ( quote c d ) )
Апостроф автоматически преобразуется в QUOTE.
*( quote ' y )
( QUOTE Y )
*'' y
( QUOTE Y )
*( QUOTE QUOTE )
QUOTE
Перед константами не надо ставить апостроф, так как число и его значение совпадают
*' 3.17
3.17
*( + ' 2 3 )
5
*t
T
*' t
T
*' nil
NIL
Функция EVAL
Функция EVAL обеспечивает дополнительный вызов интерпретатора Лиспа. При этом вызов может производиться внутри вычисляемого S-выражения. Функция EVAL позволяет снять блокировку QUOTE.
*( quote ( + 1 2 ) )
( + 1 2 )
*( eval ( quote ( + 1 2 ) ) )
3
Quote и eval действуют во взаимно противоположенных направлениях и аннулируют эффект друг друга.
*( setq x ' ( a b c ) )
( a b c )
*x
( a b c )
*' x
x
*( eval ' x )
( a b c )
EVAL - это универсальная функция Лиспа, которая может вычислить любое правильно составленное S-выражение.
Использование символов в качестве переменных
Изначально символы в Лиспе не имеют значения. Значения имеют только константы.
*t
T
*1.6
1.6
Если попытаться вычислить символ, то система выдает ошибку.
Значения символов хранятся в ячейках, закрепленных за каждым символом. Если в эту ячейку положить значение, то символ будет связан (bind) сo значением. В процедурных языках говорят "будет присвоено значение".
Для Лиспа есть отличие:
- Не оговаривается, что может храниться в ячейке: целое, атом, список, массив и т.д. В ячейке может храниться, что угодно.
- С символом может быть связана не только ячейка со значением, а многие другие ячейки, число которых не ограничено.
Для связывания символов используется три функции.
Функция SET
Функция SETсвязывает символ со значением, предварительно вычисляя значения аргументов
В качестве значения функция SET возвращает значение второго аргумента.
*( set 'd ' ( x y z ) )
( x y z )
*( set ' a ' b )
b
Если перед первым аргументом нет апострофа, то значение будет присвоено значению этого аргумента.
*( set a ' e )
e
*a
b
*b
e
На значение символа можно сослаться, записав его без апострофа.
Функция SETQ
SETQ аналогична SET, но не вычисляет значение первого аргумента. Буква q на блокировку
*( setq m ' k )
k
*m
k
Обобщенная функция SETF
SETF действует аналогично SETQ, но может использоваться для присвоения символу не только значения.
Похожие статьи:
