CLISP Hangs on Code from Page 147

[Brian144]

Greetings,

        I'm a total Lisp novice just settling down with Land of Lisp.  I'm running CLISP 2.41 under Windows XP.   I get inconsistent results when I run t I run this example function from page 147.

(defun ingredients (order)
    (mapcan (lambda (burger)
        (case burger
            (single '(patty))
            (double '(patty patty))
            (double-cheese '(patty patty cheese))))
        order))

        Many times the function will return the list I'm expecting but often CLISP just hangs.  Pressing Control-C will bring the REPL back to life.  I think I have the example copied accurately and I'm unaware of anything in this code that could cause an infinite loop.  In my brief experience with Lisp this is the first time I've had a function not promptly return some value or an error message due to either a syntax or logical error on my part.

       I'm not able to predict which which calls to ingredients or which what kind of parameter list will reliably cause or not cause this problem.

       Please do let me know if I've overlooked something important.

[Conrad]

Hi Brian:

I can't see any good reason why the code would hang in this way- The code you posted looks correct, and the fact that it works for you sometimes and not others is unusual- It points to something being wrong with your PC or your CLISP installation, but there might be some other way to explain this that I'm missing...

[Brian144]

Conrad,

        Thanks for getting back to me so quickly.  I should hasten to add that Land of Lisp is a jewel of a book!

         I seem to have the same trouble with the ingredients function even if I use CLISP 2.49 on my XP computer.  I've also been able to reproduce the problem  with Clisp 2.49 under Ubuntu, using a different computer.  

[Brian R. Russell]

Hey Peter,

Thanks for your suggestion. I don't think it's a question of
my omitting a parentheses. I've tried typing it directly into the
REPL, I've pasted it in from my PDF version of the book. I've studied
in in emacs to make sure I have balanced parentheses. I've pasted it
into an email message so I could use the "Paste Without Formatting"
option in case there were some non printing characters sneaking in and
running amok.

Here is a copy of a CLISP session in progress. I've again
copied the code from the Land Of Lisp pdf file, then pasted that into
the REPL. The first three calls to the ingredients function work just
great. The fourth call seems to hang the REPL. At this point I left
my computer unattended for a bit. When I returned there was a pop from
my Norton Anti-Virus software "High CPU Usage: Lisp.exe" I've seen
this before but I don't see it every time.

Here is my session:

[7]> (defun ingredients (order)

(mapcan (lambda (burger)
(case burger
(single '(patty))
(double '(patty patty))
(double-cheese '(patty patty cheese))))
order))

INGREDIENTS
[8]> (ingredients '(single))
(PATTY)
[9]> (ingredients '(double))
(PATTY PATTY)
[10]> (ingredients '(double-cheese))
(PATTY PATTY CHEESE)
[11]> (ingredients '(single single))

*** - Ctrl-C: User break
The following restarts are available:
ABORT :R1 ABORT
Break 1 [12]>


In this session I managed to exercise every branch in the "case
" call before the function stopped responding. That doesn't PROVE it's
not a syntax problem, but I'm beginning to think it isn't.

Never the less, Peter, thank you for taking a moment to help me
think about my problem.



On 12/11/2012 10:24 AM, Peter Frings wrote:
> Hi Brian,
>
> maybe it's a stupid suggestion, but I've had a similar problem, so maybe it can help...
>
> Did you enter that function directly in the repl? If the expression is not properly closed (e.g., missing last paren), the repl will wait for you to finish the sexp, and that looks like it's hanging...
>
> Just trying...
> Peter.
>
>

[Peter Frings]

[Mauricio]

I'm a little late, but I was able to reproduce the error Brian saw, using SLIME when the debugger pops up it tells me a circular reference is being created, I think it has to do with the fact that I used a repeated burger in the list, but anyway when you create a list it allocates memory the first time but later tries to reuse it, this creates the illusion of a neverending list, which will stuck CLISP.

I don't think is a bug, I would like to try it on other common lisps like SBCL and see if the error is also present there, I also would like to try CLISP on Linux, and see if I can reproduce the error there.

I also compiled and unassembled the code in clisp, however did not see anything obvious that could produce an infinite loop, so I'm betting for the circular reference.

[Mauricio]

I don't know if anybody is paying any attention to this posts anymore, anyway, I used CCL with the code in question and it also runs fine the first time and hangs from there on.

If I'm interpreting the disassembled code correctly the case is creating a hash structure which is closed over (The function with an internal lambda forms a closure), so every time a single, double or double-cheese is summoned the link to it is used, creating a circular reference.

I may be wrong but it would explain the failure, and the fact that different common lisps work the same, in other words is not a bug, I would try redoing the case with nested IFs and see if that works better.

[Brian R. Russell]

        Mauricio,

        Thank you for taking the time to investigate this issue and report back to the group. As I mentioned in my original post on this thread I am a complete LISP novice, so I hope you'll bear with me if some of my questions seem naive.

        Is it normal to examine disassembled code from a Lisp function and find that the compiler has created a closure that has no obvious counterpart in the source code?   You say this is not a bug, but it seems reasonable to assume that an unintended closure could case quite a bit of damage inside a program.  Is it possible that this is, in fact, a bug and you are able to reproduce it in multiple Lisp implementations  because there is some common code between these implementations? 

        I"m a little unclear about your reference to a hash table.  Not sure if the hash table is an alternative representation of the list the function is supposed to return or if the hash table is an editorial decision the compiler came up with as an substitute for some other attribute of the function. 

       Again, Mauricio, I did want to thank you for taking the time to help me think about this issue.

[Mauricio]

Hi Brian,

As you say an unintended closure is indeed a problem. I was reading a bit more about CASE in Common LISP the Language 2nd Edition, which is the basis of the whole standard, and which you can read online. As it turns out CASE is a macro, the documentation says how it should behave but not how it should be implemented ( http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node84.html ) , since CCL and CLISP are open source you can find the definition of the macros in the distribution (provided you downloaded the source code).

The macro in CCL looks like this:

(defmacro case (key &body forms)

  "CASE Keyform {({(Key*) | Key} Form*)}*

  Evaluates the Forms in the first clause with a Key EQL to the value of

  Keyform. If a singleton key is T then the clause is a default clause."

   (let ((key-var (gensym)))

     `(let ((,key-var ,key))

        (declare (ignorable ,key-var))

        (cond ,@(case-aux forms key-var nil nil)))))

  
Which depends on the definition of case-aux which I´m not going to reproduce but it expands into a list that is used as the body of the cond at the end of the macro definition. So the case macro will expand into an equivalent cond. Something similar to this:

(let (b burger) 

  (cond ((eq b 'single) ('(patty)))

((eq b 'double) ('(patty patty)))

((eq b 'double-cheese) ('(patty patty cheese))))

Which would produce something similar to the following code:

(defun ingredients (order)

  (mapcan (lambda (burger)

   (let ((b burger)) 

     (cond ((eq b 'single) '(patty))

   ((eq b 'double) '(patty patty))

   ((eq b 'double-cheese) '(patty patty cheese)))))

   order)) 

which believe it or not behaves exactly the same as the case, that is it works the first time but not the second, cond is also a macro, which basically in CCL expands into a series of nested ifs.

(defmacro cond (&rest args &aux clause)

  (when args

     (setq clause (car args))

     (if (cdr clause)         

         `(if ,(car clause) (progn ,@(cdr clause)) (cond ,@(cdr args)))

       (if (cdr args) `(or ,(car clause) (cond ,@(cdr args)))

                      `(values ,(car clause))))))

I have not gotten further into the problem from here on, but my closure/hash theory is wrong, but I´m not yet sure what is happening, using cond defmacro we could try to expand it and define it as the more primitive to see if it still fails. of if there is something wroing with the expansion, but so far it does not seem like it should be failing.

I think probably some CCL or CLISP developer would be able to throw some light on this faster than what I'm doing, I am not expert and it is been an interesting but slow process for me to investigate this. (I'm not expert myself).

[Mauricio]

Finally here is an apropriate explanation of the hang in that code.

 

I consulted in the IRC with far more experienced LISP programmers, and turns out this example is badly written, there is no bug, is just that mapcan uses nconsc. If you look at the hyperspect it tells you that:

 

 (mapcan f x1 ... xn)
   ==  (apply #'nconc (mapcar f x1 ... xn))

 

nconsc is a destructive operation, that is it gives you the right answer but it changes the first list which is the one in the case, thus changing the code itself, at each pass, so at the end the code no loger works because the lists it generates for each case have been changed, most likely with circular references as http://www.lispworks.com/documentation/HyperSpec/Body/f_nconc.htm#nconc warns.

 

By substituting the nconc with an append (which is the non destructive counterpart) in the mapcan equivalent above I came out with:

 

(defun ingredients1 (order)
  (apply #'append (mapcar (lambda (burger)

       (case burger
         (single '(patty))
         (double '(patty patty))
         (double-cheese '(patty patty cheese))))

     order)))

 

Which works correctly every time. There is no bug, just non compliant use of the mapcan function by our friend Conrad, I never looked at the mapcan itself, I assumed there was something wrong with the case, that is why I did not understand it before.

[Brian R. Russell]

        Wow, Mauricio!   Thanks for your detective work.  I've been merrily abusing your revised ingredients function which seems robust for all input lists with lengths of under 4,000 elements.   Much larger than that apply complains that there are too many parameters being passed to append. But the function never hangs.

        In light of what you've uncovered, I'm surprised no one has noticed this behavior before.  For my part I should probably review the hyperspec to get some feeling of when to use apply, and the map* functions, which I tend to confuse.

        Thank you, again, Mauricio, for your assistance with my questions   Much appreciated!

        Wishing you a joyful and Lispy New Year!.