In Lisp, how many inputs can the + function actually have?

Question

I'm relatively new to Lisp, and I was wondering if there really is an upper limit to the "+" function.

(I guess this applies to all the other arithmetic functions "-", "/" etc.)

Niels

Answer 1

Yes, there is an upper limit, but the exact upper limit is implementation-dependent. You're guaranteed to be able to pass at least 50, but it all depends. If you need to sum a list, you're probably better off with (reduce #'+ list), that should give you a much better scalability than any other method.

Common Lisp HyperSpec has some more info.

When it comes to value ranges there are two distinct cases, floats and integers. Floats are inherently limited by their size and an implementation that changed from single-floats to double-floats would surprise me a lot. With integers and rationals, CL seamlessly transition between fixnums and bignums, so the limit is a function of the usable address space available to the implementation. I suspect the same holds for complex numbers (complex integers and rationals -> go to bignums if needed; complex floats -> signal an out of range, or return an Inf or NaN).

Inspirit

That's what the spec says, but do you know of any implementations that actually enforce a limit? – Carbonation

@Carbonation Well, SBCL guarantees you a CALL-ARGUMENTS-LIMIT in the region of 10^18 and I would expect that passing more arguments that that simply would not work. I do not have any other implementaion trivially at hand, but I do recall reading about people having problems using APPLY instead of REDUCE with lists as short as "in the hundreds of elements". – Inspirit

@Inspirit I just realised that my title and question description contradict each other in their intended meanings. Since I think you are answering the value-limit of the "+" function, do you mind commenting on the limit of inputs that the function can have? Sorry for the confusion! – Niels

@Niels I'm pretty certain that he's talking about the number of inputs. – Carbonation

@Niels I think it's fair to say that he's proved me and Mark Hurd wrong on this. – Carbonation

@Carbonation Argh, sorry about that then. Hyperspec says "An integer not smaller than 50" so I was assuming that he was talking about the value of the inputs (and I guess, the function's output), and then I read "The upper exclusive bound on the number of arguments that may be passed to a function.". – Niels

Answer 2

Common Lisp has been defined in such a way that it could be implemented efficiently on a wide variety of hardware and software systems. Examples are processors like the Motorola 68000/20/30/40, the various Intel x86 processors, Lisp Machine stack-based processors, DEC VAX, RISC processors, super computers like those from Cray. In the 80s there were a lot of processor families competing, including processors developed for execution of Lisp code. Today we still have several processor families (x86, x86-64, ARM, SPARC, POWER, PowerPC, ...).

It can also be compiled to C, Scheme or other programming languages.

It can also be compiled to virtual machines like those of CMUCL, CLISP or the JVM / Java Virtual Machine (The Java Virtual Machine seems to have a limit of 254 arguments).

For example a Common Lisp compiler might compile Lisp code to straight-forward C code. Thus it would be good if as much of the function calling of the C compiler could be reused as possible. Especially also to make calling Lisp from C easier.

C/C++ has limits on that, too:

Maximum number of parameters in function declaration

Above gives numbers like 127 (C) and 256 for C++. So for a Lisp to C compiler these might be the limits. Otherwise the Lisp code would not use the C function calling.

The first such compiler KCL (Kyoto Common Lisp, later this implementation evolved into GCL / GNU Common Lisp and ECL / Embeddable Common Lisp) had a CALL-ARGUMENTS-LIMIT of 64.

A 64bit implementation of LispWorks / Mac OS X for example has a value of 2047 for CALL-ARGUMENTS-LIMIT.

CALL-ARGUMENTS-LIMIT should be no smaller than 50.

Thus in Common Lisp, list processing and calling arguments are not related. If you want to process lists, you have to use the list processing tools (LIST, MAPCAR, APPEND, REDUCE, ...). Common Lisp provides a mechanism to access the arguments as a list using a &RESTparameter. But that should usually be avoided, since it might cause function calling overhead because a list of the arguments need to consed.

Zymolysis

Answer 3

Clojure provides an example of a Lisp where you can actually have an infinite number of arguments to a function, via the use of lazy sequences:

; infinite lazy sequence of natural numbers
(def naturals (iterate inc 1))

(take 10 naturals)
=> (1 2 3 4 5 6 7 8 9 10)

; add up all the natural numbers 
(apply + naturals)
=> ...... [doesn't terminate]

Not particularly useful, of course.....

Jocelin

This example does not convince me. APPLY gets called with two arguments. That + gets called with infinite arguments is not clear. Maybe APPLY is busy BEFORE + gets called with infinite arguments. Given the example by @jwinandy showing Clojure to 'hang' at 8192 arguments, I would suspect the same happens here... – Zymolysis

Answer 4

It depends of the implementation. "I would suggest LISP users take 5 minutes to test their platform".

For Clojure

(defn find-max-n [n]
  (try 
    (eval (concat (list +) (take n (repeat 1))))
    (println "more than" n)
    ; return n if something goes wrong
    (catch Exception e n))
  (recur (* n 2)))


(find-max-n 1)

It doesn't terminate, it hangs at 8192 given my settings.

more than 1
more than 2
more than 4
more than 8
more than 16
more than 32
more than 64
more than 128
more than 256
more than 512
more than 1024
more than 2048
more than 4096
more than 8192

Merell

Answer 5

Simple answer, no, although a poor implementation using recursion and not tail recursion will have a stack limit.

Depending upon your implementation + may be implemented using recursion or as a straight function call.

I don't know Common Lisp well enough to know what requirements it specifies, but most implementations, if they use recursion, will use tail recursion and avoid any stack limits.

A function call will be able to access the arguments as a list and so there is no limit to the number of arguments that can be processed.

EDIT: Since someone has actually given a Common Lisp reference, it clearly should be a better answer, but I would have thought any good implementation would automatically apply the equivalent of (reduce #'+ arg-list) when enough arguments are supplied.

Samos

Common Lisps are generally not tail recursive. I have a feeling that I've read that there is a reason why they are not permitted to have tail-call optimisation (although, I may well be imagining that). – Carbonation

Also, there is no reason why an implementation would use recursion, given the availability of reduce and loop. – Carbonation

@Carbonation They are allowed to have tail-call optimization and most do, if you tweak your optimization variables (primarily "speed" high and "debug" low, but see your implementation's manual for specifics). – Inspirit

Note I am answering the question implied by the title of this question. The text could be seen to be asking is there a maximum value + can return. I do know one of Common Lisp's "claims to fame" is that it uses "large numbers" by default and so, if that was (part of) the question, no, every finite number of + arguments will produce a "large number" and not overflow. – Samos

I would have assumed that + would be implemented in much the same way you suggest. – Carbonation

@Marcin: I would have assumed that + would be implemented in the most efficient way as possible and that it does not involve arbitrary list processing. – Zymolysis

@RainerJoswig Why would you assume that when it takes an arbitrary number of arguments (up to the implementation-defined limit)? – Carbonation

@Marcin: since it has an upper limit, it is not arbitrary. – Zymolysis

@RainerJoswig Now you're just quibbling about the exact meaning of "arbitrary". Is that for any reason, or are you just trying to score a point in your mind? – Carbonation

@Marcin: the limit is there to allow efficient implementation on typical processors or on top of C compilers (using the C stack). Thus it is not arbitrary. – Zymolysis

@RainerJoswig An "arbitrary number" means a number that may be arbitrarily large, i.e. there is no upper bound on the value that it may take, although it must be finite, not a number chosen capriciously. – Carbonation