Simple pattern-matching in a functional way

[Alex Shabanov]

Several days ago I needed an easy to use and easy to extend facility
that performs pattern matching.

I ended up with the following interface:

// matcher function. To prevent situations when no pattern matches the
object given,
// it might be initialized as follows:
// matcher = function() { throw new Error("no applicable pattern
found") }
var matcher

matcher = combine(PATTERN1, CALLBACK1(OBJ, .. OPTIONAL_ARGS){...},
matcher)
matcher = combine(PATTERN2, CALLBACK2(OBJ, .. OPTIONAL_ARGS){...},
matcher)
// the result of combine method shall be immediately callable to
perform pattern matching
matcher = combine(PATTERN3, CALLBACK3(OBJ, .. OPTIONAL_ARGS){...},
matcher)

....

// perform pattern matching
matcher(OBJ, ... OPTIONAL_ARGS)

Here is a sample usage:

var matcher = function(val, arg) {
print("matcher fallback: val = " + val + ", arg = " + arg)
}

matcher = pm.combine({type: "string"}, function(val, arg) {
print({expr: "matcher(stringVal, arg)", value: "val = " + val
+ ", arg = " + arg})
}, matcher)

matcher = pm.combine({instanceOf: Function}, function(val, arg) {
print({expr: "matcher(functionVal, arg)", value: "val = " +
val + ", arg = " + arg})
}, matcher)

matcher = pm.combine({scheme: {key: "number", value: "any"}},
function(val, arg) {
print({expr: "matcher({key:number, value:any}, arg)", value:
"val = (" + val.key + "," + val.value + "), arg = " + arg})
}, matcher)

matcher(5, "one")
matcher("str", "two")
matcher(new Function("return 1"), "three")
matcher({key: 12, value: 34}, "four")
matcher({key: "some", value: "unk"}, "five")

Here is an implementation:

// namespace
var pm = {}

/**
* Matcher functions constructors are used in pm.combine method.
* Each key in this object corresponds to the certain pattern member.
*/
pm._matcherConstructors = {
instanceOf: function (matcher, instanceTarget) {
return function (obj) {
if (obj instanceof instanceTarget) {
return matcher.apply(this, arguments)
}
return false
}
},

type: function (matcher, typeId) {
return function (obj) {
if (typeof(obj) === typeId) {
return matcher.apply(this, arguments)
}
return false
}
},

scheme: function (matcher, scheme) {
return function (obj) {
if (typeof(obj) !== "object") {
return false
}
for (var i in scheme) {
if (i in obj) {
var target = obj
var source = scheme
var sourceType = typeof(source)
if (sourceType === "string") {
if (source === "any" || source ==
typeof(target)) {
continue
}

return false
}

if (source !== target) {
return false
}
}
else {
return false
}
}
return matcher.apply(this, arguments)
}
}
}

/**
* Creates pattern matching function that accepts the pattern given.
* The latter combined patterns takes priority over the previously
declared ones.
* @param pattern Pattern to match the target object.
* @param callback User-defined callback to accept target object as
well as the accompanying arguments.
* @param prevMatcher Previous matcher function created by combine
method or null or undefined.
* @returns Matcher function to be used as follows:
matcher.call(objectToBeMatched, optionalArguments...).
*/
pm.combine = function(pattern, callback, prevMatcher) {
var matcher = function() {
callback.apply(this, arguments)
return true
}

// join visitor function according to the pattern given
for (var i in pattern) {
if (!(i in pm._matcherConstructors)) {
throw new Error("unexpected pattern tag: " + i)
}

matcher = pm._matcherConstructors(matcher, pattern)
}

// if prev matcher either undefined or null - create new function
if (prevMatcher == null) {
return matcher
}
else {
return function() {
if (matcher.apply(this, arguments)) {
return true
}
return prevMatcher.apply(this, arguments)
}
}
}

/**
* Helper function that initializes matcher for all the types of
objects with
* the callback that throws an error.
*/
pm.unknownObjectMatcher = function() {
throw new Error("unknown object matched")
}


Comments appreciated

 

[Thomas 'PointedEars' Lahn]

Several days ago I needed an easy to use and easy to extend facility
that performs pattern matching.

I ended up with the following interface:

[...]

Comments appreciated

Looks like an awful lot of code to do what could probably be done in one
line. Perhaps you could explain why one would use your approach instead?


PointedEars

 

[Alex Shabanov]

Several days ago I needed an easy to use and easy to extend facility
that performs pattern matching.

I ended up with the following interface:

[...]

Comments appreciated

Looks like an awful lot of code to do what could probably be done in one
line.  Perhaps you could explain why one would use your approach instead?

This is to avoid using lots of typeofs and ifs to analyze certain
incoming object.
You can think of using this approach as of visitor pattern. In
contrast to visitor pattern, pattern-matching approach deals with
object type or with it's structure or with both.

