Pattern matching

Discussion in 'Ruby' started by Jon Harrop, Feb 17, 2007.

  1. Jon Harrop

    Jon Harrop Guest

    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 add x y)
    (defstruct mul x y)

    (defgeneric simplify-add (x y)
    :)method ((x number) (y number)) (+ x y))
    :)method ((x (eql 0)) y) y)
    :)method (x (y (eql 0))) x)
    :)method (x (y add))
    (simplify-add (simplify-add x (add-x y)) (add-y y)))
    :)method (x y) (make-add :x 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 x :y y)))

    (defgeneric simplify (exp)
    :)method (exp) exp)
    :)method ((exp add))
    (simplify-add (simplify (add-x exp)) (simplify (add-y 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/products/ocaml_for_scientists/index.html?usenet
     
    Jon Harrop, Feb 17, 2007
    #1
    1. Advertising

  2. 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 add x y)
    > (defstruct mul x y)
    >
    > (defgeneric simplify-add (x y)
    > :)method ((x number) (y number)) (+ x y))
    > :)method ((x (eql 0)) y) y)
    > :)method (x (y (eql 0))) x)
    > :)method (x (y add))
    > (simplify-add (simplify-add x (add-x y)) (add-y y)))
    > :)method (x y) (make-add :x 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 x :y y)))
    >
    > (defgeneric simplify (exp)
    > :)method (exp) exp)
    > :)method ((exp add))
    > (simplify-add (simplify (add-x exp)) (simplify (add-y 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
     
    Robert Klemme, Feb 18, 2007
    #2
    1. Advertising

  3. Jon Harrop

    Phil Tomson Guest

    On 2/17/07, Jon Harrop <> 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?
    >


    check out this article on artima by Topher Cyl:
    http://www.artima.com/rubycs/articles/patterns_sexp_dsls.html


    Phil
     
    Phil Tomson, Feb 21, 2007
    #3
  4. Jon Harrop

    Jon Harrop Guest

    Jon Harrop, Feb 21, 2007
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. DelphiDude
    Replies:
    3
    Views:
    1,176
  2. danpres2k
    Replies:
    3
    Views:
    7,496
    danpres2k
    Aug 25, 2003
  3. CV
    Replies:
    2
    Views:
    596
    Charles DeRykus
    Aug 31, 2004
  4. Marc Bissonnette

    Pattern matching : not matching problem

    Marc Bissonnette, Jan 8, 2004, in forum: Perl Misc
    Replies:
    9
    Views:
    244
    Marc Bissonnette
    Jan 13, 2004
  5. Bobby Chamness
    Replies:
    2
    Views:
    240
    Xicheng Jia
    May 3, 2007
Loading...

Share This Page