• Как растаращить class-файл

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

      Можно поискать какие-то короткие конструкции языка, которые компилируются в длинные цепочки байткода, но линейный прирост меня не устраивал. Я сразу подумал про компиляцию finally-блоков: про неё уже писали на Хабре. Если вкратце, то для каждого finally-блока при непустом try-блоке создаётся минимум два варианта в байткоде: для случая нормального завершения try-блока и для случая завершения с исключением. В последнем случае исключение сохраняется в новую локальную переменную, выполняется код finally, затем исключение достаётся из локальной переменной и перебрасывается. А что если внутри finally снова разместить try-finally и так далее? Результат превзошёл все ожидания.
      Читать дальше →
    • Нисходящий парсер с операторным предшествованием

      • Translation
      Дуглас Крокфорд

      2007-02-21

      Введение


      В 1973 году на первом ежегодном симпозиуме «Принципы языков программирования» (Principles of Programming Languages Symposium) Вон Пратт представил статью «Нисходящий парсер с операторным предшествованием» (Top Down Operator Precedence). В этой статье Пратт описал метод синтаксического разбора, который объединяет лучшие стороны рекурсивного спуска и метода операторного предшествования Флойда. Метод Пратта очень похож на рекурсивный спуск, но требует меньше кода и работает гораздо быстрее. Пратт заявил, что его метод прост в освоении, реализации и использовании, необычайно эффективен и очень гибок. Благодаря своей динамичности он может использоваться для расширяемых языков.

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

      Есть и другое объяснение: этот метод наиболее эффективен для динамических, функциональных языков программирования и использовать его в статическом, процедурном языке куда сложнее. Свою статью Пратт иллюстрирует на примере Lisp и играючи строит синтаксические деревья по потоку лексем. Но методы синтаксического разбора не особо ценятся в сообществе Lisp-программистов, которые проповедуют спартанский отказ от синтаксиса. С момента создания Lisp предпринималось немало попыток придать этому языку богатый синтаксис в стиле ALGOL: CGOL Пратта, Lisp-2, MLISP, Dylan, Interlisp's Clisp, оригинальные М-выражения Маккарти и так далее. Но все они провалились. Для Lisp-сообщества согласованность программ и данных оказалась важнее выразительного синтаксиса. С другой стороны, подавляющее большинство программистов любит синтаксис, поэтому сам Lisp так и не стал популярен. Методу Пратта нужен динамический язык, но сообщество динамических языков исторически не пользовалось синтаксисом, который так удобно реализуется методом Пратта.
      Читать дальше →
      • +26
      • 11.9k
      • 7
    • Найти бозон Хиггса может каждый!


        12 мая ЦЕРН объявил «Higgs Boson Machine Learning Challenge», конкурс на лучший алгоритм по поиску событий с участием бозона Хиггса в наборе экспериментальных данных. Конкурс продлится до 15 сентября, победителей ждут денежные призы от $2000 до $7000. Удачное решение может быть интегрировано в реальный процесс обработки данных с детектора ATLAS. Для участия в конкурсе не нужны специальные знания в физике элементарных частиц.
        Читать дальше →
      • Пул констант

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

        Возьмём, к примеру, такой код:

        System.out.println("Hello World!");

        Он транслируется в три инструкции байткода: getstatic (для загрузки статического поля System.out), ldc (для загрузки константной строки «Hello World!») и invokevirtual (для выполнения виртуальной функции println). Попробуйте прикинуть, сколько констант нужно для того, чтобы этот код работал.
        Читать дальше →
      • Как понять NullPointerException

          Эта простая статья скорее для начинающих разработчиков Java, хотя я нередко вижу и опытных коллег, которые беспомощно глядят на stack trace, сообщающий о NullPointerException (сокращённо NPE), и не могут сделать никаких выводов без отладчика. Разумеется, до NPE своё приложение лучше не доводить: вам помогут null-аннотации, валидация входных параметров и другие способы. Но когда пациент уже болен, надо его лечить, а не капать на мозги, что он ходил зимой без шапки.

          Итак, вы узнали, что ваше приложение упало с NPE, и у вас есть только stack trace. Возможно, вам прислал его клиент, или вы сами увидели его в логах. Давайте посмотрим, какие выводы из него можно сделать.
          Читать дальше →
        • Сбор лайткоинов в помощь вьетнамскому приюту

            Update: сбор средств завершёл и статья напечана!


            Пока некоторые центробанки считают, что криптовалюты нужны для финансирования терроризма и создания финансовых пирамид, энтузиаст из Вьетнама saigoned проводит акцию по сбору лайткоинов в поддержку детского приюта Gò Vấp, где много больных детей, в том числе испытывающих на себе последствия от «Агент Оранж».
            Читать дальше →
          • FindBugs помогает узнать Java лучше

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

              В этом плане статический анализатор похож на опытного товарища, который сидит рядом и смотрит, как вы пишете код. Он не только подсказывает вам: «вот здесь ты ошибся, когда копипастил», но и говорит: «нет, так писать нельзя, вон сам в документацию глянь». Такой товарищ полезней самой документации, потому что он подсказывает только те вещи, с которыми вы реально сталкиваетесь в работе, и молчит о тех, которые вам никогда не пригодятся.

              В этом посте я расскажу о некоторых тонкостях Java, о которых я узнал в результате использования статического анализатора FindBugs. Возможно, какие-то вещи окажутся неожиданными и для вас. Важно, что все примеры не умозрительны, а основаны на реальном коде.

              Тернарный оператор ?:


              Казалось бы, нет ничего проще тернарного оператора, но у него есть свои подводные камни. Я считал, что нет принципиальной разницы между конструкциями
              Type var = condition ? valTrue : valFalse;
              и
              Type var;
              if(condition)
                var = valTrue;
              else
                var = valFalse;

              Читать дальше →
            • Нескучные интегралы

                Некоторые из вас, вероятно, видали на просторах сети эту задачку: какое число продолжает следующий ряд?

                Предлагался такой очевидный правильный ответ:

                Для тех, кому неочевидно, как он получен, предлагалось объяснение. Пусть (ну и 1 при x = 0, хотя неважно). Тогда каждый член ряда — это значение следующего интеграла в цепочке:

                Пока всё идёт хорошо, но тут внезапно:

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

                  Затеяли мы амбициозный проект — открыть свой электронный научный журнал. Поначалу казалось, что это дело неподъёмное и ничего хорошего не выйдет, тем более, что мы никогда издательским делом не занимались. Однако как и с любым делом тут главное начать. Хотя будущее нашего журнала ещё под вопросом, но я решил описать наш опыт на этом нелёгком пути и, надеюсь, этот рассказ сподвигнет ещё кого-нибудь создать свои хорошие журналы на благо российской науки.

                  Нам хотелось примерно следующее: создать электронный рецензируемый журнал на английском языке, полностью официальный, который бы воспринимался всерьёз западными учёными, на статьи в котором бы ссылались, чтобы высчитывался импакт-фактор. Программа-минимум — попасть в список журналов ВАК, в идеале — попасть в PubMed (журнал у нас по биоинформатике). Коммерческая выгода не предполагалась.
                  Читать дальше →
                • FindBugs против CDK

                    Мне всегда интересно читать посты от PVS-Studio о том, как они ищут баги в каком-нибудь опенсорсном проекте. Я решил, что я тоже смогу написать такой пост, только про Java. Существует совершенно замечательный бесплатный статический анализатор Java-кода FindBugs. О нём на удивление мало писали на Хабре.

                    Помимо анализатора кода для такой статьи требуется подопытный кролик. Нужен довольно большой проект, но при этом не настолько распространённый, чтобы разработчики идеально вылизывали код. Я выбрал проект Chemistry Development Kit (версия 1.4.19), которым доводилось пользоваться. FindBugs я установил как плагин к Eclipse, потому что мне так привычнее.


                    Читать дальше →
                  • Эмуляция хвостовой рекурсии в JavaScript

                      Если кто-то ещё не знает, что такое хвостовая рекурсия, вот простой пример метода, складывающего в лоб натуральные числа от 1 до n (n≥0):
                      function add(n,acc) {
                        if(n===0) return acc;
                        return add(n-1,acc+n);
                      }

                      Изначально функция вызывается с параметром acc=0. В случае, если n не равно нулю, метод вызывает сам себя с другими параметрами и возвращает результат. Компилятор (или интерпретатор, или виртуальная машина) могут понять, что текущий вызов функции в стеке уже не нужен, стереть его и заменить следующим вызовом. Таким образом, рекурсия не приводит к разрастанию стека. Строго говоря, хвостовой вызов не обязан обращаться к текущей функции: вызов любой другой тоже может быть хвостовым. Главное условие: вызов функции и возврат её результата должны быть последними действиями в текущей функции. К примеру, в такой реализации метода хвостовой рекурсии нет, так как после вызова происходит ещё сложение:
                      function add(n) {
                        if(n===0) return 0;
                        return n+add(n-1);
                      }

                      По ряду причин хвостовая рекурсия в JavaScript не поддерживается (обсуждение на эту тему есть на StackOverflow). Поэтому вызов вроде add(100000,0) завершится исключением. На Хабре предпринимались попытки решить эту проблему через setTimeout, но это выглядит не очень честно и не очень красиво. Более изящное решение для языка Python было предложено с использованием «трамплина». Похожий подход для JavaScript рассмотрен здесь. Но мне захотелось, чтобы работало быстро и чтобы функцию можно было записать прямо как в примере выше. Посмотрим, что можно сделать.
                      Читать дальше →
                    • Таинственный FrontCache

                        Всё началось с того, что я в очередной раз ковырял в Eclipse Memory Analyzer дамп памяти Java-приложения и увидел такую интересную вещь:

                        С кодом HashMap я знаком весьма неплохо, но вложенного класса FrontCache никогда там не видел. Может, с последним обновлением JDK мне прислали обновлённый HashMap? Я заглянул в исходники, но слова «front» там не обнаружилось. Стало интересно, откуда же этот класс берётся и что он делает.
                        Читать дальше →
                      • Браузеры генома

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

                          Читать дальше →
                        • Латентность при загрузке веб-страниц

                            Пост «Кое-что о весе страницы» вызвал у меня желание написать маленькое дополнение. Многие замечают, что оптимизация размера веб-страниц становится менее актуальной в связи с увеличением пропускных способностей каналов. Рано или поздно все будут сидеть на гигабите, и будет совершенно неважно, весит ваша страница 100Кб или 250. Возможно, так оно и будет. Однако помимо скорости канала есть и другой параметр — задержка или латентность. И если пропускная способность каналов с развитием технологий может вырасти ещё очень сильно, то у латентности существует физический предел: это скорость света в оптоволокне — около 200 тысяч километров в секунду.

                            Хотя эта скорость очень велика, но всё же недостаточно, чтобы о ней забывать, ведь и планета у нас немаленькая. Wolfram Alpha не зря выдаёт на запросы по расстоянию время прохождения этого расстояния светом в волокне. Пусть у вас стоит сервер в Токио, а клиент пришёл из Рио-де-Жанейро. Если даже эти два города соединить оптоволокном по кратчайшей траектории на поверхности Земли, свет будет идти 86.7 мс.
                            Читать дальше →
                          • Накладные расходы памяти у коллекций

                              Мне было интересно, какие коллекции сколько съедают дополнительной памяти при хранении объектов. Я провёл замеры накладных расходов для популярных коллекций, предполагающих хранение однотипных элементов (то есть списки и множества) и свёл результаты на общий график. Вот картинка для 64-битной Hotspot JVM (Java 1.6):

                              Читать дальше →
                            • Визуализация характеристической функции

                                Многие в общих чертах представляют, как работает обратная лучевая трассировка: через каждый пиксель окна вывода алгоритм пропускает луч и вычисляет, с какими объектами сцены он пересекается и как в результате данный пиксель должен быть освещён. Алгоритм по сути требует, чтобы у нас была функция, которая для каждой позиции возвращает цвет точки. Разумеется, тот же подход можно применять не только для трёхмерной графики: любое изображение можно растеризовать таким образом, если у нас есть подходящая функция. Рассмотрим для примера, как с помощью такого подхода решить задачу визуализации диаграмм разложения на простые множители, о которой написал helarqjsc.

                                Моя реализация здесь. На картинке изображено 10! = 3628800, хотя всех деталей, разумеется, не видно.
                                Читать дальше →
                              • Изменяемые числовые объекты

                                  Как известно, в Java существуют примитивные типы для чисел (byte, short, int, long, float, double) и объектные обёртки над ними (Byte, Short, Integer, Long, Float, Double). В различных статьях можно встретить диаметрально противоположные рекомендации о том, чем пользоваться. С одной стороны объектные обёртки универсальны: их можно использовать со стандартными коллекциями, которые удобны, инкапсулированы и вообще прекрасны. Но боксинг убивает производительность и ест кучу памяти. Примитивные типы быстры и компактны, но их можно поместить только в массивы, которые и от записи не защитишь, и абстракция на нуле. Если же вам нужно что-то типа Map, для отображения чего-нибудь на числа, то придётся либо мириться с потерей производительности и памяти, либо использовать сторонние библиотеки, реализующие нестандартный интерфейс. Однако в некоторых случаях вам помогут изменяемые (mutable) числа.
                                  Читать дальше →
                                • Интерфейсы классов и коллекции

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

                                    Предположим, у вас есть интерфейс для некоторых коллекций, которые помимо прочего функционала позволяют доставать наборы упорядоченных строк по ключу. То есть вам нужен метод типа
                                    List<String> getElements(String key);
                                    

                                    Но вы решили, что иногда эти наборы бывают огромными, либо трудно достать все строки сразу (например, некоторые реализации запрашивают их у какого-нибудь медленного веб-сервиса с дурацким протоколом). А применяете вы их, например, отображая на экране с постраничной навигацией или подгружая частями. Тут некоторым разработчикам придёт мысль расширить интерфейс как-то так:
                                    public interface MyCollection {
                                        List<String> getElements(String key);
                                        String getElement(String key, int index);
                                        List<String> getElementsRange(String key, int fromIndex, int toIndex);
                                        int getElementsCount(String key);
                                    }
                                    
                                    Читать дальше →
                                  • Заглавные и строчные буквы

                                      Я собрал здесь некоторые не очень очевидные факты о заглавных и строчных буквах, с которыми может столкнуться программист в работе. Многие из вас переводили строки во «все заглавные» (uppercase), «все строчные» (lowercase), «первую заглавную, а остальные строчные» (titlecase). Ещё более популярна операция сравнения без учёта регистра. В мировом масштабе такие операции могут быть весьма нетривиальны. Пост построен в виде «сборника заблуждений» с контрпримерами.

                                      1. Если я переведу строку в uppercase или lowercase, число Unicode-символов не изменится.

                                      Нет. В тексте могут попасться строчные лигатуры, которым не соответствует один символ в верхнем регистре. Например, при переводе в uppercase: fi (U+FB00) -> FI (U+0046, U+0049)

                                      2. Лигатуры — изврат, ими никто не пользуется. Если их не учитывать, то я прав.

                                      Нет. Некоторым буквам с диакритикой нет точного соответствия в другом регистре, поэтому приходится использовать комбинированный символ. Скажем, в языке африкаанс есть буква ʼn (U+0149). В верхнем регистре ей соответствует комбинация из двух символов: ʼN (U+02BC, U+004E). Если вам попадётся транслитерация арабского текста, вы можете столкнуться с (U+1E96), которой в верхнем регистре также нет односимвольного соответствия, поэтому придётся заменять на (U+0048, U+0331). В ваханском языке есть буква (U+01F0) с аналогичной проблемой. Вы можете возразить, что это экзотика, однако на африкаанс в википедии 23000 статей.

                                      3. Ну хорошо, но давайте считать комбинированный символ (с участием modifying или combining code points) одним символом. Тогда длина всё же сохранится.

                                      Нет. Есть, например, в немецком языке буква «эсцет» ß (U+00DF). При переводе в верхний регистр, она превращается в два символа SS (U+0053, U+0053).
                                      Читать дальше →
                                    • Бесконечно выгодная программа

                                      • Translation
                                      Недавняя статья на Slashdot о программировании игр на ассемблере для Атари (Donkey Kong и я) напомнила об ассемблерных приложениях, которые я писал по молодости, и о компьютерах, которые у нас тогда были.

                                      Поначалу я набирался опыта на DEC PDP-8, но самый кайф начался, когда появилась CP/M. CP/M изначально была «операционной системой для бизнеса», но ещё это была система, которую можно было позволить себе иметь дома, — серьёзная вещь для молодого подающего надежды гика.
                                      Читать дальше →