Re: Which programming language is better to start




"Jon Harrop" <usenet@xxxxxxxxxxxxxx> wrote in message
news:42bc8515$0$30811$ed2619ec@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> >> I'm more interested in the case of a pattern match (because these are
not
> >> native in Lisp). ML does a lot of pattern match optimisations which, I
> >> assume, Lisp cannot do as a consequence.
> >
> > There is no concept of pattern matching on data in Lisp as there is in
> > MLs. These operation would be done by representing the data as lists
> > and applying basic list operations.

Probably not, except in a Lisp class teaching macros...

> There have been whole books written on pattern match optimisations. They
are
> fantastic constructs in terms of simplicity, expressiveness and providing
> great scope for optimisation. The main downside is that dissecting a data
> structure (e.g. lists) using pattern matches ties you to that data
> structure. In contrast, using maps and folds frees you from the underlying
> data structure.
>
> For example, if you have a string match like:
>
> "ABC" -> 1
> | "ABD" -> 2
> | "ABE" -> 3
> | _ -> 0
>
> then you can clearly just lookup the third character in the incoming
string
> and do a little arithmetic (and a branch) to get your answer. Naively
> implementing this requires many branches and many string compares. More
> generally, ML can use hashing (sometimes with optimal hash functions) to
> achieve fantastic performance on much more complicated matches.

Sure. Lisp can use hashing too.

> There are many other optimisations, particularly decision-tree based
> optimisations which can be applied to data structure pattern matches. This
> lets the ML compiler minimise the number of branches required whilst
> guaranteeing the same result.
>
> I had guessed that you could add pattern matches to Lisp but that the Lisp
> compiler could not achieve anything like the performance of ML pattern
> matches.

I still don't see why.


--
Matthieu Villeneuve


.



Relevant Pages

  • Re: Which programming language is better to start
    ... How does Lisp handle monomorphic types? ... If you don't specify a variable to have a type then the compiler ... ML does a lot of pattern match optimisations which, ... These operation would be done by representing the data as lists ...
    (comp.programming)
  • Re: Parallel Common-Lisp with at least 64 processors?
    ... My original point was that Lisp makes high-level programming ... high-level abstract constructs like pattern ... matching are heavily optimized by the compilers of all modern ... A list of records, a list of BNF production rules, ...
    (comp.lang.lisp)
  • Re: merits of Lisp vs Python
    ... many other interesting features that haven't originated from Lisp (e.g. ... Various pattern matching ideas have been implement (not always first, ... can be associated with elementary patterns which check relationships ...
    (comp.lang.lisp)
  • Re: Unlearning Pattern Matching
    ... It's almost hard to believe a language can be ... This ML-style pattern matcher ... takes just a few hours to write, even less for a real Lisp guru. ... Obviously you haven't read Dijkstra's PATTERN MATCHING considered ...
    (comp.lang.lisp)
  • Re: Parsing an HTML file - skipping to a line
    ... let's say you want to process the lines after a pattern matches, ... # Test $_ for the pattern ... Note that the line with the pattern match assigns the result (a ... But, again, are you searching a text file or an HTML ...
    (perl.beginners)