ОБЗОР ВОЗМОЖНОСТИ АВТОМАТИЧЕСКОГО СИНТЕЗА ПРОГРАММ

Задача автоматического синтеза программ, по сути, означает автоматическое решение заданной проблемы таким образом, чтобы решение было понятным для компьютера. Программирование часто считают очень многообещающей областью информатики. Оно тесно связано с искусственным интеллектом, потому что у них обоих общая задача - автоматизировать определенные творческие действия человека. Близкие родственники часто используют похожие методы для выполнения аналогичных задач. Например, в некоторых методах автоматического синтеза программ эвристический поиск используется аналогично тому, как эвристический поиск используется при автоматическом решении задач. С другой стороны, автоматический синтез программ поддерживает также тесную связь с методологией программирования, потому что оба изучают процесс построения программы. Мы не можем автоматизировать процесс построения программы, если не понимаем, как программировать достаточно глубоко, чтобы иметь возможность формализовать наши знания. И снова, с другой стороны, попытка автоматизировать программирование может привести нас к новым методам программирования, которые могут вытеснить традиционные методы ручного программирования в будущем. Это может быть полезным побочным эффектом попытки автоматизировать создание программ, даже если полная автоматизация никогда не будет достигнута.

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

Есть разные способы составления программы. Что касается содержания, спецификация проблемы описывает, как вывод программы должен быть связан с вводом программы. Что касается формы, проблема может быть определена набором примеров пар ввода / вывода или набором примеров его трассировок вычислений. Оба эти способа по сути неполны, поскольку набор примеров, не включает все возможные входы и соответствующие выходы. Другая форма спецификации, которая состоит из условий ввода и вывода, выраженных в виде формул исчисления предикатов первого порядка, служит отправной точкой процесса вывода программы. На этом уровне задачу автоматического синтеза программ можно рассматривать как задачу доказательства теоремы.

для всех: Input (x) -> Output (x, y)} , т.е. как функция f такая для всех x: Input (x) -> Output (x.f (x)).

Однако обычно используются более практичные языки. Часто спецификация состоит из двух частей, озаглавленных словами COMPUTE и WHERE для условий вывода и ввода, соответственно. В общем, любой язык спецификаций, основанный непосредственно на исчислении предикатов, наследует от него точность и элегантность, которые, без сомнения, являются важными свойствами любого документа, участвующего в программном синтезе. Большая трудность состоит в сложностях описания реальных проблем на языке формул исчисления предикатов. Следует отметить, что были исследованы также другие формальные подходы и разработаны другие формальные языки, помимо чистого исчисления предикатов. Сообщалось о работах, в которых решались проблемы крупного масштаба. Были попытки описания на языке спецификации [3].

Еще один важный вопрос, связанный данной проблемой, заключается в том, что слишком идеалистично предполагать, что полную спецификацию проблемы можно написать за один шаг, прежде чем начнется реальное решение проблемы, которое в конечном итоге приведет к формированию желаемой программы. Гораздо более реалистично признать, что спецификация будет разрабатываться постепенно и может быть неполной по крайней мере на начальном этапе. Процесс её создания следует рассматривать как часть процесса решения проблемы [1].

В семидесятых годах было опубликовано несколько методов, пытающихся полностью автоматизировать задачу программирования. Они способны автоматически синтезировать программы размером не более нескольких строк текста. Методы используют разные формы спецификации программ, а также разные подходы к решению проблем. Синтез программы из нескольких или только одного примера ее предполагаемого поведения должен опираться на некоторую способность к обобщению, обычно выполняемую посредством индукции Синтез программы на основе формулы, определяющей общую форму ее ввода и соответствующего вывода путем использования подходящих правил или особого вида, преобразования [4].

Хотя индукция и дедукция являются общими принципами решения проблем и их использование было уместным, способ их формулирования и использования был слишком общим, чтобы обеспечить эффективное построение. Большая часть конкретных знаний, используемых человеком-программистом при построении программы, была упущена «автоматизацией», пытающейся построить программу автоматически [2]. Это было определено как, основная трудность всех перечисленных выше методов. Решение проблемы было предложено в отказе от требования полностью автоматического синтеза и обращении за советом к программисту двумя способами: в режиме онлайн, во время процесса синтеза, рассматривая его как непрерывное взаимодействие с человеком-программистом, помогающим системе преодолеть самые сложные части синтеза, давая опытные подсказки или советы, и в автономном режиме, путем подготовки баз формально выраженных паттернов программирования. Навыки программирования, а также приемы и основы, описывающие предмет решаемой задачи. Этот подход соответствовал развитию в смежных областях автоматического решения проблем, где переход от решения общих проблем к специалистам по решению конкретных проблем, основанных на знаниях конкретного эксперта, привел к появлению так называемых экспертных систем. Необходимость выражения знаний, используемых в процессе поиска решения, стала очевидной [1].

