L_OBZOR (ЛИСП)

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

1. Краткая история развития искусственного интеллекта.

Искусственный интеллект (ИИ) - это область исследований, находящаяся на стыке наук, специалисты, работающие в этой области, пытаются понять, какое поведение, считается разумным (анализ), и создать работающие модели этого поведения (синтез). Практической целью является создание методов и техники, необходимой для программирования «разумности» и ее передачи вычислительным машинам (ВМ), а через них всевозможным системам и средствам.[1]

В 50-х годах исследователи в области ИИ пытались строить разумные машины, имитируя мозг. Эти попытки оказались безуспешными по причине полной непригодности как аппаратных так и программных средств.

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

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

И только в конце 70-х годов была принята принципиально новая концепция, которая заключается в том, что для создания интеллектуальной программы ее необходимо снабдить множеством высококачественных специальных знаний о некоторой предметной области. Развитие этого направления привело к созданию экспертных систем (ЭС).[6]

В 80-х годах ИИ пережил второе рождение. Были широко осознаны его большие потенциальные возможности как в исследованиях, так и в развитии производства. В рамках новой технологии появились первые коммерческие программные продукты. В это время стала развиваться область машинного обучения. До этих пор перенесение знаний специалиста-эксперта в машинную программу было утомительной и долгой процедурой. Создание систем, автоматически улучшающих и расширяющих свой запас эвристических (не формальных, основанных на интуитивных соображениях) правил - важнейший этап в последние годы. В начале десятилетия в различных странах были начаты крупнейшие в истории обработки данных национальные и международные исследовательские проекты, нацеленные на «интеллектуальные ВМ пятого поколения».[1]

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

• обработка естественного языка;

• экспертные системы (ЭС);

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

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

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

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

• и др.

1.2 Языки программирования ИИ.

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

Все языки программирования можно разделить на процедурные и декларативные языки. Подавляющее большинство используемых в настоящее время языков программирования (Си, Паскаль, Бейсик и т. п.) относятся к процедурным языкам. Наиболее существенными классами декларативных языков являются функциональные (Лисп, Лого, АПЛ и т. п.) и логические (Пролог, Плэнер, Конивер и др.) языки (рис.1).

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

Процедурная программа состоит из последовательности операторов и предложений, управляющих последовательностью их выполнения. Типичными операторами являются операторы присваивания и передачи управления, операторы ввода-вывода и специальные предложения для организации циклов. Из них можно составлять фрагменты программ и подпрограммы. В основе процедурного программирования лежат взятие значения какой-то переменной, совершение над ним действия и сохранения нового значения с помощью оператора присваивания, и так до тех пор пока не будет получено (и, возможно, напечатано) желаемое окончательное значение.[2]

ЯЗЫКИ ПРОГРАММИРОВАНИЯ

П РОЦЕДУРНЫЕ ЯЗЫКИ ДЕКЛАРАТИВНЫЕ ЯЗЫКИ

П аскаль, Си, Фортран, ...

ЛОГИЧЕСКИЕ ЯЗЫКИ ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ

Пролог, Mandala... Лисп, Лого, АРЛ, ...

Рис.1 Классификация языков программирования

Логическое программирование - это один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна. Логика предикатов первого порядка - это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений. Логическое программирование базируется на подмножестве логики предикатов первого порядка, при этом оно одинаково широко с ней по сфере охвата. Логическое программирование дает возможность программисту описывать ситуацию при помощи формул логики предикатов, а затем, для выполнения выводов из этих формул, применить автоматический решатель задач (т. е. некоторую процедуру). При использовании языка логического программирования основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать. Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ.[8].

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

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

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

1. Сравнительные характеристики языков ИИ.

На первом этапе развития ИИ (в конце 50-х - начале 60-х годов) не существовало языков и систем, ориентированных специально на области знаний. Появившиеся к тому времени универсальные языки программирования казались подходящим инструментом для создания любых (в том числе и интеллектуальных ) систем, поскольку в этих языках можно выделить декларативную и процедурную компоненты. Казалось, что на этой базе могут быть интерпретированы любые модели и системы представления знаний. Но сложность и трудоемкость таких интерпретаций оказались настолько велики, что прикладные системы для реализации были недоступны. Исследования показали, что производительность труда программиста остается постоянной независимо от уровня инструментального языка, на котором он работает, а соотношение между длиной исходной и результирующей программ примерно 1:10. Таким образом, использование адекватного инструментального языка повышает производительность труда разработчика системы на порядок, и это при одноступенчатой трансляции. Языки предназначенные для программирования интеллектуальных систем содержат иерархические (многоуровневые) трансляторы и увеличивают производительность труда в 100-ни раз. Все это подтверждает важность использования адекватных инструментальных средств.[7]

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

