thedeemon: (Default)
В свежем номере ПФП замечательная статья про продолжения. К сожалению, в качестве примеров там зачем-то приведены дампы памяти интерпретатора плохо типизированного лямбда-исчисления, формат которых некоторые ошибочно называют языком программирования. К счастью, история знает пример настоящего языка программирования с поддержкой продолжений - Руби версий до 1.8 включительно (поскольку поддержка продолжений была одной из причин тормознутости интерпретатора, а сами продолжения никому не нужны, то в версии 1.9 их выкинули).

Посмотрим, как на Руби выглядит пример с поиском общего префикса у деревьев. По условию задачи у нас есть некая структура данных (в данном случае дерево) и для нее есть функция, которая последовательно обходит элементы и для каждого вызывает наш callback. Т.е. это активный итератор в стиле Руби, в отличие от пассивных итераторов в стиле С++/C#/Java. Пусть наше дерево представлено массивом, элементы которого могут быть либо листьями дерева, либо такими же массивами-деревьями:
tree1 = [1, [2,3], [[[4,5], 6]], 7, 8]
tree2 = [[1,2], [[3,4], 0,0], 1]
Тогда итератор выглядит так:

def iterate_tree(tree, &f)
if tree.is_a? Array
tree.each{|x| iterate_tree(x, &f) }
else
yield tree
end
end
Чтобы вывести последовательно все элементы дерева его можно использовать так:
iterate_tree(tree1) {|x| print x}
Теперь мы хотим определить для двух деревьев длину общего префикса - число совпадающих при последовательном обходе с начала листьев, используя такие итераторы, но не обходя деревья целиком. Для этого при создании колбэка сохраним контекст вычисления главного потока в виде продолжения с именем main_thread, вызванный итератором колбэк будет вызывать это продолжение, тем самым передавая управление главному потоку, а также передавая ему параметром собственное продолжение под именем iteration_thread, которое, будучи вызванным из главного потока, продолжит работу колбэка, чтобы итератор продолжил работу и пошел на следующую итерацию, где все повторится. Главный поток на каждой итерации цикла передает свое продолжение main_thread, которое колбэк внутри себя обновляет, чтобы возвращаться не в начало обхода, а в нужное место. Звучит страшно, но код довольно короткий:
def start_iteration(tree, main_thread)
iterate_tree(tree) {|x|
main_thread = callcc {|iteration_thread|
main_thread.call(x, iteration_thread)
}
}
main_thread.call(nil, nil)
end

def loop(iter1, iter2, n)
x1, it1 = callcc { |main_thread| iter1.call(main_thread) }
x2, it2 = callcc { |main_thread| iter2.call(main_thread) }
if x1 && x2 && x1==x2 then loop(it1, it2, n+1) else n end
end

def prefix_length(tr1, tr2)
loop( lambda {|c| start_iteration(tr1,c)}, lambda {|c| start_iteration(tr2,c)}, 0 )
end
В функции loop мы передаем продолжение главного потока main_thread в продолжения итераторов, получая назад элементы деревьев и новые значения продолжений итераторов. Если оба элемента получены и они равны, то увеличиваем счетчик и идем на следующую итерацию, иначе возвращаем текущее значение счетчика.

Если вызвать prefix_length для описанных выше tree1 и tree2 и вывести результат,
p prefix_length(tree1, tree2)
будет выведено 4.
thedeemon: (Default)
Питер Норвиг зачем-то написал на Питоне интерпретатор небольшого подмножества Схемы в 90 строк кода. Дабы слегка посрамить этот гадкий питон, я перевел Норвиговский интерпретатор на Руби и заодно добавил туда поддержку продолжений, важной фичи Схемы, которую в питоний интепретатор должно быть вставить заметно сложнее. Такой вот пример
(begin
 (define fact (lambda (n) 
  (if (<= n 1) 1 (* n (fact (- n 1))))))
 
 (define f (lambda (return)
   (begin
    (return 2)
    1)))

 (display (f (lambda (x) x)))
 (display (callcc f))
 (fact 5)
)

выдает 1, 2, 120. Здесь return - не конструкция языка, а имя переменной, получающей текущее продолжение.
Выложил здесь.

Получилось всего 60 строк. Let the срачь begin! ;)
thedeemon: (Default)
Не раз уже видел восторженные отчеты об успешном применении Эрланга в задаче скачивания большого числа файлов. На мое замечание, что распараллеливание кучи одинаковых независимых заданий - невелико достижение, мне ответили, что для обычных императивных языков это вполне достижение. Сегодня я сам столкнулся с такой задачей, и на совершенно императивном языке Руби задача решилась очень просто.

