суббота, 20 декабря 2008 г.

Prolog

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

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

Условие задачи: Сократ - человек. Все люди смертны.
Найти: Смертен ли Сократ?

Запишем условие в терминах языка пролога (со знака % начинаются комментарии):


% Сократ - человек
human(sokrat).
% Платон - тоже человек
human(platon).

% Чтобы некто был смертным, он должен быть человеком
mortal(Someone) :- human(Someone).

теперь спросим пролог систему, смертен ли Сократ:

?- mortal(sokrat).

Yes % да

?- mortal(stranger).

No % нет, поскольку пролог система не знает ничего о stranger и потому, не может ответить на вопрос

% Мы можем спросить какие смертные существа известны системе:
?- mortal(Who).

Who = platon ;

Who = sokrat

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

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

Собственно, хочу привести для примера решение на прологе задачи о расстановке на шахматной доске 8 ферзей, так чтоб они не били друг друга, основанное на приведенном в книге Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта (кстати, очень хорошая книга, рекомендую).


% будем искать решение как набор 8 координат вида X/Y каждого из ферзей
% при этом понятно, что поскольку все вертикали так или иначе будут заняты
% задача сводится к отысканию соответствующих Y - координат
getSolution(S):-
S=[1/_,2/_,3/_,4/_,5/_,6/_,7/_,8/_],
solution(S).

% доска 0x0 без ферзей очевидно является решением
solution([]).

% доска NxN является решением, если является решением её под-доска (N-1)*(N-1),
% а первый ферзь не бьет ферзей на этой под-доске.
solution([X/Y | Others]) :-
solution(Others),
member(Y, [1, 2, 3, 4, 5, 6, 7, 8]),
nokill(X/Y, Others).

% очевидно что ферзь с любыми координатами не бьет ферзей из пустого массива,
% поскольку просто некого бить
nokill(_, []).

% ферзь не бьет набор ферзей если он не бьет первого ферзя из набора
% и не бьет остальных ферзей набора
nokill(X/Y, [X1/Y1 | Others]) :-
Y =\= Y1, % на разных горизонталях
Y1-Y =\= X1-X, % на разных диагоналях
Y1-Y =\= X-X1,
nokill(X/Y, Others).

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

1 ?- getSolution(P).

P = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ;

P = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1] ;

P = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1] ;

P = [1/3, 2/6, 3/4, 4/2, 5/8, 6/5, 7/7, 8/1] ;

P = [1/5, 2/7, 3/1, 4/3, 5/8, 6/6, 7/4, 8/2] ;
...


Кстати, а как это будет выглядеть на вашем любимом языке программирования? =)

Кстати, тут можно посозерцать решение той же задачи на рефале, еще одном интересном языке функционального программирования, идейно перекликающимся с прологом, кстати, создатель которого - наш соотечественник Валентин Федорович Турчин (вики).


вторник, 2 декабря 2008 г.

Функциональный питон

На досуге пришла идея используя list comprehensions изобразить на питоне некое подобие функционального программирования.

И вот что получилось:


[ [[[[[
(
(
p('Multiplications:'),
doMult(4, 10),
l()
),
(
p(),
p('Fib:'),
[
(
p('%d->%d' % (i, fib(i)))
)
for i in range(1, 10)
]
),
(
p(),
p('Qsort:'),
p(qsort([2,1,4,-11,9]))
)
)

for doMult in [lambda I, J:
[
(
l() if j==1 else [],
p('%sx%s=%s' % (i, j, i * j))
)
for i in range(1, I)
for j in range(1, J)]
]]

for qsort in [lambda L:
[] if L==[]
else [
qsort([e for e in T if e<=H]) + [H] + qsort([e for e in T if e>H])
for H in [L[0]]
for T in [L[1:]]
][-1]
]]

for fib in [lambda n:
n if n<2 else fib(n-1) + fib(n-2)
]]

for l in [lambda:
p('-' * 10)
]]

for p in [lambda s='':
w(str(s)+'\n')
]]

for w in [
__import__('sys').stdout.write
]
]


Вывод:

Multiplications:
----------
1x1=1
1x2=2
1x3=3
1x4=4
1x5=5
1x6=6
1x7=7
1x8=8
1x9=9
----------
2x1=2
2x2=4
2x3=6
2x4=8
2x5=10
2x6=12
2x7=14
2x8=16
2x9=18
----------
3x1=3
3x2=6
3x3=9
3x4=12
3x5=15
3x6=18
3x7=21
3x8=24
3x9=27
----------

Fib:
1->1
2->1
3->2
4->3
5->5
6->8
7->13
8->21
9->34

Qsort:
[-11, 1, 2, 4, 9]


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


суббота, 15 сентября 2007 г.

Почему Python не идеален

Мне, будучи Java-разработчиком (а теперь уже и .Net) грех не провести хоть какое-то сравнение Java'ы и питона (попутно коснувшись и других языков). Да, знаю, что таких сравнений пруд пруди на просторах интернета. И тем не менее... Тут я хочу выйти немного в другую плоскость, отчасти философскую. Я не претендую на объективность, более того, вероятно, мои мысли покажутся вам довольно спорными.
Питон - язык с идеологией, есть особая культура написания программ на нем. О программе, написанной "правильно", по канонам питона говорят, что она pythonic, соответствует python way. Для непосвященных скажу, что есть своего рода Дзен Питона - сводка негласных правил правильного кодирования на питоне. Чтоб доказать, что питон - язык с идеологией, разработчики даже встроили эти правила в качестве стандартного модуля языка, вот пример работы:


>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!


Впрочем, я слукавил, правила эти вполне даже гласные, и они создают ту самую самобытность языка, за которую некоторые и изучают новые языки. Правила эти по сути были заложены в язык его создателем и главным идеологом, Гвидо ван Россумом. Он недаром получил статус BDFL (Benevolent dictator for life, Великодушный Пожизненный Диктатор).
Но позвольте высказать одну крамольную мысль: Java лучше соответствует этим правилам, нежели сам Питон. И вот почему.
Возьмем, например пресловутое
"There should be one-- and preferably only one --obvious way to do it."
но многим известно что питон - очень гибкий язык и на практике путей довольно таки много (не так мого, правда, как в перле =). Вот хотя бы почитайте рассуждения самого Россума об изысканиях при оптимизации.
Язык я бы оценивал по отношению двух параметров:
  1. Средствам программирования, реализованным в языке (предоставляемые языком) (ООП, функциональный стиль, исключения, замыкания, продолжения, система модулей)
  2. Языковые конструкции, синтаксический сахар, которыми достигается функциональность пункта 1.
И я склонен первое оценивать со знаком плюс, второе со знаком минус. Вторые плохи, т.к. они вносят неоднородность, неконсистентность в язык. И позволительны, только когда действительно наглядны и явно упрощают написание кода (в эту категорию я бы внес list comprehensions). Так вот, надо отдать должное Гвидо, питон довольно хорошо вписывается в эти критерии. Он обеспечивает, в целом, удовлетворительное ООП (почему так - ниже), систему модулей, исключения, замыкания, при этом синтаксис вполне однороден (за что собственно питон называют "языком с человеческим лицом", и по некоторым версиям это самый читабельный язык). Более того, Гвидо идет далее и в версии 3.0 языка убирает синтаксические конструкции (print, exec становятся функциями, % заменяется на метод .format)
А, например, перл совершенно не укладывается в эти рамки, у него достаточно посредственное ООП, исключения, при этом язык перенасыщен синтаксическими конструкциями настолько что позволяет писать даже такой, такой и такой код, ну скажите, о какой поддерживаемости кода тут может идти речь). Конечно мне возразят, что существуют стандарты кодирования на перл, в фирмах используются свои стандарты и т.п. Но в одном месте я слышал мысль что если что-то включено по умолчанию, то, хотя и присутствует очень простая опция сделать по-другому, но 90% пользователей (программистов) будут делать именно как по умолчанию. Применительно к перлу, слышал мысль, что большинство кода на CPAN написано хоть и не так как в вышеприведенных ссылках, но мягко говоря не по стандартам. Все из-за той-самой никому не нужной гибкости. Но ведь это гибкость из пункта 2, которая идет с минусом! Напротив, Java тем хороша, что она очень однородна по части синтаксиса. Вершиной идеала тут выступает, конечно смоллтолк. О минималистичности синтаксиса говорит тот факт, что в языке всего 6 ключевых слов и напрочь отсутствуют управляющие конструкции (if, while, for). Вместо этого там присутствуют методы ifTrue:, whileTrue:, each:, которые в сочетании с блоками дают такую функциональность, которой джава с питоном и руби только завидуют и слюнки пускают (продолжения, особая модель "откатываемых" исключений, чудесные возможности интроспекции кода и чудовищная гибкость). Впрочем, признаюсь, не знаю, куда отнести лисп, он вроде еще более однородный, довольно мощный, но при этом как по мне, у него плохо с читаемостью кода.
Питону, же, в отличие от того же руби который взял многое от смоллтолка, не хватает гибкости первого рода. Например, мне, в динамическом языке хотелось бы видеть
  1. Расширяемые базовые классы (Как в Руби, Смоллтолк, javascript(!!!))
  2. Любое выражение возвращает значение (руби) типа

    a = if 2>5 then "more" else "less" end

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

По пункту 2. Тут мне возразят, дескать, в питоне 2.5 таки наконец ввели конструкцию условного присваивания.

a = "more" if 2>5 else "less"

Вот именно! В язык ввели сущность вида 2 из-за недостаточной гибкости по пункту 1. Вот в этом и проблема. В частности, здесь и видна обратная сторона медали синтаксиса основанного на отступах (а не там где склонны видеть некоторые). Тут же и проблема немногострочной ламбды, для нее просто не смогли придумать подходящего синтаксиса!

Ruby кажется (вернее мог бы показаться, если б я только выбирал, какой динамический язык учить) более интересным, чем питон по нескольким причинам: удовлетворяет пунктам 1) и 2), менее консервативен чем Python, а потому более инновационен, более целостный (нет различий между базовыми типами и классами, которые , впрочем в Питоне 2.5 наконец тоже сведены на нет, нет функций - только методы). Единственное, мне не нравится его синтаксис, и кроме того, в нем нет чего-то концептуально нового по сравнению со смоллтолком, а продолжения, и вообще в 1.9 хотят убрать.

