ЛИСП

Лабораторнаяработа № 1.

Тема: Ознакомительнаяработа в средеMuLisp. Базовые функцииЛиспа.Символы, свойствасимволов. Средст-ваязыка для работыс числами.

Цель: Ознакомитьсясо средой MuLisp.Изучить базовыефункции Лиспа,символы и ихсвойства, атакже средствадля работы счислами.

1. Основныеположенияпрограммированияна Лиспе.

2. Загрузка системы,системныйредактор.

3. Базовые функцииязыка. Символы,свойства символов.

4. Средства языкадля работы счислами.

5. Задание клабораторнойработе.

6. Вопросы.

1. Основныеположенияпрограммированияна Лиспе.

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

• Язык имеетфункциональнуюнаправленность,т. е. любое предложениезаключенноев скобки, введенноевне редакторасчитаетсяфункцией ивыполняетсясразу посленажатия «ENTER».

• Чтобы предотвратитьвычислениезначения выражения,нужно передэтим выражениемпоставитьапостроф «’».Апостроф передвыражением- это на самомделе сокращениелисповскойфункции QUOTE.

• В Лиспе формыпредставленияпрограммы иобрабатываемыхею данных одинаковы.И то и другоепредставляетсясписочнойструктуройимеющей одинаковуюформу.

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

• Основные типыданных языка- атомы и списки.

Атомы - это символыи числа.

Список - упорядоченнаяпоследовательность,элементамикоторой являютсяатомы либосписки. Спискизаключаютсяв круглые скобки,элементы спискаразделяютсяпробелами.Несколькопробелов междусимволамиэквивалентныодному пробелу.Первый элементсписка называется«головой», аостаток , т. е.список безпервого элемента,называется«хвостом. Списокв котором нетни одного элемента,называетсяпустым и обозначается«()» либо NIL.

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

• Символы Tи NILимеют в Лиспеспециальноеназначение:T -обозначаетлогическоезначение истина,а NIL- логическоезначение ложь.

• При генерацииили считыванииMuLispомнового символа,за его величинупринимаетсяон сам. Такаяссылка символана себя называетсяавтоссылкой.

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

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

• Определенияфункций могутхраниться вфайлах и загружаться используя функцию LOAD:

(load )

Эта функциязагружает файлвыражений и выполняет этивыражения. - этостроковаяконстанта,которая представляетсобой имя файла без расширения (подразумевается расширение".lsp"). Если операция успешно завершена,LOAD возвращаетимя последнейфункции, определеннойв файле. Еслиоперация невыполнена, LOADвозвращаетимя файла ввиде строковоговыражения.

Функция LOAD неможет вызываться из другой функции LISP. Она должна вызываться непосредственнос клавиатуры,в то время как ни одна другая функция LISP ненаходится впроцессе выполнения.

• Интерпретаторсчитает файлами,содержащимиисходные текстыпрограмм наЛиспе, все файлы,имеющие расширениеLSP.

• В связи с тем,что диалектMuLispвключает всебя сравнительнонебольшойнабор базовыхфункций, указаннаяЛисп-системаобеспечиваетсябиблиотекамиЛисп-функций,дополняющимибазовый наборфункциями,имеющимисяв CommonLisp-е и другихдиалектах(Common.lsp, Array.lspи т. д. ...).

2.Загрузкасистемы. Системныйредактор.

Запуск системыMuLisp срасширениемCommon.lsp осуществляетсякомандой:

MuLisp87.comCommon.lsp.

После несколькихсекунд загрузкина экране дисплеяпоявится сообщение:

MuLisp-87 IBM PC MS-DOS Version 6.01(11/05/87)

(C ) Copyright SoftWarehouse, Inc.,1983, 1985, 1986, 1987.

All rights Reserved Worldwide.

; Loading C:Common.lsp

После чегопоявится знак$,означающийприглашениесистемы к работе.Для загрузкисистемногоредакторанеобходимонабрать следующуюкоманду:

(LOAD edit.lsp)

Системныйредактор начинаетработать. Ончистит экранрисует рамкуи выдает наэкран своеменю:

Alpha, Block,Delete, Jump, List, Options, Print, Quit, Replace, Search, Transfer,Undelete иWindow.

Затем системаждет, покапользовательне выберет однуиз опций. Дляэтого необходимоустановитькурсор на выбраннойопции и нажатьклавишу «Enter».Переход отодной опциик другой производитсяс помощью клавиши«Tab».

• Alpha:включениережима редактирования.

• Block:работа с блоком.Выделение,копирование,удаление, перенос и др.

• Delete:удаление блока,символа, слова,строки.

• Jump:переход в началоили конец текстапрограммы,вверх-внизстраницы.

• List:работа со списком.Удаление, переходк предыдущему,последующему.

• Options:работа с цветами,монитором,звуком.

• Print:печать текстапрограммы.

• Quit:выход из системы.

• Replace:изменениестроки.

• Search:поиск строки.Причем строчныеи прописныебуквы различаются.

• Transfer:работа с файлами.Запись, нахождение,объединение,удаление.

• Undelete:восстановление.

• Window:работа с окнами.Открыть, закрыть,перейти к другомуи т. д.

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

Функции разбора.

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

(CAR список) рS -выражение (атомлибо список).

_(CAR ‘(a b cd)) р a

_(CAR ‘((a b)c d)) р (ab)

_(CAR ‘(a))р a

_(CAR NIL)р NIL «Головапустого списка- пустой список.»

Вызов функцииCAR саргументом(a b c d)без апострофабыл бы проинтерпретированкак вызов функции«a» с аргументом«b c d»,и было бы полученосообщение обошибке.

Функция CARимеет смыслтолько дляаргументов,являющихсясписками.

(CAR ‘a)р Error

Функция CDR- возвращаетв качествезначения хвостовуючасть списка,т. е. список,получаемыйиз исходногосписка послеудаления изнего головногоэлемента:

(CDR список)р список

Функция CDRопределенатолько длясписков.

_(CDR ‘(a b cd)) р(b c d)

_(CDR ‘((a b)c d)) р(c d)

_(CDR ‘(a (bc d))) р((b c d))

_(CDR ‘(a)) рNIL

_(CDR NIL) рNIL

_(CDR ‘a) рError

Функция созданияCONS.

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

(CONS головахвост)

Для того чтобыможно быловключить первыйэлемент функцииCONS вкачестве первогоэлемента значениявторого аргументаэтой функции,второй аргументдолжен бытьсписком. Значениемфункции CONSвсегда будетсписок:

(CONS s-выражениесписок)рсписок

_(CONS ‘a ‘(bc)) р(a b c)

_(CONS ‘(a b)‘(c d)) р((a b) c d)

_(CONS (+ 1 2) ‘(+3)) р(3 + 3)

_(CONS ‘(a bc) NIL) р((a b c))

_(CONS NIL ‘(ab c)) р(NIL a b c)

Предикаты ATOM,EQ, EQL, EQUAL.

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

ПредикатATOM - проверяет,является лиаргумент атомом:

(ATOM s- выражение)

Значениемвызова ATOMбудет T,если аргументомявляется атом,и NIL- в противномслучае.

_(ATOM ‘a) рT

_(ATOM ‘(a bc)) рNIL

_(ATOM NIL) рT

_(ATOM ‘(NIL))рNIL

Предикат EQсравниваетдва символаи возвращаетзначение T,если они идентичны,в противномслучае -NIL. С помощьюEQсравниваюттолько символыили константыT иNIL.

_(EQ ‘a ‘b)рNIL

_(EQ ‘a (CAR‘(a b c))) рT

_(EQ NIL ()) рT

Предикат EQL работаеттак же как иEQ, но дополнительнопозволяетсравниватьоднотипныечисла.

_(EQL 2 2) рT

_(EQL 2.0 2.0) рT

_(EQL 2 2.0) рNIL

Для сравнениячисел различныхтипов используютпредикат «=».Значениемпредиката «=»является Tв случаеравенства чиселнезависимоот их типов ивнешнего видазаписи.

(= 2 2.0) рT

Предикат EQUALпроверяетидентичностьзаписей. Онработает как EQL, но дополнительнопроверяетодинаковостьдвух списков.Если внешняяструктура двухлисповскихобъектов одинакова,то результатом EQUAL будетT.

_(EQUAL ‘a‘a) рT

_(EQUAL ‘(a bc) ‘(a b c)) рT

_(EQUAL ‘(a bc) ‘(CONS ‘a ‘(b c))) рT

_(EQUAL 1.0 1) рNIL

Функция NULLпроверяет напустой список.

_(NULL ‘()) рT

Вложенныевызовы CARи CDR.

Комбинациивызовов CARи CDRобразуют уходящиев глубину спискаобращения, вЛиспе для этогоиспользуетсяболее короткаязапись. ЖелаемуюкомбинациювызововCAR иCDR можно записатьв виде одноговызова функции:

(C...R список)

Вместо многоточиязаписываетсянужная комбинацияиз букв Aи D(для CAR и CDRсоответственно).В один вызовможно объединятьне более четырехфункций CARи CDR.

(CADAR x) у(CAR (CDR (CAR x)))

_(CDDAR ‘((ab c d) e)) р(c d)

_(CDDR ‘(k lm)) р(M)

Функция LIST- создает списокиз элементов.Она возвращаетв качествесвоего значениясписок из значенийаргументов.Количествоаргументовпроизвольно.

_(LIST ‘a ‘b‘c) р(a b c)

_(LIST ‘a ‘b(+ 1 2)) р(a b 3)

4.Символы,свойства символов.

Функции присваивания:SET, SETQ,SETF.

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

_(SET ‘a ‘(bc d)) р(b c d)

_a р(bc d)

_(SET (CAR a) (CDR(o f g)) р(f g)

_a р(b c d)

_(CAR a) рb

_b р(f g)

Значение символавычисляетсяс помощью специальнойфункции Symbol-value,которая возвращаетв качествезначения значениесвоего аргумента.

_(Symbol-value (CARa)) р(f g)

Функция SETQ- связываетимя, не вычисляяего. Эта функцияотличаетсяот SETтем, что вычисляеттолько второйаргумент.

_(SETQ d ‘(lm n)) р(l m n)

Функция SETF- обобщеннаяфункция присваивания.SETF используетсядля занесениязначения вячейку памяти.

( SETFячейка-памятизначение)

_(SETF ячейка‘(a b c)) р(a b c)

_ячейкар(a b c)

Переменная«ячейка» безапострофауказывает наячейку памяти,куда помещаетсяв качествезначения список(a b c).

Свойства символа.

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

(имя1 знач1 имя2знач2 ... имяN значN)

Пусть имя студентимеет следующийсписок свойств:

(имя Иван отчествоИванович фамилияИванов)

Функция GET- возвращаетзначение свойства,связанногос символом.

(GET символсвойство )

При отсутствиисвойства функцияGETвозвращаетNIL вкачестве ответа.

_(GET ‘студент‘имя)р Иван

_(GET ‘студент‘группа)рNIL

Присваиваниеи удалениесвойств.

Для присваиваниясимволу свойствв MuLisp (каки в CommonLisp) отдельнойфункции нет.Для этогоиспользуютсяуже известныенам функции:

(SETF (GET символсвойство) значение)

_(SETF (GET‘студент’группа)’РВ-90-1)р РВ-90-1

_(GET ‘студент’группа)р РВ-90-1

Удаление свойстваи его значенияосуществляетсяпсевдофункциейREMPROP:

Эта функциявозвращаетв качествезначения имяудаляемогосвойства. Еслиудаляемогосвойства нет,то возвращаетсяNIL.

(REMPROP символсвойство)

_(REMPROP ‘студент’группа)р группа

_(GET ‘студент’группа)р NIL

_(REMPROP ‘студент’ср_бал)р NIL

Для просмотравсего спискасвойств используютфункцию SYMBOL-PLIST.Значениемфункции являетсявесь списоксвойств.

(SYMBOL-PLIST‘СИМВОЛ)

(SYMBOL-PLIST‘студент)р (имяИван отчествоИванович фамилияИванов)

Свойства символовнезависимоот их значенийдоступны извсех контекстовпока не будутявно измененыили удалены.Изменениезначения символане влияет надругие свойства.Свойства символапередаютсядругому символус помощью функцииSETQ.

5.Средстваязыка для работыс числами.(Математическиеи логическиефункции).

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

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

Арифметическиедействия:

(+ числа) -сложение чисел

(- число числа)- вычитаниечисел из числа

(* числа) - умножениечисел

и т. д.

_(+ 5 7 4) р16

_(- 10 3 4 1) р2

_(/ 15 3) р5

Сравнениечисел:

(= число числа)р равны(все)

(

(> числочисла) рбольше (длявсех)

и т. д.

Числовые предикаты:

(ZEROPчисло) рпроверка наноль

(MINUSPчисло) рпроверка наотрицательность

и т. д.

Логическиедействия:

(NOTобъект) рлогическоеотрицание

(AND (формы))р логическоеИ

(OR(формы)) рлогическоеИЛИ

_(AND(ATOM NIL) (NULL NIL) (EQ NIL NIL)) рT

_( NOT (NULL NIL))рNIL

Кроме приведенных,существуетмножестводругих, но неменее полезныхфункций.

6. Заданиек лабораторнойработе.

1. Запишитепоследовательностивызовов CARи CDR,выделяющиеиз приведенныхниже списковсимвол «а».Упростите этивызовы с помощьюфункций C...R.

а) (1 2 3 а 4)

б) (1 2 3 4 а)

в) ((1) (2 3) (а 4))

г) ((1) ((2 3 а) (4)))

д) ((1) ((2 3 а 4)))

е) (1 (2 ((3 4 (5 (6 а))))))

2. Каковозначение каждогоиз следующихвыражений:

1. (ATOM(CAR (QUOTE ((1 2) 3 4))));

2. (NULL(CDDR (QUOTE ((5 6) (7 8)))));

3. (EQUAL(CAR (QUOTE ((7 )))) (CDR (QUOTE (5 7))));

4. (ZEROP(CADDDR (QUOTE (3 2 1 0))));

   
   

3. Проделайтеследующиевычисленияс помощьюинтерпретатораЛиспа:

а) 3.234*(45.6+2.43)

б) 55+21.3+1.54*2.5432-32

в) (34-21.5676-43)/(342+32*4.1)

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

а) ‘(+2 (* 3 5))

б) (+ 2 ‘(*3 5))

в) (+ 2 (’* 3 5))

г) (+ 2 (* 3 ’5))

д) (quote‘quote)

е) (quote 6)

5.1 Составьтесписок студентовсвоей группы

(ФИО ФИО ... ФИО)

5.2 Длякаждого студента

а) с помощьюфункции LISTсоставьтеследующиесписки:

Для самогостудента - (датарождения), (адрес),(средний балпо лекционнымзанятиям), (среднийбал по практическимзанятиям), (среднийбал по лабораторнымработам). Дляотца и матери- (ФИО), (дата рождения),(адрес), (местоработы).

б) с помощьюфункций CONSи SETQобъединитеполученныесписки и присвойтеих в виде значенийсимволам, означающимФИО каждогостудента:

ФИО ст. - (((датарождения ст.)(адрес ст.)((ср.бал(до десятых)по лекционнымзанятиям) (ср.бал по практическимзанятиям) (ср.бал по лабораторнымработам))) (((ФИОотца) (дата рожденияотца) (адрес)(место работыотца)) ((ФИО матери)(дата рожденияматери) (адрес)(место работыматери)))).

5.3 Дляпроизвольновыбранныхстудентов спомощью базовыхфункций сравните:

а) год рождения;

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

в) выясните, неявляются лиони родственниками;

г) выясните,живут ли онис родителями.

6.1Для каждогостудента составьтесписки свойств

а) оценки полекциям;

б) оценки попрактикам;

в) оценки полабораторнымработам.

6.2 Дляпроизвольновыбранныхстудентовсравнить свойства.

7.Вопросы.

1 Перечислитебазовые функции.

2 Каковы типыаргументовбазовых функций?

3 Какие значенияони возвращают?

4 Что такое предикат?

5 Назовите основныеотличия предикатовEQ, EQL, EQUAL и=.

6 Назовите отличияфункций CONSиLIST.

7 Что такое символ?

8 Различия функцийSET, SETQ, SETF?

9 Особенностисвойств символов?

Лабораторнаяработа №2.

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

Цель: Получитьнавыки в написаниифункций. Изучитьфункции ввода-вывода.

1. Функции, определяемыепользователем.

2. Функция ввода.

3. Функции вывода.

4. Вычисления,изменяющиеструктуру.

5. Задание клабораторнойработе.

6. Вопросы.

1.Функции,определяемыепользователем.

Определениефункций и ихвычислениев Лиспе основанона лямбда-исчисленииЧерча.

В Лиспе лямбда-выражениеимеет вид

(LAMBDA(x1 x2 ... xn) fn)

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

Телом функцииявляется произвольнаяформа, значениекоторой можетвычислитьинтерпретаторЛиспа.

_(lambda(x y) (+ x y))

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

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

(лямбда-выражениеа1 а2 ... аn)

Здесь ai- формы, задающиефактическиепараметры,которые вычисляютсякак обычно.

_((lambda (x y) (+x y)) 1 2) р3

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

_((lambda (x) ;Телолямбда-вызова-

((lambda(y) (list x y)) ‘b)) ‘a) р(a b) лямбда-вызов.

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

Дать имя и определитьновую функциюможно с помощьюфункции DEFUN:

(DEFUN имялямбда-списоктело)

DEFUNсоединяетсимвол с лямбда-выражением,и символ начинаетпредставлятьопределенныеэтим лямбда-выражениемвычисления.Значением этойформы являетсяимя новой функции.

После именованияфункции еевызов осуществляетсяпо имени ипараметрам.

_(defun list1 (x y)

(consx (cons y nil))) рlist1

_(list1 ‘c‘n) р(c n)

(eval )

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

(setq a 123)

