Пас­ха­лия в sed.

Содер­жа­ние:

• Вве­де­ние
• Опи­са­ние вспо­мо­га­тель­ного языка
• Расчёт даты
• Тести­ро­ва­ние
• Воз­мож­ные улуч­ше­ния
• Ссылки

Вве­де­ние

Во время поста перед Пас­хой решил напи­сать сце­на­рий (скрипт) computus.sed [1] для хорошо извест­ного поточ­ного тек­сто­вого реда­тора sed, расчи­ты­ва­ю­щий дату празд­но­ва­ния (в дан­ном слу­чае пра­во­слав­ной) Пасхи.

При­мер исполь­зо­ва­ния скрипта computus.sed:

echo 2020 | ./computus.sed
# April, 19

Исход­ное опре­де­ле­ние даты праз­до­ва­ния Пасхи выгля­дит не очень сложно [2,3]. Согласно ему, день празд­но­ва­ния Пасхи при­хо­дится на пер­вое вос­кре­се­ние после пер­вого пол­но­лу­ния, насту­пив­шего не ранее весен­него рав­но­ден­ствия. Про­грамм­ный расчёт этой даты под­ра­зу­ме­вает моде­ли­ро­ва­ние дви­же­ния земли и луны, либо, что проще для реа­ли­за­ции, аппрок­си­ма­цию полу-эмпирическими фор­му­лами.

Про­блема только услож­ня­ется тем, что эта дата — т.н. аст­ро­но­ми­че­ская Пасха — из-за при­ня­того в церкви алго­ритма рас­чета ука­зан­ных аст­ро­но­ми­че­ских собы­тий (пол­но­лу­ние, рав­но­ден­ствие), вити­е­ва­той исто­рии кален­дар­ных реформ и ряда допол­ни­тель­ных спе­ци­аль­ных соглашений/оговорок, сильно отли­ча­ется от фак­ти­че­ских дат (тоже сильно раз­ли­ча­ю­щихся между собой) празд­но­ва­ния Пасхи в раз­лич­ных церквях/религиях.

Это обсто­я­тель­ство вме­сте с [почти] пол­ным отсут­ствием под­держки ариф­ме­тики в sed сде­лало напи­са­ние этого скрипта несколько нетри­ви­аль­ной зада­чей (хотя пери­о­дич­ность резуль­та­тов пас­ха­лии, а именно повто­ре­ние дат с пери­о­дом в 532 года, в прин­ципе поз­во­ляет обой­тись и радуж­ными таб­ли­цами, что не так инте­ресно).

Поэтому сна­чала был напи­сан про­стой интер­пре­та­тор для пост­фикс­ного (обрат­ная поль­ская нота­ция, далее кратко rpn) языка, исполь­зу­ю­щего стек/«магазин» (но под­дер­жи­ва­ю­щего име­но­ван­ные пере­мен­ные).

Опи­са­ние вспо­мо­га­тель­ного языка

Весь rpn-скрипт состоит из после­до­ва­тель­но­сти «слов», раз­де­лен­ных про­бе­лами. Слова могут быть чис­лами или коман­дами. Слова пере­чис­ля­ются и обра­ба­ты­ва­ются (выпол­ня­ются) «слева-направо» (т.е. с пер­вого до послед­него).

Целое поло­жи­тель­ное число в деся­тич­ной записи пре­об­ра­зу­ется в унар­ную запись и кла­дётся на вер­шину стека.

Команды:

• Срав­не­ние: eq. Уда­ляет из стека два верх­них эле­мента, срав­ни­вает их и кла­дет на вер­шину стека еди­ницу если аргу­менты равны, и ноль – в про­тив­ном слу­чае.
• Работа с пере­мен­ными: set, get. Син­так­сис: set_<variable> и get_<variable>, где <variable> – имя изме­ня­е­мой или, соот­вет­ственно, чита­е­мой пере­мен­ной (без угло­вых ско­бок). При записи, с вер­шины стека уда­ля­ется зна­че­ние и запи­сы­ва­ется в ука­зан­ную име­но­ван­ную пере­мен­ную. При чте­нии зна­че­ние из пере­мен­ной добав­ля­ется на стек.
• Адди­тив­ные ариф­ме­ти­че­ские опе­ра­ции: plus, minus. Эти опе­ра­ции уда­ляют два значения-аргументы со стека, скла­ды­вают или нахо­дят их раз­ность (при­чем вычи­тать можно только из боль­шего мень­шее), а резуль­тат кла­дут на стек.
• Муль­ти­пли­ка­тив­ные опе­ра­ции: div, mod. Эти опе­ра­ции тоже берут со стека два зна­че­ния и кла­дут резуль­тат обратно на вер­шину. Опе­ра­ция div про­из­во­дит цело­чис­лен­ное деле­ние, mod – нахо­дит оста­ток от деле­ния.
• Услов­ный опе­ра­тор: if ... then. При выпол­не­нии команды if про­ве­ря­ется вер­шина стека и если на вер­шине лежит ноль, то блок между if и бли­жай­шим, рас­по­ло­жен­ным пра­вее, сло­вом then про­пус­ка­ется, иначе блок выпол­ня­ется (N.B., вло­жен­ность не под­дер­жи­ва­ется).

