Ѕаза знаний студента. –еферат, курсова€, контрольна€, диплом на заказ

курсовые,контрольные,дипломы,рефераты

Ћ»—ѕ — ѕрограммирование, Ѕазы данных

ѕосмотреть видео по теме –аботы

††††††††††††††††††††††††††††††††††††††††† †††††††††¬ведение.

¬ последнее врем€ особый интерес приобрела технологи€ искусственного интеллекта (»»). ¬ычислительные устройства, обладающие в той или иной степени Ђинтеллектуальными способност€ми, стали встраивать даже в бытовые приборы.

— развитием »» по€вилось большое количество специализированных €зыков программировани€: Ћисп, ѕролог, Ћого,  онивер и другие. ќни посто€нно развивались, оказывали взаимное вли€ние друг на друга, многие, не долго просуществовав, исчезали, но порождали идеи, которые давали новый толчок к мощному €зыкотворчеству в своей области.

¬едущее место среди €зыков »» занимает Ћисп, а точнее, множество его диалектов. ƒлительное врем€ не существовало стандарта этого €зыка. Ќо такое разнообразие не доставл€ло непри€тностей, пока €зык использовалс€ лишь в исследовани€х. ƒаже напротив, идеи Ћиспа таким образом могли посто€нно развиватьс€ и поэтому в €зык вошли новые, оказавшиес€ полезными свойства, в том числе и из других €зыков. ќднако недостатки, возникающие из-за несовместимости между диалектами становились все более существенными по мере роста числа практических приложений Ћиспа.

¬ конечном счете стандарт €зыка был разработан. »м стал Common Lisp. Ётот диалект содержит важнейшие черты современных Ћисп-систем: разнообразные типы данных, возможности определени€ типов, управл€ющие структуры, макросы с помощью которых легко определ€ютс€ новые синтаксические формы, функционалы, замыкани€, последовательности, а также синтаксический интерпретатор и трансл€тор. ћожно сказать, что Common Lisp содержит почти все, что на сегодн€шний день могут дать другие известные €зыки программировани€, и кроме того, он предусматривает средства дл€ расширени€.

ќсобенност€м €зыка Ћисп и посв€щена данна€ дипломна€ работа, целью которой €вл€етс€ разработка лабораторных работ по курсу Ђ—истемы искусственного интеллектаї дл€ студентов специальности Ђ омпьютерные и интеллектуальные системы и сетиї, а также расширение Ћисп-библиотек дл€ интегрированной среды dlisp.

¬ первой части дипломной работы проведен анализ €зыков программировани€ искусственного интеллекта. ќсобое место уделено анализу диалектов €зыка Ћисп. ¬ конце раздела подвод€тс€ итоги анализа и обосновываетс€ выбор конкретного диалекта Ћиспа и вырабатываетс€ постановка задачи.

¬тора€ часть дипломной работы посв€щена конкретно €зыку Ћисп. «десь рассматриваютс€ общие особенности и пон€ти€ €зыка, присущие всем диалектам Ћиспа.

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

¬ четвертый разделе дипломной работы затрагиваютс€ вопросы техники безопасности, а точнее, вопросы инженерной психологии, применительно к отработке программ.

¬ заключении работы подвод€тс€ итоги проделанной работы.


††††††††††††† 1 Ћитературный обзор.

1.1  ратка€ истори€ развити€ искусственного интеллекта.

»скусственный интеллект (»») - это область исследований, наход€ща€с€ на стыке наук, специалисты, работающие в этой области, пытаютс€ пон€ть, какое поведение, считаетс€ разумным (анализ), и создать работающие модели этого поведени€ (синтез). ѕрактической целью €вл€етс€ создание методов и техники, необходимой дл€ программировани€ Ђразумностиї и ее передачи вычислительным машинам (¬ћ), а через них всевозможным системам и средствам.[1]

¬ 50-х годах исследователи в области »» пытались строить разумные машины, имитиру€ мозг. Ёти попытки оказались безуспешными по причине полной непригодности как аппаратных так и программных средств.

¬ 60-х годах предпринимались попытки отыскать общие методы решени€ широкого класса задач, моделиру€ сложный процесс мышлени€. –азработка универсальных программ оказалась слишком трудным и бесплодным делом. „ем шире класс задач, которые может решать одна программа, тем беднее оказываютс€ ее возможности при решении конкретной проблемы.[5]

¬ начале 70-х годов специалисты в области »» сосредоточили свое внимание на разработке методов и приемов программировани€, пригодных дл€ решени€ более специализированных задач: методов представлени€ (способы формулировани€ проблемы дл€ решени€ на средствах вычислительной техники (¬“)) и методах поиска (способы управлени€ ходом решени€ так, чтобы оно не требовало слишком большого объема пам€ти и времени).

» только в конце 70-х годов была прин€та принципиально нова€ концепци€, котора€ заключаетс€ в том, что дл€ создани€ интеллектуальной программы ее необходимо снабдить множеством высококачественных специальных знаний о некоторой предметной области. –азвитие этого направлени€ привело к созданию экспертных систем (Ё—).[6]

¬ 80-х годах »» пережил второе рождение. Ѕыли широко осознаны его большие потенциальные возможности как в исследовани€х, так и в развитии производства. ¬ рамках новой технологии по€вились первые коммерческие программные продукты. ¬ это врем€ стала развиватьс€ область машинного обучени€. ƒо этих пор перенесение знаний специалиста-эксперта в машинную программу было утомительной и долгой процедурой. —оздание систем, автоматически улучшающих и расшир€ющих свой запас эвристических (не формальных, основанных на интуитивных соображени€х) правил - важнейший этап в последние годы. ¬ начале дес€тилети€ в различных странах были начаты крупнейшие в истории обработки данных национальные и международные исследовательские проекты, нацеленные на Ђинтеллектуальные ¬ћ п€того поколени€ї.[1]

»сследовани€ по »» часто классифицируютс€, исход€ из области их применени€, а не на основе различных теорий и школ. ¬ каждой из этих областей на прот€жении дес€тков лет разрабатывались свои методы программировани€, формализмы; каждой из них присущи свои традиции, которые могут заметно отличатьс€ от традиций соседней области исследовани€. ¬ насто€щее врем€ »» примен€етс€ в следующих област€х:

n обработка естественного €зыка;

n экспертные системы (Ё—);

n символьные и алгебраические вычислени€;

n доказательства и логическое программирование;

n программирование игр;

n обработка сигналов и распознавание образов;

n и др.

1.2 языки программировани€ »».

1.2.1  лассификаци€ €зыков и стилей программировани€.

¬се €зыки программировани€ можно разделить на процедурные и декларативные €зыки. ѕодавл€ющее большинство используемых в насто€щее врем€ €зыков программировани€ (—и, ѕаскаль, Ѕейсик и т. п.) относ€тс€ к процедурным €зыкам. Ќаиболее существенными классами декларативных €зыков €вл€ютс€ функциональные (Ћисп, Ћого, јѕЋ и т. п.) и логические (ѕролог, ѕлэнер,  онивер и др.) €зыки (рис.1).

Ќа практике €зыки программировани€ не €вл€ютс€ чисто процедурными, функциональными или логическими, а содержат в себе черты €зыков различных типов. Ќа процедурном €зыке часто можно написать функциональную программу или ее часть и наоборот. ћожет точнее было бы вместо типа €зыка говорить о стиле или методе программировани€. ≈стественно различные €зыки поддерживают разные стили в разной степени.[1]

ѕроцедурна€ программа состоит из последовательности операторов и предложений, управл€ющих последовательностью их выполнени€. “ипичными операторами €вл€ютс€ операторы присваивани€ и передачи управлени€, операторы ввода-вывода и специальные предложени€ дл€ организации циклов. »з них можно составл€ть фрагменты программ и подпрограммы. ¬ основе процедурного программировани€ лежат вз€тие значени€ какой-то переменной, совершение над ним действи€ и сохранени€ нового значени€ с помощью оператора присваивани€, и так до тех пор пока не будет получено (и, возможно, напечатано) желаемое окончательное значение.[2]

†††††††††††††††††††† я«џ » ѕ–ќ√–јћћ»–ќ¬јЌ»я


ѕ–ќ÷≈ƒ”–Ќџ≈ я«џ »†††† ƒ≈ Ћј–ј“»¬Ќџ≈ я«џ »

ѕаскаль, —и, ‘ортран, ...†††††††††††††††††††††††††


†††††††††††††††† Ћќ√»„≈— »≈ я«џ »†††† ‘”Ќ ÷»ќЌјЋ№Ќџ≈ я«џ »†††

†††††††††††††††††† ѕролог, Mandala...††††††††††††††††††††† Ћисп, Ћого, ј–Ћ, ...

††††††††††††††††††††††

–ис.1  лассификаци€ €зыков программировани€

