|
|
 |
Аннотация tExp tExp - логический декларативный язык
Термин логическое программирование неоднозначен: часто под логическим программированием понимают программирование на прологе или на подобных языках, иногда к логическому программированию относят функциональное программирование, также к логическому программированию в широком смысле относят и так называемое семантическое программирование. Язык tExp - это декларативный язык семантическго программирования, парадигма которого была предложена в середине 80-х годов XX века Ю. Л. Ершовым, С. С. Гончаровым и Д. И. Свириденко.
tExp основан на семантике полного исчисления предикатов, что принципиально отличает tExp от прологоподобных языков логического вывода, которые основаны на синтаксисе различных исчислений (типа исчисления хорновских дизъюнктов). Также очень важным является то, что tExp, в отличие от прологообразных логических языков, позволяет эффективно оперировать не только с хорновскими дизъюнктами или каким-либо другим неполным классом формул, а с полным классом формул первого порядка. Но возможности tExp не ограничиваются выразительными средствами первого порядка. В tExp можно оперировать также и свойствами второго порядка, задающимися так называемыми шаблонами - специальными конструкциями, имитирующими формулы второго порядка, причём именно шаблоны являются базовыми конструктивами языка.
В целом программа на tExp задаётся следующими элементами: - множеством формул первого порядка
- множеством шаблонов (конструкций второго порядка)
- списком, задающим порядок наложения шаблонов на текст
Парадигма семантического программирования
В чём же заключаются фундаментальные принципы, заключённые в парадигму семантического программирования, и в чём их отличие от традиционной парадигмы прологоподобных языков?
Как уже было замечено, прологообразные языки используют принцип дедукции: из программы, которая представляет собой набор формул (утверждений о предметной области), делаются выводы, цель которых - доказать или опровергнуть запрос в форме некоторого утверждения (тоже формулы). Принципиальным ограничением эффективности такого подхода является потенциально экспоненциальный рост дерева перебора доказательств в зависимости от глубины этого дерева. В большой степени развитие традиционного логического программирования в прологообразном стиле и состояло в преодолении этой неэффективности.
Парадигма семантического программирования базируется на вычислении так называемых формульных множеств: если есть некоторая формула и некоторая модель, согласованная с этой формулой по языку (сигнатуре), то множество тех элементов, которые удовлетворяют этой формуле, и называется формульным. Можно провести довольно точную аналогию между нахождением формульного множества (или множества решений некоторой формулы) и решения алгебраического уравнения (в общем случае от нескольких переменных). Строго говоря, решение системы алгебраических уравнений и есть нахождение множества решений некоторой формулы специального вида.
Эффективность нахождения формульного множества первого порядка в любом случае полиномиальна, и с помощью специальных алгоритмов степень этого полинома может быть существенно редуцирована, часто до линейной. Более того, ограничивая области определения переменных в формуле (в том числе и под кванторами), можно сильно сузить область определения всей формулы и ускорить вычисление формульного множества.
Верхняя оценка эффективности нахождения формульного множества второго порядка уже экспоненциальна, но в tExp есть средства сведения вычисления формульных множеств второго порядка к нахождению формульных множеств первого порядка (шаблоны), то есть эффективно, причём использование таких конструкций оказывается очень удобным в машинной лингвистике.
Специализация tExp для анализа текстов на естественном языке Основной моделью, в которой ищутся формульные множества, для tExp является текст на естественном языке. Элементами этой модели являются слова текста, на них определён естественный линейный порядок следования.
В tExp нет настоящих предикатов, вместо этого вводятся так называемые парапредикаты, которые задают параметрические семейства предикатов, что позволяет очень гибко задавать конкретные предикаты. Например, вместо огромного количества унарных предикатов, фиксирующих грамматические характеристики слов, вводится парапредикат LingAttribute, два параметра которого задают конкретный лингвистический атрибут и его значение, то есть конкретный предикат. В некоторых парапредикатах синтаксис параметра задаётся особым элементарным языком. Элементарным он называется потому, что в нём записываются условия на один элемент модели (то есть на слово в тексте) в виде пропозициональной булевой формулы. Это позволяет очень лаконично задавать достаточно сложное строение конкретного предиката, и в конечном итоге, сократить размер программы.
Набор парапредикатов tExp достаточно широк, чтобы быть удобным для реализации таких сложных операций над текстом как полный синтаксический анализ неадаптированных предложений русского языка. Кроме того, возможность оперировать шаблонами (конструкциями второго порядка), очень удобна для работы с неопределённостью естественного языка. Так, подлежащее в предложении может состоять и из одного слова и из двадцати, а выделяться должно как одно целое.
Перспективы развития tExp Ближайшей задачей для развития tExp является задача перехода от анализа текстов к возможности манипуляции текстами. Дело в том, что, несмотря на очень развитые возможности анализа текста на естественном языке, существующая версия языка не позволяет менять исходный текст или синтезировать новый на основе старого. Решать эту задачу планируется путём офункционаливания tExp, то есть, вводя различные рекурсивные функционалы и операторы, позволяющие изменять исходный текст и синтезировать новый. Это позволит качественно дополнить возможности tExp и существенно расширить класс задач, доступных для решения на tExp. Например, реальной станет задача динамического изменения и синтеза логических программ.
Очень заманчиво выглядит идея синтеза парадигм логического вывода и семантического программирования в единую логическую теоретико-модельную парадигму программирования, позволяющую в рамках средств языка переходить как от формул к их моделям (в смысле их эффективного построения), так и обратно. Это может опять качественно расширить возможности языка. Возможно, это позволит эффективно решить поставленную задачу динамической генерации программ. |
