malloc error in append/mappend/k-permutations/Hansoncode

[cormullion]

I managed to get this - using code from that Rickyboy -

newlisp(28593) malloc: *** mmap(size=2097152) failed (error code=12)

*** error: can't allocate region

*** set a breakpoint in malloc_error_break to debug



ERR: not enough memory in function append

called from user defined function mappend

called from user defined function k-permutations

is this just the inevitable result of calling a recursive function too much? - it was only with 10 items, your honor... :)

[Lutz]

Your honor, defendant is clearly guilty of computer abuse.



Defendant also has subjected the environment to excessive heat emanating from his computer, before reaching catastrophic memory overflow.



We owe it to newLISP's error handling routines to interrupt the process before worse things could happen.



There are a total of 3,628,880 lists of 10 elements each, resulting from calculating all permutations without repetition from a 10 element list. 580,608,000 byte of memory would be necessary to hold the result, without counting the overhead required when using recursive routines.



I recommend a 256 hour suspension of defendant's newLISP usage license.



;-)

[newdep]

I recommend a 256 hour suspension of defendant's newLISP usage license.

Now thats a statement ! ;-)

[cormullion]

Your honor, my client maintains that he was recursing down the highway using code that he had borrowed in good faith from a well-regarded supplier and was unaware of the rapidity with which the physical limitations of his surroundings overwhelmed his modest circumstances. He appeals for clemency, and asks that the sentence be reduced to 12 hours suspension of the newLISP licence, and a promise to explore iterative solutions where practical.

[Lutz]

... that the sentence be reduced to 12 hours suspension of the newLISP licence, and a promise to explore iterative solutions where practical.

Granted.



Often recursive solutions confuse the programmer's mind, suggesting false elegance and simplicity while hiding dangerous waste of resources in CPU cycles and memory.

[rickyboy]

This writ of error coram nobis and amicus curiae brief is respectfully submitted on behalf of rickyboy, as amicus party, in support of the motion of judgment on the pleadings filed by Defendant cormullion.



Exhibits and Facts



A. There are at least two versions of the k-permutations computing function mentioned on the newLISP forum.  One is the original version at http://www.alh.net/newlisp/phpbb/viewtopic.php?t=553">//http://www.alh.net/newlisp/phpbb/viewtopic.php?t=553, and subsequently posted by this Honorable Court at http://www.newlisp.org/index.cgi?page=Code_Snippets">//http://www.newlisp.org/index.cgi?page=Code_Snippets.  The code will be repeated here and henceforth be called EXHIBIT A:

Code Select Expand

(define (make-k-permutations k multiset)
  (let ((pivots (unique multiset)))
    (if (= k 1)
        (map list pivots)
        (let ((acc '()))
          (dolist (p pivots)
            (let ((sub-multiset (remove1 p multiset)))
              (dolist (sub-perm
                       (make-k-permutations (- k 1) sub-multiset))
                (push (cons p sub-perm) acc))))
          acc))))

(define (remove1 elt lst)
  (let ((elt-pos (find elt lst)))
    (if elt-pos (pop lst elt-pos))
    lst))

B. Another is one which was a modification of an algorithm originally written by Fanda, an acknowledged quality supplier of algorithmic products.  Modifications were suggested by Defendant and amicus.  The effort was documented by posting at http://www.alh.net/newlisp/phpbb/viewtopic.php?t=2000">//http://www.alh.net/newlisp/phpbb/viewtopic.php?t=2000.  The modified algorithm is repeated now forthwith, and will be referred to as EXHIBIT B:

Code Select Expand

(define (k-permutations k multiset)
  (let ((pivots (unique multiset)))
    (if (= k 1)
        (map list pivots)
      (mappend (lambda (p)
                 (map (lambda (k-1-perm) (cons p k-1-perm))
                      (k-permutations (- k 1) (remove1 p multiset))))
               pivots))))


C. The offending function, used by Defendant, appeals to the mappend function, according to the error message Defendant received when attempting to compute 10-tuple permutations.



D. All programmers right to recurse is clearly established in Wirth [Algorithms + Data Structures = Programs. Prentice-Hall, Inc., 1975], Knuth [The Art of Computer Programming, Addison-Wesley, 1998], and Abelson, Sussman [Structure and Interpretation of Computer Programs, MIT Press, 1984].



E. As of this date, no iterative version of said algorithm has been exhibited to this Court, which utilizes space in lesser amounts than recursive algorithm EXHIBIT A.



F. Well respected figures favor recursive solutions over iterative ones.

   1. "Iterative solutions?!  How uncivilized!"  --Obi Won Kenobi

   2. "It's the recursion ... Chicks dig the recursion."  --Batman

   3. "Iteration is the world that has been pulled over your eyes to blind you from the Truth of Recursion."  --Morpheus

   4.  "Recursion goes all the way to 11!"  --Nigel Tuffnel



Argument



1. Clearly, Defendant was not using the original version of the k-permutations computation function, i.e. EXHIBIT A, for if he were, he would not have received an error message referring to the function mappend on the call stack.  Indeed, EXHIBIT A does not utilize function mappend, in any way.



2. It is possible, however, that Defendant could have reached for EXHIBIT B, which the Court will note, has reference to function mappend.



3. Amicus cannot make the precise determination that, in fact, Defendant did use EXHIBIT B (with the adverse effects).  However, and for the sake of the argument we will make in this very paragraph, we suppose then that Defendant indeed used EXHIBIT B, that is, that EXHIBIT B is the offending function in question.  Now, as of this day, amicus tested EXHIBIT A versus EXHIBIT B on time and space metrics on 9-tuple input, running on his MacBook Pro, wherein he received the following average statistics: EXHIBIT A took 9.247 seconds and 111.57MB/138.13MB real/virtual memory; EXHIBIT B took 17.2 seconds with use of 222.53MB/249.10MB real/virtual memory.  Hence, by the supposition, that is, under such circumstances, amicus recommends that any User cease to utilize EXHIBIT B in favor of EXHIBIT A.



4. Due process also requires this Court to acknowldge Defendant's basic right of recursion, as established in Fact D.



5. By Fact E, Defendant had no legal or computational recourse at his disposal, but to use any of the solutions offered by accredited suppliers of procedural solutions, i.e. EXHIBIT A and EXHIBIT B.  None of the authors of either procedure declaimed or declared fiduciary responsibility for said code, but rather they shared the code inter alios; hence, neither solution indemnifies Users, such as Defendant, from arbitrary space resource allocations, or other such adverse side-effects of the User's otherwise harmonious computing experience.  Hence, sentence commutation or leniency is in order.



6. Society's acceptance of recursion is clearly exhibited in Fact F, where leaders of important groups of society (e.g. the knighted, the law enforcement, the prophetical and the musical) testify to recursion's cultural refinement, truthful qualities, coolness and basic animal attraction.



Conclusion



Based on the foregoing, the amicus respectfully requests that the Court amend opinion of recursive solutions, with caveats and qualifiers deemed appropriate, before submitting it to the Court's record of opinion in finality.  Furthermore, amicus respectfully submits that the Court commute the current sentence of Defendant to eight (8) days, as sentences which are not powers of two, such as 12, could be construed as cruel and unusual punishment in jurisdictions of Binary authority.



Dated: May 27, 2008



RICKYBOY, Pro Se Petitioner

[Lutz]

Wow Rickyboy, if I ever have a legal problem with my code, I will consult with you ;-)

[m35]

wow...

[newdep]

Im getting the feeling I somewhere took the wrong door ;-)



hahahahaha...