Николай Иваныч ([info]nivanych) wrote,
@ 2009-01-13 17:49:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
По поводу MskHUG.
Возникли у меня по поводу предстоящего
сборища "MskHUG" некоторые сложности.
Сложности не с тем, чтобы приехать.
А с тем, что есть куча глупых дел и думать
про действительно важные важные и нужные,
и что немаловажно, интересные вещи, сложновато.
Я пока не умею "5 минут подумать про категории",
надо как-то посидеть, "раскрутить мозги"...


Насчёт того, что именно рассказывать...
Я считаю, что нельзя сразу рассказывать
про монады и T-алгебры, хотя эти темы
замечательно ложатся на Haskell-программирование.
Нужно рассказывать с самого начала.
В основах есть много мелких непонятностей,
которые заметно тормозят дальнейшее понимание.
Я сужу не только по себе и своему опыту изучения,
такой вывод я сделал после некоторого общения с людьми...

Предположительно, описание не будет привязано
к конкретному языку, но возможно, мелким шрифтом,
будет сделан Haskell-код (или Agda-код?) с комментариями.

Сначала будет дано определение категории, примеры, про то,
как это можно сделать ещё и краткое сравнение с этими же
определениями, но на основе классической логики предикатов.
Обязательно постараюсь побольше примеров, где категорное описание
действительно оправдано и ведёт к упрощению.
Потом некоторые свойства стрелок, (моно-эпи-изо)морфизмы и типа того.
Сразу ввожу понятия функторов, как стрелок между категориями,
раскрываю тему про то, что функтор -- это сложная стрелка,
это уточнение внутренней структуры стрелки (и объекта).
Потом построения в категории, начинаю с (ко)произведений,
тут же можно будет объяснить категорную модель
simply-typed lambda calculus, потом будут
всякие (ко)уравнители и pullback'и, тут надо постараться
и объяснить алгоритм их построения. Это не очень просто.
После этого (ко)пределы и классификатор подобъектов.
Потом рассказать про топосы, как про модель
higher-order-теорий типов, что-ли...
Либо продолжить тему функторов -- категорию функторов,
сопряжённые функторы, связь с пределами...

В одно выступление это не уместить.
Сколько уместится, я не знаю, эта тема для меня самого новая,
и я ни разу не производил целостного и последовательного объяснения.

Несколько сомневаюсь, но хочу рассказывать
про теорию категорий без объектов.
То есть, с присутствием только стрелок
и особых стрелок -- единичных, они
вполне заменяют понятие "объекта".
От этого теория становится чуть проще,
становится меньше сущностей.
Но, повторюсь, я пока не уверен.

Я убеждён, что объяснение всех этих вещей даже и не главное.
Главное -- это показать, что это несложно, что это всё понятные вещи,
чтобы люди смогли дальше самостоятельно читать литературу.
У меня, например, было много мелких непоняток, и разъяснение их
на самом начальном уровне сэкономило бы кучу усилий (и времени).

Кроме того, если понять эти вещи на основе конструктивной логики,
то классическое будет пониматься совсем просто, конечно, если
оно вообще будет востребовано для нужд computer science.

