Комбинаторные (монадические) парсеры достаточно хорошо известны (wikibooks). Они представляют из себя библиотеку маленьких парсеров, которые распознают простые элементы грамматики, и способы объединять несколько парсеров в один (комбинировать — от сюда и название). Монадические они потому что один из способов комбинирования, порождения парсера остатка текста на основе результата разбора начала, удовлетворяет условиям, накладываемым на математический объект «монада». В языке Haskell это позволяет воспользоваться мощным сервисом, предоставляемым языком и библиотеками. В других языках название «монадические» можно смело игнорировать — это не будет мешать их реализации и использованию, включая упомянутую выше операцию «bind».

Проще всего комбинаторные парсеры реализуются в языках с поддержкой замыканий, но можно воспользоваться и классическим ООП (пример описан Rebecca Parsons в книге Мартина Фаулера «Предметно-ориентированные языки»).
К преимуществам комбинаторных парсеров относится простота использования (запись на языке программирования практически не отличается от обычного описания грамматики), независимость от препроцессора (как yacc/bison, happy или ocamlyacc), возможность реализовать некоторые элементы, плохо укладывающиеся в контекстно-свободную грамматику, прямо на языке программирования общего назначения.

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

Наследование

Персер конкретного языка состоит из множества более специализированных парсеров, ссылающихся друг на друга. В этом отношении парсеры напоминают методы некого объекта. Возникает желание порождать парсеры новых версий языков, подменяя отдельные подпарсеры (как это делается в паттерне проектирования «шаблонный метод» из ООП). Для экспериментов с этим подходом (а так же в порядке изучения очередного языка) я выбрал язык Julia — динамически-типизированном с особым подходом к наследованию (подобному CLOS из Common Lisp и R).
В отличие от обычных комбинаторных парсеров, подход с наследованием является экспериментальным (хотя в некотором виде поддерживается библиотекой макросов OCaml и языком Perl6). Пока он порождает не очень читабельный код. Исходный код доступен на Github.

Думаю, многим, также, как и мне, книга «Getting Started with LLVM Core Libraries» покажется интересной. Это первая книга, посвященная целиком и полностью LLVM. В основном, как следует из названия, ориентирована на новичков, которые только обратили свое внимание на LLVM, но уже имеют опыт программирования на C++.

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

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

Уважаемые читатели! Хочу поделиться с вами своим open-source проектом, над которым я работаю в своё свободное время уже достаточно давно, TeaVM. TeaVM представляет собой транслятор из байткода Java в JavaScript. Существует несколько попыток создать JVM на JavaScript, одна из самых удачных — Doppio. Однако, кроме академической, никакой ценности они не представляют, так как скорость интерпретации байт-кода оставляет желать лучшего. Более того, для интерпретации байткода необходимо как минимум загрузить этот байткод в браузер, а это вырождается в загрузку десятков мегабайт class-файлов.

В отличие от них, TeaVM не интерпретирует байткод, а генерирует JavaScript, который выполняет ровно то, что делал бы байткод, будь он запущен в реальной JVM. Проще говоря, TeaVM декомпилирует байткод Java, но не обратно в Java, а в JavaScript. Разумеется, всё это верно до определённых пределов. Во-первых, в JavaScript попросту отсутствуют некоторые вещи, привычные Java-разработчикам, такие как потоки, полноценная поддержка Юникода (например, поддержка классов символов, регулярные выражения), блокирующий ввод-вывод. Во-вторых, это обусловлено требованиями, которые я предъявлял к компилятору. Например, в TeaVM очень ограничена поддержка reflection. Это следствие одного из преимуществ TeaVM — сравнительно небольшой размер генерируемого файла. Нет, TeaVM не генерирует минимально возможный JavaScript, однако и не станет генерировать огромные многомегабайтные скрипты на каждый чих. Reflection делает невозможным какой-либо статический анализ, поэтому было принято решение от него отказаться.

Прежде чем я продолжу, я хочу для начала показать, на что способен TeaVM. Во-первых, он способен в реальном времени симулировать физику. Во-вторых, он ещё способен по этой физике рисовать красивые картинки в Canvas. Можно увидеть, что JavaScript-файлы сравнительно небольшие. Кстати, обсчёт физики я сам не реализовывал, я всего лишь взял имеющуюся библиотеку JBox2D.

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

Хотя на самом-то деле, если вспомнить историю Си, всё достаточно очевидно и, главное, логично. А все жалобы людей, «обжёгшихся» на неопределённом поведении для людей не забывших что такое Си и зачем он вообще существует звучат примерно как: «я тут гвозди бензопилой забивал… забивал и забивал, всё было хорошо, а потом я дёрнул за ручку и у неё коготки как забегают, задёргаются, мне руку оттяпало и полноги… ну кто так строит?».

Люди, которые знают что такое бензопила пытаются, конечно, объяснить, что за если за эту рукоятку дёрнуть, то так, в общем-то, и должно быть, но люди, считающие, что у них у руках такой себе молоток говорят «мимо» них, и, в результате, все остаются при своих.

Отличные новости ждут пользователей gcc при переходе на версию 4.9.0 – новые оптимизации с использованием неопределенного поведения могут «сломать» (на самом деле — доломать) существующий код, который, например, сравнивает с нулем указатели, ранее переданные в memmove() и ряд других функций стандартной библиотеки.

Например, утверждается, что в таком коде:

int wtf( int* to, int* from, size_t count ) {
    memmove( to, from, count );
    if( from != 0 )
        return *from;
    return 0;
}

новый gcc может удалить сравнение указателя с нулем и в результате вызов wtf( 0, 0, 0 ) будет приводить к разыменованию нулевого указателя (и аварийному завершению программы).

Да, да. Вы не ослышались. В этот раз статья «наоборот». Не мы проверяем какой-то проект, а проверили наш анализатор с помощью другого инструмента. На самом деле, подобное делали мы и раньше. Например, проверяли PVS-Studio с помощью Cppcheck, с помощью анализатора, встроенного в Visual Studio, смотрели на предупреждения Intel C++. Но раньше не было повода написать статью. Ничего интересного не находилось. А вот Clang смог заинтересовать своими диагностическими сообщениями.

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

В процессе подготовки очередного релиз-кандидата в ядре Linux 3.16 выяснилось совершенно непредсказуемое поведение функции балансировки нагрузки в Linux 3.16-rc6. В списке рассылки для разработчиков ядра двое авторов прислали сообщения о разных багах, хотя у них могла быть общая природа.

Линус Торвальдс внимательно разобрался в вопросе и ёмко ответил одному из сообщивших о баге: «Ok, я посмотрел на генерацию кода, и твой компилятор — чистое и полное дерьмо».

В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные #pragma. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

В условии цикла мы ошиблись на единицу, поставив <= вместо <. В итоге exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() может сделать всё что угодно — в том числе, вернуть true! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table() до

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Такие оптимизации иногда застают программистов врасплох.

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

В качестве реализуемого языка возьмем Brainfuck. Он прост в реализации, что отлично подходит для изучения данной темы, но сначала предоставлю вам свою реализацию.

JBrainfuck — оптимизирующий интерпретатор и компилятор Brainfuck под Java VM. Благодаря JIT обладает высокой производительностью.

• Лицензия: MIT
• Адрес проекта: https://github.com/SystemXFiles/jbrainfuck/
• Платформы: Linux, Windows, MacOS и везде, где есть Java.

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

Статья демонстрирует технику создания парсеров с использованием наследования грамматик. Наследование позволяет описывать новые грамматики на основе уже существующих путем добавления новых правил или переопределения унаследованных, что существенно упрощает реализацию новых парсеров. Изменения в базовой грамматике автоматически становятся доступными во всех порожденных грамматиках. Основная область применения такой техники — поддержка нескольких диалектов или версий языков.

«Инициация в программирование» (1997 году, на 286-х), вторые деньги, заработанные в школе за написание программ на информатике для двоечников (первые деньги были за решение задач по физике), призовое место на краевой олимпиаде по программированию (хотя принимали программы только на Паскале и Сях, я раздобыл BASIC-компилятор и вооружившись речью про дискриминацию, загружал exe-шники, сделанные на Бэйсике. Прокатило). Первые программы по шифрованию, поворот картинки на 90 градусов… Все это было на Бэйсике (а друзья даже писали музыку и 3д-тетрис).

Недавно на Хабре промелькнул перевод «50 лет Бейсику!» и я решил поисследовать историю создания Бэйсиков.
Из 318 версий Бэйсиков я коснусь не больше 10.

1964

В 1964 два профессора Дартмутского колледжа создали BASIC как инструмент, с помощью которого студенты-непрограммисты могли самостоятельно создавать компьютерные программы для решения собственных задач.

Джон Кемени, учился у Ричарда Феймана и Алонзо Чёрча (разработчик λ-исчисления), водил знакомство с фон Нейманом и консультировал Эйнштейна по математическим вопросам.

Томас Курц, учился у Джона Тьюки (автора слов «software» и «bit»).

Оба награждены медалями «Пионер компьютерной техники».

Первоначально Бейсик был реализован на мейнфрейме GE-265 с поддержкой множества терминалов.
Вопреки распространённому убеждению, в момент своего появления это был компилируемый язык.

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

Как я уже говорил ранее, у продуктов Intel большое количество различных типов лицензий. Для крупных компаний, университетов, и других организаций, в которых разработкой могут заниматься относительно большое количество инженеров, предлагается вариант с использованием клиент-серверной конфигурации и floating лицензии. Это самые «жирные» лицензии, как по функционалу, так и по цене. Из своего личного опыта знаю, что «поднять» сервер и заставить всё работать как нужно – не так уж и просто. Поэтому я решил собрать в данном посте все тонкости, с которыми мне приходилось сталкиваться самому.

Наконец, стартовала бета программа для Intel Software Development Tools. На подходе новые версии всех средств, которые предлагает Intel для разработчиков. Давайте разберёмся, что интересного принесёт нам следующий релиз компилятора.

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

Go — язык, компилируемый в нативный код, а посему, очевидно, должен быть быстрым. Однако, к сожалению, на данный момент это далеко не всегда соответствует действительности.
В моём же случае, Go проиграл PHP (ну, на самом деле модулю PHP на C, однако результат всё равно удручающий). Если кратко, то при вычислении Whirlpool-хеша Go проигрывал в 3,5-7.5 раз!

Команда Visual Basic присоединяется к поздравлениям Дартмутского Колледжа и разработчикам по всему миру, чьи жизни затронул этот прекрасный язык, и хочет поздравить Dartmouth BASIC (и, конечно, всё семейство языков Бейсик) с пятидесятилетием!

В нашей команде управляемых языков программирования так много тех, кто начинал свой путь с того или иного диалекта Бейсика, что мы не могли не поностальгировать и не показать привязанность к нашим истокам. В честь 50-летия дедушки Бейсика мы представляем вам QuickVB.

QuickVB основан на платформе .NET-компиляторов Roslyn (доступна в виде Nuget-пакетов), которая была представлена на конференции BUILD в этом году. Чтобы начать работу, просто распакуйте архив QuickVB.zip (ссылка в конце поста) с проектом, затем соберите и запустите проект в Visual Studio 2013. Предварительные версии Roslyn ставить не надо, менеджер пакетов Nuget сам скачает все необходимые зависимости.

Запустив QuickVB, вы увидите среду которая немного похожа на QuickBasic.

Уважаемые коллеги,

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

А под катом я расскажу, о том, как работают современные IDE. И как проект, над которым я сейчас работаю, может помочь вывести индустрию разработки веб-редакторов на новый уровень.

Якуб Елинек (Jakub Jelinek) от имени всех разработчиков свободных компиляторов GNU Compiler Collection из Фонда свободного ПО официально объявил о выпуске новой версии GCC 4.9.0.

«Один год и один месяц прошли с момента выпуска последней мажорной версии GNU Compiler Collection, — пишет Елинек, — так что пришло время объявить о новом основном релизе. GCC 4.9.0 несёт в себе важные новые функции, недоступные в GCC 4.8.x или предыдущих версиях GCC».

Среди самого главного можно отметить поддержку OpenMP 4.0, последней версии спецификаций программирования для многоядерных процессоров. Кстати говоря, в LLVM/Clang вообще отсутствует поддержка хоть какой-нибудь версии OpenMP.