MULISP1

Мы рады приветствовать Вас в увлекательном и загадочном Мире ЛИСПа!

Если вы новичек в программировании вообще и в программировании на

ЛИСПе, в частности, то Вам будет довольно легко постигнуть все тайны

ЛИСПа и функционального программирования, которое развилось благодаря

ЛИСПу. Если же Вы уже знакомы с распространенными языками программирова-

ния типа Паскаль, Си, Фортран, то Вам будет довольно непросто привыкнуть

к новому взгляду на составление и написание программ, взгляду, который

исповедует и поддерживает ЛИСП. Но преодолейте все трудности - обещаем,

что все Ваши труды окупятся сторицей теми возможностями, которые откро-

ются Вам в ЛИСПе. Благодаря ЛИСПу Вы сможете реализовать проекты, очень

трудоемкие при программировании на традиционных языках программирования.

Итак, запаситесь терпением и вперед - в МИР ЛИСПА !

CONTINUE

Немного истории. Зачем и как появился ЛИСП.

Язык LISP был предложен Дж. Маккарти в 1958 году и ориентирован на

разработку программ для решения задач нечисленного характера. Он был раз-

работан первоначально для работы со списками (отсюда и название LISP -

LISt Processing). Но понятие "список" оказалось настолько емким, что ЛИСП

завоевал большую популярность. С помощью списков можно представить прак-

тически любую структуру данных, причем такое представление часто наиболее

естественно и очень гибко. Дж. Маккарти пошел еще дальше - он не усмотрел

существенного различия между программой и данными: программа и предложения,

ее составляющие, - это тоже списки, ничем не отличающиеся от данных.

Именно поэтому ЛИСП получил большое распространение в области искусствен-

ного интеллекта, где часто данные, полученные и селектированные системой,

надо выполнить, то есть интерпретировать их как программу и получить сле-

дующие данные.

Существует множество диалектов ЛИСПа - Common LISP, MacLISP,

InterLISP, Standard LISP, muLISP, R-LISP и т.д. Но основа всех этих язы-

ков, сколь бы ни были они непохожи друг на друга, одна - однородный син-

таксис программ и данных. Заметим, что сейчас наиболее стандартизованным

наречием ЛИСПа является Common LISP.

В этом уроке мы познакомим Вас с одной из разновидностей ЛИСПа для

персональных компьютеров - muLISP'ом. Вы узнаете основные понятия ЛИСПа и

его базовые функции.

CONTINUE

LISP предназначен для обработки символьных данных. Он оперирует

структурами символьных данных, такими, как слова или предложения. В ЛИСПе

любые символьные данные представлены объектами. Мы начнем этот урок с

описания, что такое объекты и как использовать их для представления и об-

работки символьных данных.

Объекты могут быть простыми или составными. Простой объект называ-

ется атомом. Интуитивно это название понятно - атомом является все то, в

чем невозможно выделить составляющие его компоненты. К атомам можно обра-

щаться по их именам. Имя атома - это строка символов. Заметим, что поня-

тие "имя" здесь немного отличается от общепринятого понятия "имя перемен-

ной", ибо атом - это не совсем переменная, поэтому и его имя - это нечто

иное. Например, числа в ЛИСПе являются атомами и имя числа, положим,

-459, есть -459. Приведем примеры имен:

APPLE RABBIT 54321 -41

Заметим, что значением атома является сам атом:

$ APPLE

CONTINUE

Составные объекты называются списками. Список состоит из нуля или

более объектов. Последнее слово должно подсказать Вам, что элементом

списка может быть также список (или вообще любой составной объект) или

атом - других объектов нет. Список вводится и отображается на дисплее как

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

мер, вот список из четырех элементов:

(THE QUICK BROWN FOX)

А как muLISP выводит списки ?

- давайте посмотрим ($ - это приглашение muLISP'a вводить предложение

языка):

$ '(THE QUICK BROWN FOX)

А что если в скобках ничего нет ?

- Это называется пустой список :

$ '()

NIL - атом, обозначающий в данном случае пустой список. Таким обра-

зом, Вы видите, что в ЛИСПе принято скобочное пердставление списков.

CONTINUE

