Нижеследующие задачи могут рассматриваться как темы курсовых и дипломных работ,
а также как стартовая площадка для подготовки кандидатских диссертаций по программированию.
Требования к возможным исполнителям: знание языка программирования C, стремление к расширению знаний об окружающем мире.
Приветствуются знание языка программирования РЕФАЛ и опыт программирования на функциональных языках.
Задачи написаны в порядке возрастания сложности.
Лаборатория автоматизации программирования Института программных систем РАН приглашает на конкурсной основе
студентов и аспирантов для решения ниже поставленных задач.
- Реализация поддержки интерфейса десятичной целочисленной арифметики в системе программирования РЕФАЛ-5.
В актуальной реализации системы программирования РЕФАЛ-5 целые числа представляются в системе счисления
по основанию 2^32 (точнее, в системе счисления по основанию "машинное слово").
Разрядность (длина в системе счисления 2^32) чисел не ограничена.
Здесь имеется ввиду как внутреннее представление целых чисел в структурах интерпретатора РЕФАЛа-5,
так и их синтаксическое представление на уровне самого языка. В задаче требуется сделать понятие системы
счисления по основанию 2^32 только внутренним понятием реализации. С точки зрения самого языка целочисленная
арифметика должна стать десятичной - без ограничения разрядности. Базовые встроенные/библиотечные алгоритмы
интерпретатора РЕФАЛа-5 останутся без изменений, но потребуется изменение представления целых чисел в памяти
РЕФАЛ-машины.
- Реализация динамической загрузки/выгрузки модулей в интерпретаторе системы программирования РЕФАЛ-5.
В актуальной версии интерпретатора РЕФАЛ-5 загрузка всех модулей производится только во время начала
работы интерпретатора. Далее множество модулей (РЕФАЛ подпрограмм) остается фиксированным в поле программ
интерпретатора до полного завершения его работы. Требуется разработать и написать
встроенные/стандартные/библиотечные функции загрузки (добавления в поле программ) и
выгрузки (удаление из поля программ) модулей, функции из которых можно было бы вызывать из РЕФАЛ-программы.
- Русификация РЕФАЛа-5. Реализация поддержки уникода в системе программирования РЕФАЛ-5.
Актуальная версия языка РЕФАЛ-5 ориентирована на латинскую азбуку.
Кроме того, среди базисных данных есть символ (размер которого один байт) и слово,
но нет "расширенного символа", размер которого должен совпадать с размером уникода.
В задаче требуется разработать и реализовать расширение языка РЕФАЛ-5,
поддерживающее понятие уникода в языке образцов и выражений. Требуется также на примере Кириллицы разработать
и реализовать удобный интерфейс языковой настройки на конкретную "локаль".
- Реализация на базе многоядерных процессоров версии системы программирования РЕФАЛ-5, поддерживающей автоматическое распараллеливание некоторых базовых алгоритмов внутри шага РЕФАЛ-машины.
Шаг РЕФАЛ-машины включает некоторые критические по времени исполнения и, в то же время,
не конфликтующие между собой по использованию памяти алгоритмы. Необходимость запуска этих алгоритмов
определяет компилятор из языка РЕФАЛ в промежуточный язык сборки RASL, программы на котором затем
интерпретируются. Требуется разработать и реализовать расширение язык RASL, которое позволило бы распределять
исполнение вышеотмеченных алгоритмов между ядрами одного многоядерного процессора. Требуется также реализовать
в компиляторе РЕФАЛа-5 автоматическое распределение исполнения этих алгоритмов между ядрами.
Задачи для освоения методов специализации программ
(для студентов и аспирантов)
- Перенос реализации частично самоприменимого суперкомпилятора SCP3 под актуальную версию языка РЕФАЛ-5 и эксперименты с самоприменением.
Суперкомпилятор SCP3 реализован в середине 90-х годов в системе программирования РЕФАЛ-5.
Входным языком SCP3 является алгоритмически полное подмножество базисного РЕФАЛ-а, в образцах которого
не допускаются открытые e-переменные и повторные e- и t-переменные, выражения (правые части предложений)
могут быть только двух видов: либо <F expr> либо expr, где expr - пассивное выражение
(не содержащее вызовов функций). С суперкомпилятором SCP3 были произведены несколько успешных простых экспериментов
самоприменения
(см.
A. P. Nemytykh, V. A. Pinchuk, V. F. Turchin. A Self-Applicable Supercompiler. In: Partial Evaluation, LNCS vol. 1110, 1996, pp. 322-337
).
Требуется перенести суперкомпилятор SCP3 под актуальные версии языка программирования РЕФАЛ-5 и его интерпретатора. С перенесенной версией SCP3 повторить эксперименты, описанные в вышеуказанной статье.
- Расширение суперкомпилятора SCP4.
Суперкомпиляция есть метод автоматической специализации программ (например, с целью оптимизации этих программ), основанный на анализе их семантики.
Суперкомпилятор SCP4 реализован на языке программирования РЕФАЛ-5, который также является его входным языком.
(См.
А. П. Немытых. Суперкомпилятор SCP4: общая структура. Монография, М: Издательство URSS, 2007.
).
Возможные направления развития суперкомпилятора SCP4:
[1] Классическая теорема Райса-Успенского утверждает, что любое нетривиальное семантическое свойство программ, написанных на алгоритмически полном языке, алгоритмически неразрешимо. Следовательно, мощность любого преобразователя программ существенно зависит от набора стратегий, управляющих его поведением.
Одной из стратегий любого суперкомпилятора является стратегия аппроксимации распознавания бесконечных циклов
в процессе метаинтерпретации преобразуемых программ.
Требуется расширить набор таких стратегий в суперкомпиляторе SCP4 и провести их сравнительный анализ. Выбор новых стратегий для реализации в SCP4 должен производиться на основе изучения научной литературы и обсуждения на семинарах.
[2] Программа P на функциональном языке программирования есть текстовая кодировка некоторого ориентированного графа с выделенной вершиной (точкой входа). Каждая вершина в этом графе помечена описанием надмножества состояний, в которых может находиться программа P при прохождении ее конкретного вычисления через данную вершину. Условия перехода из одной вершины в смежные вершины (согласно ориентации рёбер) помечают рёбра перехода.
В некотором приближении можно считать, что
суперкомпилятор разворачивает этот граф в бесконечное дерево семантики программы P, анализирует, исправляет это дерево и затем сворачивает (фактаризует) его в другой конечный граф,
который и является результатом преобразований. При разворачивании графа метки вершин и рёбер корректируются.
Язык описания этих меток в дереве семантики может быть шире, чем в исходном графе программы P.
Требуется разработать и реализовать расширение этого языка, дающее возможность описывать простые неравенства между рациональными значениями арифметических выражений.
Задачи для программирования на языке РЕФАЛ
(курсовые задания для студентов)
- Распознавание падежа по А. Н. Колмогорову.
Андрей Немытых,
nemytykh@math.botik.ru
|
Институт программных систем РАН,
г. Переславль-Залесский
http://www.botik.ru/pub/local/scp/refal5/
