Pull to refresh
28
0
Paul Popoff @ppopoff

Lead software engineer

Send message

Решение задачи о 8 ферзях на трёх уровнях Scala — программа, типы, метапрограмма

Level of difficulty Medium
Reading time 10 min
Views 2K

В заметке Ричарда Тауэрса (Richard Towers) Typescripting the technical interview (есть перевод на Хабре: Руны и лёд: техническое собеседование по TypeScript) по ходу повествования была решена классическая задача расстановки 8 ферзей на шахматной доске. Для решения использовалась система типов TypeScript. Мне захотелось посмотреть, как эта задача будет выглядеть на Scala. Т.к. Scala 3 помимо развитой системы типов предлагает превосходную поддержку метапрограммирования, то здесь мы рассмотрим не только решение на типах, но и мета-программное решение.

Читать дальше →
Total votes 13: ↑13 and ↓0 +13
Comments 4

Пешком по тайлам

Reading time 6 min
Views 24K


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

Ни один из известных нам сервисов не строил маршрут из точки А до точки Б там, где нет тропинок и тротуаров, зато полно заборов и домов причудливых очертаний.

2ГИС решил эту проблему. Мы научились строить маршруты для пешеходов по растеризованной карте местности. Карта формально представляется графом с вершинами на регулярной решётке в местах, где пешеход может находиться физически.

Принято считать, что такой способ строить маршруты неприемлем, потому что съедает много ресурсов. Под катом — как мы с этим справились.
Читать дальше →
Total votes 65: ↑64 and ↓1 +63
Comments 26

Подделываем письма от крупнейших российских банков

Reading time 3 min
Views 41K
Однажды я просматривал электронную почту и наткнулся на спам от БинБанка. Это было особенно странно, так как мне предлагали не банковские услуги, а что-то на уровне «Доход 70000 рублей за день». Похоже, спамеры начали отправлять письма от имени разных компаний (вероятно, чтобы обходить какие-то фильтры). Если вам интересно почитать о подделке писем от крупнейших российских банков и полном игнорировании проблем со стороны службы безопасности, то добро пожаловать под кат.


Достаточно простой пример поддельного письма
Читать дальше →
Total votes 68: ↑63 and ↓5 +58
Comments 83

Классы типов в Scala (с небольшим обзором библиотеки cats)

Reading time 12 min
Views 18K

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

Читать дальше →
Total votes 21: ↑21 and ↓0 +21
Comments 12

Теплый и ламповый VPN

Reading time 9 min
Views 393K

Ничего не предвещало беды, как вдруг в 2 часа ночи раздался телефонный звонок.

— Алло, милый! У меня youtube не работает!
— Прекрасно, иди спать!
— Нууу! Там новая серия вышла!
— Завтра всё сделаю!
— Ну Заяя, нуууу!
— Ладно! Ладно! Сейчас.


Из этого поста вы узнаете ответы на следующие вопросы:
Как спасти свою милую от стресса в 2 часа ночи? Как вернуть доступ к youtube.com, если ваш провайдер его заблокировал? Как быстро поднять VPN и настроить клиентские устройства (Android, Windows, Debian, dd-wrt) для работу с ним? Как безопасно серфить интернет на открытых точках доступа? Как заработать карму в глазах своей возлюбленной? Если вам это интересно, добро пожаловать под кат!
Читать дальше →
Total votes 188: ↑169 and ↓19 +150
Comments 157

Строго типизированное представление неполных данных

Reading time 8 min
Views 7.6K
В предыдущей статье «Конструирование типов» была описана идея, как можно сконструировать типы, похожие на классы. Это даёт возможность отделить хранимые данные от метаинформации и сделать акцент на представлении самих свойств сущностей. Однако описанный подход оказывается довольно сложным из-за использования типа HList. В ходе развития этого подхода пришло понимание, что для многих практических задач линейная упорядоченная последовательность свойств, как и полнота набора свойств, не является обязательной. Если ослабить это требование, то конструируемые типы значительно упрощаются и становятся весьма удобны для использования.

В обновлённом варианте библиотеки synapse-frames исключительно просто описываются иерархические структуры данных и представляются любые подмножества таких структур.

Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Comments 2