Read more... )
class Array
 def par_map(nt, &f)
  slices = Array.new(nt) {|i| self[i*length/nt...(i+1)*length/nt] }
  threads = slices.map {|xs| Thread.new { xs.map &f } }
  threads.inject([]) {|r, t| r + t.value}
 end
end
Read more... )
thedeemon: (office)
На днях доделывал новый кодек, в одном месте занятная загогулина получилась.
Нужно, чтобы незарегистрированная версия при кодировании через N кадров или M секунд после начала работы (что произойдет раньше) рисовала на видео похабную надпись большими красивыми буквами, тем самым побуждая к регистрации. Рисовать надпись обычными средствами GDI плохо - векторным шрифтом это делать медленно, да и нужного шрифта у пользователя может не быть. Быстрый вариант - накладывать картинку с прозрачностью. Но ее слишком легко заменить на полностью прозрачную, сам так делал с одним скринсейвером. :) К тому же, хочется какой-то защиты от взлома - чтобы так просто надпись было не убрать.
Воспользовался привычным решением, которое успешно применял в предыдущих продуктах - функциональность, которую хочется защитить от взлома, пишется на моем DSEL, который компилится в байткод простенькой регистровой виртуальной машины. Получилось следующее. Нарисовал нужную картинку нужным шрифтом в графическом редакторе, превратил в монохромную, сохранил. Дальше моя программка на Окамле прочитала картинку и прошлась по ней чем-то вроде RLE, превратив в такой примерно текст:
[[
  [119,5]
],
[
  [117,3], [3,4]
],
[
  [67,1], [56,4], [69,1], [9,19], [3,19], [4,5], [7,5], [5,5], [17,5]
],
[
  [11,2], [6,2], [9,2], [6,2], [8,2], [6,2], [7,4], [5,3], [3,3], [17,5], [2,6], [15,5]
],
[
  [11,2], [5,3], [8,3], [5,3], [8,3], [5,3], [6,5], [4,3]
],
...
]
Каждая строка картинки кодируется последовательностью пар чисел - число прозрачных точек, число непрозрачных. Записаны данные намеренно в синтаксисе Руби. А дальше происходит вот что.
Код, который будет выполняться в ВМ, у меня пишется на С-образном язычке, являющимся DSEL Руби. Т.е. синтаксически это код на Руби, который в результате выполнения порождает скомпилированный код ВМ. А раз это код на Руби, то у меня есть полная свобода действий во время компиляции - Руби выступает в качестве мета-языка. И вот, во время такой компиляции я читаю из файла описание картинки в виде того массива и прохожусь по нему, на каждой итерации цикла порождая кусочек кода для ВМ:
____________________________________________________
def drawwm(x, y, pSrc, stride, lines, bpp)
  sy = _int(y/2 - 30)
sx = _int(x/2 - 128)
pPic = _pbyte
j = _int
for ny in 0...lines.length if lines[ny].length > 0 pPic.point(pSrc + (sy+ny)*stride + sx*bpp) for pair in lines[ny] pPic.add(bpp * pair[0])
_for(j <= 0, j < bpp * pair[1], j.inc) {
pPic <= 81
pPic.inc
}
end end end end lines = open('lines.rb') {|f| eval(f.read) } _if(draw > 0) {
_if(bytespp.eq(2)) {
drawwm(x, y, pSrc, stride, lines, 2)
}.else {
drawwm(x, y, pSrc, stride, lines, 3)
}
}
____________________________________________________

Здесь синим обозначены конструкции, которые генерят код для ВМ, это как бы run-time, а черным - то, что происходит в compile-time, в частности, выражения типа bpp * pair[0] превращаются в сгенеренном коде в константы. Compile-time функция drawwm вызывается дважды - с разными значениями числа байт на пиксел, что приводит к генерации двух рисующих кусков кода, отличающихся лишь конкретными значениями констант. Т.е. налицо partial evaluation. В итоге, для каждой пары чисел из того массива, например [4,5], генерится такой вот код (bpp=3):

ADD|RV, 23, 12,  # перепрыгиваем через 4 точки
MOV|RV, 24, 0,   # обнуляем счетчик цикла
LE|RV, 24, 15,   # цикл на 5 точек - 15 байт
JZ, 13,
MOVB|PV, 23, 81, # пишем в картинку 
ADD|RV, 23, 1,   # увеличиваем указатель на место рисования и счетчик цикла
ADD|RV, 24, 1,
JMP, -14,        # конец цикла

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

Profile

thedeemon: (Default)
Dmitry Popov

May 2017

S M T W T F S
 1234 56
789 10 11 1213
14151617181920
21222324252627
28293031   

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 23rd, 2017 02:53 pm
Powered by Dreamwidth Studios