Index

This file was automatically generated from http://svn.pugscode.org/pugs/v6/docs/kp6-roadmap.pod on Thu Nov 29 23:08:16 2007 GMT, revision 18984.

kp6-roadmap


NAME

kp6-roadmap - The "KindaPerl6" Project Roadmap

DESCRIPTION

This document describes the current status and roadmap of the "KindaPerl6" project.

The document "POD" source can be found at: http://svn.pugscode.org/pugs/v6/docs/kp6-roadmap.pod

The html version is at: http://moritz.faui2k3.org/pugs/v6/docs/kp6-roadmap.pod.html

OBJECTIVE

KindaPerl6 ("kp6") aims for a "Perl 6 in Perl 6" compiler design and implementation.

KindaPerl6 Project overview

Phase 7 - aggressive optimizer

  Target speed is 1/20x Perl 5

Phase 6 - optimizer

  Target speed is 1/200x Perl 5

Phase 5 - improved grammar

  Upgrade to Perl-6.0.0-STD Grammar

Phase 4 - improved runtime

  The runtime libraries needed by the Perl-6.0.0-STD parser will be specified and implemented
  This is the current phase

Phase 3 - regex compiler refactoring

  This phase is finished

Phase 2 - improved compiler architecture

  This phase is finished

Phase 1 - bootstrap

  This phase is finished


Phase 6 - optimizer

Phase 7 - aggressive optimizer

Phase 5 - improved grammar

The goal for this phase is to upgrade kp6 to Perl-6.0.0-STD Grammar

Milestone 5.1 - Upgrade the regex engine to the current specification

The regex engine in KindaPerl6 will be refactored. The regex engine was implemented a while ago, and the regex language specification has changed since then.

Status

KindaPerl6 can now do proper parameter passing. It is now possible to implement parameters in regexes.

Dependencies

* Improved parameter handling
* Status: near finished
* Improved "perl5rx" backend
* Status: passes all tests

Tasks

* Upgrade the grammar engine in MiniPerl6 to the regex new syntax

* we need MiniPerl6 in order to compile KindaPerl6

* Status: finished; replaced all occurrences of <? > with <. >

* Upgrade the KindaPerl6 grammar source code to the new regex syntax
* Status: replaced all occurrences of <? > with <. >
* Upgrade the KindaPerl6 regex engine to the new regex syntax
* Status: <. > works.
* Add "perl5rx" support to Makefile

* Status:

Added "scripts/run_tests_kp6_mp6_perl5rx.pl"

KindaPerl6 can compile itself, invoking the makefile with "KP6_TARGET=KP6-BOOT Makefile.PL"

Test Plan

The resulting code will be tested by running the existing test suite.

* Status:

All t/kp6/grammar/ tests pass under the "perl5rx" backend.

Some grammar tests fail under the "perl5" backend, which uses the portable regex engine.

Milestone 5.2 - Working bootstrapped grammar

The KindaPerl6 image generated by compiling KindaPerl6 with itself will be able to parse small programs.

Status

KindaPerl6 can compile itself under the "perl5rx" backend.

The generated code can parse ' 1 '.

Dependencies

* ...
* Status: ...

Tasks

* Refactor emitted regex code

* move complex code blocks outside of regexes, avoiding the delimiter problems

* Status: TODO

Test Plan

New tests should be added.

* unfinished

Milestone 5.3 - Precedence parser

Milestone 5.4 - Improved multi-token

Phase 4 - improved runtime

The goal for this phase is to specify and implement the runtime libraries needed by the Perl-6.0.0-STD parser.

* Status:

On the Perl 5 runtime, the Runtime::Perl5::MOP is the preferred Object Model.

On the Lisp runtime, the Object Model is based on CLOS.

The Perl 5 native OO is no longer supported.

The Parrot, Python and JVM backends, which existed for MiniPerl6, are not currently active.

Milestone 4.1 - Add support for multis

The Sub and Method classes will be able to do multi-dispatch.

Status

Tests passed for a while, but are currently broken.

Multi subs need a more complete ".select" algorithm. It currently only checks for .arity

Multi token needs a better algorithm.

Dependencies

* The specification for multi dispatching; see S12:905.
* A working type system; finishing the Code, Signature, Capture classes and also Array and Hash
* There is sample code for "Code" in lib/KindaPerl6/Runtime/Perl5/Code.pm
* Grammar and AST support for signatures and captures

