Lisp loop macro, pop macro and memory-CodePudding

I'm learning lisp and and implemented a nested array parses, so that:

"[1,[2,[3,[4,[5,6,7]]]],8,9]" -> '(1 (2 (3 (4 (5 6 7)))) 8 9)

Online Code snippet here

This was my first implementation of parse-line

(defun parse-line (string)
     (loop 
          :for i = 0 :then (1  j)
          :for stack = (list nil)
          :as j = (position-if (lambda (c) (member c '(#\[ #\] #\,))) string :start i)
          :as n = (parse-integer string :start i :end j :junk-allowed t)         
          :when n :do (push n (car stack))
          :while j
          :do (cond
            ((eql #\[ (aref string j)) (push nil stack))
            ((eql #\] (aref string j)) (push (nreverse (pop stack)) (car stack))))
          :finally (return (car (pop stack))))
        ))

But it crashes on the stack pop.

;test-case        
(print (equal '(1 (2 (3 (4 (5 6 7)))) 8 9) (parse-line "[1,[2,[3,[4,[5,6,7]]]],8,9]")))

The value NIL is not of type CONS

I then brute-forced my way into a solution declaring stack with let outside the loop macro

(defun parse-line (string)
    (let ((stack (list nil)))
     (loop 
          :for i = 0 :then (1  j)
          :as j = (position-if (lambda (c) (member c '(#\[ #\] #\,))) string :start i)
          :as n = (parse-integer string :start i :end j :junk-allowed t)         
          :when n :do (push n (car stack))
          :while j
          :do (cond
            ((eql #\[ (aref string j)) (push nil stack))
            ((eql #\] (aref string j)) (push (nreverse (pop stack)) (car stack))))
          :finally (return (car (pop stack))))
        ))

But I can't see why the second implementation works.

I also can't see why I need to initialize stack with (list nil). I thought that initializing stack to nil and removing the final car should be equivalent but it crashes with the same error at the same place, ie:

(defun parse-line (string)
        (let (stack)
         (loop 
              :for i = 0 :then (1  j)
              :as j = (position-if (lambda (c) (member c '(#\[ #\] #\,))) string :start i)
              :as n = (parse-integer string :start i :end j :junk-allowed t)         
              :when n :do (push n (car stack))
              :while j
              :do (cond
                ((eql #\[ (aref string j)) (push nil stack))
                ((eql #\] (aref string j)) (push (nreverse (pop stack)) (car stack))))
              :finally (return (pop stack)))
            ))

CodePudding user response：

Look at these two lines in your first implementation:

:for i = 0 :then (1  j)
:for sack = (list nil)

There is a typo (sack -> stack), but even then it doesn't work, because with each new value of i, you will create a brand new stack, losing all previous values. Add some debug print to see, what's going on:

i:0 j:0 n:NIL stack:(NIL NIL)
i:1 j:2 n:1 stack:((1))
i:3 j:3 n:NIL stack:(NIL NIL)
i:4 j:5 n:2 stack:((2))
i:6 j:6 n:NIL stack:(NIL NIL)
i:7 j:8 n:3 stack:((3))
...

If you don't want to use let to initialize stack, you can use keyword :with:

(defun parse-line (string)
  (loop 
   :with stack = (list nil)
   :for i = 0 :then (1  j)
   :as j = (position-if (lambda (c) (member c '(#\[ #\] #\,))) string :start i)
   :as n = (parse-integer string :start i :end j :junk-allowed t)         
   :when n :do (push n (car stack))
   :while j
   :do  (cond
         ((eql #\[ (aref string j)) (push nil stack))
         ((eql #\] (aref string j)) (push (nreverse (pop stack)) (car stack))))
   :finally (return (car (pop stack)))))

You can use a similar debug print to see, why your code crashes with stack initialized to nil. This error can be reproduced with:

> (let ((stack '((9 8 (2 (3 (4 (5 6 7)))) 1))))
    (push (nreverse (pop stack)) (car stack)))

Error: NIL (of type NULL) is not of type CONS.

You can find some explanation for this behaviour here: Why I can't (push 3 '()) in Common Lisp's REPL?

CodePudding user response：

I would recommend using a Lisp compiler and using its warnings. SBCL gives this warning on your first form:

; in: DEFUN PARSE-LINE
;     (PUSH N (CAR STACK))
; 
; caught WARNING:
;   undefined variable: COMMON-LISP-USER::STACK
; 
; compilation unit finished
;   Undefined variable:
;     STACK
;   caught 1 WARNING condition

That would lead you to investigate why that is: why is STACK undefined?