Два мира виртуальных машин

Reading time 18 min
Views 38K
Виртуальный. В отличие от большинства модных компьютерных словечек, это понятие обычно соответствует своему словарному определению в тех случаях, когда речь идёт об аппаратуре или программах. Словарь «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» оно стало сочетаться со множеством других слов. Недавно я осознал, что термин «виртуальная машина» (ВМ) на самом деле используется для обозначения двух хоть и связанных, но различных сущностей. В этой статье я расскажу о двух классах: языковые и системные виртуальные машины. Я покажу сходства и различия между ними, их назначение, классификацию, общие и частные черты в их практической реализации.


Читать дальше →
Total votes 31: ↑30 and ↓1 +29
Comments 5

Обзор LLVM

Reading time 13 min
Views 84K
LLVM (Low Level Virtual Machine) — это универсальная система анализа, трансформации и оптимизации программ или, как её называют разработчики, «compiler infrastucture».

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, и на каком уровне придётся работать, давайте разберёмся,
что из себя представляет LLVM IR.
Total votes 52: ↑51 and ↓1 +50
Comments 25

Сегодняшний мир — это amd64, armv7 и aarch64. Всё остальное мертво, Джим

Reading time 3 min
Views 76K
Вашему вниманию предлагается перевод прощального письма Миода Валлата, разработчика OpenBSD в течение 15+ лет, покинувшего проект неделю назад. Письмо, изначально адресованное лично некоему Джиму, рассказывает историю о том, куда порой приводят благие намерения, и вызвало резонанс среди пользователей Reddit и HackerNews. Учтите — высказанное мнение субъективно, и, по словам самого автора, "вы имеете право с ним не согласиться".

Сегодняшний мир — это amd64 (по-другому x64, или x86-64), armv7 и, в скором будущем, aarch64 (64-битный ARMv8). Всё остальное мертво, Джим. Никто не вкладывает достаточно денег и мыслительного труда в прочие архитектуры. В действительности, лишь небольшая часть людей в курсе существования остальной части экосистемы (mips, power8, ...), и все равно никому нет до них дела.

Поддержка устаревшей платформы на плаву — это весело, поскольку это напоминает тебе о 90-ых, когда существовал большой выбор «железных» платформ, с приблизительно одинаковым соотношением цены/мощности. В конце концов, дешевые PC убили практически всю конкуренцию, а рынок смартфонов дал ARM нездоровую долю рынка в мире встраиваемых систем.

Затем, спустя некоторое время, веселье подходит к концу, поскольку никто не пишет код, держа в уме твою платформу, — ведь она не считается достаточно мощной, а современные компиляторы больше ее не поддерживают (или они генерируют для нее нерабочий код, что на деле еще хуже). У твоей платформы есть аппаратные границы в несколько сотен MB физической памяти? Тебе не удастся запустить на ней веб-браузер или даже программу для просмотра PDF. Кто-нибудь все еще запускает testsuite из последней версии gcc на твоей платформе? Нет? Прости, чувак, но вот тебе «никель» (5 центов), сходи купи себе уже компьютер получше
Читать дальше →
Total votes 73: ↑69 and ↓4 +65
Comments 128

Полвека «универсальным машинным языкам» (1966—2016): прошлое, настоящее, будущее

Reading time 27 min
Views 19K
КДПВ

Прошлое


Повествование можно начать с 1962 г., когда в Кембриджском университете началась работа над CPL («Cambridge Programming Language») — «усовершенствованным вариантом» ALGOL-60. К работе над языком подключился аспирант Мартин Ричардс; главной сложностью в реализации нового ЯП ему показалась необходимость ручного портирования компилятора для разных компьютерных платформ. В частности, когда кембриджский EDSAC-2 заменили на Atlas-2, разработчики CPL потратили много времени на портирование своего компилятора для новой платформы.

Диссертация Мартина была посвящена «само-компилирующемуся» CPL: разработанный Мартином компилятор был написан на сильно упрощённом варианте CPL, компилятор которого несложно было написать на тогдашнем макроассемблере. Перенос CPL на новую платформу теперь можно было выполнить в два шага:
  1. Вручную пишем компилятор «упрощённого CPL»;
  2. Компилируем им компилятор «полного CPL».