Мы определили ранее ЛИСП как язык для символьной обработки, так как

он оперирует символьными структурами данных. Но ЛИСП также и язык функци-

онального программирования, потому что функции - и только они! - исполь-

зуются для обработки символьных данных. В ЛИСПе нет ни операторов, ни

процедур - есть только функции.

Получая упорядоченный набор объектов, функция возвращает уникальное

значение, вычисленное по переданным объектам. Заметим, что есть класс

функций, основное назначение которых - побочный эффект, а не вычисление

возвращаемого объекта. Использование побочных эффектов во многих традици-

онных языках программирования является плохим тоном и признаком низкой

квалификации программиста, но в ЛИСПе это нормально, так как многие вещи

можно сделать только за счет побочного эффекта.

Если Вам не очень понятна мысль об использовании побочного эффекта,

считайте ее лирическим отступлением и на время забудьте эти слова.

Выше мы отмечали, что в ЛИСПе нет различия между данными и програм-

мой. В самом деле, даже визуально Вы не различите их :

Вот вызов функции CAR (о ней чуть ниже) и ответ muLISP'а:

$ (CAR '(CAR CDR))

а это список, второй элемент которого - также список

$ '(CAR (CAR CDR))

CONTINUE

В ЛИСПе есть 5 базовых функций-примитивов для работы с объектами

(атомами и списками). Используя эти 5 примитивов и зная, как определять

свои функции, Вы можете написать практически любую программу обработки

списков. Но прежде чем рассказать о пяти примитивах, опишем вкратце

систему muLISP'а и принципы ее работы.

Кстати, даже не зная эти примитивы, но имея опыт работы со списками

и имея в виду, что в ЛИСПе есть лишь два типа объектов - атомы и списки,

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

вать их. Подумайте, прежде чем двигаться дальше, - это не вредно!

CONTINUE

В общих чертах общение с muLISP'ом похоже на работу с калькулятором.

Приглашением ко вводу и сигналом, что muLISP готов к дальнейшей работе,

является знак $. В ответ на этот знак Вы вводите выражение, которое

muLISP считывает, затем оценивает и выдает результат на дисплей. Отметьте

особо, что все, что вводится, muLISP ОЦЕНИВАЕТ (!). Если Вы ввели чушь,

то muLISP попытается ее вычислить, но, конечно, ничего не получится. Тог-

да появляется сообщение об ошибке и запрос дальнейших действий. На первых

порах в ответ на такой запрос вводите латинскую букву T (Top-level -

возвратиться к состоянию системы, каким оно было до возникновения ошибки).

CONTINUE

Если Вы не хотите, чтобы введенное Вами выражение было вычислено, а

желаете ввести его как данные, Вы должны предварить вводимое выражение

знаком апострофа ' (не путайте его со знаком обратного апострофа ` на

клавиатуре - это разные вещи!). Таким образом, знак ' подавляет вычисле-

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

дить имя атома APPLE:

$ 'APPLE

Но Вы уже знаете, что в ЛИСПе значением атома является сам атом, то есть

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

вычку перед атомами:

$ APPLE

- результат тот же.

Теперь почувствуйте это сами. Попробуйте ввести различные атомы раз-

ными способами и посмотрите реакцию ЛИСПа. Для выхода в среду muLISP'а

нажмите на клавишу с русской буквой О. По завершении Ваших экспериментов

в ответ на приглашение $ введите выражение

(RETURN)

и нажмите <Enter>.

BREAK

CLRSCRN

Список вводится заключенным в круглые скобки. Посмотрите, как пра-

вильно ввести список:

$ '(CAT COW DOG PIG)

Здесь знак ' обязателен, если Вы не хотите вычислять значение

списка, которое в данном случае бессмысленно. Как правило, забыв поста-

вить кавычку, где она нужна, Вы получите в ответ сообщение об ошибке

"Undefined Function" (Неопределенная функция) - вспомните, что в ЛИСПе

вызов функции и список синтаксически неотличимы!

CONTINUE

Элементы списка также могут быть списками, а раз так, то и

списки-элементы также нужно заключать в скобки - закон распространяется

на всех. Например, покажем сложную структуру:

