KNOWLEDGE REPRESENTATION IN FUNCTIONAL GRAMMARS

Abstract

One of the ways of representation of knowledge (theories) by means of functional grammars is considered in the article. The authors make an attempt to give the uniform scheme of the decision of the problem, by its downsinking in functional grammar of the theory.

Full Text

Рассмотрим вопрос о формализации языка с точки зрения формирования понятий на основе анализа от- ношений между различными объектами. В программировании существенную роль играет понятие полиморфизма. В данной статье нам хотелось бы выдвинуть следующий тезис: любая предметно- ориентированная теория (например, электротехника, механика и т. п.) является по существу полиморфной программой, которая написана на специализирован- ном естественном языке, и если использовать функ- циональные грамматики [1; 2], то можно описать практически любую теорию (группу теорий) в про- граммной оболочке, способной генерировать решение любой задачи в рамках данной теории (групп теорий). Согласно данному подходу, любое предложение естественного языка, а также любая программа на языке программирования может быть представлена либо математически в виде суперпозиции функций (рис. 1), либо графически в виде дерева синтаксиче- ского разбора с функциями в узлах (рис. 2). При этом оба представления являются эквива- лентными и выражают одни и те же зависимости эле- ментов текста. Однако суперпозиции функций, представленные на рис. 1 и 2, являются неполными, так как они выра- жают лишь разбор на уровне синтаксиса. Ниже мы будем рассматривать вычисления, основанные на функциональных грамматиках, и процессы функцио- нально-логических вычислений на иерархическом уровне типов, т. е. вычисления на уровне предметной и общей логики типов для построения суперпозиций функций, или генерации процедур. 55 Математика, механика, информатика программа f1 условие f2 лог. знач. f3 дизъюнкция f4 лог. знач. f3 лог. знач. f3 сравнение f6 сравнение f7 текст f8 текст f8 Начало если A < 0 или A > 1 то B иначе C конец ? = f1(f2(f3(f4(f3(f6(A,0)),f3(f7(A,1))),f8(B),f8(C))) Рис. 1. Дерево синтаксического анализа и суперпозиция функций для программы предложение f 1 определение f6 причастный оборот f2 дополнение f5 сказуемое f7 подлежащее f3 причастие f9 обстоятельство f4 мест. f11 глагол f13 сущ. f8 предлог f10 сущ. f8 наречие f12 Книга , найденная в библиотеке , мне очень помогла . ? = f1(f3(f8(книга)),f2(f9(найденная),f4(f10(в),f8(библиотеке))),f5(f11(мне)),f6(f12(очень)),f7(f13(помогла))) Рис. 2. Дерево синтаксического анализа и суперпозиция функций для предложения русского языка Однако для выполнения вычислений на уровне ло- гики типов необходимо развить саму общую теорию логики типов, или общую теорию понятий, которая существенно отличается от математической теории: общая теория логики типов (понятий) предполагает разработку специального языка (или семейств языков) для представлений знаний об окружающем нас мире, в то время как математическая логика опирается на группу своих языков логики, например на язык ис- числения предикатов и теорию рекурсивных функций, 56 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева которые до настоящего времени были ориентированы на решение только математических задач. Однако в связи с развитием информатики все более актуальной становится относительно недавно возникшая инжене- рия знаний. Так, дерево на рис. 1 можно углубить, расписав в качестве суперпозиций элементы A, B и C. Во втором же случае (см. рис. 2) представлению в виде суперпо- зиций можно подвергнуть каждое слово, выразив его значение через другие слова. Но в каждом языке в результате самого глубокого разложения можно дой- ти до тех функций, которые не подлежат дальнейше- му функциональному представлению и в этом смысле являются элементарными. Такие функции будем на- зывать базисными. Пример 1. Приведем простейшую функциональ- ную грамматику, описывающую основные законы кинематики. Напомним, что главными объектами (ти- пами) в этом разделе физики являются расстояние, время, скорость и ускорение. Между ними существу- ют следующие известные соотношения (предикаты): − <TimeInMIN> → (R: real; мин); − <TimeInS> → (R: real; с); − <AccInKM/HH> → (R: real; км/ч2); − <AccInM/SS> → (R: real; м/с2). Условно обозначим приведенные выше продукции через GT . Для заданной грамматики между нетерминальны- ми понятиями имеются следующие соотношения (<Предикаты>): − <Speed> = <Start> + <Acc>*<Time>; − <Dist> = <Start>*<Time> + <Acc>*<Time>*<Time>/2; − <Dist> = [<Speed>*<Speed> – <Start>*<Start>] / (2*<Acc>). Программная оболочка по известным алгоритмам должна автоматически порождать из указанного пре- диката следующие функции (<Автоматически порож- денные функции>): − <Speed> → <Start> + <Acc>*<Time> {f1}; − <Speed> → КОРЕНЬ [2*<Acc>*<Dict> + <Start>*<Start>] {f2}; ⎧⎪ a ⋅ t 2 V 2 −V 2 ⎫⎪ − <Start> → <Speed> – <Acc>*<Time> {f3}; ⎨V = V0 + a ⋅ t; ⎪⎩ S = V0 ⋅ t + 2 ; S = 2 ⋅ a ⎬. (1) ⎭⎪ − <Start> → <Dist>/<Time> – <Acc>*<Time>/2 {f4}; Из предиката (1) порождаются 12 функциональ- ных зависимостей: V = V0 + a ⋅ t, V = 2 ⋅ a ⋅ S + V 2 , 0 V0 = V − a ⋅ t, V = S − a ⋅ t , 0 t 2 2 − <Start> → КОРЕНЬ [<Speed>*<Speed> – 2*<Acc>*<Dict>] {f5}; − <Dist> → <Start>*<Time> + <Acc>*<Time>*<Time>/2 {f6}; − <Dist> → [<Speed>*<Speed> – <Start>*<Start>] / [2*<Acc>] {f7}; − <Time> → [<Speed> – <Start>] / <Acc> {f8}; − <Time> → [ КОРЕНЬ [<Start>*<Start> + 2*<Acc>*<Dist>] – <Start> ] / <Acc> {f9}; V0 = V − 2 ⋅ a ⋅ S , a ⋅ t 2 − <Acc> → [<Speed> – <Start>] / <Time> {f10}; − <Acc> → 2* [<Dist> – <Start>*<Time>] / S = V0 ⋅ t + 2 и т. д. [<Time>*<Time>] {f11}; − <Acc> → [<Speed>*<Speed> – <Start>*<Start>] Дадим обычно принятые в функциональных грам- матиках определения объектов (типов, понятий): − <Speed> → <SpeedInKM/H> | <SpeedInM/S> | <SpeedInKM/S>; − <Start> → <StartInKM/H> | <StartInM/S> | <StartInKM/S>; − <Dist> → <DistInKM> | <DistInM> | <DistInSM>; − <Time> → <TimeInH> | <TimeInMIN> | <TimeInS>; − <Acc> → <AccInKM/HH> | <AcctInM/SS>; − <SpeedInKM/H> → (R: real; км/ч); − <SpeedInM/S> → (R: real; м/с); − <SpeedInKM/S> → (R: real; км/с); − <StartInKM/H> → (R: real; км/ч); − <StartInM/S> → (R: real; м/с); − <StartInKM/S> → (R: real; км/с); − <DistInKM> → (R: real; км); − <DistInM> → (R: real; м); − <DistInSM> → (R: real; cм); − <TimeInH> → (R: real; ч); / [2*<Dict>] {f12}. Также имеются следующие функции преобразова- ния единиц измерения объектов: − g1 = (<SpeedInKM/H>) <SpeedInM/S>: (0.278*R.<SpeedInKM/H>; м/с); − g2 = (<TimeInH>) <TimeInS>: (3600*R.<TimeInH>; с) и т.д. Рассмотренный выше процесс образования функ- циональной грамматики теории GT можно предста- вить в виде следующей обобщенной схемы: G (0) + <Предикаты> = = > G (1) + <Автоматически T T порожденные функции> = = > GT. В заданной функциональной грамматике рассмот- рим интерпретацию конкретной задачи. Дано: A: <Acc> = (5.0; м/с2); S: <Dist> = (6; км); V0: <Start> = (0.0; м/с). Необходимо найти: T: <Time> = (?.?; c). Сформулируем процесс решения задачи про- граммной оболочкой, которая загружена функцио- нальной грамматикой GT. 57 Математика, механика, информатика Шаг 1. Примем за аксиому величину, которую (0) T + <Предикаты> = = > G (1) + <Автоматически нужно найти, а за терминальные символы – заданные величины (в смысле грамматики). Шаг 2. Выберем из грамматики GT продукции, со- держащие аксиому в левой части. Шаг 3. Может существовать три ситуации: первая – в правых частях полученных продукций отсутствуют порожденные функции> = = > GT, где G (0) – начальная грамматика, в которой приводят- ся определения понятий в термах: <Предикаты> описывают соотношения и связи между понятиями теории. нетерминалы и тогда решением задачи будет путь в дереве от аксиомы к заданному данными продукция- ми узлу; вторая – в правых частях есть нетерминалы, тогда выбираем продукции для самого левого нетер- минала; третья – в правых частях присутствует ак- сиома и такие ветви будем отбрасывать. Шаг 4. Процесс повторяем до тех пор, пока не бу- дет найден узел, содержащий только терминалы, т. е. решение задачи. Таким образом, решение рассматриваемой нами задачи имеет вид суперпозиции функций, которая получается при чтении дерева разбора по пути от ак- сиомы до найденного узла, при этом функции, входя- щие в суперпозицию, находятся на ветвях дерева раз- бора, т. е. решение может быть представлено в виде дерева и соответствующей суперпозиции функций (рис. 3). В примере 1 мы показали, что, используя функ- циональные грамматики, можно описать практически любую теорию (группу теорий) в программной обо- лочке, способной генерировать решение любой зада- чи в рамках данной теории (групп теорий). Процесс решения задачи по своей сути является построением подграмматики функциональной грамматики теории. Процесс образования функциональной грамматики теории GT можно представить в виде следующей обобщенной схемы: Объединение G (0) и <Предикаты> образует грам- матику G (1), которая является входным интерфейсом пользователя, настраивающего систему на определен- ную теорию (группу теорий). Сама же система авто- матически строит функциональную грамматику тео- рии (группы теорий) внутри себя и готова к автомати- ческому решению задач. Пример 2. Покажем, как, используя функциональ- ную грамматику, можно создать модель состояние памяти для следующего программного фрагмента: начало цел A, B, C, вещ D, E, … конец. Цель этого примера состоит в том, чтобы проде- монстрировать, как описания переменных X, Y, Z, T, L могут быть формально представлены в виде процесса управления памятью. Для этого введем формальные определения модели памяти, модели типов перемен- ных и синтаксис описания переменных в языке. Грамматика GM–1 – это грамматика описания об- щей памяти: E → M ω F; M → вид X #, M → ε; F → B # B; B → ε. Здесь E – память; M – вспомогательная модель па- мяти для суперпозиции функций; F – внешняя память; B – файл ввода; ε – пустое множество. <Time> f8 f9 [<Speed> – <Start>] / <Acc> [ КОРЕНЬ [<Start>*<Start> + <Acc>*<Dist>*<Time> *<Time>] – <Start> ] / <Acc> ТУПИК (наличие аксиомы <TIME>) f1 2 [<Start> + <Acc>*<Time> – <Start>] / <Acc> ТУПИК (наличие аксиомы <TIME>) [КОРЕНЬ [2*<Acc> + <Start>*<Start>] – <Start>] / <Acc> РЕШЕНИЕ (наличие только терминальных символов <Acc> и <Start>) <Time> = f8(f2(<Acc>, <Start>),<Start>, <Acc>) Рис. 3. Решение задачи в виде дерева разбора и суперпозиции функций 58 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Начальное состояние памяти: E ≡ ω B #. Грамматика GM1 – это грамматика описания видов: ВИД → цел, ВИД → вещ, ВИД → имя ВИД. Упорядоченность g1 = (имя ВИД) ВИД. Грамматика G0 – это грамматика синтаксиса: <программа> → начало <описания>, <операторы> конец {f1}; <описания> → <описание> {f2}; <описания> → <опи- сания>, <описание> {f3}; <описание> → <описание>, <идент> {f5}; <описание> → ВИД, <идент> {f6}; <идент> → X {f18}; X → <буква>; X → X <буква>. Функции fi: − f2 = (конт t, знач x) конт: (E, M) f3(E, ε, M); − f3 = (конт t, знач x, y) конт: ((M ВИД X # E, ε, ВИД(1) X # M) ┴ | (E, ε, ВИД X # M) f3(имя ВИД X # E, ε, M) | (E, ε, ε) знач (ε)); − f5 = (знач x, текст y) знач: (ВИД X # M, X(1)) ВИД X # M ВИД X(1) #; − f6 = (текст x, y) знач: (ВИД, X) имя ВИД X #; − f18 = (конт t, текст x) знач: (M ВИД X # E, X) ВИД. Согласно введенной для заданного фрагмента про- граммы грамматике можно построить дерево синтак- сического разбора (рис. 4). Результат представленного выше фрагмента про- граммы будет определяться работой функций (или нетерминалов), находящихся в узлах дерева. Рассмот- рим принцип работы функций на примере функции f6 = (текст x, y) знач: (ВИД, X) имя ВИД X #. Эта функция состоит из двух частей. Часть функции до двоеточия называется заголовком функции, после двоеточия – телом функции. Заголовок функции f6 сообщает о том, что она имеет два аргумента: x и y, причем тип этих аргументов – текстовый. Результа- том функции является тип знач. Следует отметить, что любой аргумент, равно как и результат функции, может иметь один из четырех типов: текст, функ, знач, конт. Тип текст говорит о том, что аргумент необходимо рассматривать как по- следовательность символов (как терминальных, так и нетерминальных), тип функ – как невыполненную суперпозицию функций, тип знач – как значение вы- полненной суперпозиции, которая, как правило, пере- дается по соответствующей исходящей ветви дерева разбора в качестве аргумента к вышестоящему нетер- миналу. Тип конт применяется, когда параметр изме- няет значение общей памяти. <описания> f3 <описания> f2 <описание> f5 (1) <описание> f5 <описание> f5 (2) <описание> f6 <описание> f6 <идент> f18 <идент> f18 <идент> f18 <идент> f18 <идент> f18 X X X X X ВИД <буква> <буква> <буква> ВИД <буква> <буква> цел X , Y , Z , вещ T , ш Рис. 4. Дерево синтаксического разбора заданного фрагмента программы 59 Математика, механика, информатика Таким образом, заголовок функции играет боль- шую логическую роль при синтаксическом разборе и управлении вычислением суперпозиции функций. Это связано с тем, что каждый нетерминал в качестве сво- его значения имеет несколько функций. Выбор кон- кретной функции нетерминал осуществляет в зависи- мости от контекста, а инструментом данного выбора являются типы, перечисленные в заголовке. Отсюда следует, что заголовок служит фундаментом для по- строения контекстно-ориентированного программи- рования и имеет основное значение при синтаксиче- ском разборе предложений естественного языка. Рассмотрим тело функции f6 (см. рис. 4). Внутри скобок находятся два нетерминала: ВИД – от грамма- тики GM1 − и X – от грамматики G0, которые являются формальными параметрами функции. Фактическими параметрами функции f6 в начале программного Тогда результат функции f6 равен имя цел A #. отождествление f6 = (текст x, y) знач: (ВИД, X) имя ВИД X # цел A фактические параметры (тип «текст») имя цел A # результат (тип «знач») фрагмента (это самая левая часть дерева разбора) яв- ляются цел и X, при этом цел сворачивается в ВИД по одному правилу, а A как буква сворачивается сначала в нетерминал X, а потом – в нетерминал <идент> {f18}. Далее ВИД и <идент> сворачиваются в <описание> {f6}. Поскольку в заголовке f6, как уже было указано, аргументы x и y имеют тип текст, то нетерминалы ВИД и X рассматриваются функцией как текстовые значения цел и A. Функция f18, соответствующая не- терминалу <идент>, игнорируется, так как ее резуль- тат имел тип знач, а вовсе не тип текст. Отсюда мож- но сделать вывод, что заголовок функции управляет процессом вычислений в теле функции, а также про- цессом вычислений в суперпозиции функций, что еще раз подтверждает значимость заголовка функции. Результат функции f6 в терминах формальных па- раметров имеет вид имя ВИД Х #, где имя, # – термы; ВИД имеет текстовое значение цел, X – текстовое значение A. Значение функции оп- Рис. 5. Вычисление значения функции f6 Теперь рассмотрим функцию f5 = (знач x, текст y) знач: (ВИД X # M, X(1)) ВИД X # M ВИД X(1) #. Она также имеет два аргумента x и y, но первый аргумент имеет тип знач. Именно поэтому в качестве первого фактического параметра будет выступать результат выполнения функции f6 имя цел A #. Отметим, что формальный параметр X имеет в своем составе нетерминал M, который в данном слу- чае равен ε (пустоте). Вторым параметром f5 является текстовое значение нетерма X, которое равно B. Ре- зультатом функции f5 (рис. 6) будет являться значение имя ВИД A # имя ВИД B #. Найденный результат, согласно дереву синтакси- ческого разбора, будет подаваться на вход новой (1) ределяется при помощи операции отождествления. функции f5 . В этом случае нетерминал M уже не бу- Для вычисления f6, с одной стороны, имеются фор- мальные параметры ВИД и X, c другой стороны – фактические параметры цел и A (рис. 5). Операция отождествления основывается на сопоставлении фор- мальных и фактических аргументов: ВИД : = цел и X : = A. дет пустым, а равным имя ВИД B #. В этом случае результатом функции является зна- чение имя ВИД A # имя ВИД B # имя ВИД C #. отождествление f5 = (знач x, текст y) знач: (ВИД X # M, X(1)) ВИД X # M ВИД X(1) # имя ВИД A # ? B Фактический имя ВИД A # имя ВИД B # результат (тип «знач») Фактический параметр x (тип «знач») параметр y (тип «текст») Рис. 6. Вычисление значения функции f5 60 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Таким образом, фрагмент программы цел A, B, C сворачивается в нетерминал <описание>, которому соответствует результат функции f (1): 5 имя ВИД A # имя ВИД B # имя ВИД C #. Другой фрагмент вещ D, E также сворачивается в <описание> с функцией f5 , (1) значение нетерминала M не будет исчерпано. Таким образом, область значения функции f2 состоит из де- картового произведения множества состояний памяти (конт) и множества значений, которые образуются на исходящей ветви нетерминала f2 в дереве разбора (знач). Результатом на памяти будет являться состоя- ние памяти E ≡ имя имя цел C # имя имя цел B # имя имя цел A #, а результатом на исходящей ветви дерева – пустое значение значение которой, по аналогии с f5 , равно ε = знач (ε). имя ВИД D # имя ВИД E #. Далее символ <описание>, находящийся в левой части дерева, сворачивается в символ <описания> посредством функции Последнее означает, что нетерминал <описание> не производит передачу результата в суперпозицию функций, вместо этого происходит формальная пере- дача параметра ε. f2 = (конт t, знач x) конт: (E, M) f3(E, ε, M). Полученный результат ε и результат функции f5 (2) Стоит обратить внимание на то, что результатом данной функции, имеющей два аргумента, является вызов функции f3 с тремя параметрами: f3 = (конт t, знач x, y) конт: ((M ВИД X # E, ε, ВИД(1) X # M) ┴ | (E, ε, ВИД X # M) f3 (имя ВИД X # E, ε, M) | (E, ε, ε) знач (ε)). При этом два аргумента вызывающей функции нахо- дят свое место в качестве первого и третьего парамет- подаются (теперь уже непосредственно) на вход функции f3. Возникающая при этом рекурсия будет аналогична рассмотренной ранее. Ошибка ┴ описы- ваемая альтернативой (M ВИД X # E, ε, ВИД(1) X # M), необходима для того, чтобы исключить добавление уже имеющейся переменной, объявив для нее новый тип. В результате значение функции f5 пополнит об- ров вызванной функции, а в качестве второго пара- метра выступает ε. Таким образом, f2 является вспо- могательной функцией вызова f3. Обе функции рабо- тают с общей памятью E, о чем нам сообщает тип конт. Функция f3 является рекурсивной и состоит из трех альтернатив. В случае выполнения первой альтерна- тивы значением функции будет являться ошибка (┴). Вторая и третья альтернативы образуют рекурсию. Вид рекурсии (E, ε, ВИД X # M) f3(имя ВИД X # E, ε, M) говорит о том, что каждый новый вызов функции бу- дет изымать значение имя ВИД X из нетерминала M и добавлять его в память E, про- ставляя каждый раз впереди дополнительно терм имя. Это будет происходить до тех пор, пока согласно вы- ражению (E, ε, ε) знач (ε) щую память E до состояния E ≡ имя имя вещ E # имя имя вещ D # имя имя цел C # имя имя цел B # имя имя цел A #. Таким образом, с помощью составленной функ- циональной грамматики мы смогли описать процесс выделения в памяти ячеек для переменных разных типов. Вычисления на уровне типов, выполняемые ком- пилятором, имеют существенное значение для синте- за программ. При этом контексты, в среде которых находятся нетерминалы, могут управлять синтаксиче- ским разбором и процессами вычислений в суперпо- зиции функций. Данное управление осуществляется через заголовки базисных функций – нетерминалов.