Vladimir Gubarkov

Prolog

2008-12-20T10:50:00.000-08:00

В описании блога фигурирует слово 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] ;
...


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

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



Функциональный питон
2008-12-02T10:18:00.000-08:00
На досуге пришла идея используя 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), но, как видим, можно и так извратиться =)
Сразу замечу, практического смысла в этом нет, и, более того, такой код является плохой практикой, но с точки зрения экспериментов, по-моему, занятно.


Почему Python не идеален
2007-09-15T16:27:00.000-07:00
Мне, будучи 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.
И я склонен первое оценивать со знаком плюс, второе со знаком минус. Вторые плохи, т.к. они вносят неоднородность, неконсистентность в язык. И позволительны, только когда действительно наглядны и явно упрощают написание кода (в эту категорию я бы внес list comprehensions). Так вот, надо отдать должное Гвидо, питон довольно хорошо вписывается в эти критерии. Он обеспечивает, в целом, удовлетворительное ООП (почему так - ниже), систему модулей, исключения, замыкания, при этом синтаксис вполне однороден (за что собственно питон называют "языком с человеческим лицом", и по некоторым версиям это самый читабельный язык). Более того, Гвидо идет далее и в версии 3.0 языка убирает синтаксические конструкции (print, exec становятся функциями, % заменяется на метод .format)
А, например, перл совершенно не укладывается в эти рамки, у него достаточно посредственное ООП, исключения, при этом язык перенасыщен синтаксическими конструкциями настолько что позволяет писать даже такой, такой и такой код, ну скажите, о какой поддерживаемости кода тут может идти речь). Конечно мне возразят, что существуют стандарты кодирования на перл, в фирмах используются свои стандарты и т.п. Но в одном месте я слышал мысль что если что-то включено по умолчанию, то, хотя и присутствует очень простая опция сделать по-другому, но 90% пользователей (программистов) будут делать именно как по умолчанию. Применительно к перлу, слышал мысль, что большинство кода на CPAN написано хоть и не так как в вышеприведенных ссылках, но мягко говоря не по стандартам. Все из-за той-самой никому не нужной гибкости. Но ведь это гибкость из пункта 2, которая идет с минусом! Напротив, Java тем хороша, что она очень однородна по части синтаксиса. Вершиной идеала тут выступает, конечно смоллтолк. О минималистичности синтаксиса говорит тот факт, что в языке всего 6 ключевых слов и напрочь отсутствуют управляющие конструкции (if, while, for). Вместо этого там присутствуют методы ifTrue:, whileTrue:, each:, которые в сочетании с блоками дают такую функциональность, которой джава с питоном и руби только завидуют и слюнки пускают (продолжения, особая модель "откатываемых" исключений, чудесные возможности интроспекции кода и чудовищная гибкость). Впрочем, признаюсь, не знаю, куда отнести лисп, он вроде еще более однородный, довольно мощный, но при этом как по мне, у него плохо с читаемостью кода.
Питону, же, в отличие от того же руби который взял многое от смоллтолка, не хватает гибкости первого рода. Например, мне, в динамическом языке хотелось бы видеть
Расширяемые базовые классы (Как в Руби, Смоллтолк, javascript(!!!))
Любое выражение возвращает значение (руби) типа 

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

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

По пункту 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-скрипт для тестового заполнения базы, админские скрипты для работы с файлами на нем - одно удовольствие. Мне кажется, что комбинация статический + динамический язык (не важно, что вы изберете в качестве первого и второго) довольно обоснована и полезна.


