вторник, 16 апреля 2013 г.

HackDay#25. Проект Virtualens. Отчет.

Черт возьми, мы победили!

Ну а теперь подробнее как это начиналось, как продолжалось и чем закончилось.

С чего все начиналось.

Началось все в пятницу, пятого апреля с прочтения поста на хабре про то, что мол вот будет хакатон в Нижнем Новгороде, и что там будет интеловский конкурс. Подобные события в Нижнем Новгороде бывают не столь часто, к тому же этой весной похоже так и не будет Application Developers Days, которого я очень жду, так что я загорелся идеей поучаствовать в этом хакатоне. 

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

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

В понедельник вечером, я скачал и установил PerC SDK, и начал играться запуская примеры пока без спец. камеры. И обнаружил, что из за особенностей реализации (либо технологии распознавания лиц вообще) одна из идей отпадает, ибо становится не реализуемой на дОлжном уровне. Это была идея динамического формирования изображения в зависимости от положения наблюдателя. Правильная реализация подобной идеи была еще в 2007 году, и основывалсь не на распознавании лиц. Посмотреть как это выглядело можно посмотреть на ютубе:
Проблема в том, что из за угла обзора камеры, и нюансов реализации распознавания лиц, алгоритм в PerC SDK периодически теряет лицо, что приводит к не желательным эффектам (подергивания, лаги (то есть задержки)) - иллюзия "окна за которым другой мир" полностью разваливается. И это было хорошо видно потом, на менторской сессии на хакатоне во время демонстрации технологии самими сотрудниками Intel.
(а еще реализацию этой идеи было бы сложно демонстрировать людям - оно работает только для одного наблюдателя, а остальные видят фигню)

В результате стало ясно, что выбрать идею связанную с PerC SDK не пощупав камеру просто не получится - малейший нюанс может сделать любую идею не реализуемой, причем не только за 48 часов, но и вообще в принципе. В списке идей были идеи проектов не только связанные с этим конкурсом, но все же работа с этой камерой, работа с технологией дополненной реальности, это было то, что я всегда хотел попробовать, так что у конкурсных идей был приоритет.

Поэтому во вторник я написал организаторам письмо, где изложил вышесказанное - чтобы определиться с идеей, нужна камера, а камеру дают после оглашения идеи (уже на хакатоне) - замкнутый круг! Организаторы (а конкретно Михаил) среагировали мгновенно, в переписку была включена Светлана из Intel, и в среду ко мне уже приехала камера. Стало возможно посмотреть на что она способна, и на что способен PerC SDK.

А еще в среду я познакомился с Надей - я искал по знакомым (в том числе и на работе) кто еще хочет пойти, выяснил что Надя собирается идти, и написал ей письмо.

Вообще, к тому моменту у меня в фаворе была идея вовсе не Virtualens'a, а идея таки 3D сканера и сервиса обмена отсканированными моделями. Было даже название придумано - Let's clone. Меня крайне забавляла сама возможность сделать "пиратскую" копию скажем фигурки из шахматного набора. То есть берем предмет, показываем его камере, и в компьютере у нас получается моделька предмета, а потом рраз, и распечатали её на 3Д-принтере. Я прекрасно понимал свои возможности (да и возможности команды, если таковая набралась бы), и знал что мы не сможем за 48 часов научиться сканировать все что угодно. Предполагалось, что будем сканировать спереди и сзади зеркально-симметричный предмет, а затем с помощью жестов из этих половинок лепить готовую модель. Соответственно камеру я проверял в первую очередь на её возможности в приложении для этой идеи.

В ходе экспериментов, я узнал о камере довольно много - понял что там нет защиты от внешней засветки (солнце, лампы дневного света), что она ловит блики от собственного же ИК-фонарика, что подсветка у нее не равномерная, и для 3Д сканера, вообще говоря, неплохо бы построить будет мат. модель этой самой подсветки, чтобы компенсировать вносимые ей искажения. Ну и шум, да. На расстоянии сантиметров в 25 фильтрованный силами SDK сигнал выдавал шум порядка 2-3 миллиметров (то есть между двумя кадрами у одного и того же пикселя разница в глубине может быть 3 миллиметра легко), на не фильтрованном сигнале же... Если воткнуть свой дли-и-инный фильтр (скажем на 1000 кадров), то оно все равно плавает, но уже можно получить точнее 1 миллиметра. А еще оно по разному работает на разных материалах, поэтому вещь которую будем сканировать желательно чтобы была однотонной, не бликующей, зеркально симметричной.