На дан­ный момент все ариф­ме­ти­че­ские опе­ра­ции про­из­во­дятся в унар­ной системе счис­ле­ния. К при­меру, для про­верки висо­кос­но­сти 2020 года тре­бу­ется среди про­чего найти оста­ток от деле­ния на 4, а для этого тре­бу­ется запи­сать 2020 еди­ниц в буфер редак­ти­ро­ва­ния и начать после­до­ва­тельно уда­лять по 4 еди­ницы за раз, пока не оста­нется менее четы­рех еди­ниц, что и будет тре­бу­е­мым остат­ком. Да, это очень мед­ленно, но обес­пе­чи­вает осо­бую про­стоту кода.

Ана­ло­гично, деле­ние опи­сы­ва­ется сле­ду­ю­щим псев­до­ко­дом:

swap_stack();
a=pop_stack();
b=pop_stack();
c=0;
while(a>b)
{
    a-=b;
    c++
}
push_stack(c);

Эта логика в computus.sed реа­ли­зу­ется сле­ду­ю­щим фраг­мен­том (обра­тите вни­ма­ние, что неко­то­рые строки про­ком­мен­ти­ро­ваны соот­вет­ству­ю­щими стро­ками из выше­при­ве­ден­ного псев­до­кода):

/^div/ {
    s/\n(1*)\n(1*)@/\n\2\n\1@/ # swap_stack();
    s/@/\n@/ # c=0;
    :div_iterations
        /\n(1*)\n1*\1\n/! bnot_matched
        s/\n(1*)(\n1*)\1(\n1*@)/\n\1\2\3/ # a-=b.
        s/\n(1*)@/\n1\1@/ # c++.
        bdiv_iterations
    :not_matched
    s/\n1*\n1*(\n1*@)/\1/
}

В основе этого фраг­мента лежит соот­вет­ству­ю­щая строке a-=b sed-инструкция s/\n(1*)(\n1*)\1(\n1*@)/\n\1\2\3/. Здесь работа ведется с двумя унар­ными чис­лами, раз­де­лен­ными пере­во­дом строки (\n). Мы ищем (с помо­щью обрат­ной ссылки или «back-reference») пер­вое число «внут­ри» [записи] вто­рого: (1*)(\n1*)\1, и при удач­ном сопо­став­ле­нии заме­няем сов­пав­ший шаб­лон на строку \1\2, вклю­ча­ю­щую ссылки на пер­вые две группы в круг­лых скоб­ках из шаб­лона, — т.е. (1*) и (\n1*), — и игно­ри­ру­ю­щую «хво­сто­вую» часть вто­рого числа, нахо­дя­щу­юся, как вы можете видеть, за пре­де­лами ско­бок: (\n1*)\1.

Эта про­це­дура, по-сути, уда­ляет пер­вое число из вто­рого, т.е., говоря дру­гими сло­вами, вычи­тает пер­вое число из вто­рого, чем, соб­ственно, и дости­га­ется тре­бу­е­мый эффект от опе­ра­ции a-=b (да, поря­док сле­до­ва­ния «пе­ре­пу­тан» из-за сте­ка; за это отве­чает строка swap_stack() из псед­во­кода, меня­ю­щая два числа на вер­шине стека местами).

В подроб­ном раз­боре всего кода, есте­ственно, нет осо­бого смысла — ничто не заме­нит чте­ния самого computus.sed.

Расчёт даты

В [2] при­ве­ден сле­ду­ю­щий алго­ритм для рас­чета даты пра­во­слав­ной Пасхи (здесь добав­лена частич­ная кор­рек­ция даты для под­держки гри­го­ри­ан­ского кален­даря или т.н. нового стиля):

