Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

сайт: http://al.cs.msu.su/malk/ai

Лектор понимает, что научиться лиспу или пленнеру за 1—2—3 лекции нельзя. Ясно, что мы должны здесь получить какое-то понятие. Если кто-то знаком кто-то с Лиспом и Пленнером, то хорошо.

Вопросы к экзамену по предыдущей лекции:

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

Сегодня лектор расскажет в пленнере про аппарат блоков, такой же есть в Лиспе, но есть отличия.

[править] Раздел 2. ПО работ по ИИ

Создание интеллектуальной системы — процесс сложный, итеративный. Интеллектуальная деятельность человека очень сложна и слабо изучена. Поэтому хотелось бы иметь языки сверхвысокого уровня для быстрого прототипирования. Хотелось бы, чтобы язык был исследовательской. Хотелось бы, чтобы система работала, но допустимо, что она решала более простые задачи, работала долго.

Какие есть ещё задачи с точки зрения программирования:

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

динамику проблемной среды

• Требуется решать переборные задачи
• Придётся использовать алгоритмы поиска по образцу и нам нужны гибкие структуры управления

Реально используются самые разные системы, используют эксп. системы-оболочки, используются различные лиспоподобные языки. Используются языки логического программирования (Пролог; про него рассказывает Захаров). Используются языки ООП. Языки на основе т. н. фреймов. Используются универсальные языки программирования (реальные системы написаны не на лиспе, а на с, с++, java; но тут можно утонуть в деталях, упустив самое важное). Используются т. н. языки, ориентированные на доступ. Используются и другие средства программной поддержки, средства отладки, соредства управления базами знаний.

Если мы посмотрим на Лисп:

• Работа со сложными структурами есть
• Хранилища --- где-то есть, где-то нет
• Симв данные есть
• Отр. среду --- есть
• Переборные алгоритмы --- можно организовать
• Алгоритмы поиска по образцу --- как таковых нет (пильщиков писал работу по поиску образцу в лиспе)

Блоки — позволяют использовать императивный стиль в лиспе.

[править] Пленнер

Один из потомков лиспа, созданный специально для работ по ИИ. /?/ Лектор склонен рассматривать Пленнер как среду для работ по ИИ.

Пленнер не прижился, так как претендовал на всеобъемлемость. Он не нашёл более-менее широкого применения.

Появился он в 70 году. Придумал его Карл Хьюетт (?). Он предложил его в диссере как некое теоретическое построение, в котором было всё, что требуется для работ по ИИ. Реализуют его обычно как надстройку над Лиспом.

Пильщиков выбрал пленнер как язык для диссера. И реализовал его на автокоде. И на защите Шура-Бура спросил, почему П. считает в восьмеричной системе, и Пильщиков ответил, что он работает на автокоде Чайковского (а не на БЭМШ, где 10-ричная система была, в отличие от автокода Чайковского)

Хьюетт не поверил, что Пленнер реализован в СССР на автокоде. Когда к нему подвели Пильщикова, то Х. с ужасом на него посмотрел.

Пленнер работал на БЭСМ-6 на порядок быстрее Лиспа. Причин несколько:

• Пильщиков --- один из лучших программистов в мире
• БЭСМ-6 во время реализации Лиспа была ещё новой и неотлаженной. В частности, там была такая интересная вещь: там операции обмена с памятью был страничный обмен и секторный. И там, где надо было поменять два сектора, меняли два сектора, а секторный обмен был реализован через страничный.

Вечерами лектор приходил на БЭСМ-6 ...

• Работа со списками в Пленнере (лисповская часть)

  В Пленнере немного другая организация списков. Это, так скажем, Лисп, но более богатый (как в рекламе нескафе, богатый, насыщенный). Можно только на нём программировать, и получается необыкновенно эффективный. Кроме того, там был компилятор, но скомпилировать можно не всё (например, нельзя скомпилировать функцию, которая выполняет аргумент).

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

• Пленнерская база данных

  Это не БД, а скорее blackboard. Это некоторая область,куда можно что-то набросать, а потом там искать и искать по образцу. Такого рода аппарат позволяет работать с моделями проблемной среды.

• Встроенный режим возвратов

  Помогает реализовать backtracking.

  • Есть поиск в глубь (бэктрекинг), а есть вширь, когда варианты раскидываются по процессам. Единственное, чего не было реализации Пильщикова, это аппарата параллелизма. Его потом реализовал его ученик на Эльбрусе. Потом Пильщиков реализовал пленнер для IBM PC, который написан на паскале, работа необыкновенно быстро и занимал с документацией 360 Кб

• Аппарат работы с образцами
• Аппарат теорем

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

[править] Примеры

Будет 3 лекции по 45---50 минут и лектор расскажет столько, сколько успеет. Остальное лектор расскажет на лекциях, которые выпросит обратно у Захарова, так как скорее всего в Севастополь не поедет.

• взять второй элемент с конца (с конца из-за минуса)

[ELEM -2 (A B C D)] → C — 

