No account? Create an account  cananian

Dr. C. Scott Ananian

Echo^n Square Thru A(5)

[Square Dance primer for computer scientists: square dance calls are (recursive) sequences of basic actions: walk forward, turn around, do a square dance call. "U-turn back" is a square dance call, which means simply "turn around". Some calls take numeric arguments: "square thru N" for N=1 means "pull by"; "pull by" is another square dance call which is roughly "step past the person you're facing". For N>1, "square thru N" means "pull by, turn in, mirror square thru (N-1)". The word "mirror" in that definition is a square dance concept. It is a function which takes a square dance call and transforms it, yielding square dance calls or actions. "Mirror" means to simply do the call as if you were looking in a mirror, exchanging right and left. (If you've ever tried to comb your hair looking into the display from a webcam, which is not mirrored the way you expect it to, you know how hard it can be to do well-practiced actions mirror-wise. "Mirror" is a simple square dance concept.) So the definition of square thru N I gave above is recursive, defined in terms of a transformation of the call itself. The concept "twice" takes a call and merely means to repeat the call twice.

Concepts can take multiple arguments, including arguments which are themselves concepts, not just calls. (Some would call these supercalls or meta-concepts, but we'll gloss over this for now.) Which brings us to the subject of today's post: the ECHO concept.]

"ECHO <concept> <call>" means do <concept> <call> then do <call> — like you were hearing the last part of the phrase echoed back from a distance. So, "ECHO mirror square thru 4" means do a "mirror square thru 4" and then a "square thru 4". "Echo twice u-turn back" means u-turn back three times.

Most dancers have a bit of a formal grammar in their heads, something like:

```call: <simple_call> | <concept> <call> | <metaconcept> <concept> <call> ;
simple_call: square thru <number> | u-turn back | pull by | ... ;
concept: mirror | twice | ... ;
metaconcept: echo | ... ;

```
Examples of valid utterances:
"mirror square thru 4", "echo mirror square thru 4", "echo twice u-turn back".
Some invalid utterances:
"square thru 4 mirror", "mirror square", "echo mirror".

Now here comes the fun part: how do you parse the expression "echo echo twice u-turn back"?

It doesn't parse according to the grammar above: you have to mentally curry an argument to make "echo twice" into a concept (since when provided with a concept the remaining part is a 'function taking a call', aka a concept). You end up with something like "echo (echo twice) u-turn back", which would mean, "echo twice u-turn back, u-turn back". Thus, "echo twice u-turn back" means do the u-turn back 3 times; "echo (echo twice) u-turn back" thus means to do the call 4 times, and "echo (echo (echo twice)) u-turn back" is 5 times. Adding another echo adds another u-turn back. Bo-ring.

Because we're adventurous types, let's throw the grammar out the window and treat echo as a simple macro-expander, which grabs the shortest possible phrase following it as its argument. Now we'll parse "echo echo twice u-turn back" as "echo (echo) twice u-turn back", that is, "echo twice u-turn back, twice u-turn back". That's 5 u-turn backs. The next one, "echo echo echo twice u-turn back" becomes "echo (echo) (echo (echo) twice u-turn back)", which is 8. Continuing, "echo (echo) (echo (echo) (echo twice u-turn back))" is 13. Adding more echos yields subsequent terms in the Fibonacci sequence. Now we're talking!

The sequence constructed above grows in duration as an exponential function of the length of the utterance, but we already know of another such construction: the humble "square thru N" also grows exponentially with its input, since the value of its numeric argument "999...9" is also exponential with the number of digits uttered. Let's say that the goal is to allow the square dance caller time to enjoy a nice beverage and sporting event on TV while the dancers work out the implications of a short call. Exponential is okay, but we could certainly do better.

Some readers might be aware of the "baker's function", which naturally involves multiplying everything by 13/12. One might imagine "Baker's Square Thru 6" called using this function as a concept; this is equivalent to "square thru 6 1/2 times". (Computer scientists: define "square thru 1/2" as "do the first half of a pull by" then you can continue using the recursive definition above.)

But, for packing the most dancing into the fewest words — super-exponentially! — I submit "Ackermann's Square Thru 5". (Use f(n)=A(n,n) as computer scientists do.) Guy Steele has suggested that the caller might use "Ackermann's Square Thru Your Couple Number", finish the tip calling for two couples, and then use three-couple figures for the rest of the night. Perfect for the lazy caller who wants to do 25% less.

(Credits: Justin Legakis discovered the Fibonacci connection. Guy Steele had most of the good ideas here. Bill Ackerman is the recipient of the eponymous super-exponential concept. I just wrote it all up.) 