Немного о Continuations (продолжениях) и легковесных нитях
2007-08-23T07:40:00.000-07:00
Продолжения - очень интересная концепция в программировании, объяснять подробно лень, т.к. она, надо сказать, не очень-то проста, и всех тонкостей я и сам не знаю, поэтому и за точность изложения не поручусь (Мопед не мой, я лишь разместил объяву=) ).
 
 Опишу лишь в двух словах. Продолжения позволяют довольно хитро манипулировать потоком выполнения программы. Представьте себе обычную императивную программу. Исполнение программы - это, по сути, выполнение команды за командой "сверху - вниз". Использование функций, объектов, методов ничего не меняет, оно лишь структурирует программу, но, по сути, это то же линейное выполнение. Так вот, продолжения позволяют провернуть примерно следующее:  программа выполняется до некоторой точки (назовем ее 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-реализации!


Полезный скрипт для извлечения видео из кэша Firefox (под Win)
2007-07-12T04:14:00.000-07:00
Часто поднимается вопрос, как скачать видео с 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 мб).



Алгоритмы Маркова
2007-06-22T10:00:00.000-07:00
Давно, еще классе в 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


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

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

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

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

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


Еще про декораторы
2007-06-01T03:05:00.000-07:00
Интересная статья про декораторы на сайте ibm.com


Кроссбраузерность
2007-05-16T10:20:00.000-07:00
Такой код

<textarea id="t">
123
123
123
123
</textarea>
<script>
var t = document.getElementById('t');
alert(t.value.length+", "+
 t.value.charCodeAt(3)+", "+t.value.charCodeAt(4));
</script>

под Firefox'ом (1.5.0.11) выдает 
16, 10, 49

а под IE 7.0
20, 13, 10

Напомню, что ASCII-код '\r' равен 13, а '\n' равен 10.
Таким образом файрфокс переносы строк обрабатывает как '\n' а IE как '\r\n' в текстовых полях. Но что характерно, оба браузера при сабмите шлют на сервер '\r\n', такая вот небольшая несуразность с файрфоксом. Проблема с этим у меня возникла при клиентской валидации длины вводимого текста. При этом на файрфоксе в некоторых случаях клинентская валидация проходила успешно, а серверная нет.


ООП, замыкания, или изобретая велосипеды...
2007-05-11T05:40:00.000-07:00
Тут одна занятная штука нарисовалась. Вот возьмем объект (экземпляр класса) из ООП. Упрощенно, его методы можно считать обычными функциями, в контекст которых захвачена переменная this (или self, кому что нравится). Поясню на примере языка Python, что такое замыкание.

def makeAdder(num):
   def adder(num1):
       return num + num1
   return adder

sevenAdder = makeAdder(7)
print sevenAdder(2) # => 9

В данном случае вложенная функция adder при своем создании захватывает окружающий ее контекст. В частности, в этом контексте оказывается переданная в функцию makeAdder переменная num.
И вот пришла идея создать на такой основе что-то вроде ООП. Вот что в результате получилось:
from bicycleoop import *

@klass()
def Superclass(this, kls):
   kls.AAA = 'Superclass_AAA'

   @method
   def say1():
       print 'from super.say1: [arg1 = %s];' % this.arg1

   @method
   def say3():
       print 'from say3;'

   @method
   def say5():
       print 'from say5:',
       this.say2()

   @method
   def say6():
       print 'from super say6;'

   @method
   def say7():
       print 'from say7: this.AAA='+this.klass.AAA, 'super.AAA='+this.super.klass.AAA

@klass(Superclass)
def Klass1(this, kls):
   kls.AAA = 'Klass1_AAA'

   @klassmethod
   def klm1():
       print 'KlassMethod1: Klass1.AAA='+kls.AAA, 'Superclass.AAA='+kls.superClass.AAA

   @method
   def __init__(arg1, arg2):
       print 'creating instance of %s with arg1=%s, arg2=%s' % (this.klass.name, arg1, arg2)
       this.arg1 = arg1
       this.arg2 = arg2

   @method
   def say1():
       print "from say1: [arg1 = %s]" % this.arg1

   @method
   def say2():
       print "from say2: [arg2 = %s]" % this.arg2,
       this.say1()

   @method
   def say4():
       print 'from say4:',
       this.say3()

   @method
   def say6():
       print 'from say6:',
       this.super.say6()

print Superclass.AAA        # => Superclass_AAA
print Klass1.AAA            # => Klass1_AAA

k = Klass1.new(17, "Hello") # => creating instance of Klass1 with arg1=17, arg2=Hello
k.say1          # => from say1: [arg1 = 17]
k.super.say1()  # => from super.say1: [arg1 = 17];
k.say2()        # => from say2: [arg2 = Hello] from say1: [arg1 = 17]
k.say3()        # => from say3;
k.say4()        # => from say4: from say3;
k.say5()        # => from say5: from say2: [arg2 = Hello] from say1: [arg1 = 17]
k.say6()        # => from say6: from super say6;
k.say7()        # => from say7: this.AAA=Klass1_AAA super.AAA=Superclass_AAA

k1 = Klass1.new(20, "sdfs") # => creating instance of Klass1 with arg1=20, arg2=sdfs
k.say2()        # => from say2: [arg2 = Hello] from say1: [arg1 = 17]
k1.say2()       # => from say2: [arg2 = sdfs] from say1: [arg1 = 20]

print Superclass.AAA        # => Superclass_AAA
print Klass1.AAA            # => Klass1_AAA

Klass1.klm1()     # => KlassMethod1: Klass1.AAA=Klass1_AAA Superclass.AAA=Superclass_AAA

sup = Superclass.new()

print k.methods.keys()      # => ['say7', 'say6', 'say5', 'say4', 'say3', 'say2', 'say1', '__init__']
print sup.methods.keys()    # => ['say7', 'say6', 'say5', 'say3', 'say1']

print k.klass == Klass1                                 # => True
print k.super.klass == Klass1.superClass == Superclass  # => True

o1 = obj()

Klass1(o1, Klass1)
o1.arg1 = 15
o1.say1()   # => from say1: [arg1 = 15]

Как видим, реализовано наследование (одиночное, правда), обычные и статические методы (методы класса), и статические поля тоже.  Создание объектов реализовано в стиле Смоллтолк и Руби (через Klass.new). В объявлении класса передаются 2 переменные (this и kls), что кажется немного странным. Но это, во-первых, более pythonic (Explicit is better than implicit) а, во-вторых, это как раз те переменные, которые будут "замкнуты" в замыкания из функций-методов. Замечу, что они инициализируются лишь в момент создания объекта.
Для выразительности объявление классов и методов выполненно в виде декораторов. Декоратор (для тех, кто не в курсе) это функциональность, работающаю следующим образом: код

@decor
def f(arg):
    # do smth
    pass
эквивалентен коду:

def f(arg):
    # do smth
    pass

f = decor(f)

То есть декоратор - это обычная функия, которой мы "декорируем" некоторую другую функцию. Я полагаю это имеет отношение к AOP и вероятно, этот механизм призван внести большую выразительность и декларативность в код. Подробнее про декораторы читать тут.
А вот описание модуля с декораторами:
# this is file bicycleoop.py
import sys

def obj():
   def _obj():pass
   return _obj

def klass(*args):
   # args - superclasses, now only 1 allowed
   def classDecorator(classFunc):
       if len(args) == 1:
           _superClass = args[0]
       else:
           _superClass = None

       def copyMethodsTo(this):
           this.klass = classFunc

           if _superClass:
               this.klass.superClass = _superClass
               this.klass.superClass.copyMethodsTo(this)# now into this exist all functions with captured 'this'
               this.klass = classFunc # return back after ^^^ changes it
               this.super = obj()
               this.super.klass = _superClass
               for meth in this.methods.keys():
                   setattr(this.super, meth, this.methods[meth])
           else:
               classFunc.superClass = None

           this.klass(this, obj()) # initing methods
           return this

       def new(*a, **k):
           this = obj()
           copyMethodsTo(this)
           this.__init__(*a, **k)
           return this

       classFunc.copyMethodsTo = copyMethodsTo
       classFunc.new = new
       classFunc.name = classFunc.func_name

       classFunc(obj(), classFunc) # for class vars and class methods

       return classFunc

   return classDecorator