Лисп.

Язык Лисп был разработан в Стэнфорде под руководством Дж. Маккарти в начале 60-х годов. По первоначальным замыслам он должен был0 включать наряду со всеми возможностями Фортрана средства работы с матрицами, указателями и структурами из указателей и т. п. Но для такого проекта не хватило средств. Окончательно сформированные принципы положенные в основу языка Лисп: использование единого спискового представления для программ и данных; применение выражений для определения функций; скобочный синтаксис языка.[4]

Лисп является языком низкого уровня, его можно рассматривать как ассемблер, ориентированный на работу со списковыми структурами. Поэтому на протяжении всего существования языка было много попыток его усовершенствования за счет введения дополнительных базисных примитивов и управляющих структур. Но все эти изменения , как правило, не становились самостоятельными языками. В новых своих редакциях Лисп быстро усваивал все ценные изобретения своих конкурентов.[2]

После создания в начале 70-х годов мощных Лисп-систем Маклисп Интерлисп попытки создания языков ИИ, отличных от Лиспа, но на той же основе, сходят на нет. Дальнейшее развитие языка идет, с одной стороны, по пути его стандартизации (Стандарт-Лисп, Франц-Лисп, Коммон Лисп), а с другой - в направлении создания концептуально новых языков для представления и манипулирования знаниями в Лисп среде. В настоящее время Лисп реализован на всех классах ЭВМ, начиная с ПЭВМ и кончая высоко производительными вычислительными системами.

Лисп - не единственный язык, используемый для задач ИИ. Уже в середине 60-х годов разрабатывались языки, предлагающие другие концептуальные основы. Наиболее важные из них в области обработки символьной информации - СНОБОЛ и Рефал.

СНОБОЛ.

Это язык обработки строк, в рамках которого впервые появилась и была реализована в достаточно полной мере концепция поиска по образцу. Язык СНОБОЛ был одной из первых практических реализаций развитой продукционной системы. Наиболее известная и интересная версия этого языка - Снобол-4 Здесь техника задания образцов и работа с ними существенно опередили потребности практики. По существу, он так и остался «фирменным» языком программирования, хотя концепции СНОБОЛа, безусловно, оказали влияние и на Лисп, и на другие языки программирования задач ИИ.

Рефал.

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

В основу языка Рефал положено понятие рекурсивной функции, определенной на множестве произвольных символьных выражений. Базовой структурой данных этого языка являются списки, но не односвязные, как в Лиспе, а двунаправленные. Обработка символов ближе к продукционной парадигме. При этом Активно используется концепция поиска по образцу, характерная для СНОБОЛа.

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

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

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

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

Таким образом, Рефал вобрал в себя лучшие черты наиболее интересных языков обработки символьной информации 60-х годов. В настоящее время язык Рефал используется для автоматизации построения трансляторов, систем аналитических преобразований, а также, подобно Лиспу, в качестве инструментальной среды для реализации языков представления знаний.[7]

Пролог.

В начале 70-х годов появился новый язык составивший конкуренцию Лиспу при реализации систем, ориентированных на знания - Пролог. Этот язык не дает новых сверхмощных средств программирования по сравнению с Лиспом, но поддерживает другую модель организации вычислений. Его привлекательность с практической точки зрения состоит в том, что, подобно тому, как Лисп скрыл от программиста устройство памяти ЭВМ, Пролог позволил ему не заботится о потоке управления в программе.[8]

Пролог - европейский язык, был разработан в Марсельском университете в 1971 году. Но популярность он стал приобретать только в начале 80-х годов. Это связано с двумя обстоятельствами: во-первых, был обоснован логический базис этого языка и, во-вторых, в японском проекте вычислительных систем пятого поколения он был выбран в качестве базового для одной из центральных компонент - машины вывода.