Хроники айтишника

Оказывается, уже полгода как PLT Scheme переименовали в Racket.
Блиин, как можно было губить такой бренд? Ему 40 лет как-никак, его знают все, кто хотя бы касался SICP, а тут теперь что-то невнятное.
Тем более слово "Scheme" читается вслух как «Ским», что мне весьма импонировало :)

Выдержка из одного эдиториала TC.

We then need to count the number of maximum matchings in this graph, and then we're done. Unfortunately, this is a #P-complete problem, and if we can solve it in polynomial time, we would have proved that P = NP. That would make this problem quite a bit trickier than the usual Division 1 Medium.

Слова, вынесенные в заголовок, отправили меня ржать под стол :D Почти буквально)

Тут один умный человек ещё раз рассосал по косточкам свои объективные претензии к C++. Причем на этот раз я с ним в каждом слове целиком и полностью согласен. Лично я бы добавил ещё парочку пунктов, кроме изложенных, но это уже не суть важно. Читайте.

Кстати, забавно получилось с грамматикой. В комментариях изрядно удивленный народ в шоке обсуждает «как же это так, контекстно-зависимый язык, как они там вообще компилятор-то написали, какая же это каша в нем творится?» У них в голове не укладывается :) Что же, вполне справедливо.

У меня было все ОК. Надеюсь, будет ещё круче.
Всех с Новым Годом :)

Есть вот такая замечательная ссылка: http://www.ega-math.narod.ru/Arnold2.htm

В ней две статьи из далекого 1998 года. Одна написана великим В. Арнольдом, так и называется "О преподавании математики", вторая - "Пятое правило арифметики", Виктор Дос.

Я позволю себе привести избранные цитаты:
( Read more... )

С тех пор прошло 12 лет. 12 лет назад я проводил беззаботное детство в детском саду, и понятия не имел о том, как решать квадратные уравнения :) Зато умел складывать, умножать, вычитать, делить, возводить в степень обыкновенные числа и десятичные дроби, и считал это само собой разумеющимся и простейшим пареной репы. Последующие 10 лет в школе и (на данный момент) 2.5 года в университете показали мне, как и великим математикам - авторам приведенных статей - всю суровую правду жизни: взрослые люди спокойно остаются на том же уровне, если они не понимают, во-первых, зачем им это нужно, во-вторых, откуда оно берется.

Я периодически общаюсь со школьниками, только что поступившими в лицей, и конкретно в маткласс, из которого я имел удовольствие выйти в свое время. Между нами разница в несчастных 6 лет, но я в точности помню, что мы такими не были. У нас не возникало того древнего, как само образование, вопроса: «Зачем нужны доказательства?». Точнее, он возник, но гораздо раньше, и нам дали понять смысл интуитивно, самостоятельно позволяя выводить факты и обнаруживать эти прекрасные, удивительные вещи, связывающие все буйство и красоту науки математики. Науки, черт возьми, естественной.
Люди уже и у нас считают, что вся суть этих палочек и крючочков - взять и заучить, нигде в реальной жизни оно тебе после экзамена не понадобится. Как в том анекдоте про выпускника, который проволочку в форме интеграла один раз согнул, чтобы телефон из канализационного люка достать. Но это же зло, дети, зло.

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

На дискретной математике - одна абстрактная структура с ассоциативной операцией, другая структура с двумя операциями, одна дистрибутивна по другой, а если там есть еще и нейтральный элемент по второй операции, то мы рассмотрим наличие или отсутствие его делителей и получим еще два подвида абстрактных структур, затем добавим еще три аксиомы, получим общим числом восемь и выделим последнюю абстрактную структуру в отдельный предмет, потому что она реально вам пригодится и там будет рассказываться с примерами.... нет, ну ё-моё!!! А остальное, значит, не пригодится?! Галуа свою короткую жизнь положил на то, чтобы вы тут за один месяц научились бросаться умными словами вроде "идемпотентное кольцо" и ни на один жалкий грамм не понимали, какое реальное применение оно имеет к проектированию и при чем тут, например, текстуры на плоскостях в вашем любимом Контр-Страйке? И что общей формулы решения нет для уравнения выше четвертой степени, вам сообщили, вы со скорбным лицом покивали, подумали про себя "Если мне попадется уравнение на экзамене - значит, у него есть метод решения попроще, а там уже и Wolfram Mathematica справится..."
А потом людям рассказывают о силе и мощи функционального программирования, они обретаются к Хаскеллу, а там же, кирдык ему в печенку, монады, моноиды, категории, функторы, стрелки, и вообще всякие зигохистоморфические препроморфизмы! И паренек в спешке улепетывает обратно, к своему jQuery. Там не надо знать математику (в программировании! испокон веков точной дисциплине!). Там достаточно интерфейсики клепать.

И когда на Хабре выкладывается статья о MapReduce с гордым подзаголовком "попробую без зауми" - это, черт возьми, клинический случай. Народ не интересует, откуда это взялось. Не интересует, правильно ли это вообще. Не интересуют особые рассуждения и тонкие случаи. Не интересуют модификации теории под другие неожиданные приложения. Они честно уверены, что готовая формула, или, в нашем случае, алгоритм, втиснется в их сферу: заработает - круто, не заработает - найдем другую дллку, мало их на свете, что ли. Это кошмарно.