,

Для полу­че­ния дат по гри­го­ри­ан­скому кален­дарю я про­сто доба­вил сла­га­е­мое 13 в при­сва­и­ва­ние . Т.е. в таком виде этот код не будет пра­вильно рабо­тать для дат до 1 фев­раля 1918 года. Тео­ре­ти­че­ски, это не сложно испра­вить (однако, см. заме­ча­ние ниже, в раз­деле «Те­сти­ро­ва­ние»).

Дослов­ная транс­ля­ция выше­при­ве­ден­ных фор­мул на уже опи­сан­ный в преды­ду­щем раз­деле проблемно-ориентированный мини­я­зык может быть такой:

set_year get_year 4 mod set_a
get_year 7 mod set_b
get_year 19 mod set_c
19 get_c mul 15 plus 30 mod set_b
2 get_a mul 4 get_b mul plus 34 plus get_d minus 7 mod set_e
get_d get_e plus 114 plus 13 plus set_t
get_t 31 div set_mont
get_t 31 mod 1 plus set_day

Несмотря на учёт пере­хода на «но­вый стиль», здесь всё ещё оста­ется про­блема с датой Пасхи, при­хо­дя­щейся на май (исход­ные фор­мулы вообще не могут давать май­ских дней). Ad-hoc кор­рек­ция для таких дат может выгля­деть сле­ду­ю­щим обра­зом:

get_month 5 eq if get_day 1 plus set_day then
get_mont 4 eq if get_day 31 eq if
5 set_month 1 set_day then then

Это соот­вет­ствует такому C-образному псев­до­коду:

if(month==5)
    day++
else if(month==4)
    if(day==31)
    {
        month=5
        day=1
    }

В конце rpn-скрипта мы про­сто кла­дем гото­вые месяц и день на стек для даль­ней­шей печати (с пре­об­ра­зо­ва­нием номера месяца в строку): get_month get_day

Тести­ро­ва­ние

В репо­зи­то­рии можно найти файл-список test-easter-dates.txt с неко­то­рыми про­ве­роч­ными датами и скрипт dictionary-test.sh для авто­ма­ти­че­ского тести­ро­ва­ния с их исполь­зо­ва­нием. Спешу лишь пре­ду­пре­дить о доста­точно боль­шом вре­мени, тре­бу­е­мом для завер­ше­ния работы скрипта даже для отно­си­тельно неболь­шого диа­па­зона дат, вклю­чен­ных в ука­зан­ный файл (1994–2034 гг.)

Кроме этого был напи­сан на perl про­стой скрипт-обёртка computus.pl, при­ни­ма­ю­щий год в каче­стве аргу­мента команд­ной строки, расчи­ты­ва­ю­щий дату празд­но­ва­ния Пасхи с помо­щью модуля Dates::Easter [4] и воз­вра­ща­ю­щий её в том же фор­мате, что и computus.sed. Он может исполь­зо­ваться для срав­ни­тель­ного тести­ро­ва­ния моего скрипта, а с целью упро­ще­ния этой про­це­дуры для диа­па­зо­нов дат, можно вос­поль­зо­ваться сце­на­рием обо­лочки range-test.sh.

При­мер:

./computus.pl 2020
# April, 19
./range-test.sh 2018 2021
# 4 tests performed, 4 tests passed, 0 tests failed.

Для меня пока остаётся откры­тым вопрос о рабо­то­спо­соб­но­сти скрипта computus.sed для всего XXI века, а так­же для дат, пред­ше­ство­вав­ших реформе 1918 года, вплоть до вре­мен раз­ра­ботки и начала при­ме­не­ния пас­ха­лии (хотя кон­кретно этот алго­ритм, по-видимому, не будет рабо­тать для вре­мени более ран­него чем 1583 год, что свя­зано с вве­де­нием гри­го­ри­ан­ского кален­даря именно в 1582 году; это тре­бует уточ­не­ния). К слову, computus.pl согла­су­ется с моим для теку­щего века, но рас­хо­дится с моим на один день для века XIX, что, воз­можно, свя­зано с вопро­сом о новом стиле, хотя в начала XX века, скрипты дают оди­на­ко­вые даты, а это уже сви­де­тель­ствует о нали­чии в perl-модуле Dates::Easter той же или похо­жей недо­ра­ботки, что и в моём слу­чае.

