From d0666bd369f551de3e5d843a09bab78754c0d70e Mon Sep 17 00:00:00 2001 From: nsensfel Date: Wed, 9 Oct 2019 11:44:25 +0200 Subject: Moves the optimization functions out. --- src/ataxic.erl | 159 +----------------------------------------- src/ataxic_optimize.erl | 178 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 180 insertions(+), 157 deletions(-) create mode 100644 src/ataxic_optimize.erl (limited to 'src') diff --git a/src/ataxic.erl b/src/ataxic.erl index 4d829f3..4e011c6 100644 --- a/src/ataxic.erl +++ b/src/ataxic.erl @@ -3,53 +3,9 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TYPES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-include("ataxia/ataxic.hrl"). %%%% BASIC OP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%% Select --record(field, {ix :: non_neg_integer(), op :: basic()}). --record(upfield, {ix :: non_neg_integer(), op :: basic()}). - -%%%% Sequence of instructions --record(seq, {ops :: list(basic())}). - -%%%% Values Access --record(const, {value :: any()}). --record(current, {}). - -% Possible improvement: add support for some sort of registers. -% This would add a dict (no need for orddict here) when evaluating Ataxic -% expressions, with the following functions: -% -record(reg_store, {name :: binary(), op :: basic()}). -% -record(reg_load, {name :: binary()}). -% It's kind of weird to use though, cause you can't retrieve what you've stored -% at a node that was deeper in the query's tree. It can be used to move values -% further down (or horizontally) though, and there are already instructions that -% give you values found further down. - --record -( - apply_fun, - { - module :: atom(), - function :: atom(), - params :: list(basic()) - } -). - -%%%% Number Comparison --record(gt, {p0 :: basic(), p1 :: basic()}). --record(ge, {p0 :: basic(), p1 :: basic()}). --record(lt, {p0 :: basic(), p1 :: basic()}). --record(le, {p0 :: basic(), p1 :: basic()}). --record(eq, {p0 :: basic(), p1 :: basic()}). - -%%%% Bool Operations --record(land, {params :: list(basic())}). --record(lor, {params :: list(basic())}). --record(neg, {param :: basic()}). - --record(list_cons, {param :: basic()}). - -type basic() :: #field{} | #upfield{} @@ -78,14 +34,6 @@ | #list_cons{}. %%%% META OP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%% Select --record(read_perm, {op :: basic()}). --record(write_perm, {op :: basic()}). --record(lock, {op :: basic()}). --record(value, {op :: basic()}). - --record(mseq, {ops :: list(meta())}). - -type meta() :: #read_perm{} | #write_perm{} | #value{} | #lock{} | #mseq{}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% EXPORTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -126,7 +74,7 @@ -export([apply_to/2, matches/2]). --export([optimize/1, is_constant/1]). +-export([is_constant/1]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% LOCAL FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -173,102 +121,6 @@ basic_apply_to (#neg{ param = V }, Val) -> basic_apply_to (#list_cons{ param = V }, Val) -> [basic_apply_to(V, Val)|Val]. --spec optimize_update_field_sequence (list(basic()), list(basic())) -> basic(). -optimize_update_field_sequence ([], Result) -> - case Result of - [A] -> A; - _ -> sequence(Result) - end; -optimize_update_field_sequence (UnsortedOPs, CurrentResults) -> - {FieldUpdates, PotentiallyImportantOPs} = - lists:splitwith(fun (E) -> is_record(E, upfield) end, UnsortedOPs), - - SortedFieldUpdates = - lists:sort - ( - fun (A, B) -> - ((A#upfield.ix) =< (B#upfield.ix)) - end, - FieldUpdates - ), - - {LastIX, LastUpdateOPs, OtherMergedFieldUpdates} = - lists:foldl - ( - fun (Update, {CurrentIX, CurrentOPs, CurrentResult}) -> - case (Update#upfield.ix == CurrentIX) of - true -> - {CurrentIX, [Update#upfield.op|CurrentOPs], CurrentResult}; - - _ -> - { - Update#upfield.ix, - [Update#upfield.op], - ( - case CurrentOPs of - [] -> CurrentResult; - [OP] -> - [ - update_field(CurrentIX, OP) - |CurrentResult - ]; - _ -> - [ - update_field(CurrentIX, sequence(CurrentOPs)) - |CurrentResult - ] - end - ) - } - end - end, - {-1, [], []}, - SortedFieldUpdates - ), - - MergedFieldUpdates = - ( - case LastUpdateOPs of - [] -> OtherMergedFieldUpdates; - [OP] -> - [ - update_field(LastIX, OP) - |OtherMergedFieldUpdates - ]; - _ -> - [ - update_field(LastIX, sequence(LastUpdateOPs)) - |OtherMergedFieldUpdates - ] - end - ), - {ImportantOPs, PotentialFieldUpdates} = - lists:splitwith - ( - fun (E) -> not is_record(E, upfield) end, - PotentiallyImportantOPs - ), - - optimize_update_field_sequence - ( - PotentialFieldUpdates, - (CurrentResults ++ MergedFieldUpdates ++ ImportantOPs) - ). - --spec flatten_sequence (list(basic())) -> list(basic()). -flatten_sequence (OPs) -> - lists:foldl - ( - fun (E, CurrentOPs) -> - case is_record(E, seq) of - true -> (E#seq.ops ++ CurrentOPs); - _ -> [E|CurrentOPs] - end - end, - [], - OPs - ). - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% EXPORTED FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -334,13 +186,6 @@ update_write_permission (OP) -> #write_perm{ op = OP }. -spec update_value (basic()) -> meta(). update_value (OP) -> #value{ op = OP }. --spec optimize (basic()) -> basic(). -optimize (#seq{ ops = OPs }) -> - S0OPs = flatten_sequence(OPs), - S1OPs = lists:filter(fun (E) -> (not is_record(E, current)) end, S0OPs), - optimize_update_field_sequence(S1OPs, []); -optimize (OP) -> OP. - %%%%% APPLY TO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -spec apply_to (meta(), ataxia_entry:type()) -> ataxia_entry:type(). apply_to (#value{ op = OP }, Entry) -> diff --git a/src/ataxic_optimize.erl b/src/ataxic_optimize.erl new file mode 100644 index 0000000..2fc269e --- /dev/null +++ b/src/ataxic_optimize.erl @@ -0,0 +1,178 @@ +-module(ataxic_optimize). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% TYPES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-include("ataxia/ataxic.hrl"). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% EXPORTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-export([aggressive/1, light/1]). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% LOCAL FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-spec optimize_update_field_sequence + ( + list(ataxic:basic()), + list(ataxic:basic()) + ) + -> ataxic:basic(). +optimize_update_field_sequence ([], Result) -> + case Result of + [A] -> A; + _ -> ataxic:sequence(Result) + end; +optimize_update_field_sequence (UnsortedOPs, CurrentResults) -> + {FieldUpdates, PotentiallyImportantOPs} = + lists:splitwith(fun (E) -> is_record(E, upfield) end, UnsortedOPs), + + SortedFieldUpdates = + lists:sort + ( + fun (A, B) -> + ((A#upfield.ix) =< (B#upfield.ix)) + end, + FieldUpdates + ), + + {LastIX, LastUpdateOPs, OtherMergedFieldUpdates} = + lists:foldl + ( + fun (Update, {CurrentIX, CurrentOPs, CurrentResult}) -> + case (Update#upfield.ix == CurrentIX) of + true -> + {CurrentIX, [Update#upfield.op|CurrentOPs], CurrentResult}; + + _ -> + { + Update#upfield.ix, + [Update#upfield.op], + ( + case CurrentOPs of + [] -> CurrentResult; + [OP] -> + [ + ataxic:update_field(CurrentIX, OP) + |CurrentResult + ]; + _ -> + [ + ataxic:update_field + ( + CurrentIX, + ataxic:sequence(CurrentOPs) + ) + |CurrentResult + ] + end + ) + } + end + end, + {-1, [], []}, + SortedFieldUpdates + ), + + MergedFieldUpdates = + ( + case LastUpdateOPs of + [] -> OtherMergedFieldUpdates; + [OP] -> + [ + ataxic:update_field(LastIX, OP) + |OtherMergedFieldUpdates + ]; + _ -> + [ + ataxic:update_field(LastIX, ataxic:sequence(LastUpdateOPs)) + |OtherMergedFieldUpdates + ] + end + ), + {ImportantOPs, PotentialFieldUpdates} = + lists:splitwith + ( + fun (E) -> not is_record(E, upfield) end, + PotentiallyImportantOPs + ), + + optimize_update_field_sequence + ( + PotentialFieldUpdates, + (CurrentResults ++ MergedFieldUpdates ++ ImportantOPs) + ). + +-spec flatten_sequence (list(ataxic:basic())) -> list(ataxic:basic()). +flatten_sequence (OPs) -> + lists:foldl + ( + fun (E, CurrentOPs) -> + case is_record(E, seq) of + true -> (E#seq.ops ++ CurrentOPs); + _ -> [E|CurrentOPs] + end + end, + [], + OPs + ). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% EXPORTED FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +-spec aggressive + (ataxic:basic()) -> ataxic:basic(); + (ataxic:meta()) -> ataxic:meta(). +aggressive (In = #field{ op = OP }) -> + In#field{ op = aggressive(OP) }; +aggressive (In = #upfield{ op = S0OP}) -> + S1OP = aggressive(S0OP), + + case S1OP of + #current{} -> S1OP; + _ -> In#upfield{ op = S1OP } + end; +aggressive (#seq{ ops = S0OPs }) -> + S1OPs = lists:map(fun aggressive/1, S0OPs), + S2OPs = flatten_sequence(S1OPs), + S3OPs = lists:filter(fun (E) -> (not is_record(E, current)) end, S2OPs), + Result = optimize_update_field_sequence(S3OPs, []), + + case Result#seq.ops of + [] -> #current{}; + _ -> Result + end; +aggressive (In = #apply_fun{ params = OPs }) -> + In#apply_fun + { + params = lists:map(fun aggressive/1, OPs) + }; +aggressive (In = #list_cons{ param = OP }) -> + In#list_cons{ param = lists:map(fun aggressive/1, OP) }; +aggressive (In = #read_perm{ op = OP }) -> + In#read_perm{ op = aggressive(OP) }; +aggressive (In = #write_perm{ op = OP }) -> + In#write_perm{ op = aggressive(OP) }; +aggressive (In = #lock{ op = OP }) -> + In#lock{ op = aggressive(OP) }; +aggressive (In = #value{ op = OP }) -> + In#value{ op = aggressive(OP) }; +aggressive (In = #mseq{ ops = OPs }) -> + In#mseq{ ops = lists:map(fun aggressive/1, OPs) }; +aggressive (Other) -> + Other. + +-spec light + (ataxic:basic()) -> ataxic:basic(); + (ataxic:meta()) -> ataxic:meta(). +light (#seq{ ops = S0OPs }) -> + S1OPs = flatten_sequence(S0OPs), + S2OPs = lists:filter(fun (E) -> (not is_record(E, current)) end, S1OPs), + Result = optimize_update_field_sequence(S2OPs, []), + + case Result#seq.ops of + [] -> #current{}; + _ -> Result + end; +light (OP) -> OP. -- cgit v1.2.3-70-g09d2