Java vs Python. Опять же трудно (и немножко глупо) сравнивать, это довольно разные языки хотя и для довольно общих целей. Взять хотя-бы пресловутый вопрос типизации. Что дает отстутствие статической типизации питону? - гибкость, легкость переделки программы "на коленке". Что дает ее присутствие Java'е - как это не парадоксально, опять же гибкость (правда, за счет довольно развитых IDE, типа Intellij Idea, способности которых - рефакторинг, генерация кода, навигация, удобства отладки, возможны исключительно благодаря типизируемой природе языка). Второе - скорость выполнения программ - очевидно, что статически-типизированный код легче оптимизировать для выполнения. И третье - конечно, легкость поддержки и совместной разработки кода, поскольку целостность и непротиворечивость кода отслеживается на уровне самого языка (той же типизацией, модификаторами доступа, интерфейсами), еще можно упомянуть четвертое - надежность - в Java приложении программист обязан обработать все (!) исключения, иначе программа попросту не скомпилируется (точнее не все, а все не RuntimeException). В питоне обычно процесс разработки может представлять следующую картину - написал код, запустил, получил исключение, обработал его в коде, снова запустил, и т.д.
Java - как это не странно - академический язык. Он очень хорошо подходит и для обучения, поскольку прекрасно реализует концепции программирования. Мне кажется, он "очень правильный". "It just feels right". Его правильность заключается в логичности, стройности, полноте, консервативности, очень полной и правильной поддержке ООП. На джаву прекрасно ложатся паттерны программирования.
Да, на счет ООП. В питоне, я бы охарактеризовал его двумя словами: оно есть. Чего в нем нет: модификаторов доступа (то что возможно с помощью префиксования имен двойным подчеркивание - не серьезно, и не соотвествует Дзену Питона). Тем самым нарушается один из принципов ООП - инкапсуляция. Там отсутствуют интерфейсы, абстрактные классы, хотя, понимаю, что это фича типизируемых языков, однако они выступают очень полезными при построении архитектуры проекта.
Коснемся модульной структуры. Java имеет очень мощную модульную структуру. Стандартно, библиотеки распространяются в виде jar-архивов. Питоновские eggs (яйца) пока не так распространены. Даже в Руби быстро смекнули что модули это хорошо и gems там "из коробки". Если спуститься на уровень ниже, то у джавы прекрасные возможности по организации и проектирования кода в пакеты, классы, внутренние классы, внутренние статические, локальные классы, final классы, абстрактные классы и интерфейсы.
Единственное, что сложнее с Java'ой - это конечно, у нее выше порог вхождения. Чтоб начать комфортно программировать, нужно как минимум установить адекватную среду разработки (разработка "в блокноте" с джавой - пропащее и бездарное дело), создать проект, настроить библиотеки... собственно и все. Плюс, по мере необходимости, конечно, придется ориентироваться в целом ряде сопутствующих J-технологий и фреймворков (J2(S|M|E)E, JSP, EJB, JMX, JNDI, JAAS, Ant, JUnit).
На самом деле все приведенные аргумены, довольно субъективны. Конкретно мне Джава польше соответствует по духу, она позволяет все "разложить по полочкам". В ней удобнее проектировать. Думаю все сказанное в той или иной мере подходит и к C#.
Впрочем, в повседневной работе я использую Python тоже. Он прекасно дополняет джаву. Распарсить логи, сгенерировать тестовые данные или sql-скрипт для тестового заполнения базы, админские скрипты для работы с файлами на нем - одно удовольствие. Мне кажется, что комбинация статический + динамический язык (не важно, что вы изберете в качестве первого и второго) довольно обоснована и полезна.


четверг, 23 августа 2007 г.

Немного о Continuations (продолжениях) и легковесных нитях

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

Опишу лишь в двух словах. Продолжения позволяют довольно хитро манипулировать потоком выполнения программы. Представьте себе обычную императивную программу. Исполнение программы - это, по сути, выполнение команды за командой "сверху - вниз". Использование функций, объектов, методов ничего не меняет, оно лишь структурирует программу, но, по сути, это то же линейное выполнение. Так вот, продолжения позволяют провернуть примерно следующее: программа выполняется до некоторой точки (назовем ее A), в этой точке программа как бы "застывает" (для полноценных продолжений это означает что запоминается весь контекст выполнения (переменные, объекты, видимые в этой точке)), и выполнение программы переносится в другую ее точку (B). Далее она продолжает линейно выполняться до некоторой третьей точки (С) после чего, программа возвращается в первоначальную точку A (возможно, принося некоторое возвратное значение из точки C), в точке A восстанавливается сохраненный контекст исполнения, и программа продолжается (отсюда и "продолжение") дальше. Следует отметить что продолжение позволяет многократно возвращаться в точку A, восстанавливать переменные и "продолжаться". Мало того, по слухам, продолжение можно даже сериализовать. Уфф, вроде основные идеи изложил. За более точными определениями и формулировками проследуйте в Википедию или в Гугл.

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

Следует отметить, что подобная функциональность достигается довольно хитроумными манипуляциями с си-стеком в реализации того или иного языка программирования. В Java'е - динамическим изменением байт-кода.

Ну настало самое время привести несколько линков. Уже упомянутый ранее веб-фреймворк Seaside, написанный на Smalltalk'е во всю мощь использует силу продолжений. Удачное использование продолжений позволило развить стройную и мощную компонентную модель.

