1

This question is about a high-level templating language called "Liquid". Why have I tagged it assembly? Because I imagine assembly programmers have more experience with manually handling multiple recursion.

In liquid you can create "Functions" by including a file with certain parameters:

{% include file var1="a" var2="b" %}

So far so good - we can create an effective multiple recursive loop with this if we have a way to return.

Unfortunately, liquid is one of the most handicapped forms of logic I've ever seen. It's barely turing-complete. There are no return values, there is no scope, and the arrays are just strings you can split.

With the multiple recursive function I'm writing, the global variables get clobbered by subcalls. I don't even have a stack to work with here!

If I set a boolean true on a tree node and recurse into lower nodes, if any of the lower nodes (Or subsequent nodes on the same level) set it it will clobber the higher node's active value.

This limits my options somewhat:

  • Stuff them in a global variable and stash the variable before calling a subnode
    • Oh no! The stash will get clobbered too!
  • Some other mysterious logic I've been trying to find but can't.

I'd like the mysterious logic please!

Taking advantage of the fact that active always propagates upwards, there should be some order of operations that accomplishes it correctly, but I've been bashing my head against this for 3 days and I'm having trouble thinking straight.

Here is the code in question though reading that will probably make this more confusing.

J V
  • 11,402
  • 10
  • 52
  • 72
  • 1
    Read more about [continuations](https://en.wikipedia.org/wiki/Continuation), [continuation passing style](https://en.wikipedia.org/wiki/Continuation-passing_style), [call stack](https://en.wikipedia.org/wiki/Call_stack), and the references I gave [here](http://programmers.stackexchange.com/a/303797/40065). Maybe Liquid is the wrong tool. Did you consider [HOP](http://hop.inria.fr/) ? – Basile Starynkevitch Nov 29 '15 at 08:38

2 Answers2

2

Compilers (and asm programmers) implement multiple recursion by pushing state on the stack, making the call, then popping state off the stack. So local variables and args are on the stack.

This works recursively, as long as there is enough stack space for the max call depth.

I think to make recursion work (other than tail-recursion of course), you need to implement some sort of data structure that can be used as a stack, pushing state onto it and popping it back off.

Fully general recursion requires being able to save and restore state with whatever depth is needed.

If you don't have any variable-sized storage, you could implement a small fixed-size stack with global variables like stack1, stack2, stack3, etc., and a counter to act as a stack pointer. You just need as many variables as the max depth of your recursion.

You might possibly be able to implement your specific algorithm with a function that isn't actually recursive, though. You said something about traversing a tree? Maybe see Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time for ideas. Some of them involve modifying the tree. Of course, if your tree nodes have parent pointers, traversal is easy because you can find your way back up after going down one side.

Community
  • 1
  • 1
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
  • Thanks for actually answering the question! Unfortunately, I can't make it iterative since I don't know the depth or the width of the user input, and I can't use numbered global variables since liquid doesn't have any "variable variables" (Unless I wanted to limit it to a maximum depth) I should be able to store state as characters in a string and pop them off the end with every iteration, but liquid will make that harder than it needs to be so it will take quite a bit of work :/ – J V Nov 29 '15 at 09:57
  • @JV: Yes, I meant limit it to a max depth. With a big ugly `switch` or something on the stack pointer, to select the right global variable. That's what I meant by "small fixed-size"... Sounds like liquid is the wrong tool for the job, or you should choose a data structure you can traverse more easily. I can't imagine that this will perform very well... Using a string as a stack sounds reasonable, if you can encode your state into fixed-size chunks nicely. I'd recommend writing an iterative algo that uses its own stack to track just the state it needs, rather than a call-stack. – Peter Cordes Nov 29 '15 at 10:03
  • 2
    Well the whole point is to render a menu in jekyll, and jekyll uses liquid so that's all I've got to work with. The troublesome state is a single boolean so I'm just going to append a `0` or `1` to the string and pop it off afterwards – J V Nov 29 '15 at 11:45
0

In my recursive includes I do this

{% assign n = include.n %}

{% if n == nil %}
  {% assign n = 0 %}
{% endif %}

++++ Do something on n
{% assign n = n  | plus: 1 %}

{% if n < something %}
  {% include self.html n=n %}
{% endif %}

++++ Reverse value of n to parent value
{% assign n = n  | minus: 1 %}

Live example here

David Jacquel
  • 51,670
  • 6
  • 121
  • 147
  • Yes but this doesn't pass state, unless I used depth as a power of 2 to create a bitmask and pass it to the next level, however I think this would be very complicated (And would only work to the width of the architecture ruby is built in) – J V Nov 29 '15 at 11:47
  • Ooh, by your example you do some tricky stuff with jekyll too - what do you think of my menu so far? One for automatic generation by url and one for generation by `_data` – J V Nov 29 '15 at 11:50
  • In general I think data driven menu is redundant. Your automenu is working but what about page order ? – David Jacquel Nov 29 '15 at 12:56
  • I can throw a sort parameter in there somewhere, I'm sure. That said, there are an awful lot of people that would like a custom menu (Just being able to reorder stuff for instance) – J V Nov 29 '15 at 14:00
  • Added sorting and reverse sorting - raise an issue if you can think of anything else :) – J V Nov 29 '15 at 14:21