Но несмотря на все это, в четверг я все еще рассматривал 3D-сканер как основную идею, к которой и готовился (искал опенсорс-библиотеки которые могли бы пригодиться, смотрел на "фреймворки" для 3D графики, чтобы было на чем быстро написать визуализацию отсканированной модели. остановился, кстати, на http://www.openframeworks.cc/. Посмотрел код, код примеров - мне понравилось). 

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

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

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

Переломный момент - рождение Virtualens.

В ночь я четверга на пятницу я внезапно обнаружил, что 3D сканирование камерой - это баян. С 2011 года баян! Ну, то есть на рынке уже есть штук 5 классных продуктов, которые делают то, о чем я мог подумать только в самых смелых мечтах. Используют они для этого кинект. И стоят относительно дешево - 150 баксов где-то, и это при наличии бесплатной версии ознакомительной! По сравнению с этим то, что мы изобразим за 48 часов будет смотреться просто жалко, настолько жалко, что даже не вторично, а еще хуже. То есть самое разумное что мы могли бы сделать - скачать одну из бесплатных версий одного продукта, который умеет данные доставать не только с камеры живьем, но и из файла. И каким-то образом расковырять формат этого файла, научиться генерировать такие файлы. Таким образом добавив в этот продукт сбоку кривую поддержку Интеловско-Креативовской камеры. Это выглядело бы уже не так плохо, это выглядело бы просто вторично. И это меня все равно не устраивало.

Так что в пятницу я обсудил ситуацию с Надей, и мы решили выбрать идею виртуального объектива для веб-камеры. Ну, то есть взять идею, которую я не прорабатывал практически с момента записи её в список. Проект не казался мне вах каким полезным. Ну, то есть с точки зрения реализации, математики и программирования - да, интересно и классно. Но с точки зрения применимости на практике - казалось сомнительным. Собственно вот что буквально было записано в пункте "риски/недостатки проекта":
Риски/недостатки проекта: Проект технодемоподобный. То есть его конечно возможно вывести на уровень полезного приложения (особенно если прикрутить туда функцию заливки получившегося на ютуб), но это все равно некая натяжка. Также из за пониженного разрешения IR-сенсора, могут возникнуть проблемы на переходах от фона к переднему плану (края будут "жеваными").
В плюсах же проекта значилось лишь то, что он в каком-то виде скорее всего реализуем за 48 часов.

Вообще, сама идея этого проекта мне пришла где-то с месяц назад, когда я развлекался с алгоритмами обратной свертки (deconvolution) - это алгоритмы которые позволяют "провернуть фарш назад", то есть получить из расфокусированной фотки нормально сфокусированную. Естественно я сразу подумал - "хм, а как на счет обратной задачи? есть фотка везде четкая, а мы хотим динамический фокус, с соответствующим размытием по глубине". Я тогда помнится еще поигрался с двумя камерами чтобы получить карту глубин на основе параллакса, наткнулся на какие-то неоднозначности восстановления такой карты, и забил.

Соответственно в пятницу же (за несколько часов до начала, да!) я спешно придумываю название для проекта (Virtualens) и регистрирую его. Надя регистрируется на сайте хакотона. В результате и проект и Надя оказались похоже последними из того что там было зарегистрировано до начала :-)

Хакатон.

День первый.

Закончив с регистрацией всего и вся, схватив рюкзак (я на работу с рюкзаком и пришел, чтобы не тратить потом время на то, чтобы его из дома забрать) я поехал добираться до места проведения хакотона. Улица Ларина, на которой и стоит этот самый бизнес-инкубатор, где все проводилось, довольно не благоустроена. Тротуары вдоль дороги? Не, не слышали! Зато я добрался за полчаса до начала регистрации участников, соответственно у меня было время отчистить ботинки в туалете :-)

Но улица Ларина не самое страшное что меня ждало в начале мероприятия, самое страшное - ПИТЧИ! Это такая штука.. За 90 секунд надо рассказать кто мы, что за проект, зачем проект, кто нужен в команду. Рассказывать это должен тот, кто заявлял проект, так что похоже, что это был я. 90 секунд! Перед аудиторией! БЕЗ БУМАЖКИ! Тут одно из двух - или я не уложусь в тайминг, либо забуду все самое важное. Пришлось готовиться (кстати, я до сих пор не уверен что подготовка как-то мне помогла - учить что-то наизусть я никогда не умел. Выучить стрихотворение из двух четверостиший - всегда было для меня проблемой. А вот втечение 10-15ти минут, а то и часа, что-то рассказывать из того, что мне интересно - это я легко и без подготовки могу.). Написал текст. Начал репетировать. С секундомером. Вначале каждую часть по отдельности, потом все вместе. Так что когда пришла Надя и поздоровалась, я ответил ей бессмысленным взглядом и шевелящимися губами - я в очередной раз прогонял текст. С секундомером.

Пошли питчи. К счастью проекты шли в порядке регистрации. То есть мы были последними. Что позволяло немного тайминг завалить и за этого никто не убил бы скорее всего. Ну, может только немного покалечили бы. Я не знаю воспользовался я этим или нет - я не смотрел на отсчет времени что показывали на iPad'e. Ну, или смотрел, но не воспринимал совершенно, ибо не помню этого. Но по крайней мере мне было от этого спокойней.

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

Началось формирование команд, мы так никого к себе и не зазвали, но два парня дали нам, как оказалось, довольно ценный совет - забить на OpenGL/шейдеры, и писать все эффекты на CPU. Думаю это таки сэкономило нам время (из за того, что ни шейдеры ни OpenGL мы не умели), хотя и пришлось попотеть над оптимизацией.

А еще у Нади не было ноутбука на котором можно было бы разрабатывать под PerC SDK (там нужно не ниже Win7 систему иметь ну и проц аля i3..i7), так что пришлось просить ребят из Интела, чтобы что-нибудь ноутбукоподобное годное для PerC SDK. И они таки дали замечательный ультрабук фирмы Intel. Ну, то есть не самсунг, не делл какой-то там, а интел. Никогда раньше таких не видел. Вообще, сотрудники Intel'a на мероприятии в плане поддержки участников конкурса проявляли чудеса оперативности - и камеру вторую дали быстро, и, потом, на второй день, оперативно ответили на вопросы по API SDK. Молодцы. Все бы так.

Ну и пообщались с Николаем Долговым - тоже нашим сотрудником, у него была идея тревожной кнопки на смартфоне (http://hackday.ru/events/hackday-25/projects#project-399). У меня был некий скепсис по поводу эффективности подобной штуки, о чем я ему и сказал. Он отлично отбил подачу, и в общем то меня переубедил. Молодец.

В общем команды набрались, и все разошлись в поисках хороших мест. Надя нашла нам уголок, в первой же комнате, где мы и обитали все эти два дня. Разложили ноутбуки, набросали план работ и решили пока разъехаться по домам. Выспаться. Спокойно почитать доки. Это довольно логично было - 48 часов без сна это одно, а 60 часов - это уже другое (мы же встали в пятницу утром все таки), и эти несколько часов могут оказаться критичными на финише. Я доложился за час до чекпоинта Мише, и мы разъехались (а Николай остался кодить свою тревожную кнопку на андроиде).

Дома я еще поковырял код, и попробовал заснуть. Не знаю, по ощущениям я спал в ту ночь часа три - слишком был возбужден чтобы нормально спать. Зато я написал свой "hello world" на PerC SDK, на котором смог оценить сколько проходов по картинке мы можем сделать не снизив fps ниже 30. Это было важно. Картинка не только должна быть красивой, но и быстрой. Если у тебя красивая картинка на видео, но при этом 5 кадров в секунду... Это будут натуральные тормоза, это не естественно и народ это заметит. Иллюзия движения распадется как карточный домик.

День второй.

В субботу я приехал раньше Нади. Так что мы с Николаем успели позавтракать и обсудить что за ночь произошло. Он боролся с андроидом. И победил. Но на это ушла вся ночь.

А потом пришла Надя, позавтракала и мы начали реализовывать первый пункт нашего плана - нужно было написать блюр. Сильный не тормозящий блюр, размытие картинки на разрешении 640x480. Нужно было выжать 30 кадров в секунду и при этом иметь еще запас по мощности, ведь будет же еще обработка глубины. Надя читала папиры, а я ковырял код и иногда думал. А потом я вспомнил что я не только программист, но и бездельник, и ушел на утренний чекпоинт.

Чекпоинт это странно. Сидишь ты, кодишь, весь такой асоциальный, погруженный в код, в голове нет никаких слов (по крайней мере человеческих), только образы как оно там внутри кода все шевелится, ну то есть ты нормальный такой обычный программист. И тут бац. Надо идти на чекпоинт. А там люди. А там надо рассказывать про проект и про людей. И про то зачем этот проект обычным простым людям (не программистам!) будет нужен и интересен. Это шок. Это контрастный душ для мозга. Приходится резко переключать думалку на совершенно другой режим. И мне было стыдно что я тут а чекпоинте фигней какой-то страдаю, а там Надя в одиночку решает важные для проекта задачи. Но с другой стороны, за эти 3-4 чекпоинта что у нас были я как-то научился говорить на эти темы не приходя в сознание. Это потом здорово пригодилось на демонстрации в конце хакатона.

Вернулся с чекпоинта и мы быстро реализовали первый вариант, в лоб, по определению свертки. И получили... 3 fps! Это был кошмар. Пошли лихорадочно гуглить, на тему эффективных алгоритмов, и тут начал отваливаться интернет. Регулярно. Постоянно. Это было ужасно.

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

После сессии, было забавно - мы решили выпить кто кофе, кто чаю, сидим разговариваем, перевариваем остатки обеда и только что прослушанной лекции. И тут подходят господа из интела и спрашивают - а что это мы не работаем? ;-) А что мы не работаем? Мы ждем идей, вдохновения, ну или хотя бы вменяемого интернета. Ибо 3 fps это приговор.

