Разработка алгоритмов и моделирование динамической типизации в программах для технических систем

• Автор: Старцев, Евгений Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Челябинск
• Количество страниц: 122 с. : ил.

Оглавление
ВВЕДЕНИЕ

1 Применение промежуточных представлений в статическом анализе программ

1.1 Статический анализ

1.2 Промежуточные представления

1.3 Требования к промежуточному представлению

1.4 Используемые представления в существующих инструментах статического анализа и компиляции

1.4.1 Абстрактное синтаксическое дерево

1.4.2 GIMPLE

1.4.3 LLVMIR

1.4.4 SSA
1.4.5 Представления Bauhaus
1.4.6 Представление Malpas
1.5 Характеристика существующих промежуточных представлений в соответствии с требованиями
1.6 Разрабатываемое представление
1.7 Объектно-ориентированные языки программирования
1.8 Математическая модель классового представления
1.8.1 Связи наследования
1.8.2 Связи агрегации
1.9 Универсальное классовое представление
2 Особенности статического анализа динамических языков
2.1 Динамические языки программирования
2.2 Проблема извлечения классового представления в динамических языках
2.3 Существующие решения
2.3.1 Алгоритм Хиндли-Милнера
2.3.2 Алгоритм Декартова произведения
2.3.3 Заключение по существующим алгоритмам вывода типов
2.3.4 Существующие инструменты вывода типов для Python
2.3.5 Pylint
2.3.6 Pysonar
2.4 Предлагаемая методика вывода типов
2.5 Описание базовой модели типов
2.5.1 Характеристическая сигнатура
2.5.2 Предлагаемая модель типов в динамических языках программирования
2.6 Численная оценка результатов извлечения типов
2.7 Применение нечетких множеств
2.7.1 Ограничения базовой модели
2.7.2 Математическая модель типов в динамических языках программирования на основе нечетких множеств
2.7.3 Функция принадлежности «capacity»
2.7.4 Функция принадлежности «frequency»
2.7.5 Пример применения функций принадлежности алгоритмом вывода типов
2.8 Применение динамического анализа для проверки адекватности математической модели
2.8.1 Результаты для программы logilab
2.8.2 Результаты для программы pylint
2.8.3 Результаты для программы bazaar
2.8.4 Выводы
2.9 Результаты для различных значений порога
3 Разработанный комплекс программ для статического анализа
3.1 Обзор разработанных инструментов анализа
3.2 Обработка XML
3.3 Извлечение представлений UCR и UCFR для Python
3.4 Реализация методики вывода типов при генерации промежуточных
представлений для языка Python
3.5 Связывание представлений
3.6 Инструменты визуального анализа
3.6.1 Визуальное представление диаграммы классов
3.7 Анализ иерархии наследования на предмет корректного выделения
методов в суперклассах
3.8 Технология выполнения срезов представлений
3.8.1 Срез на основе одного представления
3.8.2 Срез на основе нескольких представлений
3.8.3 Реализованные срезы
3.8.4 Срез наследования представления UCR
3.8.5 Срез вызовов представления UCFR
3.8.6 Срез классов представления UCFR
3.8.7 Срез создаваемых объектов представления UCR
Заключение
Список сокращений и условных обозначений
Список литературы
Список иллюстративного материала
Приложения
Исходный код программного модуля для извлечения универсального ' классового представления из исходного кода на языке программирования
Python

Название термина пошло от английского «duck test» («тест на утку»), который в оригинале звучит как: «If it looks like a duck, swims like a duck and quacks like a duck, then it probably is a duck» («Если это выглядит как утка, плавает как утка и крякает как утка, то, вероятно, это утка»)[56].
Применение подхода «утиной» типизации в Python затрудняет статический анализ классов проекта и получение связей агрегации[9], так как типы полей и методов в Python не могут быть получены в явном виде. Однако, это необходимо для поддержания универсального представления в актуальном состоянии для всех языков, независимо от типизации, используемой в них (Java, C++, Python). В Python возможность применения того или иного объекта в качестве типа ограничивается набором полей и методов, к которым происходит обращение при использовании данного объекта в программе. В качестве него может быть использован любой тип, обладающий этими полями и методами. Формально этот набор может быть определен только в момент исполнения Программы.
2.3 Существующие решения
На данный момент для решения изложенной выше проблемы может быть использована методика вывода типов. Изначально данная методика получила распространение в языках программирования, в которых тип переменной может быть опущен, компилятор на основании анализа выражения присваивания для этой переменной сам может логически вывести тип этой переменной. Впервые механизм вывода типов был представлен в языке МЦ68]. Важно отметить, что это строго типизированный язык и типы данных определяются на момент компиляции программы.
В динамических языках программирования важным является то, что типы данных определяются только на момент исполнения программы. Тем не