Ћогическое программирование - это один из подходов к информатике, при котором в качестве €зыка высокого уровн€ используетс€ логика предикатов первого пор€дка в форме фраз ’орна. Ћогика предикатов первого пор€дка - это универсальный абстрактный €зык предназначенный дл€ представлени€ знаний и дл€ решени€ задач. ≈го можно рассматривать как общую теорию отношений. Ћогическое программирование базируетс€ на подмножестве логики предикатов первого пор€дка, при этом оно одинаково широко с ней по сфере охвата. Ћогическое программирование дает возможность программисту описывать ситуацию при помощи формул логики предикатов, а затем, дл€ выполнени€ выводов из этих формул, применить автоматический решатель задач (т. е. некоторую процедуру). ѕри использовании €зыка логического программировани€ основное внимание удел€етс€ описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать. ƒругие пон€ти€ информатики из таких областей, как теори€ рел€ционных баз данных, программна€ инженери€ и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ.[8].

‘ункциональна€ программа состоит из совокупности определений функций. ‘ункции, в свою очередь, представл€ют собой вызовы других функций и предложений, управл€ющих последовательностью вызовов. ¬ычислени€ начинаютс€ с вызова некоторой функции, котора€ в свою очередь вызывает функции, вход€щие в ее определение и т. д. в соответствии с иерархией определений и структурой условных предложений. ‘ункции часто либо пр€мо, либо опосредованно вызывают сами себ€.[2]

 аждый вызов возвращает некоторое значение в вызывавшую его функцию, вычисление которой после этого продолжаетс€; этот процесс повтор€етс€ до тех пор пока запустивша€ вычислени€ функци€ не вернет конечный результат пользователю.

Ђ„истоеї функциональное программирование не признает присваиваний и передач управлени€. –азветвление вычислений основано на механизме обработки аргументов условного предложени€. ѕовторные вычислени€ осуществл€ютс€ через рекурсию, €вл€ющуюс€ основным средством функционального программировани€.[1]††††

1.2.2 —равнительные характеристики €зыков »».

Ќа первом этапе развити€ »» (в конце 50-х - начале 60-х годов) не существовало €зыков и систем, ориентированных специально на области знаний. ѕо€вившиес€ к тому времени универсальные €зыки программировани€ казались подход€щим инструментом дл€ создани€ любых (в том числе и интеллектуальных ) систем, поскольку в этих €зыках можно выделить декларативную и процедурную компоненты.  азалось, что на этой базе могут быть интерпретированы любые модели и системы представлени€ знаний. Ќо сложность и трудоемкость таких интерпретаций оказались настолько велики, что прикладные системы дл€ реализации были недоступны. »сследовани€ показали, что производительность труда программиста остаетс€ посто€нной независимо от уровн€ инструментального €зыка, на котором он работает, а соотношение между длиной исходной и результирующей программ примерно 1:10. “аким образом, использование адекватного инструментального €зыка повышает производительность труда разработчика системы на пор€док, и это при одноступенчатой трансл€ции. языки предназначенные дл€ программировани€ интеллектуальных систем содержат иерархические (многоуровневые) трансл€торы и увеличивают производительность труда в 100-ни раз. ¬се это подтверждает важность использовани€ адекватных инструментальных средств.[7]

1.2.2.1 языки обработки символьной информации.

Ћисп.

язык Ћисп был разработан в —тэнфорде под руководством ƒж. ћаккарти в начале 60-х годов. ѕо первоначальным замыслам он должен был0 включать нар€ду со всеми возможност€ми ‘ортрана средства работы с матрицами, указател€ми и структурами из указателей и т. п. Ќо дл€ такого проекта не хватило средств. ќкончательно сформированные принципы положенные в основу €зыка Ћисп: использование единого спискового представлени€ дл€ программ и данных; применение выражений дл€ определени€ функций; скобочный синтаксис €зыка.[4]

Ћисп €вл€етс€ €зыком низкого уровн€, его можно рассматривать как ассемблер, ориентированный на работу со списковыми структурами. ѕоэтому на прот€жении всего существовани€ €зыка было много попыток его усовершенствовани€ за счет введени€ дополнительных базисных примитивов и управл€ющих структур. Ќо все эти изменени€ , как правило, не становились самосто€тельными €зыками. ¬ новых своих редакци€х Ћисп быстро усваивал все ценные изобретени€ своих конкурентов.[2]

ѕосле создани€ в начале 70-х годов мощных Ћисп-систем ћаклисп »нтерлисп попытки создани€ €зыков »», отличных от Ћиспа, но на той же основе, сход€т на нет. ƒальнейшее развитие €зыка идет, с одной стороны, по пути его стандартизации (—тандарт-Ћисп, ‘ранц-Ћисп,  оммон Ћисп), а с другой - в направлении создани€ концептуально новых €зыков дл€ представлени€ и манипулировани€ знани€ми в Ћисп среде. ¬ насто€щее врем€ Ћисп реализован на всех классах Ё¬ћ, начина€ с ѕЁ¬ћ и конча€ высоко производительными вычислительными системами.

Ћисп - не единственный €зык, используемый дл€ задач »». ”же в середине 60-х годов разрабатывались €зыки, предлагающие другие концептуальные основы. Ќаиболее важные из них в области обработки символьной информации - —ЌќЅќЋ и –ефал.

—ЌќЅќЋ.

Ёто €зык обработки строк, в рамках которого впервые по€вилась и была реализована в достаточно полной мере концепци€ поиска по образцу. язык —ЌќЅќЋ был одной из первых практических реализаций развитой продукционной системы. Ќаиболее известна€ и интересна€ верси€ этого €зыка - —нобол-4 «десь техника задани€ образцов и работа с ними существенно опередили потребности практики. ѕо существу, он так и осталс€ Ђфирменнымї €зыком программировани€, хот€ концепции —ЌќЅќЋа, безусловно, оказали вли€ние и на Ћисп, и на другие €зыки программировани€ задач »».

–ефал.

язык –ефал - алгоритмический €зык рекурсивных функций. ќн был создан “урчиным в качестве мета€зыка, предназначенного дл€ описани€ различных, в том числе и алгоритмических, €зыков и различных видов обработки таких €зыков. ѕри этом имелось в виду и использование –ефала† в качестве мета€зыка над самим собой. ƒл€ пользовател€ это €зык обработки символьной информации. ѕоэтому, помимо описани€ семантики алгоритмических €зыков, он нашел и другие применени€. Ёто выполнение громоздких аналитических выкладок в теоретической физике и прикладной математике, интерпретаци€ и компил€ци€ €зыков программировани€, доказательство теорем, моделирование целенаправленного поведени€, а в последнее врем€ и задачи »». ќбщим дл€ всех этих применений €вл€ютс€ сложные преобразовани€ над объектами, определенными в некоторых формализованных €зыках.

†¬ основу €зыка –ефал положено пон€тие рекурсивной функции, определенной на множестве произвольных символьных выражений. Ѕазовой структурой данных этого €зыка €вл€ютс€ списки, но не односв€зные, как в Ћиспе, а двунаправленные. ќбработка символов ближе к продукционной парадигме. ѕри† этом јктивно используетс€ концепци€ поиска по образцу, характерна€ дл€ —ЌќЅќЋа.

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

¬о многих случа€х возникает необходимость из программ, написанных на –ефале, вызывать программы, написанные на других €зыках. Ёто просто, так как с точки зрени€ –ефала первичные функции (‘ункции, описанные не на –ефале, но которые тем не менее можно вызывать из программ, написанных на этом €зыке.) - это просто некоторые функции, внешние по отношению к данной программе, поэтому, вызыва€ какую-либо функцию, можно даже и не знать, что это - первична€ функци€.

—емантика –ефал-программы описываетс€ в терминах абстрактной –ефал-машины. –ефал-машина имеет поле пам€ти и поле зрени€. ¬ поле пам€ти –ефал-машины† помещаетс€ программа, а в поле зрени€ - данные, которые будут обрабатыватьс€ с ее помощью, т. е. перед началом работы в поле пам€ти заноситс€ описание набора функций, а в поле зрени€ - выражение, подлежащее обработке.

„асто бывает удобно разбить –ефал-программу на части, которые могут обрабатыватьс€ компил€тором –ефала независимо друг от друга. Ќаименьша€ часть –ефал-программы, котора€ может быть обработана компил€тором независимо от других, называетс€ модулем. –езультат компил€ции исходного модул€ на –ефале представл€ет собой объектный модуль, который перед исполнением –ефал-программы должен быть объединен с другими модул€ми, полученными компил€цией с –ефала или других €зыков это объединение выполн€етс€ с помощью редактора св€зей и загрузчиков. ƒетали завис€т от используемой ќ—.

“аким образом, –ефал вобрал в себ€ лучшие черты наиболее интересных €зыков обработки символьной информации 60-х годов. ¬ насто€щее врем€ €зык –ефал используетс€ дл€ автоматизации построени€ трансл€торов, систем аналитических преобразований, а также, подобно Ћиспу, в качестве инструментальной среды дл€ реализации €зыков представлени€ знаний.[7]

ѕролог.

¬ начале 70-х годов по€вилс€ новый €зык составивший конкуренцию Ћиспу при реализации систем, ориентированных на знани€ - ѕролог. Ётот €зык не дает новых сверхмощных средств программировани€ по сравнению с Ћиспом, но поддерживает другую модель организации вычислений. ≈го привлекательность с практической точки зрени€ состоит в том, что, подобно тому, как Ћисп скрыл от программиста устройство пам€ти Ё¬ћ, ѕролог позволил ему не заботитс€ о потоке управлени€ в программе.[8]

