Darren's Weekly Nugget 01/04/2010

[Ben]

---

Intaris wrote:

@Ben,

I've done a reference-based adaptive system just like yours and I used Shift registers.

I have written a SR version of the software before I've managed to get my head around the Recusrion idea.....

Shane.

---

Well here I go for the second day in a row ... "Dooh!".

You sent or posted a version!

Ben

PS: I have no excuse, only a possible explanation. "When fifty and three you are, try remembering 1103252 you post you read."  

[Darren]

---

@tst wrote:

...there are proofs showing that any recursive algorithm can also be implemented using a stack.

---

That reminds me of another great example.  Several years ago I was asked to re-write a certain NI toolkit.  One part of the toolkit had some code that parsed a third-party file format.  This code used recursive VI server calls, since there were many nested data structures in the file.  For one particularly large file, the code took over 24 hours to complete the parsing.  As part of my re-write, I trashed the old parser and wrote a new one...one which processed the file line-by-line, keeping a stack of data describing the current nesting level of the line I was on.  With this approach, the parsing time of that large file went from 24 hours to about 10 minutes.

Ever since then, I've written many parsers (some for XML, some for other formats), and I always take the line-by-line approach with a stack.

[F._Schubert]

Maybe we need some benchmarks with 2009. Recursion is not necessary slow, I was told that in languages like mathematica, nothing beats a map function.

To explain a bit: 'map' is the big paradigm of functional programming, it takes a function and a set of parameters and recursivly applies the function on these parameters. A simple example might be map(add, [0,1,2,3,4,5]) which will retur 15 (the Sum). In those languages this is the fastes way to do this. In fact, in LV it still seems to be impossible to write a map function (although I guess it can be done with LVOOP + native recursion, but the OOP overhead would be a major issue).

As a side note, the first weeks at univerity (as an engineer-to-become) we were doing recursion in every class. This isn't just a matter of code, but of pure logic. To get recursion in your head, you just need to get familiar with the mathimatical proof of Induction.

Felix 

[shb]

There is no recursion in the map function IMHO. It is a short and quick version for the following loop:

result = 0

For[ j=1,j <= Length[myData], j++, result = add(result, myData[[j]])  ]

It is a good example for a loop with a local variable (shift register in LabVIEW).

map function in LabVIEW Code:

Message Edited by shb on 01-06-2010 09:21 AM

[F._Schubert]

This is just a for loop, here the definition of map in haskel (actually my definition above is wrong):

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

of course you can code this task using a for loop. But I want to shed some light of the differences (and what we can't do in LabVIEW):

* x:xs isn't an array but a list, which is a recursive data structure (the list x:xs consists of the element x and the list xs). This isn't a clear issue for us LV'ers, but for normal C an array is always of fixed size while the list is real dynamically in size. The list is also a very primitive example for a recursive data structure, more general you can define a graph (a point connects to a number of other points), where the tree is just a subset of graph.

* The function f can be any function. Ths is also a concept alien to LabVIEW, I cannot pass a function via a wire.

* The same function can be called with different parameters, this is an extension to the polymorphism we know (overloading). You see above that there are actually two definitions of map: the first for an empty list and the second for a list.

Please not, that it's about 10 years ago I was using stuff like that, so I might write a lot of wrongs about the concept of functional programming.

Back to the beaty of the recursion we now have as 'native'. There is a set of strategies to develop fast algorithms which translates well to recursive implementations, such as 'divide-an-conquer'. As a task, try to write a function that returns the max value of an array in less than O(n) (a for loop compareing the shift register value with each element of an array will iterate n-times, but we only need O(sqrt(n)) comparisons).

Felix

[F._Schubert]

This is a recursive max finder that performs O(sqrt(n)) (I'm not really sure), the old way of VI Server recursion. It is terrible slow in LV 7.1., there are performance improvements in one of the 8.x versions. Maybe somone can recode it in 2009 with native recursion (and post a snippet) and do some benchmarks (I do not have 2009, but really enjoyed the ease of recursion when using an eval-version).

to make the snippet working, you need to set reentrant execution.

Felix

[Intaris]

If you can show me what's in the other cases then I'll whip up an example without recursion....

Shane.

[F._Schubert]

Simple:

Case ..0 returns -Inf

Case 1 returns (Index Array)

Case Error returns NaN

Felix

[Ray.R]

Thanks for letting us know about the recursive vi.  Yep..  I simply dragged the icon into its own block diagram and voila... a recursive vi was born.  Som configuration was necessary to make it active (right-click > call setup...)

I can't think of any reason to use this other than coding algorithms...  But so far the While Loop and SR have been the way to go.  Who knows...  maybe another pet project after I get started on the other 2 that have been on hold for too long.. 😉

[Jarrod_S.]

I've always wished that LabVIEW could support data type recursion in some form or fashion, meaning a typedef or class could contain a reference to itself or a queue reference to itself. I think this would open up many more scenarios, such as tree data types and linked lists. I know there are some OO hacks to get this working, but they feel a little odd to me.

I think there's a theorem that any recursive pattern can be recoded to use a stack-based pattern as Darren described, even though some would be a little ackward. But here's one cool thing you can do with recursion in LabVIEW that can't be done with just queues. You may be able to solve the same problem, but this implementation achieves it in parallel. Pretty cool!