11 Replies Latest reply on Oct 20, 2016 9:36 AM by destroid

    Understanding a tail recursive FileMaker Custom Function.

    NickLightbody

      This is just for any non-mathematicians out there for whom recursion is not second nature. Filemaker has offered recursion since 2007 and this is the first time I felt I understood tail recursion, so this may be helpful for a few other former Arts students like me.

       

      Sometimes, when doing encryption it is useful to shuffle sets of characters, for example when creating substitution keys.

      In the past I have just written simple scripts in Filemaker to do this because, although I have used and adapted recursive custom functions several times, I have never really understood the difference between a normal recursive function and a tail recursive function.

       

      This is important because the normal form is limited to 10,000 cycles in FileMaker but the tail form can run to 50,000 cycles.

       

      The other day I had to create a shuffle routine within a database definition hence, as I couldn't script it, I had to work out how to create a suitable recursive function.

       

      A quick search found an erudite explanation by RayCologon from 2006 which explained the difference...

       

      http://www.filemakertoday.com/com/archive/index.php?t-9986.html

       

      As ever, thank you to Ray for his clear explanation - how does he know all these things!

       

      Here is the key quote: "Tail recursion has nothing to do with whether you 'loop' backwards from the end or forward from the beginning. What matters is how values accumulate and are passed down through successive function calls (and in particular, whether the function must feed values via a temporary memory 'stack' in the course of its operation). In the simplest terms, recursive functions that are constructed so that they don't depend on the stack are tail recursive."

       

      In other words, it is tail recursive if you pass all the results of the expression on to the next iteration as parameters without creating local variables.

       

      With that understood it was fairly simple to construct my shuffle function so that it output the shuffled string and a control value, so the control value reduced by 1 on each call and the result of the expression no longer called itself when the control had reduced to zero.

       

      Here it is.

       

      /*

      xShuffle

       

      FileMaker Custom Function - Tail Recursive

      By Nick Lightbody September 7th, 2015

      Purpose: To shuffle a string

      Syntax: xShuffle ( string; control )

      Input: string - to be shuffled

      Input: control - number of times xShuffle should call itself i.e. to control the extent of the shuffle

      */

       

       

      Let([

      s=string;

      c=Case(control<1;1;control);

      L=Length(s);

      r=Int(L * Middle(GetAsText(Random);3;2)/100);

      x=Middle(s;r;1);

      y=Substitute (s;x;"") & x;

      c=c-1

      ];

      Case( c>0 ; xShuffle( y ; c ) ; y )

      )

       

      Do please suggest how this can be improved - note that the control parameter is required since otherwise it can't be passed on to the next call - I had of course tried this as fully automatic based on the length of the string - which doesn't work.

       

      Cheers

      Nick Lightbody

      September 9th 2015

        • 1. Re: Understanding a tail recursive FileMaker Custom Function.
          erolst

          One way to get rid of the control argument is to use a $var; another way is to pass a combination of data to be processed and intermediate result within the single argument; e.g.:

           

          /*

          xShuffle_eos

          FileMaker Custom Function - Tail Recursive

          By Nick Lightbody September 7th, 2015 – Modified by Oliver Stroh 09-SEP-2015

          Purpose: To shuffle a string

          Syntax: xShuffle ( string )

          Input: string - to be shuffled

          */

           

          Let ( [

            s = GetValue ( string ; 1 ) ;

            resultString = GetValue ( string ; 2 ) ;

            newIndex = Ceiling ( Length ( s ) * Random ) ;

            newChar = Middle ( s ; newIndex ;1 ) ;

            remainingString = Replace ( s ; newIndex ; 1 ; "" ) ;

            resultString = resultString & newChar

            ] ;

            Case (

              IsEmpty ( remainingString ) ;

              resultString ;

              xShuffle_eos ( List ( remainingString ; resultString ) )

            )

          )

           

          Note that Replace() only gets rid of the character at the randomized position, while Substitute() clears all that character's occurrences – which may or may not be what you intended.

           

          And, of course, the passing mechanism would have to be modified if the original string could contain CRs.

          • 2. Re: Understanding a tail recursive FileMaker Custom Function.
            Mike_Mitchell

            "As ever, thank you to Ray for his clear explanation - how does he know all these things!"

             

            'Cause he's a genius?  

            • 3. Re: Understanding a tail recursive FileMaker Custom Function.
              erolst

              Mike_Mitchell wrote:

              'Cause he's a genius? 

               

              I think “'cause he makes a living out of explaining this stuff” is what should first come to mind.

              • 4. Re: Understanding a tail recursive FileMaker Custom Function.
                beverly

                Nah. Genius comes to mind.

                 

                -- sent from myPhone --

                Beverly Voth

                --

                • 5. Re: Understanding a tail recursive FileMaker Custom Function.
                  FileKraft

                  "the one-eyed is king under the blind .."

                   

                  recursion is 11th grade math (used for induction)

                  • 6. Re: Understanding a tail recursive FileMaker Custom Function.
                    NickLightbody

                    Hi Erolst

                     

                    Thank you for suggesting how to simplify this function, I appreciate the time you have spent on this.

                     

                    You are shuffling each character once. With a set control the shuffling can of course continue as many times as one wishes.

                     

                    As you may know my main theme is performance, i.e. my recent paper on FMS Performance,  so I did a quick test with xShuffle and xShuffle_eos, over 11,000 iterations with a simple 37 char (a-9) substitution string.

                     

                    xShuffle typically took 6.25 secs.

                    xShuffle_eos typically took 6.9 secs

                     

                    So the convenience of not having to specify the control seems to cost about 10% in performance.

                     

                    I tried xShuffle with Replace instead of Substitute and the speed was fractionally slower, but very little.

                     

                    I agree that Replace is the logically the correct function here so I have changed xShuffle accordingly.

                     

                    Thanks again

                     

                    Cheers, Nick

                    • 8. Re: Understanding a tail recursive FileMaker Custom Function.
                      jbante

                      NickLightbody wrote:

                       

                      In other words, it is tail recursive if you pass all the results of the expression on to the next iteration as parameters without creating local variables.

                      Yes and no. Creating (and later cleaning up) local variables is one method of making a FileMaker custom function tail recursive, as @erolst explained. The data from one recursive call to the next can all be passed as parameters, and some folks certainly prefer that, but using local variables achieves the same effect.

                       

                      To be more precise, a custom function is tail recursive if at each function call it either calls itself again, or returns the final result, but never a combination of the two:

                       

                      If ( done ; result ; /* Else */ TheSameFunction ( arguments ) )    // tail recursive

                       

                      If ( done ; result ; /* Else */ result & TheSameFunction ( arguments ) )    // not tail recursive

                       

                      The benefit of the tail recursive form (both for FileMaker and for other programming tools) is that the execution of a tail recursive function can be optimized to work as a simple loop under the hood rather than maintaining a full stack of recursive calls. For a non-tail-recursive function, the value of each parameter and variable has to be remembered separately for each function call in the stack so the final result can be put together when the intermediate results percolate back up the stack. For a tail recursive function, those details can be thrown away for all but the last call in the stack. This is (probably) why the recursion limit for tail recursive functions is higher.

                      • 9. Re: Understanding a tail recursive FileMaker Custom Function.
                        NickLightbody

                        Jeremy

                         

                        Thanks for explaining this more fully, I was guilty of trying to simplify Ray's original observation.

                         

                        Cheers, Nick

                        • 10. Re: Understanding a tail recursive FileMaker Custom Function.
                          DrewTenenholz

                          Nick --

                           

                          One way to simplify the function for use would be to designate your function as the 'worker' function and create a new one as the 'master' function: xShuffleMaster (string) = xShuffle ( string ; Length ( string ) )

                           

                          If you don't want to use the length of the string as your controller, you can set up any calculation you like there such as a minimum, maximum, conditional calculation, etc. It just makes the daily use of your function a little easier, I don't think it improves calculation efficiency.

                           

                          -- Drew Tenenholz

                          • 11. Re: Understanding a tail recursive FileMaker Custom Function.
                            destroid

                            @NickLightbody Can you update the link to the fileMaker server performance paper?