.. include:: crossreferences.asc Detailed Implementation Plan ============================= :DELETE:BEGIN B6.1 :DELETE:END Workplan Introduction ~~~~~~~~~~~~~~~~~~~~~ The PyPy project can be divided into three phases: - Phase 1: The core of PyPy itself must first be developed. - Phase 2: This code base can be used as an research/integration platform of choice. - Phase 3: Specific applications can be implemented and disseminated. Phase 1 is a prerequisite for Phases 2 and 3; Phases 2 and 3 are reasonably independent from each other. Beyond phase-specific tasks, several project-long infrastructure tasks are of paramount importance. In particular, coordination is assured by the project coordinator in workpackage WP01_, with the help of the management and technical boards, as described in section B5. This workpackage involves collecting and monitoring monthly status reports, reporting to the EU, organising sprints, and maintaining an internal web site in collaboration with the maintenance workpackage. :DELETE:BEGIN B6.2 :DELETE:END Research and Technological Aspects and Options ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Phase 1 ------- The first goal is to develop a reasonably complete Python interpreter written in Python. It must be entirely compatible with the language specification. It consists of the following major parts: - A *bytecode compiler,* which inputs Python source code and outputs an internal intermediate representation, the *bytecode.* - A *bytecode interpreter,* which interprets bytecodes and manages the supporting internal structures (frames, exception tracebacks...). It considers objects as black boxes and delegates all individual operations on them to a library of built-in types, the *Object Space.* - An *Object Space,* which captures the semantics of the various types of the language. This subdivision is common among interpreter implementations, although we place special emphasis on the library of built-in types and its separation from the bytecode interpreter. The implementation will closely follow the current reference C implementation (CPython). It is thus expected to be relatively straightforward, varying from CPython only in a few design decisions (mainly with respect to the Object Space separation of concerns), and changing strictly nothing in the Python language itself. This task is done in workpackage WP04_. After the initial development, WP04_ will switch its focus to reimplementing the many extension modules written in C that are either standard or widely-used in CPython. (The Python Standard Library is already mostly written in Python, so that the problem only concerns C-coded extension modules.) For each extension module, two strategies can be followed: either the module is rewritten as a (regular) Python module, or it is written as an extension module of the PyPy interpreter (i.e. in Python too, but at the level of the interpreter.) The result of WP04_ up to this point will still only be able to run on top of another Python implementation, such as CPython. Despite this limitation, it will still present some advantages over the existing CPython implementation, in terms of education (being a much more compact, modular and readable piece of code than CPython) and in terms of flexibility (as a basis into which experimenters can plug in alternate Object Spaces, alternate interpreters, or alternate compilers) -- more about this below. At this point, to make PyPy stand-alone (and running at a reasonable speed), we must ensure that key areas of the source have been restricted to be written in a subset of the Python language, a sublanguage (RPython) in which staticness restrictions are enforced. This sublanguage is suitable for analysis and translation into a lower-level language. The sublanguage's precise definition is a trade-off between the amount of dynamic power desired to write PyPy and the amount of effort we put in the translation tools. Note that translation is not a one-shot process; the only source code for PyPy will be in Python or RPython, and translation can be repeated freely as part of a compilation process. We are giving translation an innovative emphasis (and thus a whole workpackage, WP05_) in the project. It is not only an RPython-to-C translator; it is a source-to-source transformer, and as such an essential part of our flexibility goals. Numerous aspects that used to be design decisions influencing the whole source code of the current CPython have by now become merely customizable behaviour of the translator. Indeed, instead of hard-coding such design decisions, we will keep the PyPy source as simple as possible, and "plug-in" the required knowledge into the translator. For example, the high-level source need not be concerned about memory management issues (garbage collection, reference counting...); this aspect can be "weaved" into the low-level code by the translator. This point is essential for the separation of concerns. Weaving aspects will be done mainly as intermediate stages, for example as transformations on the intermediate representation used by the translator, allowing control over orthogonality issues between aspects. This whole approach has deep advantages over the classic monolithic one, ranging from education (the main source base is not encumbered by details) to raw performance (choice of appropriate low-level models based on real-world context-dependent measures and comparisons). Also note this architecture's extreme adaptability: instead of generating C code, it is straightforward to target other runtime environments like Java or .NET. By contrast, today's costs of maintaining several evolving implementations (CPython, Jython for Java...) are very high. The translation process itself requires some kind of analysis of the RPython code. Among the various ways to perform this analysis we will most probably choose the one based on *abstract interpretation,* as opposed to source-level or bytecode-level analysis: .. image:: translation.png The basic idea is to write an alternative "abstract" Object Space which, instead of actually performing any operation between objects, records these operations and traces the control flow. The "abstract" Object Space will be plugged into the existing bytecode interpreter; these two components, together, will then function as an abstract (or symbolic) interpreter in the usual sense of the word. The net result is that we can actually analyse RPython source code without writing any code specific to the language (!), given that we already have a bytecode interpreter which is flexible enough to accommodate a non-standard Object Space. In other words, the combination of PyPy and an "abstract" Object Space performs as the front-end of the translator, and can be used to translate (for example) the regular PyPy interpreter and its standard Object Space. Note the two different roles played by the bytecode interpreter in the diagram above. Another important advantage of this approach is that, instead of operating on static source code, it works on the result of loading and initializing the code into the existing CPython interpreter. (Python, unlike more static languages, allows arbitrary computations to be performed while loading modules, e.g. initializing caches or selecting components according to external parameters.) We are thus not restricted to RPython at initialization time, which is important in order to achieve the configurability goals. Phase 2 ------- The completion of the first translated stand-alone PyPy interpreter is where the project could potentially branch into a large number of directions. Numerous exciting applications can be foreseen; we will examine some of them in more details in Phase 3. Phase 2 is concerned about research, and integration of research, based on the extreme flexibility afforded by the PyPy platform. Performance +++++++++++ Part of Phase 2 focuses essentially on performance issues, which are important in helping to establish the real-world success of a language implementation, and may open the language to a wide range of applications for which it was previously thought to be unsuitable. The flexibility in PyPy allows a number of design decisions to be easily reconsidered; better yet, it allows different design decisions to coexist. Indeed, most "hard" issues in interpreters have no obvious best solution; they are all depend in complicated ways on the specific details of the runtime environment and on the particular application considered and its possibly evolving context. PyPy will provide a good platform to experiment with, and compare empirically, several different possible approaches for many of these issues. For example: - The language's core object types can have several implementations with different trade-offs. To experiment with this, we will write a collection of alternatives in the "standard" Object Space implementation and heuristics to select between them. This kind of research effort is common, but PyPy can provide a good platform for real-world comparisons, and to help isolate which particular choices have which effects in an otherwise unchanged environment. Such data is notoriously hard to obtain in monolithic interpreters. This is the focus of WP06_. - Similarly, as described above, pervasive design decisions can be experimented with by tailoring the translator. This is the focus of WP07_. We will in particular investigate in detail two specific ways to customize the translator: - Generating Continuation Passing Style (CPS) low-level code. This makes the advanced notion of continuation available for the programmer; but -- most importantly in our case -- it allows the development, with the help of an appropriate runtime system, to support massive parallelism. Indeed, in almost any OS, native threads are not appropriate for massive usage. Applications (e.g. web servers handling thousands of connections) have to somehow emulate parallelism explicitly. Soft-threads are an ideal target for language integration. This work (also part of WP07_) consists of exploiting this idea, which has been first tried for Python in the Stackless project. - Generating a JIT compiler. Existing work in the Psyco project has shown that it would actually be possible to generate the most part of a JIT compiler instead of having to write it from scratch. The basic idea is again abstract interpretation: instead of actually performing any operation between two objects, we *generate* machine code that can perform the required operation. Again, no change to the bytecode interpreter is needed; all we need is to turn individual operation orders into processor instructions, together with a supporting runtime systems. This is defined by WP08_. In dynamic languages, the truth behind JIT compiling is a bit more involved than the above paragraph suggests. All the "standard" operations in Python, including intuitively simple ones, are in fact relatively complex because they depend heavily on the runtime type of the objects involved. This complex code is already written in detail in the "standard" Object Space. Thus the JIT compiler will work by abstract interpretation of RPython code, i.e. abstract interpretation of the interpreter itself (as opposed to user application code). This is similar to the ideas behind the translator, which operates on the RPython source (i.e. the bytecode interpreter and the standard Object Space). We plan to write the dynamic part of the JIT as a plug-in to the translator: instead of generating C code that is the direct translation of PyPy, we will generate C code (with the translator) that itself generates machine code (by directly emitting it as bytes into memory). This extra indirection has large benefits: the operations the JIT need to be manually taught about for the generation of machine code are only the ones allowed in RPython. In other words, we only need to design a JIT supporting the low-level operations of RPython; still, the translated piece of C code that we obtain is a JIT-enabled version of PyPy that supports the whole of the Python language. Other research aspects ++++++++++++++++++++++ The other part of Phase 2 focuses on non-performance-oriented research-level aspects. These are the extensions enabled by the flexible modularization (bytecode compiler, bytecode interpreter, Object Spaces, and translator) enabled in Phase 1. For example, it would be possible to write an interpreter for a completely different language using the same framework, leveraging the translator and thus obtaining an efficient JIT-enabled implementation with little effort. This is actually strongly considered as an implementation strategy for the Prolog language in a current EU-funded project:: We could replace with a reasonable amount of effort the core Python interpreter in PyPy with an experimental Prolog interpreter. This would both prove the versatility of the PyPy platform and give performance results possibly far beyond the state of the art. This is a reasonable assumption because the long history of Prolog is quite focused on static (compile-time) optimizations. --Armin Rigo, for ASAP, Southampton team (Advanced Specialization and Analysis for Pervasive Computing), EU IST FET Programme Project Number IST-2001-38059. In the context of the PyPy project, we will not replace the interpreter altogether, but experiment with extensions: - based on feedback from the Python community, we will experiment with the proposed language extensions that are deemed worthy by the CPython developers. Numerous PEPs (Python Extension Proposals), for example, need an experimental implementation for testing before they can be accepted or rejected for integration into CPython; not only is PyPy a good platform to test them on, but also, playing this sandbox role will ensure PyPy remains synchronised with the development of CPython. (The role of WP03_ is to keep track of the ongoing development of the Python language and its CPython implementation; as a part of this task, we will also look for existing solutions to automate the "passive" part of this effort at least partially.) - WP09_ involves the research and development of techniques inspired from logic programming. An inference engine already exists in the python-logic libraries. Successful integration of these concepts, far from regular imperative programming, would provide a validation of the level of flexibility we achieved in Phase 1. It would also provide an essential starting point for WP10_, described below. Phase 3 ------- The third phase of the project is to implement selected key applications of the flexibility we have enabled so far. Let us stress again that Phase 3 is not meant to run only after Phase 2, but partly in parallel with it. The core flexibility on top of which we will be building is provided by the PyPy interpreter as described in Phase 1. The applications we have selected can be categorized as follows: - Language-level object models; - Language-level extensions; - Interpreter adaptations. Phase 3 is also when we expect third parties to build on top of our platform. Language-level object models ++++++++++++++++++++++++++++ This is the topic of WP12_. We will integrate with the language itself three middleware features: security, transparent distribution, and persistence. **Security** is an important and difficult aspect that requires knowledge and support at a wide number of levels to be effective. Programming languages can help contribute to security at their level. Different object security models are possible: - The language can be artificially restricted, with dangerous operations taken out and thus impossible to achieve by interpreted programs. In effect, this amount to building a carefully stripped-down interpreter. - Access to some objects can be denied to only some (untrusted) parts of the interpreted program; or access can go though proxies performing some kind of access checks. This is a more flexible solution, but it is more difficult to implement efficiently. Explicit checks for each access consume time. In PyPy this could be implemented as an Object Space checking and delegating operations to another Object Space. For comparison, CPython used to implement security-by-absence-of-reference: untrusted parts of a program could supposedly not obtain a reference to a dangerous object. This model, called "RExec", has been recognized as fragile and hard to maintain. It has been removed from CPython. In PyPy, one or both of the alternatives previously described can be practically implemented. **Transparent distribution** of objects over a network is another middleware feature that would benefit from being implemented at the language level. This is a vast subject which has been studied extensively. There are several implementations already available in Python, with varying degrees of transparency. None however can be fully transparent by definition of the language itself, which allows introspection -- a program using introspection features could thus defeat the delicate mechanisms introduced by a network distribution library. Moreover, such libraries typically impose additional constrains, e.g. are only able to move objects over a network if they are of a class inheriting from a particular class. We will study which of these implementations is best suited for being moved into the interpreter itself. These include transparent interfaces to remote objects (like CORBA, Java RMI...), transparent distribution of objects, and transparent distribution of processes themselves. For example, a foreseen solution for the CORBA model would be to design a proxying Object Space that delegates operations to a remote CORBA object server over the network, thus hiding the complexities of the underlying protocols. We will also study approaches enabling transparent distributed execution, i.e. in which the Object Space may decide to move, rather objects or operations, a whole algorithm's bytecode. Such totally-transparent distributed execution would support applications such as fault tolerance (e.g. perform a computation on two machines and compare the results). **Persistence** is related to distribution; it is essentially a way to move objects transparently between the persistent storage and the main memory. This subject has been studied extensively, and there are several implementations already available. We are considering at this point ZODB, the Zope Database engine, and PyPerSyst, which are quite complete. Their respective developers have already expressed high interest in PyPy. Indeed, they would benefit from better language integration; they currently put non-natural constrains on the programmer in terms of what he is allowed to do for persistence to actually work transparently. Typically, it is not possible for a library to detect changes such as adding elements to lists, so that list objects cannot be automatically marked as "dirty" (as needed to ensure they will transparently be saved when necessary). This requires language support, and more specifically an extension or proxy Object Space. Language-level extensions +++++++++++++++++++++++++ WP10_ will base itself on the language extensions developed in WP09_. A major goal of the PyPy project is to enable people to carry out more of their programming tasks in Python without having to resort to other programming languages. We will therefore exploit the optimisations in the PyPy implementation and the constructs for constraints and search to enhance the object model, thus offering in Python what can currently only be found in other object-oriented languages. In particular, we will offer the ability to compose program functionality with aspects and to design object-oriented programs through contracts. Interpreter adaptations +++++++++++++++++++++++ The PyPy interpreter as developed in Phases 1 and 2 will be particularly suitable to be adapted to extremely diverse runtime environments, from embedded devices to number-crunching machines. In WP11_ we propose to study to specific case of embedded devices, which are often limited in processor speed and memory size. This either limits the power of software that is implemented for these platforms, or enforces use of low-level approaches like C/C++ or Java. PyPy is especially suited to support such platforms, since it can produce effective and compact code, while retaining the abstraction and ease-of-use of Python. Based on the specific needs of these devices, we will experiment with memory- or battery-efficient implementations of all the customizable aspects described in Phase 2. The PyPy code generator will need an extra platform specific support module, as well as interfaces to necessary device drivers. It may make sense to develop a PyPy simulator for the target platform. We will use feedback from actual hardware to compare the results obtained. If code space permits we will implement heuristics to switch to the most efficient implementations when these are context- or application-dependent. Integration and Configuration +++++++++++++++++++++++++++++ It is expected that most of the applications described above will still be relatively experimental when the project ends. It is also expected that the extreme flexibility will lead to a potentially large number of different end-user configurations of PyPy. Thus our essential goal, beyond validating our techniques and showing what can be done and how it benefits from integration with the language, is to make this knowledge available and easy-to-use for contributors and third-parties. To fulfill the technical aspect of this goal, we will not only release a range of different versions of PyPy with different trade-offs and including more or less of the features developed in Phase 3, but we will also build a complete toolchain to allow programmers to choose from the available features, various implementations, and runtime restrictions and build a custom PyPy version. This is the objective of WP13_. Documentation and Dissemination ------------------------------- The documentational aspect of the dissemination goal is handled by one of the few workpackages that run for the whole duration of the project. Each sprint, as well as the regular progress of non-sprint development, will produce technical novelties, some of which may afford immediate use and adoption of the novel technologies being developed. We expect all developers and participants to openly report to and discuss with their appropriate communities. Reports and summaries will be posted to the relevant mailing lists as well as archived on both the PyPy and the Python Business Forum website for universal availability. WP14_ is to support this process at all levels. Moreover, WP14_ will produce a joint report about agile methodologies employed by the project. In particular, any "lessons learned" about Sprint Driven development will be analysed in cooperation with all participants, the technical and management board. Python community members will be encouraged to keep current and get involved with the project, while community involvement and feedback on technical developments will affect design and implementation decisions. Feedback and suggestions will be gathered on the website and mailing lists and used by the appropriate project areas to further enhance the project's development efforts, in true Open Source spirit. In addition to supporting the communication process, WP14_ will on occasion present longer, detailed reports to the Commission, and to scientific committees advising the Commission on technical issues. Technical papers and talks will be submitted to scientific conferences which deal with the subject matters covered by the project. When the advancement of the project warrants it, WP14_ will also publish "popularization" articles and tutorial materials to help other practitioners of software development to make practical use of the project's results. Diagrams and schematics will be provided to illustrate fundamental concepts, as appropriate to the audience and the subject matter. Maintenance ----------- PyPy's own development needs an infrastructure that must continuously be kept up-to-date and further developed. The role of WP02_ is decisive in choosing and adopting modern development environments. The main source repository is placed under control of Subversion, a Concurrent Versioning System. This workpackage also includes maintaining and possibly redesigning frameworks for unit-testing -- unit-tests are essential in the development process in sprints. The website makes heavy use of collaborative tools like Wiki pages, a content management system, and issue trackers. Other tasks include: - Subversion maintenance (e.g. notification hooks and pre/post-commit restrictions); - providing access over http/https and ssh server; - building extensions for automatic document extraction; - maintenance or setup of mailing lists; - implementing a search facility over all content; - maintaining or extending the issue tracker; - maintaining and enhancing the website infrastructure; - performing backups for all relevant information/code; - setting up a mirror repository which is kept up-to-date and which can be used read-only in case of failure of the main repository; - taking care of regular repository backups, designing a strict backup policy suitable for the project, and adhering to it. :DELETE:BEGIN B6.3 :DELETE:END Risks in the Project and Steps to Minimise Them ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The success of the whole project depends on the success of Phase 1. When the corresponding milestone is reached -- a complete Python interpreter in Python and a translator for it -- the project will branch. Phase 2 and Phase 3 workpackages are not tightly interconnected. So we will examine project risks with our main focus on Phase 1. Phase 1 ------- The initial design decisions have already been discussed during the young history of the project and its first four sprints, and a basic working prototype has already been written, as a proof of concept. We thus take for granted that the risks associated with the following decisions are almost non-existent at this point: - writing a Python interpreter in Python is not only possible -- it is, in proven fact, markedly faster and easier than in C. - following some of the basic design decisions of CPython (the internals of whom most of us are intimately familiar with) leads to fast development and good results. - pluggable Object Spaces do work. Several proof-of-concept Object Spaces have been successfully tried. - Object Spaces are a remarkably suitable abstraction for abstract/symbolic interpretation. Control flow of simple functions has been derived using an Object Space. Moreover, simple type analysis and generation of low-level code from a low-level representation is common in a variety of contexts, so we don't expect any particular problem from that issue either. As a fall-back solution, we are aware of the more common way to do the translator analysis: if the abstract Object Space should fail to scale as expected, we will revert to classic bytecode-based analysis, adapting tools that are already available for this task. We will, however, pursue the abstract interpretation solution as far as possible, because it leads to more language-independence and particularly to a single place where all knowledge about the details of the actual bytecode needs to be represented. Phase 2 ------- Phase 2 is mainly research-oriented. It is by definition more difficult to predict the involved risks, and fall-back strategies if risks materialize, for this Phase than for the others. However, a risk-mitigating factor is that the performance goals of Phase 2 are backed by the existing and working prototypes Stackless and Psyco, whose authors are among the PyPy members. Further, it is also important to note that the described performance goals, while very interesting and important in order to widen the application area of the language, are not essential to the other applications we have planned. Phase 1 (including translation) already produces a level of performance that can reasonably be expected to be comparable to the existing CPython interpreter. Phase 3 ------- Phase 3 consists of a number of independent applications. Consequently, a failure in one of them would almost certainly not influence the others. Of course, appropriate effort has nevertheless been taken to avoid failure in each of the mentioned applications: all of them are to some extent already existing as middleware libraries, and people fluent in the corresponding domains generally appreciate the advantages a better language integration would bring. The project concludes with an Integration and Configuration workpackage; should one of the previous applications fail, the final configurable tool will still be able to integrate the others. The only risk involved there would involve difficulties (technical or others) to integrate the work done by the various partners. As a fall-back solution we may have to keep some successful but hard to integrate applications out of the mainstream full-featured release or even configuration tool. It is a tendency inherent in open source projects to sometimes fork, in order to explore alternative possibilities, and later, when consensus is reached, merge again. We will try to minimize the corresponding risk (of divergence, i.e., a fork not followed by a later merge), but we also think that it is inherently very low, as long as the different applications are kept as non-overlapping as possible. This risk minimization strategy in application-structuring is already reflected in the work-packages presented for Phase 3.