В Lua ООП нет. И оно, в общем-то и не нужно: удобной модульности и функций первого класса достаточно для реализации многих вещей. На этом можно было бы и закончить, но пост не про это. В данном случае я распишу работу с метатаблицами, где в качестве примера шаг за шагом будет реализовываться системка по работе с классами в несколько таком python-стиле. Для понимания нужен хотя бы основной базис языка: таблицы, upvalues.

Господа, рад представить вам свой новый проект — Refactoring.guru.

Сайт представляет собой каталог запахов грязного кода и, собственно, самих приёмов рефакторинга. В двух словах — это как книга Мартина Фаулера, но лучше. А именно:

• Весь контент доступен на русском языке. Я старался делать описания как можно более живыми, чтобы избавиться от чувства унылости и скуки, которое возникает при чтении любой переводной книги о рефакторинге.
• Все примеры подаются на Java и PHP. Другие языки обязательно будут добавляться со временем, но я пока затрудняюсь решить, каким будет следующий, можете предлагать в комментах.
• Всё везде перелинковано. Рефакторинги сгруппированы по предназначениям и связям.

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

Как видите, есть еще громадное поле для работы, как говорится, «если вам не стыдно за первую версию продукта — вы отрелизились слишком поздно». Тем не менее, я надеюсь, что кому-то сайт будет интересен уже сейчас.

Буду рад всем отзывам и пожеланиям! (а также лайкам и твитам)

Статья рассчитана на людей, которые знакомятся со средой Visual Studio и пытаются компилировать в ней свои Си++-проекты. В незнакомой среде всё кажется странным и непонятным. Особенно новичков раздражает файл stdafx.h, из-за которого возникают странные ошибки во время компиляции. Очень часто всё заканчивается тем, что новичок долгое время везде старательно отключает Precompiled Headers. Чтобы помочь людям разобраться что к чему, и была написана эта статья.

Недавно по работе собирал своего рода лекцию по веб-безопасности, ознакомился с известным рейтингом уявзимостей OWASP 2013 года, но с удивлением обнаружил, что корректной инфы на русском языке крайне мало, или её практически нет.

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

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

• SQL Injection
• Некорректная аутентификация и управление сессией
• Межсайтовый скриптинг (XSS)
• Небезопасные прямые ссылки на объекты
• Небезопасная конфигурация
• Утечка чувствительных данных
• Отсутствие контроля доступа к функциональному уровню
• Подделка межсайтовых запросов (CSRF)
• Использование компонентов с известными уязвимостями
• Невалидированные редиректы
• Кликджекинг
• Фишинг
• Include

Комбинаторика в старших классах школы, как правило, ограничивается текстовыми задачами, в которых нужно применить одну из трёх известных формул — для числа сочетаний, перестановок или размещений. В институтских курсах по дискретной математике рассказывают и о более сложных комбинаторных объектах — скобочных последовательностях, деревьях, графах… При этом, как правило, ставят задачу вычислить количество объектов данного типа для некоторого параметра n, например количество деревьев на n вершинах. Узнав количество объектов для фиксированного n, можно задаться и более сложным вопросом: как все эти объекты за разумное время предъявить? Алгоритмы, решающие подобного рода задачи, называются алгоритмами комбинаторной генерации. Таким алгоритмам, например, посвящена первая глава четвёртого тома «Искусства программирования» Дональда Кнута. Кнут очень подробно рассматривает алгоритмы генерации всех кортежей, разбиений числа, деревьев и других структур. Придумать какой-нибудь алгоритм, работающий умеренно быстро, для каждой из этих задач несложно, но с дальнейшей оптимизацией могут возникнуть серьёзные проблемы.

В процессе написания магистерской диссертации, защищённой в Академическом университете, мне потребовалось изучить и применить один из алгоритмов комбинаторной генерации, подходящий для особого класса задач. Это генерация структур, на которых дополнительно введено некоторое отношение эквивалентности. Чтобы было понятно, о чём идёт речь, я приведу простой пример. Давайте попробуем сгенерировать все триангуляции шестиугольника. Получится что-нибудь такое:



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

Предисловие

Проснулся я сегодня с мыслью, что огромное количество инструкций по настройке NAT советуют использовать строку вида:

iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

Многие понимают проблемы этой конструкции, и советуют добавлять:

iptables -A FORWARD -i ppp0 -o eth1 -m state --state ESTABLISHED,RELATED -j ACCEPT

Но, зачастую, забывают задать таблице FORWARD действие DROP по умолчанию, или добавить правило REJECT в конец таблицы.
На первый взгляд, вроде бы, все кажется нормальным. Однако, это далеко не так. Дело в том, что если не запретить маршрутизировать трафик из WAN-порта в WAN-порт, кто-нибудь из вашей WAN-сети (предположим, что провайдер садит весь подъезд в одну /24) может маршрутизировать трафик через вас, просто прописав ваш IP в качестве шлюза. Все современные SOHO роутеры это учитывают, а вот неопытный администратор, который делает роутер под обычным linux, может не знать или забыть об этом. В подсети моего провайдера таких роутеров не оказалось, и мой план по захвату мира провалился. Однако, статья совсем не об этом.

Магические двоеточия

Как вы, может быть, знаете, многие современные программы и сервисы биндятся на IP :: (два двоеточия), а не на 0.0.0.0, как было раньше. IPv6 адрес :: значит то же самое, что и IPv4 0.0.0.0, т.е. «слушаем все интерфейсы». Многие считают, что если программа слушает ::, то этот сокет может принимать только IPv6-соединения, однако это далеко не так.
В IPv6 есть так называемое отображение IPv4-адресов в IPv6 диапазон. Если программа слушает сокет ::, а к ней обращаются из IPv4-адреса 1.2.3.4, то программа получит соединение с адреса ::ffff:1.2.3.4. Этого можно избежать, сделав:

sysctl -w net.ipv6.bindv6only=1

Но это нужно далеко не всегда, т.к. обычно удобно, что программа слушает один сокет, а получать соединения может по двум протоколам сразу. Практически во всех дистрибутивах, IPv6-сокеты ведут себя именно так, т.е. bindv6only=0.

В новой версии Java 8 наконец-то появились долгожданные лямбда-выражения. Возможно, это самая важная новая возможность последней версии; они позволяют писать быстрее и делают код более ясным, а также открывают дверь в мир функционального программирования. В этой статье я расскажу, как это работает.

Java задумывалась как объектно-ориентированный язык в 90-е годы, когда объектно-ориентированное программирование было главной парадигмой в разработке приложений. Задолго до этого было объектно-ориентированное программирование, были функциональные языки программирования, такие, как Lisp и Scheme, но их преимущества не были оценены за пределами академической среды. В последнее время функциональное программирование сильно выросло в значимости, потому что оно хорошо подходит для параллельного программирования и программирования, основанного на событиях («reactive»). Это не значит, что объектная ориентированность – плохо. Наоборот, вместо этого, выигрышная стратегия – смешивать объектно-ориентированное программирование и функциональное. Это имеет смысл, даже если вам не нужна параллельность. Например, библиотеки коллекций могут получить мощное API, если язык имеет удобный синтаксис для функциональных выражений.

Главным улучшением в Java 8 является добавление поддержки функциональных программных конструкций к его объектно-ориентированной основе.

Частенько читаю Хабр и заметил что в последнее время появились Дайджесты новостей по многим тематикам, таким как веб-разработка на php, разработка на Python, мобильные приложения, но не встретил ни одного подборки по популярному сейчас направлению, а именно анализу данных и big data.

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

Кого заинтересовала данная тема прошу подкат. А также жду замечаний, пожеланий и дополнений, буду очень рад обратной связи.

Привет!
Не знал, как поточнее назвать статью, но хотелось бы разобрать одну маленькую задачку, которая звучит следующим образом:

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

Например, так ActionScript пытается вызвать функцию test с тремя аргументами str, false, 1.0(соответственно типы аргументов: String, Boolean, Number):

<invoke name="test" returntype="xml"><arguments><string>str</string><false/><number>1.0</number></arguments></invoke>

Хотелось бы, чтобы со стороны C++ была вызвана соответствующая функция:

void test_handler(const std::wstring& str, bool flag, double n);

Под катом — реализация с использованием нового стандарта и, для сравнения, реализация с использованием старого стандарта(и капельки boost-а).

Привет, коллеги!

Последние пару недель я трудился над интереснейшим (с моей точки зрения) занятием, которое представляло собой создание Hadoop-as-a-Service решения для приватного облака нашей компании. В первую очередь мне было интересно, что же за зверь Hadoop, почему так часто сейчас слышны сочетания слов Big Data и Hadoop. Для меня знакомство с Hadoop началось с чистого листа. Конечно же, я не являлся и не явлюясь Big Data специалистом, посему вдавался в суть на столько, на сколько необходимо было для понимания процессов в разрезе автоматизации развертывания кластера.

Привет, Хабрапосетители!


Продолжаю свою «развеселую» серию статей, посвященных знакомству с Hadoop и автоматизации развертывания кластера.

В первой части я вкратце описал, что нужно было достичь, какую архитектуру кластера построить и что представляет собой Hadoop-кластер с точки зрения архитектуры. Также, я рассмотрел, наверное, самую простую часть кластера — Clients, которая отвечает за постановку задач, предоставление данных для вычислений и получение результатов.

При построении многослойных («enterprise») систем часто оказывается, что создаются ValueObject'ы (или case class'ы), в которых хранится информация о каком-либо экземпляре сущности, обрабатываемом системой. Например, класс

case class Person(name: String, address: Address)

Такой способ представления данных в системе обладает как положительными свойствами:

• строго типизированный доступ к данным,
• возможность привязки метаинформации к свойствам с помощью аннотаций,

так и некоторыми недостатками:

