Why, yes, LabVIEW 8.5 does have recursion...

[Aristos Queue]

Users: Recursion? In LV8.5? Did he really say that?

Me: Yep.

Users: This isn't some VI Server hocus pocus is it?

Me: Nope.

Users: This is honest-to-goodness-subVI-on-its-own-block-diagram recursion, right?

Me: Yep.

Users: What's the catch?

Me: Well, you've got to use LVclasses to get it. Mwuhahaha!

Details? Check out LV8.5, and look at

examples\lvoop\Recursion\Demo Recursion.vi

Ah. I feel better. I've been wanting to announce that for many months now.

Eventually someone will ask why non-LVClass VIs can't have recursion. The answer is, they can, and someday they will. But LVClasses were already positioned to take advantage of some of the early refactoring work needed to make recursion possible. For now, I like to think of recursion as bait, to draw users into trying LVClasses who wouldn't otherwise. :-)

[Guillaume Lessard]

It seems that there are still no LV Classes in the real-time module, though.

That's unfortunate! What are the reasons this is so?

[jaegen]

QUOTE(Guillaume Lessard @ Aug 3 2007, 02:10 PM)

It seems that there are still no LV Classes in the real-time module, though.

That's unfortunate! What are the reasons this is so?

... poor Stephen ... he tries so hard to make us happy ... :headbang:

[crelf]

QUOTE(Aristos Queue @ Aug 4 2007, 06:29 AM)

For now, I like to think of recursion as bait, to draw users into trying LVClasses who wouldn't otherwise.

[Tomi Maila]

QUOTE(Aristos Queue @ Aug 3 2007, 11:29 PM)

Users: Recursion? In LV8.5? Did he really say that?

Me: Yep.

Users: This isn't some VI Server hocus pocus is it?

Me: Nope.

Users: This is honest-to-goodness-subVI-on-its-own-block-diagram recursion, right?

Me: Yep.

Users: What's the catch?

Me: Well, you've got to use LVclasses to get it. Mwuhahaha!

Oh, this is almost like a http://en.wikipedia.org/wiki/Socratic_method' target="_blank">Socratic dialogue... This is definitely the single best new feature in LabVIEW since the introduction of LabVIEW classes in LV 8.20 and actually making them work in LV 8.2.1

[Jim Kring]

QUOTE(Tomi Maila @ Aug 3 2007, 02:40 PM)

Oh, this is almost like a http://en.wikipedia.org/wiki/Socratic_method' target="_blank">Socratic dialogue... This is definitely the single best new feature in LabVIEW since the introduction of LabVIEW classes in LV 8.20 and actually making them work in LV 8.2.1

I agree! I've been using LVClasses to try to implement some well-established design patterns and found that recursion is very necessary.

Thanks AQ :worship:

[Ton Plomp]

QUOTE(Aristos Queue @ Aug 3 2007, 09:29 PM)

Me: Well, you've got to use LVclasses to get it. Mwuhahaha!

Details? Check out LV8.5, and look at

examples\lvoop\Recursion\Demo Recursion.vi

Am I right is this just plain recursion?

A->A?

And not 'branched' recursion:

A->B->A

Ton

[Aristos Queue]

QUOTE(tcplomp @ Dec 29 2007, 12:53 PM)

Am I right is this just plain recursion?

A->A?

And not 'branched' recursion:

A->B->A

Ton

The demo is A->A. But LV8.5 can do both. All the VIs involved in the recursion must be capable of recursion (meaning dynamic dispatch with shared reentrancy).

[Ton Plomp]

QUOTE(Aristos Queue @ Dec 30 2007, 04:10 AM)

The demo is A->A. But LV8.5 can do both. All the VIs involved in the recursion must be capable of recursion (meaning dynamic dispatch with shared reentrancy).

Confirmed, I was confused by the fact that I had a ton of errors where one was that a possible recursion was removed. But as soon as I got everything straightened it worked. (You can see this in version 1.2 of the Variant Probe)