def method(methodFunc):
   this = sys._getframe().f_back.f_locals['this']
   setattr(this, methodFunc.func_name, methodFunc)
   if not hasattr(this, 'methods'):
       this.methods = {}
   this.methods[methodFunc.func_name] = methodFunc
   return methodFunc

def klassmethod(methodFunc):
   kls = sys._getframe().f_back.f_locals['kls']
   setattr(kls, methodFunc.func_name, methodFunc)
   if not hasattr(kls, 'klassmethods'):
       kls.klassmethods = {}
   kls.klassmethods[methodFunc.func_name] = methodFunc
   return methodFunc

Тут есть пару моментов. Такой вот замысловатый код:

sys._getframe().f_back.f_locals['this']

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

>>> o = object()
>>> o.a = 123

Traceback (most recent call last):
File "", line 1, in 
o.a = 123
AttributeError: 'object' object has no attribute 'a'
>>>

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

PS. Извините за длинный пост. Кто-нибудь может подсказать как показывать только часть поста со ссылкой "читать далее" на лицевой странице?



Smalltalk, въезд
2007-05-08T04:42:00.000-07:00
Ну что. Расскажу я вам немного про Смоллтолк. Наверное, все (нормальные) программисты слышали такое слово как Смоллтолк, и что это есть дедушка всех ООП языков. Все это так, но мало кто знает, что это действительно очень концептуальный и интересный язык.
Что же в нем такого интересного? В общем то основные фичи языка можно прочитать тут и тут. В двух словах: все - суть объекты, которые общаются посредством сообщений (эквивалент сообщения - вызов метода).
Интересное начинается дальше. В смоллтолке все программы как бы неразрывны, более того, в смоллтолке все есть одна большая неразрывная программа. Другими словами, эта большая программа - смоллтолк-система, которая вертится на виртуальной машине. Виртуальная машина, как вы могли догадаться, написана на смоллтолке :-). При этом С-рантайм, на котором собственно вертится эта виртуальная машина очень маленький, например у Squeak исполняемый файл весит всего 1 Мб, что даже меньше чем размер текущей версии флэш-плеера!!! Основная же функциональность вынесена в виртуальную машину, которая в Squeak на данный момент весит ~17 Мб. За счет такого положения дел Squeak чрезвычайно хорошо портируем ). Похожим может похвастать Java. В ней тоже основные библиотеки (коллекции, IO, регекспы, дата-время, графич. библиотека) написаны на ней самой, благо скорость работы Java'ы это позволяет. Преимущества такого подхода очевидны. На текущий момент ни питон ни руби не могут похвастать подобным (. Подробнее об архитектуре можно прочитать тут и тут.
Однако, отвлеклись )). Архитектура смоллтолка в реализации Squeak выглядит так: на маленьком си-рантайменном ядре вертится виртуальная машина, на виртуальной машине вертится смоллтолк-система.
Сама смоллтолк-система тоже очень интересная сущность. Это исключительно динамичная (абсолютно все параметры системы можно менять на лету) система. Сказать кратко - это мини-ось, а что, в качестве шелла Workspace+Transcript, в качестве скриптового языка - его величество, Смоллтолк, рабочий стол, Morphic'овские окошки, графика (1, 2, 3))) Только не смейтесь, реализация в виде ОС тоже есть).
В смоллтолке реализована так называемая инкрементальная компиляция. Т.е. создавать классы и методы, а так-же менять методы вы можете на лету. При этом каждый раз, когда Вы говорите системе Accept некоторый код, этот код компилируется. Это возможно, потому что в Смоллтолк-системе существует порожденный экземпляр компилятора, который и выполняет данную работу)) Продолжая параллели с Java'ой - в джаве тоже замечательно, что компилируя проект, вы компилируете только еще не скомпилированные классы, при этом вам совершенно не нужно иметь исходники используемых библиотек.
Кроме того Смоллтолк предоставляет поистине невообразимые, чудовищные, колоссальные, уникальные, невероятные (эко меня торкнуло) средства для интроспекции уже работающей программы (кода). Тем более невероятно, вы можете воздействовать на работающую программу (изменять ее параметры) прямо на лету, и вам для этого не нужно ставить брекпойнты, проходить в пошаговом режиме (как в Java), вы как бы можете вклиниваться в работающую программу и подхачивать ее, не останавливая. Небольшой наглядный пример. Перед вами окошко, в котором летают шарики, отбаваясь от стенок (типа, модель газа). Вы в состоянии затормозить часть шариков, удалить, перекрасить, наблюдать за изменением их скоростей, все это на лету (Используя Inspect It, Explore It).
И вот таким динамизмом эта среда пронизана польностью ).
Что еще интересного. Исключения. В смоллтолке они особенные. Взять Java'у. В ней, если произошло исключение, стек вызовов методов как бы "раскручивается", и мы попадаем в некоторый catch блок. В смоллтолке все хитрее!! Там стек не раскручивается. И после произошедшего исключения вы можете продолжить выполнение программы. Пример. Вы написали код, запускаете - упс, исключение - перед вами возникает окошко с названием исключения, стеком вызовов, и тремя кнопками (Proceed, Abandon, Debug). Вы по стеку вызовов перемещаетесь в точку возникновения исключения, исправляете, делаете Accept, и жмете Proceed, программа побежала дальше. Красота )) В какой Java'е, Python'е, Ruby это возможно?
Ну и последнее. Когда вы выходите из системы она (система) сохраняется на диск в виде образа. Образ - это есть дамп запущенной (работающей) системы! Там хранится весь введенный вами код, все запущенные программы, все установленные пакеты, и т.д. По сути вся система (та самая большая живая неразрывная программа) сериализуется  на диск. А при следующем запуске загружается! Это очень удобно, хоть и довольно непривычно. (Предствьте, у вас запущен сервер. Вы выключаете систему, затем через время включаете, и севрер вновь запущен как ни в чем не бывало). Можно иметь несколько образов с разным набором установленного ПО, или с разной конфигурацией, кроме того разные довольно большие проекты (Seaside, Croquet) имеют обыкновение распространяться в виде отдельных образов, хотя обычно их можно установить и как пакеты.
Ладно, пока достаточно ). Тут еще не затронуты вопросы о континуациях (продолжениях), блоках кода (замыканиях) и других интересных вещах. Но хорошего по немножку. До связи!
UPD. Сдается мне в архитектуру вкралась досадная неточность, на самом деле, виртуальная машина написанная на смоллтолке автоматически конвертируется в исходники си, которые затем компилируются в исполняемый код. Это удобно, т.к. можно отлаживать виртуальную машину в смоллтолк-среде, а потом когда все работает как надо автоматически получить корректные ее си-исходники. Вот так то)


Пожалуй, начнем...))
2007-05-04T10:26:00.000-07:00
Надо что-то написать в первом посте... Блин, это мой первый блог, не знаю с чего начать))
Ну в общем так.. Я завел блог, во-первых, потому, что это нынче модно, ну а во-вторых, потому что хочу поделиться с вами (моими будущими читателями) тем что мне интересно, и, возможно, заинтересовать Вас в этом.
Немного о себе: 21 год, студент МФТИ, 5 курс, работаю программистом-аналитиком в некой оффшорной компании, занимаюсь J2EE-технологиями.
Что же все таки мне интересно: разумеется Java, хотя, впрочем как и все остальное: различные интересные концептуальные языки программирования (Python, Ruby, Smalltalk), вообще философия программирования, веб-технологии, agile development, как впрочем и RIA (в прошлом работал Flash-погромистомпрограммистом), да и сейчас приходится иногда садиться за Flex, хотя в некоторых кругах его вполне обоснованно принято ругать, Flash, AJAX, ... Так, что-то точно упустил, ну ладно, потом наверстаем))
Добавлю вот еще что, моя позиция такова - нужно использовать тот инструмент, который вам нравится использовать и с которым вы продуктивны, однако здравого рационализма и постоянного самосовершенствования и поисков (нового|лучшего) никто не отменял.
До связи!