1
\$\begingroup\$

I'm working through Paul Graham's ANSI Common Lisp and in Exercise 2.5, I'm stumped. My specific question (I wasn't sure whether this type of question is suitable for stack overflow, code review, or neither) is:

How to even begin working on an answer to this question.

What's interesting is that I simply don't know how to proceed, analytically. Hopefully, it isn't a question which involves simply knowing the answer due to existing familiarity. So, my question is subtle, and it's not simply to ask 'what is the answer', but 'how could you go about finding the answer', if you were really stumped. So I'm asking about method.

The Question: What do these functions do?

(defun enigma (x)
  (and (not (null x))              
       (or  (null (car x))        
            (enigma (cdr x)))))

(defun mystery (x y)
  (if (null y)
      nil
      (if (eql (car y) x)
          0
          (let ((z (mystery x (cdr y))))
            (and z (+ z 1))))))

I've realised in typing this in that one approach would be simply to run the functions. Perhaps we could call that the "what does this button do?" approach. :)

Update: before posting this, I've found I just solved the first one. The method I used (I won't reveal the answer completely here, but the following will certainly make it much easier to guess): just run the function with various inputs. First I discovered it errors unless the argument is not a list (we see it calls car on the arg). So, the first arg to and looks like a base case. While it's clear to me now what it does (easy to say), the only way I was able to discover it was by playing with various inputs. It seemed always to return nil on any input I gave it. That seemed strange. Then I just looked at the line (or (null (car x)), and it's easy to see how to make that evaluate to true: put a nil as an element of the list. And then the secret was revealed... This seems an interesting function, worth plenty of attention. I do love recursion :)

The second remains mystery for now. Please remember, I'd appreciate discussion to be around method and/or techniques, if anyone would care to chip in. Obviously there's much less value in just revealing the answer.

\$\endgroup\$

closed as off-topic by Vogel612 Mar 20 at 7:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Welcome to Code Review! Unfortunately this question doesn't reflect what the site is about. We review code that you have written for improvements. It's not on topic to ask for explanations of code that has been written by someone else than you. For more information, see the help center. Thanks. \$\endgroup\$ – Vogel612 Mar 20 at 7:23
1
\$\begingroup\$

I'm also huge fan of recursion, and the best book on recursion I know is "Little Schemer". I highly recommend it! It looks "slow" and repetitive, but that's how you learn (at least this approach was great for me).

In my opinion it's hard to read code when you find pattern you didn't knew before. It takes a lot of time and is highly frustrating to figure out what's happening inside, and often you still don't fully get why it was written this way (and if it's even correct). So the best advise I can give is - learn how to write code, reading will come naturally. You know what you are looking for.

In recursion, most important part is - when to stop and what to do (return) in that case.

Your mystery function stops when:

  • y is nil (it returns nil) - first if or
  • first element of y is eql to x (it returns 0) - second if

It will also return logical "something and something" - the last line - but we will talk about it later.

From the above, we know that:

  • y should be some list, since it's user with car and cdr functions, and tested for empty list (null y)
  • x should be some atom, simple one, since it's compared to every element of y list with eql, which works fine with things like symbols and numbers, but not more complicated things like strings or lists

OK, we know what to pass to mystery functions (roughly). Now - what this last part with let and and do? Apparently let is used here to store result of recursive call only to speed thing up. It could also be written as:

(and (mystery x (cdr y))
     (1+ (mystery x (cdr y))))

We know what mystery function can return: nil or 0. Last thing to do is to analyse what and can return:

  • first argument if it evaluates to false
  • second argument otherwise.

As you can see there is no magical trick to help reading code. When you use some pattern (recursion in this case) long enough, you learn what are the important things to look for, and what are just common construction parts.

When you have some idea how function works, you can call it with some parameters just to verify your understanding, but I don't think you should begin with that. Pan and paper method can be a lot better, especially when you start with simple cases, like what will happen if I pass an empty list and empty list? Or zero and one element list? Calling function you don't know and observing results is called "black box testing" and is more hackerish activity. You have all the information you need - code of the function - so it's easier to read and reason about its behaviour.

When you stuck and don't know how to proceed, try to reformat the code. Rewrite the parts you understand. It might look silly and like wasting your time, but I find it helpfull.

If something is not clear, I'm happy to expand my answer, just post a comment :)

\$\endgroup\$
  • \$\begingroup\$ Thanks @rsm, very useful :) i got mystery after some thought, followed by, i confess, a little black box testing :) - a key realisation for me was that there are actually two base cases in this example: the nil case may never be reached. The second point I had to acclimatise to was exact behaviour of and in this procedural context. So to round this out, how might we describe or think about this particular type of recursion? My feeling is that mystery is somehow exploiting the fact that we recur exactly once per position; as one of its symmetries. Does that make sense? \$\endgroup\$ – mwal Mar 20 at 9:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.