Метавычисления - теория метасистемных переходов в программировании

Теория метасистемных переходов - это теория эволюции. Условия реализации эволюции можно создать в мире программ. Достаточно написать для них метапрограммы, то есть программы, преобразующие другие программы.

Теория метасистемных переходов - это теория эволюции. Условия реализации эволюции можно создать в мире программ. Достаточно написать для них метапрограммы, то есть программы, преобразующие другие программы. Последовательное и (формально) бесконечное применение метапрограмм к программам и к самим себе будет порождать новые программы. При этом могут возникать метасистемные переходы, приводящие к качественно новым возможностям программ.

Созданием метапрограмм (новых метасистем) над программами на основе методов анализа и преобразования программ и занимается теория метавычислений.

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

При таком подходе можно отказаться от программирования методов решения уравнения f(x)=b и написать программу вычисления значений функции f(x) по заданным значениям переменной x. После инвертирования такой программы получим программу решения исходного уравнения, не реализовывая какой-либо алгоритм решения уравнения. Фантастика! Захотели получить корни системы алгебраических уравнений - запрограммируйте саму матрицу, и дело сделано…

Что это за сказки? Программирование позволяет решать математические задачи без математики? Конечно, нет, просто мы упустили одну деталь: где взять средства инвертирования программ? Их действительно можно создать, анализируя граф процессов вычисления при помощи средств метавычислений над исходной программой. Однако для сложных функций f(x) эта задача может решаться неопределенно долго.

Естественная область применения метавычислений - тестирование программ. Тестирование можно рассматривать как «метадеятельность» над программой, в ходе которой изучаются процессы выполнения программы на тестовых данных. Метадеятельность позволяет рассматривать и анализировать текст программы целиком. Это отличает метавычислительный подход к тестированию от широко распространенного подхода, использующего структурные критерии выбора тестов, основанные на анализе управляющей структуры программы.

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

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

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

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

Суперкомпиляция, инверсные вычисления, окрестностный анализ являются составными частями теории метавычислений. Они используют алгоритмы построения и анализа графа процессов выполнения программы и реализуют метасистемные переходы в жизни и развитии программ.

Теория метавычислений - одно из самых увлекательных и перспективных направлений современных компьютерных наук. Но работа в этой области связана с необходимостью почти забытого в массовом программировании сочетания высокой математической культуры с владением современными методами кодирования. Поэтому не случайно, что именно на механико-математическом факультете МГУ им. М. В. Ломоносова в прошлом году появилась новая специальность «Теоретические вопросы информатики», изучение которой включает подробные курсы по метавычислениям и их применению. Эту специальность можно получить дополнительно к высшему образованию, и мехмат МГУ, пожалуй, единственное в мире место, где есть возможность изучить соответствующие алгоритмы, приобщиться к самым сложным и интересным проблемам теоретической информатики, объединенным общим названием «метавычисления».

[i40227]