Programming Languages, Self-Application, and Computational Complexity

версия со слайдами находится по адресу / edited video with slides exist at jetbrains.ru site : http://jetbrains.ru/students/events/neil-jones-programming-languages/ Programs are often treated as data objects, for example in compilers, interpreters, and text editors. Advanced uses include program transformation and analysis, done by supercompilation, partial evaluation, and abstract interpretation. Pathbreaking work has been done in these areas by researchers from Denmark and Russia. In particular, self-application (running a program on itself) has a number of uses. The basic requirements of computability theory: Turing completeness; the existence of a self-interpreter; and the existence of a program specialiser. Program specialisation can be done by either a partial evaluator or by a supercompiler. The first part of the talk concerns programming language interpretation, compilation, and compiler generation. Program specialisation and self-application provide ways to automatically compile or generate a compiler. These possibilities were first seen in the 1970s in Japan and Russia by Futamura and by Turchin, and first realised in practice in the 1980s in Denmark and in Russia. The second part of the talk concerns some high points in computational complexity: what can be computed by programs that run within limited time or memory (storage) bounds? This leads to well-studied hierarchies of computer-solvable decision problems, started by Hartmans and Stearns in the 1960s. The best-known still unanswered question: “ is P = NP? “ (an answer is worth $1,000,000!) Interestingly, the only general way to prove that more problems can be solved within increased time- or space-bounds is diagonalisation: applying a program to itself in a way very similar to the Futamura projections as used in compiler generation. TOWARDS UNDERSTANDING SUPERLINEAR SPEEDUP BY DISTILLATION Neil D. Jones, DIKU, University of Copenhagen (joint work with Geoff Hamilton, Dublin City University) Distillation is a fully automatic program transformation that can yield superlinear program speedups. It is a further development of supercompilation, initially developed in Russia in the 1970s and in Denmark in the 1990s. Distillation can give superlinear speed-ups on some ``old chestnut’’ programs well-known from the early program transformation literature: naive reverse, factorial sum, Fibonacci, and palindrome detection. The talk describes current work on superlinear program speedups, partly theoretical and partly computer experiments. Further, complexity-theoretic results imply that a large class of exponential-time programs can be converted into second-order polynomial-time equivalents. The idea is to trade time for space, in effect replacing CONS by first-order functions used as arguments in a CONS-free program. An open conjecture is whether distillation or some extension of supercompilation can realise such superlinear speedup transformations in general. Bisimulation is a key to the proof that distillation is correct, i.e., any transformed program has the same semantics as the original. The correctness proof of distillation shows observational equivalence by bisimulation. However, this proof is insensitive to program running times, and does not help to explain how superlinear speedups can occur. A main question: how can a program running in quadratic time be bisimilar to a program running in linear time? This work’s approach is to simplify distillation as much as possible, while maintaining its capacity for superlinear speedups.