Семинар по языкам программирования и компиляторам

[Ulysses]

Напоминаю, что послезавтра состоится интересный доклад, о котором написано выше.

[juliet]

@Admin, захватите завтра, пожалуйста, камеру!

[Ulysses]

Всем привет! Мне сегодня не дали закончить предложение по докладам, которые я мог бы сделать, так что я решил просто запостить часть тут. Второе моё (неозвученное) предложение касалось того, как решают проблему визиторов в функциональном мире. Проблема, которую решает Визитор известна как Expression Problem, её сформулировал Филипп Вадлер в 1998 году. Как видно из Википедии, есть несколько работ, которые её решают разными способами.

1. Ниже я привожу самое простое решение Олега Киселёва, опубликованное в журнале Journal Of Functional Programming (2009).

2. Есть ещё работа Datatypes a la Carte (также JFP, 2008), которую мой студент Владимир Панков использовал в своей бакалаврской в прошлом году.

3. И есть ещё статья Оливейры и коллеги про объектные алгебры (конференция 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)

Замечу, что я мог бы ограничиться сложением и целыми числами, но в сегодняшнем докладе были переменные и хотелось, чтобы и тут они появились. Кодирование Киселёва не позволяет оставлять свободные переменные, так как это мешает типизации всего выражения. Но связанные переменные — в лямбда-функциях — это пожалуйста. Так что пришлось добавить лямбда-абстракцию. Ну и аппликацию, чтобы можно было написать пример с лямбдой, который распечатается на консоль (то есть чтобы в результате у визитора-вычислителя было число).

[Admin]

Видео семинара 2: https://youtu.be/F7PqpZC8E3Y

[Ulysses]

Опубликуйте, пожалуйста, презентацию.

Хорошо было бы составить чек-лист для оценки реализации визитора. А то реализаций много — нужен простой инструмент для сравнения.

[Admin]

Вот доступ к папке семинара

https://drive.google.com/folderview?id=0B2qiCR41-J01dU44a2NfMjFhYWM&usp=sharing

[juliet]

На правах предложения по тематике: можно ещё рассмотреть некоторые знаковые статьи в истории языков программирования.

[Admin]

На правах предложения по тематике: можно ещё рассмотреть некоторые знаковые статьи в истории языков программирования.

Да, это прекрасная идея. А например?

[juliet]

Это одни из наиболее цитируемых и влиятельных статей в области языков программирования, если верить википедии и Бенджамину Пирсу. Статьи по теории типов и лямбда-исчислению в списке ниже я (пока) не привожу.

• The Fortran Automatic Coding System, John Backus et al., 1957.
• The next 700 programming languages, P.J. Landin, 1966.
• Fundamental Concepts in Programming Languages, Christopher Strachey, 1967.
• Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, John Backus, 1977.
• An axiomatic basis for computer programming, Tony Hoare, 1969.

[Admin]

Напоминаю, что 25 марта в 16.00 в 211 состоится II часть семинара, посвященного визиторам.

Как всегда - приглашаются все желающие

[Ulysses]

Если хотим записывать, надо бы взять камеру.

[Ulysses]

Следующий доклад на семинаре состоится в ближайшую пятницу (1 апреля), в 16:00, примерная тема доклада: «Язык с уточнёнными типами (refinement types)», докладчик: В. Квачёв, студент 3-го курса ФИИТ. Приглашаются все желающие.

[juliet]

Видео завершающей части семинара 3. И соответствующий плейлист.

[Admin]

Семинар 3. Визиторы - окончание. https://youtu.be/poT_cvHFH_Q

[Ulysses]

Хорошо было бы выложить презентацию и ссылку на репозиторий на ГитХабе.

[juliet]

Видео семинара #4: язык программирования (c(x)) с refinement types!

[Rasie1]

Презентация

Репозиторий с прототипом интерпретатора

[Ulysses]

В ближайшую пятницу, 15 апреля, в 17-00 в 211 ауд. будет доклад

Функциональный взгляд на визиторы

докладчик: А.М. Пеленицын.