Topic: Stack functions - Push/Pop/Roll - needed

[mkweaver]

I'm looking for a few data stack routines - specifically push, pop, rollup and rolldown.  I did a google search and got a fair number of hits for common lisp, but nothing for lisp.

I have put together the following but am open to suggestions:

Code: [Select]

  (defun ListRollUp(lst /)
    ;;'(1 2 3) becomes (3 1 2)
    (cons (car(reverse lst)) (reverse (cdr (reverse lst))))
    )


  (defun ListRollDown(lst / )
    ;;'(1 2 3) becomes (2 3 1)
    (reverse (cons (car lst) (reverse (cdr lst))))
    )

Any suggestions are welcome.

Mike

[irneb]

Perhaps for push, pop & peek:

Code - Auto/Visual Lisp: [Select]

1. (defun ListPush (lst item / )
2.   (cons item lst))
3.  
4. ;;; Use by quoting the list, e.g.
5. ;;; (setq lst '(1 2 3))
6. ;;; (setq item (ListPop 'lst))
7. ;;; Now item=1 and list=(2 3)
8. (defun ListPop (lst / item)
9.   (setq item (car (eval lst)))
10.   (set lst (cdr (eval lst)))
11.   item)
12.  
13. ;;; Rather trivial!
14. (defun ListPeek (lst)
15.   (car lst))

Unfortunately we don't have the setf function in AutoLisp - otherwise the pop would be a lot simpler.

[irneb]

Or a destructive implementation (the stack needs to be quoted for each function):

Code - Auto/Visual Lisp: [Select]

1. (defun stack:push (stack item) (set stack (cons item (eval stack))))
2.  
3. (defun stack:pop (stack / tmp) (car (cons (car (setq tmp (eval stack))) (set stack (cdr tmp)))))
4.  
5. (defun stack:peek (stack) (car (eval stack)))
6.  
7. (defun stack:rollup  (stack / tmp)
8.   (set stack (cons (car (setq tmp (reverse (eval stack)))) (reverse (cdr tmp)))))
9.  
10. (defun stack:rolldown  (stack / tmp)
11.   (set stack (append (cdr (setq tmp (eval stack))) (list (car tmp)))))

Edit: RollDown was implemented incorrectly - changed  :-[

[Lee Mac]

Some variations:

Code - Auto/Visual Lisp: [Select]

1. (defun push ( x l )
2.     (cons x l)
3. )
4. (defun pop ( l )
5.     (cdr l)
6. )
7. (defun rollup ( l )
8.     (cons (last l) (reverse (cdr (reverse l))))
9. )
10. (defun rolldown ( l )
11.     (append (cdr l) (list (car l)))
12. )

[roy_043]

@ irneb:
Your (stack:pop) function (reformatted for clarity):

Code - Auto/Visual Lisp: [Select]

1. (defun stack:pop (stack / tmp)
2.   (car
3.     (cons
4.       (car (setq tmp (eval stack)))
5.       (set stack (cdr tmp))
6.     )
7.   )
8. )

Why not:

Code - Auto/Visual Lisp: [Select]

1. (defun stack:pop (stack / tmp)
2.   (set stack (cdr (setq tmp (eval stack))))
3.   (car tmp)
4. )

@ Lee:
Your (pop) does not return the popped item...

[Lee Mac]

@ Lee: Your (pop) does not return the popped item...

Sorry, I was unaware of the standard behaviour of these functions... I will revise 

[Kerry]

The push and pop I use work with a quoted list.
This allows the popped value to be returned AND have the original list value modified.

Code - Auto/Visual Lisp: [Select]

1.  
2. ;;;------------------------------------------------------------------
3. ;;;------------------------------------------------------------------
4. ;;;
5. ;;; push first element into quoted list
6. ;;; example :
7. ;;;  (setq tmp_list '( ) )
8. ;;;  (setq tmp_list (KDUB:LIST-pUSH "teststring" 'tmp_list ))
9. ;;;                  ==>  ("teststring")
10. ;;;  (setq tmp_list (KDUB:LIST-pUSH (getvar "CMDECHO") 'tmp_list ))
11. ;;;                  ==> (1 "teststring")
12. ;;;  (setq tmp_list (KDUB:LIST-pUSH (cons "BLIPMODE" (getvar "BLIPMODE")) 'tmp_list ))
13. ;;;                  ==> (("BLIPMODE" . 0) 1 "teststring")
14. ;;;  (setq tmp_list (KDUB:LIST-pUSH (cons "EXPERT" (getvar "EXPERT")) 'tmp_list ))
15. ;;;                  ==> (("EXPERT" . 2) ("BLIPMODE" . 0) 1 "teststring")
16.  
17. (defun kdub:list-push (push_value quoted_lstsym)
18.   (set quoted_lstsym (cons push_value (eval quoted_lstsym)))
19. )
20. ;;;------------------------------------------------------------------
21. ;;;------------------------------------------------------------------
22. ;;;
23. ;;; pop first element permenantly from quoted list
24. ;;; and return this element's value
25. ;;; example :  using previuusly set tmp_list
26. ;;;  (KDUB:list-pop 'tmp_list)  ==> ("EXPERT" . 2)
27. ;;;             tmp_list now= (("BLIPMODE" . 0) 1 "TESTSTRING")
28.  
29. (defun kdub:list-pop (quoted_lstsym / tmp)
30.   (setq tmp (eval quoted_lstsym))
31.   (set quoted_lstsym (cdr tmp))
32.   (car tmp)
33. )
34.  
35.  
36. ;;;------------------------------------------------------------------
37. ;;;------------------------------------------------------------------

[Keith™]

@ Lee: Your (pop) does not return the popped item...

Sorry, I was unaware of the standard behaviour of these functions... I will revise 

In c++ pop does not return the item off the stack, although it could be written to do that.

[Lee Mac]

In c++ pop does not return the item off the stack, although it could be written to do that.

An attempt to imitate C++ (I have almost no experience in C++, does it show?  )

Code - Auto/Visual Lisp: [Select]

1. ;; http://www.cplusplus.com/reference/stl/stack/push/
2. ;; (setq lst '(0 1 2 3 4 5))
3. ;; (stack::push 6 'lst) ==> lst = (6 0 1 2 3 4 5)
4. (defun stack::push ( x *stack* )
5.     (set *stack* (cons x (eval *stack*)))
6.     (princ)
7. )
8.  
9. ;; http://www.cplusplus.com/reference/stl/stack/pop/
10. ;; (setq lst '(0 1 2 3 4 5))
11. ;; (stack::pop 'lst) ==> lst = (1 2 3 4 5)
12. (defun stack::pop ( *stack* )
13.     (set *stack* (cdr (eval *stack*)))
14.     (princ)
15. )
16.  
17. ;; http://www.cplusplus.com/reference/stl/stack/top/
18. ;; (setq lst '(0 1 2 3 4 5))
19. ;; (stack::top 'lst) ==> 0
20. (defun stack::top ( *stack* )
21.     (car (eval *stack*))
22. )
23.  
24. ;; http://www.cplusplus.com/reference/stl/stack/size/
25. ;; (setq lst '(0 1 2 3 4 5))
26. ;; (stack::size 'lst) ==> 6
27. (defun stack::size ( *stack* )
28.     (length (eval *stack*))
29. )
30.  
31. ;; http://www.cplusplus.com/reference/stl/stack/empty/
32. ;; (setq lst '( ))
33. ;; (stack::empty 'lst) ==> T
34. (defun stack::empty ( *stack* )
35.     (null (eval *stack*))
36. )

[Kerry]

Stating the obvious : each language may have a different implementation.

C# and VB.net
Stack.Pop Method
Removes and returns the object at the top of the Stack.
Stack.Pop is similar to the Peek method, but Peek does not modify the Stack.

[Keith™]

Stating the obvious : each language may have a different implementation.

C# and VB.net
Stack.Pop Method
Removes and returns the object at the top of the Stack.
Stack.Pop is similar to the Peek method, but Peek does not modify the Stack.

Absolutely ...

I had some extensive discussion with some folks about why C++ does not return the value on pop, and the reason I was given by most was that the C++ stack deals with pointers and when the stack is empty, pop does nothing. Popping an empty stack with a return value thus should return nil in lisp.

[Kerry]

< .. >
 Popping an empty stack with a return value thus should return nil in lisp.

 Some do

Code - Auto/Visual Lisp: [Select]

1. (setq empty_list '())
2.  
3. (setq result (kdub:list-pop 'empty_list))
4.  
5. ;;result == nil
6.  

[irneb]

@ irneb:
Why not:

Code - Auto/Visual Lisp: [Select]

1. (defun stack:pop (stack / tmp)
2.   (set stack (cdr (setq tmp (eval stack))))
3.   (car tmp)
4. )

Thanks yes ... that's probably a better implementation 
 
 

In c++ pop does not return the item off the stack, although it could be written to do that.

It seems correct for only C++ http://www.cplusplus.com/reference/stl/stack/
 
 Though from my experience all the other languages I've come across returns the head item after removing it from the list/array (whichever implementation it's using). Basically the same manner as here (compared in C/C++/Java): http://www.cs.utsa.edu/~wagner/CS2213/stack/stack.html
 
 As for poping off an empty stack ... 2 options: (1) return null, (2) throw exception. Depends on how you implement the stack, probably you'd have to use a linked-list / array of pointers (or extend one of the collection classes if such exists in your language).
 
 Actually in Lisp such things as queues and stacks are already "implemented" ...
 http://www.lispworks.com/documentation/HyperSpec/Body/m_pop.htm#pop
 And for the roll's:

Code - Lisp: [Select]

1. (defmacro stack-rolldown (stack)
2.    `(setf ,stack (append (cdr ,stack) (list (car ,stack)))))
3.  
4.  (defmacro stack-rollup (stack)
5.    `(setf ,stack (append (last ,stack) (butlast ,stack))))

Seems to work here:

Code: [Select]

ECL-0.9i % (defparameter st (list 1 2 3))
 ST
 ECL-0.9i % st
 (1 2 3)
 ECL-0.9i % (stack-rolldown st)
 (2 3 1)
 ECL-0.9i % st
 (2 3 1)
 ECL-0.9i % (stack-rollup st)
 (1 2 3)
 ECL-0.9i % st
 (1 2 3)

[mkweaver]

Thanks for all the examples and discussion.  Good food for thought.

I guess I hadn't considered quoting the incoming list so the routine could modify it.  That's a much better approach than where I was headed.

Mike