Gaperton's blog

Исправленное решение - по результатам обсуждения на РСДН.



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

Мы сделаем это для элементарных типов, одновременно с применением еще одного дизайнерского хода - "слоеных" архитектрур. Типа как в семиуровневой модели OSI, и все такое. Суть слоев проста - верхний слой использует нижний, нижний ничего не знает про верхний. Также, этими средствами я исправляю косяк в моем предыдущем дизайне - а именно, такие важные штуки как value, ref, и error у меня не проходят явными типами, их структура - это неявный контракт между модулями cell, expression, и operation, что, вообще говоря, error-prone и, если кто не заметил - то это очень сильный косяк.

Для Хаскеля это не будет _таким_ сильным косяком, там такие типы явно определяются, а вот для динамического Эрланга - это реально сильный косяк. Вообще, планка good enough дизайна для Эрланга выше, чем для Хаскеля с его системой типов, строгой типизаций.

Итак, выделяем слой базовых типов в явном виде. Это будут reference, value, и operation.

Начнем с главного - value. Имеем конструктор из строки create, которая нам обязательно вернет валидный value. Ошибка - также вполне валидный value.

Обратите внимание - пустое значение также значение, и оно может трактоваться как 0 в операциях с целыми. Потому, у нас определены функции приведения к целому (as_integer) для нашего значения, которыми воспользуется operation. Результат придения обязан быть целым, или вылетит value:error в виде exception.

Кроме того, кто-то (а именно - expression) может захотеть создать число из строки, зная, что там должно лежать число (конструктор integer). Тут уж извините - если не вышло, то ничего не создастся и вылетит value:error.

Принципиально здесь следующее - вылет exception находится также в данном модуле, и вылетает гарантированно альтернатива варианта error. Если мы не хотим exception, а хотим чтобы вернулся честный variant, то нам достаточно перед вызовом нашей функции написать catch.

-module( value ).
-export( [ create/1, integer/1 ] ). %% create value from string
-export( [ as_string/1, as_integer/1 ]  ).
-export( [ throw_error/1 ] ). %% throw value:error

