Digging around in the documentation for the Regina (a GPL licensed REXX interpreter), I ran across reference to two functions described as part of the ANSI standard for REXX that I could find no documentation for on my Warp system or in the late Dick Goran's classic 'REXX Reference Summary Handbook' (ISBN 0-9639854-3-4). Browsing the REXX Language Association web site, I found a PDF draft of the standard that backed up the description in the Regina documentation. CountStr counts all non-overlapping instances of a substring (the "needle") in a larger string of characters (the "haystack"). For instance,

Similarly, ChangeStr changes those non-overlapping substrings to a target string:

A few questions on mailing lists and browsing Object REXX books turned up that these functions had been implemented as methods in Object REXX and some suggestions that they might be implemented with various REXX standard library functions such as Pos etc. This seemed like a good project to chew over some and see what I could come up with. The mention of the standard library function Pos seemed to miss the mark to me. It implied using numbers (and not particularly large ones at that), to keep track of location in the 'haystack' string. This was therefore going straight to probably the weakest point in REXX, speed of handling modestly sized numbers.

One of the intellectual highlights of my life was at the 2000 11th Annual International REXX Symposium, sitting beside REXX creator Mike Cowlishaw, hearing his comments while REXX L.A. president Chip Davis gave his presentation on the Parse command. My goal was simply to listen and absorb as much as possible. The most important point of Davis's talk was that Parse should be used as much as possible. A little bit of fumbling around turned up this possible implementation of CountStr:

This was good, since it didn't use any other function calls, with plenty usage of Parse, and the recursion (a function calling itself) gives a nice textbook exercise quality to it. Successful use of recursion always seems to produce a feeling of being levitated after using it, because of the mystique it has been imbued with, but it really shouldn't. (I even got inspired to re-read Douglas Hofstadter's "Goedel, Escher, Bach: An Eternal Golden Braid", which sparked the literary genre of 'Computer Aided Scholasticism.')

Recursion works on many problems because it goes straight to the heart of the engineering method of solving problems: simplifying things until you get a problem you can solve, and then step-by-step dealing with the reintroduction of complications 'til you return to the problem you originally were trying to solve. I remember reading about this in the introduction to a friends copy of Charles Proteus Steinmetz's historically important books on electrical engineering. Obviously then, some idea along these lines predates the conscious concept of modern 'computer science.'

The distinguishing point in programming is that recursion can be used to either simplify the problem data, as above (each recursive call to ChangeStr is guaranteed to have one fewer case of the needle string), or in the classic Quick Sort algorithm, simplifying the algorithm itself. (Rather than trying to do a complete, comprehensive sort of the data in one subroutine, can you sort it into two piles of data that can then be recursively sorted further until the desired result pops out?) All of this is almost a direct embodiment of the concept. Fortunately, the data structures usually dealt with in Computer Science are usually not continuous, or the act of a function calling itself in the hope of simplifying things would be tantamount to driving off a cliff. The number of points in a half-inch line seems to be the same as the number of points in a one-inch line, and trying to simplify dealing with each of the points in a line by dealing with a shorter segment of a line is, as far as we know, futile. You may see reference to 'partially recursive' functions, which go through the motion of calling themselves, but make no testable simplification of the problem with each call, and may not be guaranteed of solving the problem.

While conceptually elegant, recursion can frequently be more efficiently done if the solution can be restated as an iterative loop of some kind. Besides getting rid of function call overhead, some more subtle advantages are that simple iteration avoids the drag of having to process any switches with every recursive call, or using a wrapper function to handle the switches, (still incurring another function call). Nonetheless, the fact that the problem could be done recursively provided some hope for a simple iterative solution with few function calls, and after some more fumbling around this came up:

As the comments indicate, problems cropped up with the case of needle being exactly at the end of haystack, a last pass through the loop necessary for a correct count would be missed. Just putting any special string at the end of haystack to indicate to start special treatment because you are at the end of the haystack string opened up a can worms of possible problem cases.

A simple solution to this was to put a bogus extra case of needle on the end, which never gets counted as the DO loop comes to the problem case. In effect, this directly confronts the problem under control, and contrived circumstances, rather than waiting for it to come up with the random use of the function. One thing I think about this solution is that, to me anyway, it seems simpler than even the recursive version - it doesn't have the lines of code consumed with the SELECT statement. The DO loop compactly handles counting, all the logic of when to stop as well as the iteration for each needle string.

While going through all this, parallel development went on using the algorithms for ChangeStr and with adding all sorts of features not in the standard. Things got as far as submission to the editor for this web page, and was bounced back for correcting a confusing typo. Checking it over, something didn't seem quit right, and looking at the regression tests, a problem cropped up.

What happens if the haystack string ends, in say '.....ba', and the needle is 'aa'? Or generalizing a bit, needle is 'baba'? After I thought about this a bit, I realized that the needle string could be in a periodic string built up from smaller substrings. So with a trailing substring (I'll call it a 'cell'), the haystack ends in cell fragment of the needle, and a false finding of the needle would show up. The false needle straddles the true end of the haystack. I finaly recognized these repetative (perhaps even recursive?) strings as character sequences produced by the 'quinning' process discused in Hofstadter's book, named after American philosopher/logician/cryptologyst Willard van Orman Quine, who first brought attention to them. In this case there didn't seem to be any semantic (meaning) importance as in 'Godel, Escher, Bach:...', just an annoying problem in my attempt to count substrings. (This problem does have some vague resemblence to crystal dissolution/solidification processes, where the border between haystack/needle becomes indistinct.)

Somewhat discouraging to find a problem at this point, the flip side was that finding such a bizarre problem suggests that it was being analyzed carefully. After all, with prior knowledge of the input data under some circumstances, the simpler initial methods might work fine for some uses.

Attempts to solve this problem by some kind of strict comparison of the haystack to needle, trying to stop when the haystack is finally 'strictly' less than needles seemed hopeful at first, (DO I = 0 UNTIL haystack << needle ) but was found to be a false hope because the peculiarities of how strict comparison was carried out. It depends too much on the characters in the strings and not enough on the lengths of the strings. Another approach that worked solidly, but made too many function calls for my taste was:

After a nights sleep on this, I decided to bite the bullet, and allow one function call but avoid having one on each DO loop iteration. This is done by testing if a needle was on the end of the haystack, and only then appending a needle to avoid the missed needle syndrome:

With this version, I threw out all previous functions for ChangeStr() etc., and rewrote them to simply count the number of needle strings in haystack, and use this information as the basis of decisions on the handling of input switch information and parse results.

A finally satisfactory version

After considerable further thought, the following version was dreamed up:

It brings out a few points that should be made.

• While the Parse command doesn't provide any kind of return code to indicate what happened, you can always save the original string being parsed, and all the parts it is broken up into, to determine what happened. This will generally mean not throwing anything away in '.', the placeholder dummy variable.

• By using '=1' to 'rewind' the parse process to the start of the string, to make another pass over it, making multiple assignments, you can save the original string without having to add another statement.

• One thing reusable in converting some code from recursion to interation is the test for completion. It's got to be there, in some form, and sticking with it you keep close to the original algorithm. The recursion may hide the need for some variables (which are stored on the stack or whatever in the chain of function calls), but this is simply something to keep alert to.

Of course, besides making it work right and reasonably efficiently, the other goal was to add as many bells and whistles as possible! Typically these include:

• Ignoring case
• For ChangeStr:
  Only doing a limited count of changes
  Counting the number of changes from the end (Perl/Python style)
  Only changing one instance of needle inside haystack
  Making changes within a range on old-needle instances
  etc.

These functions are obviously useful for writing filter programs and such, so to me seemed worthwhile spending time on. Especially when adding all the extra features. There are probably better ways to do a lot of this and I'm certain some people will think they should be written in C and compiled. That's fine. Meanwhile, here's a file of several prototypes for you to work from!

Copyright 2002 the Southern California OS/2 User Group. ALL RIGHTS RESERVED.

SCOUG, Warp Expo West, and Warpfest are trademarks of the Southern California OS/2 User Group. OS/2, Workplace Shell, and IBM are registered trademarks of International Business Machines Corporation. All other trademarks remain the property of their respective owners.