IntroductionToProgrammingLanguages

Лекции

• [Лекция №1] 10.02.2012

Домашние задания

• [Задание №1 к 17 февраля 2011]

написать генерирующее расширения для программы возведения в степень

   int exp (int x, int n) {
      int y = 1;
      while (n) {
          if (n % 2) y *= x;
          n /= 2;
          x *= x;
      }
      return y;
   }

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

Программа курса

Вопросы после 19-го - опционально.

• 1. Языки программирования, синтаксис, семантика, прагматика. Когнитивные собенности человеческого мышления и их влияние на развитие языков программирования.

• 2. Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.

• 3. Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.

• 4. Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.

• 5. Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.

• 7. Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.

• 6. Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)

• 7. Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).

• 8. Двухуровневые и атрибутные грамматики, вопросы применения на практике.

• 9. Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.

• 10. Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.

• 11. Строгость, чистота, прозрачность по ссылкам.

• 12. Языки с типами и языки без типов. Статическая и динамическая типизация.

• 13. Номинальная и структурная эквивалентность типов. Простейшие конструкторы.

• 14. Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.

• 15. Subtyping. Структурный и номинальный subtyping.

• 16. Динамическая семантика языков. Операционная семантика большого и малого шага.

• 17. Денотационный подход к описанию семантики.

• 18. Аксиоматическая семантика. Верификация программ. Design by contract.

• 19. Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.

• 20. Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.

• 21. Задача генерации кода. Генерация кода путем интерпретации.

• 22. Восходящее переписывание деревьев и динамическое программирование (BURS).

• 23. Алгоритмы распределения регистров. Распределение регистров и раскраска графов.

• 24. Параллелизм на уровне инструкций. Планирование инструкций.

• 25. Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода,

оптимальная линеаризация.

• 26. Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка

циклов.

Список групп для выполнения задач

1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.

2.

3.

4.

5.

6.