В Java'е тоже имеется full-stack веб-фреймворк RIFE основанный на продолжениях, (продолжения входят в него отдельной библиотекой, т.ч., думается, ничто не мешает использовать их и вне этого фреймворка). Реализация библиотеки основана на манипуляциях с Java байткодом, которые впрочем запрятаны, и о них не стоит беспокоится. Впрочем есть и другие java-реализации продолжений, включая и от jakarta. Очень рекомендую к просмотру ролик (1.9Mb) с презентацией, наглядно показывающий смысл продолжений.

В Python'е что-то близкое к продолжениям предоставляет реализация Stackless Python. Однако в целях практичности продолжения, присутствующие там ранее были заменены облегченной концепцией partial continuations (если не путаю=)). Фактически, можно сказать, что основными примитивами там являются тасклеты и каналы, которые в совокупности позволяют реализовать очень интересные вещи: сопрограммы, легковесные нити (в чем-то аналогичные Erlang'овским). Легковесные нити очень быстры (по сравнению с нитями операционной системы, на одной нити операционной системы может присутствовать очень много легковесных нитей), правда в них требуется явное переключение контекста либо через шедулинг, либо посредством каналов. Кто-то даже провел сравнительное тестирование такой "легкой многопоточности" и получил довольно интригующий результат - Питон в некоторых случаях уделывает Эрланг на его же поле. Впрочем, наверное, не даром именно stackless python реализация многопоточности была выбрана для движка известной RPG многопользовательской онлайн-игры EVE Online.

Есть однако и некоторые сложности с продолжениями. Во-первых, они сложны (извините за тавтологию). Во-вторых, их использование может быть довольно ресурсоемким (запоминать контекст), именно поэтому используются облегченные варианты реализации типа partial continuations с выборочным сохранением контекста. А в веб-фреймворках присутствует еще одно ощутимое неудобство, являющееся прямым следствием реализации - не user-friendly ссылки, например, в Seaside ссылки представляются примерно в таком виде: http://seaside.st/documentation/faq?14&_k=UHOHBZlm&_n&_s=AkYosBcncRoLPbed. Тут присутствуют некие некрасивые параметры _k и _s. Один из них отвечает за состояние текущего продолжения, а другой - за ваше текущее местоположение на сайте (могу путать).
Впрочем, положительный момент - все линки генерируются автоматически (!!!) на основе построенной вами связи между компонентами.
UPD 1. На сайте ibm.com читайте статью Брюса Тэйта "Пересекая границы: Continuation, Web-разработка и Java-программирование". В статье описываются принципы работы веб-фреймворков основаных на продолжениях.
UPD 2. Дополнение по питону. Автор Stackless Python, Кристиан Тисмер сейчас принимает участие в реализации очень интересного проекта PyPy. Это по своей задумке довольно амбициозный проект, суть которой заключается в написании интерпретатора питона на нем самом же, а так же написании компилятора питона (на нем самом же, таки) в другие низкоуровневые языки, включая в бинарный исполнимый код. Такой подход не взят с потолка, как мы помним он используется и в случае Squeak Smalltalk'а. По мнению разработчиков, благодаря гибкости питона, это позволит легко реализовывать разные сложные но полезные концепции (включая те же продолжения, легковесные нити, и т.д.), и, что самое главное, разработчики утверждают, что благодаря реализуемому JIT-компилятору, полученный питон будет быстрее его стандартной C-реализации!


четверг, 12 июля 2007 г.

Полезный скрипт для извлечения видео из кэша Firefox (под Win)

Часто поднимается вопрос, как скачать видео с youtube.com и других подобных сайтов, есть даже сайты, типа youtubex.com специально предназначенные для скачивания локально .flv - файлов, есть плагины для Firefox.
Я использую другой метод, правда, он может помочь Вам только в случае если вы используете Firefox, как и я :-)
Представляю вашему вниманию скрипт (python) который ползет в кэш браузера Mozilla Firefox и достает оттуда уже просмотренные вами видео-файлы, на данный момент он распознает форматы FLV (именно в этом формате хранится большинство видео на youtube) и SWF (флэш-файлы). Извлеченные файлы копируются в специальную директорию, и к ним присоединяется нужное расширение.
Собственно, сам скрипт:



# file: getflv.py
import os
import os.path
import shutil
import time

REG_DIR = 'REG'
DATE_FORMAT = "%Y_%m_%d, %H-%M-%S"

OUTDIRS = {
'FLV': 'flv',
'SWF': 'swf',
}

def createDirIfNeeded(fullPath):
if not os.path.exists(fullPath):
os.makedirs(fullPath)

def createDirsIfNeeded():
for dir in OUTDIRS.itervalues():
createDirIfNeeded(dir)

createDirIfNeeded(REG_DIR)

def fileSize(fPath):
return os.stat(fPath).st_size

def getFileType(path):
s = open(path).read(30)

if s[:3] == 'FLV':
return 'FLV'
elif s[:3] == 'FWS':
return 'SWF'

return None

def isInReg(f, sourcePath):
# name and size matches
return (f in os.listdir(REG_DIR) and open(REG_DIR + '/' + f).read() == str(fileSize(sourcePath)))

def formDirName():
return time.strftime(DATE_FORMAT)

def doCopy(fromPath, outDirName, fName, fileType):
print 'Copying %s video: %s of size %s' % (fileType, fName, fileSize(fromPath))

ext = fileType.lower()

createDirIfNeeded(OUTDIRS[fileType] + '/' + outDirName)

shutil.copyfile(fromPath, OUTDIRS[fileType] + '/' + outDirName + '/' + fName + '.' + ext)