A benefit to hand-written approach is that pattern matching provides a
kind of abstraction layer to the code what deals with the object's
structure.

 

[Thomas 'PointedEars' Lahn]

Several days ago I needed an easy to use and easy to extend facility
that performs pattern matching.

I ended up with the following interface:

[...]

Comments appreciated

Looks like an awful lot of code to do what could probably be done in one
line. Perhaps you could explain why one would use your approach instead?

This is to avoid using lots of typeofs

By making a lot of comparably more expensive calls instead. The
requirements being made to the capabilities of the implementation are also
more than with `typeof' -- which is not a function, BTW -- and friends.

and ifs to analyze certain incoming object.

Note that 5 and "str" are primitive values.

You can think of using this approach as of visitor pattern. In
contrast to visitor pattern, pattern-matching approach deals with
object type or with it's structure or with both.

A benefit to hand-written approach is that pattern matching provides a
kind of abstraction layer to the code what deals with the object's
structure.

I still do not see the problem this is supposed to solve; except perhaps
extensive method overloading, which is inherently flawed and so should be
designed out of an API to begin with.


PointedEars

 

[Alex Shabanov]

Alex Shabanov wrote:
Several days ago I needed an easy to use and easy to extend facility
that performs pattern matching.
I ended up with the following interface:
[...]
Comments appreciated
Looks like an awful lot of code to do what could probably be done in one
line.  Perhaps you could explain why one would use your approach instead?

This is to avoid using lots of typeofs

By making a lot of comparably more expensive calls instead.  The
requirements being made to the capabilities of the implementation are also
more than with `typeof' -- which is not a function, BTW -- and friends.

and ifs to analyze certain incoming object.

Note that 5 and "str" are primitive values.

Yep, I know. The "matcher" function given above does understand
primitives as well as objects.

I still do not see the problem this is supposed to solve; except perhaps
extensive method overloading, which is inherently flawed and so should be
designed out of an API to begin with.

This is exactly the case I dealt with.
I needed to write a sort of print function that takes one parameter
and prints it in a way that depends on type and structure of the
object given. E.g. strings shall be printed as is, objects with expr
and value properties shall be represented as two differently colored
elements, the object with snippet property shall be represented within
an expandable element, etc.

The other sample is when I needed to display a widget that intended to
show a particular object in particular state. The problem was that
there were too much objects and their states so I ended up with a mess
of numerous if-expressions.

Of course, most of the real life problems are trivial and can be best
expressed with just built-in means but not all of them.
It is funny - I never ever needed to use regular expressions during my
professional career though I wrote literally hundreds of them in
academic years.
I wouldn't say that regular expressions are useless but I've just
never encountered a task that'd require them.

 

[Thomas 'PointedEars' Lahn]

This is exactly the case I dealt with.

So you worked around a problem by creating a lot of other problems.
That does not sound like a viable strategy to me.

I needed to write a sort of print function that takes one parameter
and prints it in a way that depends on type and structure of the
object given. E.g. strings shall be printed as is, objects with expr
and value properties shall be represented as two differently colored
elements, the object with snippet property shall be represented within
an expandable element, etc.

Unless host objects are involved, in which case this function should never
be exposed to them, this problem is much better solved with polymorphism.

Of course, most of the real life problems are trivial and can be best
expressed with just built-in means but not all of them.

ISTM this one can.

It is funny - I never ever needed to use regular expressions during my
professional career though I wrote literally hundreds of them in
academic years.
I wouldn't say that regular expressions are useless but I've just
never encountered a task that'd require them.

Chances are that you are doing something wrong, then.

Please trim your quotes to the relevant minimum, do not quote signatures.


PointedEars

 

[nick]

It is funny - I never ever needed to use regular expressions during my
professional career though I wrote literally hundreds of them in
academic years.

That's quite a statement! Maybe you haven't been doing anything that
requires processing text, or you've using them without really noticing
it?

I probably use at /least/ one regex a day for work or just everyday
stuff... Think how often tools like grep and sed come in handy, even
for non-programming related tasks? I'm sure I type "grep" at least
once a day, and I use sed or similar techniques fairly often when
refactoring code.

I wouldn't say that regular expressions are useless but I've just
never encountered a task that'd require them.

I can think of a few useful real-world applications off the top of my
head...