ѕролог - европейский €зык, был разработан в ћарсельском университете в 1971 году. Ќо попул€рность он стал приобретать только в начале 80-х годов. Ёто св€зано с двум€ обсто€тельствами: во-первых, был обоснован логический базис этого €зыка и, во-вторых, в €понском проекте вычислительных систем п€того поколени€ он был выбран в качестве базового дл€ одной из центральных компонент - машины вывода.

язык ѕролог базируетс€ на ограниченном наборе механизмов, включающих в себ€ сопоставление образцов, древовидное представление структур данных и автоматический возврат. ѕролог особенно хорошо приспособлен дл€ решени€ задач, в которых фигурируют объекты и отношени€ между ними.[9]

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

ѕролог успешно примен€етс€ в таких област€х как: рел€ционные базы данных (€зык особенно полезен при создании интерфейсов рел€ционных баз данных с пользователем); автоматическое решение задач; понимание естественного €зыка; реализаци€ €зыков программировани€; представление знаний; экспертные системы и др. задачи »».[9]

“еоретической основой ѕролога €вл€етс€ исчисление предикатов. ѕрологу присущ р€д свойств, которыми не обладают традиционные €зыки программировани€.   таким свойствам относ€тс€ механизм вывода с поиском и возвратом, встроенный механизм сопоставлени€ с образцом. ѕролог отличает единообразие программ и данных. ќни €вл€ютс€ лишь различными точками зрени€ на объекты ѕролога. ¬ €зыке отсутствуют указатели, операторы присваивани€ и безусловного перехода. ≈стественным методом программировани€ €вл€етс€ рекурси€.

ѕролог программа состоит из двух частей: базы данных (множество аксиом) и последовательности целевых утверждений, описывающих в совокупности отрицание доказываемой теоремы. √лавное принципиальное отличие интерпретации программы на ѕрологе от процедуры доказательства теоремы в исчислении предикатов первого пор€дка состоит в том, что аксиомы в базе данных упор€дочены и пор€док их следовани€ весьма существенен, так как на этом основан сам алгоритм, реализуемый ѕролог-программы. ƒругое существенное ограничение ѕролога в том, что в качестве логических аксиом используютс€ формулы ограниченного класса - так называемые дизъюнкты ’орна. ќднако при решении многих практических задач этого достаточно дл€ адекватного представлени€ знаний. ¬о фразах ’орна после единственного заключени€ следует ноль и более условий.

ѕоиск Ђполезныхї дл€ доказательства формул - комбинаторна€ задача и при увеличении числа аксиом число шагов вывода катастрофически быстро растет. ѕоэтому в реальных системах примен€ют всевозможные стратегии, ограничивающие слепой перебор. ¬ €зыке ѕролог реализована стратеги€ линейной резолюции, предлагающа€ использование на каждом шаге в качестве одной из сравниваемых формул отрицание теоремы или ее Ђпотомкаї, а в качестве другой - одну из аксиом. ѕри этом выбор той или иной аксиомы дл€ сравнени€ может сразу или через несколько шагов завести в Ђтупикї. Ёто принуждает вернутьс€ к точке, в которой производилс€ выбор, чтобы испытать новую альтернативу, и т. д. ѕор€док просмотра альтернативных аксиом не произволен - его задает программист, располага€ аксиомы в базе данных в определенном пор€дке.  роме того в ѕрологе предусмотрены достаточно удобные Ђвстроенныеї средства дл€ запрещени€ возврата в ту или иную точку в зависимости от выполнени€ определенных условий. “аким образом процесс доказательства в ѕрологе более прост и целенаправлен чем в классическом методе резолюций.

—мысл программы €зыка ѕролог может быть пон€т либо с позиций декларативного подхода, либо с позиций процедурного подхода.[8]

ƒекларативный смысл программы определ€ет, €вл€етс€ ли данна€ цель истинной (достижимой) и, если да, при каких значени€х переменных она достигаетс€. ќн подчеркивает статическое существование отношений. ѕор€док следовани€ подцелей в правиле не вли€ет на декларативный смысл этого правила. ƒекларативна€ модель более близка к семантике логики предикатов, что делает ѕролог эффективным €зыком дл€ представлени€ знаний. ќднако в декларативной модели нельз€ адекватно представить те фразы, в которых важен пор€док следовани€ подцелей. ƒл€ по€снени€ смысла фраз такого рода необходимо воспользоватьс€ процедурной моделью.

ѕри процедурной трактовке ѕролог-программы определ€ютс€ не только логические св€зи между головой предложени€ и цел€ми в его теле, но еще и пор€док, в котором эти цели обрабатываютс€. Ќо процедурна€ модель не годитс€ дл€ разъ€снени€ смысла фраз, вызывающих побочные эффекты управлени€, такие как остановка выполнени€ запроса или удаление фразы из программы.[9]

ƒл€ решени€ реальных задач »» необходимы машины, скорость которых должна превышать скорость света, а это возможно лишь в параллельных системах. ѕоэтому последовательные реализации следует рассматривать как рабочие станции дл€ создани€ программного обеспечени€ будущих высокопроизводительных параллельных систем, способных выполн€ть сотни миллионов логических выводов в секунду. ¬ насто€щее врем€ существуют дес€тки моделей параллельного выполнени€ логических программ вообще и ѕролог-программ в частности. „асто это модели, использующие традиционный подход к организации параллельных вычислений: множество параллельно работающих и взаимодействующих процессов. ¬ последнее врем€ значительное внимание удел€етс€ и более современным схемам организации параллельных вычислений - потоковым модел€м. ¬ модел€х параллельного выполнени€ рассматриваютс€ традиционный ѕролог и присущие ему источники параллельности.

†Ќа эффективности ѕролога очень сильно сказываютс€ ограниченность ресурсов по времени и пространству. Ёто св€зано с неприспособленностью традиционной архитектуры вычислительных машин дл€ реализации прологовского способа выполнени€ программ, предусматривающего достижение целей из некоторого списка. ¬ызовет ли это трудности в практических приложени€х, зависит от задачи. ‘актор времени практически не имеет значени€, если пролог-программа, запускаема€ по несколько раз в день, занимает одну секунду, а соответствующа€ программа на другом €зыке - 0.1 секунды. Ќо разница в эффективности становитс€ существенной, если эти две программы требуют 50 и 5 минут соответственно.

— другой стороны, во многих област€х применени€ ѕролога он может существенно сократить врем€ разработки программ. ѕрограммы на ѕрологе легче писать, легче понимать и отлаживать, чем программы, написанные на традиционных €зыках, т. е. €зык ѕролог привлекателен своей простотой. ѕролог-программу легко читать, что €вл€етс€ фактором, способствующим повышению производительности при программировании и увеличению удобств при сопровождении программ. ѕоскольку ѕролог основан на фразах ’орна, исходный текст ѕролог-программ значительно менее подвержен вли€нию машинно-зависимых особенностей, чем исходные тексты программ, написанных на других €зыках.  роме того в различных верси€х €зыка ѕролог про€вл€етс€ тенденци€ к единообразию, так что программу, написанную дл€ одной версии, легко можно преобразовать в программу дл€ другой версии этого €зыка.  роме того ѕролог прост в изучении.[8]

ѕри выборе €зыка ѕролог как базового €зыка программировани€ в €понском проекте вычислительных систем п€того поколени€ в качестве одного из его недостатков отмечалось отсутствие развитой среды программировани€ и неприспособленность ѕролога дл€ создани€ больших программных систем. —ейчас ситуаци€ несколько изменилась, хот€ говорить о действительно ориентированной на логическое программирование среде преждевременно.†††

—реди €зыков, с по€влением которых возникали новые представлени€ о реализации интеллектуальных систем, необходимо выделить €зыки, ориентированные на программирование поисковых задач.

1.2.2.2 языки программировани€ интеллектуальных решателей.

√руппа €зыков, которые можно назвать €зыками интеллектуальных решателей, в основном ориентирована на такую подобласть »», как решение проблем, дл€ которой характерны, с одной стороны, достаточно простые и хорошо формализуемые модели задач, а с другой - усложненные методы поиска их решени€. ѕоэтому основное внимание в этих €зыках было уделено введению мощных структур управлени€, а не способам представлени€ знаний. Ёто такие €зыки как ѕлэнер,  онивер,  юј-4,  юЋисп.

ѕлэнер.

Ётот €зык дал толчок мощному €зыкотворчеству в области »». язык разработан в ћассачуссетском технологическом институте в 1967-1971гг. ¬начале это была надстройка над Ћиспом, в таком виде €зык реализован на ћаклиспе под названием ћикро ѕлэнер. ¬ дальнейшем ѕлэнер был существенно расширен и превращен в самосто€тельный €зык. ¬ ———– он реализован под названием ѕлэнер-ЅЁ—ћ и ѕлэнер-Ёльбрус. Ётот €зык ввел в €зыки программировани€ много новых идей: автоматический поиск с возвратами, поиск данных по образцу, вызов процедур по образцу, дедуктивный метод и т. д.

¬ качестве своего подмножества ѕлэнер содержит практически весь Ћисп (с некоторыми модификаци€ми) и во многом сохран€ет его специфические особенности. —труктура данных (выражений, атомов и списков), синтаксис программ и правила их вычислени€ в ѕлэнере аналогичны лисповским. ƒл€ обработки данных в ѕлэнере в основном используютс€ те же средства, что и в Ћиспе: рекурсивные и блочные функции. ѕрактически все встроенные функции Ћиспа, в том числе и функци€ EVAL, включены в ѕлэнер. јналогично определ€ютс€ новые функции.  ак и в Ћиспе , с атомами могут быть св€заны списки свойств.