Самое противное, что я не уверен, что успею подготовить ;-(
А без этого ехать как-то ... стрёмно, что-ли...



(40 comments) - (Post a new comment)


[info]lomeo
2009-01-13 02:02 pm UTC (link)
Может стоит у [info]migmit поспрашивать про объём и содержание? Он на spbhug рассказывал про категории, насколько я знаю.

(Reply to this) (Thread)


[info]nivanych
2009-01-13 02:09 pm UTC (link)
Да, кстати.
Он и в теме разбирается значительно лучше.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-13 08:41 pm UTC (link)
У меня была, фактически, реклама. Галопом по европам, опуская не только доказательства, не только формулировки, но даже части определений. Уместил в академический час. На сайте SPbHUG лежат слайды.

Рассказал (привожу по памяти, лень лезть в файл): понятия категории, функтора (не как морфизма категорий), сопряжённых функторов и как они связаны с монадами, категории Клейсли и Эйленберга-Маклейна (? У меня с фамилиями плохо) на примере одной конкретной монады (списка), декартово замкнутые категории и реализацию лямбда-исчисления в оных. Глюкнул, обозвав категорию векторных пространств декартово замкнутой (перед выкладыванием на сайт исправил).

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-13 08:43 pm UTC (link)
Про топосы я так и не понял, куда их прилагать в программинге. Теоркатегор без объектов, ИМХО (очень Х) сложнее, чем с объектами.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-14 07:38 am UTC (link)
А куда девать декартово-замкнутые категории в программинге?

Топосами выражаются higher-order-логики (теории типов).
Ими выражаются и многие системы с зависимыми типами,
пока что ещё не прочитал, какие, но книжки есть, прочитаю.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-14 11:53 am UTC (link)
Ну, коль скоро у нас есть first-class functions, у нас есть экспоненты. А вот про топосы я пока не понял.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-15 07:06 am UTC (link)
То есть, про категорию с конечными
(ко)пределами понятно, так?
В непонятках остаётся только классификатор?

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-15 11:49 am UTC (link)
> То есть, про категорию с конечными (ко)пределами понятно, так?

Тоже не вполне, кстати. Конечные суммы/произведения - понятно, это record и union. Экспоненты - first-class functions. А вот (ко)уравнители - уже очень и очень интересно.

Скажем, уравнители - если они есть - позволяют выразить произвольные pre- и postconditions. Коуравнители, ИМХО, должны давать возможность делать функциональные интерфейсы к императивным вещам.

Или вы что-то другое имеете в виду?

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-15 02:38 pm UTC (link)
> Коуравнители, ИМХО, должны давать возможность
> делать функциональные интерфейсы к императивным вещам.

Что-то сходу не могу додуматься, каким образом...
Интересно!

> Или вы что-то другое имеете в виду?

Обобщение разбиения на классы эквивалентности...

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-15 08:07 pm UTC (link)
> Что-то сходу не могу додуматься, каким образом...

Пусть f,g:X->Y, q:Y->Z, q = coeq(f, g). Пусть есть функция t:Y->YxW, для которой а) q . p1 . t = q, и б) p2 . t . f = p2 . t . g (здесь p1, p2 - проекции на первый и второй сомножитель, точка обозначает композицию). Соорудим тогда такую весч: некая "процедура" (чтобы отличать от функции) t', которая принимает на вход элемент типа Z. Этот элемент наверняка представлен в памяти как некий элемент типа Y (ну, а как ещё, если коуравнитель). Применяем к этому элементу типа Y функцию t. На выходе получаем другой элемент типа Y, который, однако, представляет тот же элемент типа Z, и некий элемент W; последний не зависит от выбора представляющего элемента. Теперь заменим элемент типа Y на месте (!), если у нас нет других ссылок на него, и вернём элемент типа W.

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

Как приложение - допустим, Y - это какая-то функция и хэш-таблица при ней; наша t сначала смотрит в хэш-таблицу, если не находит значение там - вычисляет значение функции и возвращает это значение, а также обновлённую хэш-таблицу. В результате получим функцию с мемоизацией.

> Обобщение разбиения на классы эквивалентности...

Ы?

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-20 07:13 am UTC (link)
> В результате получим функцию с мемоизацией.

Кроме того, это даёт идеи по описанию
линейных логик в конечно-(ко)непрерывных категориях
напрямую, не используя похожее на язык Митчелла-Бенабу.
Правда, классификатор оттуда убирать противоестественно ;-)
Но это в моём понимании. Имхо, так сказать.

>> Обобщение разбиения на классы эквивалентности...
> Ы?

Немного неточно выразился.

Возьмём категорию множеств.
Пусть есть некое отношение эквивалентности на множестве X
(мономорфизм r : R -> X x X) и две проекции -- p1, p2.
Коуравнитель p1.r и p2.r -- это наименьшее множество
классов по разбиению отношением эквивалентности R.

Чо-то путаюсь в математическая термина на русская языка.
Печально, что при этом не знаю в достаточной степени английские термины.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-20 11:14 am UTC (link)
> Кроме того, это даёт идеи по описанию линейных логик в конечно-(ко)непрерывных категориях напрямую, не используя похожее на язык Митчелла-Бенабу.

Интересно. Где почитать?

> Правда, классификатор оттуда убирать противоестественно

Дык в том-то и дело, что в программинге, ИМХО, и уравнители с коуравнителями противоестественны. Потому как: вводим уравнители -> компилятор вынужден проверять равенство двух морфизмов -> получаем решение проблемы останова. Или: вводим уравнители -> программист вынужден писать дополнительный код, чтобы убедить компилятор в равенстве двух морфизмов, причём этот код выполняется при компиляции -> получаем зависимые типы -> вывод типов накрывается медным тазиком.

С классификатором ситуация просто становится ещё немножко хуже.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-21 11:54 am UTC (link)
> Интересно. Где почитать?

Почти в любых книжках по теории топосов.
Английское название -- Mitchell-Benabou.

Насколько я читал, раньше это считалось
универсальным решением -- объяснить
язык Митчелла-Бенабу и пользоваться им
для объяснения всего дальнейшего,
связанного с топосами.

P.T. Johnstone
"Topos Theory"

J. Lambek, P.J. Scott
"Introduction to Higher-Order Categorical Logic"

Saunders Mac Lane,
leke Moerdijk
"Sheaves in Geometry and Logic,
a first introduction to topos theory"

Stewen M. Awodey
"Logic in Topoi:
Functorial Semantics For Higher-Order Logic"

Я имею ввиду язык М.Б., а не линейную логику.
Про линейную логику, которая описывается чисто категорно,
я почти ничего не знаю, сказал лишь только,
что то объяснение натолкнуло меня на идею.

Вот ещё кое-что --
R.A.G. Seely
"Polymorphic Linear Logic and Topos Models"

> получаем решение проблемы останова

Я предполагаю, что она решена ;-)
То есть, не надо использовать общую рекурсию,
надо пользовать не-Тьюринг-полные системы.
Доказано, что полно таких, которыми можно
выразить алгоритмы с любой, практически применимой сложностью.
Ну кого, например, интересуют алгоритмы
со сложностью, например, O(2^(2^(2^N)))?
Зачем, в конце концов, мы тогда говорим
про всякие катаморфизмы и вообще схемы рекурсии? ;-)

В случае решённой проблемы останова (ко)уравнители всегда можно вычислить.
Но есть некоторая проблема в алгоритмически эффективном вычислении.

> вывод типов накрывается медным тазиком

Мне кажется, это незначительно для практики.
Да, вывод типов в системах с зависимыми типами,
как правило, невозможен, но мне кажется, что
для практики вполне хватает частичного вывода,
например, как в Agda/Coq (по крайней мере, в Coq).
Там, где типы не очень сложные, всё замечательно выводится.
А там, где сложные, тоже часто выводится, но становится
лучше многое указать явно, для документации кода.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-21 12:11 pm UTC (link)
Спасибо, что такое язык Митчелла-Бенабу я, в общем, знаю. Джонстон прочитан от корки до корки и является одной из любимых книг, я его даже порывался украсть из университетской библиотеки.

То есть, что вы предлагаете НЕ использовать - я понимаю хорошо. Я пытаюсь понять, что вы предлагаете ИСПОЛЬЗОВАТЬ.

> То есть, не надо использовать общую рекурсию, надо пользовать не-Тьюринг-полные системы.

Аха! Это уже много интереснее. В этом случае у нас, пожалуй, и классифигатор получится. Теперь понятно.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-21 03:14 pm UTC (link)
> что такое язык Митчелла-Бенабу я, в общем, знаю
> Джонстон прочитан от корки до корки

Мда. Было глупо с моей стороны, ну да ладно ;-)

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

Вполне может быть, что посмотреть на категорную семантику
языков с зависимыми типами будет очень даже полезно.
Когда я узнал про то, что в топосах геометрию можно
интерпретировать, как вычисления, афигел невероятно ;-)
Возможно, где-то тут находится польза топосов для народного хозяйства.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-21 05:43 pm UTC (link)
> из него можно сделать компутерный язык...

То есть, по аналогии с цепочкой "декартово замкнутые категории - лямбда-исчисление - программирование" сделать цепочку "топос - язык Митчелла-Бенабу - программирование". Может сработать, но, полагаю, только в тотальном программировании - как я понял, вы это и хотите.

В конце концов, на практике всегда есть ограничение по времени - получить результат через год неинтересно.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-21 06:07 pm UTC (link)
> Может сработать, но, полагаю,
> только в тотальном программировании

Именно.
Собственно, вполне можно обойтись и
категорной семантикой уже существующего.
Например, Agda/Coq.

> получить результат через год неинтересно

Смотря какой результат...
Но вообще, есть все основания полагать,
что эти вещи получатся похожими на существующие
языки с мощными системами типов, но с главным
отличем -- простой и ясной категорной семантикой.

(Reply to this) (Parent)


[info]migmit.vox.com
2009-01-20 11:18 am UTC (link)
> Немного неточно выразился

Это я не так понял. Связал "обобщение... на..." с "обобщением на случай".

То, что коуравнитель отношения эквивалентности = разбиение на классы эквивалентности - это теперь, кажется, в старшей группе детсада проходят.

А я спрашивал про немного другое, только не объяснил, как надо.

Когда речь заходит о категориях в применении к компьютерам, моя первая ассоциация - "типы - объекты, вычислимые функции - морфизмы". Вот я и интересовался, вы про эту же ситуацию говорите, или про что-то другое. Потому что в этой ситуации с (ко)уравнителями, равно как и с классификатором, получается жуткая фигня.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-21 10:21 am UTC (link)
> типы - объекты, вычислимые функции - морфизмы

В общем, да.
Но это упрощённый взгляд, годящийся только для
моделирования немного бОльшего, чем просто-типа-лямбды.
С higher-order логикой уже немного сложнее.
С зависимыми типами ещё немного сложнее.

> Потому что в этой ситуации с (ко)уравнителями,
> равно как и с классификатором, получается жуткая фигня.

Как минимум, можно типизировать эти вещи.
И в случае, если их возможно вычислить,
а в конструкциях это будет часто, то неудобство
будет в необходимости предоставления доказательства.

(Reply to this) (Parent)


[info]nivanych
2009-01-21 11:59 am UTC (link)
> это теперь, кажется, в старшей группе детсада проходят.

Эх, не было у нас таких садиков...

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

Но если строить систему постепенно, аккуратно,
то всё не так плохо, правда, Тьюринг-полноту
при этом никак не получить, ну так это же хорошо!

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-21 12:13 pm UTC (link)
> с вычислениями многих категорных конструкций ниччего нельзя поделать.

Ну дык. В Хаскеле даже произведение не является категорным произведением...

(Reply to this) (Parent)


[info]nivanych
2009-01-21 09:47 am UTC (link)
> конечно-(ко)непрерывных категориях

Описался.
Конечно-(ко)полных, разумеется.

(Reply to this) (Parent)


[info]nivanych
2009-01-15 06:56 am UTC (link)
> Теоркатегор без объектов,
> ИМХО (очень Х) сложнее,
> чем с объектами.

Исходная мотивация была в том,
чтобы сконцентрировать внимание людей
на стрелках, на равенстве стрелок
и равенстве их различных композиций,
отставив объекты на 3-й план.

Да, без объектов получается не то, чтобы сложно,
во многом даже проще, но в любом случае,
для бОльшей нагядности некое понятие о том,
"откуда" и "куда" направлена стрелка, нужно.
Вроде бы, получается разумный компромисс.

Кстати, как называется структура с частично
определённой ассоциативной бинарной операцией?
Предполугруппа? Или так и называется -- категория? ;-)
Хотя нет, для категории правые-левые единицы нужны.
Но в неконструктивной теории их легко ввести :-)

(Reply to this) (Parent)


[info]nivanych
2009-01-14 07:33 am UTC (link)
Обязательно посмотрю.

> сопряжённых функторов

Любопытно.
Я вот не нашёл способа быстро и просто объяснить.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-14 11:56 am UTC (link)
Помахать руками и сказать, что Hom(FA, B) и Hom(A, GB) - по сути, одно и то же. Ключевое слово "по сути" оставляется без объяснений. Эквивалентное (и более правильное) определение через единицу и коединицу не приводилось.

Ну, и пара примеров.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-15 06:47 am UTC (link)
> Помахать руками и сказать, что
> Hom(FA, B) и Hom(A, GB) - по сути, одно и то же.

Боюсь, тут такого не выйдет.
Нужно приводить конструкции
и случаи, когда это возможно.

(Reply to this) (Parent)(Thread)


[info]migmit.vox.com
2009-01-15 06:52 am UTC (link)
Вам виднее. Только не забывайте, лучшая презентация в мире - это знаменитое "chicken-chicken".

(Reply to this) (Parent)


[info]kurilka
2009-01-13 06:01 pm UTC (link)
Чот такое ощущение, что материала у тебя на семестровый курс :)
Есть мысль - может имеет смысл попробовать все эти вещи в вики описать, на том же сайте mskhug к примеру?
У меня вот такое ощущение, что материал по теоркату очень размазан и перенасыщен лишними закосами в математику (примеры, скажем, даются такие, которые понятны математикам, но не "обычным" программерам), ну а на русском инфы по-моему совсем мало.

(Reply to this) (Thread)


[info]nivanych
2009-01-13 06:21 pm UTC (link)
> материала у тебя на семестровый курс

Ты преувеличиваешь.
Посмотри на то, что делает [info]ivan_ghandhi
Он делает на Java, объяснил довольно много и компактно.
Я же собираюсь не сильно привязываться к языку
и сделать побольше примеров и разъяснений/расжёвываний.

Тем более, как я уже написал, главная цель,
дать некое начальное понимание, чтобы потом
люди спрашивали более точно и могли сами
читать и изучать материал.