Вообще, в кален­дар­ных рас­че­тах должно учи­ты­ваться (и, по всей види­мо­сти, в Dates::Easter это учи­ты­ва­ется), что раз­ница между юли­ан­ским и гри­го­ри­ан­ским кален­да­рями зави­сит от кон­крет­ного века (и уве­ли­чи­ва­ется на 3 за 4 века). Эту зави­си­мость можно про­ил­лю­стри­ро­вать сле­ду­ю­щей таблицей-примером:

Так­же должна учи­ты­ваться и кон­крет­ная дата внутри века, при­чем не самым систе­ма­тич­ным обра­зом. E.g., кор­рек­ция в 10 дней дей­ствует с 5 октября 1582 года по 28 фев­раля 1700 года, а кор­рек­ция в 11 дней — с 1 марта 1700 года по 28 фев­раля 1800 года. (При этом, я слы­шал, что пра­во­слав­ная цер­ковь про­сто исполь­зует фик­си­ро­ван­ную раз­ницу в 13 дней все­гда; это утвер­жде­ние тре­бует допол­ни­тель­ной про­верки)

В любом слу­чае, несмотря на то, что Dates::Easter соблю­дает веко­вое варьи­ро­ва­ние раз­ницы между кален­да­рями, мой скрипт, или по край­ней мере его теку­щая вер­сия, исполь­зует именно фик­си­ро­ван­ную поправку +13, впро­чем, исклю­чи­тельно ради про­стоты реа­ли­за­ции. Посмот­рим, что будет в XXII веке с его четыр­на­дца­ти­днев­ной кор­рек­цией. :)

Воз­мож­ные улуч­ше­ния

За счёт исполь­зо­ва­ния сте­ко­вого dsl-языка пред­став­ля­ется отно­си­тельно неслож­ной задача адап­та­ции насто­я­щего скрипта к дру­гим вари­ан­там Пасхи, вклю­чая като­ли­че­скую и еврей­скую. Под­держку аст­ро­но­ми­че­ской Пасхи пря­мым моде­ли­ро­ва­нием пла­не­тар­ного дви­же­ния на sed реа­ли­зо­вать слож­нее, но можно подо­брать, как уже было отме­чено, при­бли­жен­ные фор­мулы. Напри­мер, что несколько неожи­данно, ядро рас­чета еврей­ской Пасхи, кажется, доста­точно точно соот­вет­ствует аст­ро­но­ми­че­ской дате (это, однако, ниве­ли­ру­ется по мень­шей мере согла­ше­ни­ями о невоз­мож­но­сти её празд­но­ва­ния в опре­де­лен­ные дни недели).

Дру­гим оче­вид­ным (но не при­о­ри­тет­ным) направ­ле­нием для улуч­ше­ния обсуж­да­е­мого sed-сценария явля­ется уско­ре­ние его работы, напри­мер пере­хо­дом к деся­тич­ной или хотя-бы дво­ич­ной системе счис­ле­ния. В пост­фикс­ном каль­ку­ля­торе dc.sed [5], напи­сан­ном Greg Ubben, почти вся необ­хо­ди­мая ариф­ме­тика уже реа­ли­зо­вана (и рабо­тает с огром­ной ско­ро­стью, в отли­чии от моей унар­ной реа­ли­за­ции «счёт­ных пало­чек»).

Нако­нец, было бы неплохо испра­вить опи­сан­ные в преды­ду­щих раз­де­лах ошибки с расчётом дат Пасхи в веке XIX и далее в глубь веков. В про­ти­во­по­лож­ном направ­ле­нии по оси вре­мени тоже есть опре­де­лен­ные тон­ко­сти, вроде необ­хо­ди­мо­сти учёта раз­ницы между юли­ан­ским и новоюли­ан­ским кален­да­рями после 2800 года. Допол­ни­тель­ный раз­бор пас­ха­лии и кален­дар­ных несо­от­вет­ствий может быть най­ден в [6].

Ссылки

• 1. https://github.com/Circiter/computus-in-sed
• 2. Meeus J. Astronomical Algorithms. 1991
• 3. http://ru.wikipedia.org/wiki/пасхалия
• 4. http://search.cpan.org/dist/Date-Easter
• 5. http://sed.sourceforge.net/grabbag/scripts/dc.sed
• 6. Кален­дар­ный вопрос: Сбор­ник ста­тей / под ред. Чхар­ти­швили А. 2000