Newsgroups: comp.lang.scheme
Date: Sat, 1 Dec 2018 17:57:29 -0800 (PST)
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=74.73.44.58; posting-account=axAvqQoAAADT1AGxSwQmJa832U07xnMn
NNTP-Posting-Host: 74.73.44.58
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <fa05f414-95b5-430a-9a87-ae8fafdd63f1@googlegroups.com>
Subject: A dreadful discovery about variadic recursive procedures
From: John Cowan <johnwcowan@gmail.com>
Injection-Date: Sun, 02 Dec 2018 01:57:29 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 46

It was worked out on #scheme this weekend that some harmless-looking Scheme functions that appear to have linear behavior actually have quadratic behavior.  Here is an example:

(define (plus x . xs)
  (if (null? xs)
    x
    (+ x (apply plus xs))))

[Yes, I know that + is already variadic and handles zero arguments nicely. That isn't the point.  This version is not tail recursive, which is not the point either.]

This procedure *seems* to be linear in the number of arguments.  However, all Scheme standards require that a variadic function be passed a *freshly allocated* list of the values with which it was called, and at least a large number of Scheme implementations are in fact conformant.  (This feature is probably to prevent trouble if the callee mutates the list it is passed.)

Therefore, at each step of the recursion, (apply plus xs) makes a shallow copy of xs.  This O(n) behavior is performed n times, making the procedure quadratic.

The simplest resolution is this:

(define (plus x . xs) (safe-plus x xs)

(define (safe-plus x xs)
  (if (null? xs)
  x
  (+ x (safe-plus (car xs) (cdr xs)))))

For what it's worth, the Common Lisp standard allows implementations not to make this copy when a function is invoked via APPLY, but tests show that at least abcl, ccl, ecl, and sbcl actually do make the copy; clisp makes a copy in some circumstances only.

Be warned.

-- 
John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
If I have seen farther than others, it is because they are closer than
I am. --Noetica
Noetica’s standing on the shoulders of galahs.  --Gibbon
Better than standing on the shoulders of hobyahs (not to be confused
with hobbits, though some have done so).  --me

Namely, clisp copies when interpreting, and doesn't copy when the function is compiled.