473,695 Members | 2,787 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Implementing fp pattern matching, using C++

First, bear with my xpost. This goes to
comp.lang.c++
comp.lang.funct ional
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)
Sep 18 '06 #1
2 3390
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!!!
Sep 18 '06 #2
Ole Nielsby wrote:
First, bear with my xpost. This goes to
comp.lang.c++
comp.lang.funct ional
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
Sep 18 '06 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
6977
by: gsv2com | last post by:
One of my weaknesses has always been pattern matching. Something I definitely need to study up on and maybe you guys can give me a pointer here. I'm looking to remove all of this code and just use pattern matching to determine if the proper amount of numeric characters has been met. Here is the function I've already done. Any help you can give in a pattern matching solution would be much appreciated and very educational.
176
8119
by: Thomas Reichelt | last post by:
Moin, short question: is there any language combining the syntax, flexibility and great programming experience of Python with static typing? Is there a project to add static typing to Python? Thank you, -- greetz tom
9
3208
by: Xah Lee | last post by:
# -*- coding: utf-8 -*- # Python # Matching string patterns # # Sometimes you want to know if a string is of # particular pattern. Let's say in your website # you have converted all images files from gif # format to png format. Now you need to change the # html code to use the .png files. So, essentially
1
2733
by: Henry | last post by:
I have a table that stores a list of zip codes using a varchar column type, and I need to perform some string prefix pattern matching search. Let's say that I have the columns: 94000-1235 94001 94100 If I run a pattern matching search for the string "940", then I should get the top two rows of data back. If I run a pattern matching search for the string "94", then I should get all the three rows of data back.
10
4970
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement, knowledge of fast and practical algorithms is not commonplace." Hume and Sunday, "Fast String Searching", Software - Practice and Experience, Vol. 21 # 11, pp 1221-48
5
5752
by: olaufr | last post by:
Hi, I'd need to perform simple pattern matching within a string using a list of possible patterns. For example, I want to know if the substring starting at position n matches any of the string I have a list, as below: sentence = "the color is $red" patterns = pos = sentence.find($)
4
3327
by: phl | last post by:
hi, My question is: 1. To avoid possible memory leaks, when you use this pattern, after you have dealth with the unmanaged resources and before you take your object off the finalize queue, how are you sure that your managed object resources are completely freed up of resources it's might be using? In my case below I have a private bool variable. Are there any other managed resource that you might need to explicitly free up in
1
2765
by: VanKha | last post by:
I write this program for pattern-matching,but it gives wrong result: #include<iostream> #include<conio.h> #include<string.h> using namespace std; main() { char text,pat; cout<<"text:";cin>>text;
4
2110
by: Mohamed Mansour | last post by:
Hello, What is the purpose of implementing the Observer Pattern if we can trigger an event easily? For example (from books), You have a "Forecaster" which notifies "Observable" when a prediction is ready, then there is a "WeatherViewer" which calls methods from the "Observer Interface".
0
8619
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8555
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8971
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8824
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8817
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7651
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5831
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4336
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
2258
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.