Програзм's Journal
 
[Most Recent Entries] [Calendar View] [Friends]

Below are the 19 most recent journal entries recorded in Програзм's LiveJournal:

    Wednesday, April 27th, 2011
    5:16 pm
    [mao]
    Может кто-нибудь подсказать, как доказать, что языки с "циклической" структурой (где для выражения токенов используется рекурсия) не могут являться регулярными ?
    Monday, April 26th, 2010
    8:12 pm
    [mao]
    PERL САМЫЙ ЛУЧШИЙ
    subj
    Sunday, September 20th, 2009
    10:39 pm
    [olegmi]
    Кто может подсказать идею файловой системы для носителя, который предназначен ТОЛЬКО для дописывания? Объем файловой структуры ОЧЕНЬ большой. Думаю, около терабайта. Нужна приятная идеология. Арвидную систему знаю... Что еще есть?
    Wednesday, October 8th, 2008
    12:18 pm
    [olegmi]
    Чем отличается структура от класса кроме методов? Следует ли данные объявлять структурой или классом? Есть на эту тему какой-то концепт?
    Wednesday, August 29th, 2007
    2:46 pm
    [polytheme]
    вопрос по OCaml/Camlp4
    фолды часто выглядят невнятно.
    хочется писать что-то вроде

    let fold elt<-l into accu:ISet.empty = ISet.add elt accu in
    print_endline (ISet.to_string accu)

    (или что-то подобное).
    интересно, camlp4 может нам тут помочь ?
    Monday, August 27th, 2007
    5:30 pm
    [polytheme]
    еще о нём же
    появился вариант, способный грузить динамические
    библиотеки в native-варианте. подробности см.

    http://alain.frisch.fr/natdynlink.html

    там же предлагают ocamlnat, toplevel, в реальном
    времени компилирующий в native и подгружающий.

    попробовавшие говорят, что ускорение по сравнению
    с обычным ocamltop колоссальное (раз в сорок)
    3:12 pm
    [polytheme]
    красивые грабли: OCaml
    о прекрасном.

    написал чудесный функтор
    module type Holder =
    sig
    type t
    end

    module Comparable(H:Holder) =
    struct
    type t = H.t
    let compare = compare
    end

    прекрасно применяется, между прочим, к целым,
    строкам, декартовым произведениям, вариантам ...

    и всё бы было ничего, но функция
    lim f eq start =
    let next = f start in
    if (eq start next) then next
    else lim f eq next
    (которая весьма полезна для набивки множеств,
    получения связных компонент графов и
    всего такого прочего) у меня зациклилась
    (на Map[Comparable[Set[...]]] и этот самый
    compare = 0)

    мораль проста ... )
    Tuesday, July 17th, 2007
    1:23 pm
    [polytheme]
    ocaml lablgtk2
    вопрос - пытался ли кто-нибудь компилировать lablgtk2 под msys/mingw ?
    имеются проблемы - под windows почему-то отсутствует ocamlmklib,
    ocamlmktop глючит, и т.д.
    все это обходится - код у mklib несложный, и все, что она делает,
    можно сделать вручную и т.д. (также проблема в том, что
    ocaml под windows генерирует "неправильные" слэши для
    имени, например, временных файлов и т.д.).
    это не очень сложно поправить, исходники ocaml удивительно
    внятные, но интересно, не решал ли кто-нибудь уже эту задачу.
    Monday, July 9th, 2007
    1:58 pm
    [polytheme]
    еще про заключенных (романтическое)
    троих заключенных сажают в три одиночки. в каждой одиночке
    на стене лампочка. каждая лампочка либо горит, либо не горит
    в течение дня.
    заключенным известно, что лампочки переключаются по одной из
    двух стратегий. согласно первой, каждый день горят ровно
    две из трех. согласно второй, некоторое количество дней
    (неизвестное) в начале срока горят ровно две из трех,
    а остаток срока - ровно одна из трех.
    так они сидят натуральную вечность (1,2,3,...).
    по окончании вечности они должны, не советуясь,
    проголосовать - каждый за ту стратегию, которая,
    по его мнению, применялась.
    перед началом срока они могут советоваться
    сколько угодно.

    существует ли метод голосования, позволяющий угадать
    применявшуюся стратегию большинством голосов ?
    Saturday, July 7th, 2007
    9:53 am
    [izh]
    Задачка
    Для оживления коммьюнити вот еще одна задачка:
    имеется тюрьма, в которой сидят по одиночным
    камерам N заключенных. В тюрьме так же есть
    комната с двумя рубильниками, у каждого
    рубильника два положения (вкл/выкл), начальное
    положение рубильников неизвестно.

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

    Задача в том, чтобы придумать эту выигрышную
    стратегию.

    PS: Условие "достаточного количества вызовов" и
    произвольности порядка вызова можно сформулировать
    так: при стремлении к бесконечности общего числа
    вызовов в комнату, число вызовов каждого конкретного
    ЗК также стремится к бесконечности некоторым
    произвольным (не обязательно случайным!) образом.

    PPS: Комменты скринятся.
    Sunday, June 24th, 2007
    7:27 pm
    [izh]
    Простая задачка (с красивым решением)
    Имеется последовательность из N объектов,
    про любые два из которых можно сказать только
    равны они или нет. Известно, что некоторого
    объекта в последовательности больше половины.
    Придумать алгоритм поиска этого объекта,
    который бы завершался за один проход по
    последовательности и использовал фиксированный
    (то есть не зависящий от N) объем памяти.

    Комменты скринятся.

    Пояснение:

    Понятно, что количество бит, при помощи которых
    можно закодировать число N зависит от N, но
    конкретно этой зависимостью можно пренебречь.
    Также понятно, что от размера объекта зависит
    объем используемой памяти. Этой зависимостью можно
    также пренебречь. Существенно, чтобы количество
    используемой памяти не зависело от количества
    элементов в последовательности.

    Решение (выделить мышкой):

    Одно из возможных решений основывается на том
    интересном факте, что из последовательности
    можно выкинуть 3 произвольных попарно неравных
    элемента. При этом количество искомых элементов
    по прежнему будет больше половины в уменьшенной
    последовательности. Другое решение (более простое),
    предложенное Димой Калединым, также использует 
    индукцию. Понять, как именно, предоставляется 
    читателю в качестве упражнения.
    
    Для простоты в решении рассматривается массив из
    целых чисел. Алгоритмы, впрочем, будут работать для
    любых объектов.
    
    Мой вариант решения:
    
    int find_most_repeatable(int *arr, size_t size)
    {
        unsigned int        i;
        int                 a, b = 0, e, answer_a, answer_b, answer;
    
        answer_a = arr[0];
        a = 1;
        
        for (i = 1; i < size; i ++)
        {
            e = arr[i];
        
            if (answer_a == e && a > 0)
                a ++;
            else if (answer_b == e && b > 0)
                b ++;
            else
            {
                if (a == 0)
                {
                    answer_a = e;
                    a = 1;
                    continue;
                }
                else if (b == 0)
                {
                    answer_b = e;
                    b = 1;
                    continue;
                }
    
                a --; b --;
            }
        }
    
        if (a >= b)
            answer = answer_a;
        else
            answer = answer_b;
        
        return answer;
    }
    
    Вариант Димы Каледина (исправленный):
    
    int find_most_repeatable2(int *arr, size_t size)
    {
        unsigned int        i;
        int                 answer, e, c;
        
        answer = arr[0];
        c = 0; 
        for (i = 1; i < size; i ++)
        {
            e = arr[i];
    
            if (answer == e)
            {
                c ++;
                if (c <= 0)
                    c ++;
            }
            else if (c >= 0)
                c --;
    
            if (c < 0)
                answer = e;
        }
    
        return answer;
    }
    

    Wednesday, October 25th, 2006
    5:30 pm
    [peter_lemenkov]
    Erlang и утечка памяти.
    Почему это течет? Функция select_calls вызывает себя рекурсивно, но, вроде как tail recursion, так что все нормально.

    под кат! )

    Если в функции select_calls закомментировать вызов send_msg, то ничего не течет. Так как же в erlang'е правильно строки-то отсылать через socket?
    Thursday, October 19th, 2006
    10:23 pm
    [peter_lemenkov]
    Цикл на Erlang'е
    Приветствую!

    Что-то я недопонял. Как заставить выполнить кусок кода, скажем, шесть раз.

    Дано:

    unixODBC, откуда я читаю записи вот так:

    main_cycle (Ref) ->
    	case odbc:select_count(Ref, "select A,B,C from name.table") of 
    		{ok, NumberOfRows} ->
    			if 
    				NumberOfRows > 0 ->
    					select_calls(Ref)
    			end;
    		Error -> 
    			exit(Error)
    	end.


    В вышеуказанной функции я получаю NumberOfRows например равным шести. Я не нашел ничего лучше, как рекурсивно выполнить select_calls до тех пор, пока мне не сообщат об ошибке:

    select_calls(Ref) ->
    	case odbc:next(Ref) of 
    		{selected,["CS_CALLED_STATION_ID","CS_CALLING_STATION_ID","CS_LOCALCALLID"], [{Caller,Called,SessionID}]} ->
    			write_msg(Caller,Called,SessionID),
    			select_calls(Ref);
    	Error -> 
    		io:format("end of data\n")
    	end.


    Запросить сразу лист записей, а потом сделать map или foreach нельзя, т.к. драйвер базы данных (Oracle) для unixODBC еще не дописан до конца (а фирменный от Oracle или другой коммерческий от Easysoft настолько проблемно ставится, что проще будет пока с этим повозиться) и не позволяет селектом выдавать сразу лист - только так, по одной записи.

    Так вот, хотелось бы не дожидаться пока odbc:next выбросит ошибку, а выполнить его столько, сколько мне надо.

    Как?
    А то я что-то этот момент упустил пока. В туториалах есть много-много про параллельное программирование и кластеризацию ,а вот такой момент что-то обойдет вниманием.

    Я хотел добавить лишний параметр в вызов функции, что-то вроде

    select_calls(Ref, counter) ->
    	if
    		counter > 0 ->
    			...
    			select_calls(Ref, counter-1);
    	end.


    но это почему-то не работает.
    Wednesday, May 17th, 2006
    5:40 pm
    [ifp5]
    OCaml SNMP
    Недавно разгребал старые архивы и обнаружил враппер библиотеки Net SNMP для OCaml. Интересно, кому-нибудь кроме меня такое может понадобиться? :>

    /me думает, стоит ли его приводить в порядок (местами оно довольно страшное в духе потока сознания) и выкладывать куда-нибудь. Самому в настоящий момент не надо.

    P.S. Использование выглядит примерно так.
    Saturday, January 7th, 2006
    2:17 am
    [delamon]
    Переписываем и хаскеля в камл
    Тут в http://www.livejournal.com/community/ru_lambda/5507.html написана замечательная программа.
    Я попытался переписать ее на камл, получилось почти буква в букву:
    let  scanl f i l = 
      let rec aux i = function
          [] -> []
        | x :: xs -> 
            let ir = f i x in
              ir :: (aux ir xs) in
        i :: (aux i l)
    
    let flip f a b = f b a
    
    let rec rmake = function
        0 -> []
      | n -> n :: (rmake (n - 1))
    
    let lmake n =  List.rev (rmake n)
    
    let (^) f g x = f (g x)
    
    let apply f x = f x
    
    (**************)
    
    let move (top::xs, ys, zs) = (xs, top::ys, zs)
    
    let yz (x,y,z) = (x,z,y)
    let xz (x,y,z) = (z,y,x)
    
    let twist g f = g ^ f ^ g
    
    let rec moves = function
        0 -> []
      | n -> List.map (twist yz) (moves (n - 1)) @ move :: List.map (twist xz) (moves (n - 1))
    
    let hanoi n =
      scanl (flip apply) ((lmake n), [], []) (moves n)
    

    за тем малым исключением, что пришлось написать часть библиотечных функций.
    Что самое забавное, hugs, который в debian/stable, падает по sigv раньше, что ocaml(top) начинает говорить stack overflow. Желающие могут проверить ocamlopt :-)

    PS: битик в unboxed values воруется для того что бы всегда можно было знать что это: значение или указатель. Именно из-за этого у камла быстрая арифметика.
    Monday, December 12th, 2005
    3:37 pm
    [ifp5]
    А есть ли тут схимники? (schemers)
    %subj%

    Интересует как в scheme производится обработка исключений наиболее распространенным образом? Исключения интересуют, конечно, связанные с внешней средой, типа ошибки при открытии файла (про call/cc я в курсе и он тут никак не поможет).

    R5RS читал (не очень, впрочем, внимательно), но такого не обнаружил. Google при поиске типа "scheme exception handling" выдает десятки различных вариантов.

    P.S. Есть о'камловая программа, в которой в качестве языка конфигов используется примитивное подмножество scheme (написанное мною давным-давно за пару дней и даже без tail рекурсии). Думаю заменить свою убогую реализацию на ocs или schoca (скорее всего, на ocs) и вынести часть функциональности в конфиги. Обработку исключений придется, похоже, дописывать самому. Так вот интересует, стоит ли что-то брать за образец или изобретать велосипед самому?
    Friday, November 18th, 2005
    12:35 pm
    [kouzdra]
    Реализация вызова метода в O'Caml
    На самом деле идея простая, но красивая.

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

    В месте, где создается объект, компилятор как правило ничего не знает о том, что
    где-то этот объект будет использоваться с конкретной сигнатурой. В отличие от
    языков, где иерархия основана на наследовании все предки в месте создания объекта
    известны, O'Caml базируется на отношинее subtyping'a.

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

    Все имена методов нумеруются глобально по всей программе. Это может делать линкер, в
    O'Caml это делается динамически при запуске программы. Далее в качестве VMT можно использовать
    таблицу длины n_meth, где n_meth - количество имен методов. В пустующие клетки не записывается
    ничего, в остальные - адреса функций.

    Вызов делается просто - по номеру метода берется соотвествующий адрес и вызывается. Статическй
    контроль гарантирует, что метод с данным именем/номером будет.

    Идея хороша всем, кроме того, что n_meth может быть довольно большим (напирмер 1000), а заводить для каждого класса
    (пусть 200 классов) табличку в 1000 слов несколько накладно - даже тут уже получится мегабайт. Это при
    весьма умеренных n_meth и числе классов. Опять же - понятно, что таблики будут почти пустые.

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

    Далее - в начало таблицы записывается подобранное p, а адреса методов располагаются в позиция по модулю
    p. Вызов метода соотвественное делается просто - берется остаток от деления номера метода на p из таблицы
    и вызывается то, что лежит по адресу.

    Придумал это Didier Rémy в 1992 года:


    Efficient Representation of Extensible Records. In Proceedings of the 1992 workshop on ML and its Applications, page 12, San Francisco, USA, June 1992
    Monday, November 7th, 2005
    10:59 pm
    [kouzdra]
    Про объекты в O'Caml:
    Объектность там забавная и в каком-то смысле очень оригинальная

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

    То есть: "объектный тип" (АКА class type - типы, которые приписываются
    значениям объектам) - это сигнатура. То есть - список методов,
    которые должны быть у объекта + их типы. Ну например -

    type p2d = < x : int; y : int > 


    тип, которому соотвествует любой объект, у которого есть методы x и y,
    возвращающие int. Соотвественно - естественным путем возникает
    отношение тип-подтип между объектными типами. Оно и заменяет наследование.
    Важно не то, как объекты образоывывались, а что они умеют.


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

    type eq = < eq : 'a -> bool > as 'a


    Тут это тип объекта, у которого есть метод eq, ожидающий получить параметром
    объект в точности того же самого типа. Понятно, что трехмерная точка
    будет одноврменно и двумерной, но сравнение на = разнородных точек вряд ли уместно.

    Наследование, конечно, есть, но это конструкция скорее синтаксическая -
    вместо использования inherit, можно просто повторить все тоже самое
    руками. Результат, за исключением тонких нюансов, отличаться не будет:
    class p2d (x:int) (y:int) = object (self:'self)
        method x = x
        method y = y
        method eq (a: 'self) = self#x = a#x && self#y = a#y
    end
                                                                                                    
    class p3d (x:int) (y:int) (z:int) = object (self:'self)
        inherit p2d x y as super
        method z = z
        method eq (a: 'self) = super#eq (a :> 'self) && self#z = a#z
    end
                                                                                                    
    class p3d' (x:int) (y:int) (z:int) = object (self:'self)
        method x = x
        method y = y
        method z = z
        method eq (a: 'self) = self#x = a#x && self#y = a#y && self#z = a#z
    end
                        
    let p2 = new p2d 1 2                                                                             
    let p3_1 = new p3d 1 2 3
    let p3_2 = new p3d 1 2 3
    let _ = Printf.printf "%b\n" (p3_1#eq p3_2)
    


    Разницы между p3d и p3d' с точки зрения типов нет никакой. Типы
    у них идентичны.

    Обращу внимание,что
    p2#eq p3_1
    написать нельзя. Будет
    ошибка типизации.

    Вот вкратце все.

    Как это реализуется (а вызов метода делается за константное время),
    будет в следующем номере.
    Wednesday, November 2nd, 2005
    12:06 am
    [kouzdra]
    Для затравки
    Представление данных в O'Caml (и вообзще -ML):

    На самом деле - оно очень красиво. Что самое забавное - на С изобразить
    это можно, но задолбаешся. Итак:

    1) никакого RTTI в O'Caml нет. Нет настолько, что сделать downcasting в
    объектном расширении просто невозможно технически.

    2) Представление данных там стольже прямолинейно и тупо как в Pascal.

    3) Что есть - есть следующее:

    Все типызначения представляются в O'Caml одним словом и делятся на boxed
    и unboxed. Boxed - это те, которые лежат в куче, а представляются адресом в оной.
    Unboxed - представляются своим физическим значением, сдвинутым влево на 1 бит и
    1 в младшем бите. Потому, собственно, int в O'Caml не 31, а 30 битов.

    Unboxed values - int, char, bool, unit (да - у него есть значение - нолик),
    и элементы union's (АТД) без "of ...".

    Boxed - все остальное. Соотвественно как представляются

    type 'a Tree = E | N of 'a tree * 'a * 'a tree

    Вариант E - просто 0 (с учетом сдвига и битика - 1)
    вариант N - адрес блока, в котором лежит три слова - элементы узла.
    Сам тэг (1) лежат в управляющем слове по смещению -4 от адреса.

    Вот. Общая идея, надеюсь, понятна. На самом деле вся "информация о типах" в run-time
    сводится к этому самому младжему битику, который отличает значение от адреса. Более
    - ничего. Какие-то вещи (вроде сериализации или полиморфного сравнения) на этом
    сделать можно. Но вообще-то мало что можно.
About LJ.Rossia.org