Ќо между Ћиспом и ѕлэнером существуют и различи€. ќтметим некоторые из них. ¬ Ћиспе при обращении к переменной указываетс€ только ее им€, например ’, сам же атом как данное указываетс€ как СX. ¬ ѕлэнере используетс€ обратна€ нотаци€: атомы обозначают самих себ€, а при обращении к переменным перед их именем ставитс€ префикс. ѕри этом префикс указывает как должна быть использована переменна€. ќтличаетс€ от лисповского и синтаксис обращени€ к функци€м, которое в ѕлэнере записываетс€ в виде списка не с круглыми, а с квадратными скобками.

ƒл€ обработки данных в ѕлэнере используютс€ не только функции, но и образцы и сопоставители.

ќбразцы описывают правила анализа и декомпозиции данных и поэтому их применение облегчает написание программ и сокращает их тексты.

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

–ассмотренное подмножество ѕлэнера можно использовать независимо от других его частей: оно представл€ет собой мощный €зык программировани€, удобный дл€ реализации различных систем символьной обработки. ќстальные части ѕлэнера ориентируют его на область »», предоставл€€ средства дл€ описани€ задач (исходных ситуаций, допустимых операций, целей), решени€ которых должна искать система »», реализуема€ на ѕлэнере, и средства, упрощающие реализацию процедур поиска решени€ этих задач.

Ќа ѕлэнере можно программировать описыва€ то, что имеетс€ и то что надо получить, без €вного указани€, как это делать. ќтветственность же за поиск решени€ описываемой задачи берет на себ€ встроенный в €зык дедуктивный механизм (механизм автоматического достижени€ целей), в основе которого лежит вызов теорем по образцу. ќднако только вызова теорем по образцу не достаточно дл€ такого механизма. Ќеобходим механизм перебора, и такой механизм - режим возвратов - введен в €зык.

¬ыполнение программы в режиме возвратов удобно дл€ ее автора тем, что €зык берет на себ€ ответственность за запоминание развилок и оставшихс€ в них альтернатив, за осуществление возвратов к ним и восстановлени€ прежнего состо€ни€ программы - все это делаетс€ автоматически. Ќо такой автоматизм не всегда выгоден, так как в общем случае он ведет к Ђслепомуї перебору. » может оказатьс€ так, что при вызове теорем наиболее подход€ща€ из них будет вызвана последней, хот€ автор программы заранее знает о ее достоинствах. ”читыва€ это ѕлэнер предоставл€ет средства управлени€ режимом возвратов.[7]

 онивер.

язык  онивер был разработан в 1972 году, реализован как надстройка над €зыком ћаклисп. јвторы €зыка  онивер выступили с критикой некоторых идей €зыка ѕлэнер. ¬ основном она относилась к автоматическому режиму возвратов, который в общем случае ведет к неэффективным и неконтролируемым программам, особенно если она составл€етс€ неквалифицированными пользовател€ми. јвторы  онивер отказались от автоматического режима возвратов, счита€, что встраивать в €зык какие-то фиксированные дисциплины управлени€ (кроме простейших - циклов, рекурсий) не следует и что автор программы должен сам организовывать нужные ему дисциплины управлени€, а дл€ этого €зык должен открывать пользователю свою структуру управлени€ и предоставл€ть средства работы с ней. Ёта концепци€ была реализована в  онивер следующим образом.

ѕри вызове процедуры в пам€ти отводитс€ место, где хранитс€ информаци€, необходима€ дл€ ее работы. «десь, в частности, располагаютс€ локальные переменные процедуры, указатели доступа (ссылка на процедуру, переменные которой доступны из данной) и возврата (ссылка на процедуру, которой надо вернуть управление). ќбычно эта информаци€ скрыта от пользовател€, а в €зыке  онивер такой участок пам€ти (фрейм) открыт: пользователь может просматривать и мен€ть содержимое фрейма. ¬ €зыке фреймы представл€ют специальный тип данных, доступ к которым осуществл€етс€ по указател€м.

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

”читыва€ сложность реализации дисциплин управлени€, авторы €зыка были вынуждены включить в него р€д фиксированных механизмов управлени€, аналогов процедур-развилок и теорем €зыка ѕлэнер. Ќо в отличии от ѕлэнера, где разрыв между выбором альтернативы в развилке и ее анализом, а в случае необходимости выработкой неуспеха может быть сколь угодно велик, в €зыке  онивер этот разрыв сведен к минимуму. Ётим  онивер избавл€етс€ от негативных последствий глобальных возвратов по неуспеху, когда приходитс€ отмен€ть предыдущую работу чуть ли не всей программы.[7]

1.2.2.3 языки представлени€ знаний.

¬ рамках каждого базового €зыка »» €вным образом выдел€ютс€ и пр€мое его использование, и расширение за счет пакетов функций, и создание Ђавтономногої €зыка представлени€ знаний (яѕ«) с последующей интерпретацией или компил€цией программ на созданном €зыке. Ќо в последнем случае базовый €зык, как правило, становитс€ инструментальным средством дл€ реализации яѕ«.

Ќезависимо от реализации яѕ« должен отвечать следующим требовани€м:

n наличие простых и вместе с тем достаточно мощных средств представлени€ сложно структурированных и взаимосв€занных объектов;

n возможность отображени€ описаний объектов на разные виды пам€ти Ё¬ћ;

n наличие гибких средств управлени€ выводом, учитывающих необходимость структурировани€ правил работы решател€;

n Ђпрозрачностьї системных механизмов дл€ программиста, т. е. возможность их до определени€ и переопределени€ на уровне входного €зыка;

n возможность эффективной реализации, как программной, так и аппаратной;

 онечно, перечисленные требовани€ во многом противоречивы. Ќо лишь тогда, когда в рамках разумного компромисса учтены все эти требовани€, создаютс€ удачные яѕ«.