$ '((HEIGHT 72) (WEIGHT 175) (EYES BLUE) (HAIR BLOND))

а если не поставить скобок внутри:

$ '( HEIGHT 72 WEIGHT 175 EYES BLUE HAIR BLOND)

- совершенно иной результат, не правда ли ? Если Вам кажется, что

интерпретатор ошибается и ответ должен быть одинаковым, не огорчайтесь -

спустя 5 минут вы поймете разницу.

Заметьте, что элементы-списки уже не надо предварять символом ' -

ведь главный список уже не вычисляется.

А теперь - тренаж. Попробуйте ввести различные списки. Нажмите на

клавишу с руской буквой о для самопознания; когда наиграетесь, прошу да-

лее - введите (RETURN) и нажмите <Enter>. Нас ждут великие дела!

BREAK

CLRSCRN

Теперь можно приступить к изучению базовых примитивов. Вспомним, что

LISP - это аббревиатура от LISt Processing (обработка списков). Поэтому

все 5 примитивов - это основные функции для манипуляции списками. Одной

из самых распространенных операций над списками является выделение одного

из его элементов. Это нужно везде, где мы хотим работать с каким-то эле-

ментом независимо. Функции, которые делают это, называют функциями-селек-

торами.

Две из пяти базовых функций ЛИСПа являются селекторами. Это

CAR и CDR

Обе они имеют по одному аргументу-списку.

Функция CAR возвращает первый элемент списка-аргумента. CDR возвра-

щает весь список за исключением первого его элемента, то есть выделяет

хвост списка.

Расшифровка названий этих функций сложна и не внесет ясности. Имена

CAR и CDR восходят к первой реализации ЛИСПа на IBM 704 в начале 60-х.

Так назывались в этой машине регистры, содержащие указатели на первый

элемент списка и на его хвост.

CONTINUE

Теперь, коль мы добрались до функций ЛИСПа, не худо бы узнать, а как

вызывать функцию. Что ж, смотрите ...

Вызов функции имеет следующий формат:

(<имя> <арг1> <арг2> ....)

где <имя> - имя функции, <арг1> - первый аргумент функции, <арг2> -

второй аргумент, и т.д.

Заметим, что левая открывающая скобка не следует за именем функции,

как принято в математике и традиционных языках программирования, а пред-

шествует имени - таковы правила ЛИСПа. Такая запись доставляет много хло-

пот начинающим "лисповцам", но и обилие достоинств тем, кто на ЛИСПе "со-

баку съел". Именно поэтому возможно выполнение данных как программы, и

именно поэтому появился знак ' .

CONTINUE

Этот пример демонстрирует, как найти голову списка:

$ (CAR '(DOG CAT COW PIG))

а здесь берется хвост этого же списка:

$ (CDR '(DOG CAT COW PIG))

Заметим, что в последнем примере знак ' также обязателен, если Вы не

хотите, чтобы аргументы вычислялись. При вызове функции ЛИСП сначала вы-

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

лите CAR списка

((RAM 256) (ROM 64) (DISK 322))

Вы должны:

а) ввести имя CAR большими буквами;

б) не забыть перед списком-аргументом поставить кавычку '

в) расставить все скобки - так как аргумент представляет собой

список, то он должен быть заключен в скобки.

Если захотите вернуться в среду первой лабораторной работы, будем

очень рады - введите (RETURN) и нажмите <Enter>.

BREAK

CLRSCRN

Функция CDR возвращает все за исключением CAR списка. Если значением

CAR является атом либо список (в том случае, когда первый элемент списка,

к которому применяется CAR, является также списком), то значением функции

CDR всегда является список.

Следующий пример показывает, как найти CDR списка (DOG CAT COW PIG):

