"Computus" is the calculation of the date of Easter in the Christian
calendar [1]. It is a notoriously dirty problem, arising from the tension
between ecclesiastical and astronomical requirements [2].
Easter has been much studied in the APL community; I won't give a
bibliography but I'll direct your attention to the recent Vector (vol 22.4).
In particular to [2], where Ray Polivka presents a definition of Easter as a
table of sequential equations:
Step Dividend Divisor Quotient Remainder
1. x 19 - a
2. x 100 b c
3. b 4 d e
4. 8b+13 25 g -
5. 19a+b-d-g+15 30 - h
6. a+11h 319 u -
7. c 4 i k
8. 2e+2i-k-h+u+32 7 - q
9. h-u+q+90 25 n -
10. h-u+q+n+19 32 - p
(he got it from an 19th century /Nature/ article, by way of T.H. O'Beirne in
"Puzzles and Paradoxes").
The nice thing about this approach is that it makes the "dirty" problem of
Easter clean, in the sense that there are no exceptions; given x, the year
in question, x,n,p is the date of Easter in that year. No ifs, ands, buts.
Elegant.
Now, of course, if one stares at the Dividend and Divisor columns, the dirty
details reappear. But one needn't do that! Because we're given this data
as a table, we can treat it as an (opaque) input. That is, with a little
effort, we can have an exception-free table-driven definition of Easter.
I say little effort because J has a number of facilities that make defining
such a computus straightforward. In fact, indirect assignment, dynamic
evaluation, and the primitive #: are basically all you need. For example,
using the definition of easter in [3]:
easter 2000
2000 4 23
easter 2000+i.10
2000 4 23
2001 4 15
2002 3 31
2003 4 20
2004 4 11
2005 3 27
2006 4 16
2007 4 8
2008 3 23
2009 4 12
Note that the heart of this definition is merely:
for_entry. B do.
(H) =. entry
(Quotient ; Remainder) =. Divisor (#:~ 0&,)~&". eval Dividend
end.
where H is the header of the table, and B its body. Using indirect
assignment, we're able to define Quotient, Remainder, Divisor, and Dividend
as appropriate for each entry in the table. Dynamic evaluation (".) and
another indirect assignment allows us to define the temporary variables
named in the entry, which will be available for evaluation of subsequent
entries, and for the result of the verb, which is precisely x,n,p .
Coupled with the idiom (0,x) #: y for the quotient & reminder of y wrt x,
and I find this definition simple and elegant. However, there is always
room for improvement:
#1 The current definition of easter requires that that verb be
explicitly applied at rank 0.
#2 For ". y to work, y must be a valid J sentence. For the
divisor, this is ok (the divisor is just a constant
scalar integer). But the dividend is a different story.
So, 1st challenge:
Modify or extend the definition of easter to handle arbitrarily
ranked arrays, natively (i.e. no "0).
Remember, the goal is to keep the definition of easter as transparent
as possible, and let the table COMPUTUS speak for itself.
That means: keep it simple! Try not to let programming (i.e. J)
issues intrude on this simplicity (which is actually a good
argument to keep "0).
In re: #2, the dividend is close to a valid J sentence, but no cigar.
Consider 2e+2i-k-h+u+32 . Here,
#i Multiplication is implied with juxtaposition,
whereas in J, all operations are made explicit, and
#ii order of evaluation is backwards w.r.t. a J sentence.
We can address these issues with a little pre-processor, which I named eval
:
eval =: poly&.>/@:( <mailto:/@:(%3c;.2~> <;.2~ 1: _1}
>/\.@:e.&'0123456789' )&>&r2l&.;:
r2l =. |.&( (<,'-') sr (<'-~') )
poly =. '(' , [ , '*' , ')' ,~ ]
This verb has some neat features:
it operates &.;:
it addresses #ii by reversing (|.) the sentence and commuting (~) the
(non-associative) operations
it addresses #i by leveraging an obscure feature of / .
Specifically, the identity f/y <==> y when 1=#y
(which I've always found interesting, but never put
to use before).
But I'm still not satisfied with it. I think its complexity besmirches the
simplicity of the overall solution (which was its original attraction).
Also, it's not as general as I imagined. Try applying it to the dividends
in the 2nd table presented by Ray Polivka (from O'Beirne).
So, 2nd challenge:
Can you write a better eval ?
I would be particularly impressed with solutions that used the dyad ;: to
lex & parse the dividend (where, in general, the dividend can contain
parens, as in Ray's 2nd table).
-Dan
[1] Wikipedia on Computus:
http://en.wikipedia.org/wiki/Computus
[2] Vector 24.2, "Ten divisions to Easter", Ray Polivka:
http://www.vector.org.uk/?vol=24
<http://www.vector.org.uk/?vol=24&no=2&art=polivka> &no=2&art=polivka
[3] Table-driven exception-free computus:
NB.=======================================================================
NB. Utility: scalar replace.
sr =: conjunction def ' =&m`(,:&n) } '
NB. Easter calculation table, copy/pasted from NB.
http://www.vector.org.uk/?vol=24
<http://www.vector.org.uk/?vol=24&no=2&art=polivka> &no=2&art=polivka
COMPUTUS =: -`dm 1 :'({.m)sr({:m)' }."1 <;._1;._2 noun define -. ' '
Step Dividend Divisor Quotient Remainder
1. x 19 - a
2. x 100 b c
3. b 4 d e
4. 8b+13 25 g -
5. 19a+b-d-g+15 30 - h
6. a+11h 319 u -
7. c 4 i k
8. 2e+2i-k-h+u+32 7 - q
9. h-u+q+90 25 n -
10. h-u+q+n+19 32 - p
)
NB. Make ET executable
easter =: dyad define
'H B' =. ({. ,&< }.) y NB. Header and body of equation table
for_entry. B do.
(H) =. entry
(Quotient ; Remainder) =. Divisor (#:~ 0&,)~&". eval Dividend
end.
x,n,p
)
NB. Divisor evaluation: reverse sentence, commute operations, NB.
parenthesize multiplication
eval =: poly&.>/@:( <mailto:/@:(%3c;.2~> <;.2~ 1: _1}
>/\.@:e.&'0123456789' )&>&r2l&.;:
r2l =. |.&( (<,'-') sr (<'-~') )
poly =. '(' , [ , '*' , ')' ,~ ]
NB. Exported functions
eval =: eval f.
easter =: $:&COMPUTUS : easter"0 _ f.
NB.=======================================================================
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
