m2ym/optima

assoc pattern matches '(1 (2 . 3)) which is not a list of conses

Closed this issue · 5 comments

guicho271828 commented

http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_a.htm#association_list

ANSI spec defines `association list' as folowing :

association list n. a list of conses representing an association of ...

however, in test/suite.lisp

(test constructor-pattern
  ;; cons
  (is-match (cons 1 2) (cons 1 2))
  ;; assoc
  (is-match '((1 . 2)) (assoc 1 2))
  (is-match '((1 . 2) (3 . 4)) (assoc 3 4))
  (is-match '(1 (2 . 3)) (assoc 2 3))   ;;;;;;;;;   <---

(1 (2 . 3)) is not a list of conses.
I think it should throw an error, but I also think it is OK to let it match for the sake of convenience as long as it is documented and warned in the README.

m2ym commented

A match error is raised internally at the case you specified, because the association of 2 and 3 doesn't match againt 1, that causes the matcher to continue to match againt other clauses. So I think it is fine.

guicho271828 commented

Thanks for the reply.

I think it should throw an error

Sorry now I don't know why I put it that way. I'd rather have to say "(assoc 2 3) should not match against '(1 (2 . 3)) because '(1 (2 . 3)) is not an association list".
The proper test may be (is-not-match '(1 (2 . 3)) (assoc 2 3)).

Or, the documentation could explain that (assoc a b) matches to any list which contains a cons matching against (cons a b), and it does not ensure the list is a proper association list.

NOTE: evaluating `(assoc 2 '(1 (2 . 3)))' raised an error on sbcl 1.1.14.

; SLIME 2013-11-17
CL-USER> (assoc 2 '(1 (2 . 3)))

The value 1 is not of type LIST.
   [Condition of type TYPE-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [*ABORT] Return to SLIME's top level.
 2: [ABORT] Abort thread (#<THREAD "repl-thread" RUNNING {1006010063}>)

NOTE 2: function assoc specifies the following:

Exceptional Situations:
Should be prepared to signal an error of type type-error if alist is not an association list.

http://www.lispworks.com/documentation/HyperSpec/Body/f_assocc.htm

m2ym commented

I don't remember why I chose this spec for assoc pattern. Maybe, I thought it must be expensive to check for the list to be a true association list or not.

guicho271828 commented

Hmm. I came to think that the thing is a bit complicated.

There is an ambiguity in ANSI spec itself -- it just says the user "should be prepared"... because I guess it does not always throw an error. Contrary to the example code above, (assoc 2 '((2 . 3) 1)) returned (2 . 3) without any errors. It seems like assoc is implemented (in each lisp implementation) in a way that it just /assumes/ each element is a cons, then some internal function calls like car throw a type error when they met a non-cons and try to evaluate (car 3).

Is assoc pattern implemented with function assoc itself? If so, we can say "assoc pattern depends on function assoc, so its behavior is implementation-dependent, the background is ...(bra bra bra)" and optima is not to be blamed. Also, it might be also the case that you were already aware of these problems and choose to make it that way, but you just forgot about it.