Как говорил один мой преподаватель с первого курса, глядя на то, как мы не в силах решить тупейшую задачу: "У вас есть уникальная особенность: вы совершенно не умеете писать". Именно это я сейчас и вижу в тех школьниках и первокурсниках, которые попадаются мне на глаза - на факультативах, при репетиторстве, просто так. Они не умеют писать - то есть расписывать. Брать формулировку и выводить из нее следствия, идя хоть в какую-нибудь сторону, пользуясь известными фактами. В таких случаях и говорят: "ответ на задачу лежит в условии задачи", только перепиши другими словами, пойми наконец взаимосвязь эту скрытую, красивую, между двумя разными областями знаний!!! Не видят. Не понимают. Не считают нужным.

Я помню, когда я впервые узнал, что свободно подвешенная за два конца нить располагается в воздухе по закону гиперболического косинуса. Не поверил. Сообща с преподавателем это дело потом было доказано, и я еще несколько дней находился под впечатлением красивого приложения к реальной жизни.
Сейчас прошло меньше года - до меня за это время наконец дошло, что взаимосвязи математики с физикой жизни есть и гораздо более потрясающие, и в больших количествах. Потому что так изначально заложено в природе обоих наук, в конце-то концов. Но тогда это меня потрясло - и я сейчас могу сказать, почему. Потому что система образования не больно-то балует нас подобными примерами в первые 10+ лет обучения, и мы учим математику как абстрактную игру, забаву, в которой можно свести к моделям и играться объектами, обозначаемыми маленькими латинскими буквами.
Я прекрасно понимаю потребность подобных шагов в XX веке, когда господа Кантор, Гедель, Гильберт, Рассел и прочая CS-компания своими совместными действиями породили третий кризис математики. Который, кстати, до сих пор не закончен, и полчища математиков-логиков и теоретиков Computer Science по всему миру пытаются найти модель ZFC, или найти иную аксиоматику с доказанной непротиворечивостью, или решить наконец, равны ли P и NP, или разобраться с континуум-гипотезой... Это правильно, это основания математики, это необходимо для того, чтобы мы были уверены, что все наши результаты верны и мы можем далее продолжать работать. Но на самом-то деле в большинстве случаев есть правдоподобное "доказательство" корректности и непротиворечивости абстрактной структуры: в реальной жизни у нее есть модель, которая ведет себя так или почти так, как и предсказывает теория. А что компьютер не всегда стопроцентно сможет доказать теорему - ну что ж, увы. Вы же не думали, что все будет так легко. В конце концов, этой "легкости" противоречит сама жизнь и физика.

Не надо переносить этот подход на образование. Дети и студенты - скоропортящийся материал, мы быстро приобретаем свой собственный набор ценностей, который легко может отличаться от общепринятого миром. И понимание математических принципов, которые "рулят" миром, и как именно и где они им "рулят", в последнее время совершенно не входит в необходимый набор. Что печально. И дает катастрофические результаты, как показывают все те же статьи, приведенные мною в самом начале.

P.S. Мой блог посещают не самые глупые люди, насколько я знаю. В том числе куча программистов и других околоматематических специальностей.
Мне очень любопытно задать вам все тот же вопрос, который задавал Дос французским студентам. Сможете ли вы внятно объяснить, а почему же синус 30° равен 1/2? Ответ в комментах спойлерите, пожалуйста (цвет фона == цвет текста).
(UPD: наличие этого вопроса в постскриптуме НЕ значит, что на остальные размышления в посте не надо пробовать отвечать и дискутировать!)

Мне хочется верить, что в данной конкретной (очень нерепрезентативной) выборке все будет хорошо.
Совершенно не так, как в высших учебных заведениях XXI века.
Независимо от страны.

За последние несколько месяцев у меня набралось несколько планов на статьи, которых сильно не хватает хабра-аудитории. В целом они делятся на три больших класса: ФП, Computer Science и ACM-алгоритмистика.

Это - список, себе на память, чтобы брать из очереди, как время появится.

• FParsec - "утереть нос" товарищу Дмитрию mezastel Нестеруку :)


• Списочные гомоморфизмы. Свертка. Сканирующие пробеги. Короче, основы Vector Models for Data-Parallel Computing, и немного про MapReduce с математической стороны вопроса.


• Структура данных Rope, на основании уже существующего моего цикла про декартово дерево.


• В рамках той же темы "Основы Computer Science: ликбез для птушников" - λ-исчисление, порядок редукций, теорема Черча-Россера, и как отсюда логически выходят потоки и ленивые вычисления. Ссылки на SICP и ПФП.


• (?) Что-то про теорему Райса и теоретически вычислимые алгоритмы. Можно и классы сложности упомянуть.


• Дерево отрезков.


• (?) Дерево Фенвика.


• Суффиксный массив, его применения. Возможно - суффиксный автомат и дерево. Уже почти год хочу рассказать, офигенная вещь ведь.

To be continued...

Простой и в то же время кошмарный пример, демонстрирующий Силу и Мощь показательной функции.

> let f0 x = (x, x);;

val f0 : 'a -> 'a * 'a

> let f1 x = f0 (f0 x);;

val f1 : 'a -> ('a * 'a) * ('a * 'a)

> let f2 x = f1 (f1 x);;

val f2 :
  'a ->
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))

> let f3 x = f2 (f2 x);;

val f3 :
  'a ->
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))))) *
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))))

Если вам не жаль свой fsi.exe, можете пойти еще дальше:

> let f4 x = f3 (f3 x);;

Моя консоль честно трудилась 42 секунды, выводя тип этой функции на экран. В её возвращаемом значении 65536 упоминаний 'a.