Tasks

* Signature and Capture
* Status: implemented
* dispatching algorithm
* Status: implemented
* Method and Sub refactoring
* Status: implemented
Add 'multi' to the Grammar
* Status: implemented
* Multi Regex, Multi Token
* Status: tests are currently failing.

Test Plan

The resulting code will be tested by running the existing test suite and implementation-specific tests.

* Status:

added tests for positional multis,

TODO: add tests for type-based multi dispatch

Milestone 4.2 - Runtime architecture review

The goal for this phase is to allow more kp6 data structures to be represented in plain Perl6.

Status

Under planning.

Dependencies

* Container code-review

The compiler needs to collect the side-effects of BEGIN blocks.

kp6 uses a native hash to store "modified" flags.

* Pad code-review
Status: the "Code" objects now hold the compile-time AST, for easier serialization.

Tasks

* Namespace support using plain Perl 6 hashes.

* Status:

Created a visitor module that refactors global variable access into namespace-hash access.

This is currently broken because the Hash implementation has autovivification problems.

Needs a refactoring of the "GLOBAL" perl5-runtime module.

* Rewrite the Pad structure using plain Perl 6

* Status:

Created a "Scope" class for holding "my" variables.

Needs a general emitter and runtime refactoring.

Test Plan

The resulting code will be tested by running the existing test suite.

* not started

Bonus Tasks

These tasks are not required for the successful completion of this phase.

Tasks

* dispatcher cache/memoization

Problem: open classes and inheritance

* Status: not started

* Junction dispatching

* Status: tests passed for a while, but are currently broken;

- added grammar support for infix:<|>, infix:<&>, all(), any().

- method .APPLY() on Junction objects needs more work. Some tests fail because the runtime can't tell if it should call a method on the Junction object or on the Junction elements. This can be fixed by verifying the Code.signature at "APPLY" time.

* default (Main) namespace, nested namespaces
Status: depends on milestone 4.2
* Lazy lists

* Status:

it is now possible to implement lazy lists in plain Perl 6;

Lazy ranges work.

* gather / take
* Status: lazy gather/take is implemented on P5 backend
* Threads

- TimToady and ruoso asked to avoid using Perl 5 threads.

- Lisp style call/cc is implementable in Perl 5. The AST transformation would take a while to implement.

- Threads implementation is deferred. Threads probably belong to the backend implementations.

* given / when
* Status: not implemented.
* IO

* Status:

implemented mkdir(), rmdir();

implemented the 'unsafe' flag

* Macros

* Status: added basic support in the grammar and AST.

- macro implementation is blocking, because mixing MP6 and KP6 runtimes makes the compiler environment unusable.

- it would be nice to have MP6 to emit KP6-runtime code.

* Bootstrapping on Perl 5

* Status:

KP6 can compile itself, but the regex runtime still have problems.

Bootstrapping is deferred to Phase 5.

* Lisp backend

* Status: some tests pass.

- Lisp can "dump" a compiled program. This can be a solution for collecting BEGIN-time side-effects, which is difficult to do in Perl 5.

* Parrot backend
* Status: idle.

Phase 3 - regex compiler refactoring

The goal for this phase is to refactor the regex compiler, to take advantage of the KindaPerl6 compiler architecture.

As a side effect, kp6 will also be able to use a native regex engine, if available. For example, PGE in the Parrot backend, and Pugs::Compiler::Rule in the Perl 5 backend. The kp6-regex engine will still be supported, for benefit of perl6-in-jvm and other backends.

Milestone 3.1 - Regex AST refactoring

The regex AST will be refactored from hash-of-hashes to Object-oriented.

Status

Finished.

Dependencies

* KindaPerl6 compiler architecture code-review

* finished

We need someone to review the previous phase results, in order to consider the "compiler architecture" phase finished. This is a non-blocking task.

