Интересный факт: в Java'е могут быть dead-lock'и

Вот абсолютно невинный код:

class A {
    static B B = new B();
}

class B {
    static A A = new A();
}

Можете ли вы заметить, где здесь dead-lock?



Шаг 1. Тред 1 вызывает код инициализации класса А и занимает его монитор. Тред 2 вызывает код инициализации класса B и занимает его монитор.

Шаг 2. Теперь вызовы конструктора потребуют, чтобы соотвествующие классы были инициализированы.

Шаг 3. Так как классы уже находятся в процессе инициализации, оба треда просто подождут, когда инициализация закончится.


Почему парсить C++ трудно

Известно, что компилятору языка C++ работать существенно сложнее, чем, скажем, компилятору Java. Давайте разберемся, почему.

Вот фрагмент из Михаила Щербакова:

«[Его жизни Звонкий балаган] летит и в холод, и в жару, и в гром, и в тишину.»

Разбираем. Глагол «летит». Дальше, винительный падеж, винительный падеж, винительный падеж, винительный падеж. Стоп, стоп. «В тишину» – не подходит по семантике. Должно было быть «летит в тишине». А если «летит в тишину», то это значит ответ на вопрос «куда?». Значит это было все перечисление того, куда летит Балаган? Ему предстоят холод, жара, гром и тишина? Вот облом, забываем все впечатления от строки и начинаем разбор с начала.

Примерно так. Человеку эта игра слов может показаться забавной, ну а компилятору – нет.

Что я узнал про Java'у не сразу

1. HashMap всеядный, но это совсем не бесплатно.
Да, в Java'е у любого объекта есть метод hashCode, но как он работает? Вы тоже считали, что он просто возвращает внутренний адрес объекта? В JVM объекты двигаются в памяти, там нет постоянных адресов. Приходится заводить поле, чтобы хранить этот identity hash code и возвращать всегда одно и то же число.

2. Методы классов вызываются как в C++ (хорошо), методы интерфейсов вызываются как в JavaScript'е (плохо).
Для классов работает стандартная схема: экземпляр ссылается на виртуальную таблицу; известно, что требуемый метод хранится, скажем, в ячейке №5. Итого, один переход по указателю и один переход по смещению. А для интерфейсов такого нет: когда нужно вызвать метод, например, int size(), то делается переход в виртуальную таблицу, где во всем списке натурально по имени и сигнатуре приходится искать нужную запись, вообще говоря, каждый раз. Потому что никакого фиксированного номера ячейки у нас нет.

3. Какой тип получается у анонимного класса?
Допустим, вы создали на лету Runnable:

(new Runnable() { public void run() { } })

Прада ли, что у вас получилось выражение типа Runnable?
Нет, не правда, это другой тип. Он конечно у вас очень скоро сдуется до обычного Runnable'а, но можно успеть поймать, пока тип настоящий:

new Object() {
    int gcd(int a, int b) {
        if (a == b) {
            return a;
        } else if (a < b) {
            return gcd(a, b - a);
        } else {
            return gcd(a - b, b);
        }
    }
}.gcd(1071, 462);

Видите, у этого класса есть метод gcd(int, int), я его вызываю. (Таким образом можно на лету сделать рекурсивный код целиком внутри другого метода.)

Концепты: 7. Описание протокола с состояниями

Задача: написать интерфейс взаимодействия между двумя процессам/потокам, которые работают по очереди и передают друг другу данные.

Начнем с того, что у двух потоков есть только один способ сообщать данные друг другу: записывать значение в переменную и дергать семафор; после этого другой поток из этой переменной читает (немного непривычно после ООП, где объекты посылают друг другу сообщения). Как записать такой интерфейс взаимодействия, если данные бывают разных типов – непонятно. Например, как описать интерфейс между процессами (не сами процессы), когда передаем сначала два boolean'а, а потом последовательность строк?

Collapse )

Концепты: 6. Легкие Fiber'ы

Задача: сделать алгоритмы, которые выполняются параллельно; многопоточность не использовать (она дорогая и требует эзотерических знаний).

Традиционно алгоритмы оформляют как процедуры – то есть запускать их можно только последовательно. Например, есть xml-parser – разбирает строку как xml-дерево, и есть алгоритм построения пользовательских данных по этому xml-дереву. Если запустить их по очереди, то дерево придется целиком хранить в памяти как промежуточные данные; это не всегда приемлемо, они даже могут целиком не умещаться в оперативной памяти. Параллельное исполнение позволило бы разбирать строку и сразу же «скармливать» xml-данные второму алгоритму. Можно оформить алгоритм не в виде процедуры, а в виде callback'а, т. е. объекта который получает порцию данных, обрабатывает ее, сохраняет состояние и возвращает управление до следующего вызова. Тогда два алгоритма (или больше) действительно смогут работать в параллель, так обычно и делают. Но записывать алгоритм в виде callback'а (или в «пассивном» виде) обычно очень тяжело (простые случаи не в счет). Например, алгоритм обхода дерева или алгоритм соединяющий два списка в один: в виде процедуры они выглядят тривиально, а в виде callback'а (в данном случае он называется «итератор») становятся сложными и запутанными.