На этом Мартин не остановился, и разработал BCPL — систему для разработки переносимых компиляторов. Компилятор BCPL генерировал псевдокод, названный Мартином «OCODE».
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 поступает точно так же.)

Исходный код на BCPL:
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
      }
    }
}
В более новых версиях OCODE добавилась поддержка чисел с плавающей точкой (соответственно, набор поддерживаемых опкодов почти удвоился), а также удалили опкод ENDFOR — вместо него генерируется пара LE JT.

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

Компилятор BCPL(1) поставлялся в виде OCODE, и чтобы перенести его на новую платформу, нужно было:
  1. Вручную написать интерпретатор псевдокода(2) (на любом языке, хоть на Бейсике);
  2. Адаптировать кодогенератор,(3) написанный на BCPL, для своей платформы;
  3. Запустить под интерпретатором (2) компилятор BCPL (1), скормить ему кодогенератор (3), и получить на выходе исполнимый файл кодогенератора(4);
    • Интерпретатор (2) нам с этого момента больше не нужен.
  4. Прогнать через кодогенератор (4) псевдокод компилятора (1), и получить на выходе исполнимый файл компилятора.


Такой подход означал, что для переноса компилятора на новую платформу требуется лишь самый минимум низкоуровневого программирования; и действительно, реализация BCPL была завершена к 1967 г. — раньше, чем была завершена реализация CPL, начатая на несколько лет раньше!

Достоинства BCPL применительно к системному программированию вдохновили Кена Томпсона на создание языка Би, а тот — коллегу Кена, Денниса Ритчи, на создание Си. Именно из BCPL пошла традиция обозначать {фигурными скобками} блоки программы, и именно на BCPL была написана первая программа «Hello, World!».
GET "libhdr"

LET start() = VALOF
{ writef("Hello*n")
  RESULTIS 0
}
Более важная нам причина, по которой BCPL вошёл в историю: OCODE — первая универсальная «архитектура набора команд» (ISA), т.е. «виртуальная машина», не привязанная ни к какой конкретной аппаратной платформе с её особенностями. BCPL, таким образом — первый язык программирования, соответствующий парадигме «Write once, run anywhere» (WORA): программу на BCPL можно распространять в скомпилированном виде, и её можно будет запустить на любой платформе, для которой существует OCODE-кодогенератор.
Читать дальше →
Total votes 53: ↑51 and ↓2 +49
Comments 45

Создание плагина для Intellij IDEA. Заметки и мелкие советы

Reading time 4 min
Views 23K
Полгода назад или около того я загорелся-таки идей написать свой плагин для Intellij IDEA. Согласно задумке, он должен был считать, сколько времени разработчик потратил на проект (всего, за день, за сеанс) и отображать результат на диаграмме. Никакой магии, но такая функция здорово помогла бы мне рассчитывать время работы.


И что из этого вышло?
Total votes 16: ↑16 and ↓0 +16
Comments 17

Макросы в Scala, Евгений Бурмако. Скринкаст, слайды и фото со scalaby#6

Reading time 2 min
Views 3.1K

На 6-ой встрече коммьюнити #scalaby выступал Евгений Бурмако — докторант EPFL, и член команды Мартина Одерски, занимающейся разработкой Scala. Темой презенатции был «Проект Кеплер» — пропозал по добавлению макросов в Scala, над которым Евгений работает в течение последнего месяца.

Фото и скринкаст под катом
Total votes 15: ↑14 and ↓1 +13
Comments 2

Обработка ошибок в Rust

Reading time 32 min
Views 39K

Как и многие языки программирования, Rust призывает разработчика определенным способом обрабатывать ошибки. Вообще, существует два общих подхода обработки ошибок: с помощью исключений и через возвращаемые значения. И Rust предпочитает возвращаемые значения.



В этой статье мы намерены подробно изложить работу с ошибками в Rust. Более того, мы попробуем раз за разом погружаться в обработку ошибок с различных сторон, так что под конец у вас будет уверенное практическое представление о том, как все это сходится воедино.



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


Читать дальше →
Total votes 37: ↑36 and ↓1 +35
Comments 73

Information

Rating
Does not participate
Date of birth
Registered
Activity