—реди яѕ« первого поколени€ (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.3.1 ƒиалекты Ћиспа.

ћаклисп.

 роме символьной обработки ћаклисп широко использовалс€ в традиционных числовых вычислени€х, примен€емых , например, в обработке речи и изображений.  роме исследователей »» и разработчиков алгебраической системы ћаксима на ћаклисп оказали вли€ние и работы групп в ћ»“ по робототехнике, обработке речи и изображений. »сход€ из требований, предъ€вл€емых этими област€ми, в ћаклисп были включены новые математические типы данных, такие как матрична€ и битова€ обработка, а также широкий набор арифметических функций и средств. Ѕыть может, важнейша€ из них - возможность вычислений с неограниченной точностью, основывающа€с€ на созданных  нутом (1969) алгоритмах.[2]

ћаклисп был также первой Ћисп-системой дл€ которой создан хороший трансл€тор. “рансл€тор генерирует машинную программу в форме списков. ћашинный код в виде списка легко обрабатывать и результирующий код дл€ числовых задач получалс€ эффективнее, чем у лучших фортрановских трансл€торов.

ќднако большую часть своих свойств ћаклисп приобрел под вли€нием сто€щих перед исследовател€ми »» проблем и накопленного опыта. “ак в €зык попали макросы чтени€ и таблицы чтени€, позвол€ющие легко измен€ть и расшир€ть структуру €зыка. “аким же образом из требований к программам и окружению возникли управл€ющие структуры, механизмы обработки прерываний и ошибок, а также использование управл€ющих символов, создан и интегрирован в систему экранный редактор, по€вились управление и взаимодействие параллельных процессов.

ќсновное внимание разработчики ћаклиспа сосредоточили на эффективности. Ётому служат указани€, уточн€ющие способы обработки аргументов функций, а также экранирование от вмешательства программиста внутренних механизмов системы. «а счет этих мер скорость работы ћаклиспа в 1.5-2.5 раза выше, чем »нтерлисп.[7]

¬сего в ћаклиспе используетс€ около 400 функций. —амым большим недостатком системы €вл€етс€ то, что ее никогда не документировали должным образом. ƒокументаци€ по этой системе разбросана по различным отчетам и руководствам. ћаклисп был исследовательской системой и не предназначалс€ дл€ обучени€ и промышленного использовани€.[2]

муЋисп.

»нтерпретатор ћулисп-85, разработанный дл€ ѕЁ¬ћ серии IBM PC - удачный вариант реализации диалекта €зыка, включающий сравнительно ограниченный набор базовых функций (около 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 Ћисп-машин дл€ «еталиспа.

Ќовый диалект был реализован в университете в Ѕеркли на Ё¬ћ VAX 780/11 на €зыке —и под управлением системы UNIX. ‘ранс Ћисп довольно широко используетс€ как под управлением UNIX, так и под управлением VAX/VMS и в насто€щее врем€ €вл€етс€ наиболее часто используемой версией Ћиспа дл€ систем разделени€ времени.  роме того, он широко используетс€ и на 32-битовых микро-Ё¬ћ и рабочих станци€х, работающих под управлением UNIX.

Ѕлагодар€ своей хорошей переносимости ‘ранс Ћисп получил распространение во многих университетах и исследовательских учреждени€х. —опровождение системы также разошлось в различных исправлени€х системных ошибок, реализаци€х наиболее эффективных алгоритмов, а также в расширени€х €зыка.

«еталисп Ћисп-машин.

«еталисп также опираетс€ на ћаклисп. ќн создан в 70-е годы в MIT в рамках проекта Ћисп-машины, финансированного оборонным агентством. — самого начала его целью было изготовление коммерческого продукта. ¬ 1979 году в св€зи с проектом родились два предпри€ти€ изготавливающие Ћисп-машины: Symbolic Inc. и Lisp Machine Inc. (LMI). ѕосле этого в 80-е годы работа по развитию «ета Ћиспа продолжалась в них независимо друг от друга на коммерческой основе. ¬ какой-то мере системы отличаютс€ друг от друга, но в части «ета Ћиспа машины почти совместимы.[2]

«ета Ћисп содержит следующие развитые механизмы и черты:

n широкий выбор типов данных;

n возможность объектно-ориентированного программировани€ в системе Flavor ;

n современные управл€ющие структуры, динамические механизмы передачи управлени€ сопрограммы и процессы;

n гибкий механизм ключевых слов в л€мбда-списке и многозначные функции;

n ввод и вывод основывающийс€ на потоках;

n пространства имен;

n уже готовые функции, в том числе дл€ сортировки, работы с линейными управлени€ми и матричные вычислени€.

¬ыбор используемых в среде «еталиспа инструментов и €зыков программировани€ зависит от поставщика, причем предлагаемый набор средств все врем€ расшир€етс€. —реди других €зыков предлагаютс€ ‘ортран, ѕаскаль, јда и ѕролог. ƒл€ этих €зыков в среде «еталиспа существуют особенно развитые программные окружени€, и разработанные в них программы можно выполн€ть вместе с программами на Ћиспе.

√отовые инструменты и прикладные разработки в большом количестве имеютс€ дл€ работы с Ё—, с естественным €зыком и речью, с рел€ционными базами данных, машинной графики и машинного проектировани€.[2]

 оммон Ћисп.

Ётот диалект отличаетс€ наиболее широким представлением различных структур данных и включает около 800 встроенных функций. ¬ этом диалекте обеспечиваютс€ средства обработки основных классов числовой информации: целых, вещественных и комплексных. —имвольные данные (литеры, литеральные атомы, строки) в  оммон Ћиспе соответствуют основным возможност€м других Ћисп-систем. ƒополнительно имеютс€ средства обработки непечатных литер в символьных именах.

ќдним из существенных преимуществ диалекта  оммон Ћисп €вл€етс€ наличие средств обработки массивов и структур, по своим возможност€м не уступающих соответствующим средствам традиционных €зыков программировани€ (‘ортран, ѕаскаль). ћассивы в  оммон Ћиспе могут иметь любое неотрицательное число измерений и индексируютс€ последовательностью целых чисел. “ип компонентов массива может быть произвольным. ¬ыдел€етс€ подкласс векторов - одномерных массивов, среди которых отдельно рассматриваютс€ строки и битовые массивы.

—труктуры  оммон Ћиспа €вл€ютс€ типом многокомпонентных записей, определ€емых пользователем и имеющих именованные компоненты. ¬строенное макроопределение DEFSTRUCT используетс€ дл€ определени€ структур новых типов. ƒл€ создани€ данных нового типа в виде структуры предусмотрены средства автоматической генерации набора функций, обеспечивающих средства манипулировани€ объектами этого класса.[1]

”добным средством контрол€ доступа к различным переменным и функци€м Ћисп-программ в  оммон-Ћиспе €вл€ютс€ пакеты. ѕакет - множество имен объектов, определенных и доступных в нем. ¬нутри пакета имена объектов подраздел€ютс€ на внутренние и внешние. ѕервые предназначены дл€ использовани€ только внутри данного пакета, а вторые - дл€ обеспечени€ св€зи с другими пакетами. Ћисп-интерпретатор представл€ет широкий спектр средств манипулировани€ с пакетами.  ак правило, Ћисп-система имеет в своем составе четыре стандартных пакета: lisp (содержащий примитивы системы), user (умалчиваемый пакет прикладных программ и данных пользовател€), keyword (содержащий ключевые слова всех встроенных функций и функций, определ€емых пользователем), system (зарезервированный дл€ системных целей).

«начительной переработке и расширению в  оммон Ћиспе подверглись средства ввода-вывода и передачи информации. ƒл€ эффективной организации различных обменов с внешней средой введена концепци€ потоков, позвол€ющих осуществл€ть одно- и (или) двухстороннюю передачу информации. ƒл€ потоков предусмотрен набор базовых функций. ¬ диалекте различают символьные и двоичные потоки. ¬ первом случае передача осуществл€етс€ по байтам, а во втором - целыми числами.  роме стандартных потоков пользователь имеет возможность создавать и использовать собственные потоки.[2]

¬ дополнение к указанным типам данных  оммон Ћисп имеет р€д специфических классов объектов: хэш-таблицы, обеспечивающие эффективный способ доступа к данным по ключу; READ-таблицы, обеспечивающие управление обработкой информации поступающей из входного потока Ћисп-системы, и некоторые другие. “акое множество имеющихс€ в диалекте различных типов данных, с одной стороны, развеивает существующее ошибочное представление о €зыке Ћисп как о средстве обработки только символьной информации, а с другой - наличие мощных средств манипулировани€ типами данных существенно усложн€ет его.[7]

Ётот диалект оставлен открыт: принципиальным €вл€етс€ то, что осталась возможность в будущем, когда подойдет врем€ и будет достигнуто согласие, добавить новые средства и методы. Ёта иде€ как раз соответствует духу Ћиспа.

 оммон Ћисп не €вл€етс€ готовой программной системой в том же смысле, что и »нтерлисп, поскольку вопросы среды в основном оставлены открытыми. ¬ стандарте не определено, каким должен быть редактор или другие вспомогательные средства. —казано лишь в самом общем виде, каким образом они вызываютс€. ƒл€ того чтобы обеспечить быстрое развитие, среда и инструментальные средства еще не затронуты стандартизацией, и поэтому есть возможность создавать различные среды дл€ различных целей.  оммон Ћисп не определ€ет также и интерфейс пользовател€.

¬  оммон Ћисп на современном этапе не включены даже средства объектного программировани€, хот€ и определены необходимые дл€ этого базовые механизмы (замыкание и др.). “аким образом, объекты можно реализовать на Ћиспе. Ќо уже ведетс€ работа по стандартизации средств и форм объектного программировани€.

¬  оммон Ћиспе много внимани€ уделено практическим требовани€м, и, веро€тно, поэтому не все его черты эстетичны и чисты. Ќесомненно, что и другие Ћисп-системы будут использоватьс€ в дальнейшем, и их также необходимо развивать.

 оммон Ћисп предназначен не только дл€ работы со списками или дл€ символьной обработки, он €вл€етс€ универсальным €зыком программировани€, включающим в себ€ особенно хорошие средства дл€ численных вычислений, управлени€ данными и св€зи. Ќа  оммон Ћиспе можно с одинаковым успехом писать программы в традиционных операторном, процедурном, фразовом стиле, а также и в свойственных Ћиспу стил€х. ¬ €зыке содержатс€ предпосылки дл€ использовани€ различных способов и стилей программировани€, таких как операторное, функциональное, макропрограммирование, программирование, управл€емое данными, и продукционное программирование, а также средства, необходимые дл€ логического и объектного программировани€ и реализации других средств более высокого уровн€.[1]

ћожно смело сказать, что  оммон Ћисп содержит почти все, что на сегодн€шний день могут дать другие известные €зыки программировани€, и, кроме того, он предусматривает средства дл€ расширени€ €зыка.

1.3.2 Ћисп-машины.

— наступлением 70-х годов большие системы »» и алгебраические системы натолкнулись на ограничени€ пам€ти и эффективности, существующие и на больших универсальных Ё¬ћ. ¬осемнадцатибитовое поле адреса широко используемых машин PDP-10/20 стало серьезным ограничением, к тому же исследователи »» не могли работать в системе разделени€ времени в дневное врем€ из-за большой нагрузки на машины. »з этих проблем родилась иде€ об отдельной Ћисп-машине и о маневре, который известен под названием Ђбегство из разделени€ времениї. Ќа это направление повли€ло также и быстрое развитие микро-электронники в 70-х годах, сделавшее возможным проектирование и производство ориентированных на €зык процессоров и персональных Ё¬ћ.

ѕервый отчет, св€занный с Ћисп-машинами, по€вилс€ в серии изданий лаборатории »» MIT в 1974 году, а интегральна€ схема LSI была изготовлена в 1978 году. ѕервые промышленные Ћисп-машины по€вились на рынке несколько лет спуст€.

„асть идей, касающихс€ Ћисп-машин, зародилась в »сследовательском центре Palo Alto фирмы Xerox и была результатом пионерских разработок в области обработки данных на персональных Ё¬ћ и экранно-ориентированных человеко-машинных интерфейсов. Ёто были объектно-ориентированный подход, а также специальные интегрированные в среду средства и методы программировани€, созданные фирмами Xerox и BBN в ходе работы над »нтерлиспом.[2]

÷елью† проектировани€ Ћисп-машин была разработка их в виде персональных Ё¬ћ, которые можно было бы использовать не только дл€ профессиональных исследований в области »», но и дл€ различных промышленных и коммерческих приложений. –азработке и их распространению помешала необходимость переноса программного обеспечени€ большого объема из дорогой среды больших машин.

ѕо производительности оборудовани€ Ћисп-машины очень эффективны, кроме того, они имеют большой объем основной пам€ти. »х аппаратура спроектирована специально дл€ вычислений на Ћиспе. — точки зрени€ эффективности одной из наиболее важных особенностей €вл€етс€ проверка типов на уровне аппаратуры, используема€ в системах, происход€щих из MIT.

ќднако наиболее существенным преимуществом такой аппаратуры €вл€етс€ возможность использовани€ на Ћисп-машине интегрированной программной среды. ¬ ней нар€ду с самим Ћиспом содержатс€ разнообразные программные средства. ѕрограммное обеспечение использует тыс€чи функций. ¬о многих системах помимо Ћиспа доступны и другие €зыки (ѕаскаль, јда, —и, ѕролог и др.). “ак, в систему можно добавить реализованные ранее на других €зыках части или сделать традиционное программирование более эффективным с помощью разнообразнейших средств, имеющихс€ на Ћисп-машине.

—оздание Ћисп-машин дало новый толчок развитию Ћиспа.  роме высокого быстродействи€ (перва€ же Ћисп-машина работала в несколько раз быстрее, чем ћаклисп) и огромной виртуальной списковой пам€ти, достоинством Ћисп-машин €вл€етс€ и то, что дл€ них это единственный €зык программировани€. Ќа нем написаны все системные программы, начина€ с ќ— и конча€ всевозможными препроцессорами, и программы пользовател€. “ака€ однородность значительно упрощает как разработку самих системных компонентов, так и взаимодействие с ними. ѕо сути дела, на Ћисп-машинах стираетс€ грань между системным и прикладным программным обеспечением. ¬ насто€щее врем€ Ћисп-машины выпускаютс€ р€дом фирм —Ўј, японии и «ападной ≈вропы. ¬ бывших социалистических странах также имеютс€ положительные примеры разработки таких машин.[7]

1.3.3 ¬ыводы.

—овременные диалекты €зыка Ћисп можно рассматривать как мощные интерактивные системы программировани€. Ёто объ€сн€етс€ двум€ причинами. ¬о-первых, сам €зык Ћисп претерпевает серьезные изменени€ - развиваютс€ средства €зыка, предназначенные дл€ обработки нетрадиционных дл€ Ћиспа типов данных: массивов, векторов, матриц; по€вл€ютс€ некоторые средства управлени€ пам€тью (пакеты), отсутствующие в Ћиспе. —ерьезные изменени€ претерпевают и управл€ющие структуры. ѕо€вились несвойственные природе €зыка Ћисп функции, заимствованные из ‘ортрана, јлгола, ѕаскал€, —и: Do, Loop, Goto , Case и прочие, позвол€ющие пользователю, незнакомому с принципами функциональных €зыков, легко переходить на Ћисп.  ачество программ снижаетс€, зато возрастает попул€рность €зыка. ¬о-вторых, если на первом этапе развити€ Ћисп-системам была присуща небольша€ скорость обработки данных и серьезные ограничени€ на емкость используемой оперативной пам€ти, то† современные Ћисп-системы уже могут соперничать по этим параметрам с такими €зыками, как —и, ѕаскаль и др. »спользование Ћисп-машин вообще практически снимает ограничени€ пам€ти и быстродействи€.

ƒл€ ѕЁ¬ћ ограничени€ по пам€ти и быстродействию все еще остаютс€ существенными. ќднако положение не безнадежно. –азвитие Ћисп-систем дл€ ѕЁ¬ћ идет сегодн€ по трем различным направлени€м. ѕервое св€зано с увеличением емкости пам€ти, котора€ может использоватьс€ Ћисп-системой. — этой целью р€д компаний разработал версии €зыка Golden Common Lisp, использующие расширени€ оперативной пам€ти и виртуальную пам€ть. ¬торое направление св€занно с повышением быстродействи€ Ћисп-систем. “ретье направление состоит в разработке эффективных компил€торов программ с €зыка Ћисп в традиционные €зыки (чаще всего в €зык —и).

ѕоложительным нововведением в современные диалекты €зыка можно считать псевдоассемблерные команды, которые позвол€ют оперировать основными регистрами машины и организовывать прерывани€ на уровне DOS и† BIOS.  роме того, многие Ћисп-системы имеют хорошие интерфейсы с другими €зыками (‘ортран, ѕаскаль, јссемблер, —и), что позвол€ет повысить эффективность прикладных Ћисп-программ.

≈сли же говорить о глобальной тенденции развити€ самой идеологии €зыка Ћисп, то очевидно, что она св€зана с созданием объектно-ориентированных версий €зыка как наиболее пригодных дл€ реализации систем »».

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

1. †ћожно предположить, что Ћисп еще значительное врем€ будет оставатьс€ основным €зыком дл€ реализации интеллектуальных систем.

2. †”же в ближайшее врем€ можно ожидать по€влени€ €зыков, вобравших в себ€ лучшие черты Ћиспа и др. €зыков† программировани€ »».

3. †Ќаблюдаетс€ €вна€ тенденци€ к созданию параллельных версий €зыков дл€ программировани€ задач »». языки типа Ћисп, ѕролог, –ефал (а также всевозможные модификации и Ђсмесиї этих и/или других €зыков символьной обработки) будут все больше уступать свои позиции на уровне инженеров по знани€м специальным €зыкам представлени€ знаний, остава€сь инструментарием системных программистов.†††

†† Ќа основании анализа сравнительных характеристик дл€ изучени€ €зыка Ћисп в курсе лабораторных работ по предмету Ђ—истемы искуственного интеллектаї† был выбран диалект муЋисп. ¬ыбор этого диалекта основан на следующих его особенност€х:

1. †ѕростота в изучении (благодар€ небольшому набору базовых функций).

2. †Ѕлизость к стандарту €зыка.

3. †¬озможность пополнени€ базового набора функций.

4. †ƒополнительные библиотеки Ћисп-функций, расшир€ющие базовый набор функций, имеющимис€ в диалектах  оммон Ћисп и »нтерлисп, а также библиотеками, позвол€ющими выполн€ть манипулирование окнами на экране диспле€ и работать с устройством Ђмышьї.

5. †ƒополнительное программное обеспечение к интерпретатору: интерактивный редактор текстов и проста€ обучающа€ система.

†††


†††††††††††††††† 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 —писочна€ €чейка.

Ћогически идентичные атомы содержатс€ в системе лишь один раз. Ќо логически идентичные списки могут быть представлены различными списочными €чейками. Ќапример, список ((d c) a d c) изображаетс€ как показано на рис.4. ¬ результате вычислений в пам€ти могут возникнуть структуры на которые нельз€ потом сослатьс€. Ёто происходит, если структуры не сохранены с помощью функции SETQ или тер€етс€ ссылка на старое значение в св€зи с новым переприсваиванием.


††††††††††††††††††† †A††††††††††††† †††††††D††††††††††††††††††† C


††††††††††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

–ис.4 ††


††††††††††††††††††††††††† A††††††††††††† †††††††D††††††††††††††††††† C


рис.5

¬ зависимости от способа построени€ логическа€ и физическа€ структуры двух списков могут оказатьс€ различными. Ќапример, список ((d c) 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 списка, €вл€ющегос€ вторым аргументом функции. Ќапример в случае одного списка получаетс€ следующее выражение:

(MAPCAR fn С(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-выражени€. ќбращени€ к этим функци€м имеют следующий вид:

(APPLY fun arg)

(FUNCALL fun 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. ‘реймы. Ёто частный случай семантических сетей. Ёто метод представлени€ знаний,† который св€зывает† свойства† с узлами , представл€ющими пон€ти€ и объекты. —войства описываютс€ атрибутами (называемыми слотами) и их значени€ми. »спользование фреймов с их атрибутами и взаимосв€з€ми позвол€ет хранить знани€ о† предметной† области† в структурированном† виде,† представл€ть в Ѕ« абстракции и аналогии.

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

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

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


Ћабораторна€ работа є 1.

“ема: ќзнакомительна€ работа в среде MuLisp. Ѕазовые функции Ћиспа. —имволы, свойства символов. —редст-ва €зыка дл€ работы с числами.

÷ель: ќзнакомитьс€ со средой MuLisp. »зучить базовые функции Ћиспа, символы и их свойства, а также средства дл€ работы с числами.

1. †ќсновные положени€ программировани€ на Ћиспе.

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

3. †Ѕазовые функции €зыка. —имволы, свойства символов.

4. †—редства €зыка дл€ работы с числами.

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

6. †¬опросы.

1. ќсновные положени€ программировани€ на Ћиспе.

n † списочных структур, л€мбда-исчислении и теории рекурсий.

n †ЂENTERї.

n QUOTE.

n

n

n

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

—писок - упор€доченна€ последовательность, элементами которой €вл€ютс€ атомы либо списки. —писки заключаютс€ в круглые скобки, элементы списка раздел€ютс€ пробелами. Ќесколько пробелов между символами эквивалентны одному пробелу. ѕервый элемент списка называетс€ Ђголовойї, а остаток , т. е. список без первого элемента, называетс€ Ђхвостом. —писок в котором нет ни одного элемента, называетс€ пустым и обозначаетс€ Ђ()ї либо NIL.††††††††

n MuLisp, прописные и строчные буквы отождествл€ютс€ и представл€ютс€ прописными буквами.

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

n MuLispом нового символа, за его величину принимаетс€ он сам. “ака€ ссылка символа на себ€ называетс€ автоссылкой.

n LSP.

n † всю† программу† в одну строку. ќднако отступы в строках и пустые строки делают структуру программы пон€тней и более читабельней. “ак же выравнивание начальных и конечных скобок основных выражений помогают† убедитьс€† в балансе ваших скобок.

n † загружатьс€† использу€† функцию† LOAD:

(load <им€ файла>)

Ёта функци€ загружает файл выражений и† выполн€ет† эти выражени€. <»м€ файла> - это строкова€ константа, котора€ представл€ет собой† и숆 файла† без† расширен舆 (подразумеваетс€† расширение ".lsp"). ≈сли† операц舆 успешно завершена, LOAD возвращает им€ последней функции, определенной в файле. ≈сли операци€ не выполнена, LOAD возвращает им€ файла в виде строкового выражени€.

‘ункци€ LOAD не может вызыватьс€† из† другой† функции† LISP.† ќна должна† вызыватьс€† непосредственно с клавиатуры, в то врем€ как† ни† одна† друга€† функц舆 LISP не находитс€ в процессе выполнени€.†††††††††††††††

n LSP.

n MuLisp включает в себ€ сравнительно небольшой набор базовых функций, указанна€ Ћисп-система обеспечиваетс€ библиотеками Ћисп-функций, дополн€ющими базовый набор функци€ми, имеющимис€ в Common Lisp-е и других диалектах(Common.lsp, †Array.lsp и т. д. ...).

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

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

MuLisp87.com Common.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ї.

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

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

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

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

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

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

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

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

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

n Search: поиск строки. ѕричем строчные и прописные буквы различаютс€.

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

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

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

3. Ѕазовые функции €зыка.

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

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

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

_(CAR С(a b c d)) ð a

_(CAR С((a b) c d)) ð (a b)

_(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 c d)) ð (b c d)

_(CDR С((a b) c d)) ð (c d)

_(CDR С(a (b c d))) ð ((b c d))

_(CDR С(a)) ð NIL

_(CDR NIL) ð NIL

_(CDR Сa) ð Error

‘ункци€ создани€ CONS.

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

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

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

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

_(CONS Сa С(b c)) ð (a b c)

_(CONS С(a b) С(c d)) ð ((a b) c d)

_(CONS (+ 1 2) С(+ 3)) ð (3 + 3)

_(CONS С(a b c) NIL) ð ((a b c))

_(CONS NIL С(a b c)) ð (NIL a b c)

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

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

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

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

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

_(ATOM Сa) ð T

_(ATOM С(a b c)) ð 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 b c) С(a b c)) ð T

_(EQUAL С(a b c) С(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 С((a b c d) e)) ð (c d)

_(CDDR С(k l m)) ð (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 С(b c d)) ð (b c d)

_a ð(b c d)

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

_a ð (b c d)

_(CAR a) ð b

_b ð (f g)

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

_(Symbol-value (CAR a)) ð (f g)

‘ункци€ SETQ - св€зывает им€, не вычисл€€ его. Ёта функци€ отличаетс€ от SET тем, что вычисл€ет только второй аргумент.†

_(SETQ d С(l m 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 (как и в Common Lisp) отдельной функции нет. ƒл€ этого используютс€ уже известные нам функции:

(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), (h x (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.  аково значение каждого из следующих выражений:

a) †(ATOM (CAR (QUOTE ((1 2) 3 4))));

b) †(NULL (CDDR (QUOTE ((5 6) (7 8)))));

c) †(EQUAL (CAR (QUOTE ((7 )))) (CDR (QUOTE (5 7))));

d) †(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)

†††††††††††† (cons x (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 С(b c d)) ð (b c d)

_(RPLACA a Сd) ð (d c d)

_(RPLACD a С(o n m)) ð (d o n m)

_a ð (d o n m)

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

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

a) †+y-x*y;

b) †x*x+y*y;

c) †x*y/(x+y)-5*y;

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

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

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

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

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

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

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

b) †

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

d) †

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