Лучше оставим программисту право оформлять свои алгоритмы в естественном процедурном виде и посмотрим, как при этом их можно эффективно выполнять одновременно. Все что должен нужно программисту – это возможность запустить любую процедуру в новом потоке и оператор, который передает управление от одного потока другому. Например, обход дерева будет записан как обычная рекурсивная программа, которая на каждом элементе выполняет инструкцию «yeild(master_thread)», останавливаясь при этом до тех пор, пока основной программе не понадобится следующий элемент. Основной же программе будет казаться, что это у нее итератор с методом next().

Мы получаем, что есть два или более потоков, которые выполняются по очереди (кооперативно, такое бывает и называется Fiber'ы). Как известно, состояние каждого потока определяется его программным стеком, на котором хранятся все локальные переменные и адреса возвратов. Но стандартная организация стека очень расточительна: всегда выделяется большой участок памяти, способный вместить глубокую рекурсию (поэтому в программе может быть только ограниченное число тредов). Если мы хотим создавать по потоку на каждый итератор, это нам, понятно, не подходит. Может быть и альтернативная организация стека – в heap'е. Функция при каждом вызове выделяет себе участок памяти, в котором держит свои данные и указатель на память вызвавшей функции, а когда заканчивается – освобождает память. Получается такой связный список, который практически не тратит память впустую. Но платой за такую эффективность является очень низкая скорость работы.

Сделаем гибридную конструкцию. Заведем один единственный традиционный стек, который будем использовать всегда, когда возможно. То есть всегда, когда функция, которую мы вызываем, обещает завершиться, не передавая никому управление, а это большинство функций. Если же функция может выполнить оператор yield (прямо или вызвав другую функцию), то общий стек ей давать нельзя (он будет занят, когда понадобится передать управление), и ее данные должны всегда храниться в heap'е. Таким образом все функции делятся на два класса – прерываемые (должны хранить данные в heap'e) и непрерываемые (могут хранить данные на общем стеке). По определению непрерываемая функция не может вызывать прерываемую.

Остается определить, какие функции какие. Возлагать лишнюю работу на программиста в наше время не модно. Но можно положиться на виртуальную машину (это в моде) и ее адаптивные способности. Пусть все функции поначалу считаются непрерываемыми. Когда же во время работы программы непрерываемая функция наконец выполнит оператор yield, виртуальная машина должна на ходу переназначить ее и все функции ниже нее по стеку прерываемыми. Функции должны быть перекомпилированы, их данные перемещены в heap, а основной стек освобожден. Не так это и трудно. При этом, с точки зрения программиста ничего не произойдет. Но в следующий раз эти функции будут сразу выделять память в heap'е.

Задача решена.

Теперь любой сколь угодно сложный алгоритм может быть выполнен в виде callback'а; например, компиляция программы.

Еще одно интересное применение этой технологии может быть для систем с event loop'ом. Такие системы по смыслу исполняют несколько потоков, реально являясь однопоточными (для простоты); например Node.JS – это веб-сервер на JavaScript'е. Такой эффект достигается за счет того, что потоки оформляются в виде callback'ов, которые выполняют часть работы и возвращают управление диспетчеру (event loop'у). Описанный здесь подход позволил бы сохранить все преимущества системы, но программировать потоки как обычно, не заботясь о том, где придется возвращать управление.

Концепты: 5. Рефакторинг для кода и данных

Обычно, программы сначала пишут, а потом – запускают. Интересно было бы поэкспериментировать с тем, как делать эти две вещи одновременно. Конечно, если я разрабатываю коммерческий mp3-плеер, это вряд ли очень нужно. Другое дело с проектами под конкретного заказчика; здесь типично, когда программа работает в одном экземпляре и требования к ней проясняются по ходу использования.

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

Я это вижу так. Возьмем небольшой масштаб нагрузок, например веб-сервер для офиса. Типизированный язык программирования (Java), типизированное API к базе данных, база данных объектная. IDE знает об этом API и о самой базе данных. Java’ский компилятор следит за тем, чтобы программа была согласована с API, новый tool следит за тем, что API соответствует базе данных. Этот же tool помогает базу данных менять (в виде рефакторингов) пока программа остановлена, то есть предполагается, что сервер не работает, пока им занимается программист. Для коммерческих программ это, видимо, неприемлемо, ну так не все сразу.

