Содержание к диссертации
Введение
1. Исследование проблемно-ориентированных языков и средств их реализации II
1.1. Принцишпостроения проблемно-ориентированных языков II
1.2. Способы реализации проблемно-ориентированных языков 24
1.3. Автоматизация реализации проблемно-ориентированных языков 32
1.4. Результаты и выводы 41
2. Формальное описание языка БЭКУС 44
2.1. Метаязык - как средство формального описания алгоритмов 44
2.2. Формальное описание управляющих конструкций языка БЭКУС 55
2.3. Формальное описание терминалов 63
2.4. Результаты и выводы 76
3. Исследование языка БЭКУС 77
3.1. Основные свойства конструкций языка БЭКУС . 77
3.2. Структурность языка БЭКУС 88
3.3. Особенности выполнения программ на языке БЭКУС 93
3.4. Методика написания программ на языке БЭКУС 96
3.5. Результаты и выводы 107
4. Система автоматизированного проектирования специализи рованных языков " LANk" 109
4.1. Принципы организации системы "LAN&." 109
4.2. Методика разработки проблемно-ориентированных языков в системе "XA/TG " jjr,
4.3. Реализация входного языка САПР ФОТ . 12з
4.1. Реализация препроцессора с языка РАТФОР в язык фортран 128
4.5. Реализация языка описания электрических схем J35
4.6. Результаты и выводы 137
Заключение J3g
Литература
- Принцишпостроения проблемно-ориентированных языков
- Метаязык - как средство формального описания алгоритмов
- Основные свойства конструкций языка БЭКУС .
- Принципы организации системы "LAN&."
Принцишпостроения проблемно-ориентированных языков
Последние двадцать-тридцать лет стали эпохой бурного развития языков, ориентированных на решение определенных проблем. Сейчас можно насчитать несколько сотен таких языков, причем языков, получивших заслуженное признание. Приблизительно в то же время были разработаны и реализованы сотни других языков, использовавшихся некоторое время, а затем бесследно исчезнувших. Причины успеха или неудачи какого-либо языка могут быть самыми различными. Они могут быть как чисто внешними по отношению к данному языку, так и внутренне ему присущими.
Пионером проблемно-ориентированных языков (ПОЯ) можно смело назвать алгебраический язык ФОРТРАН. Во времена его создания решение задач непрограммистами рассматривалось как сумасбродная идея, которая никогда не сможет ликвидировать превосходство программиста. Разработчики же ФОРТРАНа убедительно продемонстрировали, что при трансляции с алгебраического языка можно получать эффективные программы, и тем самым позволили непрограммистам самим решать свои проблемы, не прибегая к услугам программистов
Следующим специализированным языком, который продемонстрировал целесообразность создания ПОЯ, являлся КОБОЛ. Этот язык впервые позволил решать экономические задачи и на протяжении многих лет он был единственным доступным средством обработки экономических данных.
Заслуги этих двух языков были в том, что они дали ощутимый толчок к созданию и развитию ПОЯ. И поэтому не удивительно, что многие проблемно-ориентированные языки строились именно как расширение КОБОЛа или ФОРТРАНа.
В ряде зарубежных работ приведены длинные списки и краткие аннотации удачно реализованных проблемно-ориентированных языков, получивших широкое распространение и относящихся к различным областям [98, 100, 103, 112, 107, 114, 115, 117, 119, 126, 133].
Удачные отечественные разработки отображены в следующем ряде работ [I, 7, 15, 19, 23, 25, 32, 41, 47, 57, 70, 76, 77, 90, 92, 134-138].
Как видно только из списка разработок, количество ПОЯ огромно и существует тенденция к еще большему их увеличению. Такое изобилие языков находится в явном противоречии с тем фактом, что конструирование этих языков еще очень далеко от совершенства. Каждый из языков, представленных в литературе, имеет много недостатков, но и в то же время, анализируя их, можно сформулировать ряд общих принципов разработки хороших проблемно-ориентированных языков.
Существующие разработки свидетельствуют, что некоторые ПОЯ возникли и создавались часто случайно: на проработку их были потрачены крайне незначительные усилия, и поэтому, как следствие, они отличаются или примитивизмом и неструктурностью, или необоснованной усложненностью и обилием деталей, которые должен запомнить пользователь ПОЯ, что, в свою очередь, сводит на нет те преимущества, которые дает использование ПОЯ в заданной области.
Поэтому первый принцип при построении хорошего ПОЯ заключается в том, что его разработчики должны ясно представлять себе, чего они хотят добиться. Поэтому их цели должны быть хорошо продуманы и структурированы. Без выполнения этого принципа немые лимо достижение такой важной характеристики языка как ясность и согласованность его понятий [7Ї]. ПОЯ, как и любой другой язык, представляет собой систему понятий и средств выражения специализированных задач. Язык должен предоставлять специалисту гармоничную систему понятий, просто и ясно выражающих специфику проблемной области, которые он может использовать как элементарные при описании своих задач. Поэтому желательно иметь минимальное число таких понятий, а правила, по которым группируются эти понятия, должны быть простыми и естественными [29].
Ясно поставленные цели важно иметь также потому, что всякая разработка ПОЯ представляет собой совокупность компромиссов. Поэтому без явно очерченных целей разработчик не может судить, когда и как прийти к компромиссу. Так, например, при разработке языка приходится считаться с двумя прямопротивоположными требованиями: с одной стороны, надо, чтобы язык удовлетворял всем требованиям пользователя, а, с другой, надо учитывать реальность разработки. Хотя требования пользователя являются определяющими, не всегда их можно реализовать с теми затратами ресурсов, которые допускаются при реализации языковой части САПР.
Следующим важным принципом, которым надо руководствоваться при разработке языков, является принцип обеспечения языка единообразием и ясной структурой. Единообразие языка - это запрещение использования особых случаев. Единообразие существенное упрощает жизнь пользователя, так как он должен меньше запоминать информации об языке. С понятием единообразия тесно связано понятие ортогональности, которое означает, что между отдельными языковыми понятиями не должно быть взаимного влияния.
Метаязык - как средство формального описания алгоритмов
В настоящее время в таких областях, как искусственный интеллект и исследование операцийУхорошо себя зарекомендовали алгоритмы с возвратами ( BACKTRACK ). Эти алгоритмы позволяют решить широкий спектр задач от/ чисжовЕтасш1тельннх до логических. В качестве примера, можно [привести длинный список таких разработок, использующих алгоритмы BACKTRACK , наиболее удачными из которых являются: SAINT - программа вычисления неопределенных интегралов; MATCH - комплекс вычислительных программ, позволяющий ставить и решать задачи в общем виде; GPS! - универсальный решатель задач; СНА6&Е - программы, играющие в шахматы.,
Особенностью алгоритмов BACKTRACK является то, что действительный путь решения таких задач практически всегда не известен и он существенным образом меняется в зависимости от исходных данных. Этот класс задач решается серией последовательных испытаний, методом проб и ошибок, используя при этом допустимые альтернативы. При возникновении тупиковых ситуаций такие алгоритмы возвращаются назад для поиска пути решения по другим веткам дерева решений С 58].
В алгоритмах с возвратами каждый этап соответствует одной из трех ситуаций: - решение найдено; - имеется еще некоторое множество возможных действий, ко торые могут привести к решению; - тупиковая ситуация, когда данным путем решение найдено быть не может.
В первом случае алгоритм завершен. Во втором может быть выбрано согласно какому-то критерию одно из действий и включено в путь решения. И наконец, в последнем случае надо вернуться назад к самому последнему этапу, на котором еще не были исчерпаны все возможные альтернативы, и, применяя еще неиспользованную альтернативу, попытаться снова построить путь решения. Если исчерпаны все альтернативы, то надо вернуться к еще более раннему этапу и т.д. Этот алгоритм применяется до тех пор, пока не возншсает две ситуации; - решение найдено и алгоритм перешел в некоторое конечное состояние; - решение не найдено, алгоритм возвратился в иоходное состояние .
Как следует из вышесказанного, для того чтобы решить задачу Р (ее функцию обозначим как Р ), необходимо решить последовательность более простых задач Р± , Р2 ,..., Ра (с их функциями Р4 » Р2 » t Ра ) і при этом существует только два способа формирования задачи Р при помощи подзадач: 1. Найти подзадачи Р± , Рг ,..., Ра такие, что M(X,Y)Y SOO}U{ 2. Найти подзадачи Pt, Р2 ..... РЛ такие, что P = {(X T)Y-Pnop 1o....op2opi(x)}
В свою очередь, подзадачи Рх , Р& ,..., Р могут быть составными и иметь свои подзадачи и т.д. И наконец, на самом ниж нем уровне находятся подзадачи, представляющие собой элементарные действия, выполняющие, например, роль критериев. Такие элементарные операции или могут быть непосредственно выполнены, тогда они входят в путь решения и принимают значение "истина", или не могут быть выполнены, тогда они соответствуют задачам, не имеющим решения, и принимают значение "ложь".
Рассмотрим теперь составные задачи.
Если задача состоит, из подзадач, связанных условием "ШШ", то ясно, что сама эта задача соответствует решаемой задаче и принимает значение "истина" тогда и только тогда, когда существует хотя бы одна подзадача, принявшая значение "истина", т.е. принадлежит решаемой задаче.
Если задача состоит из подзадач, связанных условием "И", то в этом случае задача соответствует решаемой задаче и принимает значение "истина" тогда и только тогда, когда все ее подзадачи принимают значение "истина" и принадлежат решаемой задаче.
Эти правила выполнения применяются рекурсивно. Результатом применения правил будет дерево, вершиной которого является начальное состояние, а листьями - элементарные непосредственно выполняемые действия. Последовательность действий, ведущая к решению задачи, называется путем решения. Поэтому целью алгоритма с возвратами „является в нахождении пути решения, ведущего из начального состояния к некоторому конечному состоянию.
Основные свойства конструкций языка БЭКУС .
Программы на метаязыке БЭКУС всегда имеют один вход и один выход, поэтому их действие на множество данных может быть оценено по состоянию на входе и выходе. Элементарные программы -это продукции, составленные из управляющих конструкций языка БЭКУС, которые в определенном смысле являются неделимыми. Поэтому важную роль играют программные функции, которые позволяют для каждого исходного состояния X поставить в соответствие результирующее состояние Y , поэтому программная функция выступает как множество упорядоченных пар {(X,Y)} Программные функции являются точными и исчерпывающими описаниями действия элементарных программ на данные - от исходного состояния X до их конечного состояния Y .
Рассмотрим программные функции основных конструкций. Обо-значим ї программную функцию элементарной продукции Т . Тогда по определению простой терминал и нетерминал, реализующий функцию 1"=: j"(X,Yj} имеет программную функцию Т- {(X jlY
Программной функцией последовательности из двух и более терминалов и нетерминалов будет композиция функций каждого из этих символов:
Теперь рассмотрим программную функцию повторяющейся спецификации. Для этого введем предикат р(Х) , который принимает значение истина тогда и только тогда, когда применимость конструкции X - истина. Можно заметить, что для последовательности т.е. истинность пути действии складывается из истинности отдельных действий.
Важным вопросом, который необходимо рассмотреть применительно к конструкциям языка БЭКУС, является вопрос правильности программ. Это связано с тем, что основным критерием качества программного обеспечения является его правильность. При этом правильность определяется как соответствие мевду программой и ее заданной функцией [51, 97]. Доказательство правильности всей программы сводится к доказательству правильности отдельных элементарных конструкций.
Рассматривая .-. программные функции, можно заметить, что все программы языка БЭКУС могут быть выражены через элементарные конструкции, которые могут быть верифицированы посредством применения методов доказательства, требуемых для конструкций типа последовательность и повторяющаяся спецификация, при этом условие правильности этих конструкций выражается описанными выше программными функциями.
Какие бы формализмы не применялись при доказательстве, реально, однако, доказательство даже простых программ сталкивается с большими трудностями, а сами доказательства становятся слишком тяжеловесными, поэтому доказательство программ большого размера практически неосуществимо. Можно также отметить [91], что доказательство правильности программ располагается на том же интеллектуальном уровне, что и само программирование, поэтому в само доказательство могут вкрадываться ошибки и, как следствие, доказательство может потребовать своего доказательства.
Из сказанного выше можно сделать вывод о том, что бесполезно пытаться доказать правильность уже существующих программ. Дейкстрой [37] был предложен метод, который состоит в написании уже правильных программ, исходя из доказательства, проводимого параллельно с написанием.
Конструкции языка БЭКУС для этого идеально подходят, при этом проектирование правильных программ заключается в использовании заведомо правильных конструкций, программные функции которых совпадают с заданной функцией. Например, пусть дана некоторая функция z =з абз(min(x,y)) , тогда можно сначала рассмотреть решение:
Принципы организации системы "LAN&."
Как уже отмечалось во введении, повышенный и все возрастающий интерес к проблеме автоматизации разработки языков общения пользователя с САПР, объясняется в первую очередь резким увеличением контингента неподготовленных пользователей из промышленности. Естественным требованием этих пользователей является использование для взаимодействия с ЭВМ простого, ориентированного на их предметную область языка [82 ] . Задачи, которые приходится решать при создании такого языка, зачастую не подсилу проблемному программисту и тем более неспециалисту.
Языки САПР в полной мере обладают свойствами, перечисленными в первой главе. Именно эта специфика является основным тормозом на пути повышения эффективности их использования САПР. Именно поэтому пользователи САПР вынуждены использовать примитивные или малопонятные для них языки. Для ликвидации языковых барьеров между неспециалистами в области программирования и САПР, а также для обеспечения высокой эффективности процесса проектирования была создана диалоговая система проектирования специализированных языков " LANGt"«
Важным вопросом, который пришлось решить при создании системы " LAN&", был вопрос о принципах организации системы "LAMS.". Естественно, в этих принципах должным образом нашли свое отражение принципы разработки ПОЯ и построения метаязыка БЭКУС, изложенные в предыдущих главах.
Рассмотрим поэтому основные принципы организации системы " LAN&". функционально система " LANGt" разделена на две части: подсистему этапа проектирования языка и подсистему этапа эксплуатации языка. Деление системы на две части связано с существенным различием требований, предъявляемых к системе проектирования языка на стадиях проектирования и эксплуатации языка.
Этап проектирования языка включает в себя составление описания, кодирование и тестирование входного языка и выходных форм. Поэтому основными требованиями на этом этапе являются: - простота и полнота описания проектируемого языка, оперативность внесения изменений в проектируемый язык; - простота и полнота тестирования, проверки правильности описания языка; - получение объективных характеристик будущего транслятора с описываемого языка; - использование при отладке языка только логических характеристик данных.
Как уже указывалось в первой главе, этим требованиям удовлетворяет интерпретатор. Он позволяет в диалоговом режиме описывать языки, изменять их, отлаживать и оперативно вмешиваться в ход разбора и генерации. Поэтому на этапе проектирования языка система выступает как интерпретатор описания проектируемого языка, и основной акцент в этом случае делается на сервисные возможности системы. А это, естественно, приводит к существенному дополнительному расходу памяти и увеличению времени работы системы на обработку описания проектируемого языка.
С другой стороны, на этапе эксплуатации языка основными требованиями являются: - получение минимального объема памяти, занимаемого разра ботанным компилятором; - сокращение времени обработки запросов на описываемом языке; - использование разработанного компилятора вне системы проектирования языков; - использование данных согласно их физическим характеристикам, что существенно сокращает время обработки запросов на проектируемом языке.
Этим требованиям удовлетворяет компилятор. Поэтому перед этапом эксплуатации система " LANG " выступает как компилятор-компиляторов. Система переводит описание на метаязыке в коды команд системного ядра, при этом из описания исключаются все функции, связанные с тестированием и сервисным обслуживанием языка. Это позволяет, с одной стороны, существенно сократить время расшифровки и генерации по описанию языка, а с другой стороны, позволяет существенно сократить объем памяти, занимаемый описанием. Сокращение этого объема происходит за счет того, что системные команды представляют собой обобщенные операции, которые в традиционных языках программирования занимают от 50 до 100 операторов (на языке ФОРТРАН это около 500 байт), а в системе "bANG" они занимают всего около 8 байт.