# add to reg
open(REG_DIR + '/' + fName, 'w').write(str(fileSize(fromPath)))

def getFirefoxCacheDir():
profileDir = os.environ['USERPROFILE']
firefoxProfile = profileDir + '/Local Settings/Application Data/Mozilla/Firefox/Profiles'

files = os.listdir(firefoxProfile)
assert len(files) == 1

hashDir = firefoxProfile + '/' + files[0]
assert os.path.isdir(hashDir)

return hashDir + '/Cache'

def main():
createDirsIfNeeded()
outDirName = formDirName()
cacheDir = getFirefoxCacheDir()
files = os.listdir(cacheDir)

for f in files:
path = cacheDir + '/' + f

fileType = getFileType(path)

if fileType in ('FLV', 'SWF'):
if not isInReg(f, path): # path to determine size
# copying
doCopy(path, outDirName, f, fileType)

if __name__ == '__main__':
main()


Немного поясню принцип работы. Конфигурировать скрипт никак не требуется. После запуска (в первый раз) будет созданы директории с именами swf, flv и REG в директории со скриптом. Первые две будут, разумеется, использоваться для наполнения извлеченными видео-файлами, а директория REG имеет служебное назначение. В ней хранится список выкачанных файлов и их размеров, чтоб при следующем запуске скрипта они повторно не выкачивались. При каждом запуске в случае обнаружения в кэше новых видео-файлов в соответствующей директории (flv, swf) будет создана новая директория с именем составленным из текущего таймстемпа, в нее будут скопированны файлы данного типа.
Директория кэша браузера находится исходя из настройки переменной окружения %USERPROFILE% (разумеется, речь идет о Windows). Файлы в кэше браузера распознаются по сигнатурам начала файла (flv-файл начинается на 3 байта 'FLV', а flash-файл на 'FWS'). Собственно по сигнатурам можно распознавать и другие файлы, было бы хорошо сделать mov, wmv, avi, mp3 но там сигнатуры посложнее. Если кто сделает - обязательно дайте знать, буду оч. благодарен! )
Да, и совет сделать кэш браузера слегка побольше (100 - 150 мб).


пятница, 22 июня 2007 г.

Алгоритмы Маркова

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

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

Программа на языке алгоритмов Маркова - представляет из себя набор правил (Rules). Каждое правило представляет собой замену. Т.е. правило имете вид


S1 -> S2

где S1 и S2 некие строки. Правило представляет подстановки, последовательно применяемые ко входной строке и приводящие в итоге ее к требуемой выходной строке. Порядок задания правил важен. Работает алгоритм этот следующим образом. Берется исходная строка и мы начинаем переберать правила с самого первого, анализируя, может ли оно быть применено (существует ли в строке S подстрока S1). Если не может -> анализируется следующее по порядку правило. Если не одно правило не подошло, алгоритм завершается, текущее состояние строки S является результатом работы алгоритма. Если же правило применимо - совершается замена самого левого вхождения подстроки S1 на строку S2 (или, выражаясь языком питона, S = S.replace(S1, S2, 1)). Причем, (что очень важно!) далее правила начинают перебираться опять с начала.

Еще есть так называемые терминальные правила, обозначающиеся точкой в конце:

S1 -> S2.

При срабатывании такого правила алгоритм завершается и текущее состояние строки S считается результатом работы алгоритма.

Кто не понял еще, как это работает могут обратиться за помощью к Википедии, а нам, я понимаю уже не терпится начать программировать на алгоритмах Маркова =).

Сразу оговорюсь, что я буду использовать вместо стрелки "->" знак ">".

Итак, решим задачу: задана строка из 0 и 1. Получить на выходе строку в которой 1-цы заменены 0-ми, а 0-и - единицами.

Нет ничего проще (";" в начале строки - это комментарий):

; "*"-работник движется вдоль строки, и выполняет "работу" меняет 0 -> 1, 1 -> 0
*0 > 1*
*1 > 0*

; уничтожение "*"-работника, алгоритм завершается.
* > .

; ставим в самом начале звездочку-"работника" (замена пустой подстроки на *)
> *


Проследим, как это работает. Возьмем входную строку "1101". Пробуем последовательно применить подстановки. Понятно, что первые 3 не подйдут, поскольку в строке нет "*". Но подойдет самая последняя подстановка и звездочка будет добавлена. Получим "*1101". Затем, поседовательно применяя подстановки номер 1) и 2) будем получать: 0*101, 00*01, 001*1, 0010*. Сейчас применима только 3)-я подстановка, она же и завершающая. Звездочка в конце удаляется, получаем результат: 0010

Рассмотрим задачу посложнее: дано строковое представление числа в десятичной системе счисления, получить десятичное представление числа на 1-цу больше.

Рассмотрим решение.


; incrementing decimal
; data:

9999

; algorithm:

0#>1.
1#>2.
2#>3.
3#>4.
4#>5.
5#>6.
6#>7.
7#>8.
8#>9.

9#>#0

*#>1.

*0>0*
*1>1*
*2>2*
*3>3*
*4>4*
*5>5*
*6>6*
*7>7*
*8>8*
*9>9*

*>#

>*