One thing I dislike is that a 'dynamic dispatch' VI can't be part of a polymorphic VI.

Ton

[robijn]

Hoora ! Implementing your own "stack" was often a bit cumbersome (although it forced you to think about the problem...)

I have had for a long time the following text in the footer of my mail - just to illustrate:

To understand recursion, we must first understand recursion.

And a happy new year to all of you ! (sorry, this is terribly off topic)

Joris

[Falevoz Y.]

The thing that miss to me is that we can't have a class1 in data members of class1...

[LAVA 1.0 Content]

FYI

Traditonal VI Re-cursion does now handle the branch version

A > B > A

No LVOOP required.

Ben

[AdamRofer]

QUOTE(Aristos Queue @ Aug 3 2007, 12:29 PM)

Eventually someone will ask why non-LVClass VIs can't have recursion. The answer is, they can, and someday they will.

They sure can!

Just pop in this bad boy (commence shuddering and fear): http://forums.lavag.org/Recursion-t9832.html' target="_blank">Rusty Nail

Use caution with them, though. I am not perfect. NI will provide much more stability in this arena than I will with my rusty nails.

[Aristos Queue]

QUOTE(Falevoz Y. @ Jan 2 2008, 09:14 AM)

The thing that miss to me is that we can't have a class1 in data members of class1...

There is no programming language in existence that allows this. None. What you're asking for would be, in C++, this:

class X {

____X blah;

}

Not legal. What is legal is:

class X {

____X *blah; // Very important asterisk!

}

i.e., a pointer to the type. Defining the data within the data would be a type of infinitely large size. The second one is possible in LabVIEW. Please look in the LAVA forums for the topic about the Map class.

[Tomi Maila]

QUOTE(Aristos Queue @ Jan 6 2008, 09:10 PM)

There is no programming language in existence that allows this. None.

Actually there are languages that allow recursive types without reference mechanism. However I think at least in eager languages there must be a mechanism to end the recursion. Lazy languages could possibly allow infinite recursion that simply is not evaluated until needed. C++ pointer mechanism that AQ referred to is one way to end the recursion. Anohter way to end the type recursion is to allow a variable to be of type 1 or type 2. Let's use symbol '|' to denote for this type of or. Then we can define a recursive class

Class A(y) {

x : A | Nothing

= y

}

where the class A has a variable x that can either be of class A or of class Nothing. The class Nothing is a empty Class with not functions and not private data. We now can define a few variables of class a.

a1 : A(Nothing);

a2 : A(a1);

a3 : A(a2);

A lazy language could have something like this

Class

NaturalNumber

(

initialValue

) {

next

:

NaturalNumber

(

initialValue

+1)

function

getValue

{ return

initialValue

}

}

The constructor parameter initialValue is a number that is passed to the class when created. We assume that constructor parameters are stored byt the language as a class private data automatically. The class has a private data called next. However next not initialized until referred to; lazy languages compute data only when the data is actually needed. Now we can define all natural numbers the following way

naturalNums = NaturalNumber(0); // initialize class NaturalNumber with constructor parameter 0.

We can get the three first natural numbers with the following lines

naturalNums.getValue; // returns 0

naturalNums.next.getValue // evaluates initialValue (1) of naturalNumber.next and returns it

naturalNums.next.next.getValue // evaluates initialValue (2) of naturalNumber.next.next and returns it

So to conclude, AQ, never say never;)

APPENDIX - Notation

Class definition:

Class ClassName(list of constructor parameters) {

class body

...

}

Function deifinition;

function functionName(list of arguments)

{

function body

...

}

Variable definition:

varname : VarType | AlternateType | AlternateType [= initial_value]

Variable definition with constructor parameters:

varname : VarType(constructor arguments)

Class construction:

• Class argument list is stored as if it was private data.
  
• Class body is executed
  

Edited several times, last edit at 8.17 pm GMT

--

Tomi

[Falevoz Y.]

CITATION(Aristos Queue @ Jan 6 2008, 08:10 PM)