a) †n-ый элемент L† есть 12;

b) †n-ый элемент L есть атом;

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

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

8. Ќапишите функцию, котора€ спрашивает у пользовател€ ‘»ќ студента из группы (список группы составлен раньше) и выдает следующие данные о нем:

a) †

b) †

c) †

d) ††††

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

a) †

b) †

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

a) †x = Т(a b);

b) †x = Т(a);

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

a) †(RPLACD С(a) Сb);

b) †(RPLACA С(a) Сb);

c) †(RPLACD (CDDR С(a b x)) Сc);

d) †(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 x y)) ð (a b)

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

†††††††††† (LIST x y)) ð ERROR

ѕри вычислении у ” и ’ еще нет св€зи. «начени€ переменным присваиваютс€ одновременно. Ёто означает, что значени€ всех переменных mi вычисл€ютс€ до того, как осуществл€етс€ св€зывание с формальными параметрами.

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

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

††††††††††† (LIST x y)) ð (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))

†††††††††††† ((< x 0) (SETQ x -x) (SETQ рез х))

†††††††††††† ((= х 0))

† †††††††††††(“ Сошибка))

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

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

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

≈сли выполн€етс€ условие (т. е. х>0), то к значению y прибавл€етс€ значение х, иначе (x<0) от y отнимаетс€ отрицательное значение х, т. е. прибавл€етс€ абсолютное его значение.

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

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

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