На первый взгляд может показаться немного сложно и непонятно, но на самом деле все более чем просто. Рассмотрим, как работает этот алгоритм. Сперва срабатывает последяя подстановка, добавляющая "*" в начало числа. Применяя подстановки *N > N* она передвигается к концу числа. Когда звездочка дойдет до конца числа, она будет заменена на "#". Собственно, это пока было сделано ровно для того, чтоб получить ту самую # в конце числа. Теперь интересно. Решетка (#) будет выполнять роль 1-цы, которую мы прибавляем к числу. В самом деле, посмотрим на первые 9 подстановок (N# > {N+1}., N=0..8). Если последняя цифра числа от 0 до 8, то она увеличивается на 1 и алгоритм успешно завершаетя. Интереснее, когда в конце числа 9-ка, в этом случае срабатывает 9# > #0. Фактически это как будто перенесение 1-цы в следующий разряд. Теперь благодаря опять-же первым 9 подстановкам на 1 пытается быть увеличенной предпоследняя цифра. Если она меньше 9 опять же алгоритм завершается.

Положим, что все цифры в числе - девятки. Тогда # заменяя их нулями дойдет до самого начала числа. После этого произойдет интересный финт ушами. Снова сработает последняя подстановка и добавит в начало *. После этого терминальная подстановка *# > 1. завершит алгоритм.

Вот лог работы при входном числе 9999:

Applying rule 22 >*
9999 -> *9999

Applying rule 20 *9>9*
*9999 -> 9*999

Applying rule 20 *9>9*
9*999 -> 99*99

Applying rule 20 *9>9*
99*99 -> 999*9

Applying rule 20 *9>9*
999*9 -> 9999*

Applying rule 21 *>#
9999* -> 9999#

Applying rule 9 9#>#0
9999# -> 999#0

Applying rule 9 9#>#0
999#0 -> 99#00

Applying rule 9 9#>#0
99#00 -> 9#000

Applying rule 9 9#>#0
9#000 -> #0000

Applying rule 22 >*
#0000 -> *#0000

Applying rule 10 *#>1.
*#0000 -> 10000

Terminating rule!
Result : 10000


Вот еще интересный случай. Умножение числа на 2. Тут уже объяснять не буду как работает, просто приведу программу и пример работы.

; doubling decimal

948

; algorithm:

0[0]>[0]0
0[1]>[0]1

1[0]>[0]2
1[1]>[0]3

2[0]>[0]4
2[1]>[0]5

3[0]>[0]6
3[1]>[0]7

4[0]>[0]8
4[1]>[0]9

5[0]>[1]0
5[1]>[1]1

6[0]>[1]2
6[1]>[1]3

7[0]>[1]4
7[1]>[1]5

8[0]>[1]6
8[1]>[1]7

9[0]>[1]8
9[1]>[1]9

[0]>.
[1]>1.

*0>0*
*1>1*
*2>2*
*3>3*
*4>4*
*5>5*
*6>6*
*7>7*
*8>8*
*9>9*

*>[0]

>*


Вывод, по которому все должно стать понятно:


Applying rule 33 >*
948 -> *948

Applying rule 31 *9>9*
*948 -> 9*48

Applying rule 26 *4>4*
9*48 -> 94*8

Applying rule 30 *8>8*
94*8 -> 948*

Applying rule 32 *>[0]
948* -> 948[0]

Applying rule 16 8[0]>[1]6
948[0] -> 94[1]6

Applying rule 9 4[1]>[0]9
94[1]6 -> 9[0]96

Applying rule 18 9[0]>[1]8
9[0]96 -> [1]896

Applying rule 21 [1]>1.
[1]896 -> 1896

Terminating rule!
Result : 1896


Самое интересное, что реализация такой машины Маркова - сущие пустяки. Вот скрипт, который я написал пару лет назад:


# file: markov.py
COMMENT_SYMBOL = ';'
DELIM_SYMBOL = '>'

import sys
if len(sys.argv) > 1:
FILE_NAME = sys.argv[1]
else:
FILE_NAME = 'alg.txt'

arr = [s for s in open(FILE_NAME, 'r').read().split('\n') \
if s.lstrip() and s.lstrip()[0] != COMMENT_SYMBOL ]

DATA_STRING = arr[0]

ALG = arr[1:]

ALG_PAIRS = [ tuple(s.split(DELIM_SYMBOL)) for s in ALG ]

# algorithm:
_s = DATA_STRING

class Exit:
pass

while True:
try:
for i in range( len( ALG_PAIRS ) ):
_rule_applied = False

pair = ALG_PAIRS[i]

if pair[0] in _s:
_rule_applied = True

_repl = pair[1]
_term = False

if _repl[-1]=='.': # this is terminating rule
_term = True
_repl = _repl[0:-1]

print ' Applying rule', i, ALG[i]
print _s,'->',

_s = _s.replace(pair[0], _repl, 1)

print _s+'\n'

if _term:
print ' Terminating rule!'
raise Exit()

break

if not _rule_applied:
print ' No rules matched!'
break # no one rules matched

except Exit:
break

print 'Result : '+_s


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