$ (CDR '(DOG CAT COW PIG))

На протяжении данной паузы определите CDR списка

((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).

Когда будете готовы возвратиться к продолжению лабораторной работы, вве-

дите (RETURN) и нажмите <ENTER>.

BREAK

CLRSCRN

До сих пор аргументы в функцию мы передавали посредством кавычки '.

Но нет никаких запретов на то, чтобы значение, возвращаемое одной функци-

ей, не могло бы быть использовано как аргумент вызова другой функции.

Рассмотрим задачу выделения второго элемента списка. CDR списка -

это список, состоящий из всех элементов исходного списка за исключением

первого. Следовательно, CAR от списка - результата применения CDR, и бу-

дет являтся решением нашей задачи. Пусть исходный список есть (DOG CAT

COW PIG). Тогда вычисление второго элемента будет выглядеть так:

$ (CAR (CDR '(DOG CAT COW PIG)))

Используя комбинацию функций CAR и CDR, попробуйте выделить

подсписок (WEIGHT 175) из списка ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).

Сначала задайте себе вопрос: каким по счету является элемент (WEIGHT 175)

в списке ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)). Если вы правильно отве-

тите на этот вопрос, то решение задачи не составит труда!

BREAK

Конечно, (WEIGHT 175) является вторым элементом списка

((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)) !

И решение задачи просто :

$ (CAR (CDR '((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)) ))

CONTINUE

А теперь выделите атом 175 из списка

((HEIGHT 72) (WEIGHT 175) (HAIR BLOND))

BREAK

Я надеюсь, Вы сделали правильно:

$ (CAR (CDR (CAR (CDR '((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)) ))))

Несколько длинновато, но правильно. Казалось бы, можно опустить пер-

вый CAR в этом выражении, так как CDR, стоящий перед ним, возвращает

хвост списка (WEIGHT 175). Но посмотрите:

$ (CDR '(WEIGHT 175))

Это не 175, ведь исходный список - это список из одного элемента!

CONTINUE

Наверное, Вы заметили, что при выделении элементов списка получаются

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

ко Вы, но задолго до Вас, и придумали нехитрый способ сократить количест-

во скобок и вызовов CAR и CDR. Вот эти сокращения:

(CAAR L) <=> (CAR (CAR L))

(CADR L) <=> (CAR (CDR L))

(CDAR L) <=> (CDR (CAR L))

(CDDR L) <=> (CDR (CDR L))

Вы уже заметили правило? Оно таково: между C и R пишутся средние

буквы слов CAR и CDR в той последовательности, в которой вызовы CAR и CDR

следуют в развернутой записи. Например,

(CDAADR L) <=> (CDR (CAR (CAR (CDR L))))

Правда, здесь есть ограничение на длину такого сжатого написания. В

течение данной паузы попробуйте определить это ограничение и заодно по-

экспериментируйте с такими аббревиатурами.

BREAK

CLRSCRN

CAR и CDR называют селекторами, потому что они выделяют части объек-

та. Но существуют и функции-дополнения к ним; это функции-конструкторы.

Они собирают составной объект из простых объектов как из составляющих.

Один из примитивов является функцией - конструктором и называется CONS.

CONS используется для добавления объекта в начало существующего списка.

Первый аргумент этой функции - объект, который необходимо добавить в го-

лову списка; второй аргумент - список. Например

$ (CONS 'DOG '(CAT COW PIG))

Попытайтесь добавить (EYES BROWN) к ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).

Соблюдайте баланс скобок вокруг каждого аргумента CONS

BREAK

CLRSCRN

Заметим, что CAR от результата выполнения CONS будет всегда равен

первому аргументу CONS. Аналогично, CDR от CONS есть его второй аргумент.

Убедитесь в этом:

$ (CAR (CONS 'DOG '(CAT COW PIG)))

$ (CDR (CONS 'DOG '(CAT COW PIG)))

Теперь посмотрим, сможете ли Вы с помощью функций CONS, CAR и CDR из

списков ( X Y Z ) и ( A B C ) получить список ( A Y Z ).

BREAK

Правильное решение:

$ (CONS (CAR '(A B C)) (CDR '(X Y Z)))

CONTINUE

А теперь попробуйте вычислить CONS от CAR от CDR списка ( A B C ) и

списка ( X Y Z ). Не забывайте скобки!

BREAK

Правильный ответ:

$ (CONS (CAR (CDR '(A B C))) '(X Y Z))

CONTINUE

Как отмечалось выше, данные в ЛИСПе могут быть либо атомами, либо

списками. Также мы поняли, что CAR от списка есть первый элемент этого

списка. Но что есть CAR от атома? Хотя это нестандартное использование

функции CAR, в muLISP'е оно не приведет к ошибкам, так как muLISP не вы-

зывает CAR с аргументом - атомом, он просто возвращает аргумент как зна-

чение функции. Но то, что можно в muLISP'е, может привести к ошибкам в

других наречиях ЛИСПа. Как же избежать подобных ситуаций? Нам надо иметь

возможность распознавать объект - атом он или нет. Конечно, в ЛИСПе для

этого есть соответствующая функция! И она является четвертым примитивом -

это функция-распознаватель ATOM. ATOM - функция одного аргумента; и возв-

ращает она атом T, если аргумент является атомом, и атом NIL, если аргу-

мент не есть атом. Например,

$ (ATOM 'APPLE)

$ (ATOM '(DOG CAT COW PIG))

Здесь прервитесь ненадолго, чтобы потренироваться в применении новой

функции - ATOM. Проверьте, является ли число атомом; а как с помощью

функции ATOM превратить ложь (NIL) в истину? Подумайте! Проверьте также,

какой результат будет у вызова (ATOM '() ) и попробуйте его объяснить.

BREAK

CLRSCRN

$ (ATOM '())

Хотя аргумент функции - список, но она возвращает T, то есть '() -

это атом! Да, это так - в muLISP'е пустой список представляется атомом

NIL. Так,

$ '()

Попытайтесь найти CDR одноэлементного списка '(APPLE).

BREAK

CLRSCRN

Последняя примитивная функция ЛИСПа - это EQL. Эта функция имеет два

аргумента и проверяет, являются ли два ее аргумента-атома одними и теми

же атомами, то есть равны ли значения атомов:

$ (EQL 'ROM 'RAM)

$ (EQL (CAR '(DOG CAT COW)) (CAR (CDR '(HORSE DOG PIG))))

Используя функции CAR, CDR и EQL, проверьте, равен ли вес (weight),

заданный в списке ((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)), атому 175.

BREAK

Правильный ответ:

$ (EQL 175 (CAR (CDR (CAR (CDR '((HEIGHT 72) (WEIGHT 175) (HAIR BLOND)))))))

CONTINUE

Помните, что EQL сравнивает только атомы. Если вы попытаетесь срав-

нить объекты, не являющиеся атомами, то результат всегда будет NIL.

Посмотрите:

$ (EQL '(DOG CAT COW) '(DOG CAT COW))

На основании функции EQL и используя рекурсию, о которой Вы узнаете

в следующих лабораторных работах, Вы сможете построить функции для срав-

нения любых объектов.

CONTINUE

В этой лабораторной работе Вы познакомились с пятью основными прими-

тивами ЛИСПа, имеющимися в любой реализации этого языка. Приведем краткое

резюме:

1. (CAR список) - функция - селектор; возвращает первый элемент

<списка>

2. (CDR список) - функция - селектор; возвращает модифицированный

<список> без первого элемента, то есть хвост списка.

3. (CONS объект список) - функция - конструктор; возвращает список,

голова ( CAR ) которого есть <объект>, а хвост ( CDR ) - <список>.

4. (EQL атом1 атом2) - функция, возвращающая T (истина), если

<атом1> и <атом2> одинаковы, и NIL (ложь) в противном случае.

5. (ATOM объект) - функция - распознаватель; возвращает T, если

<объект> является атомом, и NIL в противном случае.

Поздравляем! Вы добрались до конца первого урока! Впереди Вас ждет

более интересная информация, но без знания основ невозможно в ней доско-

нально разобраться.

CONTINUE

А теперь убедитесь, что Вы усвоили материал урока и самостоятельно

выполните небольшое

Задание

1. Используя базовые функции, выясните, равен ли цвет волос ANN, за-

данный в списке

((DOLLY HAIR BLOND) (ANN HEIGHT 68) (ANN HAIR BROWN))

значению BROWN (русый)?

2. Из атомов и одноэлементных списков сконструируйте список

((HAIR BLOND) (HEIGHT 55) (EYES BLUE))

3. Cоздайте из атомов список

(a (b c) d)

CONTINUE

$ (RDS)