cvs commit: ponie Roadmap

cvsuser     05/04/04 07:35:36

  Added:       .        Roadmap
  Log:
  Roadmap, iteration 2.
  
  Revision  Changes    Path
  1.1                  ponie/Roadmap
  
  Index: Roadmap
  ===================================================================
  =head1 Ponie Roadmap
  
  The purpose of Ponie is to provide source compatibility between Perl
  extensions written in C<C> and C<XS> with Parrot, and thereby allow many
  important existing CPAN modules to be used unchanged with Perl 6.
  
  In terms of implementation, Ponie is a large refactoring exercise. It
  involves taking a copy of the existing Perl 5 code base, and making
  incremental changes that gradually re-write it to use Parrot, ensuring that
  at each step nothing external changes. It's not about adding new features to
  Perl 5, and there a few tasks suitable for volunteers who do not already
  understand the C<C> programming language and the Perl 5 core.
  
  If you want to help, but you don't know C<C>, the best way contribute
  is to download Ponie from CVS, build and install it, and try using it to build
  and run the CPAN modules and scripts you already use. If everything works as
  expected, great, and please report your glad tidings to [email protected].
  If things don't work, please report what details of the problems (what OS,
  what modules, what went wrong) to [email protected].
  
  Another good way to contribute to the success of Ponie is to join the Phalanx
  project ( http://qa.perl.org/phalanx/ ). It aims to improve the regression
  tests of CPAN modules, which in turn will improve the testing of Ponie. A
  third good way is to contribute to Parrot, by working to completing the
  Parrot features that Ponie will need in the near future.
  
  =head2 Current state
  
  The current state is that we have Parrot embedded in Perl. Perl data structures
  have been completely hidden behind PMCs, and Perl access macros have all been
  replaced by functions that call methods on the PMCs. The internal data layout
  of the data structures can be changed at will. The location of IV, NV and RV
  has been changed, to demonstrate that all still works.
  
  Structure is currently
  
      +-----+
      | PMC |
      +-----+
         |     +---------+
         +-----| SV head | (including Perl's reference count)
               +---------+
                    |       +---------+
                    +-------| SV body |
                            +---------+
  
  
  All PMCs are registered with Parrot as external PMCs, to stop them being
  garbage collected. Perl is still doing full reference counting, and PMCs
  are unregistered at the point where Perl would free the SV's storage.
  
  [strictly actually there's a hack here - they're freed at scope end, because
  it seems that some parts of the Perl core manage to hold onto pointers to SVs
  that have been marked as free, which works because the core never actually
  calls free() on the RAM. Full stack walking and internal Perl GC would solve
  this]
  
  Currently only one PMC type is used, and all SV type conversion done via
  SvUPGRADE() uses the existing code in Perl_sv_upgrade, which allocates a
  new body and frees the old.
  
  =head2 Overview of where next
  
  The roadmap is broadly
  
  =over 4
  
  =item 1
  
  Progressively refactor all of the perl data structures to be PMCs. Do this by
  
  =over
  
  =item 1
  
  Moving the existing perl code inside PMCs, and the existing perl data
  structures behind PMCs, providing/changing perl 5 wrappers to keep the
  existing calling conventions working.
  
  =item 2
  
  Refactoring the code/structures into something that feels parrot native.
  
  =back
  
  =item 2
  
  Perl 5's type polymorphism is done with code in the ops. Parrot's is done
  with code in the PMCs. Move the complexity from the op code into appropriate
  PMC methods
  
  =item 3
  
  Perl 5 provides special features and behaviour, such as C<tie>, overloading,
  C<%ENV> and C<%SIG>, using "magic". Parrot provides this by using custom
  vtables and derived PMC types. Replace all use of magic with Parrot
  implementations.
  
  =item 4
  
  At this point we have a Perl interpreter which is looking much more like
  Parrot, using Parrot's data structures for storage, and having much simpler,
  Parrot-like ops. So we can convert the Perl 5 ops to Parrot ops, and migrate
  the Perl interpreter over from using its runloop to using the Parrot runloop.
  Probably generate the Parrot ops by walking the Perl 5 optree using a custom
  C<B> module. This would cost in startup time each run, but is likely to be the
  fastest way to get something functional.
  
  =back
  
  Each major item requires the previous major item to be completed first.
  
  This gives a Ponie that compiles Perl 5 code to Parrot bytecode, runs this
  bytecode in Parrot, allows existing CPAN modules to be compiled and linked
  to it, and enables calls from Parrot bytecode into the CPAN modules. The
  relatively slow compile speed for Perl 5 code is not a big problem as the
  generated bytecode can be saved out to disk. With this we attain the goals
  of the Ponie project - CPAN modules can be used directly from Perl 6.
  
  There are still improvements that could be made. The Perl 5 parser could be
  modified to emit Parrot bytecode directly. Larry Wall is working on changes
  to the Perl 5 parser codebase to emit Perl 6 code, and this work may provide
  a good foundation for emitting Parrot bytecode. Ponie would still be using
  the Perl 5 regexp engine, and the Perl 5 IO system. Both could be migrated to
  their Parrot equivalents.
  
  =head2 Detailed plans
  
  The detailed plans tend to be subject to change, because typically at some
  point part way working through the first item, you discover one of
  
  =over 4
  
  =item *
  
  there's a task that you overlooked that needs doing first
  
  =item *
  
  there's an unwarranted assumption in the Perl 5 core that has just turned into
  a bug and therefore now needs fixing. (Cue wild goose chase)
  
  =item *
  
  it becomes clear that this task is actually better done after one of the
  subsequent tasks. So the list is re-ordered and that gets started
  
  =item *
  
  there's something buggy or missing in Parrot, which needs fixing first.
  
  =back
  
  Currently the detailed tasks seem to depend closely on each other, and don't
  appear to be parallelisable, so it's tricky to find ways for a second person
  to help out by working on the Ponie codebase itself.
  
  =head3 Refactoring the Data structures
  
  Perl 5 contains an enormous amount of logic to perform data type conversions,
  spread across many functions in several files. For Ponie, this functionality
  needs to be migrated inside PMCs. Perl 5 uses reference counting to manage
  memory, with special casing to avoid needing to reference count items on its
  stack. Ponie needs to make Perl 5's memory management work with Parrot's
  garbage collection scheme.
  
  =over 4
  
  =item *
  
  Move the scalar body upgrade code from C<sv_upgrade> in C<sv.c> into the
  Perl 5 PMC. This encapsulates conversions between different Perl 5 data
  types, allowing the internal data representation to be changed as needed,
  and gives Ponie the flexibility to add more types. At this point Ponie will
  still only be using one PMC type, and making an explicit method call into
  the PMC.
  
  2 days
  
  =item *
  
  With the upgrade code inside PMCs, Ponie can be changed to make the public
  API call C<SvUPGRADE()> use the Parrot morph interface. Different Perl
  types will be in distinct PMC types (even if the implementation is currently
  identical). This will make the Perl data types start to behave like any
  other data types in Parrot, which is needed for interoperability with other
  languages including Perl 6.
  
  3 days
  
  =item *
  
  Migrate the number/string conversion code into the PMC.
  
  5 days
  
  =item *
  
  Make the C<PMC_get_intval>, C<PMC_getnumval> etc calls functional
  
  3 days
  
  =item *
  
  Currently Ponie is maintaining the Perl 5 reference count inside each PMC's
  data structures. Parts of the Perl 5 code, mostly involved in cleanup,
  currently rely on knowing a scalar's reference count. Parrot provides a
  way to register PMCs that live outside of its root set, which Ponie uses to
  register all its PMCs. Parrot's registration is actually holds a registration
  count which is a reference count, but its API doesn't allow access to this
  count. As this is internal information Ponie shouldn't really be allowed access
  to this, so it seems better that Ponie should track its own hash of PMCs.
  This also means that Ponie can iterate over all its "reference counted" PMCs,
  which I have a hunch will become useful at some point. This hash gets
  registered with Parrot, which makes all of Ponie's PMCs visible to Parrot's
  GC.
  
  This effectively moves the reference count out of each PMC's storage, which
  is needed for the next step.
  
  3 days
  
  =item *
  
  The PMCs still have the Perl 5 head/body structure internally. All locations
  are read by function calls, so it is possible to rearrange structures
  internally from the Perl 5 layout, without affecting Perl 5 code. (In fact,
  this has already been done). This head/body isn't using PMC storage
  effectively, and is particularly wasteful for simple types such as integers
  and strings. At this point it is possible to refactor the PMC storage layout
  to remove the head/body.
  
  In particular, given that the reference count is no longer stored in the PMC,
  it allows floating point values (NVs) to be stored in an unextended PMC
  structure, as there is not space in the PMC union for an integer reference
  count simultaneously with a floating point value. At first sight the SV
  flags entry may seem a problem for the smaller types, but as access to it is
  via a function call, it is possible to make the default PMC type for floating
  point assume set flags (NOK,pNOK) and morph the scalar to a larger type if
  any code requests the flags value read/write.
  
  4 days
  
  =item *
  
  Replace the complex SV copying code in C<sv_setsv> with copying code
  encapsulated within the PMC.
  
  5 days
  
  =item *
  
  Refactor the core to use C<*_set> macro variants when setting scalar values.
  
      /* From */
      SvNVX(sv) = 42;
      
      /* To   */
      SvNV_set(sv, 42);
  
  This will allow the non-C<_set> variants to be defined as read only within
  the core (and any XS module that requests this), which will allow greater
  reading efficiency (no need to pass a pointer to dereference), and permit
  tighter PMC data storage. (No need to store values that can be faked)
  
  This can be done in parallel with the SvPVX_readonly() task.
  
  5 days, although this may already be done for free if Dave is able to implement
  iCow.
  
  =item *
  
  Make read only look ups such as C<SvNV()> call the appropriate PMC method.
  
  2 days
  
  =item *
  
  Make calls such as C<sv_setnv> call the appropriate PMC method.
  
  A distinction needs to be made between value like calls, such as C<sv_setnv>
  and C<SvNV>, and internals-aware direct calls, such as C<SvNVX_set> and
  C<SvNVX>. The former expect magic to be called for them, the latter expect
  direct access and will handle magic themselves.
  
  4 days
  
  =item *
  
  Refactor the core to use a new C<SvPVX_readonly()> macro when requesting
  a pointer to a scalar's string that isn't going to be modified. Consider
  whether this also shouldn't return a C<'\0'> terminated string, or whether
  to introduce even more variants.
  
  Currently if C<SvPVX()> is called it returns a C<char *> pointer direct into
  the scalar's buffer, and the caller is free to alter the buffers contents.
  Most callers don't do this, but the implementation can't know this. By
  making a readonly variant, it frees up the implementation to avoid expensive
  read-write emulation whenever possible. (see later).
  
  5 days, although this may already be done for free if Dave is able to implement
  iCow.
  
  =item *
  
  Review the situation.
  
  At this point all the Perl datatypes should be fully contained within the PMC
  code. All public Parrot APIs should work on the PMCs, and all Ponie code
  should be calling those Parrot APIs rather than going direct. With the exception
  of magic, all private access to data structures should be via PMC get/set
  methods, with no assumptions about structure layout or storage.
  
  1 day
  
  =item *
  
  Refactor the Perl core code to avoid using reference counts. Arthur and I
  think that this is possible, and Dave suspects that there may be speed
  benefits from removing all the special case code that deals with the stack.
  
  This involves
  
  =over 4
  
  =item 1
  
  Making Parrot's GC walk the Perl 5 C stack.
  
  1 day
  
  =item 2
  
  Registering PMCs held in Perl globals.
  
  2 days
  
  =item 3
  
  Amending the reference, array and hash code to properly mark the contained
  PMCs as "in use".
  
  2 days
  
  =item 4
  
  Replacing C<SvREFCNT_inc()> and C<SvREFCNT_dec()> macros with null
  operations inside the core. (Unaware XS code would still use them)
  
  5 minutes
  
  =item 5
  
  Experimenting to find out how much of the special case code for the Perl stack
  and C<@_> can be removed.
  
  3 days
  
  =item 6
  
  Calling a high priority DOD run at every freetmps point. (Roughly every
  semicolon)
  
  2 days
  
  =back
  
  This change is risky, but we suspect it's the only way to get destruction
  right when Ponie's aggregate PMCs are passed out to unsuspecting Parrot
  code.
  
  =item *
  
  Refactor stashes to be a derived type of hashes. This means that Perl's hashes
  don't need to waste space storing the extra information needed by stashes.
  
  1 day
  
  =item *
  
  Refactor restricted hashes to be a derived type of hashes.
  
  1 day
  
  =item *
  
  With proper GC in place it becomes much easier to replace the implementation
  of Perl 5's hashes and arrays with types derived from the proper Parrot
  array and hash PMCs. This brings interoperability and code reuse. Removing
  the special cases of stashes and restricted hashes makes the implementation
  simpler.
  
  It's not clear whether pads need to be split out from arrays at this point,
  and the underlying code kept constant until such time as the pad code is
  replaced by Parrot's lexicals.
  
  5 days. Plus 3 for Pads if needed.
  
  =item *
  
  Replace the Perl 5 string storage with Parrot native storage. This makes
  Perl string scalars behave far more like any other Parrot type, which buys
  portability.
  
  It also buys efficiency, because Parrot can do copy-on-write for strings
  and even substrings.
  
  To provide C<SvPVX()> compatibility with the Perl 5 API, make the
  implementation copy the PMC's string contents to a temporary read-write
  buffer if called, and push a function onto statement exit that will write
  the buffer's contents back to the underlying PMC string. While the temporary
  buffer exists, its contents are master. (This may mean changing the PMC's
  vtable for the duration). This way the PMC behaves as if it's storing data
  in the Perl structure, without actually suffering the inefficiencies.
  
  To be useful this task depends on the readonly PVX being implemented.
  
  5 days
  
  =back
  
  65 days, plus 3 if Pads need migrating.
  
  =head3 Migrating complexity from Ops to PMCs
  
  This is probably parallelisable, at least at the level of working on groups of
  ops, such as numeric ops, string ops, array ops, IO ops, logic ops, I<etc>
  
  "Complexity" manifests itself as lots of code branches based on SV type, or
  op flags. Ideally in a Parrot world, all of this would become vtable methods
  called on different PMC types, or concealed inside the black box of PMC code.
  The problem with the Perl 5 approach is that it makes maintenance hard (logic
  is spread out in many places) and adding Perl 5 types nearly impossible. In
  particular creating derived type with small behaviour changes isn't viable.
  Perl 5 allows behaviour variations by using the "magic" system, which hangs
  extra information from the SV, but this approach means that all code must
  explicitly check for magic and call it as appropriate (once and at the right
  point), which is slower and potentially error-prone.
  
  Complexity is
  
  =over 4
  
  =item *
  
  Polymorphic integer/numeric/reference code in arithmetic operators. There are
  30 numeric operators with overloading, so if each has polymorphic code to
  migrate at half a day each, that's 15 days.
  
  =item *
  
  UTF8-or-not code branches. There are 21 string operators listed in perlfunc.
  If each takes half a day to tidy up, that's 11 days.
  
  =item *
  
  Code such as C<pp_rv2av> which switches based on SV type. There are 81
  instances of C<SvTYPE()> in the PP functions, so if each is 2 hours that's 20
  days.
  
  =back
  
  46 days.
  
  =head3 Migrating from Magic to PMCs
  
  This is probably parallelisable, at least in terms of different people being
  able to independently work on
  
  =over 4
  
  =item *
  
  C<tie>
  
  =item *
  
  Overloading
  
  =item *
  
  C<%ENV>
  
  =item *
  
  C<%SIG>
  
  =item
  
  C<pos>
  
  =back
  
  C<pos>, C<%ENV> and C<%SIG> are probably quite simple (1 day's work each?).
  
  =head4 tie
  
  Replacing C<tie> involves providing new vtables for the relevant PMC types
  which call back to the correct Perl methods for the operation concerned. Perl
  5 has 4 sorts of C<tie>ing. It's probably best to tackle in order of
  complexity, starting with the simplest, tied scalars. The C<TIE*> and C<UNTIE>
  methods don't need vtable support.
  
  =over 4
  
  =item *
  
  Scalars
  
  C<TIESCALAR>, C<FETCH>, C<STORE>, C<UNTIE>.
  
  1 week for creating the method call framework, and .5 day per method?
  
  =item *
  
  Hashes
  
  C<TIEHASH>, C<FETCH>, C<STORE>, C<EXISTS>, C<DELETE>, C<CLEAR>, C<FIRSTKEY>,
  C<NEXTKEY>, C<SCALAR> and C<UNTIE>
  
  6 half days for the 6 simple methods. 3 days for C<FIRSTKEY> and C<NEXTKEY>
  to get integration with Parrot's iterators.
  
  =item *
  
  Arrays
  
  C<TIEARRAY>, C<FETCH>, C<STORE>, C<FETCHSIZE>, C<STORESIZE>, C<UNTIE>, C<POP>,
  C<PUSH>, C<SHIFT>, C<UNSHIFT>, C<SPLICE>, C<DELETE>, C<EXISTS> and C<EXTEND>.
  
  2 days for C<FETCH> to C<STORESIZE> and C<EXTEND>. 1 day each for C<DELETE>
  and C<EXISTS> as it's not clear how well these map to Parrot vtable methods.
  1 week for the other 5.
  
  =item *
  
  File handles
  
  C<TIEHANDLE>, C<PRINT>, C<PRINTF>, C<WRITE>, C<READLINE>, C<GETC>, C<READ>,
  C<CLOSE>, C<UNTIE>, C<OPEN>, C<EOF>, C<FILENO>, C<SEEK> and C<TELL>
  
  12 methods. Initially Ponie won't be using Parrot's IO, so these from Parrot's
  perspective these will just be opaque named methods that only Ponie calls to,
  and only Ponie is called by. So 0 days - no work needed here.
  
  =back
  
  =head4 Overloading
  
  Operator categories are taken from Perl's F<overload.pm>. It includes "int"
  with transcendental operations, so I will too.
  
  Perl 5's overloading is a complex interaction between C macros in all the
  pertinent operators, C code in F<mg.c> and F<gv.c>, and Perl code in
  F<overload.pm>. I estimate that it will take 1 week to get a reasonable
  understanding of how the code works, and where to modify it, before starting
  on anything specific.
  
  =over 4
  
  =item * Arithmetic operations
  
      "+", "+=", "-", "-=", "*", "*=", "/", "/=", "%", "%=",
      "**", "**=", "<<", "<<=", ">>", ">>=", "x", "x=", ".", ".=",
  
  Presumably these will require an interface layer to
  
  =over 4
  
  =item 1
  
  Make calls to C<use overload> set up the correct vtables on PMCs
  
  =item 2
  
  Create PMC table routines that call back into Perl.
  
  =back
  
  There are 10 pairs of operators. It might be possible to initially implement
  the assignment variants in Perl space using the non-assignment code. This
  work might take a week? Then half a day per pair, for 2 weeks total?
  
  =item * Comparison operations
  
      "<",  "<=", ">",  ">=", "==", "!=", "<=>",
      "lt", "le", "gt", "ge", "eq", "ne", "cmp",
  
  14 operators. 1 week or so, using the code and experience from the arithmetic
  operations?
  
  =item * Bit operations
  
      "&", "^", "|", "neg", "!", "~",
  
  6 operators. 3 days?
  
  =item * Increment and decrement
  
      "++", "--",
  
  2 days? Perl uses one method for both pre and post. Does parrot use 2?
  
  =item * Transcendental functions
  
      "atan2", "cos", "sin", "exp", "abs", "log", "sqrt", "int"
  
  8 methods. 1 day to set up a framework, and 2 hours per method, for 3 days
  total?
  
  =item * Boolean, string and numeric conversion>
  
      'bool', '""', '0+',
  
  3 methods, but there is a special case noted. 3 days?
  
  =item * Iteration
  
      "<>"
  
  C<readline> and C<glob> are both overloaded to this method. Until Ponie uses
  Parrot IO, I don't think that this overloading needs to be implemented as a
  vtable method. However, to allow removal of all of Perl5's overloading magic
  infrastructure, it will probably be necessary to convert this to a PMC method
  call (from Ponie back to Ponie). So 1 day.
  
  =item * Dereferencing
  
      '${}', '@{}', '%{}', '&{}', '*{}'.
  
  These could be quite messy, as they presumably need to return valid Parrot
  references. 1 week?
  
  =item * Special
  
      "nomethod", "fallback", "=",
  
  The nomethod and fallback logic will need to be moved from F<gv.c> to code
  accessible to PMCs. The copy operator will need to be embedded in PMC code
  too. All this code acts as support for overloading implementations that don't
  define 100% of overloaded methods. It's not clear where the logic to implement
  this should actually go - C code in PMCs, or more Perl space code. 1 week?
  
  This probably needs doing in parallel, as needed, by the other ops.
  
  62 days.
  
  =back
  
  =head3 Migrating from Perl 5 Ops to Parrot bytecode.
  
  This is probably highly parallelisable - in theory each of Perl's 353 Ops can
  be worked on separately. In practice it is likely that similar ops share code,
  so it seems best to work on groups of ops together.
  
  During the transition period Larry suggests using a similar technique to the
  one he used when migrating from Perl 4 to Perl 5. Have a new Perl 5 op that
  is "jump into Parrot op dispatcher", and a Parrot op that is "jump into Perl 5
  op dispatcher". The Perl 5 parser, as today, builds a Perl 5 optree. The
  B module that does Perl 5 tree -> Parrot Bytecode stream conversion walks the
  tree in execution order, starting in a "Perl 5" state. When it encounters a
  sequence of 1 or more ops that are now implemented as Parrot ops, it writes
  out a section of Parrot bytecode containing the ops, finishing with a "jump
  into Perl 5" Parrot op that points to the correct continuation point in the
  Perl 5 tree. The Parrot bytecode is linked into the Perl 5 optree by replacing
  the sequence of translated Perl 5 ops with the "jump into Parrot" op pointing
  to the Parrot bytecode sequence.
  
  This way at runtime the flow of execution will seamlessly be passed between
  the Perl 5 and Parrot runloops, which allows a progressive conversion of
  Ops from Perl 5 to Parrot with programs (and regression tests) runnable
  throughout. As work progresses the proportion of Parrot ops will increase and
  Perl 5 ops decrease. When 100% of ops are Parrot ops, the interchange ops and
  the Perl 5 runloop can be removed.
  
  If this process averages out at 2 hours per op converted, then it will take
  88 programmer days.
  
  =head2 Release!
  
  The estimate is that this takes 261 days. This is a lot.
  
  About 50 days of the first 60 can't be parallelised easily. Later work is
  more parallelisable, less dependent, shorter, and far more suitable for
  others to work on.
  
  =head2 Future work
  
  After a first complete release of Ponie there are still improvements that
  could be made.
  
  =over 4
  
  =item *
  
  Modify the Perl 5 parser to emit Parrot bytecode directly.
  
  =item *
  
  Migrate from the Perl 5 regexp engine to the Parrot Rules Engine
  
  =item *
  
  Migrate from the Perl 5 IO system to the Parrot IO system
  
  =item *
  
  Replace the Perl 5 pad code with Parrot's lexicals.
  
  =cut