The following code sample represents a basic recursion algorithm using the JEMS services within Presto to trace the dependency tree for any published mashup. It should be generally applicable to any recursive design.
<mashup xmlns:xsi= "http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.jackbe.com/2008-03-01/EMMLSchema ../src/schemas/EMMLSpec.xsd"
xmlns="http://www.jackbe.com/2008-03-01/EMMLSchema"
xmlns:macro="http://www.jackbe.com/2008-03-01/EMMLMacro"
name = "RecursiveDependencies">
<operation name="invoke">
<!-- Service to Check -->
<input name="service" type="string" default="depRoot"/>
<!-- Result to Return -->
<output name="result" type="document"/>
<!-- Temporary Storage for this Presto Service Call Result -->
<variable name="tResult" type="document"/>
<!-- Get Immediate Dependencies for this Service, Continue on Failure -->
<invoke service="JEMSServiceHelper" operation="getDependentServices"
inputvariables="service" outputvariable="tResult" onerror="continue"/>
<!-- If there is no faultcode -->
<if condition="$faultcode=0">
<!-- if successful -->
<!-- new variable to hold the current dependencies after parsed -->
<variable name="allResults" type="document"><dependencies/></variable>
<!-- loop through the dependencies for this call -->
<foreach variable="subServiceName" items="$tResult/services//service/@name/string()">
<!-- recurse on result for each service -->
<invoke service="RecursiveDependencies" operation="invoke"
inputvariables="subServiceName" outputvariable="tResult" onerror="continue"/>
<!-- append the dependencies for this checked service as a dependency for the original input service -->
<appendresult outputvariable="allResults">
<dependentService>
{$tResult/xml/dependentService/service}
{$tResult/xml/dependentService/dependencies}
</dependentService>
</appendresult>
</foreach>
<!-- success -->
</if>
<!-- this code block would not have executed if the service queried had no dependencies -->
<!-- this would have indicated a leaf node in the dependency tree, and served as a base case for the recursion -->
<!-- append the dependencies found as dependencies for the queried input service -->
<appendresult outputvariable="result">
<dependentService>
<service>{$service}</service>
{$allResults}
</dependentService>
</appendresult>
</operation>
</mashup>
This cannot be published without first commenting out the recursive call. Once it has been published, Presto will recognize it as a valid target service for the recursive 'invoke' command and this block can be uncommented and republished to create a functioning recursive EMML script.
That is some very fancy stuff! I am guessing you've used this technique in real-life before. Care to share an example or two?
---
Mashup Developer Community Manager. Find me on Blogger, Twitter, LinkedIn, Facebook, and YouTube.
I assume the technique you are referring to is recursion. This is a technique that I have used before and one that is used extensively in the field of computer science. By far the most common general purpose use for recursion is in parsing trees not unlike the dependency tree traversed in the above example. Other trees suchs as file structures or even biological taxonomy trees would also be traversed using recursive algorithms. Some mathematical functions are also best implemented by recursive algorithms. The most common example, frequently used as an introduction to the concept of recursion in CompSci courses, is the factorial operation, (x!) = (x*x-1*x-2*...*2*1).
The keys to any recursive algorithm are the base case and the recursive cases. The recursive cases are not dissimilar from loops, except they run by recalling the same recursive function from within that function. This allows a recursive function call to loop through data as it is processed by simply recalling the function with new data as that data is processed. The base case indicates the final step of the recursive algorithm where the results should be returned through the function call stack to the original caller. As each recursive call after the base case returns, the results are included in the return from the next recursive call until the final result is available to the original caller. In the above example, the recursive cases called the same dependency analyzer on the dependencies of the orignal parameter until the base case was reached, when no more dependencies were available to recurse on. The similarities between the above EMML script and the pseudocode below for implementing a recursive factorial solution should illustrate the commonalities between recursive algorithms.
function factorial(x) {
// base case, 1! = 1
if (x == 1) {
return 1;
}
// recursive case, x! = x*(x-1)!
return x*factorial(x-1);
}
The comments should also illustrate why the factorial operation can be defined recursively even with mathematical notation.
(x! = x*(x-1)!, 1! = 1).