Changing recursive Closure to TrampolineClosure in Groovy

Question

I need to construct all possible binary representations from a string containing only the characters 0, 1, and V (the wildcard). The string may be of any length (over 1000 characters) though the number of wildcards is less than 20.

For example, for the input V1V the output would be [010, 011, 110, 111]

My current implementation works but overflows the stack with a modest number of wildcards. The code is running here and shown below.

def permutts
permutts =
{
  if (!it.contains('V'))
    return [it]

  def target = it
  def res = []

  ['0', '1'].each
  {
    def s = target.replaceFirst(~/V/, it)
    if (s.contains('V'))
    {
      res += permutts(s)
    }
    else
    {
      res << s
    }
  }
  res
}
println permutts('V1V')

I've attempted to follow some of the examples of using trampoline() but I'm not even sure if that's the right approach. The API says, "...the function is supposed to perform one step of the calculation..." but each step performs two actions: substituting in 0 and 1 for V.

Here's one of my attempts, which can be run here.

def permutts

permutts =
{ it, res = [] ->
  println "entering with " + it + ", res=" + res
  if (it.contains('V'))
  {
    def s = it.replaceFirst(~/V/, '1')
    permutts.trampoline(s, res)

    s = it.replaceFirst(~/V/, '0')
    permutts.trampoline(s, res)
  }
  else
  {
    res << it
  }
}.trampoline()
println permutts('VV')

The output is:

entering with VV, res=[]
entering with 0V, res=[]
entering with 00, res=[]
[00]

At least it's doing something but I don't understand why it doesn't keep going. Can anyone explain what I'm doing wrong or suggest a different way to tackle this problem?

Answer 1

Groovy's trampoline()provides tail call optimization, so it should be used for closures/methods that invoke themselves in the last instruction executed (tail).

Hence, a better solution would be a classic "head/tail" processing (added println to track calls):

def permutts
permutts = { s, res ->   
    if (s.length() == 0) {
        println "s = $s, res = $res"
        res
    } else {
        println "s = $s, res = $res"
        if (s[0] == 'V') { // s[0] ~ list.head()
            res = res.collect({ it = it + '0' }) + res.collect({ it = it + '1' })
        } else {
            res = res.collect({ it = it + s[0] })
        }

        permutts.trampoline(s.substring(1), res) // s.substring(1) ~  list.tail()
    }
}.trampoline()

Examples:

permutts('VV', [''])     
  s = VV, res = []
  s = V, res = [0, 1]
  s = , res = [00, 10, 01, 11]
  Result: [00, 10, 01, 11]

permutts('0V0', ['']) 
  s = 0V0, res = []
  s = V0, res = [0]
  s = 0, res = [00, 01]
  s = , res = [000, 010]
  Result: [000, 010]

Regarding your code, from TrampolineClosure javadoc:

A TrampolineClosure wraps a closure that needs to be executed on a functional trampoline. Upon calling, a TrampolineClosure will call the original closure waiting for its result. If the outcome of the call is another instance of a TrampolineClosure, created perhaps as a result to a call to the TrampolineClosure.trampoline() method, the TrampolineClosure will again be invoked. This repetitive invocation of returned TrampolineClosure instances will continue until a value other than TrampolineClosure is returned. That value will become the final result of the trampoline.

That is, the substitution that is made in the tail call optimization. In your code, the whole chain of TrampolineClosures returns as soon as one of them does not return a TrampolineClosure.

From groovy 2.3, you can use @TailRecursive AST transformation for tail call optimization:

import groovy.transform.TailRecursive

@TailRecursive
List permutts(String s, List res = ['']) {   
    if (s.length() == 0) {
        res
    } else {
        res = (s[0] == 'V') ? res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + s[0] })       
        permutts(s.substring(1), res)
    }
}

EDIT:

Just to complete my answer, the above can be done in one line with the functional fold, which in Groovy is inject (uses the head of the collection as the inital value and iterates over the tail):

assert ['000', '010'] == ['0', 'V', '0'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })
assert ['00', '10', '01', '11'] == ['V', 'V'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })