Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
Just another Perl shrine
 
PerlMonks  

Re: Standardized Interface Design for Search tree

by ariels (Curate)
on Jun 25, 2002 at 11:49 UTC ( #177066=note: print w/ replies, xml ) Need Help??


in reply to Standardized Interface Design for Search tree

One Way To Do It1 is to steal ideas off of C++ and the STL. STL is based on concepts. A concept is a requirement of a thing, that is a combination of syntactic requirements (say, "two things must be comparable by saying $a->le($b)") and semantic requirements (say, "and this relationship must be a pre-order: if $a->le($b) && $b->le($c) then $a->le($c), and $a->le($a)"). In C++, operator overloading is prevalent, so these requirements are typically phrased in terms of existing operators; in Perl, overloading is probably too slow to force on the user, so we should avoid it.

The C++ STL then uses these concepts as bases for generic programming using templates. The C++ vector<T> isn't a vector<Object>! It doesn't require that all Ts inherit from a common ancestor (compare the aforementioned Hash::Element). This would not be type-safe (a vector of cars is NOT a vector of vehicles; the former cannot accept a submarine, but the latter can!). Instead, when you sort a vector (you really sort ranges in C++, based on the interval between 2 iterators, but let's keep things simpler than they really are...), the compiler generates code that assumes it can meaningfully compare T t1, t2; by checking whether t1 <= t2.

Perl is not C++. It isn't type-safe: variables don't really have types (you can say my Foo $foo, but the compiler cannot enforce this type safety). And it doesn't have templates; you can see these as only necessary for a type-safe language (so Perl doesn't need them), or as allowing for much better compilation, paying the price of type safety for vastly faster execution. But this should not prevent us from stealing!

So here's what I'd propose:

  • A search tree organises things of one or more types.
  • For any $a,$b in the search tree, $a->le($b) must be defined (i.e. "$a->can('le')").
  • This relation must be a pre-order: if $a->le($b) and $b->le($c) then $a->le($c), and always $a->le($a).
  • No inheritance of any kind is required to be defined.
  • (Optionally:) you may provide a coderef for comparisons; if you do not, the following will be used:
    sub { $_[0]->le($_[1]) }
Given these rules, you can define your data structures.

But how can we implement them cleanly? Well, some things (e.g. Math::BigInts) are compared using <=. For such MyObjs, we wrap as follows:

package Numeric; sub le { $_[0] <= $_[1] } package MyInt; our @ISA = qw(Math::BigInt Numeric);
(This pattern is usually called a "mixin": Numeric is a base class which only makes sense as part of multiple inheritance; you mix it in to some other class). Now MyInts are Math::BigInts which can be put into a Demerphq::SearchTree! If you have plain numbers, you can just bless them into Numeric, and they're ready for use in your search tree.

Of course, a similar strategy would give you Lexical, if needed. And a Hash::Element can be similarly wrapped by translating the method cmp into le.

Since a common base class for contained things buys us nothing in Perl (and almost nothing in other languages), we don't bother to make us of it.

If you really wanted to be creative, you could use TheDamian's multimethods to give a more symmetric definition. I wouldn't bother, though.

The most important differences in what I propose from C++ are that only objects can go into a search tree (C++ can put anything in any container, as long as it matches the concepts -- and these never require any methods of the "thing"), that there is no type safety, and that you lose out on C++'s optimization opportunities.

But then, if you want C++, you know where to get it...


Footnotes:

  1. "Way To Do It" is (I hope!) an unregistered trademark of Larry Wall.

Update:

I forgot. We have no SPL.


Comment on Re: Standardized Interface Design for Search tree
Select or Download Code
•Type Safety, was Re: Re: Standardized Interface Design for Search tree
by merlyn (Sage) on Jun 25, 2002 at 15:18 UTC
    I couldn't let this untruth stand unchallenged:
    Perl is not C++. It isn't type-safe
    While the first part is certainly true, the second part is absolutely not. Perl is compile-time type-safe in that a scalar cannot be accessed as a hash or array, nor can an array be accessed as a scalar or hash, etc etc. Perl is also run-time type-safe in that an object method cannot be called on an object that does not understand it without triggering an exception.

    Just because Perl is "smalltalk-like" in its type safety doesn't mean you have to "dis" it if you've only seen Java and C++ type-safety.

    And for the record, I prefer Perl's type safety to "always and only compile-time" type-safety in those other languages. For every hour you spend "working around" those, you could have been coding another useful hour instead.

    Compile-time type safety is neither necessary nor sufficient.

    -- Randal L. Schwartz, Perl hacker

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://177066]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2014-04-19 06:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (478 votes), past polls