3.12.3 Аппаратная реализация языка лисп

Существующие структуры компьютеров (Неймановская архитектура машин) не ориентированы нязык Лисп по 3-м причинам:

1. Для эффективной реализации Лисп-машины требуется большое адресное пространство.

2. Частое использование стека требует аппаратной реализации стека большого объема.

3. Требуется наличие средств обработки тегов.

Лисп-машины впервые появились в начале 70-х годов, 1-ая машина называлась CONS, 2-ая – CADR – по имени выполняемых функций.

Сейчас, существует 4 фирмы, производящие Лисп-машины:

Symbolic (64 разряда), Xerox, LMI, TI (Explorer) - машины, аппаратно реализующие Лисп.

Обобщенная структурная схема ЛИСП-машины

• ПИ - процессор трансляции. Переводит исходные тексты (s-выражения) программ в макрокоманды и виртуальную Лисп-машину.

• ПИ - процессор интертрепации. Выполняет макрокоманды.

• ПП - процессор памяти. Осуществляет управление ОП; реализует функции по размещению структур данных в памяти и сборке мусора

• ПО - процессор обмена. Служит для передачи и обмена данных.

• СП - сервисный процессор. Выполняет диагностику и тестирование Лисп-машины.

• ОП - оперативная память.

Лисп-машина очень часто не является самостоятельным устройством, а подключается к ЭВМ через мультиплексный канал. Такая система реализуется например в машинах фирмы Fujitsu (FACOM).

4 Математические основы логического вывода

Логический вывод базируется на теории вычисления высказываний и теории исчисления предикатов.

Выссказыванием – называется утверждение, которое может быть истинным или ложным (Рим – столица Франции). Каждое такое выссказывание обозначается большой начальной буквой латинского алфавита А, В, С. Такие буквы называются пропозиционными буквами.

Простые выссказывания могут объединяться в формулы с помощью простых логических операций – V, , Ā , AB

Таблица для импликации

A	B	AB
и	и	И
и	л	Л
л	и	И
л	л	И

AB ~ ĀVB

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

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

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

Наиболее часто в основу логик положены следующие законы:

1. - закон отрицания третьего

2. - закон отрицания противоречия

3. - закон modus ponens

4. - закон modus tollens

5. - закон силогизма

Теоремы де Моргана:

(1)

(2)

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

Предикатом называют неоднородную логическую функцию от N - аргументов P(x₁, x₂,…, x_n), где x₁ЄX₁, x₂ЄX₂ … Значение P всегда имеет логическое значение истина или ложь, и является логической функцией.

Как и в логике исчисления высказываний в этой логике тоже имеются формулы. Приведенная формула предиката соответствует n-местному предикату, т.к. имеет n перемееных.

Например:

P(x₁, x₂, x₃)= x₁ есть сумма x₂+x₃

Если x₁=5; x₂=3; x₃=2, то подставив в предикат получим

5=3+2 – выссказывание.

N местный предикат, в котором конкретизирована одна из переменных, называется (N-1)-местным предикатом, и т.д.

Предикат, в котором конкретизированы все переменные, называется 0- местным или выссказыванием.

При записи функции на языке исчисления предикатов используют два квантора:

1. Общности ;

2. Существования .

хР(х) для всех х выполняются свойства Р(х)

хР(х) существует такой х при котором выполняется свойство Р(х)(~Р(0) – выссказывание.

Квантор связывает переменную, которая записана рядом с ним. При работе с кванторами также существует две теоремы де Моргана.

(1)

(2)

Введем понятие формулы в языке исчисления предиката. Для этого введем понятия:

• Терм;

• Элементарная формула;

• Формула.

Термом называют:

1. предикатную переменную или предикатную const (например - (x₁, x₂,…, x_n);

2. если символ F обозначает функцию от N-аргументов и t₁, t₂,…, t_{n –} термы, то f(t₁, t₂,…, t_n) – тоже терм;

3. Никакая другая запись термом не является.

Элементарной формулой называют:

1. пропозициональную букву А,В,С … (т.е. выссказывание);

2. если Р – это предикатная буква и t₁, t₂,…, t_{n –} термы, то Р(t₁, t₂,…, t_n) – это элементарная формула;

3. Никакие другие объекты элементарными формулами не являются.

Формулой называют:

1. элементарная формула – это формула языка исчисления предикатов;

2. если P и Q – это предикатные буквы, а х – это аргумент или предметная переменная, то выражение, построенное с помощью логических операторов и кванторов, будет являться формулами.

Примеры формул: хР(х), хР(х), PVQ, PQ, PQ

3. Никакие другие формулы не являются правильными формулами.

Правила, построенные по приведенным формулам, называют правильно построенными формулами (ППФ).

Пример



ППФ

х(Р(х)Q(x,y))

хy(Q(х,y,z)P(x,f(z))

___

хy(Р(х,Q(х,y))f(х,y) – не правильная формула

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

Пример:

G(f(x,y), g(x,y)) – функция, где

f(x,y)= x+y и g(x,y)= x*y

предметные переменные x и y принадлежат множеству целых положительных чисел – x,y N, G=’<’