[Common Lisp] Implement new Concept Exercise: sameness

verdammelt commented 4 years ago

This issue describes how to implement the sameness concept exercise for the Common Lisp track.

Getting started

Please please please read the docs before starting. Posting PRs without reading these docs will be a lot more frustrating for you during the review cycle, and exhaust Exercism's maintainers' time. So, before diving into the implementation, please read up on the following documents:

Please also watch the following video:

The Anatomy of a Concept Exercise.

Goal

The goal of this exercise is to teach the student the variety of generic equality predicates in Common Lisp.

Learning objectives

Be familiar with eq, eql, equal and equalp and how each builds upon the previous.
Understand that = works for numbers and does some 'conversion' of numbers
Understand when not to use eq.
Know that most standard functions use eql for equality. (The exercise could use find or position for example).

Out of scope

conses, arrays, hash tables, structures. These are needed to teach the concept but are not being taught in this exercise.
type specific equality predicates such as char=, string= etc. These may be mentioned but are not being taught. (They can be taught in the exercises for the concept of the specific types.)

Concepts

sameness

Prerequisites

expressions
integers
symbols
conditionals (using case would be good for an exercise task)

Resources to refer to

https://eli.thegreenplace.net/2004/08/08/equality-in-lisp

Hints

After

It would be good to discuss the idiomatic/stylistic choice to use specific type equality predicates rather than the generic equality predicates. It is a common point raised in mentoring v2 exercises and I expect it will continue to be.

Representer

Analyzer

The analyzer should check for use of eq on characters and integers. This should cause the exercise to not be accepted with appropriate discussion.

Implementing

To show the full range of equality we will need to coach the student along on how to create some types they may not yet be familiar with (hash tables, arrays, structures). It is suggested to provide functions that construct such objects which the student could then use. Or provide such functions to produce the data for the tests to use. In either case such functions should have good documentation strings/comments which explain, briefly what they are doing but without digressing into the larger topic of the types are dealing with.

It will not be possible to write a test that shows that (eq #\a #\a) or (eq 0 0) may be false given the flexibility allowed to the implementations. This point should be mentioned in the instruction.md and/or after.md. It should also be caught by the analyzer.

Help

If you have any questions while implementing the exercise, please post the questions as comments in this issue.

TheLostLambda commented 4 years ago

Looks pretty good overall!

I'd suggest adding sameness as the concept (I think that's probably the only one being taught here) and adding the following concepts as prerequisites:

expressions
integers (so the student knows about =, but maybe not the type-trickery)
symbols (so they know about quoting)

Maybe we could mention here that most standard functions in CL use eql for equality. We could include the conditionals prerequisite and then use case as an example of this.

Finally, maybe this is the perfect place for adding an analyser? For discouraging things like (eq #\a #\a)?

Let me know what you think!

verdammelt commented 4 years ago

Excellent points! I will fold those into the issue text.

verdammelt commented 4 years ago

On and off I've been thinking about this exercise and I am having a problem coming up with how we can write an exercise for this.

It seems like we'd need to have the student write functions which use eq etc.. But those functions seem like they would be little more than a call to one of the equality functions.

Perhaps the problem I am having is thinking of a 'story' as to why the student must do this.

I sort of wish this exercise could be done in a style like the code 'koans' where the tests themselves should be modified to replace placeholders with the correct code.

TheLostLambda commented 4 years ago

I know what you mean, this is a tricky one. I think that the 'koans' style might work well, so perhaps the stub file could be a function like:

(defun equality ()
   (assert (_ 'hello 'HELLO))
   (assert (_ 2 2.0))
   (assert (_ "string" "StRiNg"))
   ...)

Then the student just fills in the proper function to make each statement valid, like:

(defun equality ()
   (assert (eq 'hello 'HELLO))
   (assert (= 2 2.0))
   (assert (string-equal "string" "StRiNg")))

If the filled-in operator is wrong, the test-runner can catch that panic.

The biggest issue with this is (though I think this always applied to this exercise) that we are relying more on the analyser than the test-suite (as the student could just submit an empty function and "pass" all of the tests).

Let me know what you think! Story may be a little tricky, but I'm sure we can come up with something once we have a plan for how we are testing things.

verdammelt commented 4 years ago

The biggest issue with this is (though I think this always applied to this exercise) that we are relying more on the analyser than the test-suite (as the student could just submit an empty function and "pass" all of the tests).

Yeah, that is a very good point. I had only been thinking about the issue of eq and how we can't test for how it handles numbers and characters... but in fact the student could just use equalp for any test we give them and it would work, unless we are careful to provide tests which would fail when given too permissive a predicate.

Let me know what you think! Story may be a little tricky, but I'm sure we can come up with something once we have a plan for how we are testing things.

Last time I looked I don't think any other track had an equality/sameness concept nor any exercises. Is that a sign that this might be not be a good 'concept'? I would have thought there might be something in JavaScript with this == and === issue but nothing there. Perhaps instead of a concept we teach them as they come up? So perhaps when we teach lists, arrays, vectors we teach these predicates.

TheLostLambda commented 4 years ago

Hmm, I've done some thinking on this and I think it would be good to keep this concept as I believe "sameness" in Common Lisp is probably more complex than any other language I've come across.

With that in mind, I've devised a way to shift the checking back to the test-suite (for the most part) and add a story. The brief sketch of the story could be:

You've designed a maze-solving robot, but it's so enthusiastic that it will use whatever key you give it to go through every door it can. The problem is that, behind some doors, there are traps! To protect your robot friend, you decide to give them a key that only opens the safe doors of the maze.

Then you have stub-file for the student that looks like this:

(defparameter *key1* nil)
(defparameter *key2* nil)

;; Maze Level 1 (*key1* will be used to fill in the blanks: _)
;; (cond ((_ "a trap!" "a trap!") (error "Trap 1"))
;;       ((_ 42 42.0) (error "Trap 2"))
;;       ((_ 'escape 'ESCAPE) (maze-level-2))))

