Friday, February 25, 2011

Rosseta code tutorials:Amb operator

Practically from the very start I had a problem with finding interesting samples to be implemented on ELENA. And only recently I found a place where I could find them

So I'm continuing implementing these tasks. My next sample is Amb operator.

Let's consider several tasks - one (with literals) from rosetta code (i.e. it is a failure if the last character of word 1 is not equal to the first character of word 2, and similarly with word 2 and word 3, as well as word 3 and word 4) and another (with numeric) from here. We will call them Program1 and Program2.

#symbol Program1 =>
[
#var A := AmbValue::(1, 2, 3).
#var B := AmbValue::(4, 5, 6).

AmbOperator::(A, B) seek: => (A * B== 8).

'program'Output << A << "*" << B << "=8".
].

#symbol Join =
{
if &first:aFirst &second:aSecond
[
^ aFirst@(aFirst length - 1) == aSecond@0.
]
}.

#symbol Joinable : aPair = Join if:ctrl'Args::aPair.

#symbol Program2 =>
[
#var A := AmbValue::("the","that","a").
#var B := AmbValue::("frog", "elephant", "thing").
#var C := AmbValue::("walked", "treaded", "grows").
#var D := AmbValue::("slowly", "quickly").

AmbOperator::(A, B, C, D) seek:
=> (Joinable::(A,B) and:Joinable::(B,C) and:Joinable::(C,D)).

'program'Output << A << " " << B << " " << C << " " << D.
].


How does Amb operator work? At first we have to define set of possible values for amb operator to choose from (AmbValue). Then we ask AmbOperator to find a correct subset. Joinable symbol is used for a tricky condition of the rosetta code sample (a@(a length)==b@0). ctrl'Args symbol is used to simplify the symbol argument list (i.e. Join if:ctrl'Args::(a, b) is similar to Join if:{ first'get = A. second'get = B. } or Join if:(&first:A &second:B)).

So let's consider the code to implement Amb operator.
We start with a multi-list enumerator. I would like to remind that an enumerator is used in ELENA to execute an action for every member of a collection (similar to foreach statement in C#). Why we need an enumerator? To find a correct solution AmbOperator has to go over all possible combinations of amb operands. So let's implement it (it is declared in ext'patterns module):
#class MultiEnumerator
{
#field theEnumerators.

#role BOF
{
#method proceed
[
#shift.

ctrl'Control run &list:theEnumerators &foreach:anEnumerator => (anEnumerator proceed).

^ basic'True.
]
}

#method enumerator = $self.

#method proceed
[
#var aRetVal := ctrl'Control run &list:theEnumerators &foreach:anEnumerator =>
[
#if(anEnumerator proceed)?
[ ^ basic'False. ].

anEnumerator clear proceed.
].

^ (basic'nilValue != aRetVal).
]

#method new : aCollection
[
#shift BOF.

theEnumerators := basic'ArrayType evaluate &__array &count:(aCollection count) &filling: aCurrent => (aCollection@(aCurrent indexer) enumerator).
]

#method get = nil.
}

There is nothing special there. In the construct we create a list of enumerators for every member of the parameter. There is a special use case at the beginning (role BOF) where all enumerators are initialized (first call of proceed method). With each next call of proceed method the first enumeration goes on until it reaches the end, then it is repeated for the next member of the second enumeration and so on until the last enumeration is finished.

Now we need AmbValue enumerator:
#class AmbEnumerator
{
#field theValues.

#role BOF
{
#method proceed
[
theValues $reset.

#shift.

^ basic'True.
]
}

#method new : Values
[
theValues := Values.

#shift BOF.
]

#method proceed
[
^ theValues $next.
]

#method clear
[
#shift BOF.
]

#method get = theValues.
}

AmbEnumerator is actually an adapter which dynamically modify (mutate) AmbValue by calling private methods - $reset (AmbValue is wrapped around the first member of its collection) and $next (AmbValue is wrapped around the next one).
#class AmbValue
{
#field theValues.
#field theCurrent.

#method enumerator = AmbEnumerator::self.

#method $reset
[
theCurrent := theValues@0.
]

#method $next
[
#var anIndexer := theCurrent indexer.

anIndexer += 1.

^ anIndexer eof'is back:basic'False | back:basic'True.
]

#method new : Values
[
theValues := Values.
theCurrent := nil.
]

#union (theCurrent primary).
}

As I said before AmbValue is a proxy class (dynamic extension) over the collection of possible values. Only one value at the time can be accessible (statement #union). "Primary" message is used to return the actual object (note that theCurrent is an indexer).

And finally our AmbOperator
#symbol AmbOperator : Values =
{
seek : anExpression
[
ctrl'Control run &enumerator:exctrl'MultiEnumerator::Values &foreach: aCurrent =>
[
^ anExpression evaluate inverted.
].
]
}.

So how does it work? The key is AmbValue. With a help of ELENA magic AmbValue could be wrapped around one of its members.
    #var A := AmbValue::(1, 2, 3).
#var B := AmbValue::(4, 5, 6).

At the beginning A and B points to nil objects. But if we will call $reset method they will be equal to 1 and 4 integer constants (actually are wrapped around them, bit for other parts of the program they ARE integer numbers). After we call $next method they will be 2 and 4. Others are quite simple. AmbOperator with the help of MultiEnumerator executes the required expression for every possible combination of A and B values (i.e. 1 and 4, 1 and 5, 1 and 6, 2 and 4 and so on) until the expression is true (A * B = 8). Et voila!

P.S. The code works for ELENA API starting from 1.6.0.1 (I'm going to release it very soon). I added exctrl'MultiEnumerator and fixed several bugs in indexer implementation (without them the code for Join symbol should be like this: (aFirst literal)@(aFirst literal length - 1) == (aSecond literal)@0.).

No comments:

Post a Comment