Анализ программ 4MIT весна 2018 — различия между версиями

Версия 18:35, 13 марта 2018

Преподаватели:

Ахин Марат (akhin@kspt.icc.spbstu.ru )

Беляев Михаил (belyaev@kspt.icc.spbstu.ru )

Содержание

1 Лекции
2 Практика

Лекции

Лекция 1

Введение в предмет курса. Слайды

Лекция 2

Анализ на основе систем типов. Слайды

Лекция 3

Теория решеток и монотонный фреймворк. Слайды

Лекция 4

Примеры потокочувствительных анализов. Слайды

Лекция 5

Интервальный анализ. Widening и narrowing. Слайды

Практика

НЕ ВЫКЛАДЫВАЙТЕ РЕШЕНИЯ В ОТКРЫТЫЙ ДОСТУП - это просьба от коллег из университета Орхуса (ˈɒːhuːˀs), откуда взяли существенную часть этого курса. В частности, не выкладывайте решения в открытые репозитории на GitHub. Используйте сервисы закрытых репозиториев (например, Gitlab или Bitbucket).

Задание к лекции 2

Дописать реализацию класса TypeAnalysis в TIP. Подумайте, как будет работать анализ, если в программе есть рекурсивный тип.
Попробуйте добавить в описанную в лекции систему типов тип Bool, не меняя синтаксис языка. Перепишите правила так, чтобы они продолжали работать на основе имеющегося алгоритма унификации.
(опционально) Реализуйте пункт 2 в рамках пункта 1.
Попробуйте добавить в описанную в лекции систему типов тип массива (при этом меняется синтаксис, см. слайды). Перепишите правила и попробуйте протипизировать программу из лекции.

Задание к лекции 3

Подумайте, выразим ли анализ типов в монотонном фреймворке? А наоборот?
Допишите метод transfer в трейте IntraprocSignAnalysisFunctions здесь.
Реализуйте класс PowersetLattice в файле GenericLattices.

Задание к лекции 4

Рассмотрим плоскую решётку над типами {Bool,Int} из задания 1. Если реализовать для неё анализ, каким по предложенной классификации он будет? Попробуйте выписать правила вывода.
Дореализуйте live variables analysis здесь.
Реализуйте reaching definitions analysis в файле ReachingDefsAnalysis.scala рядом.

Задание к лекции 5

Допустим, мы хотим реализовать оптимизирующий компилятор для языка TIP. Среди прочего, для работы ему требуется информация о размерах различных переменных: bool (1 bit), byte (8 bit signed), char (16 bit unsigned), int (32 bit signed), bigint (any integer), any (any other thing).
- Предложите решетку для реализации анализа размера переменных
  - Нужно описать не только решетку для одного абстрактного значения, но и все другие решетки, требуемые для анализа целой программы
- Опишите правила вычисления различных выражений
- Придумайте нетривиальный пример программы на TIP для получившегося анализа и посмотрите, что для него получается
Допишите реализацию метода widen в IntervalAnalysisWorklistSolverWithWidening здесь.
Реализуйте придуманный вами анализ размера переменных в файле VariableSizeAnalysis.scala рядом.

@@ Строка 51: / Строка 51: @@
 # Дореализуйте live variables analysis [https://github.com/vorpal-research/TIP/blob/master/src/tip/analysis/LiveVarsAnalysis.scala здесь].
 # Реализуйте reaching definitions analysis в файле ReachingDefsAnalysis.scala рядом.
+=== Задание к лекции 5 ===
+# Допустим, мы хотим реализовать оптимизирующий компилятор для языка TIP. Среди прочего, для работы ему требуется информация о размерах различных переменных: bool (1 bit), byte (8 bit signed), char (16 bit unsigned), int (32 bit signed), bigint (any integer), any (any other thing).
+#* Предложите решетку для реализации анализа размера переменных
+#** Нужно описать не только решетку для одного абстрактного значения, но и все другие решетки, требуемые для анализа целой программы
+#* Опишите правила вычисления различных выражений
+#* Придумайте нетривиальный пример программы на TIP для получившегося анализа и посмотрите, что для него получается
+# Допишите реализацию метода widen в IntervalAnalysisWorklistSolverWithWidening [https://github.com/vorpal-research/TIP/blob/master/src/tip/analysis/IntervalAnalysis.scala здесь].
+# Реализуйте придуманный вами анализ размера переменных в файле VariableSizeAnalysis.scala рядом.