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

[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]

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