Но сидя за чаем конечно что-либо высидеть сложно. так что мы допили чай и пошли дальше биться головой об тормоза. С интернетом плохо, так что пришлось думать. Думали, придумали как ускорить - реализовать через разностую схему. Теперь сложность алгоритма была не O(W*H*N^2), где W - ширина окна (640) H - высота (480) а N - диаметр размытия, а всего лишь O(W*H*N). Чтобы проверить насколько нам это поможет, реализовал "плоское" размытие - размытие только по горизонтали. Гадость конечно, но реализуется быстро, и оценка сложности та же, что у разностной схемы. Получили 9-10 fps. Это было хорошо. но не достаточно хорошо - надо было где-то взять еще ускорение раза в 4. Надя искала хитрые алгоритмы, которые дали бы O(W*H), а я думал что там в коде можно допилить/еще ускорить. 

И нашел. Я совершенно на всякий случай просто решил проверить, а что у нас будет в релизе. Особой надежды, что там будет что-то принципиально другое у меня не было, ибо обычно там разница в производительости процентов 20 бывает, ну 50. А тут... А тут ускорение в три раза! Черт, мы сразу получили искомые 30 fsp! Мораль команды поднялась, и я начал реализовывать разностную схему в коде. Поскольку хотелось еще скорости, чтобы потом свободно себя чувствовать при обработке данных по глубине, то Надя продолжила поиск идей по дальнейшему ускорению.

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

По возвращению с чекпоинта я засел за реализацию выделения областей которые нужно и которые не нужно размывать. Области выделить удалось довольно быстро, и мы еще до полуночи уже получили картинку с размытым задним планом, но тут всплыла проблема - между depth-координатами и координатами на цветной картинке нет взаимно однозначного отображения. Соответственно в изображении были дырки. Часть тех пикселов которые не должны размываться, размывались таки. На лице был виден шум. Более того, средствами API получить отображение из цветной картинки в depth вовсе невозможно. Пришлось лепить велосипед для такого отображения. Кроме того, на границах размытия вылезли баги в алгоритме размытия - были дикие черные контуры и тени там где не надо.

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

День третий.

За ночь я пофиксил большую часть багов, точнее не столько пофиксил, сколько свел их визуальный эффект к минимуму  Теперь картинка смотрелась более-менее прилично, но еще было над чем поработать.

После завтрака и утреннего чекпоинта, я продолжил улучшать картинку, а Надя занялась экспериментами с жестами. Её опыт работы с жестами затем здорово на демонстрации пригодился.