- For scanners / parsers (think syntax highlighting)
- For URL rewriting (mod_rewrite and co.)
- For input validation (that's not a valid email address!)
- For text munging (e.g. find a URL in a block of text, create a
hyperlink)

Seems to me regex is the way to go when you need to search/filter/
replace text in all but the simplest cases. I'm curious how you've
managed to avoid them so thoroughly in your professional career?

 

[Alex Shabanov]

...
So you worked around a problem by creating a lot of other problems.
That does not sound like a viable strategy to me.
...
ISTM this one can.

Could you please clarify what strategy is acceptable from your point
of view?
To introduce lots of if+typeof+in?
Too error prone, from my point of view.

 

[Alex Shabanov]

...
Seems to me regex is the way to go when you need to search/filter/
replace text in all but the simplest cases. I'm curious how you've
managed to avoid them so thoroughly in your professional career?

Well, I'm surprised too
I'm not alone who writes code so text filtering tasks always assigned
to solve to someone else.
And yes, I wrote regex for grep and sed though I didn't take them into
an account

 

[Thomas 'PointedEars' Lahn]

Trimming quotes means to trim the quotes you are not referring to, and to
summarize, if necessary, those which you are referring to. It does not mean
to completely destroy the context of a quotation.

Could you please clarify what strategy is acceptable from your point
of view?

AISB, polymorphism, unless host objects are involved. Let the (values
converted into) objects have a method with the same name that does the
serialization.

To introduce lots of if+typeof+in?
No.

Too error prone, from my point of view.

As for error-proneness, your approach beats almost everything else by
inches.


PointedEars

 

[Alex Shabanov]

AISB, polymorphism, unless host objects are involved.  Let the (values
converted into) objects have a method with the same name that does the
serialization.

This works bad for situations where an incoming object taken from,
say, JSON response.
Of course, for some cases the visitor pattern might be used (I guess
this is what you mean by polymorphism approach), but not always.
E.g. consider "named parameters" feature when you have one function
that might take a big variety of incoming objects, say:
print("sample arg")
print({ expr: "sample expr", value: 45 })
print({ expr: "sample expr", value: "sample val" })
print({ snippet: "Huge block of text..." })
print(new SomePrintableObject(arg1, arg2,..))
And for each line a different printing algorithm should be used.

As for error-proneness, your approach beats almost everything else by
inches.

Your criticism is groundless.

 

[Thomas 'PointedEars' Lahn]

This works bad for situations where an incoming object taken from,
say, JSON response.
No.

Of course, for some cases the visitor pattern might be used (I guess
this is what you mean by polymorphism approach),

I have not studied the Visitor pattern in detail, but from its abstract ISTM
I mean quite the contrary: I do not want to separate the algorithm from the
object structure it operates on, I want to join them.

but not always.

E.g. consider "named parameters" feature when you have one function
that might take a big variety of incoming objects, say:
print("sample arg")
print({ expr: "sample expr", value: 45 })
print({ expr: "sample expr", value: "sample val" })
print({ snippet: "Huge block of text..." })
print(new SomePrintableObject(arg1, arg2,..))
And for each line a different printing algorithm should be used.

So what? either the referred supported *native* object already has a method
like e.g. serialize() or its prototype can be (temporarily) augmented with
one:

/*
* This one should be temporarily only, so the RHS should probably be kept
* in a closure
*/
Object.prototype.serialize = function () {
/* ... */
};

/* No real harm in keeping this one */
String.prototype.serialize = function () {
/* ... */
};

/* Can be provided along with the declaration */
SomePrintableObject.prototype.serialize = function () {
/* ... */
};

All your print() method (which is an unwise identifier, BTW) needs to do
then is essentially to check for the existence of this method on the passed
value (of course, if you augmented temporarily you would choose a much less
likely identifier, like one returned by jsx.object.findNewProperty()), call
it, and return its result.

Your criticism is groundless.

No, it is not. Search the archives, including those jQuery threads (they
made the same mistake as you, or vice-versa).


PointedEars

 

[Alex Shabanov]

Alex Shabanov wrote:
...
I have not studied the Visitor pattern in detail, but from its abstract ISTM
I mean quite the contrary:  I do not want to separate the algorithm from the
object structure it operates on, I want to join them.



So what?  either the referred supported *native* object already has a method
like e.g. serialize() or its prototype can be (temporarily) augmented with
one:

  /*
   * This one should be temporarily only, so the RHS should probably be kept
   * in a closure
   */
  Object.prototype.serialize = function () {
    /* ... */
  };

  /* No real harm in keeping this one */
  String.prototype.serialize = function () {
    /* ... */
  };

  /* Can be provided along with the declaration */
  SomePrintableObject.prototype.serialize = function () {
    /* ... */
  };

All your print() method (which is an unwise identifier, BTW) needs to do

"print" identifier was taken just to illustrate an idea.

then is essentially to check for the existence of this method on the passed
value (of course, if you augmented temporarily you would choose a much less
likely identifier, like one returned by jsx.object.findNewProperty()), call
it, and return its result.

I knew about the possibility to extend prototypes but never thought of
it in that way, I mean temporary extension or "augmentation".
This is quite an interesting approach.

No, it is not.  Search the archives, including those jQuery threads (they
made the same mistake as you, or vice-versa).

Thank you very much for your comments.

PointedEars
--
    realism:    HTML 4.01 Strict
    evangelism: XHTML 1.0 Strict
    madness:    XHTML 1.1 as application/xhtml+xml
                                                    -- Bjoern Hoehrmann

Alex