(CASE ключ

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

††††††††††† (список-ключей2 m21 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))

††††††††† ((< x 10) рез)

††††††††† (SETQ рез (+ рез x y))

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)

††††† ††С(+ 1 2) Сc);

b) ((LAMBDA (x y) ((LAMBDA (z) (LIST x y z)) Сc)

††††† ††Сa Сb);

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

†††† †††((LAMBDA (z) z) Сa)

†††† †††Сb).

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

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

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

a) †NIL, если L атом, и T в противном случае;

b) †L ,состо€щего из трех элементов, первый из этих трех, который €вл€етс€ атомом, или список, если в списке нет элементов атомов.

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

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

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

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

9. »спользу€ функцию COND, напишите функцию, котора€ спрашивает у пользовател€ ‘»ќ двух студентов из группы (список группы составлен раньше) дл€ которых:

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

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

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

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

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

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

(DEFUN center (x y z)

†††††††† (COND ((> x y) (IF (< x z) (PROGN (PRINT x)

††††††††††††††††††††††††††††††††††††††††† †††††††††††††††††††††††(PRINT Ђсреднее (1)ї))

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

†††††††††††††††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††††††††(TERPRI)

†††††††††††††††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††††††††(PRINT Ђсреднее (2)ї))

†††††††††††††††††††††††††††††††††††††††††††† †††††††††††††††††††††(PROGN (PRIN1 z)

†††††††††††††††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††††††††(PRIN1Ђсреднее (3)ї)))))

†††††††††††††††††††††††††† ((< x y) (IF (< y z) (PROGN (PRIN1 y)

†††††††††††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††(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. –екурси€. –азличные формы рекурсии.

ќсновна€ иде€ рекурсивного определени€ заключаетс€ в том, что функцию можно с помощью рекуррентных формул свести к некоторым начальным значени€м, к ранее определенным функци€м или к самой определ€емой функции, но с более Ђпростымиї аргументами. ¬ычисление такой функции заканчиваетс€ в тот момент, когда оно сводитс€ к известным начальным значени€м.

–екурсивна€ процедура, во-первых содержит всегда по крайней мере одну терминальную ветвь и условие окончани€. ¬о-вторых, когда процедура доходит до рекурсивной ветви, то функционирующий процесс приостанавливаетс€, и новый такой же процесс запускаетс€ сначала, но уже на новом уровне. ѕрерванный процесс каким-нибудь образом запоминаетс€. ќн будет ждать и начнет исполн€тьс€ лишь после окончани€ нового процесса. ¬ свою очередь, новый процесс может приостановитьс€, ожидать и т. д.

Ѕудем говорить о рекурсии по значению и рекурсии по аргументам. ¬ первом случае† вызов €вл€етс€ выражением, определ€ющим результат функции. ¬о втором - в качестве результата функции возвращаетс€ значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции. јргументом рекурсивного вызова может быть вновь рекурсивный вызов и таких вызовов может быть много.

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

n

n

n

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

ƒл€ примера напишем функцию вычислени€ чисел ‘ибоначчи (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 С+) ð +

_(APPLY a С(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† 1 2) ð 3

_(LIST 1 2) ð (1 2)

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

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

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

MAPCAR.

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

(MAPCAR fn С(x1 x2 ... xn))

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

_(MAPCAR СLISTP С((f) h k (i u)) ð (T NIL NIL T)

_(SETQ x С(a b c)) ð (a b c)

_(MAPCAR СCONS x С(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. Ќапишите функцию:

a) †

b) †

c) †

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

a) †X и N, котора€ создает список из N раз повторенных элементов X;

b) †

c) †(a b) ð ((a) (b));

d) †

e) †

