Пользователь
Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,
f :: a -> bто образ f в D, F f, связывает образ a с образом b:
F f :: F a -> F b(Надеемся, что такая смесь математических обозначений и синтаксиса Haskell понятна читателю. Мы не будем писать скобки, применяя функторы к объектам или морфизмам.)
Недавно мне понадобилось написать 2-3-дерево и я начал искать информацию в русскоязычном интернете. К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке. На всех ресурсах было одно и то же: свойства дерева, как вставляются ключи в дерево, поиск в дереве и иногда простой пример, как удаляется ключ из дерева; не было реализации. 
Это перевод доклада с голландского TED Talks, прочитанного Гвидо Ван Россумом, "великодушным пожизненным диктатором" языка программирования Python. Много автобиографии и немного про значение языков программирования и основную идею Python.
Позвольте представиться — я нерд, гик. И я постоянно медлю. Я закончил университет в 26, мне было 45, когда я женился, сейчас мне 60, и у меня четырнадцатилетний сын. Может, мне просто трудно даются решения: я прожил в США больше 20 лет, но всё ещё имею вид на жительство.
Я не Стив Джобс или Марк Цукерберг. Но в возрасте 35 лет я создал язык программирования, который нашёл своих последователей. То, что произошло после этого, невероятно. Но об этом позже.
| OCODE | «расшифровка» («procode») | |
|---|---|---|
94 5 L1 83 73 69 86 69 95 4 42 0 42 0 40 2 14 83 42 0 42 1 40 2 14 83 42 2 40 3 42 1 15 92 85 L5 90 L6 42 1 40 4 40 2 14 83 40 4 42 1 14 80 4 90 5 40 4 40 5 88 L6 91 4 42 2 40 3 42 1 15 92 85 L7 90 L8 40 4 40 2 14 8 87 L9 40 4 42 2 11 92 85 L11 90 L10 42 0 40 6 40 2 14 83 40 4 40 6 14 80 6 90 L11 40 6 40 3 22 86 L10 91 6 90 L9 40 4 42 1 14 80 4 90 L7 40 4 40 5 88 L8 91 4 97 103 0 |
ENTRY 5 L1 'S' 'I' 'E' 'V' 'E' SAVE 4 LN 0 LN 0 LP 2 PLUS STIND LN 0 LN 1 LP 2 PLUS STIND LN 2 LP 3 LN 1 MINUS STORE JUMP L5 LAB L6 LN 1 LP 4 LP 2 PLUS STIND LP 4 LN 1 PLUS SP 4 LAB L5 LP 4 LP 5 ENDFOR L6 STACK 4 LN 2 LP 3 LN 1 MINUS STORE JUMP L7 LAB L8 LP 4 LP 2 PLUS RV JF L9 LP 4 LN 2 MULT STORE JUMP L11 LAB L10 LN 0 LP 6 LP 2 PLUS STIND LP 4 LP 6 PLUS SP 6 LAB L11 LP 6 LP 3 LS JT L10 STACK 6 LAB L9 LP 4 LN 1 PLUS SP 4 LAB L7 LP 4 LP 5 ENDFOR L8 STACK 4 RTRN ENDPROC 0 |
; стековый кадр (два параметра и две локальные переменные) ; поместить на стек число 0 ; поместить ещё один 0, прибавить к нему 2-ой элемент стека ; записать в массив на вершине стека значение под ним ; всё то же самое для 1-ого элемента массива ; поместить на стек число 2 ; вычесть единицу из значения 3-его элемента стека ; записать результат в локальную переменную ; перейти к метке L5 ; объявление метки L6 ; взять 4-ый элемент стека, записать в массив по этому индексу 1 ; прибавить к 4-ому элементу стека 1, записать результат обратно ; L5: перейти к метке L6, если 4-ый элемент стека <= 5-ому ; объявление, что на стеке сейчас четыре элемента ; вычесть единицу из значения 3-его элемента стека ; перейти к метке L7 ; L8: сложить 4-ый и 2-ой элементы стека ; прочитать значение по этому адресу; если это 0, перейти к L9 ; умножить 4-ый элемент на два ; перейти к метке L11 ; объявление метки L10 ; взять 6-ой элемент стека, записать в массив по этому индексу 0 ; прибавить к 6-ому элементу стека 4-ый, записать рез-т обратно ; объявление метки L11 ; перейти к метке L10, если 7-ой элемент стека меньше 4-ого ; на стеке сейчас шесть элементов; объявление метки L9 ; прибавить к 4-ому элементу стека 1, записать результат обратно ; L10: перейти к L8, если 4-ый элемент стека <= 5-ому ; на стеке четыре элемента; окончание процедуры |
LET sieve(workvec, vecsize) BE
{
workvec!0 := 0
workvec!1 := 0
FOR i = 2 TO vecsize-1 DO workvec!i := 1
FOR i = 2 TO vecsize-1 DO
IF workvec!i DO
{ LET j = 2 * i
WHILE j < vecsize DO
{ workvec!j := 0
j := j + i
}
}
}
ENDFOR — вместо него генерируется пара LE JT.
Компилятор BCPL(1) поставлялся в виде OCODE, и чтобы перенести его на новую платформу, нужно было: {фигурными скобками} блоки программы, и именно на BCPL была написана первая программа «Hello, World!».
GET "libhdr"
LET start() = VALOF
{ writef("Hello*n")
RESULTIS 0
}
