Arc Forum | On Lisp - Figure 18.5 matching function

Arc Forum

On Lisp - Figure 18.5 matching function

2 points by cthammett 3282 days ago | 4 comments

Good evening Ladies and Gents,

I am trying to convert the following into arc. In particular I am having difficulty converting the binding function. I think it involves using rfn and returning a list containing (cdr b) and b. Please find enclosed the link and code. http://unintelligible.org/onlisp/onlisp.html#SEC119

  (defun match (x y &optional binds)
    (acond2
     ((or (eql x y) (eql x '_) (eql y '_)) (values binds t))
     ((binding x binds) (match it y binds))
     ((binding y binds) (match x it binds))
     ((varsym? x) (values (cons (cons x y) binds) t))
     ((varsym? y) (values (cons (cons y x) binds) t))
     ((and (consp x) (consp y) (match (car x) (car y) binds))
      (match (cdr x) (cdr y) it))
       (t (values nil nil))))

  (defun varsym? (x)
    (and (symbolp x
      (eq (char (symbol-name x) 0) #\?)))
 
  (defun binding (x binds)
    (labels ((recbind (x binds)
      (aif (assoc x binds)
        (or (recbind (cdr it) binds)
	  it))))
     (let ((b (recbind x binds)))
       (values (cdr b) b))))

I'm wondering if this is close

  (def binding (x binds)
    (assign b
      (rfn recbind (x bind)
        (aif (assoc x binds)
          (or (recbind (cdr it) binds)
	    it)))))
    (list (cdr b) b))

2 points by zck 3281 days ago | link

I see that you've got some code that's working, but if you want to extend it more, I'll recommend a unit test library I wrote. You might find some unit tests helpful to know when your code is working. The library is https://bitbucket.org/zck/unit-test.arc/ .

You'll make unit tests inside a test suite, like so:

    (suite match
           single-specific-element (assert-same '(t t) (match '(a) '(a)))
           single-variable-symbol (assert-same '((?x 3) t) (match '(?x) '(3))))

And you'll run them like this:

    (run-suite match)

-----

2 points by cthammett 3280 days ago | link

Thanks this will be very useful.

-----

2 points by cthammett 3281 days ago | link

What I have so far seems to work.

  ;is the element a var symbol? i.e ?x ?y.. etc.
  (mac varsym? (x)
    `(and (is (type ,x) 'sym) (is ((string ,x) 0) #\?)))

  ;Are both elements varsyms? i.e ?x = ?y (?x . ?y)
  (mac tvs? (x y)
    `(and (varsym? (car ,x))(varsym? (car ,y))))

  ;is element x a varsym that hasn't been added to binds?
  (mac xvs? (x y binds)
    `(and (varsym? (car ,x))(~varsym? (car ,y))(no (assoc (car ,x) ,binds))))

  ;is element y a varsym that hasn't been added to binds?
  (mac yvs? (x y binds)
    `(and (varsym? (car ,y)) (~varsym? (car ,x))(no (assoc (car ,y) ,binds))))

  ;make bind i. e  ((?x . a)(?y . b))
  (mac mb (a b binds)
    `(push (cons (car ,a) (car ,b)) ,binds))

  (def match (x y)
    (let binds nil
      ((afn (x y)
        (if (or (no x) (no y)) binds ;lists are missing
          (if (iso x y) binds        ;list are the same
            (do
              (if (tvs? x y) (mb x y binds))
              (if (xvs? x y binds) (mb x y binds))
              (if (yvs? x y binds) (mb y x binds))	
            (self cdr.x cdr.y)))))
      x y)))

Tests

  (match '(p ?x b ?y a) '(p ?y b c a))
    ((?y . c) (?x . ?y))

  (match '(p ?x b ?y ?z) '(p ?y b c a))
    ((?z . a) (?y . c) (?x . ?y))

  (match '(a b c) '(a a a))
    nil     ... i.e nil bindings since there are no vars

  (match '(a b c) '(a b c)) 
    nil

-----

1 point by akkartik 3281 days ago | link

Nice! So does it work? :)

-----