[erlang-questions] Backtracking in Erlang, part 1 - control
Hynek Vychodil
vychodil.hynek@REDACTED
Wed Mar 18 09:19:09 CET 2009
Sorry, I did not read carefully your post. It is not question, it is answer
;-)
On Wed, Mar 18, 2009 at 9:16 AM, Hynek Vychodil <vychodil.hynek@REDACTED>wrote:
> Have you seen 2.6.3 Parsing
> http://www.erlang.org/doc/programming_examples/funs.html#2.6?
>
> I think higher order function elegantly solve this even it can be slower
> than straight forward approach.
>
> 2009/3/18 Robert Virding <rvirding@REDACTED>
>
>> Sometimes you need to be able to do search algorithms which can step back
>> and try other alternate ways of finding a solution, "backtracking".
>> Generally this is difficult to do in functional languages like Erlang (most
>> other languages too for that matter). A classic example of this type of
>> problem is parsing ambiguous grammars.
>>
>> Prolog syntax is like that, in some cases you need almost indefinite
>> look-ahead before you can decide how input is to be parsed. When I
>> implemented Erlog (a prolog in and for Erlang) I decided to do the parser in
>> Erlang so that it could run stand-alone and so I ran straight into this
>> problem.
>>
>> Here is *a* solution to the problem. It is in two parts, the first
>> describing the control structures and the second (more difficult) describing
>> handling of data. There may also be a third part discussing some problems
>> with the solution to control, if anyone is still interested.
>>
>> The main problem we have to overcome is that normally when you choose a
>> path you "commit" to it and can't go back and try an alternate path. For
>> example in:
>>
>> case get_a_value() of
>> Choice1 -> ... ;
>> Choice2 -> ... ;
>> ...
>> end
>>
>> once you have chosen a path, say Choice1, there is no (simple) way to go
>> back try Choice2 if you later decide that Choice1 was wrong. We can't
>> backtrack.
>>
>> Another problem is that if we have:
>>
>> a() -> foo(), bar(), baz().
>>
>> and once we have completed foo() then even if it gave an answer which
>> later was shown to be wrong there is no way to step back into it, backtrack,
>> and let it give a new answer.
>>
>> In this first section we will (almost) completely ignore arguments and
>> return values.
>>
>> When looking at control we will (almost) completely ignore arguments and
>> returning values. We will use the convention that functions return either
>> '{succeed,Value}' when they succeed or 'fail' when they can't find a
>> solution.
>>
>> The trick is to ensure that functions only return at all when they fail,
>> otherwise they just continue by explicitly calling the next thing which
>> should be done. We will do this by using a Continue Passing Style (CPS)
>> where each function will have an argument which is the next function call to
>> continue. (CPS is not new and is generally known) So functions will usually
>> look like this:
>>
>> a(Next) ->
>> <do our stuff>,
>> OurNext = fun () -> even_more_stuff(Next) end,
>> more_stuff(OurNext).
>>
>> We will use the convention that when a function fails and cannot go on it
>> will return 'fail'. When *the* solution has been found then the final test
>> will return {succeed,Value}. So the top level function will look something
>> like:
>>
>> top_call() ->
>> Succeed = fun () -> {succeed,yes} end, %We have succeeded
>> find_solution(Succeed).
>>
>> So now our program will keep going forwards until it finally calls the
>> Succeed fun when it all returns back to the initial caller.
>>
>> The next problem is to introduce 'choice points' where we can choose one
>> path but still allow the code to backtrack and make another choice. This is
>> the done in the function cp/1 where the argument is a list functions which
>> are separate paths to choose from:
>>
>> cp([fun () -> do_stuff_a(Next) end,
>> fun () -> do_stuff_b(Next) end,
>> fun () -> do_stuff_c(Next) end,
>> ...]).
>>
>> Cp/1 will try the functions in order, if one succeeds then the choice
>> point will succeed and return the same succeed value, if it fails then the
>> next function in the list will be tried, until no more exist when the choice
>> point will fail: The code for cp is simple:
>>
>> cp([G|Gs]) ->
>> case G() of
>> {succeed,Value} -> {succeed,Value};
>> fail -> cp(Gs)
>> end;
>> cp([]) -> fail.
>>
>> That's it, we're done. A lot of explanation for very little code.
>>
>> A slight variation is to not chain the continuation together as shown here
>> but to have Next as a list of functions to call. Instead of directly calling
>> Next you call next/1 with argument Next, next(Next), where next/1 is defined
>> as:
>>
>> next([N|Ns]) -> N(Ns).
>>
>> There is no functional difference it just make writing some code a bit
>> easier. For example the function defined above:
>>
>> a() -> foo(), bar(), baz().
>>
>> would look like this in the normal way:
>>
>> a(Next) ->
>> Next1 = fun () -> baz(Next) end,
>> Next2 = fun () -> bar(Next1) end,
>> foo(Next2).
>>
>> while using the list variant it would look like:
>>
>> a(Next) ->
>> foo([fun (Ns) -> bar(Ns) end,
>> fun (Ns) -> baz(Ns) end | Next]).
>>
>> which can be easier to read, especially if there many calls in the
>> continuation.
>>
>> After I introduce handling data in the next installment I can give a
>> proper example.
>>
>> I have also posted this to my blogg for those who prefer to read there,
>>
>> Robert
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>
>
>
>
> --
> --Hynek (Pichi) Vychodil
>
> Analyze your data in minutes. Share your insights instantly. Thrill your
> boss. Be a data hero!
> Try Good Data now for free: www.gooddata.com
>
--
--Hynek (Pichi) Vychodil
Analyze your data in minutes. Share your insights instantly. Thrill your
boss. Be a data hero!
Try Good Data now for free: www.gooddata.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20090318/f1cbc8f1/attachment.htm>
More information about the erlang-questions
mailing list