Пример слепой немой удачи.
Преамбула
Почти десять лет назад я написал о библиотеке, разработанной двенадцатью годами ранее, в другом посте под названием Манифест клеток.
Ячейки и многие другие потоки данных, также известные как реактивные библиотеки, великолепны, но разработчики глухи к смене парадигмы. Хороший знак: поток данных настолько отличается, что его не могут понять те, кто вырос на других парадигмах. А чтобы быть лучше, он должен быть другим.
Я не чувствую себя плохо: они также невосприимчивы к Лиспу.
Lisp является аналогом парадигмы потока данных: чем тупее каждый из них, тем больше вы с ними сталкиваетесь. C++ и Java открыли для себя лямбду, и удачи вам в поиске UI-фреймворка, в котором нет «привязки данных» или каких-то реактивных хаков.
Какое, черт возьми, это ^^^ имеет отношение к изобретению клеток?
Что ж, у меня есть шанс посадить моего второго пользователя Cells, и он продолжает говорить, что ему нужно более глубокое понимание, и я вспомнил сумасшедший доклад перед Linux-группой Джея Сульцбергера на острове Манхэтто, как Джей любит говорить, в котором отступление от Lisp привело к незапланированному переизобретению Cells над клавиатурой, когда группа программистов FSF «C», глядя через мое плечо, выкрикивала исправления ошибок Lisp (они сделали довольно хорошо), и мне пришло в голову, что, возможно, проблема в том, что когда программисты получают взволнованные новым трюком с кодированием, они начинают пережевывать декорации с гиперболой Святого Грааля и отключают всех. Где был я?
Правильно. Идея здесь состоит в том, чтобы, наконец, донести невероятную силу потока данных, просто рассказав о проблеме, которую мы пытались решить, и о том, как мы ее решили, как мы затем исправили решение и плавно перешли к потоку данных.
Проблема: динамический, вложенный макет пользовательского интерфейса
Мы разрабатывали образовательное математическое приложение, предназначенное для отстающих учеников, поэтому меньше всего мы хотели, чтобы они сражались за то, чтобы набрать свою математику. Для начала мы разработали математический редактор WYSIWYG, а при следующем масштабировании беспокоились о том, что им не хватит места, когда они будут работать далеко.
Бары изменения размера не должны применяться, эти дети и взрослые уже недовольны.
Я придумал отличную схему расчета динамического макета, но на второй день мой ведущий разработчик JD сообщил о проблеме с моим подходом. Вариант использования был довольно специфичным: дроби.
Фон: геометрия, которую я придумал для любого визуального элемента, состояла из (а) смещения (x, y) этого элемента в его родительском контейнере и (б) локальных границ элемента: слева, сверху, справа, дно относительно (0,0) (отсюда «локальный»). Где нарисована коробка? Суммируйте смещения моих контейнеров, начиная с окна (0,0), и соответствующим образом сдвиньте локальную ограничивающую рамку.
Забавное примечание: позже подчиненный пожаловался, что моя геометрия понятна только мне самому. Харрамф. Я почувствовал себя лучше, когда узнал, что в OpenGL такая же система.
Так в чем проблема с дробями? Мой алгоритм надеялся вычислить геометрию дочернего элемента перед вычислением геометрии его родителя, но для того, чтобы операнды дроби были центрированы по вертикали, числитель, например, должен был быть горизонтально вставлен на половину разницы между шириной дроби и шириной числителя. Но дробь не знала своей ширины, пока числитель не определил ее ширину, потому что дробь брала бы максимум из числителя и знаменателя. Так что ни ребенок, ни родитель не могли пойти первыми.
Хорошо, хорошо: позже я понял, что у дробей должен быть атрибут вертикального выравнивания, говорящий «по центру», и что числитель должен просто располагаться горизонтально на минус половине своей ширины, но я посмотрел на этот случайный вариант использования и понял свою общую идею определения элемента. вся геометрия за один раз никогда бы не охотилась. Я также знал, что на самом деле цикличности нет, только в моем алгоритме.
«Все к доске!», — крикнул я, словно это была брешь в городской стене Харфлёра.
Изобретение
Верный моему пониманию, что это были не просто дроби, я начал с изложения номера задачи (будь то «1» или «42(а)»), постановки задачи (будь то «Упростить» или «Решить и охарактеризовать»). как условность, противоречие или тождество»), а под ними — задача любого размера, которую напечатал ученик.
Нулевой шаг
«Хорошо, что такое левый край номера задачи?», — риторически спросил я, случайно решив первую проблему: моя привычка «шагать» при решении сложных задач привела меня к размышлениям о выводе одного бита геометрии виджета. , а не его полная геометрия,
— Ноль, — заключил я. — То же самое с верхом. В отличие от OpenGL, геометрия экрана имеет тенденцию увеличиваться по мере того, как вы перемещаетесь вниз по экрану.
— Мы в ударе, — сказал я, чувствуя, что Харфлер наш. — Что такое правый край?
Шаг первый
Подождите. Прежде чем перейти к первому шагу, нам нужно сделать несколько предостережений.
- Весь приведенный ниже код был набран с помощью текстового редактора Blogger. Парены не будут балансироваться, опечаток будет предостаточно.
- Если вы не знаете Лисп, код может вызвать затруднения. Хорошим примером является то, что (defstruct a b c) — это редко используемая краткая форма, определяющая структуру типа «a» со слотами b и c.
- Черт, прошел год с тех пор, как я в гневе программировал Лисп. Если что-то ниже выглядит как Clojure, возможно, так оно и есть.
- Оставив в стороне глупости и неясности, если, как и я, вы внимательно смотрите на примеры и пытаетесь понять, что должно происходить, вы получите массу вопросов и «это не сработает!». История постепенной разработки продолжалась в течение нескольких недель в стабильном темпе и в течение многих лет с перерывами по мере того, как возникали новые проблемы схемы. Может быть, в этот раз, не смотри слишком пристально.
Теперь мы возвращаемся к шоу, начиная с первого шага, где, после удачного переключения на слот-мышление для левого края (и верхней части) виджета, я рассмотрел правый край того же виджета, который мы хотели увеличить. и уменьшаться по мере того, как студент редактировал номер задачи.
Шаг первый
«Хорошо, правый край — это левый край плюс ширина строки номера задачи с учетом метрик шрифта выбранного шрифта», — довольно очевидно заявил я, поскольку мы уже это делали. Но Харфлер был нашим.
Значение было указано как функция других значений. При создании экземпляра виджета textedit мы бы не указали разумную ширину 42, слишком большую для большинства проблемных номеров и прокрутки для больших чисел, мы бы указали:
(make-instance ‘textedit
…etc…
:l-right (lambda (self)
(+ (l-left self)
(fontStringWidth (text self)
(math-font *app*))))
Прохладный. Нам больше никогда не придется беспокоиться о том, в каком порядке вычислять вещи: другие значения, которые мы считываем, будут вычисляться JIT. Э, как?
Нам просто нужен аксессор (читатель), который знает, что мы делаем (и новый макрос defmodel для написания всех этих аксессоров):
(defmethod l-right ((self textedit))
(let ((sv (slot-value self ‘l-right)))
(if (functionp sv)
(funcall sv self)
sv)))
Да, нам нужно работать лучше, потому что функция — это прекрасное значение для слота, поэтому мы не можем предположить, что это правило должно быть фанназванным, но это справедливое предположение для экранных расположений, и оно не будет длиться долго. все равно долго.
JD сделал это за полдня, и мы были в восторге. Потом, конечно, колеса оторвались: вечно пересчитывать геометрию было слишком медленно. Обратите внимание, что это экспоненциальная проблема, потому что свойство P может вычислять несколько других свойств, а несколько других свойств могут вычислять P, и рекурсивно, так как контейнер за вложенным контейнером вычисляет свои свойства.
Шаг 2
Мы кешируем вычисление, и теперь нам нужна структура:
(defstruct cell rule value)
Обратите внимание, что это решает нашу предыдущую проблему: нам больше не нужно предполагать, что функция является формулой. Действительно, функция есть функция, мы сейчас ищем ячейки.
Гениально: когда мы получаем событие обновления Mac OS, мы пересчитываем всю геометрию, но никогда ничего не пересчитываем дважды. Мы очищаем все кэшированные значения, пересчитываем и перерисовываем.
Так продолжалось два дня. В то время 100 МГц считались быстрыми, поэтому достаточно скоро у нас было достаточно материала на экране, чтобы сделать полный пересчет слишком медленным.
Хорошей новостью является то, что я знал, что это не масштабируется, но когда дело доходит до оптимизации производительности, всегда приятно, когда меня спрашивают. Нас спросили.
Шаг 3
Чтобы обойти это, мы должны пересчитывать только по мере необходимости. Если учащийся вводит другую цифру в знаменателе, нам нужно пересчитать ширину знаменателя, пересчитать его горизонтальное смещение внутри дроби и, если знаменатель шире числителя, пересчитать ширину дроби и передать ее вверх по иерархии контейнеров. .
Обратите внимание на удачную оптимизацию: если бы знаменатель был достаточно меньшим, чем числитель, дробь приняла бы решение о той же ширине, что и раньше, и не было бы необходимости пересчитывать дальше вверх по иерархии контейнеров. Я отвлекся.
Итак, как мы принимаем решение «пересчитывать только по мере необходимости»?
(defstruct cell rule value users)
Ячейке необходимо знать, какие другие ячейки использовали ее значение в своих вычислениях, чтобы она могла сказать им пересчитать, если оно изменится. Держитесь за шляпы:
(defmethod lr ((self textedit))
(let ((sv (slot-value self ‘lr)))
(if (typep sv ‘cell)
(progn
(when *user*
(c-record-user sv *user*))
(let ((*user* sv))
(setf (value sv) (funcall rule self))
sv)))
Я должен любить специальные переменные Лиспа: выше мы одновременно (а) отслеживаем, кто может использовать нас, и (б) даем знать любому, к кому наше правило обращается, что мы их используем. Что может не бросаться в глаза читателю, так это то, что это работает рекурсивно, потому что при запуске новой структуры переменные, к которым обращается наше правило, могут вычислять свои значения JIT, перепривязывая *user* к себе.
Благодаря макросам Lisp это не требует слишком большого набора текста (поэтому выделяется семантика). Сначала макрос:
(defmacro c? (rule)
`(make-instance ‘cell
:rule (lambda (self)
,rule)))
(Плохо то, что лямбда-параметр self будет захвачен кодом правила. Гигиена? Нам не нужна вонючая гигиена!)
И сейчас:
(make-instance ‘textedit
…etc…
:lr (c? (+ (ll self)
(fontStringWidth (text self)
*math-font*)))
Но это только записывает зависимость. Порыв два:
(defmethod (setf l-right) (new-value self)
(let ((sv (slot-value self ‘l-right)))
(if (typep sv ‘cell)
(progn
(when (not (eql new-value (value sv)))
(setf (value sv) new-value)
(dolist (user (users sv))
(c-recompute user)))
new-value)
(setf (slot-value self ‘l-right) new-value))))
Обратите внимание, как распространение останавливается на неизменном изменении. Мы действительно делаем функциональный крик.
Обратите также внимание на то, что я был настолько сосредоточен на быстром функционировании, что упустил из виду, что мир перевернулся с ног на голову.
Это инверсионные очки. Носите их несколько дней без перерыва, и вдруг мир становится легко ориентироваться; мозг переворачивает мир назад, как если бы один бит контролировал наше зрение.
В этом случае лучшей метафорой может быть река, меняющая направление. Да, первоначальная проблема заключалась в том, чтобы знать, в каком порядке извлекать информацию для вычислений, но после настройки номер три библиотека заключалась в том, чтобы дать возможность некоторым начальным изменениям состояния домино эффективно перейти в другое состояние. Притяжение стало толчком, причинно-следственная связь была задействована.
Вот мы и снова, пережевывая декорации. Давайте снова займемся практикой: как на самом деле обновляется экран? Давайте просто посмотрим на приведенный выше фрагмент, где обнаружено изменение, теперь с простым трюком, чтобы сделать больше, чем просто изменить другие вычисленные значения:
(when (not (eql new-value (value sv))) (c-observe self ‘l-right new-value (value sv)) ;; <<--- NEW! (setf (value sv) new-value) (dolist (user (users sv)) (c-recompute user)))
c-observe – это общий мультиметод, который мы предоставляем в качестве обратного вызова "при изменении":
(defmethod c-observe ((self vis-obj) (slot (eql ‘l-right)) new old)
… insert here code to trigger the update of the
union of the old + new rectangles of self…)
Мы не только организуем эффективные, минимальные и полные изменения, но теперь у нас есть крючок для произвольного увеличения обработки изменений.
И последнее замечание: мы упомянули заранее, что в настоящее время все делают реактивное. Это правда, но Hoplon/Javelin — единственные, которые не требуют явной подписки и уведомления (и это работает путем поднятия проверки кода, поэтому он чрезмерно пересчитывает). Благодаря макросам Lisp и некоторым относительно скромным инженерным решениям подписка выглядит так (снова):
(make-instance ‘textedit
…etc…
:l-right (c? (+ (l-local self)
(fontStringWidth (text self)
*math-font*)))
… и уведомление выглядит так:
(setf (text self) (concatenate ‘string (text self) new-char))
т.е. невидимый. Нет необходимости прерывать мой процесс кодирования и кодировать издателя в новом источнике и подписке здесь, я просто пишу свой код и позволяю движку отметить зависимость. Чем сложнее становится пользовательский интерфейс, тем экспоненциально больше этот выигрыш.
Именно так были изобретены Cells, как и сам Lisp:
- Мы начали с трудной проблемы;
- мы использовали метапрограммирование для решения сложной проблемы;
- и мы беспокоились об опыте программиста.