Стоит отметить, что на самом деле проблема имеет более глубокий характер. Мы можем объяснить это, обратив внимание на аналогичную задачу автоматического доказательства теорем. Многие методы основаны на принципе разрешения. Они выполняют доказательство путем опровержения, способом, который позволяет достаточно эффективно механизировать. С другой стороны, такие процедуры совершенно неестественны для людей при доказательстве теорем. Люди чаще делают естественные дедукции. Но если бы мы попытались имитировать человеческое поведение при доказательстве теорем, то есть механизировать естественные методы дедукции, мы не смогли бы воспользоваться преимуществами определенных свойств метода разрешения, который манипулирует формулами в специальной форме предложения. Хотя приведенный выше аргумент несколько упрощен, но представляет собой основной вопрос для искусственного интеллекта. Достигает ли его цель «разумного» поведения независимо от основного метода, который может полностью отличаться от того, который используется людьми или он больше изучает человеческий интеллект, например, путем построения соответствующих моделей, которые описывали бы так называемое «интеллектуальное» поведение и позволяли экспериментировать с ними на компьютере?

Фактические концепции теоретических методов, лежащие в основе всех этих методов, были обнаружены после абстрагирования от достаточного количества деталей. Основанием для всех из них является поиск. Действительно, поиск - одна из фундаментальных концепций, изучаемых в теории накопления, а также в искусственном. Все методы являются очень специфическими примерами поиска, потому что недостаточно информации для формулирования алгоритмического решения. С другой стороны, на уровне объекта предполагается прямо противоположное, а именно – проблема объектного уровня разрешима геометрически. В противном случае вообще не существовало бы программ.

В области автоматического программирования в целом не наблюдается значительного прорыва. Однако, были достигнуты интересные результаты в различных связанных областях, которые часто примечательны и удивительно близки к цели автоматического программирования, даже если они не предназначены или не связаны в явном виде в качестве помощников по автоматическому программированию. Доступ к компьютеру стал возможным для миллионов непрограммистов желающие решить свои проблемы из-за широкого использования персональных компьютеров и сетей, но им не хватает «грамотности» в программировании. Когда они ограничены конкретным типом задач из конкретной проблемной области, большинство решений могут быть заранее запрограммированы тем или иным способом, так что окончательная программа формируется на человеко-машинном уровне. Типичными примерами являются проблемы, связанные с обработкой больших объемов данных. Инструменты, которые будут названы здесь, - это языки четвертого поколения, электронные таблицы, гипертекстовые и мультимедийные процессоры и, конечно же, различные Системы баз данных, обеспечивающие не только управление базами данных, но и поддержку формирования процедур необходимой обработки данных.

Исследования по автоматическому синтезу программ и предлагают следующий подход к управлению сложностью поиска. Синтез должен быть ограничен одной областью, что позволяет широко использовать предметно-ориентированные знания. Более того, пространство дизайна должно быть разделено на более мелкие задачи с помощью абстракции. Знания должны использоваться для сокращения пространства дизайна и, следовательно, сложности дизайна. Разработан прототип автоматического синтеза программ, который объединяет знания предметной области с различными методами автоматического синтеза программ, называемых ELF, и концентрируется на вопросах представления знаний и рассуждений. Выбранная область - это инструменты САПР, которые прокладывают пути для проводов в схемах WLSI и печатных платах. Обычно такие инструменты представляют собой программы со сложностью от 1000 до 2000 строк кода на языке «C». По сравнению со многими ранее опубликованными работами по автоматическому синтезу программ, данное исследование является примером, демонстрирующим полезность его результатов для решения реальных инженерных задач.

В качестве еще одного плодотворного направления исследований следует упомянуть формирование программ на основе повторного использования существующего программного обеспечения. В самом деле, весьма вероятно, что большая часть ноу-хау в области программирования воплощена в уже существующем и работающем программном обеспечении. Также, как и в других отраслях инженерии, ситуация, когда совершенно новое решение разрабатывается с нуля, на самом деле очень редка, в целом вместо того, чтобы пытаться решать каждую новую проблему заново, необходимо повторно использовать большую часть существующего программного обеспечения. Идея может быть принята на абстрактном уровне, но на более конкретных уровнях возникает много практических трудностей. Повторное использование любой существующей программы требует ее понимания, что, конечно, намного сложнее на рабочем уровне конкретного языка программирования, чем на уровне высокоуровневой спецификации того, что он делает. Формирование программного обеспечения из повторно используемых компонентов изучалось ранее [3]. Формирование новой программы, которая повторно использует существующую программу (или несколько из них), зависит от сходства спецификаций. Но сходство - это не тождество, поэтому формирование включает модификацию, поскольку, подразумевает частичное повторное использование и частичную доработку. Модификация на конкретном языке намного сложнее, чем на абстрактном уровне. И вместо того, чтобы повторно использовать результат разработки программы, может быть более плодотворным повторное использование (воспроизведение) самой разработки для другой, но схожей проблемы. Даже до фактического повторного использования существует задача в использовании подходящего программное обеспечение и установка надлежащего соответствия, что равносильно распознаванию сходства. Проблема разработки программ на основе повторного использования изучалась ранее исследованиях [3]. В заключение критического обсуждения автоматического синтеза программ и связанных подходов возникает вопрос, похоже, не в том, как автоматизировать (полностью) процесс формирования программы, а скорее в том, насколько можно поднять уровень участия человека в этом процессе.