From irc discussions:

    > - One of my basic design principles was to implement AST
    > transformations as "pluggable" modules, using a visitor pattern.
    > Do you see potential problems with this approach?

    No problems with the visitor pattern, but the way that "aspects" are
    implemented in the AST-plugins might cause hard-to-detect errors.
    For example, if the AST is changed in one place and the AST-plugin is
    not updated, no error will be reported (pmurias++).

    * this has been refactored; it's now more difficult to have an undetected bug

    > - BEGIN block side-effects are recorded in a hash. This adds an
    > overhead to all assignment operations. Do you see a better way to
    > check for side-effects?

    This will probably be discussed in an irc meeting scheduled for next week.

    Yesterday, we discussed the way the compiling environment is
    represented internally. It's complex, but it works. We don't have a
    simpler solution yet.
* KindaPerl6 syntax review

* finished; the syntax was not corrected

We need to verify that the KindaPerl6 grammar is a valid subset of Perl 6. This is a non-blocking task.

  * POD cannot contain #-comments in Pugs (bug)
    - workaround: move comments outside the pod (example: Grammar::Regex)
    
  * POD should finish in '=end', not '=cut'
  
  * ::Obj( val => 1 )  should be   Obj.new( val => 1 )
  
  * $obj.val(1)  should be  $obj.val := 1
    - the accessor declaration is "has $.val is rw"
    
  * s/<'...'>/'...'/g in several places in the grammar
  
  * (this one is no longer necessary; the spec now says the statements are returned in the right order) 
    XXX '@.body.>>emit' is wrong, because it would emit the statements in any order

Tasks

* Create the regex AST node classes
* finished
* Rewrite the hash constructors in the regex grammar to OO style
* finished

Test Plan

The resulting code will be tested by running the existing test suite.

* unfinished

Milestone 3.2 - Regex AST processor

The regex compiler will use the AST processor engine.

Status

* Some tasks finished.

Dependencies

* OO regex AST
The regex AST created in Milestone 1 must be fully implemented and tested.

Tasks

* Create an AST ".perl" dumper

* finished

This will be used for debugging

* Create an AST-to-Perl6 dumper

* finished

This will finish replacing the current kp6 code

* Merge the regex AST processor with the main AST processor

* finished

Currently, the grammar for "regex" returns Perl 6 procedural AST. This is because the regex AST processor is being called too early.

In this phase, the grammar will be refactored to return plain regex AST. This AST will be processed to procedural code later, by applying an optional plugin module.

Test Plan

The resulting code will be tested by running the existing test suite.

Milestone 3.3 - Additional Regex AST processors

The regex compiler will use the AST processor engine to implement additional semantics.

Status

* finished.

Dependencies

* OO regex AST
The regex AST created in Milestone 1 must be fully implemented and tested.

Tasks

* Identify which regex features are needed for parsing Perl-6.0.0-STD
* Identify which regex AST transformations are needed in order to implement the Perl-6.0.0-STD parser
* Create regex tests for the new features
* Implement the AST transformations

This task may require implementing additional regex runtime.

* Status: the 'RegexCapture' processor implements AST annotation for positional capture numbering, and for "capture to array" flags.

Test Plan

The resulting code will be tested by bootstrapping the compiler, and by running the improved test suite.

* Status: the compiler will not be bootstrapped yet, because it is easier to hack on the non-bootstrapped compiler for now.

Bonus Tasks

These tasks are not required for the successful completion of this phase.

Tasks

* Add support for optionally using Perl6regex-on-Perl5regex, as described in v6/v6-KindaPerl6/temp/backtracking-recursive-subrule.pl

* Status:

implemented as Visitor::EmitPerl5Regex; added a '-perl5rx' backend to kp6, that performs the p6rx-on-p5rx compilation.

* Add support for optionally using Pugs::Compiler::Rule in the Perl 5 backend
* Add support for optionally using Parrot Grammar Engine in the Parrot backend
* Regex backtracking

Choose one or more backtracking models, and implement them. This is specially important for Perl6regex-in-Perl6 (as implemented in Visitor::Token)

* Status: the '-perl5rx' kp6 backend implements backtracking by using the Perl5.8 regex engine.

* Special variables
Create COMPILING::<$?PARSER>, $?FILE, $?LINE
* Finer-grained error messages
* Grammar and precedence parser merged from Perl6-STD
* Lexically modifieable Grammar

Phase 2 - improved compiler architecture

This phase is finished. The product is the KindaPerl6 compiler, which implements a plug-in system for AST processors and backend emitters.

Phase 1 - bootstrap

This phase is finished. The product is the MiniPerl6 compiler, which is bootstrapped in Perl 5.