Да, кроме программерских радостей, у нас случилась новая напасть - нужно было вписать себя в расписание репетиций тренеровок к питчу/демофесту. Надо было придумать время так, чтобы к тому моменту и все было готово, и при этом было не слишком поздно, чтобы в случае чего еще было время поправить косяк. Записались на 15-15.

Потом к нам подходил ментор из Интела. Мы его попытали вопросами, он нам здорово помог с деталью API касательно реализацией жестов. Итого у нас таки к обеду было готово приложение генерирующее более-менее сносную картинку, управляемое интуитивными жестами.

Сходили на обед. Я стремительно начал превращаться в зомби - все же организму иногда нужно спать. Впрочем, я до того момента ни разу на хакатоне еще кофе не пил (да и чай почти не пил, пил в основном просто воду), так что на один, последний рывок у меня еще были резервы. Перед репетицией у меня дикий тупняк - не мог совершенно придумать текст речи. На репетиции кое-как что-то изобразил. Меня покритиковали. Спасибо! Я как-то постепенно пришел в себя, и к демофесту таки сочинил и текст вменяемый, и план демонстрации (который мы, впрочем, таки нарушили).

Ну и вот наконец сам демофест. Порядок выступлений не известен! Так, сказать, сюрприз будет. Во время демофеста выйти нельзя, а мне для выступления просто необходимо выпить кофе, иначе я улиточка, а то и просто слизень. Нужно, так сказать, включить турбобуст, а то ничего не выйдет. Но есть нюанс - кофе действует не бесконечно, и после окончания действия (минут 30-40 я полагаю) я окончательно превращусь в овощь. Я рискую и выпиваю чашку перед началом демофеста. И нам везет! Мы выступаем вторые!

Более-менее бодро рассказываю какую штуку мы сделали и зачем это все нужно, Надя синхронно все это демонстрирует, естественно по законам жанра вылезают сразу все глюки моего рендера, о чем меня потом из зала и спросили, можно ли это дело устранить в принципе. Отвечаю на вопросы... Меня спрашивают про команду, её опыт и так далее.. Надя! Мне до сих пор стыдно, что я забыл про тебя сказать когда рассказывал про свой опыт работы. Жутко стыдно! Но я там просто отключился. Я опять не помню секундомера, такое было ощущение, что кратковременная память сказала мне "бай-бай", обойдешься пока без меня, по крайней мере пока не выспишься.

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

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

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

И были наши соперники по конкурсу - Personal DJ. Они класные, креативные. Ребята, вы отлично выступили! Вы были точно лучше чем например вот этот товарищ занявший одно из первых мест в Intel® Perceptual Computing Challenge Phase 1:
В общем, респект вам.

Ну и были ребята с роботом - единственные железнячники на этом хакатоне. И было общение после демофеста в ожидании пока жюри там отсовещается. И было волнение, мы далеко не были уверены что у нас получится - все же программа сырая, баги в отрисовке на лицо, хотя идея, она да, у нас хорошая оказалась. Многообещающая.

И была радость от победы. Черт возьми, это здорово! Это здорово когда много работаешь и это приносит плоды. Как сказала Ася:  "иметь опыт победы - это самое главное в жизни, и ради этого стоит лезть под ток." (отсюда)

Что будет.

И это еще не конец. Будет еще много чего. Мы, я думаю, примем участие в Intel® Perceptual Computing Challenge Phase 2. Это будет много работы, но оно того стоит. У меня есть четкое представление что нужно и как сделать в программе, как должен выглядеть результат и как и где это будет использоваться. Нас еще ждет общение с ребятами из Skype. Возможно будет что-то еще. Все еще только начинается :-)

Большое спасибо организаторам мероприятия, всем менторам, было жутко интересно и очень полезно. Спасибо!

среда, 19 января 2011 г.

and then in C++

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

В Оберон (точнее в один из его диалектов), где, как известно нет исключений и подобных механизмов, предлагается ввести новую синтаксическую конструкцию :
Первый_этап;
IF первый этап удался THEN
  Второй_этап
AND второй этап удался THEN
  Третий_этап
AND третий этап удался THEN
  Завершающие действия
ELSE
  Задача не выполнена