There is no programming language in existence that allows this. None. What you're asking for would be, in C++, this:

class X {

____X blah;

}

Not legal. What is legal is:

class X {

____X *blah; // Very important asterisk!

}

i.e., a pointer to the type. Defining the data within the data would be a type of infinitely large size. The second one is possible in LabVIEW. Please look in the LAVA forums for the topic about the Map class.

Yeah, that's the way I was thinking about. I wanted to be short but I agree, the asterisk is very important. I didn't find the way to do that. Thanks for the topic. I'll have a look soon.

[robijn]

QUOTE(Aristos Queue @ Jan 6 2008, 08:10 PM)

class X {

____X *blah; // Very important asterisk!

}

i.e., a pointer to the type. [...] The second one is possible in LabVIEW.

Is it really ? I thought we could not build a doubly linked list.

Joris

[Aristos Queue]

QUOTE(robijn @ Jan 7 2008, 04:38 AM)

Is it really ? I thought we could not build a doubly linked list.

You can't. The pointer type is allocatable but not assignable. The challenge of building a recursive datatype that is dataflow safe is an open challenge.QUOTE(Tomi Maila @ Jan 6 2008, 01:43 PM)

a1 : A(Nothing);a2 : A(a1);a3 : A(a2);

To my eye, this results in the same behavior as LV already has -- allocatable but not assignable. You still can't build the double-linked list / graph with this setup. The only structure that holds for that is the indexed array setup, a structure that stores a set of nodes and a set of edges. Care to contradict?

[Tomi Maila]

The discussion in this thread insipred me to post an article on recursive types to my blog at ExpressionFlow.

QUOTE(Aristos Queue @ Jan 7 2008, 04:06 PM)

Care to contradict?

No.

[robijn]

QUOTE(Aristos Queue @ Jan 7 2008, 03:06 PM)

You can't. The pointer type is allocatable but not assignable. The challenge of building a recursive datatype that is dataflow safe is an open challenge.To my eye, this results in the same behavior as LV already has -- allocatable but not assignable. You still can't build the double-linked list / graph with this setup. The only structure that holds for that is the indexed array setup, a structure that stores a set of nodes and a set of edges. Care to contradict?

Well, not against that part of the story. I would object against the comparison being made with C.

Only with lots of knowlegde of the internals it's possible to know if new memory will be allocated or that existing memory will be reused. As a programmer, I don't consider this interesting. I want to use my objects, I don't want to think about how I should shuffle with the various parts of memory. Only when things are too slow, I am going to optimize my code and remove duplicate allocations and copies.

The first C example would contain the data right in the parent objects. This would result in an infinite size of the object, as each child object would contain yet another fully sized object. But in LabVIEW we cannot control how the data is stored. Advanced users know that complex data structures are stored with a pointer to them. But in theory, the storage behaviour of for example a string could be changed by NI at any time, and the resulting programs would still run the same (apart from big timing differences). The current implementation is one of multiple possible implementations, where the semantics are the same.

The structure of how the data is stored is much more similar to Java, so I consider that a beter comparison. In Java, just as in LabVIEW, you have no direct influence on how the compiler performs its actions, but you know the end result. You cannot access pointers there. When you store an object, internally a pointer is stored, just like it's done in LabVIEW.

There is no fundamental problem with recusive structures in Java, while you cannot use use dangerous pointers like in C. And what is nice is that you can "store" a NULL object.

Joris

PS Very clear article Tomi !

[Falevoz Y.]

CITATION(Aristos Queue @ Jan 6 2008, 08:10 PM)

Please look in the LAVA forums for the topic about the Map class.

I had a look to the project in that topic. This is more or less the way I use in my project but in my case it's not the most natural way.

I heard about tricks that allow to use object reference but didn't find anything on the web... If you have links, you will have my eternal gratitude :worship:

By!

[Tomi Maila]

Tomi> The discussion in this thread insipred me to post an article on recursive types to my blog at ExpressionFlow.

robijn> PS Very clear article Tomi !

Thanks I promised to keep posting on challenging subjects as well Let's see if LabVIEW 10.25½ includes recursive types

[Tomi Maila]

Hi,

Tail recursion optimization is a compiler optimization mechanism where a recursive call is made to the function instance itself when possible. In the context of LabVIEW this would mean that when a VI makes a recursive call to itself, the call would be executed by the same VI clone when possible. Tail recursion optimization greatly increases recursion performance as there is no need to reserve a new clone for each recursive call. The tail recursion optimization can be made when the output buffers of a recursive call are not used for anything on the block diagram of the calling VI but instead they are one of the following: 1) directly connected to indicators, 2) unconnected or 3) connected to structure borders or similar non-executed nodes. Tail recursion optimization cannot be made when an output of a subVI node is connected to a node or other operation that needs the data in the buffer to execute. Tail recursion optimization can also be made across subVI borders as long as the same conditions apply across the subVI borders. That is A.vi can call B.vi that calls A.vi so that the call can be tail recursive optimizined if the call of A in B can be tail recursive optimized and the call of B in A can be tail recursive optimized.

I just tested if LabVIEW 8.5 recursion supports tail recursion optimization and it doesn't. See the attached VI for computing factorial in a way that would be tail recursion optimizable. My question is targeted for LabVIEW R&D, is there a special reason for the fact that tail recursion optimization isn't supported by LabVIEW? Will you support in the (near) future LabVIEW versions? Tail recursion optimization increases

[Aristos Queue]

QUOTE(Tomi Maila @ Jan 16 2008, 08:54 AM)

Is there a special reason for the fact that tail recursion optimization isn't supported by LabVIEW?

Yep. Rule 1: Get it working before you optimize it. Just getting recursion into LV has been a Hurculean effort of many years, bordering on a decade. I found a hole in the barrier that allowed me to get it working for dynamic dispatch VIs, so I exploited that in order to provide a highly requested feature. Anything beyond that was not in my mind. QUOTE

Will you support in the (near) future LabVIEW versions?

I don't know. The compiler optimization teams (plural) are doing all sorts of upgrades over the next few releases. Whether or not recursion gets any attention from them depends largely upon how much usage of it we see in the field. See, recursion is a highly requested feature, but usually in the "my goodness, you can't even do recursion, what kind of language are you?" sense, and only very rarely in the "I have a real-world need for recursion; could you please add it?" sense. This is one of those cases where the biggest bang-for-buck comes from just having the feature at all, not from having it work well.

We may very well have all sorts of optimizations in the pipeline that I don't know about... My slipping recursion into 8.5 was something of a surprise to everyone -- the rest of LV VIs are still a ways away from it, and so optimizations for recursion hadn't really been discussed here-to-fore. It may be that tail recursion is planned to go along with the rest of LV VIs becoming recursion-capable.

To take a line from the finance industry: "Past performance is not indicative of future optimizations." :-)

QUOTE(Tomi Maila @ Jan 16 2008, 08:54 AM)

Will you support in the (near) future LabVIEW versions?

I asked Optimizations and got this tidbit back:

There are a lot of optimizations for the general case that would be tackled before special gencode for tail recursion. The big ones being further size reductions for reentrant dataspaces and the ability to create stack based dataspaces.

Additionally I would say that indirect tail recursion is much harder to detect than direct tail recursion and most direct tail recursion can be fairly easily expressed as a non-recursive loop.

So there's your answer.

[Tomi Maila]

QUOTE(Aristos Queue @ Jan 17 2008, 12:39 AM)

I asked Optimizations and got this tidbit back:

There are a lot of optimizations for the general case that would be tackled before special gencode for tail recursion. The big ones being further size reductions for reentrant dataspaces and the ability to create stack based dataspaces.

Additionally I would say that indirect tail recursion is much harder to detect than direct tail recursion and most direct tail recursion can be fairly easily expressed as a non-recursive loop.

So there's your answer.

Thanks for the answer