[fr] more symmetry between push and pop -> [fr] cancelled

[hartrock]

[Update 2] Feature request ([fr]) cancelled.

There is a reason for not making (pop aList -1) as simple as (push elem aList -1): it is performance, which degrades for longer lists, because there is a pointer forwards from each cell to its next cell in the list, but not backwards. This has implications for pop back (because its predecessor has to be reached from the other list end), but not for push back: thanks to 'last element optimization' of keeping a pointer to last element in list.

So there is an asymmetry in the sense, that regarding performance it's better to leave the FIFO/LIFO choice at pushers side, which is visible in making (or leaving) the less performant variants more difficult to use.

Nevertheless there may be usecases for the cpop/em-cpop macros (see link in previous update).



[Update] See http://www.newlispfanclub.alh.net/forum/viewtopic.php?f=16&t=4732#p23319">//http://www.newlispfanclub.alh.net/forum/viewtopic.php?f=16&t=4732#p23319 for better and more general macro code.

[*] On one side push is robust, if pushing into s symbol set to nil: it creates an empty list then, and ignores some given index just in this special case.

[*] On the other side pop always expects a list, no one will be created, if there is none (together with ignoring a given ix then).

[/list]
But this is not the problem for FIFO functionality: this would be solved by some more symmetrie between push and pop at another place.




 

[*] (pop '() -1)) and (pop '() 0)

    as valid expression returning nil; this corresponds to

 

[*] (push "foo" '() 0) and (push "foo" '() -1)

    , which is working now.

[/list]

[*] More more symmetry would be reached by creating an empty list for pop'ing from a nil symbol value, just as for push (ignoring any given ix and returning nil in this case).

[/list]
Interesting to note, that

Code Select Expand

