Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Implementing fp pattern matching, using C++

Reply
Thread Tools

Implementing fp pattern matching, using C++

 
 
Ole Nielsby
Guest
Posts: n/a
 
      09-18-2006
First, bear with my xpost. This goes to
comp.lang.c++
comp.lang.functional
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
objects.

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
generated.

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
them.)

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
language)


 
Reply With Quote
 
 
 
 
Phlip
Guest
Posts: n/a
 
      09-18-2006
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
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!


 
Reply With Quote
 
 
 
 
Default User
Guest
Posts: n/a
 
      09-18-2006
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?




Brian
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
implementing mvc - using observer pattern - beginner to OOP Adam Akhtar Ruby 8 11-11-2008 01:31 PM
Implementing a singleton pattern on a given session RSH ASP .Net 4 10-10-2007 05:01 PM
A class implementing the archiver pattern eyal.susser@gmail.com C++ 2 04-28-2005 02:31 PM
Implementing Mediator Pattern in C++ cppaddict C++ 2 08-05-2004 12:13 PM
Implementing Adapter Pattern with class and method renaming Maurice C++ 1 10-03-2003 03:00 PM



Advertisments