• если сущностей много, то таких классов также становится довольно много, а их обработка требует много однотипного кода (copy-paste);
• потребности отдельных слоёв системы в метаинформации могут быть представлены аннотациями к свойствам этого объекта, но возможности аннотаций ограничены и требуют использования reflection'а;
• если требуется представить данные не обо всех свойствах объекта сразу, то созданные классы использовать затруднительно;
• затруднительно также представить изменение значения свойства (delta).

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

• возможность описывать отдельные свойства сущностей (с указанием типа данных в этом свойстве и любой метаинформации, необходимой приложению, в форме, подходящей именно для этого приложения);
• возможность оперировать со свойствами экземпляров строго типизированным образом (с проверкой типов на этапе компиляции);
• представлять частичную/неполную информацию о значениях свойств экземпляра сущности, пользуясь объявленными свойствами;
• создавать тип объекта, содержащего частичную информацию о свойствах экземпляра сущности. И использовать этот тип наравне с другими типами (классами, примитивными типами и др.).

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

Этот конспект-памятка о том, как добиться относительно высокой безопасности приложений в вебе, а также предостеречь новичков от банальных ошибок. Список составлялся без учета языка программирования, поэтому подходит для всех. А теперь позвольте, я немного побуду КО.


Итак, каким должен быть безопасный сайт?

Определение

Параллельное программирование сложно. При использовании систем с общей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к общему ресурсу (памяти). Для этого используются:

• блокировки (mutex);
• алгоритмы без блокировки (lockless, lock-free);
• транзакционная память.

Транзакционная память — технология синхронизации конкурентных потоков. Она упрощает параллельное программирование, выделяя группы инструкций в атомарные транзакции. Конкурентные потоки работают параллельно¹, пока не начинают модифицировать один и тот же участок памяти. К примеру, операции добавления узлов в красно-чёрное дерево (анимация в заголовке) способны работать параллельно в нескольких потоках.

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

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

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

Как вы, наверное, догадались, эта статья посвящена lock-free очередям.

Очереди бывают разные. Они могут различаться по числу писателей (producer) и читателей (consumer) – single/multi producer — single/multi consumer, 4 варианта, — они могут быть ограниченными (bounded, на основе предраспределенного буфера) и неограниченными, на основе списка (unbounded), с поддержкой приоритетов или без, lock-free, wait-free или lock-based, со строгим соблюдением FIFO (fair) и не очень (unfair) и т.д. Подробно типы очередей описаны в этой и этой статьях Дмитрия Вьюкова. Чем более специализированы требования к очереди, тем, как правило, более эффективным оказывается её алгоритм. В данной статье я рассмотрю самый общий вариант очередей — multi-producer/multi-consumer unbounded concurrent queue без поддержки приоритетов.

Эта статья содержит те ловушки программирования, в которые я попадал сам, продолжаю попадать и возможно никогда не прекращу, а также те, в которых я находил своих товарищей.

Однако я верю в то, что их можно избежать, если знать в какие ловушки можно попасть и как из них выбираться. Возможно эта вера — очередная ловушка.

Всем прикольно пообсуждать «всё новое хреновое», и последние пару лет мы увлечённо обсуждали и пробовали NoSQL/NewSQL на сервере и Angular/Knockout/Ember на клиенте. Но эти тренды, похоже, уже на излёте. Отличный момент, чтобы присесть и поразмыслить, что же дальше. Как сказал M. Andreessen, «software is eating the world». В то же время, mobile/web apps едят обычные приложения. Поэтому особенно интересно прикинуть, а куда же всё катится в мире мобильных и веб-приложений? Ведь они, получается, едят вообще всех. Я считаю, что следующей Большой Темой будет синхронизация данных, и вот почему.

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



Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

Рассмотрим более конкретный пример: мы хотим иметь программу, которая в двудольном графе находит паросочетание максимального размера вместе с доказательством его максимальности.



Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

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



Как можно доказать правильность результата? Если система совместна, то доказательством совместности может стать решение этой системы (нетрудно доказать, что если у такой системы есть решение, то есть и рациональное решение, т.е. его можно записать). А как доказать, что система несовместна? Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.

В этой статье мы поговорим о том, нужны ли доказательства, или проверка доказательства всегда не проще, чем самостоятельное решение задачи. (В примере про максимальное паросочетание мы не доказали, что не существует алгоритма, решающего задачу за то же время, сколько занимает проверка доказательства.) Если мы не ограничиваем размер доказательства, то окажется, что доказательства нужны, а если будем требовать, чтобы доказательства были короткими, то вопрос о нужности доказательств эквивалентен важнейшему открытому вопросу о равенстве классов P и NP. Потом мы поговорим об интерактивных доказательствах (доказательства в диалоге). Обсудим криптографические доказательства, которые не разглашают лишнюю информацию, кроме верности доказываемого утверждения. И закончим обсуждением вероятностно проверяемых доказательств и знаменитой PCP-теоремы, которая используется для доказательства трудности приближения оптимизационных задач.

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