XP is just a number PerlMonks

### Re: The (Larry) Wall Series

by Prof Vince (Friar)
 on Nov 09, 2007 at 08:11 UTC ( #649869=note: print w/replies, xml ) Need Help??

in reply to The (Larry) Wall Series

You'll note this is similar to, but not quite, the Fibonacci series. It's a series known to mathematicians, but does not seem to have a name, so I'm taking the liberty of calling it the Wall Series.
Do not mistake numerology for maths. If we had to start giving a name to every single sequence, we'd run out of names very quickly.

This sequence "looks like" Fibonacci's because it should be solution of a similar linear recurrence equation.

Replies are listed 'Best First'.
Re^2: The (Larry) Wall Series
by Jeffrey Kegler (Hermit) on Nov 09, 2007 at 12:43 UTC
The recurrence equation is a(n) = 2*a(n-2) + a(n-3) + 1. It's in the literature as A052952. I take "numerology" to suggest a pseudo-relationship based on conjecture from a small sample. That is, the first few numbers may match a series, but how do I know later numbers will actually match the series? I'll present a proof below that the parse counts generated from the Minus Sign Grammar are precisely A052952, and I hope that will take us out of the realm of numerology.

First, a comment on why this is useful and/or interesting. Many monks will have heard of the Ackermann function. I don't know of any direct applications for it, but it gets a lot of use in testing because 1) it's an extreme example of a kind of computation that is practical; and 2) it focuses on a functionality that is useful.

In investigating parsing of ambiguous grammars, I wanted an extreme example of the kind of grammar likely to be encountered in practice. "In practice" and "Perl" aren't quite synonyms, but they're close. My problem with Perl grammar was that it's (of course) unambiguous. So I eliminated all notions of precedence. Also, I did away with lvalue restrictions. That is, I legalized 6++, treating it as roughly equivalent to (\$tmpNN=6)++.

Honing in on the part of Perl most likely to generate lots of ambiguity, I focused on expressions with a number at each end and minus signs between them. Four operators are composed entirely of minus signs: pre-decrement, post-decrement, arithmetic negation and subtraction. The resulting grammar is

E ::= Number | E-- | --E | -E | E-E

In testing an ambigious parser, you want to be sure it gets all the parses. Counting by hand gets you only so far. Call the parse count for a string with n minus signs, W(n). At n=5, W(n)=8 and the counting is already quite difficult to do in your head:

W(10)=144, W(20)=17711 and W(36)=39088169 so even for small n, we're in territory where hand counts just ain't gonna happen. Hence the importance of identifying the W(n) series with a mathematical series. I can simply count the parses generated by my algorithm and look up the appropriate number in the series to see if they match.

Yes, you say, all very nice, but since you only hand checked up to 5, isn't this numerology? What reason is there to believe that the number of parses generated, W(n), actually matches A052952?

A proof follows. Those who think they might have any taste for this sort of thing might want to at least attempt to follow it, since it's not what the mathematicians call "technical" and is presented in Perlish terms.

Create A New User
Node Status?
node history
Node Type: note [id://649869]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (3)
As of 2018-05-25 22:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (191 votes). Check out past polls.

Notices?