Здравствуйте, Gaperton, Вы писали:
G>Вообще — общий вывод такой: функциональная чистота радикально упрощает дизайн — фактически, она устраняет его как геморройную и ответственную фазу, к которой мы привыкли в ОО. Конкретнее — спасает отсутствие указателей, референсов, и изменяемого состояния. Из-за этого рефакторинг обходится дешевле на порядок — его просто не замечаешь. И дизайн элементарен — это уже не настолько трудоемкая и ответственная фаза. Думать нужно только о связности и группировке функций. Халява полная.
G>А вот с процессами мы таки получим обратно изменяемое состояние и референсы. Тогда и начнется самое интересное.
а хвостовая рекурсия? получил сигнал, пересчитал состояние и всё:
-- ход противника
chess state = do move <- getChannel c
chess2 (applyMove state move)
-- наш ход
chess2 state = do let move = calcOurMove state
putChannel c move
chess (applyMove state move)
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
G>>Вообще — общий вывод такой: функциональная чистота радикально упрощает дизайн — фактически, она устраняет его как геморройную и ответственную фазу, к которой мы привыкли в ОО. Конкретнее — спасает отсутствие указателей, референсов, и изменяемого состояния. Из-за этого рефакторинг обходится дешевле на порядок — его просто не замечаешь. И дизайн элементарен — это уже не настолько трудоемкая и ответственная фаза. Думать нужно только о связности и группировке функций. Халява полная.
G>>А вот с процессами мы таки получим обратно изменяемое состояние и референсы. Тогда и начнется самое интересное.
BZ>а хвостовая рекурсия? получил сигнал, пересчитал состояние и всё:
BZ>
BZ>-- ход противника
BZ>chess state = do move <- getChannel c
BZ> chess2 (applyMove state move)
BZ>-- наш ход
BZ>chess2 state = do let move = calcOurMove state
BZ> putChannel c move
BZ> chess (applyMove state move)
BZ>
Это чистый код. Тут ссылок нет. В Эрланге у процесса есть identity — pid, зная который, ты можешь послать ему сообщение. Этот pid можно передавать другим процессам. А у тебя здесь identity нет. Нет identity — нет агрегирования, владения, связей, и прочих проблем.
Здравствуйте, red75, Вы писали:
R>Здравствуйте, Gaperton, Вы писали:
R>>>Хм. А ведь Cell — это, в общем-то, простое хранилище, однозначно определяемое по {Ref,Table}. Почему-бы не вынести cell:evaluate, cell:eval_and_get в Table?
G>>Склеить их в принципе можно. Однако, стоит объяснить, почему они разделены.
R>Нет, я не говорю о склеивании. Связь Cell->Table осуществляется только через table:get_cell, но зачем Cell'у знать как получать значения из таблицы? Это нужно только для expression.
Интересно. А ведь и в самом деле.
G>>Только зная внутреннюю структуру типа cell, мы сможем понять, что внутри лежит формула. Перенеся этот код в модуль sheet, мы получим более сильную связность — потому что человек, разбирающийся в устройстве sheet, не сможет понять его, не разобравшись в деталях cell. А это именно то, чего мы хотим избежать.
R>Я имел в виду: R>
Хм-м-м... В результате одним махом убираем связь от cell к sheet, и от expression к cell. Гениально. Отлично, спасибо!
G>>Однако, cell этого не знает, плевать cell-y, как устроен expression. Он знает, что expression можно создать G>>create( string() ) -> expression() G>>и вычислить G>>evaluate( Ref, expression(), sheet() ) -> { Value, sheet() }.
G>>Вот, кстати, тут виден реальный прощот. Value и Ref проходят явно в межмодульном интерфейсе. Вот это — ай-ай-ай. cell и expression слишком сильно связаны. Буду думать, как править.
R>Избавиться от передачи Ref'ов по-моему нельзя. Может запромотить его в АТД? Что-то вроде: R>
R>-module(table).
R>%% make_ref::(integer(),integer())->ref()
R>make_ref(X,Y)->{X,Y}.
R>-module(expression).
R>create_arg( [ Row, Col ] ) when Row >= $a, Row =< $z, Col >= $0, Col =< $9 ->
R> { ref, table:make_ref(Row - $a + 1, Col - $0) };
R>
Да, именно так я и собрался сделать. Т.е. в точности так. Вплоть до имен функций и модулей .
R>А на счёт Value бродят смутные мысли о разделении значения ячейки (формула/литерал/пусто) и вычисленного значения ячейки (число/строка/ошибка), но пока не оформились.
Именно такие мысли ходили и у меня. В первых внутримодульных тайпдефах у меня это так и разделялось — UnevaluatedCell и Cell. Однако красиво завернуть это в АДТ — я прощелкал. Просто пропустил. Заметил только сейчас, когда начал объяснять.
Вот, с твоей правкой по поводу evaluate + с решенными проблемами Value и Ref, можно будет поднять оценку дизайна с 4 (good enough) до 5 (perfect).
Прикольно дизайнить для Эрланга, правда? Ничего нет кроме модулей и функций, а насколько дофига оказывается можно сделать! Даже налажать можно .
Здравствуйте, Gaperton, Вы писали:
G>Это чистый код. Тут ссылок нет.
именно об этом я и говорю
>В Эрланге у процесса есть identity — pid, зная который, ты можешь послать ему сообщение. Этот pid можно передавать другим процессам. А у тебя здесь identity нет. Нет identity — нет агрегирования, владения, связей, и прочих проблем.
а на пальцах показать? с чистыми данными такая проблема — это и есть данные. хочешь — шахматную доску передавай, хочешь — состояние ядерного реактора. "не будет ни радио, ни газет, ни кино — одно сплощное телевидение"
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
G>>Это чистый код. Тут ссылок нет.
BZ>именно об этом я и говорю
>>В Эрланге у процесса есть identity — pid, зная который, ты можешь послать ему сообщение. Этот pid можно передавать другим процессам. А у тебя здесь identity нет. Нет identity — нет агрегирования, владения, связей, и прочих проблем.
BZ>а на пальцах показать? с чистыми данными такая проблема — это и есть данные. хочешь — шахматную доску передавай, хочешь — состояние ядерного реактора. "не будет ни радио, ни газет, ни кино — одно сплощное телевидение"
-module( my_object ).
-record( this, { member1 = "a", member2 = 1, ... } ).
new() ->spawn( fun dispatch/1, #members{} ).
set( This, Attribute, Value ) -> This ! { set, Attribute, Value }.
get( This, Attribute, Value ) ->
This ! { get, Attribute, self() },
receive { return, This, Value } -> Value end.
dispatch( Members ) ->
NewState = receive
{ set, member1, Value } -> Members#this{ member1 = Value };
{ get, member1, Caller } -> Caller ! { return, self(), Members#this.member1 }, Members;
...
end,
dispatch( NewState ).
-module( caller ).
...
Obj = my_object:new(),
"a" = my_object:get( Obj, member1 )
my_object:set( Obj, member1, "b" ),
...
"a" = my_object:get( Obj, member1 ), %% Ой! Эксцепшн bad_match! Значение то у нас вернулось - "b"!
Здравствуйте, Gaperton, Вы писали:
G>Так не получится. Вся сложность в алгоритме expression. Он вычисляет клетки рекурсивно. Когда он встречает в аргументе reference, ему надо вычислить значение в клетке, а там также может быть expression. Отсюда протягивается обратная ссылка на cell.
Каюсь, первая мысль была передавать в expression:evaluate функцию-разыменователь
evaluate(expression(), Ref->Value ) -> Value.
Это, конечно, плохо – нельзя исключить перевычислений и к тому же ни разу не идиоматически.
Но что если дать возможность узнать, на что ссылается выражение и передавать контекст для его вычисления?
Т>А обновлениями ячеек и порядком вычислений пусть рулит sheet.
Неплохо. Я с самого начала мельком подумал о таком подходе, но почему-то сразу его отмел и решил делать тупо — тот же алгоритм, как в плюсах. Однако, получается интересно.
Можно обойтись и простым списком значений — без dictionary. Тогда реально все вытягивается в трубу. Ты имеешь в виду вот это?
Это решение мне нравится существенно больше лобовой реализации типического плюсового алгоритма, как у меня. Попробую реализовать и этот вариант, как будет время.
Здравствуйте, Gaperton, Вы писали:
BZ>>а на пальцах показать? с чистыми данными такая проблема — это и есть данные. хочешь — шахматную доску передавай, хочешь — состояние ядерного реактора. "не будет ни радио, ни газет, ни кино — одно сплощное телевидение"
для меня этот некомментированный код — не на пальцах
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
BZ>>>а на пальцах показать? с чистыми данными такая проблема — это и есть данные. хочешь — шахматную доску передавай, хочешь — состояние ядерного реактора. "не будет ни радио, ни газет, ни кино — одно сплощное телевидение"
BZ>для меня этот некомментированный код — не на пальцах
spawn — создает процесс, берет параметром функцию, которая будет вызвана этим процессом, возвращает PID.
PID ! Message — отправляет процессу PID сообщение Message
Здравствуйте, Gaperton, Вы писали:
G>Да, именно так я и собрался сделать. Т.е. в точности так. Вплоть до имен функций и модулей .
R>>А на счёт Value бродят смутные мысли о разделении значения ячейки (формула/литерал/пусто) и вычисленного значения ячейки (число/строка/ошибка), но пока не оформились.
G>Именно такие мысли ходили и у меня. В первых внутримодульных тайпдефах у меня это так и разделялось — UnevaluatedCell и Cell. Однако красиво завернуть это в АДТ — я прощелкал. Просто пропустил. Заметил только сейчас, когда начал объяснять.
G>Вот, с твоей правкой по поводу evaluate + с решенными проблемами Value и Ref, можно будет поднять оценку дизайна с 4 (good enough) до 5 (perfect).
Насчёт Value: ими ведь занимается только Expression? Добавить туда (в expression) конструкторы Value и преобразование Value->string, ну а Cell будет хранить Value|expression().
G>Прикольно дизайнить для Эрланга, правда? Ничего нет кроме модулей и функций, а насколько дофига оказывается можно сделать! Даже налажать можно .
Эт точно. Впрочем минимизация связности — NP-задача. ХЗ как мы её вообще решаем .
Здравствуйте, red75, Вы писали:
R>Здравствуйте, Gaperton, Вы писали:
G>>Прикольно дизайнить для Эрланга, правда? Ничего нет кроме модулей и функций, а насколько дофига оказывается можно сделать! Даже налажать можно .
R>Эт точно. Впрочем минимизация связности — NP-задача. ХЗ как мы её вообще решаем .
А вообще, интересно есть какие-либо исследования/книги посвящённые этой теме? Что-нибудь с обобщённой точки зрения на вопрос, а не конретика по языкам и т.п.?
Или в основном это на базе интуиции? Но даже если так, то должны же быть какие-нибудь эвристики или типа того...
G>Так не получится. Вся сложность в алгоритме expression. Он вычисляет клетки рекурсивно. Когда он встречает в аргументе reference, ему надо вычислить значение в клетке, а там также может быть expression. Отсюда протягивается обратная ссылка на cell. Придется мне привести код, чтобы стало понятно.
G>Кстати, приглашаю поиграть в "пятнашки". Помоги мне, попробуй улучшить дизайн. Принципы дизайна, которые надо сохранить — очень простые: если ты посмотришь внимательно на код, то ты обратишь внимание, что модули не знают про структуры данных друг друга — между ними ходят либо абстрактные, либо очень простые типы данных. Предлагается это свойство сохранить, и попытаться уменьшить связность.
Поставив себя сразу в очень удобное от критики положение, тем что я здесь алгоритмами не занимаюсь, а только дизайном, G по сути дела прыгнул с головой в смоляную яму – отличная позиция. Полностью конечно отрешиться от алгоритмов не удалось, появилась какая-то жуткая мистика про живые процессы, которые должны быть мало связанны и не должны что знать друг про друга, а в следующем мастер классе можно будет сказать, что они наоборот теперь жестко связанны и все друг про друга знают. Конечно от геморроя это никак не избавит, а напротив усугубит еще в большей степени чем раньше. Это я могу гарантировать.
Поэтому еще так слаба пояснительная часть написанная псевдокодами, а чего пояснять –то?
Чистописание кода понравилось, я так не умею. Но сам язык беден.
Здравствуйте, sergesokolov, Вы писали:
S>Поэтому еще так слаба пояснительная часть написанная псевдокодами, а чего пояснять –то? S>Чистописание кода понравилось, я так не умею. Но сам язык беден.
Так ведь все просто: предложи лучшее решение
Здравствуйте, Gaperton, Вы писали:
G>Можно обойтись и простым списком значений — без dictionary. Тогда реально все вытягивается в трубу. Ты имеешь в виду вот это?
G>
G>-module( sheet ).
G>evaluate( Ref, Sheet ) ->
G> Value = get_cell( Ref, Sheet ), % цыклы не ловим, ломает. Понятно, как, но лень
G> { Context, NewSheet }= mapfoldl( fun evaluate/2, Sheet, cell:dependency_list( Value ) ),
G> NewValue = cell:evaluate( Value, Context ),
G> { NewValue, set_cell( Ref, NewValue ) }.
G>...
G>
Да, примерно это.
Но при случае можно разделить анализ зависимостей и собстванно вычисление.
evaluate( Ref, Sheet ) ->
Value = get_cell( Ref, Sheet ),
Context = lists:map( fun ( R ) -> get_cell( R, Sheet ) end, cell:dependency_list(Value) ),
cell:evaluate( Value, Context ).
evaluate( Sheet ) ->
DepGraph = build_depgraph(Sheet),
case digraph_utils:is_acyclic(DepGraph) of
true ->
RefList = digraph_utils:topsort(DepGraph),
lists:foldl( fun evaluate/2, Sheet, RefList);
false ->
...
end.
Здравствуйте, Курилка, Вы писали:
К>А вообще, интересно есть какие-либо исследования/книги посвящённые этой теме? Что-нибудь с обобщённой точки зрения на вопрос, а не конретика по языкам и т.п.?
Да я в общем-то ненастоящий сварщик. Поэтому советовать остерегусь.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, sergesokolov, Вы писали:
S>>Поэтому еще так слаба пояснительная часть написанная псевдокодами, а чего пояснять –то? S>>Чистописание кода понравилось, я так не умею. Но сам язык беден. C>Так ведь все просто: предложи лучшее решение
решение чего?
мистических вещей, тут одна словестная ловушка в той терминологии которую выдумавает G.
Бьен Страуструп тоже был в определенной степени мистик со скрытием данных, но у него была четкая цель, которой здесь сознательно нет.
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Gaperton, Вы писали:
G>>Можно обойтись и простым списком значений — без dictionary. Тогда реально все вытягивается в трубу. Ты имеешь в виду вот это?
Т>Да, примерно это.
Т>Но при случае можно разделить анализ зависимостей и собстванно вычисление. Т>
Вряд ли анализ графа оправдан в такой задаче. В чем преимущество? Цыкл — так его поймать можно и попроще. Первый способ — "раскраска" клеток (когда мы берем вычисление значения в "скобки" считаем/несчитаем — как это в моем старом коде сделано и как нормальные люди делают в плюсах), второй способ — передавать "стек" вычислений параметром (это будет set из ref-ов), и проверять, нет ли повторного захода.
"Раскраска" — это одна накладная операция вставки в sheet значения updating при входе в функцию evaluate.
В случае "стека" — две операции вставки и удаления, зато в меньший по размеру set. Я выбрал "раскраску" потому, что дополнительного контейнера таскать а собой не надо. Красивее, штоли. Собственно, код увеличивается на 3 строки.
G>>
Это еще порефакторить можно, чтобы было красиво. Кстати, вот еще одна лажа. Для ошибки надо делать конструктор. А создается она зараза везде. Во всех модулях.
А вообще — все это частности. Твой подход рулит со страшной силой. Так делать (а именно — заставить клетку знать список ячеек, от которых она зависит) — правильно. Именно это решение ключевое — только этот подход позволяет полностью изолировать алгоритм вычисления шыта от вычисления выражений (у меня это было в куче, и меня это беспокоило). И это решение — безусловно решение дизайна, а не алгоритма. Короче, "я всегда жалел, Штирлиц, что вы работаете не в моем департаменте" .
__________________
Кстати, хаскелисты жгут. potan у себя в ЖЖ опубликовал жосткое решение этой задачи на Хаскеле с использованием "релятивистских эффектов". Там клетки с формулами напрямую ленивыми связями на аргументы замыкаются, а потом вычисляются. Жесть.
Здравствуйте, sergesokolov, Вы писали:
G>>Кстати, приглашаю поиграть в "пятнашки". Помоги мне, попробуй улучшить дизайн. Принципы дизайна, которые надо сохранить — очень простые: если ты посмотришь внимательно на код, то ты обратишь внимание, что модули не знают про структуры данных друг друга — между ними ходят либо абстрактные, либо очень простые типы данных. Предлагается это свойство сохранить, и попытаться уменьшить связность.
S>Поставив себя сразу в очень удобное от критики положение, тем что я здесь алгоритмами не занимаюсь, а только дизайном, G по сути дела прыгнул с головой в смоляную яму – отличная позиция. Полностью конечно отрешиться от алгоритмов не удалось, появилась какая-то жуткая мистика про живые процессы, которые должны быть мало связанны и не должны что знать друг про друга, а в следующем мастер классе можно будет сказать, что они наоборот теперь жестко связанны и все друг про друга знают. Конечно от геморроя это никак не избавит, а напротив усугубит еще в большей степени чем раньше. Это я могу гарантировать. S>Поэтому еще так слаба пояснительная часть написанная псевдокодами, а чего пояснять –то? S>Чистописание кода понравилось, я так не умею. Но сам язык беден.
Симметричный ответ: Вы, любезный, поставили себя в очень удобное для критики положение. По сути — вы нырнули с головой просто в яму какую-то с чем-то, не скажу с чем. Сами посудите — чистый код вы писать не умеете, проблем дизайна не понимаете, понятие "связности" для вас мистика. И единственное, что вы можете гарантировать — это геморрой. Прям хоть в резюме включай .
Несимметричный ответ: Короче, в этом топике обсуждается проблема и подходы к дизайну для ФЯ. Не мое чистописание, не бедность языков, не алгоритмы (алгоритмы в этой задаче тривиальны — не о чем тут говорить). На примере простой задачи. По существу вопроса есть что сказать? Считаешь, что само понятие дизайна в контексте ФП — глупость? Да ради бога — раскрой тему, с тобой поговорят. Может быть. А вые..ся и переходить на личности здесь не надо.
Здравствуйте, sergesokolov, Вы писали:
C>>Так ведь все просто: предложи лучшее решение S>решение чего? S>мистических вещей, тут одна словестная ловушка в той терминологии которую выдумавает G. S>Бьен Страуструп тоже был в определенной степени мистик со скрытием данных, но у него была четкая цель, которой здесь сознательно нет.
Дурачком прикидываться не надо, ок? Вот реальная тестовая задача, которая применялась при найме в реальную компанию — CQG, ее до тебя уже успешно решили уже сотни людей. Так что не надо делать трагическое выражение лица, вставать в позу, и вещать драматическим голосом, работая на публику. Не оценят, посмеются только. Собственно, уже.
Необходимо реализовать простую электронную таблицу в виде программы, выполняющейся
из командной строки. Она должна уметь обрабатывать ячейки таблицы как и более
продвинутые аналоги, только с упрощенным синтаксисом выражений. Каждая ячейка
может содержать:
— Ничего
— Неотрицательное целое число
— Текстовые строки, которые начинаются с символа '
— Строки-выражения, которые начинаются с символа '=' и могут содержать
неотрицательные целые числа, ссылки на ячейки и простые арифметические
выражения. Скобки запрещены, у всех операций одинаковый приоритет.
Ссылки на ячейки состоят из одной латинской буквы и следующей за ней
цифры.
Эти ограничения введены для упрощения разбора выражений, поскольку разбор
выражений не является основной частью проблемы. Вы можете спокойно
положиться на эти ограничения. Вот грамматика содержимого ячейки:
expression ::= '=' term {operation term}*
term ::= cell_reference | nonnegative_number
cell_reference ::= [A-Za-z][0-9] --
operation ::= '+' | '-' | '*' | '/'
text ::= '\'' {printable_character}
Процесс обработки:
— Все выражения должны быть заменены на вычисленный результат.
— Все вычисления выполняются с помощью целочисленной арифметики со знаком.
— Ячейки с текстом должны быть вычислены как соответствующий текст без
префикса '.
— Операции над строками текста запрещены.
— В случае любой ошибки вычисления формулы, вычисляемая ячейка должна содержать
слово-сообщение об ошибке, начинающееся с символа '#'. Используйте короткие,
ясные сообщения. Не надо предоставлять подробности об ошибках в выводе.
Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.
Ввод и вывод
------------
Программа получает описание таблицы с формулами из стандартного ввода,
вычисляет ее и печатает полученный результат в стандартный вывод. Входные
данные представлены таблицей, элементы строк которой разделены табуляциями.
Первая строка содержит пару чисел, разделенных табуляцией — высоту и
ширину таблицы, соответственно. Затем идут строки с ячейками таблицы,
в грамматике, приведенной выше.
Выход должен содержать только ожидаемую информацию, включая сообщения об
ошибках, и никакой другой информации в выводе не должно быть, включая и
welcome text. Выход должен быть отформатирован в соответствии с приведенным
ниже примером.
Указания по решению
-------------------
Необходимо промышленное качество кода. Более короткое и читаемое решение
предпочтительней. Решение должно содержать тестовые примеры и код, использованные
в процессе создания решения. Не забудьте откомментировать код в ключевых
местах. Код должен быть устойчив к ошибкам.
Представьте, что это требования к первой фазе проекта. Необходимо реализовать
только то, что нужно на этой фазе. Однако, известно, что планируется вторая
фаза, в которой требования будут расширены следующими:
— Расширить формулы операциями над строками,
— Оптимизировать производительность для громадных таблиц.
Вам необходимо будет указать, какие изменения необходимо сделать для
реализации второй фазы проекта.