Однако, продолжим. Не так давно мне захотелось усовершенствовать немного интерпретатор алгоритмов Маркова, в следующих направлениях:

  • Ввести псевдосимволы начала "^" и конца "$" строки, знакомые тем кто разбирается в регулярных выражениях. В первом, пожалуй нет особой необходимости, но вот последний позволит таким правилом

    $ > #

    сразу добавить что-нибудь (в данном случае решетку) в конец, а не так как мы ее добавляли выше
  • Второе, более хитрое. Позволяет делать "универсальные" правила. Словами объяснять долго, объясню на примере:

    {A=abc} > {A}{A}{A}

    Эквивалентно целым 3 правилам

    a > aaa
    b > bbb
    c > ccc

    При этом можно даже так:

    {BBB=1-3} > { int(BBB)*7 }

    что эквивалентно

    1 > 7
    2 > 14
    3 > 21

    То есть это позволяет сокращать "программы". Кто не понял, как это работает, объясняю подробнее: фигурные скобки слева от ">" будут соответствовать только одному символу, из тех, что находятся внутри этих фигурных скобок после знака "=". При этом, если соответсвтие произошло, переменной слева от "=" будет присвоено строковое значение этого символа. При совершении подстановки оно может быть раскрыто в правой части. Если быть точнее от того, что стоит в фигурных скобках в правой части будет взят питоновский eval. Это вообще не совсем честная операция, в том смысле что алгоритмы Маркова основаны исключительно на подстановках, и правильнее было бы сделать препроцессор, который "раскрывал" бы такие универсальные подстановки, генерируя нормальные программы для классической машины алгоритмов Маркова. Но это оказалось выполнить немного технически сложнее, поэтому все осталось именно так как я описал.

Не мудрствуя лукво, привожу исходник.

import re

COMMENT_SYMBOL = ';'
DELIM_SYMBOL = '>'

class FromMatcher(object):
def __init__(self):
self.vars = []

def appendVarName(self, varname):
self.vars.append(varname)

def setFromReStr(self, s):
self.fromReStr = s
self.fromRe = re.compile(s)

def getFromRe(self):
return self.fromRe

def __str__(self):
return 'FromMatcher(%s)' % self.fromReStr

def getVarDict(self, mo):
return dict([(v, mo.group(v)) for v in self.vars])

class MarkovCompiler(object):
FROM_VAR_PATTERN = re.compile(r'\{(?P<varname>[A-Z_][A-Za-z0-9_]*?)=(?P<chars>.+?)\}') # } to place first in chars group if needed
SPECIAL_CHARS = re.compile(r'(?<!\\)([*?+\{\}\[\]\(\)])')
REPLACE_GROUP_RE = re.compile(r'\{([^{}]+?)\}')

@staticmethod
def makeRe(from_s):
fm = FromMatcher()

class ResultHolder:
def __init__(self):
self.result = ''
self.lastend = 0

rh = ResultHolder()

def processBetween(s):
s = MarkovCompiler.SPECIAL_CHARS.sub(r'\\\1', s)
return s

def subf(mo):
varname = mo.group('varname')
fm.appendVarName(varname)
chars = mo.group('chars')

between_s = from_s[rh.lastend:mo.start()]
rh.result += processBetween(between_s)
rh.lastend = mo.end()

rh.result += r'(?P<%s>[%s])' % (varname, chars)

MarkovCompiler.FROM_VAR_PATTERN.sub(subf, from_s)

rh.result += processBetween(from_s[rh.lastend:])

fm.setFromReStr(rh.result)
return fm

@staticmethod
def expandTo(to_s, var_dict):
def subf(mo):
# print 'Evaling:', '#'+mo.group(1)+'#'
return str(eval(mo.group(1), None, var_dict))

return MarkovCompiler.REPLACE_GROUP_RE.sub(subf, to_s)


class Rule(object):
def __init__(self, s):
self.terminating = False
self.parse(s)

def parse(self, s):
self._from, self._to = map(str.strip, s.split(DELIM_SYMBOL))

if self._to[-1] == '.':
self.terminating = True
self._to = self._to[:-1]

self.compile()

def compile(self):
self._fromMatcher = MarkovCompiler.makeRe(self._from)
# print 'Compiled:', self._fromMatcher

def match(self, s):
self._mo = self._fromMatcher.getFromRe().search(s)

def getMatch(self):
return self._mo

def expand(self):
return MarkovCompiler.expandTo(self._to, self._fromMatcher.getVarDict(self._mo))

def showVars(self):
d = self._fromMatcher.getVarDict(self._mo)
return ', '.join(['%s=%s' % (k, d[k]) for k in d])

def __str__(self):
return '%s: %s > %s' % (self.__class__.__name__, self._from, self._to)

def isTerminating(self):
return self.terminating

class Algorithm(object):
def __init__(self, listOfStr):
self.rules = list(map(Rule, listOfStr))

def __str__(self):
return '%s(\n\t' % self.__class__.__name__ + \
'\n\t'.join(map(str, self.rules)) + \
'\n)'

def getRules(self):
return self.rules

class Exit:
pass

class Processor(object):
def __init__(self, program=None, file=None):
if type(program) == str:
self.parse(program)
elif type(program) == file:
self.parse(program.read())
elif file:
self.parse(open(file).read())

def parse(self, _s):
_arr = [s.strip() for s in _s.split('\n') \
if s.lstrip() \
and s.lstrip()[0] != COMMENT_SYMBOL]
self.setData(_arr[0])
self.setAlgorithm(_arr[1:])

def setData(self, initialData):
self.initialData = initialData

def setAlgorithm(self, algorithm):
if type(algorithm) == str:
self.parse('_\n'+algorithm)
self.initialData = None
if type(algorithm) in (list, tuple) :
self.algorithm = Algorithm(algorithm)
elif type(algorithm) == Algorithm:
self.algorithm = algorithm

