Implementing fp pattern matching, using C++

Discussion in 'C++' started by Ole Nielsby, Sep 18, 2006.

  1. Ole Nielsby

    Ole Nielsby Guest

    First, bear with my xpost. This goes to
    with follow-up to comp.lang.c++

    - I want to discuss an aspect of using C++ to implement a
    functional language, and I'd like the attention of fp as well
    as C++ gurus if available.

    The language I'm implementing - PILS - is dynamically
    typed and heavily depending on pattern matching. Like
    with Lisp, programs are just data that happen to be
    executed. Generally, programs are built from rules, each
    consisting of a pattern and an action. It is not rare for
    rules to construct other rules and use them.

    While the language is generally interpreted rather than
    compiled, the patterns are compiled for speed. This
    happens dynamically: whenever a rule is constructed
    by the parser or by some PILS program, a code snippet
    for matching an arbitrary datum to the pattern is
    immediately generated behind the scenes.

    My current working implementation of PILS is a NASM
    shitpile, PILS data being represented as v-table based

    The pattern matching works by generating and executing
    strings of native code. The compiler works in two passes:
    first, it collects variable bindings and computes the code
    length, then (after allocating memory as required) code is

    When rules are trashed, their code memory is recycled.

    All objects have vtable methods that control what code
    should be generated if the object occurs in a pattern.

    Registers and stack are set up so that rejection of misfits
    is very fast.

    The generated code is stuff like:

    - immediate compares, to verify constants,
    - type checks to verify lists, nodes, numbers etc.,
    - loads, pushes, pops, to inspect substructures,
    - stores into slots, for variable firsts,
    - compares againts slots, for recurring variables,
    - stack management, allocation of slots, etc.,
    - calls of special routines for string searching etc.

    With C++, I can't do heavy native code generation and
    maintain a sensible level of portability - dynamic native
    code generation sort of doesn't fit in with C++ programming,
    so I have to think of something else.

    What should I do - and what have others done???

    Should I design a bytecode system, and use a giant
    switch statement or a function pointer array to execute it?
    (One problem with this approach is alignment - the code
    will have to include larger operands, should they be in
    separate segments, or inline aligned, or inline unaligned...)

    Or should I create arrays of function pointers instead of
    bytecode strings? This might be faster, or it might be just
    waste of space.

    Or should I create trees or linked lists of specialized
    vtable based matcher objects?

    Or should I take the trouble of placing the matcher
    objects consecutively, to save indirections and better
    utilize caches? (I think this is what I'm going to do,
    but I might be talked out of it...)

    How should type checks be done? By RTTI? By executing
    specialized virtual methods? By executing a single virtual
    method that returns a typecode? By somehow grafting the
    typecode directly into the vtable? By comparing specific
    methods in the vtable? (The two latter is what I used in
    NASM but I'm not sure the C++ community will endorse

    Type checking is complicated by the fact that there are
    lots of specialisations of general types. Nodes with
    particular combinations of attributes are recognized as
    conditional statements, additions, rules, you name it...
    and for these purposes given special vtables, but they
    should still be recognizable as just nodes. This means
    I can't just compare type ids.

    I don't expect someone to come up with the one and
    only solution - I'd just like to hear: did you ever do
    something similar, how did you do it, and why, and
    how did you like the result and what do you wish you
    had done instead?

    Or did you happen to stumble on a "become a dynamic
    pattern compiler expert in 21 days" manual recently?

    Ole Nielsby
    (maker of the still widely unknown PILS programming
    Ole Nielsby, Sep 18, 2006
    1. Advertisements

  2. Ole Nielsby

    Phlip Guest

    Ole Nielsby wrote:

    > Should I design a bytecode system, and use a giant
    > switch statement or a function pointer array to execute it?

    Raid the source of Ruby, Smalltalk, Python, Prolog, and Perl. They all solve
    generally the same problem. You also ought to target the Java VM, and have a
    huge installed platform base to run in.

    Phlip <-- NOT a blog!!!
    Phlip, Sep 18, 2006
    1. Advertisements

  3. Ole Nielsby

    Default User Guest

    Ole Nielsby wrote:

    > First, bear with my xpost. This goes to
    > comp.lang.c++
    > comp.lang.functional
    > with follow-up to comp.lang.c++

    This is a crappy idea. What do you expect the people on clf to do,
    subscribe to clc++ just to follow the conversation?

    Default User, Sep 18, 2006
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. CV
    Charles DeRykus
    Aug 31, 2004
  2. Maurice
    Oct 3, 2003
  3. Andrew Warkentin
    Andrew Warkentin
    Apr 11, 2008
  4. Adam Akhtar
    Adam Akhtar
    Nov 11, 2008
  5. Marc Bissonnette

    Pattern matching : not matching problem

    Marc Bissonnette, Jan 8, 2004, in forum: Perl Misc
    Marc Bissonnette
    Jan 13, 2004
  6. CV
    Gunnar Hjalmarsson
    Aug 31, 2004
  7. Mark Seger
    Ilya Zakharevich
    Nov 12, 2004
  8. Bobby Chamness
    Xicheng Jia
    May 3, 2007