Velocity Reviews > Ruby > Pattern matching

# Pattern matching

Jon Harrop
Guest
Posts: n/a

 02-17-2007

Hi!

I recently got engaged in a thread on comp.lang.functional about ML and
Lisp. I posted some simple but efficient OCaml code that is difficult to
translate into Lisp:

let rec ( +: ) f g = match f, g with
| `Q n, `Q m -> `Q (n +/ m)
| `Q (Int 0), e | e, `Q (Int 0) -> e
| f, `Add(g, h) -> f +: g +: h
| f, g -> `Add(f, g)

let rec ( *: ) f g = match f, g with
| `Q n, `Q m -> `Q (n */ m)
| `Q (Int 0), e | e, `Q (Int 0) -> `Q (Int 0)
| `Q (Int 1), e | e, `Q (Int 1) -> e
| f, `Mul(g, h) -> f *: g *: h
| f, g -> `Mul(f, g)

let rec simplify = function
| `Q _ | `Var _ as e -> e
| `Add(f, g) -> simplify f +: simplify g
| `Mul(f, g) -> simplify f *: simplify g;;

This code does some simple rearrangements of symbolic expressions to
simplify them, e.g. 2+1*x+0 -> 2+x. It works with arbitrary-precision
rational arithmetic.

Does Ruby have pattern matching? If so, what does the above look like in
Ruby? If not, how else can you express this elegantly in Ruby?

Lisp doesn't have pattern matching but Pascal Constanza wrote quite an
elegant solution in Lisp using dynamic method dispatch:

(defstruct mul x y)

(:method ((x number) (y number)) (+ x y))
(:method ((x (eql 0)) y) y)
(:method (x (y (eql 0))) x)
(:method (x y) (make-add x :y y)))

(defgeneric simplify-mul (x y)
(:method ((x number) (y number)) (* x y))
(:method ((x (eql 0)) y) 0)
(:method (x (y (eql 0))) 0)
(:method ((x (eql 1)) y) y)
(:method (x (y (eql 1))) x)
(:method (x (y mul))
(simplify-mul (simplify-mul x (mul-x y)) (mul-y y)))
(:method (x y) (make-mul x :y y)))

(defgeneric simplify (exp)
(:method (exp) exp)
(:method ((exp mul))
(simplify-mul (simplify (mul-x exp)) (simplify (mul-y exp)))))

This has the advantage that Lisp optimises the above so that it is only 10x
slower than the OCaml. Unlike the OCaml, it can be extended and
automatically reoptimised at run-time.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet

Robert Klemme
Guest
Posts: n/a

 02-18-2007
On 17.02.2007 20:47, Jon Harrop wrote:
> I recently got engaged in a thread on comp.lang.functional about ML and
> Lisp. I posted some simple but efficient OCaml code that is difficult to
> translate into Lisp:
>
> let rec ( +: ) f g = match f, g with
> | `Q n, `Q m -> `Q (n +/ m)
> | `Q (Int 0), e | e, `Q (Int 0) -> e
> | f, `Add(g, h) -> f +: g +: h
> | f, g -> `Add(f, g)
>
> let rec ( *: ) f g = match f, g with
> | `Q n, `Q m -> `Q (n */ m)
> | `Q (Int 0), e | e, `Q (Int 0) -> `Q (Int 0)
> | `Q (Int 1), e | e, `Q (Int 1) -> e
> | f, `Mul(g, h) -> f *: g *: h
> | f, g -> `Mul(f, g)
>
> let rec simplify = function
> | `Q _ | `Var _ as e -> e
> | `Add(f, g) -> simplify f +: simplify g
> | `Mul(f, g) -> simplify f *: simplify g;;
>
> This code does some simple rearrangements of symbolic expressions to
> simplify them, e.g. 2+1*x+0 -> 2+x. It works with arbitrary-precision
> rational arithmetic.
>
> Does Ruby have pattern matching? If so, what does the above look like in
> Ruby? If not, how else can you express this elegantly in Ruby?

Not that I am aware of. Even a quick search on RAA doesn't reveal
anything: http://raa.ruby-lang.org/search.rhtml?search=pattern