Пример. Нужно изменить работу с заказами. Программист меняет базу и программу, выполняя рефакторинг, делая это в несколько шагов. Шаги можно разнести по времени. Важно, что сервер остается полностью работоспособным после каждого шага.
  1. Создается новый (пустой) тип  ОбобщенныйЗаказ.
  2. Тип Заказ делается наследником типа ОбобщенныйЗаказ (это разрешено, пока предок пустой).
  3. Все ссылки на Заказ меняют свой тип на ОбобщенныйЗаказ. Программа перестает компилироваться из-за этого и должна быть изменена. Еще тут бы очень не помешал алгебраический тип данных: «ОбобщенныйЗаказ – это либо Заказ, точка», но в Java’е такое сделать трудновато. Программист подготавливает программу к тому, что бывает разные типы заказов (добровольно или принудительно всюду вставляет switch с одной веткой).
  4. Тип Заказ переименовывается в СтарыйЗаказ.
  5. Создается новый тип НовыйЗаказ, который наследуется от типа ОбобщенныйЗаказ, он же включается в алгебраический тип, т.е. теперь «ОбобщенныйЗаказ – это либо СтарыйЗаказ, либо НовыйЗаказ». Программа перестает компилироваться, пока программист во всех обращениях к типу ОбобщенныйЗаказ не сделает поддержку типа НовыйЗаказ (добавит в каждый switch новую ветку с заглушкой).
  6. Тип НовыйЗаказ заполняется полями, заглушки заменяются на работающий код (создаются новые веб-формы и т.д.).
  7. Допускается создание пробных экземпляров типа НовыйЗаказ через UI.
  8. Если НовыйЗаказ работает неправильно:
    • Тестовые экземпляры удаляются.
    • Поля типа меняются произвольно (это разрешено делать, пока нет экземпляров).
    • Возврат к предыдущему пункту.
  9. Тип НовыйЗаказ вводится в штатную работу.
  10. При необходимости, запускается скрипт, который переделывается старые заказы в новые (или старые изживаются со временем).
  11. Удаляет тип СтарыйЗаказ (это возможно, если нет экземпляров).

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

Концепты: 4. Описание логики диалогов

Программировать диалоговые окна – довольно уныло. Возьмем пример.



Типичная программа будет состоять из функции создания графических элементов, развешивания listener’ов, которые будут считывать данные, включать (enable’ить) или выключать другие элементы и выводить сообщения об ошибках, а также из метода, который достает введенные значения и отдает их в конце вызывающей стороне. Структура кода никак не будет похожа на структуру диалога. Программист в основном будет занят анализом того, какие события к каким изменениям должны приводить. При этом добавление еще одной логической связи между элементами может привести к существенным переделкам программы.

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

DeliveryDetails askDeliveryDetails() {
  print("Choose delivery detail:\n");
  print("(s)elf-delivery/(c)ourier service/(m)ail\n");
  char deliveryTypeChar = readChar();
  switch (deliveryTypeChar) {
  case 's':
    return new DeliveryDetails.SelfDelivery();
  case 'c': {
    String address = readLine("Enter address");
    print("Do you know your GPS coordinates? (y/n)");
    char knowsGps = readChar();
    GpsCoordinates gpsCoordinates;
    if (knowsGps == 'y') {
      String latitude = readLine("Latitude:"); 
      String longitude = readLine("Longitude:"); 
      gpsCoordinates = new GpsCoordinates(latitude, longitude);
    } else {
      gpsCoordinates = null;
    }
    String contactPhone = readLine("Enter your contact phone:");
    return new DeliveryDetails.CourierDelivery(address, gpsCoordinates,
                                               contactPhone);
  }
  case 'm': {
    String address = readLine("Enter mail address");
    String index = readLine("Enter mail index");
    return new DeliveryDetails.MailDelivery(address, index);
  }
  default:
    throw new RuntimeException();
  }
}

Идея в том, чтобы сделать язык, который выглядел бы как императивный (как в этом примере), а на самом деле описывал бы логику работы диалогового окна и первичную обработку данных.

Вот несколько мыслей:

  • в программе перемешаны обращения к пользователю (read/write) и операции над данными; например:
    String pwdhash = makeHash(readLine(“Enter password”));

  • пользователь будет вводить данные в диалоговом окне в произвольном порядке, необходимые фрагменты «программы» перевыполняются каждый раз;
  • операторы if/switch управляют вычислениями, а также доступностью элементов диалога: если readLine оказался в ветви, которая «не выполняется», поле ввода disable’ится;
  • брошенное исключение блокирует кнопку OK и высвечивает сообщение где-то в поле окна;
  • язык вводит мало своих конструкций, а вместо этого эксплуатирует базовый язык (например Java’ы): выражения и имена типов можно писать на базовом языке (примерно как ассемблерные вставки);
  • некоторые выражения могут на самом деле вычисляться долго (асинхронно); например, проверка занятости логина;
  • программа транслируется в код на базовом языке; в том числе генерируется интерфейс доступа к диалоговым элементам; собственно созданием диалоговых элементов программист занимается вручную, он же реализует этот интерфейс.

