Arc Forum | Take the pattern-matching args challenge

Arc Forum

Take the pattern-matching args challenge

5 points by dreeves 6160 days ago | 9 comments

Here's the problem: Take a list representing a mathematical expression in postfix (aka RPN) and evaluate it.

  (2 2 +) => 4  or 
  (2 2 + 9 1 - /) => 1/2.

Pattern-matching args I feel make this very clean because you don't have to pick apart the arguments using destructuring-bind or whatnot.

Here's an implementation in mathematica: (2 underscores mean one or more elements; 3 underscores mean zero or more elements)

  (* start with an empty stack *)
  rpn[lst_] := rpn[lst, {}]

  (* all done; return what's on the stack *)
  rpn[{}, {x_}] := x  

  (* extra stuff on the stack *) 
  rpn[{}, {_, __}] := ERROR1

  (* divide by zero *)
  rpn[{Divide, ___}, {0, ___}] := ERROR2

  (* pop, pop, push... *)
  rpn[{a_Symbol, b___}, {x_, y_, r___}] := 
      rpn[{b}, {a[y,x], r}]

  (* just push... *)
  rpn[{a_, b___}, {s___}] := rpn[{b}, {a,s}]

Call it like so:

  rpn[{2,2,Plus,9,1,Subtract,Divide}] => 1/2

6 points by soegaard 6160 days ago | link

PLT Scheme:

  (require  (lib "match.ss"))

  (define (rpn xs) (rpn2 (list xs ())))
  (define rpn2
    (match-lambda
      [(() (x))                              x]
      [(()  xs)                              (error "extra stuff on stack")]
      [(('/ . _) (0 . _))                    (error "divisision by zero")]
      [(((and a (? symbol?)) . b) (x y . r)) (rpn2 (list b (cons ((eval a) y x) r)))]
      [((a . b) s)                           (rpn2 (list b (cons a s)))]))

  (rpn '(2 2 + 9 1 - /))
  (rpn '(2 2 + 9 9 - /))

-----

6 points by almkglor 6160 days ago | link

Reverse polish notation? Why not just model the stack directly? How is pattern-matching involved in this?

  (def rpn-eval (lst)
    (let stack nil
       (each c lst
         (if (isa c 'fn)
           (withs (snd (pop stack) fst (pop stack))
             (push (c fst snd) stack))
           (push c stack) ))
       (pop stack)))

-----

3 points by sacado 6160 days ago | link

(def rpn args

        (let stack '()

                (each elt args

                        (if (is (type elt) 'fn)

                                (with (second (pop stack) first (pop stack))

                                        (push (elt first second) stack))

                                (push elt stack)))

                (pop stack)))

-----

1 point by sacado 6160 days ago | link

then we've got :

arc> (rpn 2 2 + 9 1 - /)

1/2

-----

1 point by dreeves 6159 days ago | link

Thanks almkglor and sacado! At first I thought I was soundly defeated in the pattern-matching args challenge but I notice you don't catch the errors, either division by zero or too much stuff on the stack at the end. The fact that I can stick that in to my version without touching the rest of my code I feel points to the advantage of this style of programming.

And note that if I remove those error checks, my code is this:

  rpn[lst_] := rpn[lst, {}]
  rpn[{}, {x_,___}] := x
  rpn[{a_Symbol, b___}, {x_, y_, r___}] := rpn[{b}, {a[y,x], r}]
  rpn[{a_, b___}, {s___}] := rpn[{b}, {a,s}]

-----

2 points by almkglor 6159 days ago | link

Using my defpat macro (pushed on nex-3's arc-wiki.git):

  (defpat rpn
    (lst)          (rpn lst ())
    (() (x . xs))  x
    ((x . xs) (a b . s))
                   (if (isa x 'fn)
                      (rpn xs (cons (x a b) s))
                      (rpn xs `(,x ,a ,b ,@s)) )
    ((x . xs) s)
                   (if (isa x 'fn)
                      (ero "Too few parameters")
                      (rpn xs `(,x ,@s))))

Admittedly my defpat can't do the a_Symbol check, but then I can destructure more complex lists.

-----

1 point by dreeves 6159 days ago | link

I like defpat. It looks soegaard's scheme solution does allow things like the a_Symbol check, right? Also, mathematica does allow destructuring arbitrarily complex lists:

  f[{{a_,{b_,c_,{{d_},e_}}}}] := g[a,b,c,d,e]

-----

1 point by almkglor 6159 days ago | link

The problem in a lisplike is how to properly embed checks in destructuring binds. Since code represenetation == data representation, it's rather difficult to do:

  (defpat foo
    (x (isa x 'sym))
        (list x isa))

As it is, I'm already forbidding one symbol from being used for variables: quote. This is so that I can support:

  (defpat cmd
    ('niaw)   "cat"
    ('arf)    "dog"
    ('squeek) "mouse"
    (x)       (ero "unknown sound!"))

I don't know how scheme's pattern matching works; possibly yet another symbol has been removed from the allowed symbols.

-----

1 point by almkglor 6159 days ago | link

I've since added guards in defpat. See the arc-wiki, also http://arclanguage.org/item?id=2276

-----