О возможных основаниях немонотонного дедуктивного синтеза программ

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2003
1. Verfasser:	Приходько, П.П.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2003
Schlagworte:	Теоретические и методологические основы программирования
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/1333
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	О возможных основаниях немонотонного дедуктивного синтеза программ / П.П. Приходько // Проблеми програмування. — 2003. — N 4. — С. 5—23. — Бібліогр.: 18 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-1333
record_format	dspace
spelling	irk-123456789-13332008-07-28T12:00:44Z О возможных основаниях немонотонного дедуктивного синтеза программ Приходько, П.П. Теоретические и методологические основы программирования Предлагается подход к практической автоматизации синтеза программ из готовых исполнимых программных составляющих, непосредственно извлекаемых из моделей предметных областей. Этот подход основывается на использовании немонотонных дедуктивных построений. Рассматривается возможность организации действенных баз данных для задач построения конкретных программ. Пропонується підхід до практичної автоматизації синтезу програм з готових програмних складових, що безпосередньо видобуваються з моделей предметних областей. Цей підхід ґрунтується на використанні немонотонних дедуктивних побудов. Розглядається можливість організації дієвих баз даних для задач побудови конкретних програм. This Paper reported the Approach to practical automatically Synthesis of Programs from Components, with direct received from Subject Field Model. This Approach is based on using non-monotone deductive Constructions. Potentiality to Organizations real Databases for programming Problems is considered. 2003 Article О возможных основаниях немонотонного дедуктивного синтеза программ / П.П. Приходько // Проблеми програмування. — 2003. — N 4. — С. 5—23. — Бібліогр.: 18 назв. — рос. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/1333 681.3.06 ru Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теоретические и методологические основы программирования Теоретические и методологические основы программирования
spellingShingle	Теоретические и методологические основы программирования Теоретические и методологические основы программирования Приходько, П.П. О возможных основаниях немонотонного дедуктивного синтеза программ
description	Предлагается подход к практической автоматизации синтеза программ из готовых исполнимых программных составляющих, непосредственно извлекаемых из моделей предметных областей. Этот подход основывается на использовании немонотонных дедуктивных построений. Рассматривается возможность организации действенных баз данных для задач построения конкретных программ.
format	Article
author	Приходько, П.П.
author_facet	Приходько, П.П.
author_sort	Приходько, П.П.
title	О возможных основаниях немонотонного дедуктивного синтеза программ
title_short	О возможных основаниях немонотонного дедуктивного синтеза программ
title_full	О возможных основаниях немонотонного дедуктивного синтеза программ
title_fullStr	О возможных основаниях немонотонного дедуктивного синтеза программ
title_full_unstemmed	О возможных основаниях немонотонного дедуктивного синтеза программ
title_sort	о возможных основаниях немонотонного дедуктивного синтеза программ
publisher	Інститут програмних систем НАН України
publishDate	2003
topic_facet	Теоретические и методологические основы программирования
url	http://dspace.nbuv.gov.ua/handle/123456789/1333
citation_txt	О возможных основаниях немонотонного дедуктивного синтеза программ / П.П. Приходько // Проблеми програмування. — 2003. — N 4. — С. 5—23. — Бібліогр.: 18 назв. — рос.
work_keys_str_mv	AT prihodʹkopp ovozmožnyhosnovaniâhnemonotonnogodeduktivnogosintezaprogramm
first_indexed	2025-07-02T04:49:13Z
last_indexed	2025-07-02T04:49:13Z
_version_	1836509302744940544
fulltext	Теоретические и методологические основы программирования © П.П. Приходько, 2003 ISSN 1727-4907. Проблемы программирования. 2003. № 4 5 УДК 681.3.06 П.П. Приходько О ВОЗМОЖНЫХ ОСНОВАНИЯХ НЕМОНОТОННОГО ДЕДУКТИВНОГО СИНТЕЗА ПРОГРАММ Предлагается подход к практической автоматизации синтеза программ из гото- вых исполнимых программных составляющих, непосредственно извлекаемых из мо- делей предметных областей. Этот подход основывается на использовании немонотон- ных дедуктивных построений. Рассматривается возможность организации действен- ных баз данных для задач построения конкретных программ. Введение Программирование все еще ос- тается довольно кропотливым и трудо- емким делом. Программы все еще “пи- шутся”, “кодируются”, а не получаются автоматически по “... исходной записи, более близкой к начальной формули- ровке задачи ... в рамках существенно более широкого языка формулирова- ния задач, не ограничиваемого конк- ретным классом” [1], как высказывал это А.П. Ершов в 70-х годах прошлого столетия. Успехи в автоматизации доказа- тельных рассуждений [2] способство- вали становлению взглядов о возмож- ности автоматизации дедуктивного синтеза программ по их спецификаци- ям средствами логико-математических исчислений [3, 4]. Установилась точка зрения, в соответствии с которой авто- матическое программирование заклю- чается в реализации алгоритма постро- ения (синтеза) требуемой программы из предварительно полученных состав- ляющих, если задача анализа решена положительно, т.е. если такую про- грамму можно построить. Указанные составляющие отвечают условиям зада- чи, решаемой при выполнении требуе- мой программы. Автоматическое программирова- ние предусматривает явное описание в условиях задачи знаний, которые предполагается использовать для по- строения требуемой программы. В со- ответствии с этим описанием указы- ваются входные и выходные парамет- ры требуемой программы. Сложным вопросом в такой ор- ганизации моделей предметных облас- тей задач автоматического синтеза конкретных программ оказалась эф- фективность представления объектов, связанных с построением цикличе- ских предложений, в частности рекур- сивных объектов. В решении этого вопроса получил распространение подход, основывающийся на предпо- ложении, что a priori известно о по- требности построения соответствую- щих циклических предложений, т.е. речь идет о собственно программиро- вании циклов [4—6]. Указанную ситуацию можно свя- зать с использованием исчислений, основывающихся на классической логике. Одним из важнейших их свойств является монотонность [7, с. 218]. В силу этого свойства какое-либо утверждение, получаемое в результате логического вывода, не может быть опровергнуто в ходе дальнейших умозаключений. При этом извлечение программы требует хотя бы интенсио- нального описания всех значений, по- лучаемых в процессе ее выполнения. Предложения программы извлекаются из соответствующих применений пра- вил. Сложности возникают при ото- ждествлении цикличности в последова- тельностях таких применений. Этого можно избежать, исполь- зуя для дедуктивного синтеза программ немонотонное исчисление с эффек- тивной реализацией структурных свойств их предметных областей. Рас- смотрим возможный подход к по- Теоретические и методологические основы программирования 6 строению такого исчисления, его осно- вания и особенности использования. 1. Основные понятия и определения Предметные области задач авто- матического синтеза конкретных про- грамм имеют глубоко специальный ха- рактер. Даже само существование кор- ректно поставленного вопроса о по- строении программы предполагает, что определены процедурные представле- ния всех исходных отношений, ука- занных в условиях решаемой задачи. Выполнение этих процедур может по- надобиться для получения требуемых значений. Такую предметную область можно эффективно представить вы- числительной моделью – совокупно- стью некоторых исходных функцио- нальных зависимостей, изначально по- лучающих определенную программную реализацию. Для формализованного представ- ления синтезируемых программ и их предметных областей используем под- ход, развитый Э.Х. Тыугу [4], А.Я. Ди- ковским и М.И. Кановичем [5, 6] и примененный в [8, 9]. Функции, реализуемые програм- мой, выражают взаимосвязь значений различных объектов, представляемую ее моделью предметной области. Назо- вем такие объекты программными. Модель предметной области програм- мы заключает в себе всю совокупность знаний об этих объектах. Их значения используются в программе или опреде- ляются при ее выполнении. Программе, описываемой такой моделью, соответствует функциональ- ное отношение, которое связывает значения объектов, представляющих входные и выходные данные. Значе- ния, устанавливаемые для элементов какой-либо совокупности объектов при выполнении программы, можно истол- ковывать как состояние этой совокуп- ности в указанный момент ее выпол- нения. Различные программы могут быть связаны с одной и той же сово- купностью объектов, т.е. иметь общую модель предметной области. Такую модель следует рассматривать как со- вокупность знаний о некотором моде- лируемом объекте, а получение про- граммы – как установление одно- значного соответствия, которое свя- зывает характеристики этого объекта. Его состояние отражается совокуп- ным значением этих характеристик, представляемых программными объ- ектами. Состояние любого их множества следует рассматривать как часть со- стояния всех таких объектов, пред- ставляющих моделируемый объект. Поэтому модель предметной области можно рассматривать еще и как сред- ство определения состояния модели- руемого объекта по значению части его характеристик. В силу наличия взаимосвязей между такими характе- ристиками всем возможным состояни- ям такого объекта могут отвечать не все мыслимые значения наборов про- граммных объектов. Модель предметной области, оп- ределяющая требуемую программу, представляет знания, существенные для ее построения, в том числе и зна- ния об алгоритме, реализуемом этой программой. Например, никакая прак- тическая система автоматического синтеза программ “сама” никогда не реализует алгоритм решения большой теоремы Ферма, если для x, y, z и n указать лишь способ их представления в памяти ЭВМ [3]. В [8, 9] составляющие какой- либо предметной области конкретной программы представляются тройкой ( )X,,εX , где X – множество программных объектов; { }XxEx ∈= :ε – семейство час- тично упорядоченных множеств ( ) XxxxE ∈⊆, этих объектов; X – булева алгебра множеств- наборов программных объектов. Какое-либо состояние набора программных объектов представляет функция вида ,εU→wXw : Теоретические и методологические основы программирования 7 где X Xw ∈ и ( )w x Ex∈ для x X w∈ . По- этому все такие состояния представ- ляются множеством ( ) ( ){ }U XX ∈=≡ ∏ CXWW C :,, εε . Для элементов W можно ввести отношение частичного порядка ⊆. Пусть для ( )X,,, εXWvu ∈ ( ) ( )( )xvxuXxXXvu xuvu ⊆∈∀⊆⇔⊆ & . Это отношение индуцирует на W операции взятия точных верхней и нижней граней, а также отношения равенства и строгого порядка. Для множества ( ) ( )W W X W X возм возм = ⊆, , , ,ε εX X (1) состояний наборов программных объ- ектов, соответствующих возможным состояниям моделируемого объекта, в [8, 9] установлено следующее требова- ние: { } &,(, &: U IIU возмвозм возм WW wvWvvWw ∈∈∃ ⊆∈⊆∀∈∀ UUUU U )IU w⊆UU ,& . (2) Пусть функция ( ) ( )F W X W X: , , , ,ε εX X→ (3) каждому состоянию w W∈ ставит в од- нозначное соответствие состояние Fw W∈ , представляющее все сведения о состоянии моделируемого объекта, получаемые исходя из w на основе знаний о предметной области, заклю- ченных в некоторой ее модели. В [8] показано, что эта функция должна удовлетворять таким условиям: ∀ ∈ ⊆w W w Fw , (4) ( )F W Wвозм возм⊆ (5) и ∀ ∈ ∀ ⊆ ⊆w W v Fw Fv Fwвозм . (6) Там же моделью первого типа предметной области (МПрОI) названо пятерку (X, ε, X, F, Wвозм ), где (X, ε, X) – представление составляющих пред- метной области (ПСПрО); Wвозм – множество возможных состояний на- боров программных объектов, удовле- творяющее условиям (1) и (2), а F – функция вида (3), удовлетворяющая условиям (4)—(6). Пусть для A X⊆ ( ) ( ) ( ){ },AXXWww AXWAW w ⊆∈= =≡ &,,: ,,, X X ε ε ( ) ( ) ( ){ },AXXWww AXWAW w =∈= =≡ &,,: ,,,** X X ε ε ( ) ( ) ( ){ },wXAXWww AXWAW ⊆∈= =≡ &,,: ,,, X X ε ε ( ) ( ) ( ) ,возм возмвозм WAXW AXWAW ∩= =≡ ,,. ,,, X X ε ε ( ) ( ) ( ) ,возм возмвозм WAXW AXWAW ∩= =≡ ,,, ,,, * ** X X ε ε ( ) ( ) ( ) .,,, ,,, возм возмвозм WAXW AXWAW ∩= =≡ X X ε ε Процедурные представления от- ношений, выражающих знания о предметной области, можно соотнести с функциями вида ( ) ( )ff BWAWf →: , (7) где fA , X∈fB . Пусть µ – множество таких функций, представляющих зависимо- сти в некоторой предметной области. В [8] для элементов такого множества ус- тановлены следующие требования: ( ) ( ) возмfAfвозм WwfwAWwf ∈∪∃∈∀∈∀ µ , (8) ( )gAAWwgf f ∪∈∀∈∀ µ, возм gAfA Wwgwfw ∈     ∪     ∪∃ , (9) а также ( ) wwAWwwf fвозм ′′⊆′∈′′′∀∈∀ :, µ ( ) )(wfwf ′′⊆′ . (10) Теоретические и методологические основы программирования 8 Моделью второго типа предмет- ной области (МПрОII) в [8] названо пя- терку (X, ε, X, µ, Wвозм ), где (X, ε, X) – ПСПрО, µ – конечное множество функций вида (7), удовлетворяющее условиям (8)—(10), а Wвозм – множест- во возможных состояний, удовлетво- ряющее условиям (1) и (2). Нетрудно убедиться, что в любой МПрОII условие (9) вытекает из усло- вий (8), (10) и (2): для ( )gfвозм AAWw ∪∈ wf XA ⊆ , поэтому ( )w W Af∈ и в силу (8) существует ( )fвозм fA AWwfw ∈     ∪ , но при этом         ∪ ∪⊆⊆ fAwfw XXXA wwg , а ( )w f w W AAf возм g∪     ∈ и, опять же в силу (8), ∈                   ∪∪     ∪ Ag fAfA wfwgwfw возмW∈ , (11) при этом, поскольку ( ∪⊆ ww gA Ag fA wf         ∪ , то в силу (10) g w g w f wAg Af Ag     ⊆ ∪                 и поскольку ,возм gA fA fAgAfA Wwfwg wfwwgwfw ∈                    ∪∪ ∪     ∪⊆     ∪     ∪ то существует возм gAfA Wwgwfw ∈     ∪     ∪ . В [8] обсуждается эквивалент- ность МПрОI и МПрОII. Утверждается объективный характер предлагаемых формальных определений. При этом для выражений вида (11) существенно используется монотонность, представ- ляемая условиями (6) и (10). Приме- ненный подход основывается на воз- зрениях Д. Скотта об эффективной организации данных [10, 11]. Но структурированность данных может отражать структурные свойства не только решаемой задачи, но и методов ее решения. Функциональность использован- ных отношений связана с процедур- ным характером знаний о предметной области, они имеют эквивалентное ло- гическое представление. Конструктив- ность описания этих знаний предпола- гает наличие конкретизаций предика- тов в таком логическом представлении. Использование в таком представлении сентециальных связок обусловливает структуру булевой алгебры множеств для совокупности наборов программ- ных объектов. Монотонность, выра- жаемая отношением частичного поряд- ка, установленным для состояний та- ких наборов, связана с учетом всех вычисляемых значений. В ней прояв- ляется монотонность соответствующе- го логико-математического исчисления. Поэтому изложенный подход к организации автоматического синтеза программ не позволяет в полной мере избежать упоминавшихся выше слож- ностей, связанных с применением ло- гико-математических исчислений, ко- гда необходимо выбирать пути реали- зации моделируемых свойств в тре- буемых программах и учитывать осо- бенности такой реализации. Ведь дале- ко не всегда реальное выполнение про- граммы предполагает сохранение всех промежуточных значений. Более того, именно в переприсваиваниях, в цикли- ческих предложениях и вызовах про- цедур проявляются преимущества ав- томатической обработки данных. Указанные особенности иллюст- рирует использованный в [9] пример модели предметной области последова- тельного построения чисел Фибоначчи. Представим такую МПрОII ( )Y U, , , ,τ ϕY , в которой { }mnvuY df .,,= , ( )τ u Eu df = =N* и ( )τ n En df = =N* , но ( )τ v Ev df = =N и ( ) =mτ Теоретические и методологические основы программирования 9 N df mE == , а { }m v, ∈Y и { } Y∈u , { }gf df ,=ϕ , где { }uA df f = , { }B uf df = и для { }( ) ( )w W Y u U W Yвозм возм∈ ⊆ =, , , , ,τ τY Y { }( )( ) )(,..., 1,21 nnnu uuuuuuwf += − , если ( ) nuuuuw df ,...,, 21= , а { }muA df g ,= , { }B vg df = и для { }( )u,mYWw возм ,,, Yτ∈ { }( )( ) =nwg mu , mu= , если ( ) nuuuuw df ,...,, 21= и nm ≤ , ина- че n X g w Ag ∉       . При этом для всякого { }( )uYWw возм ,,, Yτ∈ существуют ( )( )w u 1 1= и ( )( )w u 2 1= . В этом примере видно, как строение значений u Y∈ представ- ляет рекуррентность соотношений, из которых получаются числа Фибоначчи. Уточним общую формулировку задач автоматизации программирова- ния с учетом возможных утрат моно- тонности. Средой поддержки программ (СПП) назовем пятерку (X, ε, X, µ, Wвозм ), где (X, ε, X) – ПСПрО, µ – ко- нечное множество функций вида (7) таких, что для каждой функции f ∈µ существуют единственные ее входной и выходной наборы X∈ff BA , , удов- летворяющие условиям (7) и (10), причем для B f установлено его един- ственное разбиение на наборы X∈′′′ ff BB , , для которых fff BBB ′′∪′= , (12) ∅=′′∩′ ff BB (13) и ( ) возм fAfBfвозм WwfwAWw ∈     ∪∃∈∀ ′′ . (14) Очевидно, МПОII представляет частный случай СПП, когда ′′ = ∅B f для всех f вида (7). Примером определен- ной выше среды может быть предла- гаемая СПП ( )UY ′′′′′ ,,,, ϕτ Y , которая, как и рассмотренная выше МПрОII (Y, τ, Y, ϕ, U), представляет последова- тельное получение чисел Фибоначчи. Пусть { }mvuuuY fd ,,,, 321=′ , ( ) f ju d j Eu ==′τ { }λ∪=N fd , 3,1=j а ( )′ = =τ v Ev df N , ( ) =′ mτ N df mE == , { }rhgf df ,,,=′ϕ , { }21,uuA fd f = , =fB { }3uB df f =′′= и для ( )w W Y Aвозм f∈ ′ ′ ′, ,τ Y , ( )Y ′′′=′∈ ,,τYWUw возм ( ) ( )+=      13 uwuwf fA ( )2uw+ , { }A ng df = , { }B B ng g df = ′′ = и для { }( )nYWw возм ,,, Y ′′′∈ τ { }( ) ( ) 1+= nwwg n , { }mnuA df h ,,3= , { }B B vh h df = ′′ = и для ∈w ( )fвозм AYW ,,, Y ′′′∈ τ ( ) ( )h w v w uAh ( ) ,= 3 ес- ли n m= , иначе v X h w Ah ∉       , а { }32,uuA df r = , { }321 ,, uuuBB df rr =′′= , причем для ( )w W Y Aвозм f∈ ′ ′ ′, ,τ Y , ( ) ( )21 uwuwr rA =     , ( )( ) ( )r w u w uAr 2 3= и ( )u X r w Ar 3 ∉ . Примем следующие обозначе- ния. Пусть для любой СПП (X, ε, X, µ, Wвозм ), функции f ∈µ и для состояния ( )w W X∈ , ,ε X ( )      ∈     ∪ ≡ ′′ ,остальных всех для ,если, w w AWwwfw F fвозм f fABf а для множества µ { }U +∈= Znn Df :* µµ , { }U N∈=+ nn Df :µµ , { }µ λ0 = Df , где λ – от- сутствие символа, и для цепочки сим- волов f f df =  = f i i j, ,1 и f = df j , а для нату- ральных m, n [ ] ( )jmiif df m ,, ==f , если m j≤ , и [ ] ( )f n df fi i n= =, ,1 , (15) Теоретические и методологические основы программирования 10 если n j≤ , а [ ] ( )nmiif df n m ,, ==f , если m n j≤ ≤ , и ( ) iDfi f=f (16) для натурального i ≤ f , а ( ) Df r =f ( ){ }ff ≤∈== iiff iDf &&: N . Пусть при этом для ( )w W X∈ , ,ε X ( ) wwG Df =,λ , а для f ∈µ* ( ) [ ]G w G F w Df ff f, ,=    2 1 и ( ) [ ]( )wGFwG n D nff ,, 1−= ff , если 2≤f , и ( )G ,w F w Df ff = для f ∈µ . Для какой- либо цепочки функциональных симво- лов f ∈µ* { }U ff ≤∈= &iiAA ifDf N: , { }U ff ≤∈= &iiBB ifDf N: , { }U ff ≤∈′′=′′ &iiBB ifDf N: , fff BBB Df ′′=′ \ , [ ]U       ≤∈= − f ff &iiBAA iifDf N:\ 1 , причем A A Bλ λ λ= = = ∅ . Какое-либо состояние набора программных объектов отражает неко- торую часть данных о состоянии моде- лируемого объекта. Все данные о со- стоянии такого объекта, соответст- вующего СПП (X, ε, X, µ, Wвозм ), кото- рые можно получить исходя из опре- деленного состояния набора програм- мных объектов ( )w W X∈ , ,ε X , пред- ставим как ( )F G w Df Bµ µ= ∈        ′′f f f , : .U (17) Нетрудно убедиться в справед- ливости следующего утверждения [8 с. 45], выражающего связь МПрОII и МПрОI. Теорема 1. Пусть (X, ε, X, µ, Wвозм) – МПрОII. Тогда (X, ε, X, Fµ , Wвозм ) – МПрОI, если f µ∈∃∈∀ возмWw ( ),wGF f≡µ . На основе определения СПП за- дача синтеза программы формулирует- ся следующим образом: для известной СПП (X, ε, X, µ, Wвозм ) и указываемых X∈BA, реализовать функцию ( ) ( )f W A W B: * → такую, что ( ) ( )f w F w B ≡ µ для ( )w W Aвозм∈ * . Здесь наборы про- граммных объектов представляют зна- чения входных и выходных парамет- ров, функция f – требуемую програм- му, а СПП (X, ε, X, µ, Wвозм ) – ее спе- цификацию. Очевидно, решение зада- чи следует считать существующим, ес- ли ( )F w W Bвозмµ ∈ для всех ( )w W Aвозм∈ * . Следующее утверждение выра- жает взаимосвязь МПрОII и СПП, а также пути использования СПП. Теорема 2. Пусть (X, ε, X, µ, Wвозм) – СПП, A B, ∈X и для любого ( )w W Aвозм∈ * существует F wµ вида (17) такое, что ( )F w W Bвозмµ ∈ и указанному ( )w W Aвозм∈ * соответствует цепочка f ∈µ* , для которой ( )F w G w Bµ ≡ ′′f f , . (18) Тогда существует МПОII (X, δ, X, ν, V) такая, что ( )E xx ⊂ δ , если {U ≡∈′′∈ wFBx µµ &: * f f ( ) ( )    ∈≡ ′′ AWw,wG возмB & f f , (19) и ( )E xx = δ , если x X∈ не удовлетво- ряет условию (19); при этом Wвозм (X, ε, X) ⊂ V и Wвозм (X, ε, X, A) = Wвозм (X, δ, X, A), Wвозм (X, ε, X, B) = Wвозм (X, δ, X, B ); а каждой h ∈ν соответствует f ∈µ Теоретические и методологические основы программирования 11 такая, что fh AA = , B Bh f= и для ( )w W Aвозм∈ ( ) ( )wfwh ≡ ; причем для лю- бого ( )w W Aвозм∈ * всякой цепочке f ∈µ* , удовлетворяющей условию (18), соответствует цепочка h∈ν* , для ко- торой ( ) ( )F w G w W X Bвозмν δ= ∈h, , ,X, и ( ) ( )F w F w B B ν µ = . Доказательство состоит в про- верке выполнения условий, представ- ляющих заключение теоремы, для пя- терки (X, δ, X, ν, V), где { }δ = ∈ df xD x X: и для любого x X∈ ( )Dx x,≤ – частично упорядоченное множество, += xx ED , ес- ли x удовлетворяет условию (19), и D Ex x= во всех остальных случаях, а ≤ x совпадает с ⊆ x , если x не удовле- творяет условию (19), иначе для ′ ′′ ∈ +d ,d Ex ( )kk ddddddd x ′′≤′′≤∀′′≤′⇔′′≤′ xk& ; { }U N∈= nVV n fd : , ( )V W X df возм1 = , ,ε X и для N∈n {V u u w w Xn df w+ = ⊆ →1 : & : ( ) ∪∪ +1nε ( ){ } [ ] &&,...,1: n nj Vwnj ∈=∪∪ ε &1 nfn wFw =+ }µ∈f& , причем для w∈W(X, δ, X) ( )( ) ( ){ }xwnw df n xwXxw ,min.∈=Λ , [ ] ( )[ ] ( ){ }xwn w df n xwXxw ,min.∈=Λ , где Λ – металамбдаабстракция, а (...)j и [...] j определены выражениями (16) и (15); множество ν составляют функции, которые соответствуют элементам це- почек f ∈µ* , удовлетворяющих усло- вию (18) для некоторых ( )w W Aвозм∈ * , причем для какой-либо из этих функ- ций h ∈ν и соответствующей ей функ- ции f ∈µ для всех w∈W(X, δ, X, Af) и для x B f∈ , если x удовлетворяет усло- вию (19), то для N∈n ( )( )( ) =nxwh ( )nwf= , иначе ( )( ) ( )( ){ }N∈∪= nxwfxwh n : . Теорема 2 показывает опреде- ленное качественное различие между понятиями МПрОII и СПП. МПрОII более отождествляется с “предметной областью”, а СПП – с “проблемной областью”. СПП более ориентирована на учет путей решения представляе- мых задач. В МПрОII знания о пред- метной области представляются хотя и в процедурной форме, но более общо. Это различие можно рассмотреть, сравнивая предложенные выше МПрОII (Y, τ, X, ϕ, U) и СПП(Y′,τ ′, X ′, ϕ ′, U′). 2. Планирование действий синтезируемых программ Еще во времена становления дедуктивного подхода к автоматизации программирования использование ал- горитмических языков высокого уров- ня дало “естественное” толкование ор- ганизации автоматического синтеза программ [12—13]. Его можно предста- вить следующими положениями. Положение 1. Исполнимые про- граммные предложения размещаются в тексте программы в очередности, оп- ределяющейся наличием требуемых значений их входных параметров. Положение 2. Текст программы заканчивается, когда получены значе- ния ее искомых выходных параметров. Положение 3. Исполнимые про- граммные предложения не касаются программы, если они не являются звеньями цепочки исполнимых про- граммных предложений, в которой входные параметры каждого такого звена являются входными параметрами программы или выходными парамет- рами предыдущих звеньев либо преды- дущего звена, а выходные параметры конечного звена содержат хотя бы один выходной параметр программы. Выполнение любой программы, поддерживаемой в какой-либо СПП (X, ε, X, µ, Wвозм ), представляется цепочкой функциональных символов-элементов Теоретические и методологические основы программирования 12 µ, соответствующих действиям про- граммы в их очередности. Рассмотрим свойства таких цепочек и условия их рациональной организации. Пусть для СПП (X, ε, X, µ, Wвозм ), каких-либо f , g ∈µ и n ∈N при n ≤ f ( )( ( &1:&1 &&, 1 1,1 kk mmLkk nLnmf Lkkmn <≤<∈∀+ +−≤=⇔ − = N f=gfg[ ( ) [ ] [ ] .\& &\& 1 1 11 1   ∅≠′′      ∅≠′′∩ + − +− − LmLg km km BB BBA kgkg f f Следующее утверждение пред- ставляет условие рациональной орга- низации действий, выражаемых цепоч- ками функциональных символов СПП. Теорема 3. Пусть (X, ε, X, µ, Wвозм ) – СПП, а f ∈µ . Если для натураль- ного n ≤ f не существует цепочки g ∈µ* такой, что g f[ n , то ( ) [ ] [ ]( )G w G w n n f f f, ,≡ − + 1 1 для любого w∈W(X, ε, X). Нетрудно убедиться в справед- ливости следующего вспомогательного утверждения, которое требуется для доказательства этой теоремы. Лемма 1. Пусть (X, ε, X, µ, Wвозм ) – СПП, а f ∈µ* и B ∈X . Если суще- ствует натуральное m такое, что m < f и       ≤∈′′∪⊆ mj&jBB jf N: , причем ∀ ∈ ≤ ∩ = ∅j j m A Bf j N: , то ( ) ≡′wG ,f ( )wG ′′≡ ,f для каких-либо ∈′′′ ww , ( )fAW возм∈ таких, что ′ ≡ ′′w wB B и ′ ≠ ′′w wB B . Доказательство теоремы 3. Пе- реформулируем эту теорему следую- щим образом. Докажем, что если для некоторого ( )w W X∈ , ,ε X ( ) [ ] [ ]( )wG,wG n n ,1 1 + −≠ fff , (20) то существует цепочка g ∈µ* , для ко- торой g f[ n . Из (20) следует, что [ ]( ) [ ]( )wG,wG nm ,1−≠ ff (21) и [ ]( ) [ ] [ ]     ≠ + − wG,wG k n nk ,1 1 fff (22) для всякого натурального k при n k< . Но тогда лемма 1 в соответствующей формулировке применима к (21) и (22) и удовлетворяет условиям существова- ния элементов требуемой цепочки. Теорема доказана. Рассмотрим несколько утвер- ждений для рациональной организации действий при решении определенных задач. Пусть для СПП (X, ε, X, µ,Wвозм ) { }fggfff nDf nn [µµ ∈∃<∈∀∈≡ :&: NS , а для каких-либо A B, ∈X ( ) Df BA =,z { :&&&: N∈∀′⊆⊆∈= nBBAA Df ffff S [ ] ( )( )}.∅≠∩′=∈∃∈∃         ∅≠′′≤∈∃≤ − BBgfm BAkkn mn kk f f gfgg ff k &:: \&: 1 [N N µ Следующее утверждение пред- ставляет условия, которым удовлетво- ряет каждый шаг рационально орган- зованных действий. Лемма 2. Для каких-либо СПП (X, ε, X, µ, Wвозм ), наборов A B, ∈X и цепочки ( )f ∈ z A B, [ ] [ ] [ ]f f fn A B B B n n ∈ ∪ ∩ ′        − z 1 , для любого натурального n ≤ f . Доказательство. Непосредст- венно из соответствующих определе- ний следует, что [ ] [ ] A A B n nf f ⊆ ∪ − 1 и Теоретические и методологические основы программирования 13 [ ]f n ∈S . Кроме того, очевидно, что [ ]B B n ∩ ′ ⊆ f [ ]n B f ′ . Остается доказать, что для любого натурального n′ при n n≤ ′ ≤ f существует натуральное k такое, что n k n≤ ≤ ′ и [ ] A Bf kk n \ ′′ ≠ ∅ + −f 1 1 , существует цепочка g = df f j Lq j , ,=      1 та- кая, что для некоторого натурального m L< q nm = ′, причем [ ]g f[ n n и [ ]′ ∩ ∩ ′ ≠ ∅B B B n g f . (23) Из определения S следует, что суще- ствует цепочка h= df f i tm i , , =     ∈1 µ та- кая, что h f[ n , но тогда 2mk = , а [ ]g = h 2 . Поскольку ( )f ∈z A B, , то ∅≠∩′ BBh и условие (23) удовлетворяется. Лемма доказана. Следующее утверждение суще- ственно используется в дальнейшем изложении. Теорема 4. Пусть (X, ε, X, µ, Wвозм ) – СПП, для наборов A B, ∈X ( )z A B, ≠ ∅ и для цепочки f ∈µ* ( )f ∈ z A B, . Тогда для какого-либо не- пустого набора ′ ⊆A A f существует цепочка ( ) ( )g g g g= = ∈ ′ df mf i A B i , , ,1 z та- кая, что ′ ⊆ ⊆A A Ag f и ′ ≠ ∅Bg , а для какого-либо ( )w W Aвозм∈ * ( ) [ ] ( ) g ggg gff B BBmB uuGGwG ′′ ′′′+′′       ∪≡ ,,, 1 , где ( )wGu ,f ′= , а ′ = ′ =   f g df f j mj , ,1 и для любого натурального j m≤ −g 1 ′ =f fj j ,если j mi≠ для всех натураль- ных i ≤ g и ′ =f j λ , если j mi= для не- которого натурального i ≤ g . Доказательство. Пусть для ка- кой-либо h∈µ* и любого натурального n при n ≤ h ( ) [ ]( ) ( ∪′=′ AAAAA n df GGG hh ,,,, [ ] [ ]( ) )h hh ,, ,, nAAn BAB ′ ∪′∪ G и ( ) hhAA df =′,,G , если A A Ah ⊆ ∪ ′ и ∅≠′∩ AAh , а если ( )A A Ah \ ∪ ′ ≠ ∅ или A Ah ∩ ′ = ∅ , то ( )G A A h df , ,′ = λ для h ∈µ . Требуемую це- почку g представляет выражение ( )[ ]G A A h k, ,′ для натурального f≤k , ес- ли ( )[ ]′ ⊆ ′ A A A A h kG , , и ( )[ ]B A A h kG , , . ′ ≠ ∅ Такое k существует, поскольку S∈f , а ′ ≠ ∅B f , и если бы утверждение теоре- мы было ложно, то не могло бы суще- ствовать и исходной цепочки f – она ведь тоже удовлетворяет требуемым условиям. Теорема доказана. Из леммы 2 и теоремы 4 вытека- ет справедливость следующего утвер- ждения. Следствие 1. Пусть (X, ε, X, µ, Wвозм) – СПП, для наборов A B, ∈X ( ) ∅≠BA,z , а для любого ( )w W Aвозм∈ * существует ( )BA,z∈f , для которой ( ) ( )F w G ,w W BB возмµ ≡ ∈′′f f . (24) Тогда для какого-либо возможно- го состояния ( )w W Aвозм∈ * и соответст- вующей ему цепочки ( )BA,z∈f , удов- летворяющей условию (24) , для любо- го непустого набора ′ ⊆A A f сущест- вует цепочка ( )g ∈ z A B, такая, что ′ ⊆ ⊆A A Ag f , ′ ≠ ∅Bg и ( ( ) ( ) [ ]( ) })).ff g gg ≤∈⊆       ∈∪≡ ′′′′ jjwGu AWuuGFwF j B w возмB &&,& &:, * N Uµµ Теоретические и методологические основы программирования 14 Представленное утверждение описывает действия подзадачи, поня- тие которой в дедуктивном синтезе программ было введено Э.Х. Тыугу [12, 13], развито М.И. Диковским и А.Я. Кановичем [5, 6]. Очевидно, опи- сываемая подзадача является разде- ляемой, если для указанной цепочки g ее действий A Ag f⊂ , и независимой, если A Ag = ′ . 3. Структурные свойства программных составляющих Представленные выше утвер- ждения основываются на положениях 1—3. Хотя описываемые в них свойст- ва соотносятся с некоторыми необхо- димыми условиями, примеры, опровер- гающие их достаточность, в еще боль- шей степени демонстрируют возмож- ности преднамеренного составления неэффективных вычислительных моде- лей. Перейдем к рассмотрению других структурных свойств исполнимых про- граммных составляющих, позволяю- щих определить их место в синтези- руемых программах. Следующее утверждение пока- зывает возможность полного использо- вания в синтезируемой программе всех знаний, представляемых в СПП соот- ветствующими функциональными за- висимостями. Теорема 5. Пусть (X, ε, X, µ, Wвозм ) – СПП, а для наборов A B, ∈X ( )z A B, .≠ ∅ Тогда для каких-либо ∈gf, ( )BA,z∈ существует ( )BA,z∈h , для ко- торой ( ) ( ) ( )r r rh f g= ∪ . Доказательство. Сначала рас- смотрим условия, которым должна удовлетворять такая цепочка h. Из леммы 1 вытекает, что элементы ис- ходных цепочек f и g должны следовать в h в очередности, задаваемой последо- вательностью множеств ( )H i i, , ,...= 0 1 вида ( ){ ( ) ⊆=∨== ji A'g''f'j df nnnn &:,H ( )( ∉<′∈′∀⊆ jiiiAi ,:& nN ≥′∈′∃∨′ jji :NH ( ))}∅≠∅≠∩⊆≥ ′′ ijijjj AADAAAj \&& nnn , где AA =0 , ∅=0H , 1\ −= iii AAD , а ( )A A B ji i j i= ∪ ∪ ∈            − −1 1n H: , .n Если в какой-либо момент построения такой цепочки h сначала использовать все элементы f, представляемые текущим множеством iH , и перейти к таким элементам из g, то если для некоторого g j окажется, что ∅≠∩ ig AB j , то, в си- лу теоремы 4, существует цепочка s очередных элементов g такая, что ( )s s s∈ ′z A B, и ′ ∩ ′′ = ∅B Bg js . Поэтому, установив в строящейся цепочке h пе- ред указанным элементом g j такую цепочку s, мы сохраняем на текущем участке h все требуемые свойства. Аналогичные соображения справедли- вы и когда происходит формирование участка h, состоящего из одних эле- ментов f. Теорема доказана. Пусть для любого СПП (X, ε, X, µ, Wвозм ) и наборов A B, ∈X ( ) ( ){ ( ) ( ) ( )}.fg gff rrBA BABA Df ⊆∈ ∈∀∈= , &,:, z zZ Из теорем 3 и 5 вытекает спра- ведливость следующего утверждения. Следствие 2. Пусть (X, ε, X, µ, Wвозм ) – СПП, а A B, ∈X и для любо- го ( )w W Aвозм∈ * найдется цепочка f ∈µ* такая, что существует F wµ ≡ ( ) ∈′′f f B,wG ( )BWвозм∈ . Тогда ( )Z A B, ≠ ∅ и для лю- бого ( )w W Aвозм∈ * существует ( )g ∈Z A B, такая, что ( ) ( )F w G ,w W BB возмµ ≡ ∈′′g g . Пусть для любых СПП (X, ε, X, µ, Wвозм ) и наборов A B, ∈X Теоретические и методологические основы программирования 15 ( ) { ( ) ( ) ( ) ( ) ( )&,&& &&:, ,1 1 g df =fffg fgff * = == =∈∈= jj f frr rA,BBA D ZZ µ ( )(( ) ( )( ))}.:& &::& jjjij ji gfggjiif ggjiigjj =⇒≠<∈∀=⇒ ⇒=<∈∃≤∈∀ N NN λ Из следствия 2 вытекает спра- ведливость следующего утверждения, представляющего необходимое условие положительного решения задачи ана- лиза при дедуктивном синтезе про- граммы. Следствие 3. Пусть (X, ε, X, µ, Wвозм ) – СПП, а A B, ∈X и для любо- го ( )w W Aвозм∈ * найдется цепочка f ∈µ* такая, что существует ( ) ∈≡ ′′f f B,wGwFµ ( )BW возм∈ . Тогда ( )Z 1 A B, ≠ ∅ , причем для любого ( )g ∈Z 1 A B, AA ⊆g , B B⊆ ′g и [ ] [ ] [ ]g g gn A B B Bn n ∈ ∪ ∩ ′      −z 1 , для любо- го натурального n ≤ g . 4. Исчисление императивных функциональных схем Логические, а позднее и логико- математические исчисления возникли исторически как средство представле- ния и организации теоретического знания. При попытках автоматизации решения различных задач возникают исчисления “нелогического” типа. Как отмечал С.Ю. Маслов [14, с. 291], мо- делирование таких исчислений в рам- ках классической логики может ока- заться неадекватным по отношению к решаемым задачам. Также представ- ляется практически нецелесообраз- ным и сведение к логическому исчис- лению задач автоматизации програм- мирования. Рассмотрим такое исчисление нелогического типа. Представим фор- мальный язык для описания объектов этого исчисления и его правила, со- держащие условия их использования. Объектами этого исчисления являются императивные функциональные схемы. Они представляют императивные про- граммы. Частный случай таких схем – цепочки функциональных символов, представляющие линейные (ацикличе- ские) программы. Языком линейных схем является язык кортежей функ- циональных символов. Обогатим этот язык средствами для представления подзадач и циклов подобно тому, как это выполнено в [8, с. 100] для случая МПрОII. При этом строка функцио- нальных символов становиться одним из нетерминальных символов грамма- тики. Пусть ′схема′, ′элемент схемы′, ′строка′, ′функциональный символ′, ′цикл′, ′подзадача′, ′набор′, ′абстрак- ция′, ′аппликация′ – нетерминальные символы этого языка, а µ ∪ X ∪ {цикл, для, опр, вып} – множество его терми- нальных символов, причем (X, ε, X, µ, Wвозм ) – СПП. Начальный нетерми- нальный символ – ′схема′. Синтакси- ческие правила грамматики рассматри- ваемого формального языка предста- вим в бэкус-науровой форме: <схема>::=<схема><схема>\|<элемент схемы> <элемент схемы>::=<строка>\|<цикл>\| <абстракция>\|<аппликация> <строка>::=<строка><функциональный символ><функциональный символ> <цикл>::=цикл <подзадача> <подзадача>::=для <набор> <абстракция>::=опр <подзадача> <аппликация>::=вып <подзадача> <функциональный символ>::=f\|g\|... <набор>::=A\|B\|...\|S\|... где { },..., gf=µ , { },...,...,, SBA=X . При этом для схем ξ, η и ζ ηξζ AAA ∪= , ( )ξηξζ BAAA \∪= , ηξζ BBB ∪= , ηξζ BBB ′′∪′′=′′ , ηζζ BBB ′′=′ \ , если ζ ξη= . Семантика абстракции и аппли- кации предполагает введение в СПП Теоретические и методологические основы программирования 16 подзадачи – программного объекта ƒ с функциональным значением, как это выполнено в [8] для МПрОII. Если Cдляопр≡ζ , то XA =ζ , ∅=ζA , а ( ){ }B B Cζ ζ= ′ = ƒ . Для ζ ≡ выпдляC или ζ ≡ циклдляC наборы ζA , ζA и ζB , ζB′ , ζB ′′ соответствуют наборам gA , gA , gB , gB′ , gB ′′ следствия 1. Семантика рассматриваемого формального языка выражается функ- цией ( )H wζ , , представляющей значе- ние схемы ζ для исходного возможного состояния w подобно тому, как это вы- полнено в [8, с. 102—106]. Очевидно, ( ) ( )wGwH ,, ζζ ≡ , (25) если µζ ∈ ; ( ) ( ) ∈Λ=Λ∪≡ vCtwwCдляопрH ., f ( ) ( )( )vwFFCW Cвозм ∪∈ µµ. ; (26) ( ) ( )( )( ) ( ){ }( )     ∪∈∪ ≡ ≡ случаях;остальных всех во ,если, w CCWwwCw wCдлявыпH возмC ff , ( ) (∪∪≡ wwCдляциклH , ( ) ( ){ })wCдляциклHuuCдлявыпH ,:, ⊆∪ . (28) Изложенные выше утверждения позволяют представить следующие правила вывода в исчислении импера- тивных функциональных схем: &&&,1 ξηξ BAAAABA ∪⊆⊆∅≠   Z ( ) ξηηξη ξξ →⇒′∩∪∈ ,,& BBBAz , (29) ( ) :,&, 11 N∈∃∈∃∅≠    mBABA ZZ f [ ] AдляопрBAAm m ′→⇒∪⊆′≤ −1f f , (30) A B оп для A Bξ ξ ξ ξ∩ ≠ ∅⇒ ∩ →р циклдля A Bξ ξ→ ∩ , (31) →′⇒∪⊆′ AдляопрBAA ξξξ Aдлявып ′→ξ , (32) где A A B, ,′ – наборы в СПП (X, ε, X, µ, Wвозм), а ξ, η – императивные функ- циональные схемы, синтаксис которых описан в бэкус-науровой форме, а се- мантика – в выражениях (25)—(28). Аксиомами представляемого исчисле- ния являются функциональные симво- лы-элементы µ, рассматриваемые как функциональные схемы – одноэле- ментные кортежи. Следует отметить, что наличие выделенных определенных условий использования правил (29)—(32) позво- ляет получить практический метод по- строения вывода требуемой импера- тивной функциональной схемы, неко- торым образом основываясь на воз- зрениях С.Ю. Маслова о “башне де- дуктивных систем” [15]. 5. Организация автоматического синтеза программ с переприсваиваниями Рассмотрим подход к организа- ции автоматического синтеза про- грамм, основывающийся на использо- вании баз данных для задач построе- ния конкретных программ и на про- граммной реализации построения вы- водов в представленном исчислении. Проанализируем для этого существо немонотонности в дедуктивных по- строениях. Пусть имеющиеся данные о со- стоянии некоторого моделируемого объекта рассматриваются как состоя- ние среды программы. Это состояние может представлять конъюнкция ло- гических выражений. Если для опи- сания такого объекта использовать определенную СПП (X, ε, X, µ, Wвозм ), то указанное состояние среды пред- ставляется некоторым w∈Wвозм. Но обращение к какой-либо функцио- нальной зависимости f ∈ µ может вы- звать изменение состояния среды, причем этому измененному состоя- (27) Теоретические и методологические основы программирования 17 нию, представляемому w f wB f A f ∪     , соответствует конъюнкция логиче- ских выражений, получаемая из ис- ходной не только добавлением новых конъюнктов, но и удалением или из- менением исходных. Иными словами, происходит немонотонное изменение состояния среды программы, которое с адекватной сложностью невозмож- но отразить в рамках классической логики. Состояния объектов среды свя- зываются отношениями, представляе- мыми в СПП функциональными зави- симостями, которые можно истолко- вывать как правила изменения состоя- ния среды. Таким образом, СПП пред- ставляет собой семантическую сеть (рис. 1). Осуществив редукцию [15] Рис. 1 Теоретические и методологические основы программирования 18 описанного выше исчисления импера- тивных функциональных схем, можно получить однопосылочное исчисление, объектами которого являются описа- ния состояния среды построения про- граммы. Каждое такое описание отли- чается от семантической сети СПП лишь тем, что к концептам этой сети типа ’объект’ и ’правило’ добавляются еще атрибуты, отражающие текущее представление о месте отображаемого объекта, или правила в строящейся программе (рис. 2). Иначе говоря, до- бавляется еще один параметр со слож- ным структурированным значением, представляющим релевантность таких концептов требуемой программе. Данные, во взаимосвязи их по- лучения и использования, при выпол- нении программы возникают волнами. Начальную волну образуют входные данные программы, а конечная волна должна включать выходные. Но и дей- ствия по выполнению команд тоже происходят волнами. Начальную такую волну образуют действия над входны- ми данными. Конечную – действия, завершающие получение выходных данных. Можно говорить о соответст- вующих волнах объектов и правил среды построения программы. Такие волны можно строить как от начально- го состояния этой среды (входные вол- ны), так и в обратном направлении – от ее желательного конечного состоя- ния (выходные волны). Критерием ре- левантности концепта (объекта или правила) программе является его при- надлежность к пересечению каких- либо ее входных и выходных волн. Отметим, что приведенные выше рас- суждения непосредственно вытекают из следствия 3. Итак, значение релевантности каждого концепта ‘объект‘ или ‘прави- ло‘ среды построения программы в свою очередь имеет атрибуты ‘номер входной волны‘ и ‘номер выходной волны‘ с целыми неотрицательными необязательными значениями (рис. 3). В случае ациклической програм- мы или монотонной логической систе- мы синтез программы сводится к по- строению указанных пересечений Рис. 2 Теоретические и методологические основы программирования 19 волн. Однако как раз состояния по- строения программы, связанные с пе- реприсваиваниями, с утратой моно- тонности, позволяют синтезировать со- ставляющие, в которых проявляется ее программистская сущность и достоин- ства – циклические предложения, проверки, локальные процедуры. Из следствия 1 вытекает, что всякое немонотонное изменение со- стояния среды программы для объек- тов, состояние которых уже имело оп- ределенное значение, является цикли- ческим. Участок программы, состав- ляющий тело цикла, начинает образо- вываться от объектов, состояние кото- рых претерпело такое изменение, до объектов, для которых оговорены только монотонные изменения состоя- ния во всех правилах. Такое образова- ние участка происходит в пределах общих волн объектов и правил (пере- сечений их входных и выходных волн). Так образуется тело цикла- рекурсии, если упомянутое немоно- тонное изменение состояния объектов вызывается выполнением правила, принадлежащего этому же участку. Ес- Рис. 3 Рис. 4 Теоретические и методологические основы программирования 20 ли же немонотонное изменение со- стояния вызвано существованием не- скольких независимых правил, обла- дающих общим выходным объектом (или объектами), для которого (или для которых) возможны немонотонные из- менения состояния, то имеет место итерация. Следует учесть возможность су- ществования монотонных циклических изменений, рассмотренную в [14]. Мо- нотонное изменение состояния среды программы для объектов, состояние которых уже имело определенное зна- чение, является циклическим, если оно вызвано применением правила, со- стояние входных объектов (объекта) которого определяется состоянием вышеуказанных объектов. Иными сло- вами, очередность, определяемая для этого правила номерами входной и вы- ходной волн, предполагает по крайней мере для одного его выходного объекта номер входной волны не более номера входной волны самого правила. Итак, параметр ‘релевантность‘ должен иметь еще один атрибут – ‘вложенность‘ (рис. 3). Значение этого атрибута представляет отношение со- ответствующего концепта среды по- строения программы к ее циклическим предложениям (рис. 4, 5). Из вышеизложенного следует, что рассматриваемое исчисление со- стояний среды построения программ содержит правила вывода для опреде- ления очередности в тексте програм- мы, циклических изменений, очеред- ности в пределах тел циклов. Процесс построения вывода ко- нечного состояния среды построения требуемой программы Пk из ее началь- ного состояния П0 в этом исчислении имеет вид Рис. 5 Теоретические и методологические основы программирования 21 Начальное состояние П0 пред- ставляет условия решаемой задачи, оп- ределенные для модели ее предметной области. Требуемая программа извле- кается из конечного состояния Пk сре- ды ее построения. Таким образом, при автоматиче- ском синтезе конкретной программы с переприсваиваниями по условиям по- ставленной задачи строится описание среды в форме семантической сети, представленной на рис. 1. Среда по- строения программы получается из этой модели предметной области вве- дением параметра ‘релевантность‘ всем определенным в этой модели объектам и правилам. В начальном состоянии определены только начальная (первая) входная и начальная (первая) выходная волны объектов. Начальную входную волну образуют объекты, соответст- вующие входным параметрам требуе- мой программы, а начальную выход- ную – объекты, соответствующие ее выходным параметрам. Поэтому в на- чальном состоянии среды построения программы в параметре ‘релевант- ность‘ определены только значения номера входной волны (равные едини- це) для объектов, соответствующих входным параметрам программы, и значения номера выходной волны (то- же равные единице) для объектов, со- ответствующих выходным параметрам программы. При выполнении правила опре- деления очередности в тексте про- граммы получают значения номера входных и выходных волн для объек- тов и правил изменения состояния среды программы. Тем самым уста- навливается принадлежность соответ- ствующих исполнимых программных предложений требуемой программе и порядок их следования в тексте. Од- новременно решается задача анализа: если конечная входная волна не со- держит объектов, соответствующих выходным параметрам требуемой про- граммы, или конечная выходная волна не пересекается с объектами, соответ- ствующими входным параметрам тре- буемой программы, то не существует решения задачи, которое должно по- лучаться при выполнении требуемой программы, и такая программа не мо- жет быть построена для представлен- ной модели предметной области. Если задача анализа решается положитель- но, то текст требуемой программы бу- дет включать исполнимые программ- ные предложения, соответствующие правилам изменения состояния среды, для которых получены одновременно номера входной и выходной волн в очередности, определяемой порядком увеличения номера входной волны. При выполнении правила опре- деления циклических изменений для вывода в исчислении состояний СПП происходит построение списка указа- телей циклических предложений, при- надлежащих требуемой программе. Для всех правил изменения состояния среды программы осуществляется про- верка условий, связанных с определе- нием атрибута ‘вложение‘. Формиру- ются наборы соответствующих цикли- чески изменяемых объектов, принад- лежащих одной входной волне. При выполнении правила опре- деления очередности в пределах тел циклов для вывода в рассматриваемом исчислении проверяется очередность следования объектов и правил от таких наборов до объектов, состояние кото- рых изменяется монотонно. Такие пра- вила представляют исполнимые про- граммные предложения, располагаю- щиеся в соответствующих телах цик- лов в определяемой таким образом очередности. Вложений может быть несколько, поскольку циклы могут вкладываться. Программа извлекается из ко- нечного состояния среды ее построе- П0 → ... ... ... → Пi → ... ... ... → Пj → ... ... ...→ Пk определение принадлежности и очередности расположения в тексте программы определение циклических изменений определение принадлежности и очередности расположения в циклах Теоретические и методологические основы программирования 22 ния в соответствии с очередностью следования исполнимых программных предложений и их принадлежностью телам циклов. В указанной очередно- сти предварительно отрабатываются релевантные объекты – им в про- грамме соответствуют описания (на- чальная входная волна объектов) и управляющие предложения (начальной волне объектов каждого тела цикла от- вечает предложение начала цикла, ко- нечной – конца). Выводы Представляется обоснованной возможность автоматического синтеза каких-либо практически исполнимых программ, т.е. программ с перепри- сваиваниями. Такой синтез можно рас- сматривать как поддерживаемую спе- циальными инструментальными сред- ствами технологию программирования в существующих средах на сущест- вующих языках. За рамками настоящей статьи осталось несколько важных и интерес- ных вопросов: не затрагивались общие вопросы синтеза алгоритмических описаний планов решений, рассматриваемые в работах Ю.В. Капитоновой, А.А. Лети- чевского и др. (см., напр., [16]); не рассматривалась интересная возможность использования понятия фиксированной точки [10, 11]; представляет интерес изучение возможностей использования вырази- тельных средств экспликативного и композиционного программирования, обсуждение семиотических аспектов формирования немонотонных вычис- лительных моделей (состояние объекта среды программы можно истолковы- вать как его значение, а его соотноше- ния со смежными в семантической се- ти СПП правилами – как смысл и в этой связи открываются большие воз- можности для приложения композици- онных и экспликативных воззрений [17, 18]); представляется эффективным развитие теоретико-модельных подхо- дов к изучению немонотонных дедук- тивных построений для автоматическо- го синтеза программ, в частности в связи с вопросами синтеза устойчивых вычислительных алгоритмов. Эти во- просы требуют отдельного дальнейше- го обсуждения. 1. Ершов А.П. Автоматизация программиро- вания // Математическая энциклопедия / Под ред. И. М. Виноградов (глав. ред.) и др. Т. 1. – М.: Сов. энцикл., 1977. – С. 58—59. 2. Чень Ч., Ли Р. Математическая логика и машинное доказательство теорем. – М.: Наука, 1983. – 360 с. 3. Лавров С.С. Синтез программ // Киберне- тика. – 1982. – № 6. – С. 11—16. 4. Тыугу Э.Х. Концептуальное программиро- вание. – М.: Наука, 1984. – 256 с. 5. Диковский А.Я., Канович М.И. Вычисли- тельные модели с разделяемыми подзада- чами // Изв. АН СССР. Техн. кибернетика. – 1985. – №5. – С.36—59. 6. Канович М.И. Логические основы синтеза схем программ для решения вычислитель- ных задач // Там же. – 1988. – №2. – С. 82—93. 7. Логический подход к искусственному ин- теллекту: от классической логики к логиче- скому программированию: Пер. с франц. / А. Тейз, П. Грибомон, Ж. Луи и др. – М.: Мир, 1990. – 432 с. 8. Приходько П.П. Функциональный подход к концептуальному программированию // Дис. ... канд. физ.-мат. наук. – Киев, 1991. – 177 с. 9. Приходько П.П. О возможном подходе к организации синтеза программ для струк- турированных данных // УСиМ. – 1992. – № 3/4. – С.70—74. 10. Скотт Д. Набросок математической тео- рии вычислений // Кибернет. сб. Нов. сер. – М.: Мир, 1977. – Вып. 14. – С. 107—121. 11. Скотт Д. Теория решеток, типы данных и семантика // Введение в языки програм- мирования. Абстракция и типология: Сб. ст. – М.: Мир , 1982. – С.25—53. 12. Тыугу Э.Х. Решение задач на вычислитель- ных моделях // ЖВМ и МФ. – 1970. – Т. 10, № 3. – С. 716—733. 13. Тыугу Э.Х. Решатель вычислительных за- дач // Там же. – 1971. – Т. 11, № 4. – С. 992—1004. 14. Маслов С.Ю., Минц Г.Е. Теория поиска вы- вода и обратный метод: Дополнение // Чень Ч., Ли Р. Математическая логика и машинное доказательство теорем. – М.: Наука, 1983. – С. 291—326. 15. Маслов С.Ю. Теория дедуктивных систем и ее применения. – М.: Радио и связь, 1986. – 136 с. 16. Об использовании систем уравнений над структурами данных для спецификации и Теоретические и методологические основы программирования 23 синтеза программ / Ю.В. Капитонова, А.А. Летичевский, С.П. Горлач, Г.Н. Горлач // Кибернетика. – 1989. – №1. – С. 19—29. 17. Редько В.Н. Композиционная структура программологии // Кибернетика и систем- ный анализ. – 1998. – № 4. – С. 47—60. 18. Редько В.Н. Экспликативное программиро- вание: ретроспективы и перспективы // Тр. I Междунар. науч.-практ. конф. по про- граммированию. – Киев, 1998. – С. 3—24. Получено 18.03.03 Об авторе Приходько Павел Петрович, канд. физ.-мат. наук, старший научный сотрудник Место работы автора: Институт программных систем НАН Украины, просп. Академика Глушкова, 40, Киев-187, 03680, Украина Тел. (044) 532 4690

О возможных основаниях немонотонного дедуктивного синтеза программ

Institution

Ähnliche Einträge