Ритчи и сложность

[vak]

Хотите глянуть, чем занимался молодой Деннис Ритчи до того, как Кен Томпсон увлёк его игрой в Space Travel на PDP-7?

Статья Альберта Мейера и Денниса Ритчи "The complexity of loop programs" (PDF)

А сама игра вот тут: github.com/mohd-akram/st

Comments

[chaource]

Complexity of loop programs это интересный вопросъ, спасибо за статью, будемъ почитать.

Это вопросъ о томъ, какъ оцѣнить сверху время выполненiя программы. Можно ли статически его оцѣнить, не запуская программу. Скажемъ, если мы какой-то скриптъ скачиваемъ изъ интернета, то мы хотимъ сдѣлать его запускъ безопаснымъ съ точки зрѣнiя времени выполненiя.

То, что тогда называлось "loop programs", можно реализовать съ помощью чистаго типизированнаго лямбда-калькулюса вида System F и выше по лямбда-кубу. Эти системы гарантируютъ, что любая программа (прошедшая провѣрку типовъ на этапѣ компиляцiи) всегда завершаетъ выполненiе. Тамъ можно сдѣлать циклъ, только если количество повторенiй заранѣе извѣстно (а не опредѣляется въ самомъ циклѣ). Можно создавать рекурсивные типы данныхъ (списки, деревья) и обрабатывать ихъ рекурсивными функцiями, но только, если заранѣе (передъ созданiемъ структуры данныхъ и передъ вызовами функцiй) намъ извѣстно, какова будетъ максимальная необходимая глубина рекурсiи. Глубина рекурсiи можетъ быть вычисляемой, но опять-таки лишь съ помощью функцiй того же класса сложности.

Поэтому скрипты, написанные на этихъ языкахъ, могутъ вычислять лишь примитивно рекурсивныя функцiи. Но этого практически достаточно для любыхъ необходимыхъ намъ программъ.

Однако, остается опасность, что скриптъ будетъ вычисляться очень долго или занимать очень много памяти (пытаясь вычислить списокъ всѣхъ чиселъ отъ единицы до 2 въ степени 1000, скажемъ). Поэтому хотѣлось бы умѣть заранѣе статически оцѣнивать время выполненiя. И необходимую память тоже, т.е. максимальные размѣры всѣхъ промежуточныхъ результатовъ, вычисленныхъ программой.

---update:
Но, кажется, статья не даетъ никакихъ практически полезныхъ отвѣтовъ на эти вопросы. Чистая теорiя и никакого мошенничества.

[vak]

Сама постановка задачи мне всегда казалась надуманной. Если время работы программы не зависит от входных данных, то это сферический конь в вакууме. А если зависит, то о каком анализе можно говорить.

[chaource]

Время работы надо оцѣнивать какъ функцiю входныхъ данныхъ. А если входныхъ данныхъ нѣтъ, то тѣмъ лучше (значитъ, тамъ все прописано въ видѣ константъ).

Если данъ замкнутый лямбда-термъ, можно ли оцѣнить количество шаговъ редукцiи и размѣръ конечнаго значенiя?

Этотъ вопросъ эквивалентенъ поставленному въ статьѣ. Тамъ сказано, что каждый регистръ поддерживаетъ работу съ цѣлыми числами неограниченной величины. Если loop program имѣетъ входной регистръ Х и выходной регистръ F, то можно ли оцѣнить количество шаговъ и величину F какъ функцiи Х?

[vak]

Рассуждения мудрёные, но какая от них польза? К примеру, возьмём простой парсер, скажем стандартную функцию strtol(), превращающую строку в число. Что полезного теория сложности может мне про этот парсер сказать? Завершается ли он? Какая оценка времени выполнения?

[chaource]

Вотъ хотѣлось бы имѣть алгоритмъ, который бы умѣлъ это оцѣнивать болѣе разумно, чѣмъ въ этой статьѣ.

Если переписать strtol() какъ "loop program", а это, кажется, можно - закодировать строку хотя бы какъ ASCII однимъ большимъ цѣлымъ числомъ, - то strtol() будетъ эквивалентна какой-то loop program, и соотвѣтственно какому-то замкнутому типизированному лямбда-терму въ System F. И это уже хорошо бы попытаться какъ-то оцѣнить, хотя бы количество шаговъ редукцiи.

Есть на эту тему изслѣдованiя, - найденъ классъ рекурсивныхъ программъ (кажется, нѣсколько болѣе широкiй классъ, чѣмъ "loop programs"), для которыхъ можно синтаксически гарантировать завершенiе рекурсiи. https://en.wikipedia.org/wiki/Walther_recursion