В заметке Ричарда Тауэрса (Richard Towers) Typescripting the technical interview (есть перевод на Хабре: Руны и лёд: техническое собеседование по TypeScript) по ходу повествования была решена классическая задача расстановки 8 ферзей на шахматной доске. Для решения использовалась система типов TypeScript. Мне захотелось посмотреть, как эта задача будет выглядеть на Scala. Т.к. Scala 3 помимо развитой системы типов предлагает превосходную поддержку метапрограммирования, то здесь мы рассмотрим не только решение на типах, но и мета-программное решение.
Software engineering manager
Пешком по тайлам
Для автомобилистов проблему незнакомых улиц давно решили навигаторами. Но даже автомобилисты ходят пешком. Если магазин через дорогу, то мы встаём и идём. Трудности появляются, если предстоит пройти пятьсот метров по незнакомой улице и два-три раза свернуть.
Ни один из известных нам сервисов не строил маршрут из точки А до точки Б там, где нет тропинок и тротуаров, зато полно заборов и домов причудливых очертаний.
2ГИС решил эту проблему. Мы научились строить маршруты для пешеходов по растеризованной карте местности. Карта формально представляется графом с вершинами на регулярной решётке в местах, где пешеход может находиться физически.
Принято считать, что такой способ строить маршруты неприемлем, потому что съедает много ресурсов. Под катом — как мы с этим справились.
Классы типов в Scala (с небольшим обзором библиотеки cats)
При слове "полиморфизм" сразу вспоминается объектно-ориентированное программирование, в котором полиморфизм является одним из столпов (Полиморфизм для начинающих). (Причём, по-видимому, более важным, чем другие столпы.) Оказывается, что можно достичь сходного эффекта и другим путём, который в ряде случаев оказывается более предпочтительным. Например, с помощью классов типов можно приписать новые возможности уже существующим типам, у которых нельзя изменить предка, или, используя тип данных с несовместимыми классами, "решить" проблему множественного наследования.
Теплый и ламповый VPN
Ничего не предвещало беды, как вдруг в 2 часа ночи раздался телефонный звонок.
— Алло, милый! У меня youtube не работает!
— Прекрасно, иди спать!
— Нууу! Там новая серия вышла!
— Завтра всё сделаю!
— Ну Заяя, нуууу!
— Ладно! Ладно! Сейчас.
…
Из этого поста вы узнаете ответы на следующие вопросы:
Как спасти свою милую от стресса в 2 часа ночи? Как вернуть доступ к youtube.com, если ваш провайдер его заблокировал? Как быстро поднять VPN и настроить клиентские устройства (Android, Windows, Debian, dd-wrt) для работу с ним? Как безопасно серфить интернет на открытых точках доступа? Как заработать карму в глазах своей возлюбленной? Если вам это интересно, добро пожаловать под кат!
Строго типизированное представление неполных данных
В обновлённом варианте библиотеки synapse-frames исключительно просто описываются иерархические структуры данных и представляются любые подмножества таких структур.
Два мира виртуальных машин
Виртуальный. В отличие от большинства модных компьютерных словечек, это понятие обычно соответствует своему словарному определению в тех случаях, когда речь идёт об аппаратуре или программах. Словарь «Random House College Dictionary» определяет «virtual» как «проявляющий свойства и эффекты чего-либо, но не являющийся таковым на самом деле».Последние несколько лет в начале каждого семестра я даю студентам определения основных терминов, используемых в моём курсе: симуляция, эмуляция и виртуализация. И каждый раз я говорю, чтобы мои слова не принимали за стопроцентную правду. Дело в том, что в одних областях технического знания эти термины зачастую трактуются противоположно тому, что принято использовать в других. Нелёгкое это дело — давать определения.
ОригиналVirtual. Unlike most computer buzzwords, this one usually holds true to its dictionary definition when it refers to hardware or software. The Random House College Dictionary defines «virtual» as «being such in force or effect, though not actually or expressly such.» [4]
Видимо, эту проблему заметил не только я. В своей книге Software and System Development using Virtual Platforms, вышедшей в прошлом году, мои коллеги Jakob Engblom и Daniel Aarno в первой главе вводят понятия simulation и emulation и отмечают неоднозначность их толкования в областях разработки программного обеспечения и проектирования аппаратуры.
С беспорядком в толковании этих двух терминов я для себя разобрался и вроде бы смирился. Осталось ещё одно понятие, уже более десяти (на самом деле пятидесяти) лет не теряющее популярности — это «виртуализация». За время своего бытия в категории «buzzword» оно стало сочетаться со множеством других слов. Недавно я осознал, что термин «виртуальная машина» (ВМ) на самом деле используется для обозначения двух хоть и связанных, но различных сущностей. В этой статье я расскажу о двух классах: языковые и системные виртуальные машины. Я покажу сходства и различия между ними, их назначение, классификацию, общие и частные черты в их практической реализации.
Обзор LLVM
LLVM — не просто очередной академический проект. Его история началась в 2000 году в Университете Иллинойса, а теперь LLVM используют такие гиганты индустрии как Apple и Adobe. В частности, на LLVM основана подсистема OpenGL в MacOS X 10.5, а iPhone SDK использует GCC с бэкэндом на LLVM. Apple является одним из основных спонсоров проекта, а вдохновитель LLVM — Крис Латтнер — теперь работает в Apple.
В основе LLVM лежит промежуточное представление кода (intermediate representation, IR), над которым можно производить трансформации во время компиляции, компоновки (linking) и выполнения. Из этого представления генерируется оптимизированный машинный код для целого ряда платформ, как статически, так и динамически (JIT-компиляция). LLVM поддерживает генерацию кода для x86, x86-64, ARM, PowerPC, SPARC, MIPS, IA-64, Alpha.
LLVM написана на C++ и портирована на большинство *nix-систем и Windows. Система имеет модульную структуру и может расширяться дополнительными алгоритмами трансформации (compiler passes) и кодогенераторами для новых аппаратных платформ. Пользовательский фронтенд, как правило, линкуется с LLVM и использует C++ API для генерации кода и его преобразований. Однако LLVM включает в себя и standalone утилиты.
Для тех, кто не без оснований считает C++ не лучшим языком для написания компиляторов, с недавних пор в LLVM включена обертка API для OCaml.
Чтобы понять, что можно сделать с помощью LLVM, и на каком уровне придётся работать, давайте разберёмся,
Сегодняшний мир — это amd64, armv7 и aarch64. Всё остальное мертво, Джим
Сегодняшний мир — это amd64 (по-другому x64, или x86-64), armv7 и, в скором будущем, aarch64 (64-битный ARMv8). Всё остальное мертво, Джим. Никто не вкладывает достаточно денег и мыслительного труда в прочие архитектуры. В действительности, лишь небольшая часть людей в курсе существования остальной части экосистемы (mips, power8, ...), и все равно никому нет до них дела.
Поддержка устаревшей платформы на плаву — это весело, поскольку это напоминает тебе о 90-ых, когда существовал большой выбор «железных» платформ, с приблизительно одинаковым соотношением цены/мощности. В конце концов, дешевые PC убили практически всю конкуренцию, а рынок смартфонов дал ARM нездоровую долю рынка в мире встраиваемых систем.
Затем, спустя некоторое время, веселье подходит к концу, поскольку никто не пишет код, держа в уме твою платформу, — ведь она не считается достаточно мощной, а современные компиляторы больше ее не поддерживают (или они генерируют для нее нерабочий код, что на деле еще хуже). У твоей платформы есть аппаратные границы в несколько сотен MB физической памяти? Тебе не удастся запустить на ней веб-браузер или даже программу для просмотра PDF. Кто-нибудь все еще запускает testsuite из последней версии gcc на твоей платформе? Нет? Прости, чувак, но вот тебе «никель» (5 центов), сходи купи себе уже компьютер получше…
Полвека «универсальным машинным языкам» (1966—2016): прошлое, настоящее, будущее
Прошлое
Повествование можно начать с 1962 г., когда в Кембриджском университете началась работа над CPL («Cambridge Programming Language») — «усовершенствованным вариантом» ALGOL-60. К работе над языком подключился аспирант Мартин Ричардс; главной сложностью в реализации нового ЯП ему показалась необходимость ручного портирования компилятора для разных компьютерных платформ. В частности, когда кембриджский EDSAC-2 заменили на Atlas-2, разработчики CPL потратили много времени на портирование своего компилятора для новой платформы.
Диссертация Мартина была посвящена «само-компилирующемуся» CPL: разработанный Мартином компилятор был написан на сильно упрощённом варианте CPL, компилятор которого несложно было написать на тогдашнем макроассемблере. Перенос CPL на новую платформу теперь можно было выполнить в два шага:
- Вручную пишем компилятор «упрощённого CPL»;
- Компилируем им компилятор «полного CPL».
На этом Мартин не остановился, и разработал BCPL — систему для разработки переносимых компиляторов. Компилятор BCPL генерировал псевдокод, названный Мартином «OCODE».
OCODE | «расшифровка» («procode») | |
---|---|---|
94 5 L1 83 73 69 86 69 95 4 42 0 42 0 40 2 14 83 42 0 42 1 40 2 14 83 42 2 40 3 42 1 15 92 85 L5 90 L6 42 1 40 4 40 2 14 83 40 4 42 1 14 80 4 90 5 40 4 40 5 88 L6 91 4 42 2 40 3 42 1 15 92 85 L7 90 L8 40 4 40 2 14 8 87 L9 40 4 42 2 11 92 85 L11 90 L10 42 0 40 6 40 2 14 83 40 4 40 6 14 80 6 90 L11 40 6 40 3 22 86 L10 91 6 90 L9 40 4 42 1 14 80 4 90 L7 40 4 40 5 88 L8 91 4 97 103 0 |
ENTRY 5 L1 'S' 'I' 'E' 'V' 'E' SAVE 4 LN 0 LN 0 LP 2 PLUS STIND LN 0 LN 1 LP 2 PLUS STIND LN 2 LP 3 LN 1 MINUS STORE JUMP L5 LAB L6 LN 1 LP 4 LP 2 PLUS STIND LP 4 LN 1 PLUS SP 4 LAB L5 LP 4 LP 5 ENDFOR L6 STACK 4 LN 2 LP 3 LN 1 MINUS STORE JUMP L7 LAB L8 LP 4 LP 2 PLUS RV JF L9 LP 4 LN 2 MULT STORE JUMP L11 LAB L10 LN 0 LP 6 LP 2 PLUS STIND LP 4 LP 6 PLUS SP 6 LAB L11 LP 6 LP 3 LS JT L10 STACK 6 LAB L9 LP 4 LN 1 PLUS SP 4 LAB L7 LP 4 LP 5 ENDFOR L8 STACK 4 RTRN ENDPROC 0 |
; стековый кадр (два параметра и две локальные переменные) ; поместить на стек число 0 ; поместить ещё один 0, прибавить к нему 2-ой элемент стека ; записать в массив на вершине стека значение под ним ; всё то же самое для 1-ого элемента массива ; поместить на стек число 2 ; вычесть единицу из значения 3-его элемента стека ; записать результат в локальную переменную ; перейти к метке L5 ; объявление метки L6 ; взять 4-ый элемент стека, записать в массив по этому индексу 1 ; прибавить к 4-ому элементу стека 1, записать результат обратно ; L5: перейти к метке L6, если 4-ый элемент стека <= 5-ому ; объявление, что на стеке сейчас четыре элемента ; вычесть единицу из значения 3-его элемента стека ; перейти к метке L7 ; L8: сложить 4-ый и 2-ой элементы стека ; прочитать значение по этому адресу; если это 0, перейти к L9 ; умножить 4-ый элемент на два ; перейти к метке L11 ; объявление метки L10 ; взять 6-ой элемент стека, записать в массив по этому индексу 0 ; прибавить к 6-ому элементу стека 4-ый, записать рез-т обратно ; объявление метки L11 ; перейти к метке L10, если 7-ой элемент стека меньше 4-ого ; на стеке сейчас шесть элементов; объявление метки L9 ; прибавить к 4-ому элементу стека 1, записать результат обратно ; L10: перейти к L8, если 4-ый элемент стека <= 5-ому ; на стеке четыре элемента; окончание процедуры |
Исходный код на BCPL:
В более новых версиях OCODE добавилась поддержка чисел с плавающей точкой (соответственно, набор поддерживаемых опкодов почти удвоился), а также удалили опкодLET sieve(workvec, vecsize) BE { workvec!0 := 0 workvec!1 := 0 FOR i = 2 TO vecsize-1 DO workvec!i := 1 FOR i = 2 TO vecsize-1 DO IF workvec!i DO { LET j = 2 * i WHILE j < vecsize DO { workvec!j := 0 j := j + i } } }
ENDFOR
— вместо него генерируется пара LE JT
.Среди «универсальных машинных языков» OCODE уникален тем, что метки в нём определяются специальными инструкциями — т.е. для интерпретации программы её нужно сначала всю загрузить в память, и найти в ней метки.
Компилятор BCPL(1) поставлялся в виде OCODE, и чтобы перенести его на новую платформу, нужно было:
- Вручную написать интерпретатор псевдокода(2) (на любом языке, хоть на Бейсике);
- Адаптировать кодогенератор,(3) написанный на BCPL, для своей платформы;
- Запустить под интерпретатором (2) компилятор BCPL (1), скормить ему кодогенератор (3), и получить на выходе исполнимый файл кодогенератора(4);
- Интерпретатор (2) нам с этого момента больше не нужен.
- Прогнать через кодогенератор (4) псевдокод компилятора (1), и получить на выходе исполнимый файл компилятора.
Такой подход означал, что для переноса компилятора на новую платформу требуется лишь самый минимум низкоуровневого программирования; и действительно, реализация BCPL была завершена к 1967 г. — раньше, чем была завершена реализация CPL, начатая на несколько лет раньше!
Достоинства BCPL применительно к системному программированию вдохновили Кена Томпсона на создание языка Би, а тот — коллегу Кена, Денниса Ритчи, на создание Си. Именно из BCPL пошла традиция обозначать
{
фигурными скобками}
блоки программы, и именно на BCPL была написана первая программа «Hello, World!».Более важная нам причина, по которой BCPL вошёл в историю: OCODE — первая универсальная «архитектура набора команд» (ISA), т.е. «виртуальная машина», не привязанная ни к какой конкретной аппаратной платформе с её особенностями. BCPL, таким образом — первый язык программирования, соответствующий парадигме «Write once, run anywhere» (WORA): программу на BCPL можно распространять в скомпилированном виде, и её можно будет запустить на любой платформе, для которой существует OCODE-кодогенератор.GET "libhdr" LET start() = VALOF { writef("Hello*n") RESULTIS 0 }
Создание плагина для Intellij IDEA. Заметки и мелкие советы
Макросы в Scala, Евгений Бурмако. Скринкаст, слайды и фото со scalaby#6
На 6-ой встрече коммьюнити #scalaby выступал Евгений Бурмако — докторант EPFL, и член команды Мартина Одерски, занимающейся разработкой Scala. Темой презенатции был «Проект Кеплер» — пропозал по добавлению макросов в Scala, над которым Евгений работает в течение последнего месяца.
Обработка ошибок в Rust
Как и многие языки программирования, Rust призывает разработчика определенным способом обрабатывать ошибки. Вообще, существует два общих подхода обработки ошибок: с помощью исключений и через возвращаемые значения. И Rust предпочитает возвращаемые значения.
В этой статье мы намерены подробно изложить работу с ошибками в Rust. Более того, мы попробуем раз за разом погружаться в обработку ошибок с различных сторон, так что под конец у вас будет уверенное практическое представление о том, как все это сходится воедино.
В наивной реализации обработка ошибок в Rust может выглядеть многословной и раздражающей. Мы рассмотрим основные камни преткновения, а также продемонстрируем, как сделать обработку ошибок лаконичной и удобной, пользуясь стандартной библиотекой.
Information
- Rating
- Does not participate
- Date of birth
- Registered
- Activity