• Рейтрейсер на JavaScript

      TitleImage

      Знаете ли вы что такое рейтрейсер? Это программа которая рисует трёхмерную сцену на экране так, как её бы увидели вы. Конечно, не совсем так, но некоторые рейтрейсеры умеют рисовать очень правдоподобные картинки, например как в "Аватаре".

      Идея рейтрейсера очень простая и в этой статье я раcскажу как устроен этот алгоритм и даже напишу его на JavaScript. Картинки и пример прилагаются.

      Читать дальше →
    • Как работают алгоритмы сортировки

        Иногда для понимания того, как работает та или иная вещь, лучше один раз увидеть, чем сто раз услышать.

        Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



        Все это бегает и сортируется прямо на ваших глазах!

        Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».
      • WTF is a SuperColumn? Введение в модель данных Cassandra

        • Перевод
        Это перевод статьи, датированной 1м сентября 2009 года, следует это учесть при прочтении. — прим. пер.

        В последний месяц или два команда инженеров Digg потратила совсем немного времени на изучение, тестирование и окончательное внедрение Cassandra в продакшен. Это был очень веcёлый проект, но до того, как веселье началось, нам пришлось потратить какое-то время на выяснение того, что же представляет собой модель данных Cassandra… фраза «WTF is a «super column»» («что за фигня этот суперстолбец?») была произнесена не один раз.

        Если вы работали ранее с РСУБД (это касается почти всех), вы вероятно будете немного обескуражены некоторыми названиями при изучении модели данных Cassandra. Мне и моей команде в Digg потребовалось несколько дней обсуждений, прежде чем мы «врубились». Пару недель назад в списке рассылки разработчиков шёл процесс bikeshed-а на тему полностью новой схемы именования для разрешения неразберихи. На всём протяжении дискуссии я думал: «может, если будет несколько нормальных примеров, люди не будут так смущены названиями». Так, это моя попытка объяснения модели данных Cassandra; она предназначена для того, чтобы вы ознакомились, но не уходили в дебри, и, надеюсь, это поможет прояснить некоторые вещи.

        Читать дальше →
      • Компиляция. 1: лексер

          Меня всегда завораживало таинство рождения программой программы. К сожалению, российские вузы уделяют мало внимания сей интереснейшей теме. Рассчитываю написать серию постов, в которых поэтапно создадим маленький работоспособный компилятор.

          Первые посты серии уже подготовлены, и бета-тестировались в одном маленьком и наглухо закрытом сообществе. Тем не менее, я буду продолжать их править с учётом пожеланий почтенной хабрапублики.

          Далее в посте:

          1. С какой стати писать компиляторы?
          2. Общий план
          3. Анализ текста
          4. Практический пример
          5. Как это работает?
          Читать дальше →
        • Компиляция. 2: грамматики

            В предыдущем посте было много кода и, по некоторым мнениям, недостаточно объяснений. Будем чередовать: в этот раз будет много теории, а до практики почти не дойдёт.

            Далее в посте:

            1. Магазинный автомат
            2. Формальные грамматики
            3. LR-парсинг
            Читать дальше →
          • Компиляция. 4: игрушечный ЯП

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

              Чтобы неполноценность нашего языка была понятна уже из названия, назовём его JSkrip.

              Далее в посте


              1. Синтаксис
              2. Грамматика
              3. Парсер
              4. Синтаксическое дерево
              5. Pretty-printing

              Читать дальше →
            • Компиляция. 5: нисходящий разбор

                До сих пор занимались восходящим синтаксическим разбором. Какие ещё есть варианты?
                Отложим бизона в сторону, и вернёмся к теории.

                Далее в посте:

                1. Идея
                2. Воплощение
                3. Холивар
                4. Бэктрекинг
                Читать дальше →
              • Компиляция. 6: промежуточный код

                  Первый этап — разбор синтаксиса нашего джей-скрипа — пройден; подбираемся к генерации кода.

                  Начнём с генерации п-кода (промежуточного переносимого псевдокода) — нечто вроде «абстрактного машинного языка». Его выбирают так, чтобы
                  • его было легко генерировать;
                  • его было легко обрабатывать.
                  Обработка п-кода — это, как правило, его переработка в исполнимый машинно-зависимый код. Тем не менее, можно ограничиться лишь генерацией п-кода, и объявить его готовой скомпилированной программой. Запуск такой программы будет, по сути, интерпретацией п-кода. У этого подхода всё больше и больше сторонников; так что и мы для начала ограничимся компиляцией в п-код.

                  Далее в посте:

                  1. Выбор кода
                  2. Компиляция
                  3. Выполнение
                  4. Backpatching
                  Читать дальше →
                • Компиляция. 7: назначение регистров

                    File names are infinite in length, where infinity is set to 255 characters.
                    --Peter Collinson: The Unix File System

                    Итак, у нас есть программа на п-коде, и в её распоряжении неограниченное количество регистров (т.е. 255). Число регистров у реального процессора куда меньше (предположим, четыре). Что будем делать?

                    Далее в посте:

                    1. Разбор п-кода
                    2. Время жизни
                    3. Реализация
                    4. Простые оптимизации
                    5. Расщепление версий
                    6. Работа с памятью
                    7. Что получилось?
                    Читать дальше →
                  • Компиляция. 3: бизон

                      Это единственный пост в серии, в центре внимания которого — старообрядный сишный бизон, так надоевший некоторым. Тем, кто пишет не на Си, пост всё равно должен быть интересен, потому что похожие по принципу работы генераторы LR-парсеров существуют для очень многих языков. Тех же, кто идеологически не приемлет LR-парсеры, мне сегодня привлечь нечем.

                      Далее в посте:

                      1. Компиляция грамматики
                      2. Двухступенчатый парсер
                      3. Что у него внутри?
                      4. Конфликты в грамматике
                      5. Как это работает?
                      Читать дальше →