Предполагается что-то типа книжки по этой, как её...
Чего-то там GNU Free Documentation License...
Или тип того. Уточнить успеется.

(Reply to this) (Parent)(Thread)


[info]kurilka
2009-01-13 06:58 pm UTC (link)
Ну будем ждать драфтов книжки :)

(Reply to this) (Parent)


[info]thesz
2009-01-13 08:46 pm UTC (link)
Главное - ввязаться. ;)

И ещё - здесь все свои. ;)

(Reply to this) (Thread)


[info]nivanych
2009-01-14 07:00 am UTC (link)
Это реально радует.

(Reply to this) (Parent)


[info]zelych
2009-01-14 07:54 pm UTC (link)
Интересно получается.
Единственное, я думаю, может стоит рассчитывать на то, что базовые понятия люди уже будут знать. В общих чертах самостоятельно осознать, что такое категории, стрелки и функторы, каждому под силу (например тут очень доступно написано http://en.wikibooks.org/wiki/Haskell/Category_theory). А переночевав с этими понятиями в голове, и более сложный материал будут воспринимать проще.

Помню свои первые ощущения: ну функторы, ну пределы, произведения, а в чём смысл-то? Зачем оно надо?
Я думаю, что более сложные (и интересные) вещи быстрее сподвигнут людей разбираться и читать книжки.
Например, как лямбда-исчисление выражается и логика.

(Reply to this) (Thread)


[info]nivanych
2009-01-15 07:24 am UTC (link)
> Единственное, я думаю, может стоит рассчитывать на то,
> что базовые понятия люди уже будут знать.

Лучше построить материал так,
чтобы добраться до интересных примеров
как можно быстрее, например,
до декартово-замкнутых категорий
можно быстро добраться.
А пример это уже очень хороший.
Ими несложно объяснить даже
многие виды полиморфизмов
и категорную модель существенной
части ML и даже Haskell.

Наверное, это хорошая идея,
взять за основу CCC и изучить
модели на их основе.
Например, так делают тов.
J. Lambek & P.J. Scott,
уже потом приходя к объяснению
нужности и полезности классификатора.
Единственное, что мне у них
не очень нравится, это они
везде и всюду в топосы пихают
объект натуральных чисел ;-)

Я хотел уделить больше внимания
темам логик и теорий типов...

(Reply to this) (Parent)


[info]thesz
2009-01-20 08:50 pm UTC (link)
8(916)605-97-88

Сергей Зефиров ;)

(Reply to this) (Thread)


[info]nivanych
2009-01-21 05:57 pm UTC (link)
Приехать не получается.
Обидно и досадно почти буквально до слёз ;-(

Но есть и хорошее.
Я начал писать более-менее серёзно.
План статьи (хотя, по объёму получается, как книжка)
уже более-менее продуман, пишу первую главу.
В ней я рассказываю про логические системы,
кратенько про грамматики, машину Тьюринга,
term rewriting, лямбду и простые типы.
Расскажу и про классическую логику предикатов.
Про классические теории множеств, может, тоже.
Но всё это кратко, только чтобы обозначить,
что именно будет моделироваться категорно
и с чем будет сравниваться.
Будет, что покритиковать ;-)

Насчёт приезда -- ну так, как я понял, встречи
не планируются более долгие, чем на один день-вечер.
С транспортом до Екатеринбурга проблем вообще никаких --
поезда ходят, как трамваи, в смысле, регулярно.
Только добраться до Казанского-Ярославского,
и всё, через пару часов уже еду.

(Reply to this) (Parent)(Thread)


[info]zelych
2009-01-22 01:07 pm UTC (link)
Уже точно не получится, или можно как-нибудь поспособствовать?
Если добираться не на поезде, то можно за сутки туда-обратно вернуться.

(Reply to this) (Parent)(Thread)


[info]nivanych
2009-01-23 09:07 am UTC (link)
Уже точно не получится.
Хотя и на самолёте можно было бы
завтра днём вылететь и даже успеть
выспаться перед самолётом.
Проблема не в том, как добраться.

(Reply to this) (Parent)(Thread)


[info]zelych
2009-01-23 09:43 am UTC (link)
Жаль конечно.
Как-то спонтанно всё получилось.
В следующий раз будем заранее готовиться.

(Reply to this) (Parent)(Thread)


[info]kurilka
2009-01-23 01:24 pm UTC (link)
Ну тогда прям щаз надо и начинать :)
Может тогда и я приеду :)

(Reply to this) (Parent)


(40 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…