(setq b 'a)

(eval 4.0) р4.000000

(eval (abs -10)) р10

(eval a) р123

(eval b) р123

2.Функцияввода.

Лисповскаяфункция чтенияREAD обрабатываетвыражениецеликом. Вызовфункции осуществляетсяв виде

_(READ)

(Вводимое выражение)р ;выражениепользователя

р(ВВОДИМОЕВЫРАЖЕНИЕ) ;значение функцииREAD

...

Функция непоказывает,что она ждетввода выражения.Она лишь читаетвыражение ивозвращаетв качествезначения самоэто выражение,после чеговычисленияпродолжаются.

Если прочитанноевыражениенеобходимосохранить длядальнейшегоиспользования,то вызов READдолжен бытьаргументомкакой-нибудьформы, напримерприсваивания(SETQ),которая свяжетполученноевыражение:

_(SETQ input (READ))

(+ 1 2) ;введенноевыражение

(+ 1 2) ;значение

_input р(+1 2)

3.Функциивывода.

Для выводавыраженийиспользуютнесколькофункций: PRINT,PRIN1, PRINC.

Функция PRINT.

Это функцияс одним аргументом,которая сначалавычисляетзначение аргумента,а затем выводитэто значение.ФункцияPRINT перед выводомаргументапереходит нановую строку,а после неговыводит пробел.Таким образом,значение выводитсявсегда на новуюстроку.

_(PRINT (+ 1 2))

3 ;вывод

3 ;значение

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

Функции PRIN1и PRINC.

Эти функцииработают также, какPRINT, но не переходятна новую строкуи не выводятпробел:

(PRIN1 5) р55

(PRINC 4) р44

Обеими функциямиможно выводитькроме атомови списков идругие типыданных которыемы рассмотримпозже:

_(PRIN1 «CHG»)р«CHG»«CHG»

_(PRINC «tfd»)рtfd«tfd» ;выводбез кавычек,

;результат- значение аргумента

С помощью функцияPRINCможно получитьболее приятныйвид. Она выводитлисповскиеобъекты в томже виде, как иPRIN1,но преобразуетнекоторые типыданных в болеепростую форму.

Функция TERPRI.

Эта функцияпереводитстроку. У функцииTERPRI нетаргументови в качествезначения онавозвращаетNIL:

_(DEFUN out (x y)

(PRIN1 x) (PRINC y)

(TERPRI)(PRINC (LIST ‘x ‘y)) рout

_(out 1 2) р12

(1 2)

4.Вычисления,изменяющиеструктуру.

Основнымифункциями,изменяющимифизическуюструктурусписков, являютсяRPLACA иRPLACD, которыеуничтожаютпрежние и записываютновые значенияв поляCAR иCDR списочнойячейки:

(RPLACA ячейказначение-поля) ;полеCAR

(RPLACD ячейказначение-поля) ;поле CDR

Первым аргументомявляется указательна списочнуюячейку, вторым- записываемоев нее новоезначение поляCAR илиCDR.Обе функциивозвращаютв качестверезультатауказатель наизмененнуюсписочнуюячейку:

_(SETQ a ‘(bc d)) р(b c d)

_(RPLACA a ‘d)р(d c d)

_(RPLACD a ‘(on m)) р(d o n m)

_a р(d o n m)

5.Заданияк лабораторнойработе.

1. Определитес помощьюлямбда-выраженияфункцию, вычисляющую:

1. +y-x*y;

2. x*x+y*y;

3. x*y/(x+y)-5*y;

2. Определитефункции (NULLx), (CADDR x) и(LIST x1 x2 x3) с помощьюбазовых функций.(ИспользуйтеименаNULL1, CADDR1 иLIST1, чтобы непереопределятьодноименныевстроенныефункции системы.

3. Используякомпозицию,напишите функции,которые осуществляютобращениесписка из 2, 3, ... ,nэлементов.

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

a) спискомиз 2, 3, ... элементов;

b)спискомиз 2, 3, ... атомов;

5. Напишитефункцию:

1. такую, что P(n)для произвольногоцелого nесть списокиз трех элементов,а именно: квадрата,куба и четвертойстепени числаn;

2. для двух аргументовзначениемкоторой являетсясписок из двухэлементов(разности иостатка отделения);

3. такую, что A(n)есть список(The answer is n). Так, значением(A 12)будет(The answer is 12);

4. семи аргументов,значениемкоторой служитсумма всехсеми аргументов.

6. Длякаждого изследующихусловий определитьфункцию одногоаргумента L, котораяимеет значениеT,если условиеудовлетворяется,и NILв противномслучае:

1. n-ыйэлемент L есть 12;

2. n-ыйэлемент Lесть атом;

3. Lимеет не болееnэлементов(атомов илиподсписков).

7. Напишитефункцию, котораявводит фразуна естественномязыке и преобразуетее в список.

8. Напишитефункцию, котораяспрашиваету пользователяФИО студентаиз группы (списокгруппы составленраньше) и выдаетследующиеданные о нем:

1. год рождения;

2. средний бал;

3. родителей;

4. списки свойств,присвоенныеему раньше.

9. Напишите функцию:

1. от одного аргумента(ФИО любогостудента),замещающуюв списке с даннымио нем (написанномраньше) подспискисо среднимибалами на спискисвойств;

2. вычисляющуюсредние балы,беря данныеиз списковсвойств.

10. Каковы будутзначения выражений(RPLACA x x)и (RPLACD xx), если:

1. x= ’(a b);

2. x= ’(a);

11. Вычислитезначение следующихвыражений:

1. (RPLACD‘(a) ‘b);

2. (RPLACA‘(a) ‘b);

3. (RPLACD(CDDR ‘(a b x)) ‘c);

4. (RPLACD‘(nil) nil)

   
   

6.Вопросы.

1. Чтотакое лямбда-выражение?

2. Длячего используетсяфункция DEFUN?

3. Чемразличаютсяосновные функциивывода?

4. Чтовозвращаетв качествезначения функцияREAD?

5. Особенностифункций, изменяющихструктуру?

Лабораторнаяработа №3.

Тема: Организациявычисленийв Лиспе.

Цель: Изучитьосновные функциии их особенностидля организациивычисленийв Лиспе.

1. ПредложенияLET иLET*.

2. Последовательныевычисления.

3. Разветвлениевычислений.

4. Циклическиевычисления.

5. Передачауправления.

6. Задание клабораторнойработе.

7. Вопросы.

1.ПредложенияLETи LET*.

ПредложениеLETсоздает локальнуюсвязь внутриформы:

(LET((m1 знач1)(m2знач2)...)

форма1 форма2...)

Вначале статическиепеременныеm1, m2, ...связываются(одновременно)с соответствующимизначениямизнач1, знач2, ... .Затем слевана право вычисляютсязначения формы1,формы2, ... . Значениепоследней формывозвращаетсяв качествезначения всейформы. Послевычислениясвязи статическихпеременныхликвидируются.

ПредложенияLETможно делатьвложеннымиодно в другое.

_(LET ((x ‘a)(y ‘b))

(LET ((z‘c)) (LIST x y z))) р(a b c)

_(LET ((x (LET ((z ‘a)) z)) (y‘b))

(LIST xy)) р(a b)

_(LET ((x 1) (y (+ x 1)))

(LIST xy)) рERROR

При вычисленииу У и Х еще нетсвязи. Значенияпеременнымприсваиваютсяодновременно.Это означает,что значениявсех переменныхmiвычисляютсядо того, какосуществляетсясвязываниес формальнымипараметрами.

Подобной ошибкиможно избежатьс помощью формыLET*:

_(LET* ((x 1) (y (+ x 1)))

(LIST xy)) р(1 2)

2.Последовательныевычисления.

ПредложенияPROG1 иPROGNпозволяютработать снесколькимивычисляемымиформами:

(PROG1 форма1... формаN)

(PROGN форма1... формаN)

Эти специальныеформы последовательновычисляют своиаргументы ив качествезначения возвращаютзначение первого(PROG1) илипоследнего(PROGN)аргумента.

_(PROG1 (SETQ x 1)(SETQ y 5)) р1

_(PROGN (SETQ j 8)(SETQ z (+x j))) р9

3.Разветвлениевычислений.

Условное предложениеCOND:

(COND (p1 a1)

...

(pn an))

Предикатамиpi ирезультирующимивыражениямиaiмогут бытьпроизвольныеформы. Выраженияpiвычисляютсяпоследовательнодо тех пор, покане встретитсявыражение,значениемкоторого являетсяT.Вычисляетсярезультирующеевыражение,соответствующееэтому предикату,и полученноезначение возвращаетсяв качествезначения всегопредложенияCOND. Если истинногопредиката нетто значениемCOND будетNIL.

Рекомендуетсяв качествепоследнегопредикатаиспользоватьсимвол T.Тогда соответствующееему anбудет вычислятьсяв том случае,если другиеусловия невыполняются.

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

ПредложенияCONDможно комбинировать.

(COND ((> x 0)(SETQ рез x))

((

((= х 0))

(Т ‘ошибка))

ПредложениеIF.

(IF условието-форма иначе-форма)

(IF (> x 0)(SETQ y (+ y x)) (SETQ y (- y x)))

Если выполняетсяусловие (т. е.х>0),то к значениюyприбавляетсязначение х,иначе(x

Можно использоватьформу WHEN.

(WHEN условиеформа1 форма2... )

ВыбирающеепредложениеCASE^

(CASEключ

(список-ключей1m11 m12 ...)

(список-ключей2m21 m22... )

....)

Сначала вычисляетсязначение ключевойформы - ключ.Затем его сравниваютс элементамисписка-ключейi.Когда в спискенайдено значениеключевой формы,начинают вычислятьсясоответствующиеформы mi1,mi2, ... . Значениепоследнейвозвращаетсяв качествезначения всегопредложенияCASE.

_(SETQ ключ3) р3

_(CASE ключ

(1 ‘one)

(2 ‘(one + one)‘two)

(3‘(two + one) ‘three) рthree

4.Циклическиевычисления.

ПредложениеDO.

(DO ((var1знач1 шаг1) (var2знач2 шаг2) ...)

(условие-окончанияформа11 форма12...)

форма21 форма22...)

Первый аргументописываетвнутренниепеременныеvar1, var2, ..., ихначальныезначения - знач1,знач2, ... и формыобновления- шаг1, шаг2, ....

Вначале вычисленияпредложенияDOIвнутреннимпеременнымприсваиваютсяначальныезначения, еслизначения неприсваиваются,то по умолчаниюпеременнымприсваиваетсяNIL.Затем проверяетсяусловие-окончания.Если оно действительно,то последовательновыполняютсяформы1iи значениепоследнейвозвращаетсяв качествезначения всегопредложенияDO, иначепоследовательновычисляютсяформы2i.

На следующемцикле переменнымvari одновременноприсваиваютсязначения форм- шагi,вычисляемыхв текущем контексте,проверяетсяусловие-окончанияи т. д.

_(DO ((x 5 (+ x 1))(y 8 (+ y 2)) (рез 0))

((

(SETQ рез(+ рез xy))

5.Передачауправления.

На Лиспе можнописать программыи в обычномоператорномстиле с использованиемпередачи управления.Однако во многихсистемах нерекомендуетсяиспользоватьэти предложения,так как их можнозаменить другимипредложениями(например DO)и, как правило,в более понятнойформе. Но мырассмотримпредложенияпередачи управления,хотя использоватьих не следует.

(PROG (m1 m2 ...mn)

оператор1

оператор2

...

операторm)

Перечисленныев начале формыпеременныеmiявляются локальнымистатическимипеременнымиформы, которыеможно использоватьдля храненияпромежуточныхрезультатов.Если переменныхнет, то на местесписка переменныхнужно ставитьNIL. Если какая-нибудьформа операторiявляется символомили целым числом,то это меткаперехода. Натакую меткуможно передатьуправлениеоператоромGO:

(GOметка)

GO невычисляетзначение своего«аргумента».

Кроме этого,в PROG-механизмвходит операторокончаниявычисленияи возвратазначения:

(RETURNрезультат)

ОператорыпредложенияPROG вычисляютсяслева направо(сверху вниз),пропуская меткиперехода. ОператорRETURN прекращаетвыполнениепредложенияPROG;в качествезначения всегопредложениявозвращаетсязначение аргументаоператораPROG. Если во времявычисленияоператор RETURNне встретился,то значениемPROG послевычисленияего последнегооператорастанет NIL.

После вычислениязначения формысвязи программныхпеременныхисчезают.

6.Заданияк лабораторнойработе.

1. Запишите следующиелямбда-вызовыс использованиемформы LETи вычислитеих на машине:

a) ((LAMBDA (x y) (LIST x y)

‘(+ 12) ‘c);

b) ((LAMBDA (x y) ((LAMBDA (z) (LIST xy z)) ‘c)

‘a‘b);

c) ((LAMBDA (x y) (LIST x y))

((LAMBDA(z) z) ‘a)

‘b).

2. Напишите спомощью композицииусловных выраженийфункции отчетырех аргументовAND4(x1 x2 x3 x4)и OR4(x1 x2x3 x4), совпадающиес функциямиAND иOR от четырехаргументов.

3. Пусть L1и L2- списки. Напишитефункцию, котораявозвращалабы T,если N-ыедва элементаэтих функцийсоответственноравны другдругу, и NILв противномслучае.

4. Написать условноевыражение(используяCOND), которое:

1. дает NIL,еслиL атом, иT в противномслучае;

2. выдает длясписка L,состоящегоиз трех элементов,первый из этихтрех, которыйявляется атомом,или список,если в спискенет элементоватомов.

5. С помощьюпредложенийCONDили CASEопределитефункцию, котораявозвращаетв качествезначения столицузаданногоаргументомгосударства.

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

7. Запрограммируйтес помощью предложенияDOфункцию факториал.

8. Запишите спомощью предложенияPROG функцию(аналог встроеннойфункции LENGTH),которая возвращаетв качествезначения длинусписка (количествоэлементов наверхнем уровне).

9. Используяфункцию COND,напишите функцию,которая спрашиваету пользователяФИО двух студентовиз группы (списокгруппы составленраньше) длякоторых:

а) сравниваетгод рожденияи выдает результат(кто старше иличто они ровесники);

б) сравниваетсредний бали выдает сообщениео результатахсравнения;

с) проверяетродственныесвязи (еслиодни и те жеродители, тоони родственники)и выдает обэтом сообщение.

10. Напишите подобныефункции, но ужеиспользуяфункцию IF.

Для двух последнихзаданий выводинформацииосуществитьпри помощьюфункций PRINT,PRIN1, PRINC.

Center - находитсреднее из трехчисел:

(DEFUN center (x yz)

(COND ((>x y) (IF (

(PRINT «среднее(1)»))

(IF(> y z) (PROGN (PRINT y)

(TERPRI)

(PRINT«среднее(2)»))

(PROGN (PRIN1 z)

(PRIN1«среднее(3)»)))))

((

(TERPRI)

(PRIN1 «среднее(4)»))

(IF(> x z) (PROGN(PRINC x)

(PRINC«среднее(5)»))

(PROGN (PRINC z)

(TERPRI)

(PRINC«среднее(6)»)))))

(T(PRINC «ошибкаввода»))))

7.Вопросы.

1. Длячего используетсяпредложениеLET?

2. Вчем его отличиеот предложенияLET*?

3. Чемразличаютсяфункции CONDиIF?

4. Каковывозвращаемыеими значения?

5. Чемразличаютсяфункции PROG1и PROGN?

6. Почемуне желательноиспользоватьоператорыпередачи управления?Чем их можнозаменить?

Лабораторнаяработа №4.

Тема: Рекурсияв Лиспе. Функционалыи макросы.

Цель: Изучитьосновы программированияс применениемрекурсии. Научитьсяработать сфункционаламии макросами.

1. Рекурсия.Различные формырекурсии.

2. Применяющиефункционалы.

3. Отображающиефункционалы.

4. Макросы.

5. Задание клабораторнойработе.

6. Вопросы.

1.Рекурсия.Различные формырекурсии.

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

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

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

Рассмотримследующие формырекурсии:

• простая рекурсия;

• параллельнаярекурсия;

• взаимная рекурсия.

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

Для примеранапишем функциювычислениячисел Фибоначчи(F(1)=1; F(2)=1;F(n)=F(n-1)+F(n-2) приn>2):

(DEFUN FIB (N)

(IF (> N 0)

(IF(OR N=1 N=2) 1

(+(FIB (- N 1)) (FIB (- N 2))))

‘ОШИБКА_ВВОДА))

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

(DEFUN f ...

...(g ... (f ...) (f ...)...)

...)

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

(DEFUN PREOBR (L)

(COND

((NULL L)NIL)

((ATOM L)(CONS (CAR L) NIL))

(T (APPEND

(PREOBR(CAR L))

(PREOBR(CDR L))))))

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

(DEFUN f ...

...(g ...) ...)

(DEFUN g ...

...(f ...) ...)

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

(DEFUN obr (l)

(COND ((ATOM l) l)

(T (per l nil))))

(DEFUN per (l res)

(COND ((NULL l) res)

(T (per (CDR l)

(CONS (obr(CAR l)) res)))))

2.Применяющиефункционалы.

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

APPLY

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

(APPLY fnсписок)

_(SETQ a ‘+)р+

_(APPLYa ‘(1 2 3)) р6

_(APPLY ‘+‘(4 5 6)) р15

FUNCALL.

ФункционалFUNCALLпо своему действиюаналогиченAPPLY, но аргументыдля вызываемойон принимаетне списком, апо отдельности:

(FUNCALL fn x1 x2... xn)

_(FUNCALL ‘+4 5 6) р15

FUNCALLи APPLYпозволяютзадавать вычисления(функцию) произвольнойформой, например,как в вызовефункции, илисимволом, значениемкоторого являетсяфункциональныйобъект. Такимобразом появляетсявозможностьиспользоватьсинонимы именифункции. С другойстороны, имяфункции можноиспользоватькак обыкновеннуюпеременную,например дляхранения другойфункции (имениили лямбда-выражения),и эти два смысла(значение иопределение)не будут мешатьдруг другу:

_(SETQ list ‘+)р+

_(FUNCALL list 12) р3

_(LIST 1 2) р(1 2)

3.Отображающиефункционалы.

Отображающиеили MAP-функционалыявляются функциями,которые являютсяфункциями,которые некоторымобразом отображаютсписок (последовательность)в новую последовательностьили порождаютпобочный эффект,связанный сэтой последовательностью.Каждая из нихимеет болеедвух аргументов,значениемпервого должнобыть имя определеннойранее или базовойфункции, илилямбда-выражение,вызываемоеMAP-функциейитерационно,а остальныеаргументыслужат длязадания аргументовна каждой итерации.Естественно,что количествоаргументовв обращениик MAP-функциидолжно бытьсогласованос предусмотреннымколичествомаргументову аргумента-функции.Различие междувсеми MAP-функциямисостоит в правилахформированиявозвращаемогозначения имеханизмевыбора аргументовитерирующейфункции накаждом шаге.

Рассмотримосновные типыMAP-функций.

MAPCAR.

Значение этойфункции вычисляетсяпутем примененияфункции fnк последовательнымэлементам xiсписка, являющегосявторым аргументомфункции. Напримерв случае одногосписка получаетсяследующеевыражение:

(MAPCARfn ‘(x1 x2 ... xn))

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

_(MAPCAR ‘LISTP‘((f) h k (i u)) р(T NIL NIL T)

_(SETQ x ‘(ab c)) р(a b c)

_(MAPCAR ‘CONSx ‘(1 2 3)) р((a . 1) (b . 2) (c . 3))

MAPLIST.

MAPLIST действуетподобно MAPCAR,но действияосуществляетне над элементамисписка, а надпоследовательнымиCDRэтого списка.

_(MAPLIST ‘LIST‘((f) h k (i u)) р(T T T T)

_(MAPLIST ‘CONS‘(a b c) ‘(1 2 3)) р(((a b c) 1 2 3) ((b c) 2 3) ((c ) 3))

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

Функции MAPCANи MAPCONявляются аналогамифункций MAPCARи MAPLIST.Отличие состоитв том, что MAPCANи MAPCONне строят, используяLIST,новый списокиз результатов,а объединяютсписки, являющиесярезультатами,в один список.

4.Макросы.

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

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

(DEFMACRO имялямбда-списоктело)

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

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

_(DEFMACRO setqq (x y)

(LIST‘SETQ x (LIST ‘QUOTE y))) рsetqq

_(setqq a (b c)) р(b c)

_a р(b c)

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

5.Заданияк лабораторнойработе.

1. Напишитерекурсивнуюфункцию, определяющуюсколько разфункция FIBвызывает самусебя. Очевидно,что FIB(1)и FIB(2)не вызываютфункциюFIB.

2. Напишитефункцию длявычисленияполиномовЛежандра (P0(x)=1,P1(x)=x, Pn+1(x)= ((2*n+1)*x*Pn(x)-n*Pn-1(x))/(n+1) приn>1).

3. Напишитефункцию:

1. вычисляющуючисло атомовна верхнемуровне списка(Для списка (ав ((а) с) е) оно равнотрем.);

2. определяющуючисло подсписковна верхнемуровне списка;

3. вычисляющуюполное числоподсписков,входящих вданный списокна любом уровне.

4. Напишитефункцию:

1. от двух аргументовX иN,которая создаетсписок изN раз повторенныхэлементовX;

2. удаляющуюповторныевхожденияэлементов всписок;

3. которая изданного спискастроит списоксписков егоэлементов,например, (ab) р((a) (b));

4. вычисляющуюмаксимальныйуровень вложенияподсписковв списке;

5. единственнымаргументомкоторой являлсябы список списков,объединяющуювсе эти спискив один;

6. зависящую оттрех аргументовX, N иV, добавляющуюX на N-еместо в списокV.

5. Напишитефункцию:

1. аналогичнуюфункции SUBST,но в которойтретий аргументWобязательнодолжен бытьсписком;

2. которая должнапроизводитьзамены Xна Yтолько на верхнемуровнеW;

3. заменяющуюY начисло, равноеглубине вложенияY вW, напримерY=A,W=((A B) A (C (A (A D)))) р((2 B) 1 (C (3 (4 D))));

4. аналогичнуюфункции SUBST,но производящуювзаимную заменуX наY, т. е.X рY, YрX.

6. Вычислитезначения следующихвызовов:

1. (APPLY‘LIST ‘(a b));

2. (FUNCALL‘LIST ‘(a b));

3. (FUNCALL‘APPLY ‘LIST ‘(a b));

4. (FUNCALL‘LIST ‘APPLY ‘(a b);

7. Определитефункционал(A-APPLY f x),который применяеткаждую функциюfiсписка

f = (f1 f2 ... fn)

к соответствующемуэлементу xiсписка

x = (x1 x2 ... xn)

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

8. Определитефункциональныйпредикат (КАЖДЫЙпред список),который истиненв том и тольков том случае,когда, являющийсяфункциональнымаргументомпредикат предистинен длявсех элементовсписка список.

9. Определитефункциональныйпредикат (НЕКОТОРЫЙпред список),который истинен,когда предикатистинен хотябы для одногоэлемента списка.

10. ОпределитеFUNCALLчерез функционалAPPLY.

11. Определитефункционал(MAPLIST fn список)для одногосписочногоаргумента.

12. Определитемакрос, которыйвозвращаетсвой вызов.

13. Определителисповскуюформу (IFусловиеp q) в виде макроса.

Примеры написанияфункций.

;Subst - заменяетвсе вхожденияY вW наX.

(DEFUNsubst (x y w)

(COND((NULL w) NIL) ;проверкана окончаниесписка

((EQUAL ‘y ‘w)x)

((ATOM ‘w) w) ;

(t(CONS (subst x y (car w)) ;поискв глубину

(substx y (cdr w)))))) ;поиск вширину

;COMPARE1 - сравнениес образцом

(defun compare1 (p d)

(cond ((and (null p) (null d)) t) ;исчерпалисьсписки?

((or (null p) (null d)) nil) ;одинаковадлина списков?

((or (equal1 (car p) '&) ;присутствуетв образце атом&

(equal1 (car p) (car d))) ;или головысписков равны

(compare1(cdr p) (cdr d))) ;& сопоставимс любым атомом

((equal1 (car p) '*) ;присутствуетв образце атом*

(cond ((compare1 (cdr p) d)) ;* ни с чемне сопоставима

((compare1 (cdr p) (cdr d))) ;* сопоставимас одним атомом

((compare1 p (cdr d))))))) ;* сопоставимас несколь ;кими атомами

6. Вопросы.

1. Что такоерекурсия?

2. Назовитедостоинстваее использования?

3. Что такоефункционал?

4. Назовитеособенностиприменяющихи отображающихфункционалов?

5. Для чего онииспользуются?

6. Что такое макрос?

7. Когда их используют?

Лабораторнаяработа №5.

Тема: Типыданных и средстваработы с ними.Представлениезнаний.

Цель: Изучитьтипы данных,используемыев MuLisp,а так же научитьсяприменять ихв программах.

1. Точечная нотация.

2. Структурированныетипы данных.

3. Представлениезнаний.

4. Задания клабораторнойработе.

5. Вопросы.

1. Точечнаянотация.

В Лиспе существуетпонятие точечнойпары. Названиеточечной парыпроисходитиз использованнойв ее записиточечной нотации,в которой дляразделенияполей CARи CDRиспользуетсявыделеннаяпробеламиточка. Базовыефункции CARи CDRдействуютсовершенносимметрично.

_(CONS ‘a ‘d)р(a . d)

_(CAR ‘(a .b)) рa

_(CDR ‘(a .(b . c))) р(b . c)

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

(a1 a2 ... an) у(a1 . (a2 . ...(an . nil)... ))

_(a b c (d e)) у(a . (b . (c . ((d . (e . nil)) . nil))))

Признакомсписка здесьслужит NILв полеCDR последнегоэлемента списка,символизирующийего окончание.

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

2. Структурированныетипы данных.

Списки (ассоциативные).

Ассоциативныйсписок илипросто а-список- состоит източечных пар,поэтому еготакже называютсписком пар.

((a1 . t1) (a2 .t2) ... (an . tn))

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

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

PAIRLIS.

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

(PAIRLIS ключиданные а-список)

_(SETQ спис‘(один. Иванов)) р(один . Иванов)

_(SETQ спис

(PAIRLIS‘(три два)‘(ПетровСидоров)

спис)) р((три . Петров)(два . Сидоров)(один . Иванов))

ASSOC.

Ассоциативныйсписок можносчитать отображениемиз множестваключей в множествозначений. Данныеможно получитьс помощью функции

(ASSOCключ а-список)

которая ищетв списке парданные, соответствующиеключу, сравниваяискомый ключс ключами парслева направо.

_(ASSOC ‘триспис) р(три . Петров)

ACONS.

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

(ACONS x yа-список)

Поскольку ASSOCпросматриваетсписок слеванаправо и доходитлишь до первойпары с искомымключом, то болеестарые парыкак бы остаютсяв тени болееновых.

Строки.

Строка состоитиз последовательностизнаков. В строкезнаки записываютсяв последовательностидруг за другом,для ограничениякоторой с обеихсторон в качествеограничителяиспользуетсязнак «».

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

CHAR.

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

(CHAR строкаn)

(CHAR «строка»0) р \с ;индексацияначинаетсяс 0

Сравнениестрок.

(STRING= строка1строка2)

(STRING

(STRING>строка1 строка2)

(STRING/=строка1 строка2)

Массивы.

Для работы смассивами вMuLispнеобходимозагрузить файлARRAY.LSP.

Массивы создаютсяформой:

(MAKE-ARRAY (n1 n2... nN) режимы)

Функция возвращаетв качествезначения новыйобъект - массив.n1, n2, ... nN- целые числа,их количествоN отражаетразмерностьмассива, а значения- размер по каждойразмерности.Необязательнымиаргументамиможно задатьтип элементовмассива, указатьих начальныезначения илипридать самомумассиву динамическийразмер. Общийразмер массивав этом случаезнать и закреплятьне обязательно.

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

(ARREF массивn1 n2 ...nN)

n1,n2,...,nN - координаты,или индексы,элемента, накоторый ссылаются.В качествефункции присваиванияиспользуетсяобобщеннаяфункция присваиванияSETF.

_(SETQ мас(MAKE-ARRAY ‘(54)

:ELEMENT-TYPE ‘ATOM

:INITIAL-ELEMENTA)) р(ARRAY ((AA A A) ... (A A A A) (5 6)))

_(SETF (AREF мас01) B) рB

_маср(ARRAY ((AB A A) ... (A A A A )))

Структуры.

Для объединенияосновных типовданных (чисел,символов, строк,массивов) вкомплексы,отображающиепредметы, фактыиспользуетсясоставной тип,который называетсяструктурами.

Определениеструктурноготипа осуществляетсяс помощью макросаDEFSTRUCT,формой которогоявляется

(DEFSTRUCTкласс-структур

поле1

поле2

...)

Определимструктурныйтип БАЗА состоящийиз компонентПРОФИЛЬ, ПЛОЩи ВМЕСТИМ:

_(DEFSTRUCTбаза

профильплощ вместим)рБАЗА

Для каждогонового типаданных генерируетсяначинающаясяс MAKE-функция созданияструктурыданного типа.Например объекттипа БАЗА можносоздать и присвоитьпеременнойБАЗА1 следующимвызовом:

_(SETQ БАЗА1(MAKE-БАЗА))

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

Вызов MAKE-БАЗАвозвращаетв качествезначения созданнуюструктуру.

Для копированияструктурыгенерируетсяфункция, начинающаясяс COPY-(COPY-БАЗА).

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

_(БАЗА-ПРОФИЛЬx)

Вызов возвращаетзначение поляПРОФИЛЬ дляБАЗЫ, задаваемойструктуройx.

Для присваиваниязначений полямструктурыиспользуетсяобобщеннаяфункция присваиванияSETF:

_(SETF(БАЗА-ПРОФИЛЬБАЗА1) ОВОЩ) рОВОЩ

3. Представлениезнаний.

Продукционныесистемы

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

«ЕСЛИ ,ТО »

Условия и следствия- это простыепредложенияестественногоязыка. Такиеформализмыназываютпродукционными.Эти правилапохожи на условныеоператорыIF-THEN языков программирования, однако совершеннопо другомуинтерпретируются.

(ЕСЛИ на лампочкуподано напряжение

и лампочкане горит

то лампочкаперегорела)

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

Фреймы.

Эточастный случайсемантическихсетей. Это методпредставлениязнаний, которыйсвязывает свойства сузлами , представляющимипонятия и объекты.Свойства описываютсяатрибутами(называемымислотами) и ихзначениями.

[f( , , ...)]

гдеf - имяфрейма; - слот; v- имя слота;g - его значение.

Использованиефреймов с ихатрибутамии взаимосвязямипозволяетхранить знанияо предметной области вструктурированном виде, представлятьв БЗ абстракциии аналогии.Система знанийпредставляетсяв виде сети подфреймом илисубфреймом.Каждый из фреймовотражает определенныесвойства, понятия,т. е. позволяетудовлетворятьтребованиюструктурированностии связности.

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

Одной из важнейшихконцепцийформализмафреймов являетсянаследование.Можно датьуказание, чтоесли значениеслота в одномиз фреймов незадается, тофрейм долженунаследоватьумалчивамоезначение этогослота из фреймаболее высокогоуровня. Наследованиефреймами значенийслотов будетосуществлятьсяв том случае,если в фреймебудет присутствоватьслот РАЗНОВИДНОСТЬ,в котором содержитсяимя другогофрейма.

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

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

Пример1.

В качествепримера представлениязнаний в видепродукцийрассмотримпрограммухранящуюсяв файле EXSIS.LSP.

;EXSIS.LSP -пример представлениязнаний в видепродукций

;определимпредложенияявляющиесяправилами ввиде структур,состоящих изимени правила,условий и выводов,представленныхв виде спискафактов

(defstruct prav имя условиявыводы) ;определениеструктурноготипа PRAV

;создание структуртипа PRAVи присваиваниеих переменнымPRAV1... PRAV5

(setq prav1 (make-prav :имя 'prav1 ;присвоениеполю имя значения

:условия '((живимеет шерсть))

:выводы '((живмлекопитающее))))

(setq prav2 (make-prav :имя 'prav2

:условия '((живкормит детенышеймолоком))

:выводы '((живмлекопитающее))))

(setq prav3 (make-prav :имя 'prav3

:условия '((живимеет перья))

:выводы '((живптица))))

(setq prav4 (make-prav :имя 'prav4

:условия '((живумеет летать)

(жив несетяйца))

:выводы '((живптица))))

(setq prav5 (make-prav :имя 'prav5

:условия '((живест мясо))

:выводы '((живхищник))))

(setq *правила* '(prav1prav2 prav3 prav4 prav5) ;список,хранящий правиласистемы

(defun проверь-правило(правило)

;проверяетприменимо липравило

(подмнож(prav-условия правило)*факты*))

(defun подмнож (подмножмнож)

;проверяет,является лимнож подмнож

(equal подмнож(intersection1 подмножмнож)))

(defun добавь-выводы(правило)

;расширяетсписок фактовправиламивывода

(do ((выводы (prav-выводыправило))) ;инициализацияначальногозначения

((null выводы) *факты*);условие окончания

(if (member (car выводы)*факты*) nil ;проверка- входит «голова»

(progn (prin1 "Согласноправилу:") ;выводовв список фактов

(prin1 (prav-name правило))

(push (car выводы)*факты*)))

(setq выводы (cdr выводы))));шаг изменения

Для проверкиработоспособностипрограммынеобходимовыполнитьследующуюпоследовательностькоманд:

MuLisp-87.comCommon.lsp - Загрузкасистемы

(load structur.lsp)- подключениеприложениядля работы соструктурами

(load rash.lsp)- подключениерасширения,которое мырассмотримпозже

(load exsis.lsp)- подключениетестируемойпрограммы

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

(SETQ *факты*‘(начальныефакты))

где начальныефакты - условияиз какого-либоправила

Пример2.

Пример представлениязнаний с помощьюфреймов. В примереупоминаютсятри фрейма -МЕРОПРИЯТИЕ,СОБРАНИЕ иСОБРАНИЕ1. ФреймМЕРОПРИЯТИЕ- наиболее общий,фрейм СОБРАНИЕ - более конкретный,описывающийвид МЕРОПРИЯТИЯ,а фрейм СОБРАНИЕ1- наиболее уточненныйфрейм, описывающийконкретноеСОБРАНИЕ. ФреймСОБРАНИЕ называетсясубфреймомфрейма МЕРОПРИЯТИЕ,а СОБРАНИЕ1 -субфрейм фреймаСОБРАНИЕ.

(собрание имя фрейма

(разновидность(мероприятие)) имена и значенияслотов

(время (среда14.00)) (умалчиваемыезначения

(место (залзаседаний)) наследуютсясубфреймами)

)

(собрание1

(разновидность(собрание))

(присутствуют((Вася) (Петя)(Маша)))

)

Реализацияфрейм-программына Лиспе.

;EXSIS2 -реализацияфрейм-программына Лиспе.

(setf (get‘собрание‘разновидность)‘мероприятие)

(setf (get‘собрание‘время)‘(среда14.00))

(setf (get‘собрание‘место)‘(залзаседаний))

(setf (get‘собрание1‘разновидность)‘собрание)

(setf (get‘собрание1‘присутствуют)‘((Вася)(Петя) (Маша)))

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

(defunнаследование(фреймимя_слота)

(cond ((get фреймимя_слота));имеется вофрейме данныйслот?

;еслида, то вернутьего значение.

(t (cond((get фрейм‘разновидность);иначе - проверитьналичие

;слотаразновидность.В случае егоприсутствия- рекурсивноприменить

;функциюк верхним фреймам

(наследование(get фрейм‘разновидность)имя_слота))

(t nil)))))

4. Заданияк лабораторнойработе.

1.Переведитеследующиесписочныезаписи в точечные:

1. (w(x));

2. ((w)x);

3. (nilnil nil);

4. (v(w) x (y z));

5. ((vw) (x y) z);

6. (((v)w x) y z).

   
   

2. Переведитеследующиеточечные записив списочные:

1. (a .(b . (c . nil)));

2. ((a. nil) . nil);

3. (nil. (a . nil));

4. (a. ((b . (c . nil)) . ((d . (e . nil)) . nil)));

5. (a. (b . ((c . (d . ((e . nil) . (nil))) . nil)));

6. ((a. (b . nil)) . (c . ((d . nil) . (e . nil)))).

   
   

3. Напишите функцию:

1. оттрех аргументов,аналог встроеннойфункции pairlis,которая строитсписок пар;

2. отдвух аргументов,аналог встроеннойфункции assoc,которая ищетпару, соответствующуюключу.

   
   

4. Напишите функцию,аналог функцииputassocкоторая физическиизменяет а-список(putassoc1ключ данныеа-список).

5. РасширьтевозможностипрограммыEXSIS.LSP:

1. напишитефункцию, пополняющуюбазу знанийновыми знаниями;

2. напишитефункцию, удаляющуюненужные знания;

3. расширьтебазу знаний;

4. напишитеглавную программу,к которой должныбыть подключенывсе ранее написанныефункции (и имеющиесяв EXSIS.LSP),и которая выполнялабы их в диалоговомрежиме.

   
   

6. Подобным образомизмените программуEXSIS1.LSP.

7. Разработайтебазу знанийи правила базызнаний РАСПИСАНИЕЗАНЯТИЙ используя:

1. формализмфреймов;

2. формализмпродукций.

5. Вопросы.

1. В чем особенноститочечной нотации?

2. Назовитеструктурированныетипы данных,их особенности?

3. Способы представлениязнаний?

4. Их достоинстваи недостатки?

Лабораторнаяработа № 6.

Тема: Изучениеучебной версииязыка Лисп -dlisp.Расширениебиблиотекифункций dlisp.

Цель: Ознакомитьсяс учебной версиейЛиспа - dlisp.Изучить еевозможностии особенности.Расширитьбиблиотекуфункций dlisp.

1. Интерфейспользователя.

2. Функции, поддерживаемыеdlisp.

3. Расширениебиблиотекифункций dlisp.

4. Задание клабораторнойработе.

5. Вопросы.

1. Интерфейспользователя.

Запуск системыосуществляетсякомандой:

DLISP.EXE

При загрузкесистемы начинаетработать редактор,он чистит экран,рисует рамкуи выдает наэкран главноеменю:

Файл. Имеетследующиеопции: новый,открыть, сохранить,сохранить как,выход.

Просмотр: экранвывода, экранинтерпретатора.

Редактор.

Поиск: поиск,повторитьпоиск, замена.

Запуск: выполнить,перезапустить,продолжить.

Отладка: шаг,трассировка,контрольнаяточка, очиститьвсе.

Параметры:режим экрана,проверка синтаксиса.

Справка.

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

Редактор работаетс файлами, имеющимирасширениеLSP инаходящимисяв той же директории,что и файл DLISP.EXE

Результатывычисленийвыводятся наспециальныйэкран. Для просмотраэтих результатовнеобходимовыбрать опцию«Просмотр»главного меню,а в ней - «экранвывода». Чтобывернуться назаднеобходимонажать любуюклавишу.

Для переключенияв режим диалогаиспользуютклавиши SHIFT+TAB.

Для повторапредыдущейкоманды используютклавишу F3.

2. Функции,поддерживаемыеdlisp.

Dlisp поддерживаетнесколькоразличных типовданных:

*списки

* символы

* строковыеконстанты

* действительныечисла

* целыечисла

По синтаксисуи соглашениямDlisp близок кMuLispу,более того, онявляется небольшой его частью.

Dlisp содержитнекоторое числозаранее определенных функций.Каждая функциявызываетсякак список,первым элементомкоторого является имя функции,а остальными- аргументыэтой функции(если они есть).Многие из функций - стандартныефункции LISP, ихможно найтив каждом руководствепо языку.

Функции MuLispаподдерживаемыеdlispоми определенныенами в предыдущихлабораторныхработах.

(+ ...)

(- ...)

(* ...)

(/ ...)

(= ...)

(/= )

( ...)

( ...)

(> ...)

(>= ...)

(and ...)

(atom )

(boundp )

(car )

(cdr )

(cond ( ...)...)

(cons )

(defun ...)

(eq )

(if [])

(lambda ...)

(list ...)

(listp )

(mapcar ...)

(not )

(null )

(numberp )

(or ...)

(princ [])

(print [])

(progn ...)

(quote )

(read )

(set )

(setq []...)

(while ...)

(zerop )

Функции dlispане используемыеMuLispом.

(cos )

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

(cos 0.0) возвращает 1.000000

(cos pi) возвращает -1.000000

(sin )

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

(sin 1.0) возвращает 0.841471

(sin 0.0) возвращает 0.000000

(min ...)

Эта функция возвращает наименьшее из заданных. Каждоеможет бытьдействительнымили целым.

(nth )

Эта функциявозвращает"энный" элемент, где - номер элемента(ноль - первыйэлемент). Если больше, чемномер последнегоэлемента ,возвращаетсяnil. Например:

(nth 3 '(a b c d e)) возвращаетD

(nth 0 '(a b c d e)) возвращаетA

(nth 5 '(a b c d e)) возвращаетnil

(strcat ...)

Эта функция возвращает строку, которая является результатомсцеплениястроки1>, и т.д. Например:

(strcat "a" "bout") возвращает"about"

(strcat "a" "b" "c") возвращает"abc"

(strcat "a" "" "c") возвращает"ac"

(strlen )

Эта функция возвращает длину в символахстроковойконстанты какцелую величину.Например:

(stalen "abcd") возвращает4

(stalen "ab") возвращает2

(stalen "") возвращает0

(subst )

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

(setq sample '(a b (c d) b))

тогда:

(subst 'qq 'b sample) возвращает(A QQ (C D) QQ)

(subst 'qq 'z sample) возвращает(A B (C D) B)

(subst 'qq '(c d) sample) возвращает(A B QQ B)

(subst '(qq 'rr) '(c d) sample) возвращает (A B (QQ RR) B)

(subst '(qq 'rr) 'z sample) возвращает(A B (C D) B)

В сочетаниис функциейASSOC, SUBST обеспечиваетудобный способзамены величины,найденной поключу в структурированномсписке. Например,дано:

(stq who '((ferst john) (mid q) (last public)))

тогда:

(setq old (assoc 'first who)) возвращает(FIRST JOHN)

(setq new '(first j)) возвращает(FIRST J)

(setq new old who) возвращает((FIRST J) (MID Q) (LAST PUBLIC))

(type )

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

REAL числа с плавающейзапятой

STR строковыеконстанты

INT целые величины

SYM символы

LIST списки (ифункции пользователя)

3. Расширениебиблиотекифункций dlisp.

Основные принципыпрограммированияна dlispте же, что и вMuLisp,при этом сохраняетсяи синтаксисMuLispа.

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

Пример расширениябиблиотекифункций dlispасодержитсяв файле rash.lsp.Для его запусканеобходимовыполнитьследующуюпоследовательностькоманд:

MuLisp87.com Common.lsp

(load rash.lsp)

;File rash.lsp

;(Приложениек учебной версииязыка Лиспdlisp).

;Содержит функции,расширяющиебиблиотекуdlisp Лиспа.

;Функция APPEND1 соединяетдва списка водин

(defun append1 (l p)

(if (null l) p ;L пуст - вернутьP (условие окончания),

(cons (car l) ;иначе - создатьсписок,

(append1 (cdr l) p)))) ;используярекурсию.

;EQUAL1 - логическаяидентичностьобъектов(параллельнаярекурсия)

(defun equal1 (u v)

(cond ((null u) (null v)) ;возвращаетT если U и V пустые

((numberp u) (if (numberp v) (= u v) ; проверка

nil)) ;на идентичность

((numberp v) nil) ; чисел

((atom u) (if (atom v) (eq u v) ;сравнениеатомов

nil))

((atom v) nil)

(t (and (equal1 (car u) (car v)) ; идентичность"голов"

(equal1 (cdr u) (cdr v)))))) ;идентичность"хвостов"

;DELETE1 - удаляет элементX из списка L

(defun delete1 (x l)

(cond ((null l) nil)

((equal1 (car l) x) (delete1 x (cdr l)))

(t (cons (car l) (delete1 x (cdr l)))))) ;ветвьвыполняется

;в случае невыполненияпредыдущих.

;FULLENGTH1 - определяетполную длинусписка L (на всехуровнях)

(defun fullength1 (l)

(cond ((null l) 0) ;для пустогосписка возвращается0

((atom l) 1) ;если L являетсяатомом - возвращается1

(t (+ (fullength1 (car l)) ;подсчетв глубину

(fullength1 (cdr l)))))) ;подсчетв ширину

;DELETELIST1 - удаляет всеэлементы, входящиев список U изсписка V

(defun deletelist1 (u v)

(cond ((null u) v)

(t (delete1 (car u)

(deletelist1 (cdr u) v)))))

;MEMBER1 - проверяетвхождениеэлемента U всписок V на верхнемуровне

(defun member1 (u v)

(cond ((null v) nil)

((equal1 u (car v)) v)

(t (member1 u (cdr v)))))

;Вслучае присутствияS-выраженияU в спискеV функциявозвращаетостаток спискаV, начинающийсяс U,в противномслучае результатомвычисленияявляется NIL.

;INTERSECTION1 - вычисляетсписок общихэлементов двухсписков

(defun intersection1 (u v)

(cond ((null u) nil)

((member1 (car u) v);проверкана вхождение"головы" сп.U в сп. V

(cons (car u) (intersection1 (cdr u) v)));созданиесписка

(t (intersection1 (cdr u) v))));ненужныеэлементыотбрасываются

;UNION1 - объединяетдва списка, нов отличие отAPPEND1,

;в результирующийсписок не добавляютсяповторяющиесяэлементы

(defun union1 (u v)

(cond ((null u) v)

((member1 (car u) v) ;отсеивание

(union1 (cdr u) v)) ; ненужныхэлементов

(t (cons (car u)

(union1 (cdr u) v)))))

;COPY-LIST1 - копируетверхний уровеньсписка

(defun copy-list1 (l)

(cond ((null l) nil)

(t (cons (car l)

(copy-list1 (cdr l))))))

;COPY_TREE1 - копируетсписочнуюструктуру

(defun copy-tree1 (l)

(cond ((null l) nil)

((atom l) l)

(t (cons (copy-tree1 (car l))

(copy-tree1 (cdr l))))))

;ADJOIN1 - добавляетэлемент к списку

(defun adjoin1 (x l)

(cond ((null l) nil)

((atom l) (cons x ;если L атом,то он преобразуетсяв список,

(cons l nil))) ;а затем кнему добавляетсяX

(t (cons x l))))

;SET-DIFFERENCE1 - находитразность двухсписков

(defun set-difference1 (w e)

(cond ((null w) nil)

((member1 (car w) e) ;отбрасываютсяненужные

(set-difference1 (cdr w) e)) ;элементы

(t (cons (car w)

(set-difference1 (cdr w) e)))))

;COMPARE1 - сравнениес образцом

(defun compare1 (p d)

(cond ((and (null p) (null d)) t) ;исчерпалисьсписки?

((or (null p) (null d)) nil) ;одинаковадлина списков?

((or (equal1 (car p) '&) ;присутствуетв образце атом&

(equal1 (car p) (car d))) ;или головысписков равны

(compare1 (cdr p) (cdr d))) ;& сопоставимс любым атомом

((equal1 (car p) '*) ;присутствуетв образце атом*

(cond ((compare1 (cdr p) d)) ;* ни с чемне сопоставима

((compare1 (cdr p) (cdr d))) ;* сопоставимас одним атомом

((compare1 p (cdr d))))))) ;* сопоставимас несколькими

;атомами

;SUBSTITUTE1 - замена всписке L атомаS на атом N

(defun substitute1 (n s l)

(cond ((null l) nil)

((atom (car l))

(cond ((equal1 s (car l))

(cons n (substitute1 n s (cdr l))))

(t (cons (car l) (substitute1 n s (cdr l))))))

(t (cons (substitute1 n s (car l))

(substitute1 n s (cdr l))))))

;DELETE-DUPLICATES1 - удалениеповторяющихсяэлементов

(defun delete-duplicates1 (l)

(cond ((null l) nil)

((member1 (car l) (cdr l))

(delete-duplicates1 (cdr l)))

(t (cons (car l) (delete-duplicates1 (cdr l))))))

;ATOMLIST1 - проверкана одноуровневыйсписок

(defun atomlist1 (l)

(cond ((null l) t)

((listp (car l)) nil)

(t (atomlist1 (cdr l)))))

;REVERSE1- обращает верхнийуровень списка

(DEFUNREVERSE1 (l)

(COND((NULL l ) NIL)

(T (APPEND1(REVERSE1 (CDR l))

(CONS(CAR l) NIL)))))

4. Заданиек лабораторнойработе.

Напишите функцию,аналог системнойфункции Лиспа:

1. а) (1+ )Результатфункции - ,увеличенноена единицу.

в) (1- ) Результатфункции - ,уменьшенноена единицу.

2. а) (incfпамять приращение)Добавлениеприращенияк числу в памяти.

в) (decfпамять приращение)Вычитаниеприращенияиз числа в памяти.

3. (expt ) Этафункция возвращает , возведенное в указанную. Если оба аргументацелые, то результат- целое число.В любом другомслучае, результат- действительноечисло.

4. (gcd )Функция возвращает наибольший общий делитель и . и должны бытьцелыми.

5. а) (first),second,third, и т. д. возвращающиесоответственнопервый, второй,третий, и т. д.элемент списка.

в) (last )Эта функциявозвращаетпоследний элемент списка. недолжен бытьравен nil. LAST возвращаетлибо атом либосписок.

6. а) (max ...) Этафункция возвращаетнаибольшееиз заданныхчисел.

в) (min...) Эта функциявозвращаетнаименьшееиз заданныхчисел.

7. а) (evenp)Проверяет,четное ли число.Она возвращаетT -если числочетное и NIL - в противномслучае.

в) (oddrp)Эта функция- противоположнаяпо действиюфункции evenp.

8. которая сортируетчисла:

а) по возрастанию.

в) по убыванию.

9. предикат - которыйопределяет:

а) числа с плавающейзапятой.

в) целые числа.

г) строковыеконстанты.

д) символы.

е) списки.

10. зависящуюот одного аргумента,которая генерируетвсе циклическиеперестановкисписка.

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

а) встречающихсяв нем более 1,2, ... раз.

в) встречающихсяв нем не менее2, 3, ... раз.

16. S. Запишитевсе функции,написанныевами, в одинфайл. Для отладкипрограммыиспользуйтевстроенныесредства dlispа.

    
    

5. Вопросы.

1. Какие способытестированияпрограммпредусмотреныв dlisp?

2. В чем их различия?

3. Какие функциипредусмотреныдля работы состроковымиконстантамив dlisp?

4. Назовите ихосновные особенности?

Списокиспользованнойлитературы.

1. Э.Чювенен, И. Сеппянен

«Мир Лиспа»

Москва «Мир»1990 г. Т.1

2. Э. Чювенен,И. Сеппянен

«Мир Лиспа»

Москва «Мир»1990 г. Т.2

3. «Программированиена языке R-Lisp»

Москва «Радиои связь» 1991 г.

4. У.Маурер

«Введениев программированиена языке Лисп»

Москва «Мир»1976 г.

5. П. Уинстон

«Искусственныйинтеллект»

Москва «Мир»1980 г.

6. «Искусственныйинтеллектприменениев интегрированных

производственныхсистемах»

Москва«Машиностроение»1991 г.

7. «Искусственныйинтеллект:

программныеи аппаратныесредства»Справочник.

Москва «Радиои связь» 1990 г. Т.3

8. Дж.Малпас

«Реляционныйязык Прологи его применение»

Москва «Наука»1990 г.

9. И.Братко

«Программированиена языке Прологдля искусственногоинтеллекта»

Москва «Мир»1990 г.

10. П.Грей

«Логика,алгебра и базыданных»

Москва«Машиностроение»1983 г.

11. Л.Н. Преснухин,В. А. Шахнов

«Конструированиеэлектронныхвычислительныхмашин и систем»

Москва «Высшаяшкола» 1986 г.

12. «Основыинженернойпсихологии»

Москва «Высшаяшкола» 1986 г.

1 Литературныйобзор.

1. Краткаяистория развитияискусственногоинтеллекта.

Искусственныйинтеллект (ИИ)- это областьисследований,находящаясяна стыке наук,специалисты,работающиев этой области,пытаются понять,какое поведение,считаетсяразумным (анализ),и создать работающиемодели этогоповедения(синтез). Практическойцелью являетсясоздание методови техники,необходимойдля программирования«разумности»и ее передачивычислительныммашинам (ВМ), ачерез нихвсевозможнымсистемам исредствам.[1]

В 50-х годахисследователив области ИИпытались строитьразумные машины,имитируя мозг.Эти попыткиоказалисьбезуспешнымипо причинеполной непригодностикак аппаратныхтак и программныхсредств.

В 60-х годахпредпринималисьпопытки отыскатьобщие методырешения широкогокласса задач,моделируясложный процессмышления. Разработкауниверсальныхпрограмм оказаласьслишком трудными бесплоднымделом. Чем ширекласс задач,которые можетрешать однапрограмма, тембеднее оказываютсяее возможностипри решенииконкретнойпроблемы.[5]

В начале 70-хгодов специалистыв области ИИсосредоточилисвое вниманиена разработкеметодов и приемовпрограммирования,пригодных длярешения болееспециализированныхзадач: методовпредставления(способы формулированияпроблемы длярешения насредствахвычислительнойтехники (ВТ)) иметодах поиска(способы управленияходом решениятак, чтобы ононе требовалослишком большогообъема памятии времени).

И только вконце 70-х годовбыла принятапринципиальноновая концепция,которая заключаетсяв том, что длясозданияинтеллектуальнойпрограммы еенеобходимоснабдить множествомвысококачественныхспециальныхзнаний о некоторойпредметнойобласти. Развитиеэтого направленияпривело к созданиюэкспертныхсистем (ЭС).[6]

В 80-х годахИИ пережилвторое рождение.Были широкоосознаны егобольшие потенциальныевозможностикак в исследованиях,так и в развитиипроизводства.В рамках новойтехнологиипоявилисьпервые коммерческиепрограммныепродукты. В этовремя сталаразвиватьсяобласть машинногообучения. Доэтих пор перенесениезнаний специалиста-экспертав машиннуюпрограмму былоутомительнойи долгой процедурой.Создание систем,автоматическиулучшающихи расширяющихсвой запасэвристических(не формальных,основанныхна интуитивныхсоображениях)правил - важнейшийэтап в последниегоды. В началедесятилетияв различныхстранах былиначаты крупнейшиев истории обработкиданных национальныеи международныеисследовательскиепроекты, нацеленныена «интеллектуальныеВМ пятогопоколения».[1]

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

• обработкаестественногоязыка;

• экспертныесистемы (ЭС);

• символьныеи алгебраическиевычисления;

• доказательстваи логическоепрограммирование;

• программированиеигр;

• обработкасигналов ираспознаваниеобразов;

• и др.

1.2 ЯзыкипрограммированияИИ.

1.2.1Классификацияязыков и стилейпрограммирования.

Все языкипрограммированияможно разделитьна процедурныеи декларативныеязыки. Подавляющеебольшинствоиспользуемыхв настоящеевремя языковпрограммирования(Си, Паскаль,Бейсик и т. п.)относятся кпроцедурнымязыкам. Наиболеесущественнымиклассамидекларативныхязыков являютсяфункциональные(Лисп, Лого, АПЛи т. п.) и логические(Пролог, Плэнер,Конивер и др.)языки (рис.1).

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

Процедурнаяпрограммасостоит изпоследовательностиоператорови предложений,управляющихпоследовательностьюих выполнения.Типичнымиоператорамиявляются операторыприсваиванияи передачиуправления,операторыввода-выводаи специальныепредложениядля организациициклов. Из нихможно составлятьфрагментыпрограмм иподпрограммы.В основе процедурногопрограммированиялежат взятиезначения какой-топеременной,совершениенад ним действияи сохранениянового значенияс помощью оператораприсваивания,и так до техпор пока небудет получено(и, возможно,напечатано)желаемоеокончательноезначение.[2]

ЯЗЫКИПРОГРАММИРОВАНИЯ

ПРОЦЕДУРНЫЕЯЗЫКИ ДЕКЛАРАТИВНЫЕЯЗЫКИ

Паскаль,Си, Фортран,...

ЛОГИЧЕСКИЕЯЗЫКИ ФУНКЦИОНАЛЬНЫЕЯЗЫКИ

Пролог,Mandala... Лисп, Лого,АРЛ, ...

Рис.1Классификацияязыков программирования

Логическоепрограммирование- это один изподходов кинформатике,при которомв качествеязыка высокогоуровня используетсялогика предикатовпервого порядкав форме фразХорна. Логикапредикатовпервого порядка- это универсальныйабстрактныйязык предназначенныйдля представлениязнаний и длярешения задач.Его можнорассматриватькак общую теориюотношений.Логическоепрограммированиебазируетсяна подмножествелогики предикатовпервого порядка,при этом оноодинаковошироко с нейпо сфере охвата.Логическоепрограммированиедает возможностьпрограммистуописыватьситуацию припомощи формуллогики предикатов,а затем, длявыполнениявыводов из этихформул, применитьавтоматическийрешатель задач(т. е. некоторуюпроцедуру). Прииспользованииязыка логическогопрограммированияосновное вниманиеуделяетсяописанию структурыприкладнойзадачи, а невыработкепредписанийкомпьютеруо том, что емуследует делать.Другие понятияинформатикииз таких областей,как теорияреляционныхбаз данных,программнаяинженерия ипредставлениезнаний, такжеможно описать(и, следовательно,реализовать)с помощью логическихпрограмм.[8].

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

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

«Чистое»функциональноепрограммированиене признаетприсваиванийи передач управления.Разветвлениевычисленийосновано намеханизмеобработкиаргументовусловногопредложения.Повторныевычисленияосуществляютсячерез рекурсию,являющуюсяосновным средствомфункциональногопрограммирования.[1]

2. Сравнительныехарактеристикиязыков ИИ.

На первомэтапе развитияИИ (в конце 50-х- начале 60-х годов)не существовалоязыков и систем,ориентированныхспециальнона областизнаний. Появившиесяк тому времениуниверсальныеязыки программированияказались подходящиминструментомдля созданиялюбых (в томчисле и интеллектуальных) систем, посколькув этих языкахможно выделитьдекларативнуюи процедурнуюкомпоненты.Казалось, чтона этой баземогут бытьинтерпретированылюбые моделии системыпредставлениязнаний. Но сложностьи трудоемкостьтаких интерпретацийоказалисьнастольковелики, чтоприкладныесистемы дляреализациибыли недоступны.Исследованияпоказали, чтопроизводительностьтруда программистаостается постояннойнезависимоот уровняинструментальногоязыка, на которомон работает,а соотношениемежду длинойисходной ирезультирующейпрограмм примерно1:10. Таким образом,использованиеадекватногоинструментальногоязыка повышаетпроизводительностьтруда разработчикасистемы напорядок, и этопри одноступенчатойтрансляции.Языки предназначенныедля программированияинтеллектуальныхсистем содержатиерархические(многоуровневые)трансляторыи увеличиваютпроизводительностьтруда в 100-ни раз.Все это подтверждаетважностьиспользованияадекватныхинструментальныхсредств.[7]

1. Языки обработкисимвольнойинформации.

Лисп.

Язык Лиспбыл разработанв Стэнфордепод руководствомДж. Маккартив начале 60-х годов.По первоначальнымзамыслам ондолжен был0включать нарядусо всеми возможностямиФортрана средстваработы с матрицами,указателямии структурамииз указателейи т. п. Но для такогопроекта нехватило средств.Окончательносформированныепринципы положенныев основу языкаЛисп: использованиеединого списковогопредставлениядля программи данных; применениевыражений дляопределенияфункций; скобочныйсинтаксисязыка.[4]

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

После созданияв начале 70-х годовмощных Лисп-системМаклисп Интерлисппопытки созданияязыков ИИ, отличныхот Лиспа, но натой же основе,сходят на нет.Дальнейшееразвитие языкаидет, с однойстороны, попути его стандартизации(Стандарт-Лисп,Франц-Лисп,Коммон Лисп),а с другой - внаправлениисозданияконцептуальноновых языковдля представленияи манипулированиязнаниями в Лиспсреде. В настоящеевремя Лиспреализованна всех классахЭВМ, начинаяс ПЭВМ и кончаявысоко производительнымивычислительнымисистемами.

Лисп - неединственныйязык, используемыйдля задач ИИ.Уже в середине60-х годов разрабатывалисьязыки, предлагающиедругие концептуальныеосновы. Наиболееважные из нихв области обработкисимвольнойинформации- СНОБОЛ и Рефал.

СНОБОЛ.

Это языкобработкистрок, в рамкахкоторого впервыепоявилась ибыла реализованав достаточнополной мереконцепцияпоиска по образцу.Язык СНОБОЛбыл одной изпервых практическихреализацийразвитойпродукционнойсистемы. Наиболееизвестная иинтереснаяверсия этогоязыка - Снобол-4Здесь техниказадания образцови работа с нимисущественноопередилипотребностипрактики. Посуществу, онтак и остался«фирменным»языком программирования,хотя концепцииСНОБОЛа, безусловно,оказали влияниеи на Лисп, и надругие языкипрограммированиязадач ИИ.

Рефал.

Язык Рефал- алгоритмическийязык рекурсивныхфункций. Он былсоздан Турчинымв качествеметаязыка,предназначенногодля описанияразличных, втом числе иалгоритмических,языков и различныхвидов обработкитаких языков.При этом имелосьв виду и использованиеРефала в качествеметаязыка надсамим собой.Для пользователяэто язык обработкисимвольнойинформации.Поэтому, помимоописания семантикиалгоритмическихязыков, он нашели другие применения.Это выполнениегромоздкиханалитическихвыкладок втеоретическойфизике и прикладнойматематике,интерпретацияи компиляцияязыков программирования,доказательствотеорем, моделированиецеленаправленногоповедения, ав последнеевремя и задачиИИ. Общим длявсех этих примененийявляются сложныепреобразованиянад объектами,определеннымив некоторыхформализованныхязыках.

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

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

Во многихслучаях возникаетнеобходимостьиз программ,написанныхна Рефале, вызыватьпрограммы,написанныена других языках.Это просто, таккак с точкизрения Рефалапервичныефункции (Функции,описанные нена Рефале, нокоторые темне менее можновызывать изпрограмм, написанныхна этом языке.)- это простонекоторыефункции, внешниепо отношениюк данной программе,поэтому, вызываякакую-либофункцию, можнодаже и не знать,что это - первичнаяфункция.

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

Часто бываетудобно разбитьРефал-программуна части, которыемогут обрабатыватьсякомпиляторомРефала независимодруг от друга.Наименьшаячасть Рефал-программы,которая можетбыть обработанакомпиляторомнезависимоот других, называетсямодулем. Результаткомпиляцииисходногомодуля на Рефалепредставляетсобой объектныймодуль, которыйперед исполнениемРефал-программыдолжен бытьобъединен сдругими модулями,полученнымикомпиляциейс Рефала илидругих языковэто объединениевыполняетсяс помощью редакторасвязей и загрузчиков.Детали зависятот используемойОС.

Таким образом,Рефал вобралв себя лучшиечерты наиболееинтересныхязыков обработкисимвольнойинформации60-х годов. В настоящеевремя языкРефал используетсядля автоматизациипостроениятрансляторов,систем аналитическихпреобразований,а также, подобноЛиспу, в качествеинструментальнойсреды для реализацииязыков представлениязнаний.[7]

Пролог.

В начале 70-хгодов появилсяновый языксоставившийконкуренциюЛиспу при реализациисистем, ориентированныхна знания - Пролог.Этот язык недает новыхсверхмощныхсредств программированияпо сравнениюс Лиспом, ноподдерживаетдругую модельорганизациивычислений.Его привлекательностьс практическойточки зрениясостоит в том,что, подобнотому, как Лиспскрыл от программистаустройствопамяти ЭВМ,Пролог позволилему не заботитсяо потоке управленияв программе.[8]

Пролог - европейскийязык, был разработанв Марсельскомуниверситетев 1971 году. Нопопулярностьон стал приобретатьтолько в начале80-х годов. Этосвязано с двумяобстоятельствами:во-первых, былобоснованлогическийбазис этогоязыка и, во-вторых,в японскомпроекте вычислительныхсистем пятогопоколения онбыл выбран вкачестве базовогодля одной изцентральныхкомпонент -машины вывода.

Язык Прологбазируетсяна ограниченномнаборе механизмов,включающихв себя сопоставлениеобразцов, древовидноепредставлениеструктур данныхи автоматическийвозврат. Прологособенно хорошоприспособлендля решениязадач, в которыхфигурируютобъекты и отношениямежду ними.[9]

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

Пролог успешноприменяетсяв таких областяхкак: реляционныебазы данных(язык особеннополезен присоздании интерфейсовреляционныхбаз данных спользователем);автоматическоерешение задач;пониманиеестественногоязыка; реализацияязыков программирования;представлениезнаний; экспертныесистемы и др.задачи ИИ.[9]

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

Пролог программасостоит из двухчастей: базыданных (множествоаксиом) ипоследовательностицелевых утверждений,описывающихв совокупностиотрицаниедоказываемойтеоремы. Главноепринципиальноеотличие интерпретациипрограммы наПрологе отпроцедурыдоказательстватеоремы в исчислениипредикатовпервого порядкасостоит в том,что аксиомыв базе данныхупорядоченыи порядок ихследованиявесьма существенен,так как на этомоснован самалгоритм, реализуемыйПролог-программы.Другое существенноеограничениеПролога в том,что в качествелогическихаксиом используютсяформулы ограниченногокласса - такназываемыедизъюнктыХорна. Однакопри решениимногих практическихзадач этогодостаточнодля адекватногопредставлениязнаний. Во фразахХорна послеединственногозаключенияследует нольи более условий.

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

Смысл программыязыка Прологможет бытьпонят либо спозиций декларативногоподхода, либос позицийпроцедурногоподхода.[8]

Декларативныйсмысл программыопределяет,является лиданная цельистинной (достижимой)и, если да, прикаких значенияхпеременныхона достигается.Он подчеркиваетстатическоесуществованиеотношений.Порядок следованияподцелей вправиле невлияет надекларативныйсмысл этогоправила. Декларативнаямодель болееблизка к семантикелогики предикатов,что делаетПролог эффективнымязыком дляпредставлениязнаний. Однаков декларативноймодели нельзяадекватнопредставитьте фразы, в которыхважен порядокследованияподцелей. Дляпояснениясмысла фразтакого роданеобходимовоспользоватьсяпроцедурноймоделью.

При процедурнойтрактовкеПролог-программыопределяютсяне только логическиесвязи междуголовой предложенияи целями в еготеле, но еще ипорядок, в которомэти цели обрабатываются.Но процедурнаямодель не годитсядля разъяснениясмысла фраз,вызывающихпобочные эффектыуправления,такие как остановкавыполнениязапроса илиудаление фразыиз программы.[9]

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

На эффективностиПролога оченьсильно сказываютсяограниченностьресурсов повремени ипространству.Это связанос неприспособленностьютрадиционнойархитектурывычислительныхмашин для реализациипрологовскогоспособа выполненияпрограмм,предусматривающегодостижениецелей из некоторогосписка. Вызоветли это трудностив практическихприложениях,зависит отзадачи. Факторвремени практическине имеет значения,если пролог-программа,запускаемаяпо несколькораз в день, занимаетодну секунду,а соответствующаяпрограмма надругом языке- 0.1 секунды. Норазница вэффективностистановитсясущественной,если эти двепрограммытребуют 50 и 5 минутсоответственно.

С другойстороны, вомногих областяхпримененияПролога онможет существенносократить времяразработкипрограмм. Программына Прологелегче писать,легче пониматьи отлаживать,чем программы,написанныена традиционныхязыках, т. е. языкПролог привлекателенсвоей простотой.Пролог-программулегко читать,что являетсяфактором,способствующимповышениюпроизводительностипри программированиии увеличениюудобств присопровождениипрограмм. ПосколькуПролог основанна фразах Хорна,исходный текстПролог-программзначительноменее подверженвлиянию машинно-зависимыхособенностей,чем исходныетексты программ,написанныхна других языках.Кроме того вразличныхверсиях языкаПролог проявляетсятенденция кединообразию,так что программу,написаннуюдля одной версии,легко можнопреобразоватьв программудля другойверсии этогоязыка. Крометого Прологпрост в изучении.[8]

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

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

2. Языки программированияинтеллектуальныхрешателей.

Группа языков,которые можноназвать языкамиинтеллектуальныхрешателей, восновномориентированана такую подобластьИИ, как решениепроблем, длякоторой характерны,с одной стороны,достаточнопростые и хорошоформализуемыемодели задач,а с другой -усложненныеметоды поискаих решения.Поэтому основноевнимание в этихязыках былоуделено введениюмощных структуруправления,а не способампредставлениязнаний. Этотакие языкикак Плэнер,Конивер, КюА-4,КюЛисп.

Плэнер.

Этот языкдал толчокмощному языкотворчествув области ИИ.Язык разработанв Массачуссетскомтехнологическоминституте в1967-1971гг. Вначалеэто была надстройканад Лиспом, втаком виде языкреализованна Маклиспепод названиемМикро Плэнер.В дальнейшемПлэнер былсущественнорасширен ипревращен всамостоятельныйязык. В СССР онреализованпод названиемПлэнер-БЭСМи Плэнер-Эльбрус.Этот язык ввелв языки программированиямного новыхидей: автоматическийпоиск с возвратами,поиск данныхпо образцу,вызов процедурпо образцу,дедуктивныйметод и т. д.

В качествесвоего подмножестваПлэнер содержитпрактическивесь Лисп (снекоторымимодификациями)и во многомсохраняет егоспецифическиеособенности.Структураданных (выражений,атомов и списков),синтаксиспрограмм иправила ихвычисленияв Плэнере аналогичнылисповским.Для обработкиданных в Плэнерев основномиспользуютсяте же средства,что и в Лиспе:рекурсивныеи блочные функции.Практическивсе встроенныефункции Лиспа,в том числе ифункция EVAL,включены вПлэнер. Аналогичноопределяютсяновые функции.Как и в Лиспе, с атомами могутбыть связанысписки свойств.

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

Для обработкиданных в Плэнереиспользуютсяне только функции,но и образцыи сопоставители.

Образцыописываютправила анализаи декомпозицииданных и поэтомуих применениеоблегчаетнаписаниепрограмм исокращает ихтексты.

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

РассмотренноеподмножествоПлэнера можноиспользоватьнезависимоот других егочастей: онопредставляетсобой мощныйязык программирования,удобный дляреализацииразличныхсистем символьнойобработки.Остальные частиПлэнера ориентируютего на областьИИ, предоставляясредства дляописания задач(исходных ситуаций,допустимыхопераций, целей),решения которыхдолжна искатьсистема ИИ,реализуемаяна Плэнере, исредства, упрощающиереализациюпроцедур поискарешения этихзадач.

На Плэнереможно программироватьописывая то,что имеетсяи то что надополучить, безявного указания,как это делать.Ответственностьже за поискрешения описываемойзадачи беретна себя встроенныйв язык дедуктивныймеханизм (механизмавтоматическогодостиженияцелей), в основекоторого лежитвызов теоремпо образцу.Однако тольковызова теоремпо образцу недостаточнодля такогомеханизма.Необходиммеханизм перебора,и такой механизм- режим возвратов- введен в язык.

Выполнениепрограммы врежиме возвратовудобно для ееавтора тем, чтоязык берет насебя ответственностьза запоминаниеразвилок иоставшихсяв них альтернатив,за осуществлениевозвратов кним и восстановленияпрежнего состоянияпрограммы - всеэто делаетсяавтоматически.Но такой автоматизмне всегда выгоден,так как в общемслучае он ведетк «слепому»перебору. Иможет оказатьсятак, что привызове теоремнаиболее подходящаяиз них будетвызвана последней,хотя авторпрограммызаранее знаето ее достоинствах.Учитывая этоПлэнер предоставляетсредства управлениярежимом возвратов.[7]

Конивер.

Язык Конивербыл разработанв 1972 году, реализованкак надстройканад языкомМаклисп. Авторыязыка Конивервыступили скритикой некоторыхидей языкаПлэнер. В основномона относиласьк автоматическомурежиму возвратов,который в общемслучае ведетк неэффективными неконтролируемымпрограммам,особенно еслиона составляетсянеквалифицированнымипользователями.Авторы Кониверотказалисьот автоматическогорежима возвратов,считая, чтовстраиватьв язык какие-тофиксированныедисциплиныуправления(кроме простейших- циклов, рекурсий)не следует ичто автор программыдолжен саморганизовыватьнужные емудисциплиныуправления,а для этогоязык долженоткрыватьпользователюсвою структурууправленияи предоставлятьсредства работыс ней. Эта концепциябыла реализованав Конивер следующимобразом.

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

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

Учитываясложностьреализациидисциплинуправления,авторы языкабыли вынужденывключить в негоряд фиксированныхмеханизмовуправления,аналоговпроцедур-развилоки теорем языкаПлэнер. Но вотличии отПлэнера, гдеразрыв междувыбором альтернативыв развилке иее анализом,а в случаенеобходимостивыработкойнеуспеха можетбыть скольугодно велик,в языке Кониверэтот разрывсведен к минимуму.Этим Кониверизбавляетсяот негативныхпоследствийглобальныхвозвратов понеуспеху, когдаприходитсяотменять предыдущуюработу чутьли не всейпрограммы.[7]

3. Языки представлениязнаний.

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

Независимоот реализацииЯПЗ долженотвечать следующимтребованиям:

• наличиепростых и вместес тем достаточномощных средствпредставлениясложно структурированныхи взаимосвязанныхобъектов;

• возможностьотображенияописаний объектовна разные видыпамяти ЭВМ;

• наличиегибких средствуправлениявыводом, учитывающихнеобходимостьструктурированияправил работырешателя;

• «прозрачность»системныхмеханизмовдля программиста,т. е. возможностьих до определенияи переопределенияна уровне входногоязыка;

• возможностьэффективнойреализации,как программной,так и аппаратной;

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

Среди ЯПЗпервого поколения(70-е годы) лишьнекоторыесыграли заметнуюроль в программнойподдержкесистем представлениязнаний (СПЗ).Выделим срединих KRL,FRL, KL-ONE. Характернымичертами этихязыков были:двухуровневоепредставлениеданных, представлениезакономерностейпредметнойобласти и связеймежду понятиямив виде присоединенныхпроцедур,семантическийподход к сопоставлениюобразцов ипоиску по образцу.

KRL.

Один из самыхинтересныхязыков этойгруппы - KRL,в основу которогобыли положеныследующиеконцепции:организациязнаний в видеспециальновыделенныхединиц с присоединеннымиописаниямии процедурами;наличие средствпредставлениямногоаспектногои/или неполногознания об объектах;возможностьописания объектовчерез сопоставлениеих с другимиобъектами сучетом уточняющихописаний; наличиегибкого наборабазовых средствописания стратегийвывода решенийи возможностьих динамическогоизменения.Однако KRLшироко неиспользовалсяв интеллектуальныхсистемах из-занекоторой егогромоздкостии отсутствиясобственныхсредств описанияпроцедур. Какследствие, вKRLактивно использовалсяЛисп. Частонельзя былопонять, имееммы дело с KRL-программойи присоединеннымиЛисп-функциямиили с Лисп-программой,в которой применяетсяKRLкак способпредставленияданных.

FRL.

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

Для всех ЯПЗпо сравнениюс традиционнымиязыками программированияхарактернасущественнобольшая «активность»данных, чтоприводит кстиранию гранеймежду декларативнойи процедурнойкомпонентами.Кроме того,реальные объемыобрабатываемыхданных требуютпри реализацииЯПЗ использованияконцепции базыданных и методов,развитых присоздании СУБД.И, наконец, ЯПЗтяготеют большек режиму интерпретации,чем к компиляции,характернойдля реализацииобычных языковпрограммирования.В области разработкии реализацииЯПЗ можно выделитьтри круга проблем:определениевходных языковСПЗ; выбор выходногоязыка соответствующеготранслятораи собственнопроблемы этапатрансляции.

Входной языкСПЗ должен бытьблизок к языкупредметнойобласти и полексике, и посинтаксису,и по семантике.

От выборавыходного языказависит нетолько эффективность,но и сама возможностьреализацииЯПЗ. Выходнойязык долженотвечать покрайней мереследующимтребованиям:иметь достаточнобольшой наборпримитивовработы с образцами;обладать встроеннымисредствамиэффективнойподдержкирекурсии; иметьгибкие средстваописания потоковуправления.Кроме того, врамках выходногоязыка необходимысредства отображенияданных на основнуюи внешнюю памятьи удобные средстваработы с этимиданными. И, наконец,желательно,чтобы в немимелись достаточноразвитые средстваопределенияновых типовданных.

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

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

RLL.

Это фреймовыйязык представлениязнаний(представительпопулярногов 70-х годах подхода«фреймы доконца», являетсяинструментальнойсредой длясозданияспециализированныхЯПЗ.

Подобно другиминструментальнымсредствам,RLL содержитдва слоя: базисныепримитивы исредства ихкомбинированияна более высокомуровне, чемЛисп. При этомтехнологияконструированияспециальныхЯПЗ в рамкахRLL-средысводится, какправило, кредактированиюуже существующихзаготовок ипоследующемуконвертированиюих в Лисп.

УчитываяпоследовательнуюориентациюRLLна концепциюфреймов, всеструктуры(декларативныеи процедурные),более сложныечем списокзначений, описываютсяздесь в видефрейм-подобныхRLL-элементов.

С помощьюRLL-элементовописываютсяпонятия нетолько предметнойобласти, но исамой RLL-среды(например, слот,механизмнаследования,структурауправленияи т. д.). Заранеена уровнеRLL-интерпретатораили конверторафиксируетсясемантикаограниченногочисла системныхпонятий - этомножества,списки, слотыи др. RLL-элементыимеют явноспецифицированныеродовидовыеотношения,которые такжеявляются системнымипонятиями, ивстроенныймеханизм описанияотношений спомощью многосвязныхсписков.

В RLLимеется и библиотекаудачных управляющихструктур, иопределенныесредстваконструированияиз них решателей,необходимыхдля конкретнойЭС.

Одним изосновных стандартныхмеханизмоввывода решенийв RLLявляется agenda(управляющийсписок с динамическойкоррекциейэлементов).

ART.

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

Входной языксистемы ARTвесьма гибкийи обеспечиваетиспользованиефактов, схем,комбинацийэтих понятийи правил. Декларативнуюкомпонентуэтого ЯПЗ составляютфакты и схемы.По определению,факт включаеттри основныхкомпонента:утверждение,значение истинностии точку зрения.С каждым утверждениемможет бытьсвязано одноиз трех значенийистинностиtrue,false илиunknown,а также определенныесферы егосправедливости,которое и называетсяточкой зрения.Факты описываютсяэкземплярамифреймов. Фреймы-прототипыв ARTпредставляютсясхемами, каждаяиз которыхописываетобъекты и/иликлассы объектовс фиксированнымисвойствами.Механизмынаследованиясвойств приэтом поддерживаютсясамой системой.

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

В полномобъеме ARTпредставляетразработчикуЭС достаточномощные средствапредставлениязнаний, но эффективнов системе ARTмогут работатьтолько квалифицированныеЛисп-программисты,готовые реализоватьв этом языкевсе процедурыподдержки ЯПЗ.

Дальнейшееразвитие ЯПЗсмещается всторону продукций.Вместе с темв настоящеевремя уже редкоудается классифицироватьязыки и системыпредставлениязнаний на шкале«фреймы - продукции- семантическиесети - ...» однозначно.И хотя тот илииной формализмпредставлениязнаний накладываетв большей илименьшей степенисвой отпечатокна соответствующийЯПЗ, современныеязыки и системы,как правило,поддерживаютнесколькоформализмоводновременно.

1.3Особенностидиалектов языкаЛисп.

1. ДиалектыЛиспа.

Маклисп.

Кроме символьнойобработкиМаклисп широкоиспользовалсяв традиционныхчисловых вычислениях,применяемых, например, вобработке речии изображений.Кроме исследователейИИ и разработчиковалгебраическойсистемы Максимана Маклиспоказали влияниеи работы группв МИТ по робототехнике,обработке речии изображений.Исходя из требований,предъявляемыхэтими областями,в Маклисп быливключены новыематематическиетипы данных,такие как матричнаяи битовая обработка,а также широкийнабор арифметическихфункций и средств.Быть может,важнейшая изних - возможностьвычисленийс неограниченнойточностью,основывающаясяна созданныхКнутом (1969) алгоритмах.[2]

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

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

Основноевнимание разработчикиМаклиспасосредоточилина эффективности.Этому служатуказания, уточняющиеспособы обработкиаргументовфункций, а такжеэкранированиеот вмешательствапрограммиставнутреннихмеханизмовсистемы. Засчет этих мерскорость работыМаклиспа в1.5-2.5 раза выше,чем Интерлисп.[7]

Всего в Маклиспеиспользуетсяоколо 400 функций.Самым большимнедостаткомсистемы являетсято, что ее никогдане документировалидолжным образом.Документацияпо этой системеразбросанапо различнымотчетам ируководствам.Маклисп былисследовательскойсистемой и непредназначалсядля обученияи промышленногоиспользования.[2]

муЛисп.

ИнтерпретаторМулисп-85, разработанныйдля ПЭВМ серииIBMPC - удачныйвариант реализациидиалекта языка,включающийсравнительноограниченныйнабор базовыхфункций (около260) и оказавшийсяв следствиеэтого болеепростым дляизучения.

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

Среди других,вероятно, менеесущественных,особенностейсистемы можноуказать нареализациюспециальногомеханизма,позволяющегоне заботитьсяо присваиванииначальныхзначений литеральныматомам, получающихизначальноезначение, равное«печатному»имени самогоатома. Еще однойособенностьюдиалекта являетсявозможностьиспользованияновой синтаксическойконструкции«встроенныйCOND»,существенносокращающейтексты описанийфункций пользователяи применяемойпри записи телфункций илямбда-выражений.[7]

Набор базовыхфункциймуЛисп-интерпретаторавключает рядфункций, обеспечивающихдоступ практическико всем функциямОС ЭВМ черезсоответствующиепрерывания.Наконец, указаннаяЛисп-сис-темаобеспечиваетсябиблиотекамиЛисп-функций,дополняющимибазовый наборфункциями,имеющимисяв диалектахКоммон Лиспи Интерлисп,что облегчаетрешение проблемыпереносимостиисходных текстовпрограммныхмодулей, а такжебиблиотеками,позволяющимивыполнятьманипулированиеокнами на экранедисплея иобрабатыватьуправляющиевоздействиячерез устройствотипа «мышь».В комплектдополнительногопрограммногообеспеченияк интерпретаторувходят интерактивныйредактор текстови простая обучающаясистема, написанныена диалектеязыка муЛисп.[7]

Интерлисп.

Интерлисппоявился в 1972году из ББН-Лиспа.К 1978 году, когдавышло описаниеИнтерлиспа,язык и системауже достаточностабилизировались.Интерлисп ужене был языкомв том же смысле,что и Маклиспили другиеЛисп- системыили обычныетрадиционныесистемы программирования.Он представлялсобой интегрированнуюсреду программирования,в которую вошломножестворазличныхвспомогательныхсредств. Интерлиспстал классическимпримером хорошоразвитых программныхсредств и средствв системахразделениявремени.[2]

Этот диалектнаряду с КоммонЛиспом одиниз наиболеераспространенных,имеет достаточноразвитый аппаратпредставленияи манипулированияразличнымиструктурамиданных, включаямассивы. Средиобщих особенностейданного вариантаязыка следуетотметитьиспользованиедля обозначениявстроенныхфункций нетрадиционныхимен, что поройзатрудняетперенос готовыхпрограммныхпродуктов надругие диалектыи другие ЭВМ.[7]

В 1974 году Xeroxначаларазработкудля Интерлиспаперсональнойлисповскойрабочей станциипод названиемAlto.В реализацииЛиспа дляAlto впервыеприменилиспроектированнуюспециальнодля языка Лиспмикропрограммируемуюсистему команди мини-ЭВМ, способнуюс более высокойпроизводительностью,чем универсальныеЭВМ, интерпретироватьлисповскиепрограммы. Изэтой машиныAlto впоследствииразвилисьЛисп-машинысерии 1100 фирмыXerox.

На основеверсии Интерлиспа,работавшейв системе разделениявремени, быласоздана совместимаяснизу вверхверсия ЛиспаИнтерлисп-де,используемаяна Лисп-машинахсерии 1100. В еепользовательскийинтерфейсвходили многооконноевзаимодействие,графика с высокойразрешающейспособностью,средства выбораиз меню и мышь,а также ориентированныйна использованиеэкрана инспекторструктур данных.Идея разделенияэкрана на многиенезависимыеокна родиласьв XLG.Алан Кэй ужев конце 60-х годовпредложил такуюидею подходак компьютерамбудущего иинтерфейсумежду человекоми машиной. РаботаXLG привелак созданию в70-х годах к разработкеязыка программированияSmolltalk и объектногопрограммирования.

При созданииИнтерлиспаработа веласьвесьма тщательно.Система хорошодокументированаи более новыеверсии совместимыс более ранними.Так преимуществомсистемы сталонепрерывнопополняющеесябольшое количествопереносимогопрограммногообеспечения.С другой стороны,ограничениесистемы старымзафиксированнымуже в конце70-х годов диалектомсделало системуотчасти устаревшейи трудно расширяемой.В Интерлиспесреди прочегоотсутствуютиерархическиетипы данных,объекты и замыкания.К тому же онбазируетсяна динамическомсвязывании,тогда как новыеверсии Лиспа- статические.Однако из Интерлиспаберет началоновая версия- Коммон Лисп(1986). Для программированияна более высокомуровне в Интерлиспразработанытакие средства,в которых ужеприсутствовалиобъекты.

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

Интерлисписпользуетсвыше 500 функцийи большое количествосистемных имени флажков, спомощью которыхможно настроитьи подогнатьсистему. Интерлиспреализованв системе разделениявремени намногих большихЭВМ.

В Интерлиспеосновное вниманиебыло уделеноудобству системыдля пользователя.Главный принципразработчиковэтого диалекта:все, что можетиметь местов системе, должноестественновыражатьсяв терминах еевходного языка.Поэтому в Интерлисппрограммистудоступно все.Он может переопределятьлюбые, в томчисле и встроенные,функции; задаватьи переопределятьреакции наошибки; работатьнепосредственнос уровня входногоязыка с внутреннимиструктурамиинтерпретатораи т. д. При этомсистема поддерживаетсвою целостностьи работоспособность.[7]

Франс Лисп.

Маклисп сталосновой длямногих новыхдиалектов языкаЛисп, первымиз которых былФранс Лисп. Этаверсия Лиспаназвана в честьизвестноговенгерскогокомпозитора.Главным мотивомразработкиФранс Лисп быложелание получитьсовременнуюЛисп-системудля новых машинVAX,чтобы на нихможно былоиспользоватьсистему Максимаи другое лисповскоепрограммноеобеспечение.Франс Лисп вдовольно большойстепени напоминаетМаклисп, накотором первоначальнобыла реализованаМаксима. Однаков диалектеотсутствуютнекоторыеустаревшиеособенностиМаклиспа исодержатсяболее новыесистемные идеи,заимствованныев то время вMITЛисп-машин дляЗеталиспа.

Новый диалектбыл реализованв университетев Беркли на ЭВМVAX780/11 на языкеСи под управлениемсистемыUNIX. ФрансЛисп довольношироко используетсякак под управлениемUNIX, так ипод управлениемVAX/VMS и в настоящеевремя являетсянаиболее частоиспользуемойверсией Лиспадля системразделениявремени. Крометого, он широкоиспользуетсяи на 32-битовыхмикро-ЭВМ ирабочих станциях,работающихпод управлениемUNIX.

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

ЗеталиспЛисп-машин.

Зеталисптакже опираетсяна Маклисп. Онсоздан в 70-е годыв MITв рамках проектаЛисп-машины,финансированногообороннымагентством.С самого началаего целью былоизготовлениекоммерческогопродукта. В1979 году в связис проектомродились двапредприятияизготавливающиеЛисп-машины:SymbolicInc. иLisp Machine Inc. (LMI). Послеэтого в 80-е годыработа по развитиюЗета Лиспапродолжаласьв них независимодруг от другана коммерческойоснове. В какой-томере системыотличаютсядруг от друга,но в части ЗетаЛиспа машиныпочти совместимы.[2]

Зета Лиспсодержит следующиеразвитые механизмыи черты:

• широкий выбортипов данных;

• возможностьобъектно-ориентированногопрограммированияв системе Flavor;

• современныеуправляющиеструктуры,динамическиемеханизмыпередачи управлениясопрограммыи процессы;

• гибкий механизмключевых словв лямбда-спискеи многозначныефункции;

• ввод и выводосновывающийсяна потоках;

• пространстваимен;

• уже готовыефункции, в томчисле длясортировки,работы с линейнымиуправлениямии матричныевычисления.

Выбор используемыхв среде Зеталиспаинструментови языков программированиязависит отпоставщика,причем предлагаемыйнабор средстввсе времярасширяется.Среди другихязыков предлагаютсяФортран, Паскаль,Ада и Пролог.Для этих языковв среде Зеталиспасуществуютособенно развитыепрограммныеокружения, иразработанныев них программыможно выполнятьвместе с программамина Лиспе.

Готовыеинструментыи прикладныеразработкив большом количествеимеются дляработы с ЭС, сестественнымязыком и речью,с реляционнымибазами данных,машинной графикии машинногопроектирования.[2]

Коммон Лисп.

Этот диалектотличаетсянаиболее широкимпредставлениемразличныхструктур данныхи включаетоколо 800 встроенныхфункций. В этомдиалектеобеспечиваютсясредства обработкиосновных классовчисловой информации:целых, вещественныхи комплексных.Символьныеданные (литеры,литеральныеатомы, строки)в Коммон Лиспесоответствуютосновным возможностямдругих Лисп-систем.Дополнительноимеются средстваобработкинепечатныхлитер в символьныхименах.

Одним изсущественныхпреимуществдиалекта КоммонЛисп являетсяналичие средствобработкимассивов иструктур, посвоим возможностямне уступающихсоответствующимсредствамтрадиционныхязыков программирования(Фортран, Паскаль).Массивы в КоммонЛиспе могутиметь любоенеотрицательноечисло измеренийи индексируютсяпоследовательностьюцелых чисел.Тип компонентовмассива можетбыть произвольным.Выделяетсяподкласс векторов- одномерныхмассивов, средикоторых отдельнорассматриваютсястроки и битовыемассивы.

СтруктурыКоммон Лиспаявляются типоммногокомпонентныхзаписей, определяемыхпользователеми имеющих именованныекомпоненты.ВстроенноемакроопределениеDEFSTRUCTиспользуетсядля определенияструктур новыхтипов. Для созданияданных новоготипа в видеструктурыпредусмотренысредстваавтоматическойгенерациинабора функций,обеспечивающихсредстваманипулированияобъектами этогокласса.[1]

Удобнымсредствомконтроля доступак различнымпеременными функциямЛисп-программв Коммон-Лиспеявляются пакеты.Пакет - множествоимен объектов,определенныхи доступныхв нем. Внутрипакета именаобъектовподразделяютсяна внутренниеи внешние. Первыепредназначеныдля использованиятолько внутриданного пакета,а вторые - дляобеспечениясвязи с другимипакетами.Лисп-интерпретаторпредставляетширокий спектрсредств манипулированияс пакетами. Какправило, Лисп-системаимеет в своемсоставе четырестандартныхпакета: lisp(содержащийпримитивысистемы),user (умалчиваемыйпакет прикладныхпрограмм иданных пользователя),keyword(содержащийключевые словавсех встроенныхфункций и функций,определяемыхпользователем),system (зарезервированныйдля системныхцелей).

Значительнойпереработкеи расширениюв Коммон Лиспеподверглисьсредства ввода-выводаи передачиинформации.Для эффективнойорганизацииразличныхобменов с внешнейсредой введенаконцепцияпотоков, позволяющихосуществлятьодно- и (или)двухстороннююпередачу информации.Для потоковпредусмотреннабор базовыхфункций. В диалектеразличаютсимвольныеи двоичныепотоки. В первомслучае передачаосуществляетсяпо байтам, а вовтором - целымичислами. Кроместандартныхпотоков пользовательимеет возможностьсоздавать ииспользоватьсобственныепотоки.[2]

В дополнениек указаннымтипам данныхКоммон Лиспимеет рядспецифическихклассов объектов:хэш-таблицы,обеспечивающиеэффективныйспособ доступак данным поключу; READ-таблицы,обеспечивающиеуправлениеобработкойинформациипоступающейиз входногопотока Лисп-системы,и некоторыедругие. Такоемножествоимеющихся вдиалекте различныхтипов данных,с одной стороны,развеиваетсуществующееошибочноепредставлениео языке Лиспкак о средствеобработкитолько символьнойинформации,а с другой - наличиемощных средствманипулированиятипами данныхсущественноусложняетего.[7]

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

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

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

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

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

Можно смелосказать, чтоКоммон Лиспсодержит почтивсе, что насегодняшнийдень могут датьдругие известныеязыки программирования,и, кроме того,он предусматриваетсредства длярасширенияязыка.

2. Лисп-машины.

С наступлением70-х годов большиесистемы ИИ иалгебраическиесистемы натолкнулисьна ограниченияпамяти и эффективности,существующиеи на большихуниверсальныхЭВМ. Восемнадцатибитовоеполе адресашироко используемыхмашин PDP-10/20стало серьезнымограничением,к тому же исследователиИИ не моглиработать всистеме разделениявремени в дневноевремя из-забольшой нагрузкина машины. Изэтих проблемродилась идеяоб отдельнойЛисп-машинеи о маневре,который известенпод названием«бегство изразделениявремени». Наэто направлениеповлияло такжеи быстрое развитиемикро-электронникив 70-х годах, сделавшеевозможнымпроектированиеи производствоориентированныхна язык процессорови персональныхЭВМ.

Первый отчет,связанный сЛисп-машинами,появился всерии изданийлабораторииИИ MITв 1974 году, а интегральнаясхемаLSI былаизготовленав 1978 году. ПервыепромышленныеЛисп-машиныпоявились нарынке нескольколет спустя.

Часть идей,касающихсяЛисп-машин,зародиласьв Исследовательскомцентре PaloAlto фирмыXerox и быларезультатомпионерскихразработокв области обработкиданных наперсональныхЭВМ и экранно-ориентированныхчеловеко-машинныхинтерфейсов.Это былиобъектно-ориентированныйподход, а такжеспециальныеинтегрированныев среду средстваи методы программирования,созданныефирмами XeroxиBBN в ходеработы надИнтерлиспом.[2]

Целью проектированияЛисп-машин быларазработкаих в виде персональныхЭВМ, которыеможно было быиспользоватьне только дляпрофессиональныхисследованийв области ИИ,но и для различныхпромышленныхи коммерческихприложений.Разработкеи их распространениюпомешаланеобходимостьпереноса программногообеспечениябольшого объемаиз дорогойсреды большихмашин.

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

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

СозданиеЛисп-машин далоновый толчокразвитию Лиспа.Кроме высокогобыстродействия(первая жеЛисп-машинаработала внесколько разбыстрее, чемМаклисп) и огромнойвиртуальнойсписковойпамяти, достоинствомЛисп-машинявляется и то,что для них этоединственныйязык программирования.На нем написанывсе системныепрограммы,начиная с ОСи кончая всевозможнымипрепроцессорами,и программыпользователя.Такая однородностьзначительноупрощает какразработкусамих системныхкомпонентов,так и взаимодействиес ними. По сутидела, на Лисп-машинахстирается граньмежду системными прикладнымпрограммнымобеспечением.В настоящеевремя Лисп-машинывыпускаютсярядом фирм США,Японии и ЗападнойЕвропы. В бывшихсоциалистическихстранах такжеимеются положительныепримеры разработкитаких машин.[7]

3. Выводы.

Современныедиалектыязыка Лиспможно рассматриватькак мощныеинтерактивныесистемы программирования.Это объясняетсядвумя причинами.Во-первых, самязык Лисппретерпеваетсерьезныеизменения -развиваютсясредства языка,предназначенныедля обработкинетрадиционныхдля Лиспа типовданных: массивов,векторов, матриц;появляютсянекоторыесредства управленияпамятью (пакеты),отсутствующиев Лиспе. Серьезныеизмененияпретерпеваюти управляющиеструктуры.Появилисьнесвойственныеприроде языкаЛисп функции,заимствованныеиз Фортрана,Алгола, Паскаля,Си: Do,Loop, Goto ,Caseи прочие, позволяющиепользователю,незнакомомус принципамифункциональныхязыков, легкопереходитьна Лисп. Качествопрограмм снижается,зато возрастаетпопулярностьязыка. Во-вторых,если на первомэтапе развитияЛисп-системамбыла присущанебольшаяскорость обработкиданных и серьезныеограниченияна емкостьиспользуемойоперативнойпамяти, то современныеЛисп-системыуже могут соперничатьпо этим параметрамс такими языками,как Си, Паскальи др. ИспользованиеЛисп-машинвообще практическиснимает ограниченияпамяти и быстродействия.

Для ПЭВМограниченияпо памяти ибыстродействиювсе еще остаютсясущественными.Однако положениене безнадежно.Развитие Лисп-системдля ПЭВМ идетсегодня по тремразличнымнаправлениям.Первое связанос увеличениемемкости памяти,которая можетиспользоватьсяЛисп-системой.С этой цельюряд компанийразработалверсии языкаGoldenCommon Lisp, использующиерасширенияоперативнойпамяти и виртуальнуюпамять. Второенаправлениесвязанно сповышениембыстродействияЛисп-систем.Третье направлениесостоит в разработкеэффективныхкомпиляторовпрограмм сязыка Лисп втрадиционныеязыки (чащевсего в языкСи).

Положительнымнововведениемв современныедиалекты языкаможно считатьпсевдоассемблерныекоманды, которыепозволяютоперироватьосновнымирегистрамимашины и организовыватьпрерыванияна уровне DOSи BIOS.Кроме того,многие Лисп-системыимеют хорошиеинтерфейсыс другими языками(Фортран, Паскаль,Ассемблер, Си),что позволяетповыситьэффективностьприкладныхЛисп-программ.

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

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

1. Можно предположить,что Лисп ещезначительноевремя будетоставатьсяосновным языкомдля реализацииинтеллектуальныхсистем.

2. Уже в ближайшеевремя можноожидать появленияязыков, вобравшихв себя лучшиечерты Лиспаи др. языков программированияИИ.

3. Наблюдаетсяявная тенденцияк созданиюпараллельныхверсий языковдля программированиязадач ИИ. Языкитипа Лисп, Пролог,Рефал (а такжевсевозможныемодификациии «смеси» этихи/илидругих языковсимвольнойобработки)будут все большеуступать своипозиции науровне инженеровпо знаниямспециальнымязыкам представлениязнаний, оставаясьинструментариемсистемныхпрограммистов.

На основаниианализа сравнительныххарактеристикдля изученияязыка Лисп вкурсе лабораторныхработ по предмету«Системыискуственногоинтеллекта» был выбрандиалект муЛисп.Выбор этогодиалекта основанна следующихего особенностях:

1. Простотав изучении(благодарянебольшомунабору базовыхфункций).

2. Близостьк стандартуязыка.

3. Возможностьпополнениябазового наборафункций.

4. ДополнительныебиблиотекиЛисп-функций,расширяющиебазовый наборфункций, имеющимисяв диалектахКоммон Лиспи Интерлисп,а также библиотеками,позволяющимивыполнятьманипулированиеокнами на экранедисплея и работатьс устройством«мышь».

5. Дополнительноепрограммноеобеспечениек интерпретатору:интерактивныйредактор текстови простая обучающаясистема.

Реферат.

Об’ємдипломноїроботі________________стор.

Кількістьілюстрацій_______________________ 4

Вікористанолітературнихджерел ___________ 12

Ключовіслова: штучнийінтелект, інтегрованесередовище,оператор, функція,функціонал,макрос, замикання,рекурсія.

Метоюцієї дипломноіроботи є ознаємленняз основами ограмуванняна Ліспі, вівченняособливостейсередовищаMuLispтаdlisp,розробка комплексулабораторнихробіт з дисципліни«Системи штучногоінтелекту»для студентівспеціальності«Комп’ютерніта інтелектуальнісистеми тамережі», розширеннябібліотекифункцій інтегрованногосередовищаdlisp,розробка завданьта контрольныхпитань долабораторнихробіт.

Содержание.

Введение__________________________________________________

1 Литературныйобзор_______________________________________

1.1 Краткаяистория развитияискусственногоинтеллекта____

1.2 Языкипрограммированияискусственногоинтеллекта_____ 1.2.1 Классификацияязыков и стилейпрограммирова-

ния____________________________________________

1.2.2 Сравнительныехарактеристикиязыков искус-

ственногоинтеллекта____________________________

1.2.2.1 Языки обработкисимвольнойинфор-

мации____________________________________

1.2.2.2 Языкипрограммированияинтеллектуаль-

ных решателей____________________________

1.3 ОсобенностиЛисп-систем______________________________1.3.1 ДиалектыЛиспа ____________________________

1.3.2 Лисп-машины______________________________

1.4 Выводы___________________________________________ 1.5 Постановказадачи_________________________________

2 Теоретическаячасть______________________________________

2.1 Основныеособенностиязыка Лисп___________________

2.2 Понятияязыка Лисп________________________________ 2.2.1 Атомыи списки_____________________________2.2.2 Внутреннеепредставлениесписка _____________2.2.3Написаниепрограммы наЛиспе _______________2.2.4Определениефункций_______________________2.2.5 Рекурсияи итерация_________________________2.2.6 Функцииинтерпретациивыражений____________2.2.7 Макросредства_____________________________2.2.8 Функцииввода и вывода_____________________

2.3 Знания вискусственноминтеллекте___________________ 2.3.1 Требованияк знаниям_______________________ 2.3.2 Основныетипы знаний_______________________

2.3.3 Методыпредставлениязнаний ________________

3 Практическаячасть________________________________________

3.1 Лабораторнаяработа №1____________________________

3.2 Лабораторнаяработа №2____________________________ 3.3 Лабораторнаяработа №3____________________________ 3.4 Лабораторнаяработа №4____________________________ 3.5 Лабораторнаяработа №5____________________________

3.6 Лабораторнаяработа №6____________________________

4 Вопросыинженернойпсихологии,применительнок отработке

программ__________________________________________________

Заключение________________________________________________

Список литературы__________________________________________

2. Теоретическаячасть.

2.1Основные особенностиязыка Лисп.

Отдругих языковпрограммированияЛисп отличаетсяследующимисвойствами:

1. одинаковаяформа данныхи программ;

2. хранение данных,не зависящееот места;

3. автоматическоеи динамическоеуправлениепамятью;

4. функциональнаянаправленность;

5. Лисп - бестиповыйязык;

6. интерпретирующийи компилирующийрежимы работы;

7. пошаговоепрограммирование;

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

Теперьрассмотримэти свойстваболее подробно.

Одинаковаяформа данныхи программ.

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

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

Хранениеданных не зависящееот места.

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

Автоматическоеи динамическоеуправлениепамятью.

Пользовательне должен заботитьсяоб учете памяти.Система резервируети освобождаетпамять автоматическив соответствиис потребностью.Когда памятькончается,запускаетсяспециальныймусорщик.Мусорщикперебираетвсе ячейки исобирает являющиесямусором ячейкив список свободнойпамяти длятого, чтобы ихможно былоиспользоватьзаново. CредаЛиспа постоянносодержитсяв порядке ВсовременныхЛисп-системахвыполнениеоперации сборкимусора занимаетот одной донесколькихсекунд. В задачахбольшого объемасборщик мусоразапускаетсявесьма часто,что резко ухудшаетвременныехарактеристикиприкладныхпрограмм. Вомногих системахмусор не образуется,поскольку онсразу же учитывается.Управлениепамятью простои не зависитот физическогорасположения,посколькусвободнаяпамять логическисостоит изцепочки списочныхячеек.

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

.

ФункциональнаянаправленностьЛиспа.

Функциональноепрограммирование,используемоев Лиспе, основываетсяна том, что врезультатекаждого действиявозникаетзначение. Значениястановятсяэлементамиследующихдействий,и конечныйрезультат всейзадачи выдаетсяпользователю.Обойти этоможно толькопри помощиспециальнойфункции QUOTE.То обстоятельство,что результатомвычислениймогут бытьновые функции,является важнымпреимуществомЛиспа.

Лисп- бестиповыйязык.

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

Динамическая,осуществляемаялишь в процессеисполнения,проверка типаи позднее связываниедопускаютразностороннееиспользованиесимволов игибкую модификациюпрограмм. Функцииможно определятьпрактическинезависимоот типов данных,к которым ониприменяются.

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

Одним из общихпринциповразвития Лисп-систембыло свободноевключение вязык новыхвозможностейи структур,если считалось,что они найдутболее широкоеприменение.Это было возможнов связи с естественнойрасширяемостьюязыка.

Платой задинамическиетипы являютсядействия попроверке типана этапе исполнения.В более новыхЛисп-системах(Коммон Лисп)возможнофакультативноеопределениетипов. В этомслучае трансляторможет использоватьэту информациюдля оптимизациикода. В Лисп-машинахпроверкаосуществляетсяна уровне аппаратуры.

Интерпретирующийи компилирующийрежимы работы.

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

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

Пошаговоепрограммирование.

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

Вспомогательныесредства, такиенапример как,редактор,трассировщик,транслятори другие образуютобщую интегрированнуюсреду, языккоторой нельзяотличить отсистемныхсредств. Отдельныесредства посвоему принципуявляются прозрачными,чтобы их моглииспользоватьдругие средства.Работа можетпроизводитьсячасто на различныхуровнях илив различныхрабочих окнах.Такой способработы особеннохорошо подходитдля исследовательскогопрограммированияи быстрогопостроенияпрототипов.

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

Лисп являетсяодновременнокак языкомприкладноготак и системногопрограммирования.Он напоминаетмашинный языктем, что какданные, так ипрограммыпредставленыв одинаковойформе. Языкпревосходноподходит длянаписанияинтерпретаторови трансляторовкак для негосамого, так идля другихязыков. НаиболеекороткийинтерпретаторПролога, написанныйна Лиспе занимаетнесколькодесятков строк.

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

2.2Понятияязыка Лисп.

2.2.1Атомы и списки.

Основнаяструктураданных в Лиспе- символьныеили S-выражения,которые определяютсякак атомы илисписки.

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

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

Пример:х, г-1997, символ,function.

Числа неявляются символами,так как числоне может представлятьиные лисповскиеобъекты, кромесамого себя,или своегочисловогозначения. ВЛиспе используетсябольшое количестворазличных типовчисел (целые,десятичныеи т. д.) - 24, 35.6, 6.3 e5.

Символы Tи NILимеют в Лиспеспециальноеназначение:Tобозначаетлогическоезначение истина,аNIL - логическоезначение ложь.Символы Tи NIL имеютвсегда однои тоже фиксированноевстроенноезначение. Ихнельзя использоватьв качестве имендругих лисповскихобъектов. СимволNILобозначаеттакже и пустойсписок.

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

Список - этоупорядоченнаяпоследовательность,элементамикоторой являютсяатомы или списки(подсписки).Списки заключаютсяв круглые скобки,элементы спискаразделяютсяпробелами.Открывающиеи закрывающиескобки находятсяв строгомсоответствии.Список всегданачинаетсяс открывающейи заканчиваетсязакрывающейскобкой. Список,который состоитиз 0 элементовназывают пустыми обозначают() или NIL.Пустой список- это атом. Например:(а в (с о) р), (+ 3 6).

Символ

Число T, NIL Списки

Константы

Атомы

S-выражения

Рис.2Символьныевыражения.

2.2.2Внутреннеепредставлениесписка.

Оперативнаяпамять машинылогическиразбиваетсяна маленькиеобласти, называемыесписочнымиячейками. Списочнаяячейка состоитиз двух частей,полей CARиCDR (головыи хвоста соответственно).Каждое из полейсодержит указатель.Указатель можетссылаться надругую списочнуюячейку или надругой лисповскийобъект, например,атом. Указателимежду ячейкамиобразуют какбы цепочку, покоторой можноиз предыдущейячейки попастьв следующуюи так до атомарныхобъектов. Каждыйизвестныйсистеме атомзаписан вопределенномместе памятилишь один раз.Указателемсписка являетсяуказатель напервую ячейкусписка. На однуи ту же ячейкуможет указыватьнесколькоуказателей,но исходитьтолько один.

Графическисписочнаяячейка представляетсяпрямоугольником(рис3), разделеннымна части CARиCDR. Указательизображаетсяв виде стрелки,начинающейсяв одной из частейпрямоугольникаи заканчивающейсяна изображениидругой ячейкиили атоме, накоторые ссылаетсяуказатель.

Рис.3Списочнаяячейка.

Логическиидентичныеатомы содержатсяв системе лишьодин раз. Нологическиидентичныесписки могутбыть представленыразличнымисписочнымиячейками. Например,список ((dc) a d c) изображаетсякак показанона рис.4. В результатевычисленийв памяти могутвозникнутьструктуры накоторые нельзяпотом сослаться.Это происходит,если структурыне сохраненыс помощью функцииSETQили теряетсяссылка на староезначение всвязи с новымпереприсваиванием.

A D C

Рис.4

A D C

рис.5

В зависимостиот способапостроениялогическаяи физическаяструктуры двухсписков могутоказатьсяразличными.Например, список((dc) a d c) можетиметь и другуюструктуру(рис5). Логическаяструктуравсегда топологическиимеет формудвоичногодерева, в товремя как физическаяструктура можетбыть ациклическимграфом, т. е. ветвимогут сновасходиться, ноникогда немогут образовыватьзамкнутые циклы(указыватьназад).

При логическомсравниваниисписков используютпредикат EQUAL,сравнивающийне физическиеуказатели, асовпадениеструктурногопостроениясписков и совпадениеатомов, формирующихсписок.

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

2.2.3Написаниепрограммы наЛиспе.

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

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

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

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

Множествабазовых функцийразличныхдиалектовсильно отличаютсядруг от друга,и их число колеблетсяот несколькихдесятков донесколькихсотен. Встроенныефункции выполняютсяс большей скоростью,чем функции,определенныепользователем,так как первыереализованына том же языке,что и вся Лисп-система(Ассемблер, С,Паскаль). Чрезмерноеувеличениебазового наборафункций приводитк уменьшениюрабочей памяти,отводимой подзадачи пользователя.

2.2.4Определениефункций.

Определениефункций и ихвычислениев Лиспе основанона лямбда-исчисленииЧерча. В лямбда-исчисленииЧерча функциязаписываетсяв следующемвиде:

lambda(x1,x2,...,xn).fn

ВЛиспе лямбда-выражениеимеет вид

(LAMBDA(x1 x2 ... xn) fn)

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

Телом функцииявляется произвольнаяформа, значениекоторой можетвычислитьинтерпретаторЛиспа.

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

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

(лямбда-выражениеа1 а2 ... аn)

Здесь ai- формы, задающиефактическиепараметры,которые вычисляютсякак обычно.

Вычислениелямбда-вызова,или применениелямбда-выраженияк фактическимпараметрам,производитсяв два этапа.Сначала вычисляютсязначения фактическихпараметрови соответствующиеформальныепараметрысвязываютсяс полученнымизначениями.Этот этап называетсясвязываниемпараметров.На следующемэтапе с учетомновых связейвычисляетсяформа, являющаясятелом лямбда-выражения,и полученноезначение возвращаетсяв качествезначениялямбда-вызова.Формальнымпараметрампосле окончаниявычислениявозвращаютсяте связи, которыеу них, возможнобыли передвычислениемлямбда-вызова.

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

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

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

Датьимя и определитьновую функциюможно с помощьюфункции DEFUN:

(DEFUNимя лямбда-списоктело)

DEFUNсоединяетсимвол с лямбда-выражением,и символ начинаетпредставлятьопределенныеэтим лямбда-выражениемвычисления.Значением этойформы являетсяимя новой функции.

В различныхдиалектах Лиспавместо DEFUNиспользуютсядругие именаи формы (DEFINE,DE,CSETQ и др.).

2.2.5Рекурсияи итерация.

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

Основнаяидея рекурсивногоопределениязаключаетсяв том, что функциюможно с помощьюрекуррентныхформул свестик некоторымначальнымзначениям, кранее определеннымфункциям илик самой определяемойфункции, но сболее «простыми»аргументами.Вычислениетакой функциизаканчиваетсяв тот момент,когда оно сводитсяк известнымначальнымзначениям.Разумеется,можно организоватьвычисленияпо рекуррентнымформулам и безиспользованиярекурсии, однакопри этом встаетвопрос о ясностипрограммы идоказательствеее эквивалентностиисходным формулам.Использованиерекурсии позволяетлегко запрограммироватьвычислениепо рекуррентнымформулам.

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

Так образуетсякак бы стекпрерванныхпроцессов, изкоторых выполняетсялишь последнийв настоящиймомент временипроцесс; послеокончания егоработы продолжаетвыполнятьсяпредшествовавшийему процесс.Целиком весьпроцесс выполнен,когда стекснова опустеет,или, другимисловами, всепрерванныепроцессы выполнятся.

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

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

В указаннойгруппе преждевсего выделяютсятак называемыеотображающиеили MAP-функции:MAPC,MAPCAR,MAPLIST и другие.MAP-функционалыявляются функциями,которые некоторымобразом отображаютсписок (последовательность)в новую последовательностьили порождаютпобочный эффект,связанный сэтой последовательностью.Каждая из нихимеет болеедвух аргументов,значениемпервого должнобыть имя определеннойранее или базовойфункции, илилямбда-выражение,вызываемоеMAP-функциейитерационно,а остальныеаргументыслужат длязадания аргументовна каждой итерации.Естественно,что количествоаргументовв обращениик MAP-функциидолжно бытьсогласованос предусмотреннымколичествомаргументову аргумента-функции.Различие междувсеми MAP-функциямисостоит в правилахформированиявозвращаемогозначения имеханизмевыбора аргументовитерирующейфункции накаждом шаге.

Рассмотримосновные типыMAP-функций.

MAPCAR.

Значениеэтой функциивычисляетсяпутем примененияфункции fnк последовательнымэлементам xiсписка, являющегосявторым аргументомфункции. Напримерв случае одногосписка получаетсяследующеевыражение:

(MAPCARfn ‘(x1 x2 ... xn))

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

MAPLIST.

MAPLISTдействуетподобно MAPCAR,но действияосуществляетне над элементамисписка, а надпоследовательнымиCDRэтого списка.

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

Функции MAPCANиMAPCON являютсяаналогамифункций MAPCARи MAPLIST.Отличие состоитв том, что MAPCANиMAPCON не строят,используя LIST,новый списокиз результатов,а объединяютсписки, являющиесярезультатами,в один список.

LOOP.

Другим типичнымпредставителемгруппы итерационныхфункций можетслужить функцияLOOP,имеющая в общемслучае вид(LOOP expr1 expr2 ... exprN), гдев качествеаргументовмогут бытьиспользованылюбые синтаксическии семантическидопустимыеS-выражениялибо специальныеконструкции.

2.2.6Функцииинтерпретациивыражения.

Почти во всехдиалектахопределеныфункции APPLYиFUNCALL, позволяющиеинтерпретироватьS-выражения.Обращения кэтим функциямимеют следующийвид:

(APPLYfun arg)

(FUNCALLfun arg1 arg2 ... argN)

APPLYи FUNCALLвычисляютфункции, являющиесяих первымиаргументами,производясвязываниеформальныхаргументовс указаннымиS-выражениямиarg илиarg1, arg2, ... argN. Вкачестве значениявозвращаетсярезультатпримененияфункции fun,которая можетбыть встроеннойили определеннойфункцией илилямбда-выражением.

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

2.2.7Макросредства.

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

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

(DEFMACROимя лямбда-списоктело)

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

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

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

2.2.8Функцииввода-вывода.

Современныедиалекты языкаЛисп, как правило,имеют развитыесредства управлениявводом-выводом.Основу этихсредств составляюттри основныефункции READ,RATOM иPRINT. Первыедве позволяютосуществлятьопераций вводаS-выражений(READ) и атомов(RATOM), последняявыполняет выводS-выражений.

Лисповскаяфункция чтенияREADобрабатываетвыражениецеликом. Вызовфункции осуществляетсяв виде

(READ)

Функция непоказывает,что она ждетввода выражения.Она лишь читаетвыражение ивозвращаетв качествезначения самоэто выражение,после чеговычисленияпродолжаются.

Для выводавыраженийиспользуютфункцию PRINT.Это функцияс одним аргументом,которая сначалавычисляетзначение аргумента,а затем выводитэто значение.ФункцияPRINT передвыводом аргументапереходит нановую строку,а после неговыводит пробел.Таким образом,значение выводитсявсегда на новуюстроку. Болееподробно этии другие функциирассмотримв лабораторныхработах.

Базовый наборфункций обычнонаряду с указаннымифункциямивключает различныеих модификациии дополнительныефункции, позволяющиепри программированиилегко получитьнекоторыедополнительныеэффекты (автоматическоедополнениепечатной строкис изображениемS-выраженияспециальнымисимволамиперевода кареткина начало следующейстроки, блокировкаспециальныхметасимволовпри выводелитеральныхатомов, в печатныхименах которыхприсутствуютнепечатныесимволы и т.д.). кроме того,практическикаждый диалектсодержит наборфункций управлениявходными ивыходнымипотоками длясвязи с внешнимиустройствамиЭВМ. Однакоуказанныефункции являютсяодной из наиболеемашинно-зависимыхсоставляющихЛисп-систем,поскольку понеобходимостиучитываютспецифику средыоперационнойсистемы.

2.3Знанияв ИИ.

2.3.1Требованияк знаниям.

Знания должныотвечать следующимтребованиям:

1. Должныбыть явнымии доступными.Это главноеотличие знанийот другихпрограммныхпродуктов.

2. Использоватьвысококачественныйопыт специалистов,т, е, знания должныотражать уровеньнаиболееквалифицированныхспециалистовв данной области.

3. Обладатьгибкостью, т.е. система можетнаращиватьсяпостепеннов соответствиис нуждами бизнесаили заказчика.

4. Иметьсистему объяснений.Интересуетне только ответ,но и как машинак нему пришла.

5. Обладатьвозможностьюпрогнозирования.Система должнане только даватьответы на конкретнопоставленныевопросы, но ипоказыватькак они изменяютсяв новой ситуации.

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

2.3.2Основныетипы знаний.

Определениезнания какпонятия - труднаяпроблема. Вобласти ИИнаиболее важныетипы знанийклассифицируютсяследующимобразом:

1. Объектыи их свойства.

Объекты- это существующиев прикладнойобласти универсальныепонятия и ихпредставители:живые существа,предметы илиматериалы илиабстрактныепонятия.

2. События.

Событияописываютучастие объектовв деятельностии ситуациях.События характеризуют,например, время,место и причинно-следственныеотношения.

3. Действия.

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

4. Метазнания.

Метазнания- это знания ознаниях и ихиспользовании,например способностьвыбрать методрешения дляпроблем разныхтипов.

2.3.3.Методыпредставлениязнаний.

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

Рассмотримважнейшие изобщих методови формализмов,разработанныхдля представленияи обработкизнаний:

1. Логика.В программахИИ особенночасто используютсяразличныеформы логикипредикатовпервого порядка.Основноепреимуществобазирующихсяна логикеформализмовсостоит в ром,что обычно сих помощьюпроще обеспечитькорректностьструктур ирешений системы,чем с помощьюдругих способовпредставления.

2.Продукционныесистемы

Наиболеераспространенным и простым дляпониманияявляетсяпредставлениезнаний припомощи правил продукции вида «ЕСЛИ, ТО».Такие системыназываютпродукционными. Эти правилапохожи на условныеоператорыIF-THEN языков программирования, однако совершеннопо другомуинтерпретируются.

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

Всостав продукционныхсистем входят: база знаний(используют термин: «базаправил»); рабочаяпамять или базаданных; машинавывода (используюттермин: «управляющаяструктура»).База правил содержит правила продукций. Рабочая памятьотображаеттекущее состояние процесса консультации. Содержит текущие значения переменныхи состояниемашины вывода.Машина выводаявляющаяся, по сути, интерпретаторомправил определяетпоследовательностьактивизацииправил, выполняетих, частичнозаполняетрабочую памятьпо собственнийинициативе, и частично поинструкциямиз базы правил.Работа интерпретатораправил состоитиз циклическиповторяющихсяэтапов. Сначалаопределяется,какие правиламогут выполнятьсяв данный момент,для чего отдельныечасти правилсравниваютсяс информациейхранимой врабочей памяти.Затем определяется,какое правилоследует выполнятьпервым. Критериемможет бытьприоритет, скорость выполненияправила и некоторыедругие вещи.Затем правилоисполняется, под чем подразумеваетсяизменениерабочей области, внутреннихпеременныхмашины вывода и окружения.

Существуетдва основныхметода просмотраи выполнения правил. Этопрямой и обратныйвыводы.

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

Приобратном выводе, управляемом следствиями или целямиправил (используется для созданияЭС диагностикии интерпретации),происходитдвижение отследствий кпосылкам. Машинавывода выбираеточереднуюнеизвестнуюпеременнуюи пытаетсяприсвоить ей какое-то значение. Для этого онапросматриваетвсе правила,в THEN поле которыхприсутствуетэта переменнаяи проверяетпосылку правила.Если в посылкеправила присутствуютне определенныепеременные, то аналогичнымспособом машинавывода пытаетсянайти их. Еслиправило с искомойпеременнойне выполняется, то ищутся другиеправила, содержащиев THEN поле этупеременную.

Возможентак же смешанныйвывод.

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

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

4.Фреймы. Эточастный случайсемантическихсетей. Это методпредставлениязнаний, которыйсвязывает свойства сузлами , представляющимипонятия и объекты.Свойства описываютсяатрибутами(называемымислотами) и ихзначениями.Использованиефреймов с ихатрибутамии взаимосвязямипозволяетхранить знанияо предметной области вструктурированном виде, представлятьв БЗ абстракциии аналогии.

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

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

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

Введение.

В последнеевремя особыйинтерес приобрелатехнологияискусственногоинтеллекта(ИИ). Вычислительныеустройства,обладающиев той или инойстепени «интеллектуальнымиспособностями,стали встраиватьдаже в бытовыеприборы.

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

Ведущее местосреди языковИИ занимаетЛисп, а точнее,множество егодиалектов.Длительноевремя не существовалостандарта этогоязыка. Но такоеразнообразиене доставлялонеприятностей,пока языкиспользовалсялишь в исследованиях.Даже напротив,идеи Лиспатаким образоммогли постоянноразвиватьсяи поэтому вязык вошлиновые, оказавшиесяполезнымисвойства, в томчисле и из другихязыков. Однаконедостатки,возникающиеиз-за несовместимостимежду диалектамистановилисьвсе болеесущественнымипо мере ростачисла практическихприложенийЛиспа.

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

Особенностямязыка Лисп ипосвященаданная дипломнаяработа, цельюкоторой являетсяразработкалабораторныхработ по курсу«Системыискусственногоинтеллекта»для студентовспециальности«Компьютерныеи интеллектуальныесистемы и сети»,а также расширениеЛисп-библиотекдля интегрированнойсреды dlisp.

В первой частидипломнойработы проведенанализ языковпрограммированияискусственногоинтеллекта.Особое местоуделено анализудиалектов языкаЛисп. В концераздела подводятсяитоги анализаи обосновываетсявыбор конкретногодиалекта Лиспаи вырабатываетсяпостановказадачи.

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

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

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

В заключенииработы подводятсяитоги проделаннойработы.

1.5 Постановказадачи.

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

На основаниипроведенногоанализа существующихдиалектов языкаЛисп для егоизучения вкурсе лабораторныхработ был выбранMuLisp.

Цель даннойдипломнойработы можносформулироватьследующимобразом:

1. Ознакомитьсяс основамипрограммированияна языке Лисп.

2. Изучитьособенностисреды MuLispи dlisp.

3. Разработатькомплекслабораторныхработ по, позволяющихосвоить основныесредства языкаMuLisp:

• базовыефункции языка;

• средстваязыка для работыс числами;

• функцииопределяемыепользователем;

• организациявычислений;

• рекурсияв Лиспе;

• функционалыи макросы;

• типы данныхиспользуемыхв MuLisp.

4. Расширитьбиблиотекуфункций интегрированнойсреды dlisp.

5. Разработатьзадания иконтрольныевопросы клабораторнымработам.

Заключение.

В результатевыполнениядипломнойработы былопроделаноследующее:

• Проведенанализ языковпрограммированияИИ, а такжедиалектови систем Лиспа.

• В качестветеоретическихсведений рассмотреныосновные особенностии возможностиязыка Лисп.

• Разработанкомплекслабораторныхработ по изучениюязыка MuLispдля студентовспециальности«Компьютерныеи интеллектуальныесистемы и сети»,имеющих следующиетемы:

Лабораторнаяработа №1.

Тема: Ознакомительнаяработа в средеMuLisp.Базовыефункции Лиспа.Символы, свойствасимволов. Средстваязыка для работыс числами.

Цель: Освоитьсреду MuLisp.Изучить базовыефункции Лиспа,символы и ихсвойства, атакже средствадля работы счислами.

Лабораторнаяработа №2.

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

Цель: Получитьнавыки в написаниифункций наЛиспе. Изучитьфункции ввода-вывода.

Лабораторнаяработа №3.

Тема: Организациявычисленийв Лиспа.

Цель: Изучитьосновные функциии их особенностидля организациивычисленийв Лиспе.

Лабораторнаяработа №4.

Тема: Рекурсияв Лиспе. Функционалыи макросы.

Цель: Изучитьосновы программированияс применениемрекурсии. Научитсяработать сфункционаламии макросами.

Лабораторнаяработа №5.

Тема: Типыданных, используемыев MuLisp.Точечноепредставлениесписков. Представлениезнаний.

Цель: Изучитьосновные типыданных MuLisp.Разобратьсяс точечнойнотацией списков.

Лабораторнаяработа №6.

Тема: Изучениеучебной версииинтегрированнойсреды dlisp.Расширениебиблиотекифункцийdlisp.

Цель: Ознакомитьсяс учебной версиейинтегрированнойсреды dlisp.Изучитьее возможностии особенности.Расширитьбиблиотекуфункций dlisp.

• Разработанызадания, требующиеиндивидуальнойработы студентаи контрольныевопросы, позволяющиеоценить уровеньзнаний студентапо каждой теме.

• Часть лабораторныхработ былавыполненастудентами5-го курса специальности«Компьютерныеи интеллектуальныесистемы и сети»,после чегобыли проработаны(изучены иисправлены)недостатки,а так же расширенкруг вопросов,раскрываемыхв лабораторныхработах.