В пятницу, 18 марта, в 16.00 состоится второе заседание семинара “Языки программирования и компиляторы”. Аудитория 211.
Тема: “Блеск и нищета визиторов”
(обзор статьи A Survey Report of Enhancements to the Visitor Software Design
Pattern Tanumoy Pati and James H. Hill).
Докладчик: Михалкович С.С.
Доклад ориентирован прежде всего на студентов 2-4 курса и преподавателей, ведущих соответствующие дисциплины.
Приглашаются все желающие.
Всем привет! Мне сегодня не дали закончить предложение по докладам, которые я мог бы сделать, так что я решил просто запостить часть тут. Второе моё (неозвученное) предложение касалось того, как решают проблему визиторов в функциональном мире. Проблема, которую решает Визитор известна как Expression Problem, её сформулировал Филипп Вадлер в 1998 году. Как видно из Википедии, есть несколько работ, которые её решают разными способами.
Ниже я привожу самое простое решение Олега Киселёва, опубликованное в журнале Journal Of Functional Programming (2009).
Есть ещё работа Datatypes a la Carte (также JFP, 2008), которую мой студент Владимир Панков использовал в своей бакалаврской в прошлом году.
И есть ещё статья Оливейры и коллеги про объектные алгебры (конференция ECOOP, 2012). Там явно сказано, что они решают проблему Визитора.
Вот простое решение (Ideone) Киселёва. Интересно было бы услышать критику. Можно на следующем докладе.
-- Определяем типы (алгебру) узлов дерева (int, add, …)
class Algebra rep where
int :: Int -> rep Int
add :: rep Int -> rep Int -> rep Int
lam :: (rep a -> rep b) -> rep (a -> b)
app :: rep (a -> b) -> rep a -> rep b
-- «Визитор»-вычислитель дерева выражения: объявление
newtype Eval a = E {unE :: a}
-- «Визитор»-вычислитель дерева выражения: определение
instance Algebra Eval where
int = E
add x y = E (unE x + unE y)
lam f = E (unE . f . E)
app f x = E ( (unE f) (unE x) )
-- «Визитор»-измеритель глубины дерева выражения: объявление
newtype Depth a = D {unD :: Int}
-- «Визитор»-измеритель глубины дерева выражения: определение
instance Algebra Depth where
int _ = D 1
add x y = D (1 + max (unD x) (unD y))
lam f = D (1 + unD (f (D 0)))
app f x = D (1 + max (unD f) (unD x))
-- Пример дерева: (\x -> x + 2) 1
test2 :: Algebra rep => rep Int
test2 = app (lam (\x -> add x (int 2))) (int 1)
-- Основная программа: печатает результат вычисления test2 и его высоту
main = print $ (unE test2, unD test2) -- (3, 4)
Замечу, что я мог бы ограничиться сложением и целыми числами, но в сегодняшнем докладе были переменные и хотелось, чтобы и тут они появились. Кодирование Киселёва не позволяет оставлять свободные переменные, так как это мешает типизации всего выражения. Но связанные переменные — в лямбда-функциях — это пожалуйста. Так что пришлось добавить лямбда-абстракцию. Ну и аппликацию, чтобы можно было написать пример с лямбдой, который распечатается на консоль (то есть чтобы в результате у визитора-вычислителя было число).
Опубликуйте, пожалуйста, презентацию.
Хорошо было бы составить чек-лист для оценки реализации визитора. А то реализаций много — нужен простой инструмент для сравнения.
Вот доступ к папке семинара
https://drive.google.com/folderview?id=0B2qiCR41-J01dU44a2NfMjFhYWM&usp=sharing
На правах предложения по тематике: можно ещё рассмотреть некоторые знаковые статьи в истории языков программирования.
Да, это прекрасная идея. А например?
Это одни из наиболее цитируемых и влиятельных статей в области языков программирования, если верить википедии и Бенджамину Пирсу. Статьи по теории типов и лямбда-исчислению в списке ниже я (пока) не привожу.
Напоминаю, что 25 марта в 16.00 в 211 состоится II часть семинара, посвященного визиторам.
Как всегда - приглашаются все желающие
Если хотим записывать, надо бы взять камеру.
Следующий доклад на семинаре состоится в ближайшую пятницу (1 апреля), в 16:00, примерная тема доклада: «Язык с уточнёнными типами (refinement types)», докладчик: В. Квачёв, студент 3-го курса ФИИТ. Приглашаются все желающие.
Хорошо было бы выложить презентацию и ссылку на репозиторий на ГитХабе.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021