Есть две реализации; одна была не законченна, другая еще не закончена.

Концепты: 3. Плавный переход от динамической к статической типизации

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

Use-case такой: начинаем писать маленькую незатейливую программку типа на JavaScript’е, разработка «на коленке», пишем быстро и легко. Предполжим, программа всем нравится, и дела у нас идут хорошо. Размер исходников растет, разбираться в них уже не просто. Тогда несколько основных классов наконец объявляются явно, как в Java'е. Их методы все еще можно вызывать динамически, но уже больше не хочется. Программу приходится начать компилировать (исходники начинают зависить друг от друга), но это не страшно, все равно какой-то release-процесс к этому времени уже налажен (тесты там какие-никакие). Дальше рост числа программистов и стихийный процесс перевода сложных мест на статическую типизацию. Один из разработчиков ядра просит больше не использовать его классы динамически, потому что он будет их рефакторить скоро, а вручную искать и исправлять всех клиентов он не собирается. Возникающее публичное API уже полностью пишется только статически. К третьему релизу в главных модулях динамическая типизация запрещена, код компилируются с ключом --static-only как обычный код на Java’е. ...

А если в самом начале программа не пошла в рост, она так и остается написанной типа на JavaScript’е.


Интересно в этом отношении в самом деле взглянуть на Java’у.

Во-первых, когда они добавляли в язык generic’и, они сделали в точности так: сначала все коллекции были без указания типов; потом стало можно типы указывать, но осталась свобода этого не делать; наконец, у компилятора есть ключ, который требует, чтобы типы были указаны везде, гарантируя при этом, что все коллекции станут строго типизированны.

Во-вторых, любопытно, сложно ли сделать такой язык из Java'ы? Мне кажется, что не очень. Уже сейчас можно работать без типов переменных и натурально вызывать каждый метод через reflection:
Object message = "Hello, world!";
Object systemOut = System.out; // нет зависимости от java.io.PrintStream

// Подразумевается короткий синтаксис: systemOut->println(message);
systemOut.getClass().getMethod("println", String.class).invoke(systemOut, message);

Был бы интересный эксперимент. Конечно, тут есть много технических проблем, но все они должны легко обходиться.

Концепты: 2. Git и параллельные патчи

Git – это относительно молодая система version control’а. От более классических систем (CVS, SVN) ее отличает то, что она полностью работает локально, то есть клиент и сервер находятся физически в одном каталоге. Работа в сети, конечно, тоже поддерживается, но отходит как бы на второй план. За счет этого программист получает свободу работать со своим собственным репозиторием, со своими бранчами состоящими из более мелких изменений. При этом становится очевидно, что со внешним миром он обменивается не версиями файлов, а изменениями в них или patch’ами. В принципе, так было всегда при совместной работе над проектом, но не так явно.

Вообще в Git’е немного смещается перпектива: от ревизий в сторону работы именно с patch’ами. Patch, представленный как цепочка изменений (т.е. branch), можно его объединять (merge) с еще одним или применять поверх другой ревизии (rebase).

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

Я представляю себе это в метафоре Фотошопа. Программист берет стабильную версию программы за основу (background) и создает два layer’а, в которых будут храниться изменения. Layer’ы, понятно, представлены branch’ами в Git’е. В Фотошопе у каждого layer’а есть такой значок в форме глаза, который этот layer показывает или прячет. Соответственно, патч применяется к рабочим файлам или отменяется. Программист правит файлы и говорит системе, в какой именно патч это должно пойти.

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

Реализуется это на основе Git’а довольно просто: создаем временный branch и merge’им в него все патчи, которые пользователь хочет сейчас видеть; даем ему внести исправления; спрашиваем, в какой патч положить; смотрим на изменения и добавляем их в нужный patch. Конечно, возможны конфликты. Конечно. Но когда их не было?



Была предпринята незавершенная попытка реализации на базе Eclipse'а.

Концепты: интересно было бы написать

В связи с занятием программированием периодически возникают мысли о том, какую еще программу интересно было бы соорудить. Конечно, с детства больше всего хочется написать компьютерную игрушку навроде Gobliiins и в духе Магазинчика БО :), но это я совсем не представяю, как делать. Вместо этого попробую описать вещи, которые тоже давно есть желание попробовать и технически понятно как.

Один из концептов, это конечно Алгебраические типы данных в Java. Этим я давно и с разной степени интенсивности занимаюсь. Теперь об остальном.