f)   X, N и V, добавл€ющую X на N-е место в список V.

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

a) †SUBST, но в которой третий аргумент W об€зательно должен быть списком;

b) †X на Y только на верхнем уровне W;

c) †Y на число, равное глубине вложени€ Y в W, например Y=A, W=((A B) A (C (A (A D)))) ð ((2 B) 1 (C (3 (4 D))));

d) †SUBST, но производ€щую взаимную замену X на Y, т. е. X ð Y, Y ð X.

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

a) †(APPLY СLIST С(a b));

b) †(FUNCALL СLIST С(a b));

c) †(FUNCALL СAPPLY СLIST С(a b));

d) †(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.

(DEFUN subst (x y w)

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

††††††††††††††††††††††††††† ((EQUAL Сy Сw) x)†

†††††††††††††††††††††† †††††((ATOM Сw) w)††††† ;

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

††††††††††††††††††††††††††††††††††††††††††† (subst x 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< строка1 строка2)

(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 С(5 4)

†† :ELEMENT-TYPE СATOM

†† :INITIAL-ELEMENT A)) ð (ARRAY ((A A A A) ... (A A A A) (5 6)))

_(SETF (AREF мас 0 1) B) ð B

_мас ð (ARRAY ((A B 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 *правила* '(prav1 prav2 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.com Common.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.ѕереведите следующие списочные записи в точечные:

a) †(w (x));

b) †((w) x);

c) †(nil nil nil);

d) †(v (w) x (y z));

e) †((v w) (x y) z);

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

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

a) †;

b) †((a . nil) . nil);

c) †(nil . (a . nil));

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

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

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

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

a) †pairlis, котора€ строит список пар;

b) †assoc, котора€ ищет пару, соответствующую ключу.

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

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

a) †

b) †

c) †

d) †EXSIS.LSP), и котора€ выполн€ла бы их в диалоговом режиме.

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

7. –азработайте базу знаний и правила базы знаний –ј—ѕ»—јЌ»≈ «јЌя“»… использу€:

a) †

b) †

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ом и определенные нами в предыдущих лабораторных работах.

(+ <число> <число>...)

(- <число> <число>...)

(* <число> <число>...)

(/ <число> <число>...)

(= <атом> <атом>...)

(/= <атом1> <атом2>)

(< <атом> <атом>...)

(<= <атом> <атом>...)

(> <атом> <атом>...)

(>= <атом> <атом>...)

(and <выражение>...)

(atom <элемент>)

(boundp <атом>)

(car <список>)

(cdr <список> )

(cond (<тест1> <результат>...)...)

(cons <первый элемент> <список>)

(defun <символ> <список аргументов> <выражение>...)

(eq <выражение1> <выражение2>)

(if <текст-выражение> <выражение-тогда> [<выражение-иначе>])

(lambda <аргументы> <выражение> ...)

(list <выражение> ...)

(listp <элемент>)

(mapcar <функци€> <список1>...<списокn>)

(not <элемент>)

(null <элемент>)

(numberp <элемент>)

(or <выражение>...)

(princ <выражение> [<описатель файла>])

(print <выражение> [<описатель файла>])

(progn <выражение>...)

(quote <выражение>)

(read <строка>)

(set <символ> <выражение>)

(setq <символ1> <выражение1> [<символ2> <выражение2>]...)

(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> <строка2>...)

Ёта† функц舆 возвращает† строку,† котора€† €вл€етс€ результатом сцеплени€ строки1>, <строки2> и т.д. Ќапример:

(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 - обращает верхний уровень списка

(DEFUN REVERSE1 (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 <число1> <число2>) ‘ункц舆 возвращает† наибольший† общий делитель <числа1> и <числа2>. <„исло1> и <число2> должны быть целыми.

5. а) (first <список>), second, third, и т. д. возвращающие соответственно первый, второй, третий, и т. д. элемент списка.

††† в) (last <список>) Ёта функци€ возвращает последний† элемент† списка.† <—писок>† не должен быть равен nil. LAST возвращает либо атом либо список.

6. а) (max <число> <число>...) Ёта функци€ возвращает наибольшее из† заданных чисел.

††† в) (min <число> <число> ...) Ёта функци€ возвращает наименьшее из заданных чисел.

7. а) (evenp <число>) ѕровер€ет, четное ли число. ќна возвращает T - если число четное и NIL† - в противном случае.

††† в) (oddrp <число>) Ёта функци€ - противоположна€ по действию функции evenp.

8. котора€ сортирует числа:

а) по возрастанию.

в) по убыванию.

9. предикат - который определ€ет:

а) числа с плавающей зап€той.

в) целые числа.

г) строковые константы.

д) символы.

е) списки.

10. завис€щую от одного аргумента, котора€ генерирует все циклические перестановки списка.

11. завис€щую от одного элемента, котора€ по данному списку вычисл€ет список его элементов:

а) встречающихс€ в нем более 1, 2, ... раз.

в) встречающихс€ в нем не менее 2, 3, ... раз.

P. †S. «апишите все функции, написанные вами, в один файл. ƒл€ отладки программы используйте встроенные средства dlispа.

5. ¬опросы.

1.  акие способы тестировани€ программ предусмотрены в dlisp?

2. ¬ чем их различи€?

3.  акие функции предусмотрены дл€ работы со строковыми константами в dlisp?

4. Ќазовите их основные особенности?

††††††††††††††††††††††††††† «аключение.

¬ результате выполнени€ дипломной работы было проделано следующее:

n †††††ѕроведен анализ €зыков программировани€ »», а также диалектов и систем Ћиспа.

n †††††¬ качестве теоретических сведений рассмотрены основные особенности и возможности €зыка Ћисп.

n †††††–азработан комплекс лабораторных работ по изучению €зыка††††††† MuLisp дл€ студентов специальности Ђ омпьютерные и интеллектуальные системы и сетиї, имеющих следующие темы:

Ћабораторна€ работа є1.

“ема: ќзнакомительна€ работа в среде MuLisp. Ѕазовые функции Ћиспа. —имволы, свойства символов. —редства €зыка дл€ работы с числами.

÷ель: ќсвоить среду MuLisp. »зучить базовые функции Ћиспа, символы и их свойства, а также средства дл€ работы с числами.

Ћабораторна€ работа є2.

“ема: ќпределение функций. ‘ункции ввода-вывода. ¬ычислени€, измен€ющие структуру.

÷ель: ѕолучить навыки в написании функций на Ћиспе. »зучить функции ввода- вывода.

Ћабораторна€ работа є3.

“ема: ќрганизаци€ вычислений в Ћиспа.

÷ель: »зучить основные функции и их особенности дл€ организации вычислений в Ћиспе.

Ћабораторна€ работа є4.

“ема: –екурси€ в Ћиспе. ‘ункционалы и макросы.

÷ель: »зучить основы программировани€ с применением рекурсии. Ќаучитс€ работать с функционалами и макросами.

Ћабораторна€ работа є5.

“ема: “ипы данных, используемые в MuLisp. “очечное представление списков. ѕредставление знаний.

÷ель: »зучить основные типы данных MuLisp. –азобратьс€ с точечной нотацией списков.

Ћабораторна€ работа є6.

“ема: »зучение учебной версии интегрированной среды dlisp. –асширение библиотеки функций dlisp.

÷ель: ќзнакомитьс€ с учебной версией интегрированной среды dlisp. »зучить ее возможности и особенности. –асширить библиотеку функций dlisp.

n †††††–азработаны задани€, требующие индивидуальной работы студента и контрольные вопросы, позвол€ющие оценить уровень знаний студента по каждой теме.

n †††††„асть лабораторных работ была выполнена студентами 5-го курса специальности Ђ омпьютерные и интеллектуальные системы и сетиї, после чего были проработаны (изучены и исправлены) недостатки, а так же расширен круг вопросов, раскрываемых в лабораторных работах.

††††††††††††††††††††††††††††††††††††††††† †††††††††¬ведение. ¬ последнее врем€ особый интерес приобрела технологи€ искусственного интеллекта (»»). ¬ычислительные устройства, обладающие в той или иной степени Ђинтеллектуальными способност€ми, стал

 

 

 

¬нимание! ѕредставленна€ –абота находитс€ в открытом доступе в сети »нтернет, и уже неоднократно сдавалась, возможно, даже в твоем учебном заведении.
—оветуем не рисковать. ”знай, сколько стоит абсолютно уникальна€ –абота по твоей теме:

Ќовости образовани€ и науки

«аказать уникальную работу

ѕохожие работы:

ћетодическа€ разработка по C++
ќписание €зыка Turbo Basic дл€ студентов всех специальностей
ќбучение начальных курсов методам программировани€ на €зыке Turbo Pascal
—труктура и реализаци€ макро€зыков
»нформационные технологии в экономике. –азработка информационных технологий.
»нформационные технологии в экономике. —редства организации экономико информационных систем
ѕолучение уравнени€ переходного процесса по передаточной функции
Ћекции по курсу "»нформатика"
—оциальна€ информатика
—истемное программирование

—вои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru