Overloaded method 'intersection' causing error

[sabu36]

On clisp, overloading for sets seems to be conflicting with the built-in one for lists. (I'm a noob so I could be missing something elementary.)

> (intersection '(a b c) '(c d a))
(A C)
> (load "ergolib/init")
…
> (require :ergolib)
…
> (intersection '(a b c) '(c d a))

*** - NO-APPLICABLE-METHOD: When calling
      #<STANDARD-GENERIC-FUNCTION INTERSECTION> with arguments
      ((A B C) (C D A)), no method is applicable.

[rongarret]

No, you aren’t missing anything. This is intentional. But if you don’t like it, it’s trivial to fix:

(define-method (intersection (s1 cons) (s2 cons)) (cl:intersection s1 s2))

and likewise for UNION. Alternatively, you can just call CL:INTERSECTION and CL:UNION directly instead of the shadowed versions.

The reason for this design decision is that IMHO CL:INTERSECTION and CL:UNION should not be used precisely because they only operate on lists. Lists are not well suited for representing sets. Computing unions and intersections on lists is inefficient. The representation of a set as a list is ambiguous because lists can contain duplicate elements but sets by definition cannot. Adding an element to a set represented as a list in a way that avoids duplicates is an O(n) operations. Hash tables are a much better representation of sets, which is what ergolib sets use under the hood. But the main reason for ergolib’s design is that it lets you easily change the underlying representation if you need to. If you use CL:INTERSECTION and CL:UNION you are committed to using lists as your set representation. That might have been a good idea in 1980, today not so much.

On Dec 21, 2020, at 8:37 AM, sabu36 notifications@github.com wrote:

On clisp, overloading for sets seems to be conflicting with the built-in one for lists. (I'm a noob so I could be missing something elementary.)

(intersection '(a b c) '(c d a)) (A C) (load "ergolib/init") … (require :ergolib) … (intersection '(a b c) '(c d a))

*** - NO-APPLICABLE-METHOD: When calling

with arguments

  ((A B C) (C D A)), no method is applicable.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[sabu36]

Thanks for detailed explanation.

I imagine you intend to keep this to fundamental and I don't know they qualify but I have some requests:

• for … setcollect (there's already sforce, which I feel could've been str-; s- reminds me more of set but maybe just me)
• filter that inputs a set but also outputs a set
• an equivalent for sets, of built-in set-difference for lists

I think they would enable staying on sets through multiple steps.

[rongarret]

These are all good suggestions, thanks for the feedback. Note that all of these are pretty elementary exercises, so if you want to implement them yourself and send me a pull request that is probably the fastest way to get these done.

There is also a bug in the INTERSECTION method that I just now noticed. That needs to be fixed too.

FYI, the reason that sets are a bit of a mess is that I never actually use them myself, so I just threw together a half-assed implementation as a placeholder to show how sets could be built on top of dictionaries. Histograms, indexes and binners are all kind of experimental that way too. But now that I know that someone is actually using this code I’ll put a little more effort into it.

Note that sets are particularly problematic because of the way the natural names for set-related things collide with Common Lisp’s standard library. For example, the natural name for a function that makes sets is SET, as a parallel to LIST, i.e. (list 1 2 3) returns a list, and (set 1 2 3) should return a set. But SET already has a function binding in CL, and it’s not that. The right way to solve this is to put ergolib into its own package, but that requires a fair bit of work to curate the list of exported symbols. Again, now that I know that someone besides me wants to use this code, I’ll bump it up on my priority list.

On Dec 22, 2020, at 4:29 AM, sabu36 notifications@github.com wrote:

Thanks for detailed explanation.

I imagine you intend to keep this to fundamental and I don't know they qualify but I have some requests:

for … setcollect (there's already sforce, which I feel could've been str-; s- reminds me more of set but maybe just me) filter that inputs a set but also outputs a set an equivalent for sets, of built-in set-difference for lists I think they would enable staying on sets through multiple steps.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.

[sabu36]

I'm studying a book called Land of Lisp and set (in terms of list or hash-table) came up in ch.8 (wumpus) and ch.10 (evolution) so far.

Some background on how I started using this library…

I was initially learning the book with Racket because of its pedagogical emphasis but I noticed (I made a table of equivalents):

• set! doesn't keep track of where the parameter came from, requiring separate setter for each case
• general version of a function has longer name—e.g., length (for list) vs sequence-length
• no type dispatching

I then briefly looked at other dialects as well but I decided on Common Lisp featurewise. At that point I wished there was a polished version and then I found your library.

---

By the way, on names and synonyms…

Scheme/Racket suffixes ? on predicates and ! on mutators. What's your sentiment on this? You have mappend and mappend! so you seem to be using it only to differentiate. Do you want to keep close to official on names?

From the point of view of a learner, it helps if a name has satisfying etymology. For example, princ apparently comes from "PRINt the Characters", which is not very satisfying for me. Scheme/Racket equivalent is display. (An earlier reply in the same link also suggests write-object instead of print-object and write-unreadable-object instead of print-unreadable-object though I never used those yet.) Another unsatisfying name is setf and some people were even confused on the etymology. How about synonyming it as set! since the other variants don't seem that common.

[rongarret]

On Dec 23, 2020, at 8:11 AM, sabu36 notifications@github.com wrote:

I'm studying a book called Land of Lisp and set (in terms of list or hash-table) came up in ch.8 (wumpus) and ch.10 (evolution) so far. Some background on how I started using this library…

I was initially learning the book with Racket because of its pedagogical emphasis but I noticed (I made a table of equivalents):

• set! doesn't keep track of where the parameter came from, requiring separate setter for each case • general version of a function has longer name—e.g., length (for list) vs sequence-length • no type dispatching I then briefly looked at other dialects as well but I decided on Common Lisp featurewise. At that point I wished there was a polished version and then I found your library.

Interesting. This is in fact exactly what ergolib was designed for. I was actually starting to work on a companion book of my own, but I didn’t get very far. You can find the beginning of my effort here:

https://github.com/rongarret/BWFP

If you’re interested in being a beta tester I could be persuaded to pick this effort up again.

By the way, on names and synonyms…

Scheme/Racket suffixes ? on predicates and ! on mutators. What's your sentiment on this? You have mappend and mappend! so you seem to be using it only to differentiate. Do you want to keep close to official on names?

I think Scheme’s “?" and “!" convention is a good one. But Ergolib is a Common Lisp library, not a new language, and so I am bound somewhat by Common Lisp’s conventions. My long-term plan was to segue from ergolib to an entirely new language (which would be called Ergo) some day, but at this point that’s unlikely to happen. The goal for Ergo was for it to have all the cool stuff that Common Lisp has but without the historical cruft, and with modern features like type inference and pattern matching. But getting all that done is a lot of work.

From the point of view of a learner, it helps if a name has satisfying etymology. For example, princ apparently comes from "PRINt the Characters", which is not very satisfying for me. Scheme/Racket equivalent is display. (An earlier reply in the same link also suggests write-object instead of print-object and write-unreadable-object instead of print-unreadable-object though I never used those yet.) Another unsatisfying name is setf and some people were even confused on the etymology. How about synonyming it as set! since the other variants don't seem that common.

The language that really got this right is T (also Oaklisp). The design there was that SET! would transform something in the form (SET! (F …) …) into ((SETTER F) …) where SETTER was a standard generic function that took an accessor and returned the mutator for that accessor. So, for example (SETTER CAR) ==> RPLACA. It was a beautiful design, but there are no extant languages that use it. SETF, which does more or less the same thing but at compile/macroexpansion time, is the closest thing there is. And it works pretty well despite being a little ugly. One of the things I’ve learned as I’ve gotten older is that at some point the pursuit of beauty has to yield to the realities of life.

rg

[sabu36]

When I said "other variants" I actually just meant SETQ and SET in Common Lisp—I didn't know about any variant in other languages—so I was just talking about names on the surface as I'm probably not at the level where I can appreciate what's going on internally.

I've just finished studying the draft and I'm looking forward to seeing how it continues. The book uses an IDE only available for mac so I had to setup emacs and slime (found by searching "meta-point lisp").