Появились квадратные скобочки (ещё есть угловые). Нет quote

• Пример сопоставления образца с выражением:

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

[IS (*x пришёл !*y)(Саша пришёл в магазин)] → T, x ← Саша,  y ← ( в магазин)

nil ≠ ()

• Утверждение пленнерской БД

(BOX A (3 7))

Это нек-рая конструкция, которая записывается в БД. Семантика м. б. такая: есть ящик, в нём есть A, стоит он в (3; 7).

• Запись утверждения в пленнерскую БД

[ASSERT (BOX A)(WITH COL RED)]

В БД записывается такое утверждение: (BOX A), и это утверждение получает список свойств (это некий ассоц. список, пары свойство=значение) ((COL RED))

• Поиск в БД

[SEARCH (BOX [])(TEST COL [NON GREEN])]

Найти (BOX <один элемент>), причём такой, что свойство COL у него не равно GREEN. Выдаются элементы в произвольном порядке

• Определение теоремы в пленнере

[DEFINE OCB(ERASING(x) (занят *x) [ASSERT (CB .x)])]

Интерпретация: если из БД вычёркивается утверждение «занят некоторый ящик», то нужно записать утверждение «этот ящик свободен»

[править] Подробнее о пленнере

[править] Какие выражения бывают в пленнере

Их гораздо больше, чем в пленнере (о_О). Иерархия:

• Выражения
  • Атомарные
    • Ображения к переменным
    • Атомы
      • Идентификаторы
      • Числа
      • Строки // в реализации для БЭСМ-6 были ещё и шкалы
  • Списковые
    • L-списки (...) //L от слова Лисп
    • P-списки [...] //P от слова пленнер
    • S-списки <...> //S от слова сегмент

В пленнере есть ограничители: пробел, скобка; точка ограничителем не является. Поэтому в лиспе есть такая проблема: (1.2) — 1.2 в скобках, а (1 . 2) — точечная пара. В пленнере таких проблем нет.

Есть цифры, есть буквы, есть специальные литеры (префиксы, «*», «!», «:», «+», «-»)

Префиксы используются для обращения к переменным.

• Префиксы
  • Простое обращение
    • «:», «.», «*»
  • Сегментное обращение
    • «!.», «!*», «!:»

Формы. Формы --- это выражения, которые принимают некоторые значения.

• Формы
  • Атомы. Значением атома является атом. Поэтому мы не должны его квотировать
  • Простые
    • Простые обращения к переменным (с префиксом «.»). Если мы просто обращаемся к переменной, то это значит, что мы хотим взять её значение.
    • Простые обращения к переменным (с префиксом «:»). Обращение к константам. Константы отличаются только этим.
    • L-списки — значением списка в круглых скобочках является список из значений его элементов.
    • P-списки. Обращение к процедурам.
  • Сегментные формы
    • Обращение к переменной с префиксом «!.». Пусть x → (A B), тогда !.x → A B //это не конструкция пленнера, на печать она выдана быть не может, но может быть вставлена в выражение. Например, есть y → (на лекции), и можнл использовать список (я сижу !.y) , который есть (я сижу на лекции)

      Сегментация — лишение внешних скобок

    • Обращение к переменной с префиксом «!:». Сегментное обращение к константам
    • S-списки. Сегментное обращение к функции. Пример:
  • [f a] → (A B)
  • <f a> → A B

В пленнере есть встроенные функции, есть определяемые. Есть втроенные и определяемые сопоставители. А теорем встроенных нет.

[править] Определение новых функций

[define f dexp]

• f — имя функции
• dexp == (lambda (v1 ... vk) e)

Если такую функцию определили, то можем обращаться: [f a1 ... ak].

Параметры вычисляются на момент входа.

В лиспе однонаправленные списки, поэтому главные функции --- car и cdr. В реализации пленнера Пильщикова списки реализованы массивом.

[править] Функции для работы со списком

• [elem n l] — n-й элемент из списка l. Если n < 0, то считается от конца.
  • [elem n .x] == [N .x]
• [rest n l] — результат отбразывания первых n элементов, если n > 0, и |n| последних элементов, если меньше
• [head n l] — n элементов от начала, или |n| элементов с конца

Пример:

[rest 2 [head 5 (1 2 3 4 5 6)]] → (3 4 5)

• (e1 ... en) → (E1 ... En)

Пример:

x → (1 2), y → (3 4)
(.x !.y) → ((1 2) 3 4)

Пример append:

(!.x !.y) → (1 2 3 4)

[править] Арифметические функции

• [+ n1 ... nk] → n1 + ... + nk
• [- a b]
• [max n1 ... nk]

И другие.

[править] Предикаты

T — истина, () — ложь. В лиспе и пленнере считается, что истина — всё, что не ложь.

• [num e] — вычисляется E, проверяется, является ли оно числом.
• [empty e] — является ли e пустым списком (T будет для «()», «[]», «<>»)
• [eq e1 e2] — сравнивает значения выражений, T если равны
  • [neq e1 e2]