I guess the major issue here between Ruby and Lisp is that you do not
have access to Ruby expressions natively the same way as you have in
Lisp. There are no macros that integrate nicely with the language as
Lisp macros do.

The Ruby solution would likely involve creating a parser for the
expressions you want to simplify, then simplifying the syntax tree and
outputting it again. For getting at the Ruby parse tree there are
indeed libraries, so that parse should not be too hard. In any case I
guess the solution will only be half as elegant as the other two you
presented.

Side note: the feature that comes closest to pattern matching is the
assignment grouping of expressions:

irb(main):014:0> a,(b,(c,d),e)=1,[2,[3,4],5]
=> [1, [2, [3, 4], 5]]
irb(main):015:0> a
=> 1
irb(main):016:0> b
=> 2
irb(main):017:0> c
=> 3
irb(main):018:0> d
=> 4
irb(main):019:0> e
=> 5

> Lisp doesn't have pattern matching but Pascal Constanza wrote quite an
> elegant solution in Lisp using dynamic method dispatch:
>
> (defstruct mul x y)
>
> (:method ((x number) (y number)) (+ x y))
> (:method ((x (eql 0)) y) y)
> (:method (x (y (eql 0))) x)
> (:method (x y) (make-add x :y y)))
>
> (defgeneric simplify-mul (x y)
> (:method ((x number) (y number)) (* x y))
> (:method ((x (eql 0)) y) 0)
> (:method (x (y (eql 0))) 0)
> (:method ((x (eql 1)) y) y)
> (:method (x (y (eql 1))) x)
> (:method (x (y mul))
> (simplify-mul (simplify-mul x (mul-x y)) (mul-y y)))
> (:method (x y) (make-mul x :y y)))
>
> (defgeneric simplify (exp)
> (:method (exp) exp)
> (:method ((exp mul))
> (simplify-mul (simplify (mul-x exp)) (simplify (mul-y exp)))))
>
> This has the advantage that Lisp optimises the above so that it is only 10x
> slower than the OCaml. Unlike the OCaml, it can be extended and
> automatically reoptimised at run-time.

I have to admit that I am only familiar with very basic Lisp. But it
does look elegant.

Kind regards

robert

Phil Tomson
Guest
Posts: n/a

 02-21-2007
On 2/17/07, Jon Harrop <(E-Mail Removed)> wrote:
>
> Hi!
>
> I recently got engaged in a thread on comp.lang.functional about ML and
> Lisp. I posted some simple but efficient OCaml code that is difficult to
> translate into Lisp:
>
> let rec ( +: ) f g = match f, g with
> | `Q n, `Q m -> `Q (n +/ m)
> | `Q (Int 0), e | e, `Q (Int 0) -> e
> | f, `Add(g, h) -> f +: g +: h
> | f, g -> `Add(f, g)
>
> let rec ( *: ) f g = match f, g with
> | `Q n, `Q m -> `Q (n */ m)
> | `Q (Int 0), e | e, `Q (Int 0) -> `Q (Int 0)
> | `Q (Int 1), e | e, `Q (Int 1) -> e
> | f, `Mul(g, h) -> f *: g *: h
> | f, g -> `Mul(f, g)
>
> let rec simplify = function
> | `Q _ | `Var _ as e -> e
> | `Add(f, g) -> simplify f +: simplify g
> | `Mul(f, g) -> simplify f *: simplify g;;
>
> This code does some simple rearrangements of symbolic expressions to
> simplify them, e.g. 2+1*x+0 -> 2+x. It works with arbitrary-precision
> rational arithmetic.
>
> Does Ruby have pattern matching? If so, what does the above look like in
> Ruby? If not, how else can you express this elegantly in Ruby?
>

http://www.artima.com/rubycs/article...sexp_dsls.html

Phil

Jon Harrop
Guest
Posts: n/a

 02-21-2007
Phil Tomson wrote:
> http://www.artima.com/rubycs/article...sexp_dsls.html

Great article. Thanks.

--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/product...ex.html?usenet