END
 Соотвественно если нам нужно определить на каком этапе случилась ошибка, то пишется это так:
step := 1;
Первый_этап;
IF первый этап удался THEN
  step := 2;
  Второй этап;
AND второй этап удался THEN
  ...
ELSE
  Log.String("Ошибка на этапе "); Log.Int(step)
END
 Но это конечно трубует менять язык. Соответственно менять компилятор. Что не здорово, лень и вообще не факт что кто-то будет делать.

Однако в С++ мы иногда тоже не можем пользоваться исключениями. Ну, например если мы от них намерянно отказались (см. например Google C++ Style). Менять компилятор С++ тоже совсем не интересно, но это и не нужно. Всё вышеперечисленное легко реализуется средствами самого языка, при чем без шаблонов и прочего метапрограммирования.

Нам достаточно того, что в С++ есть оператор запятая (,) и есть ленивые вычисления. Соответственно концепт такой:
bool r = (
    A1, // первый этап
    A2,
    A3,
первый_этап_удался ) and (
    B1, // второй этап
    B2, 
    B3,
второй_этап_удался ) and (
    C1, // третий этап
    C2, 
    C3,
третий_этап_удался ) and (
    Z1, // завершаюшие действия
    Z2,
    Z3,
true ) or (
    ERR1, // Задача не выполнена
    ERR2, 
    ERR3,
false);
 Ну и, как обычно, рабочий пример:
#include <iostream>

bool zoo(int c)
{
    int z = c;
    int step = 1;
    
    bool r = (
        step = 1,
        z--,
        std::cout << "step 1: " << z << std::endl,
    z > 0 ) and (
        step = 2,
        z-- ,
        std::cout << "step 2: " << z << std::endl,
    z > 0 ) and (
        step = 3,
        z--,
        std::cout << "step 3: " << z << std::endl,
    z > 0 ) and (
        z = z*z,
        std::cout << "Ending... " << z << std::endl,
    true ) or (
        std::cout << "Error on step " << step << std::endl,
    false );
    
    return r;
}

int main() 
{
    zoo(4);
    zoo(3);
    zoo(2);
    zoo(1);
    zoo(0);
}
Соответственно результат запуска такой:
step 1: 3
step 2: 2
step 3: 1
Ending... 1

step 1: 2
step 2: 1
step 3: 0
Error on step 3

step 1: 1
step 2: 0
Error on step 2

step 1: 0
Error on step 1

step 1: -1
Error on step 1

пятница, 17 декабря 2010 г.

О математике.

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

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

По моему, очень точно сказано.
Источник: http://www.botik.ru/mail-archive/refal/0583.html

понедельник, 22 ноября 2010 г.

Online syntax highlighter

В процессе написания предыдущих постов долго мучался на тему раскраски и вообще приличного оформления исходников. В конце концов нашел удобный сервис для этого: http://tohtml.com

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

PS. Динамическую раскраску синтаксиса, посредством жабаскрипта, не люблю, ибо оно требует жабаскрипта в брaузере а также иногда неплохо так тормозит рендеринг страницы.

Floor через Trunc

Продолжаем наши игры с плавающими точками (начало тут).

Кто-то заметил, что ENTIER (floor) это такая королевская функция, функция всех функций, из из которой легко получаются все остальные. И что мол Вирт выбрал её именно поэтому, мол самый базисный базис.

Однако я позволил себе в этом несколько усомниться. И на то были причины. Во-первых Trunc (отбрасывание дробной части) давно и успешно применяется в Си, и никто по этому поводу не плачет, во-вторых Trunc явно проще, а следовательно, скорее всего, первичней, ну и наконец, в своем последнем творении -- Оберон-07 Вирт закопал таки EITHER и заменил его на Trunc (обозвав его почему-то словом FLOOR).

Посему я задался вопросом, а как бы мне получить из Trunc'a Floor? Попил чайку, и в результате получилась вот такая вот функция:
int Floor(float a)
{
int b = (int)a;
if (a>=0 || (a-b) == 0) return b;
else return b-1;
}
Причем она почему-то работает быстрее чем стандартная floorf. При чем, если включить sse инструкции то начинает работать ещё раза в два быстрее.

Итак, мы получили свой любимый Floor/ENTIER а дальше можем спокойно сделать с ним всё что угодно. Получать из него Ceil, Round и т.п.

Т.о. функция отбрасывающая дробную часть является таки базисной, основополагающей. И Вирт был прав когда отказался от ENTIER её пользу в Обероне-07. Также были правы создатели тёплых ламповых Сей. Правда они сделали это на десятилетия раньше Вирта. А те кто фанатеют от каждого решения Вирта в своих языках -- не правы. Он тоже может ошибаться.

воскресенье, 21 ноября 2010 г.

Оберон & real to integer

Для справки: Oberon, Oberon2 (в дальнейшем O2), ComponentPascal (CP), считается в определенных кругах (в прицнипе не без причин) эталоном базисности и простоты. Эдакий базис императивных языков. BlackBox component builder (в дальнейшем ЧорныйЯщик) -- самая популярная реализация оного Component Pascal'я особенно в постсоветском пространстве.

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

В процессе ковыряния oo2c и, заодно, сообщений о языках O2 и CP выяснил интересную вещь. Оказывается в O2 и CP НЕТ простого и быстрого способа конвертации real -> integer. Т.е. чтобы это выражалось в одну машинную инструкцию. Подобные преобразования в обероне-2 и CP (до оберона я пока не добрался) занимают примерно в ДВА раза больше времени нежели в иных языках. Ну и имеют другую, более сложную семантику. А также не отображается на прямую в одну sse инструкцию. Преобразование real->integer в Обероне2 и CP осуществляется посредством встроенной функции ENTIER.

ENTIER работает аналогично связке стандартной сишной функции floor + преобразование типов. т.е. ENTIER(x) = (int)floor(x); Чего-то более простого в арсенале оберонщика нет.

Вот такой вот код на Обероне-2 собранный oo2c:
MODULE T;
IMPORT Out, SYSTEM;
CONST
N = 10000;
PI = 3.1415;
VAR
r : LONGINT
I : LONGINT;
J : LONGINT;
BEGIN
I := N;
J := I;
WHILE I > 0 DO
WHILE J > 0 DO
r := ENTIER(PI*J*I);
DEC(J);
END;
DEC(I);
J := N;
END;
END T.
Отрабатывает за 3.4 секунды. (никаких оптимизаций).
Вот такой вот код на С++:
int main()
{
const float pi = 3.1415;
const int n = 10000;
int r = 0;

for (int i = n; i>0; i--)
for (int j = n; j>0; j--)
r = (int)(pi*i*j);
}
Отрабатывает за 1.6 секунды.
Если строчку r = (int)(pi*i*j); заменить на r = (int)floorf(pi*i*j); то будут те же самые 3.4 секунды. Да, оптимизация естественно отключена.

С готишным ЧорнымЯщиком вообще всё весело. Код:
MODULE Test;

IMPORT StdLog, Services;

CONST
N = 10000;
PI = 3.1415;

PROCEDURE Do*;
VAR t: LONGINT;
I : LONGINT;
J : LONGINT;
r : LONGINT;
BEGIN
t := Services.Ticks();
I := N;
J := I;

WHILE I > 0 DO
WHILE J > 0 DO
r := ENTIER(PI*J*I);
DEC(J);
END;
DEC(I);
J := N;
END;

t := Services.Ticks() - t;
StdLog.Int(SHORT(t))
END Do;

END Test.
Обычно функция Do отрабатывает где-то за 3.7-3.8 секунды. Однако иногда, ВНЕЗАПНО время подскакивает почти в два раза:
3759 3744 4992 3744 ...
3744 3759 3807 7441 3806 3775 4446 7800 3744 3744 3744
Да, система при этом ничем постороннем не загружена.

PS. В Обероне-07 всё это поправлено. Там ENTIER заменен на FLOOR, который не floor, а который простое отбрасывание дробной части, т.е. FLOOR(x) = (int)(x);

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

среда, 19 мая 2010 г.

Грамматика и её граф.

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

Кроме анализа исходников, в процессе анализируется и сама грамматика -- в ней ищутся классы нетерминалов. Для этого строится граф связей оных нетерминалов. И вот тут мы получаем побочный результат который может быть интересен в т.ч. и простому парню от программерской сохи -- визуальное представление оного графа грамматики реального ЯП:

(из графа удалены все терминалы)


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