• [memb e l] — вхождение любой формы e в l на внешнем уровне. Значением ф-ции является номер первого вхождения
• Есть больше, меньше, больше равно, меньше равно.
• Предикаты, проверяющие состояние переменных. Переменные могут находиться в разных состояниях.
  1. Переменная не описана
  2. Переменная без значения
  3. Переменная описана, имеет значение
  • [hasval v] — T, если переменная имеет значение
  • [bound v] — T, если переменная описана

Остались БД, бэктрекинг и теоремы. Перекличку организуем в конце следующего куска пары.

[править] Константы

Как и в лиспе, в пленнере — константы глобальной локализации.

[править] Функции ввода-вывода

В пленере достаточно богатый набор ф-ций ввода-вывода. Есть функции для работы с ФС, файлами, строками, текстом, есть функции управления терминалом.

Лектор делал систему контроля публикаций, она была гораздо круче современных текстовых процессоров, отслеживалась семантика. /* лектор забыл, про что рассказывал */. Например, «я ножницами боюсь, когда они играют», тут нарушено правило русского языка, проективность, и это отслеживалось. «Были рассмотрены вопросы собственности армии ЧСФР, она может быть продана с аукциона», тут неоднозначность, к чему относится «она»: к «ЧСФР», к «армии» и к «собственности». Лектор решал очень сложную задачу — просмотреть некий текст, инструкцию, чтобы любой солдат прочитал правильно, и выполнил те действия, которые предусмотрены инструкцией. И если русский язык для человека родной, то он поймёт правильно, а если не родной

/*Есть гипотеза лингвистической относительности, что мышление человека зависит от того, какой язык для него родной.*/

то необязательно. И это очень важно. Компьютер отличается тем, что он проверяет все варианты, даже самые нелепые.

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

Есть функции для сопоставления файлов ОС переменнам пленнера. Файл может быть в состоянии открыт (не более 8), активен (не более 1), пассивен (сколько угодно)

[open screen get] — открываем экран на ввод с клавиатуры
[active screen get] — перевели экран в состояние активен
[cset a [read]]  — считывает с клавиатуры

пусть ввели (N O T), тогда a → (:) (N O T)

[cset b [rev :a]] — b → (:) (T O N)
[open ff put][active ff put]
[print :b] — напечатать в файл ff значение переменной b

[править] Специальные функции

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

Когда на БЭСМ-6 лектор сдавал в многозвёздный демо-версию, было нехорошо, когда возникала ошибка. Что они делали -- они обрамляли вызов функции в функцию catch, и выдавалась такая же ошибка, как ОС, и как бы это была не их ошибка, а ОС.

[catch e1 e2] — вычисляется форма e1. Если выражение окончилось успешно, то E1 выдаётся в качестве значения формы. Если в процессе выполнения возникла синтаксическая ошибка, то вычисляется e2. Можно посмотреть номер ошибки, контекст ошибки, и изнутри пленнерской программы можно было её исправить.

Самый большой опыт программирования на пленнере наверное у лектора.

[exit e fn n?] (n? — опциональный параметр). Из n-го по глубине рекурсивного обращения к fn происходит выход с E. Частный случай [exit () ()] — выскочить из любого места на внешний уровень.

• [time] — время с начала работы программы
• [clock] — астрономическое время
• [alt a] — преобразование атома в список

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

[править] Функции для работы со списками свойств

Хотелось бы, чтобы идентификатор A не был запачкан каким-то списком свойств.

A → (ind1 val1 ... indk valk)

• [plist i pl] — после выполнения идентификатор A получит вот такие свойства
• [put indm valm] — изменение свойства

Если некоторое свойство входит со значением пусто == оно не входит.

• [get i ind?] — если ind не задаём, то весь список, если задаём, то указаное свойство

[править] Логические свойства

Практически всё как в лиспе. Лектор их только перечислит not (одноместный), or (многоместный), and (многоместный), [cond (p1 e11 ... e1m) ... (pk ek1 ... ekm)]

[править] Блоки

• [prog (v1 ... vn) o1 ... ok]
  • vi — может иметь вид или идентификатора (тогда без значения), или (v (A B))
  • оператор присваивания: [set v e]
  • [return e] — вычисляется E, выскакиваем с ним
  • [go e] — переход по вычисляемой метке
    • каждый из операторов o1 ... ok — либо метка, либо нормальный оператор
  • составной оператор — [do e1 ... ek]
  • циклы: while, until, for, ещё есть loop для работы со списками:
    • [loop x l e1 ... ek] — вводится локальная переменная x, и к каждому элементу l применяется e1 ... ek (элемент находится в x)
      • пример:

[set L (1 2 3)]
[prog (R ()) [loop E L [set R (.E !.R) .R]]]

Лектор вспомнил ещё один казус, связанный с лиспом: кроме set, в лиспе есть (setq v l), где имя переменной не вычисляется, а знач. вычисляется. Переводчики книжки «Интегральные работы» решили проявить свою эрудицию и дать рашифровку имён функций, и setq расшифровали как «множество q».