(push '() 1)
does not work; pushing to an empty list only works for indices 0 and -1. It could be better for detecting coding errors, if the indices would be limited to 0 and -1 as in the nil symbol value case (should be the same for pop after 'more more symmetry' then).





It is clear, that changing the semantics of push and/or pop could break some legacy code; so such a change would likely deserve a greater version number increase.




;; define some things
(macro (push-top    E L) (push E L  ))
(macro (push-bottom E L) (push E L -1))
(macro (pop-top     L) (pop L  ))
(macro (pop-bottom  L) (pop L -1))
;; repair by:
(macro (pop-bottom-repaired L) (if (> (length L) 0) (pop L -1)))

(define (doIt num_push push_op_sym num_pop pop_op_sym)
  (print (format "%45s" (string "push_op: " push_op_sym ", pop_op: " pop_op_sym)))
  (set 'l '()
       'push_op (eval push_op_sym)
       'pop_op (eval pop_op_sym))
  (dolist (e (sequence 1 num_push))
          (eval (push_op e l)))
  (print "; after push_op: " l)
  (print "; pop:")
  (dotimes (i num_pop)
           (print " " (eval (pop_op l))))
  (println))
[/code]

There has been the following session:

Code Select Expand


newLISP v.10.6.4 64-bit on OSX IPv4/6 UTF-8 libffi, options: newlisp -h

> ;;
> ;; this works:
> ;;
> (doIt 3 'push-top 3 'pop-top) ; LIFO
           push_op: push-top, pop_op: pop-top; after push_op: (3 2 1); pop: 3 2 1
nil
> (doIt 3 'push-bottom 3 'pop-bottom) ; LIFO
     push_op: push-bottom, pop_op: pop-bottom; after push_op: (1 2 3); pop: 3 2 1
nil
> (doIt 3 'push-bottom 3 'pop-top) ; FIFO
        push_op: push-bottom, pop_op: pop-top; after push_op: (1 2 3); pop: 1 2 3
nil
> (doIt 3 'push-top 3 'pop-bottom) ; FIFO
        push_op: push-top, pop_op: pop-bottom; after push_op: (3 2 1); pop: 1 2 3
nil
> ;;
> ;; but this fails, if 'pop-bottom is trying to pop from an empty list:
> ;;
> (doIt 3 'push-top 4 'pop-top) ; LIFO
           push_op: push-top, pop_op: pop-top; after push_op: (3 2 1); pop: 3 2 1 nil
nil
> (doIt 3 'push-bottom 4 'pop-bottom) ; LIFO
     push_op: push-bottom, pop_op: pop-bottom; after push_op: (1 2 3); pop: 3 2 1
ERR: invalid list index in function pop
called from user function (doIt 3 'push-bottom 4 'pop-bottom)
> (doIt 3 'push-bottom 4 'pop-top) ; FIFO
        push_op: push-bottom, pop_op: pop-top; after push_op: (1 2 3); pop: 1 2 3 nil
nil
> (doIt 3 'push-top 4 'pop-bottom) ; FIFO
        push_op: push-top, pop_op: pop-bottom; after push_op: (3 2 1); pop: 1 2 3
ERR: invalid list index in function pop
called from user function (doIt 3 'push-top 4 'pop-bottom)
> ;;
> ;; using repaired version: voila!
> ;;
> (doIt 3 'push-top 4 'pop-top) ; LIFO
           push_op: push-top, pop_op: pop-top; after push_op: (3 2 1); pop: 3 2 1 nil
nil
> (doIt 3 'push-bottom 4 'pop-bottom-repaired) ; LIFO
push_op: push-bottom, pop_op: pop-bottom-repaired; after push_op: (1 2 3); pop: 3 2 1 nil
nil
> (doIt 3 'push-bottom 4 'pop-top) ; FIFO
        push_op: push-bottom, pop_op: pop-top; after push_op: (1 2 3); pop: 1 2 3 nil
nil
> (doIt 3 'push-top 4 'pop-bottom-repaired) ; FIFO
push_op: push-top, pop_op: pop-bottom-repaired; after push_op: (3 2 1); pop: 1 2 3 nil
nil
>


Triggered by this code (for copy/paste at once):

Code Select Expand


;;
;; this works:
;;
(doIt 3 'push-top 3 'pop-top) ; LIFO
(doIt 3 'push-bottom 3 'pop-bottom) ; LIFO
(doIt 3 'push-bottom 3 'pop-top) ; FIFO
(doIt 3 'push-top 3 'pop-bottom) ; FIFO
;;
;; but this fails, if 'pop-bottom is trying to pop from an empty list:
;;
(doIt 3 'push-top 4 'pop-top) ; LIFO
(doIt 3 'push-bottom 4 'pop-bottom) ; LIFO
(doIt 3 'push-bottom 4 'pop-top) ; FIFO
(doIt 3 'push-top 4 'pop-bottom) ; FIFO
;;
;; using repaired version: voila!
;;
(doIt 3 'push-top 4 'pop-top) ; LIFO
(doIt 3 'push-bottom 4 'pop-bottom-repaired) ; LIFO
(doIt 3 'push-bottom 4 'pop-top) ; FIFO
(doIt 3 'push-top 4 'pop-bottom-repaired) ; FIFO


[Lutz]

Up to version 9.2.11 when indexing lists, indices too big would pick the last element and indices to small or to negative would pick the first element in a list. For empty lists the result would be nil in a consistent fashion, e.g for pop, nth, first, last etc..



In programming practice this often caused undetected programming errors and it was decided to flag all index overruns as an error starting with version 9.2.12 in January 2008.

[hartrock]

Up to version 9.2.11 when indexing lists, indices too big would pick the last element and indices to small or to negative would pick the first element in a list. For empty lists the result would be nil in a consistent fashion, e.g for pop, nth, first, last etc..



In programming practice this often caused undetected programming errors and it was decided to flag all index overruns as an error starting with version 9.2.12 in January 2008.

Agreed: to be restrict is good for detecting programming errors.



But what do you think about my proposal of allowing (pop '() 0) and (pop '() -1) (for empty lists) returning nil?

This would give some symmetry regarding LIFO/FIFO functionality (and the same indices for empty lists would be allowed for both pop and push).



nil pop'ing from an empty list from front or back seems to be reasonable to me (analogue to push in the other direction).



PS:

One difficulty is nil as element in lists, whose difference from an empty list cannot be detected by pop alone (as it is now for pop without ix (for implicit LIFO), so no change with my proposal).

PPS:

push currently is less picky as pop regarding ix'es with empty lists. But as well it is reasonablle to treat 0 and -1 as push'ing back/front, this could also be the case for pop.

PPPS: Currently push/pop-ing without indices means LIFO, this is implicitely using ix 0.; but explicitely using this ix works only for push.

PPPS:

The 'more more symmetry' idea could be dangerous regarding hiding of programming errors: trying of pop'ing from an unexistent list may be wrong. But the same applies for push now, which allows using a nil valued sym. Here I think, there are good reasons for both variants (comfort and denseness of code versus detecting programming errors); but it could be good to choose one of them for both push'n'pop (less to memorize amongst more 'symmetry' in code).



Hopefully my points are more clear now.

[Lutz]

You are making the point that push is an exception to the rule: flag 0, -1 on empty lists as errors. pop and everything else do flag this as error but push doesn't.



There is a frequent code pattern used where you build lists or queues by always pushing to the end using the -1 index to build queues. You are creating a 0 or -1 element position. Then using pop without index until empty?. If you do not allow pushing on on an empty list at -1, code gets complicated as the first element to push, now is a special case to be treated by code.



Basically we are having a https://en.wikipedia.org/wiki/Worse_is_better">https://en.wikipedia.org/wiki/Worse_is_better discussion here ;-)

[hartrock]

Let's give some additional perspective.

The pusher is feeding

the popper is eating,

both are using a queue

with LIFO;



but pusher may choose

poor popper has to loose,

to use this as a queue

with FIFO.

Prenote: here standard push/pop means, doing this without ix for back/front info; which has the well known and expected LIFO semantics, if both sides use this.



But the pusher has a choice: currently how to push decides, if standard poping has LIFO - pushing without or 0 ix - or FIFO - pushing with -1 ix - semantics.

On the other poper side there is no such choice after a standard push (without wrapper code around pop). If poping with -1 ix would be allowed, this choice could also be made afterwards by poper side, after a standard push without ix.



There has been a usecase, which has led to this thread: providing a standard push without any side argument (back or front), followed by a decision of the poper how to fetch elements from this queue.



Currently I don't see a problem with providing this additional symmetry regarding the choice of LIFO/FIFO semantics:

[*] choice how to push with standard pop (already provided), versus

[*] standard push with choice how to pop (missing).

[/list]

PS:

A variation of this is to introduce push-back and pop-back for the to/from back cases - both together used standard again leads to LIFO like for standard push/pop; a mixture between old and new to FIFO (problematic here could be possible confusion with indices counting backwards in the non-standard case (which would be consequent for the -back variants)).

This would have the advantage of the same code structure for FIFO as well as for LIFO cases, at the cost of two more symbols.

[hartrock]

There is a frequent code pattern used where you build lists or queues by always pushing to the end using the -1 index to build queues. You are creating a 0 or -1 element position. Then using pop without index until empty?. If you do not allow pushing on on an empty list at -1, code gets complicated as the first element to push, now is a special case to be treated by code.

This is the FIFO use case with choosing it at push side: it's good to have this choice.

There is the other FIFO use case with choosing it at pop side: it would be nice to have this choice, too.

Basically we are having a https://en.wikipedia.org/wiki/Worse_is_better">https://en.wikipedia.org/wiki/Worse_is_better discussion here ;-)

Thanks for the pointer: this may be ;-)

[abaddon1234]

Maybe you can try the Benchmark and tell us the result.

http://thgclub.blogspot.com/2016/04/gclub_29.html">gclub บาคาร่า

[rickyboy]

Maybe you can try the Benchmark and tell us the result.

WTF?  Did you even read this thread?  (The last question is rhetorical of course.)

http://thgclub.blogspot.com/2016/04/gclub_29.html">gclub บาคาร่า

The admin of this forum needs to ban this user (abaddon1234).  All this user ever does is blindly respond to posts -- usually with a mere "Thanks" -- and then *always* posts the above-quoted URL of a Thai on-line casino.  It's been going on for many weeks, and I was going to give it some time to see if this person would simply go away after a few posts, but instead they continue -- I'm getting tired of this



Please delete this user for abuse.  Thanks.