%% Public data type
%% value() = integer() | string() | error() | empty.
create( [ $', String ] ) -> String;
create( [ $#, String ] ) -> error( list_to_atom( String ) );
create( "" ) -> empty;
create( Int ) -> catch integer( Int ).

%% to_string( value() ) -> string().
%% get text representation for the given cell value
as_string( Int ) when is_integer( Int ) -> integer_to_list( Int );
as_string( { error, Msg } ) -> "#" ++ atom_to_list( Msg );
as_string( empty ) -> "";
as_string( String ) is_list( String ) -> String.

%% error( atom() ) -> error() = { error, Code }
error( Code ) when is_atom( Code ) -> { error, Code }.
throw_error( Msg ) when is_atom( Msg ) -> throw( error( Msg ) ).

%% integer( String ) -> integer() | throw error()
integer( String ) ->
	case string:to_integer( T ) of
		{ Int, [] } -> Int;
		{ error, no_integer } -> throw_error( 'not a number' ).
	end.

as_integer( empty ) -> 0;
as_integer( Int ) when is_integer( Int ) -> Int;
as_integer( _ ) -> throw_error( 'not a number' ).

ref у нас можно создавать из текста, а если не получается - то вылетает exception. Что логично - результат данной операции _только_ валидный тип ref, и ничто иное. Обратите внимание - как именно он вылетает. Вылетает гарантировано value:error, через функциональный интерфейс.

-module( ref ).
-export( [ create/1, create/2, row_range/3 ] ).

%% create( integer(), integer() ) -> ref().
create( Row, Col ) -> { Row, Col }.

%% create( string() ) -> ref() | throws value:error().
create( [ Row, Col ] ) when Row >= $a, Row =< $z, Col >= $0, Col =< $9 ->
	{ Row - $a + 1, Col - $0 };
create( _ ) -> value:throw_error( 'invalid ref' ).

%% row_range( Row, From, To ) -> [ ref() ]
%% Row = From = To = integer()
row_range( Row, From, To ) -> [ ref( Row, Col ) || Col <- lists:seq( From, To ) ].

Если вдуматься, то бинарные операции также могут являться элементарным типом данных. С операциями мы также правим один косяк. Теперь конструктор у нас возвращает тупо бунарную функцию, которая делает то, что нам нужно. Вот такую: fun( value(), value() ) -> value() | throws error(). Да, из нее могут лететь exception, но если мы напишем catch F( X, Y ) то тип этого выражения будет честный value(). Чем мы и воспользуемся в реализации expression.

Использование функций в качестве возворащаемых значений - чрезвычайно мощное средство инкапсуляции, которое радикально уменьшает связность. Чем это лучше предыдущего варианта? Например, я могу эту функцию передать в третий модуль параметром, и этот модуль может ничего не знать о модуле operation. Что в предыдущем дизайне невозможно. ФВП - совершенно потрясающая штука, я их ни на какие классы теперь не променяю.

-module( operation ).
-export( [ tokens/0, create/1 ] ).

%% create( char() ) -> Operation
%% Operation = fun( value(), value() ) -> value() | throws error()
%% create binary operator...
create( $+ ) -> fun add/2;
create( $- ) -> fun sub/2;
create( $* ) -> fun mult/2;
create( $/ ) -> fun divd/2.

%% tokens() -> [ char() ].
%% binary operators' token list...
tokens() -> "+-*/".

%% Binary operations implementation... 
%%______________________________________
add( X, Y ) when is_list( X ), is_list( Y ) -> X ++ Y;
add( X, Y ) -> value:as_number( X ) + value:as_number( Y ).

mult( X, Y ) -> value:as_number( X ) * value:as_number( Y ).

sub( X, Y ) -> value:as_number( X ) - value:as_number( Y ).

divd( X, Y ) ->
	X_1 = value:as_number( X ),
	Y_1 = case value:as_number( Y ) of
		0 -> value:throw_error( 'division by zero' );
		Y -> Y
	end,
	X_1 / Y_1.

Вот так. Теперь перейдем, так сказать, к логике нашего решения. Как я уже говорил, Трурль с РСДН предложил замечательное решение проблемы связности модуля expression. Суть его состоит в том, чтобы конструктор expression возвращал список ссылок, которые надо просчитать. Мы дополним его решение применением ФВП, и получим волшебную штуку - интерфейс expression сократился до одной функции.

create_expr( string() ) -> { Expression, [ ref() ] } | value().
Expression = fun( [ value() ] ) -> value()

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

-module( expression ).
-export( [ create/1 ] ).

%% create_expr( string() ) -> { Expression, [ ref() ] } | value().
%% Expression = fun( [ value() ] ) -> value()
create( String ) -> catch
		{ Expr, Refs } = create_expr( String ),
		F = fun( Args ) -> catch
			{ Res, [] } = evaluate( Expr, Args ),
			Res
		end,
		{ F, Refs }

%% create( string() ) -> { expression(), refs() }.
%% create expression from text...		
create_expr( Expr ) ->
	Pos = string:cspan( Expr, operation:tokens() ),
	case lists:split( Pos, Expr ) of
		{ Val, [ Op | Rest ] } ->
			L = create_arg( Val ),
			{ R, Refs } = create_expr( Rest ),
			Node = { L, operation:create( Op ), R },
			{ Node, update_refs( L, Refs ) };
		{ Val, [] } ->
			H = create_arg( Val ),
			{ H, update_refs( H, [] ) }
	end.

update_refs( { ref, Ref }, Refs ) -> [ Ref | Refs ];
update_refs( _, Refs ) -> Refs. 

%% create_arg( string() ) -> Ref | integer()
%% Ref = { integer(), integer() }
create_arg( Arg ) ->
	try value:integer( Arg ) catch
		{ error, _ } -> ref:create( Arg )
	end.

%% evaluate( Expression, Args ) -> { Value, [] }.
%% Evaluate expression.
evaluate( { A, Op, B }, Args ) ->
	{ ResA, Args_1 } = evaluate( A, Args ),
	{ ResB, Args_2 } = evaluate( B, Args_1 ),
	{ Op( ResA, ResB ), Args_2 };
evaluate( { ref, _ }, [ Arg | Rest ] ) -> { Arg, Rest };
evaluate( Val, Args ) -> { Val, Args }.

Теперь клетка таблицы. Ее можно создать из текста, также ее можно рассчитать, тогда она перестанет быть клеткой, и станет просто value(). Собственно, что такое клетка, если вдуматься? Это либо value(), либо формула. Что такое процесс вычисления? Замена в таблице cell() на value(). Вот и все.

Код выглядит так страшно потому, что мы вычисляем формулы рекурсивно, ловя циклы и модифицируя sheet, который протягивается сквозь алгоритм "монадическим образом" ((с) Зефиров). Да собственно, если вдуматься, то и не так страшно он выглядит.

-module( cell ).
-export( [	create/1, evaluate/2 ] ).

%% create( String ) -> value() | Formula
%% Formula = { expression(), [ ref() ] }
%% value:create, expression:create, Cell
create( [ $= | Expr ] ) -> expression:create( Expr );
create( Value ) -> value:create( Value ).

%% evaluate( ref(), sheet() ) -> sheet().
%% eval_and_get
evaluate( Ref, Sheet ) ->
	{ _, Sheet_1 } = eval_and_get( Ref, Sheet ),
	Sheet_1.

%% eval_and_get( ref(), sheet() ) -> { value(), sheet() }.
%% table:get_cell, table:set_cell, value:error, Cell
eval_and_get( Ref, Sheet ) ->
	case table:get_cell( Ref, Sheet ) of
		updating -> { value:error( 'cyclic reference' ), Sheet };
		{ Expr, Refs } ->
			Sheet_1 = table:set_cell( Ref, updating, Sheet ),
			{ Args, Sheet_2 } = lists:mapfoldl( fun eval_and_get/2, Sheet_1, Refs ),
			Value = Expr( Args ),
			{ Value, table:set_cell( Ref, Value ) };
		Value -> { Value, Sheet }
	end.

Вот, остался модуль sheet. К моему сожалению - он не дописан до конца, потому как мне пришла идея выделить способ хранения таблицы в отдельный модуль "базового" уровня, (table), но я не дописал sheet до конца. И я чувствую, что уже не допишу. В принципе, так - правильно, и это последний штих к дизайну. Но сил возится с этой задачей у меня больше нет. Есть у меня такое неприятное свойство - когда я вижу, что дальнейшее решение тривиально, то у меня напрочь пропадает интерес к задаче. Пальцы - не печатают. И все, хоть что делай. Поэтому привожу код как есть - пытливый ум восстановит картину.

-module( sheet ).
-export( [	new/0, 
			create_row/3, row_as_text/3, evaluate/1 ] ).

%% new() -> sheet()
%% construct new sheet...
new() -> table:new().

%% update_row( Row, [ string() ], sheet() ) -> sheet()
%% table:set_cell, ref:row_range, create_cell
create_row( Row, TextCells, Sheet ) ->
	Cells = [ cell:create( String ) || String <- TextCells ],
	Refs = ref:row_range( Row, 1, lists:length( Cells ) ),
	lists:foldl( fun table:set_cell/2, Sheet, lists:zip( Refs, Cells ) ).

%% get_row( Row, Length, sheet() ) -> [ string() ]
%% value:as_string, table:get_cell, ref:row_range
row_as_text( Row, Cols, Sheet ) ->
	[ value:as_string( table:get_cell( Ref, Sheet ) ) || Ref <- ref:row_range( Row, 1, Length ) ].
	
%% evaluate( sheet() ) -> sheet().
%% cell:evaluate, table:get_refs
evaluate( Sheet ) -> lists:foldl( fun cell:evaluate/2, Sheet, table:get_refs() ).

get_cell( Row, Col, Sheet ) -> 
	Value = table:get_cell( ref:create( Row, Col ), Sheet ),
	value:as_string( Value ).
	
set_cell( Row, Col, String, Sheet ) ->
	 table:set_cell( ref:create( Row, Col ), cell:create( String ), Sheet ),

-module( table ).
-export( [ new/0, set_cell/2, set_cell/3, get_cell/2, get_refs/1 ] ).

%% new() -> sheet()
%% construct new sheet...
new() -> gb_trees:empty().

get_refs( Sheet ) -> gb_trees:keys( Sheet ).

%% set_cell( ref(), cell(), sheet() ) -> sheet().
set_cell( _, empty, Sheet ) -> Sheet; %%% do NOT store empty values...
set_cell( Ref, Value, Sheet ) -> gb_trees:enter( Ref, Value, Sheet ).

%% set_cell( { ref(), cell() }, sheet() ) -> sheet().
set_cell( { Ref, Value }, Sheet ) -> set_cell( Ref, Value, Sheet ).

%% get_cell( ref(), sheet() ) -> Value.
get_cell( Ref, Sheet ) -> 
	case gb_trees:lookup( Ref, Sheet ) of
		{ value, Cell } -> Cell;
		_ -> empty
	end.

Вот так, мне кажется, должен выглядеть идиоматический дизайн для данной задачи. Выводы:
1) ФВП - рулят.
2) Для описания дизайна чистых программ великолепно подходит метод CRC-Cards. Буду им пользоваться.
3) Дизайн в случае функциональной чистоты - удивительно простое и приятное занятие, не приходится морочится с состоянием, identity, и следующими из них схемами агрегации. Дизайн уже не является трудоемкой фазой разработки. Это меня изумляет.
4) Рефакторинг чистой программы - чистое удовольствие. Цена ошибки дизайна на порядок ниже в случае чистой программы.
5) Перечисленное, кстати, означает применимость подходов agile в случае функциональной чистоты. Я пока особых противопоказаний не вижу. Удивительное рядом, господа.
6) Организация разработки в случае смешанных чисто-грязных языков, таких как Эрланг или Немерле, вообще отдельная тема. Дело в том, что функциональная декомпозиция (в рамках моего определения) получается 100% отделена от декомпозиции по состоянию (то есть объектной модели). Это сложно понять, это надо объяснять отдельно и долго. Грубо говоря, можно спроектировать, написать, и отладить чистую часть независимо - первым этапом. А вторым этапом - натянуть на эту готовую систему объектную модель, в которые завернуть состояние. Это потрясающе классный подход - сначала проектируем ядро системы - наслаждаясь дешевым дизайном и рефакторингом, а потом нарезаем ее на объекты в разных позах (что элементарно - stateless код гораздо пригоднее к повторному использованию - в нем нет самой сильной связности - по состоянию) - радикально сокращая таким образом комбинаторную сложность дизайна (вместо X*Y получим X+Y, если вы понимаете о чем я).

Этот момент я заметил сейчас - я в рамках развлечения проектирую Ticker Plant на Эрланге. Это фрагмент системы обработки биржевых котировок. Черт бы его побрал - такой двухфазный подход к разработке - это что-то необыкновенное и удивительное, ставящее с ног на голову все мои представления об организации и цикле разработки. Насколько я понимаю, в литературе этот эффект не описан и толком не изучен - практики-то широкой применения чистых подходов пока нет, и менеджеры до них не добрались. В первый раз вижу четкое разделение геморроя с состоянием и алгоритмического проектирования на практике. Удивительно. Как оформятся мысли, отпишу.