def process(self, debug=True):
_s = self.initialData

if debug: print 'Initial data:\n', _s, '\n\nAlgorithm:\n', self.algorithm

while True:
try:
_rule_applied = False

for rule in self.algorithm.getRules():
rule.match(_s)
if rule.getMatch():
_rule_applied = True

if debug:
vars = rule.showVars()
print str(rule) + ['', ', vars: ' + vars + ':'][int(bool(vars))]
_s = _s[:rule.getMatch().start()] + rule.expand() + _s[rule.getMatch().end():]

if debug: print _s, '\n'; import time; time.sleep(.05)
if rule.isTerminating():
if debug: print 'Terminating rule...'
raise Exit()

break

if not _rule_applied:
print 'No rule matched...'
break

except Exit:
break

if debug: print 'Result:\n', _s
return _s

def solve(self, data):
self.setData(data)
return self.process(debug=False)


if __name__ == '__main__':
import sys
if len(sys.argv) > 1:
FILE_NAME = sys.argv[1]
else:
FILE_NAME = 'alg.txt'
Processor(file=FILE_NAME).process()


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

99999

{N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }

^[0] > .
^[1] > 1.

$>[0]

Вот вывод:

G:\!TRY\Python\markov>python markov_enhanced.py doubling_decimal2.txt
Initial data:
99999

Algorithm:
Algorithm(
Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }
Rule: ^[0] >
Rule: ^[1] > 1
Rule: $ > [0]
)
Rule: $ > [0]
99999[0]

Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }, vars: N1=9, N2=0:
9999[1]8

Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }, vars: N1=9, N2=1:
999[1]98

Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }, vars: N1=9, N2=1:
99[1]998

Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }, vars: N1=9, N2=1:
9[1]9998

Rule: {N1=0-9}[{N2=0-9}] > [{ (2*int(N1)+int(N2)) / 10 }]{ (2*int(N1)+int(N2)) % 10 }, vars: N1=9, N2=1:
[1]99998

Rule: ^[1] > 1
199998

Terminating rule...
Result:
199998


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

Вот собственно решение.

()()(()(()))

** > *
()* > *
*() > *
(*) > *

() > *


1* > 1
1( > 0
1) > 0

0{A=*()} > 0

1$ > right.
0$ > wrong.

^ > 1

Вывод:

G:\!TRY\Python\markov>python markov_enhanced.py brackets.txt
Initial data:
()()(()(()))

Algorithm:
Algorithm(
Rule: ** > *
Rule: ()* > *
Rule: *() > *
Rule: (*) > *
Rule: () > *
Rule: 1* > 1
Rule: 1( > 0
Rule: 1) > 0
Rule: 0{A=*()} > 0
Rule: 1$ > right
Rule: 0$ > wrong
Rule: ^ > 1
)
Rule: () > *
*()(()(()))

Rule: *() > *
*(()(()))

Rule: () > *
*(*(()))

Rule: () > *
*(*(*))

Rule: (*) > *
*(**)

Rule: ** > *
*(*)

Rule: (*) > *
**

Rule: ** > *
*

Rule: ^ > 1
1*

Rule: 1* > 1
1

Rule: 1$ > right
right

Terminating rule...
Result:
right


Если же на вход подать такую скобочную структуру: ()()((()(())), то получим:

G:\!TRY\Python\markov>python markov_enhanced.py brackets.txt
Initial data:
()()((()(()))

Algorithm:
Algorithm(
Rule: ** > *
Rule: ()* > *
Rule: *() > *
Rule: (*) > *
Rule: () > *
Rule: 1* > 1
Rule: 1( > 0
Rule: 1) > 0
Rule: 0{A=*()} > 0
Rule: 1$ > right
Rule: 0$ > wrong
Rule: ^ > 1
)
Rule: () > *
*()((()(()))

Rule: *() > *
*((()(()))

Rule: () > *
*((*(()))

Rule: () > *
*((*(*))

Rule: (*) > *
*((**)

Rule: ** > *
*((*)

Rule: (*) > *
*(*

Rule: ^ > 1
1*(*

Rule: 1* > 1
1(*

Rule: 1( > 0
0*

Rule: 0{A=*()} > 0, vars: A=*:
0

Rule: 0$ > wrong
wrong

Terminating rule...
Result:
wrong


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

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

  1. Усовершенствовать последнюю задачу для определения правильности скобочной структуры из (){}[] и символов английского алфавита между ними.
  2. Написать алгоритм обращения строки (из символов a-zA-Z0-9) задом-наперед (reverse).
  3. Сложение 2-х десятичных чисел, заданных строкой вида "12345+678".
  4. Реализовать алгоритм rot13.

Задачи 2)-4) были решены мною, и решения будут опубликованы следующим постом.

Выводы. Алгоритмы Маркова представляют собой очень простую но вместе с тем интересную концепцию. Думается, что-то подобное было в древнем языке Snobol и в (возможно, ошибаюсь) его современном диалекте Snowball применяемом для стеммеров при полнотекстовом поиске. Пока что практическая польза такого подхода не очень велика, но, возможно, найдутся задачи, где подобный подход может показать себя с положительной стороны. Возможно, стоит улучшить интерпретатор чтоб распознавались не одиночные символы, а целые регулярные выражения.


пятница, 1 июня 2007 г.

Еще про декораторы

Интересная статья про декораторы на сайте ibm.com