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

Q&A's, tips, howto's
Locked
hartrock
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

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

Post by 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 viewtopic.php?f=16&t=4732#p23319 for better and more general macro code.

Starting point
By coding something with FIFOs and LIFOs, I've seen some 'asymmetries' between push and pop, which led to a macro repairing them. Not really a serious problem (thanks to the flexibility of newLISP), but nevertheless this possibly could be better...

Differences between push and pop
There are big differences between push and pop:
  • 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).
But this is not the problem for FIFO functionality: this would be solved by some more symmetrie between push and pop at another place.

More symmetry
  • Some more symmetry between push and pop could be reached by the following:
    define both
    • (pop '() -1)) and (pop '() 0)
      as valid expression returning nil; this corresponds to
    • (push "foo" '() 0) and (push "foo" '() -1)
      , which is working now.
  • 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).
Interesting to note, that

Code: Select all

(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).

Postfix:
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.

How I've come to these suggestions
There has been a need for macro

Code: Select all

(macro (pop-bottom-repaired L) (if (> (length L) 0) (pop L -1)))
Why? Let's give an example.

After calling newlisp with this code:

Code: Select all

;; 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))
There has been the following session:

Code: Select all

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 all

;;
;; 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
Last edited by hartrock on Tue Aug 11, 2015 4:02 pm, edited 2 times in total.

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: [fr] more symmetry between push and pop

Post by 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
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

Re: [fr] more symmetry between push and pop

Post by hartrock »

Lutz wrote: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
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: [fr] more symmetry between push and pop

Post by 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 discussion here ;-)

hartrock
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

Re: [fr] more symmetry between push and pop

Post by hartrock »

Let's give some additional perspective.
update some hours later wrote: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).
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.
Last edited by hartrock on Wed Aug 05, 2015 8:03 am, edited 2 times in total.

hartrock
Posts: 136
Joined: Wed Aug 07, 2013 9:37 pm

Re: [fr] more symmetry between push and pop

Post by hartrock »

Lutz wrote: 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.
Lutz wrote: Basically we are having a https://en.wikipedia.org/wiki/Worse_is_better discussion here ;-)
Thanks for the pointer: this may be ;-)

abaddon1234
Posts: 21
Joined: Mon Sep 14, 2015 3:09 am

Re: [fr] more symmetry between push and pop -> [fr] cancelle

Post by abaddon1234 »

Maybe you can try the Benchmark and tell us the result.
gclub บาคาร่า

rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: [fr] more symmetry between push and pop -> [fr] cancelle

Post by rickyboy »

abaddon1234 wrote: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.)
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.
(λx. x x) (λx. x x)

Locked