;; Maze Level 2 (*key2* in the blanks)
;; (cond ((_ 2 2.0)   (if (_ "agh!" "AGH!")
;;                        (error "Trap 3")
;;                        (maze-level-3)))
;;       ((_ #\F #\F) (if (_ "freedom" "freedom")
;;                        (maze-level-3)
;;                        (error "Trap 4")))))

Then the student needs to give the robot the right keys (one of the equality predicates) to avoid the traps and make it through each level.

The test-suite could look like:

(defmacro maze-level-1 ()
  `(cond ((,*key1* "a trap!" "a trap!") (error "Trap 1"))
         ((,*key1* 42 42.0) (error "Trap 2"))
         ((,*key1* 'escape 'ESCAPE) (maze-level-2))))

(defmacro maze-level-2 ()
  `(cond ((,*key2* 2 2.0) (if (,*key2* "agh!" "AGH!")
                            (error "Trap 3")
                            (victory)))
         ((,*key2* #\F #\F) (if (,*key2* "freedom" "freedom")
                              (victory)
                              (error "Trap 4")))))

(defun victory () "Victory!")

Then, one of the possible solutions to the maze could be:

(defparameter *key1* 'eq)
(defparameter *key2* 'equal)

Which allows (maze-level-1) to return "Victory" without hitting any of the traps.

This is perhaps a tad elaborate, but might make for a fun puzzle. All the student needs to do is understand conditionals and pick keys, so while it's perhaps complex for the author, it's less so for the student (I'm intentionally hiding the macros and back-quoting).

Let me know how you feel about this sort of approach! I think it might be interesting :)

verdammelt commented 4 years ago

You've designed a maze-solving robot, but it's so enthusiastic that it will use whatever key you give it to go through every door it can. The problem is that, behind some doors, there are traps! To protect your robot friend, you decide to give them a key that only opens the safe doors of the maze.

Oh this is BRILLIANT! I love it.

This is perhaps a tad elaborate, but might make for a fun puzzle. All the student needs to do is understand conditionals and pick keys, so while it's perhaps complex for the author, it's less so for the student (I'm intentionally hiding the macros and back-quoting).

The only thing I worry about is that the macros and backquoting may be too confusing to show to the student especially if we keep this as an earlier concept exercise. But maybe we can use just plain functions?

Now that you've unlocked (pun at least partially intended) this idea would you mind letting me give a go at putting together this exercise? Or do you want to do it now that you've got this idea?

TheLostLambda commented 4 years ago

Glad you like it!

And feel free to give it a swing! I've had a bit of a busy week and have been moving a bit slow, but we should have 20 GitHub issues soon! I'll focus on getting there so we have loads to do for the Markathon!

As for the macros and back-quoting, I was just planning on "hiding" them in the test file and using the simplified comments in the stub-file to present the maze, but functions would be fine too (though I suspect we'd need a funcall somewhere?)

Let me know how things go! I'm excited to see what you come up with! :)

exercism / v3