Sono relativamente nuovo a Lisp e mi chiedevo se esiste davvero un limite superiore alla funzione "+".In Lisp, quanti ingressi può avere effettivamente la funzione +?
(credo che questo vale per tutte le altre funzioni aritmetiche "-", "/", ecc)
Sì, c'è un limite superiore, ma il limite superiore esatto dipende dall'implementazione. Hai la certezza di poter passare almeno 50, ma tutto dipende. Se hai bisogno di sommare una lista, probabilmente stai meglio con (reduce #'+ list), che dovrebbe darti una scalabilità molto migliore di qualsiasi altro metodo.
Common Lisp HyperSpec ha qualche info in più.
Quando si tratta di valore varia ci sono due casi distinti, galleggiante e interi. I float sono intrinsecamente limitati dalle loro dimensioni e un'implementazione che è passata da single float a double float mi sorprenderebbe molto. Con interi e razionali, CL passa senza problemi tra fixnum e bignum, quindi il limite è una funzione dello spazio di indirizzi utilizzabile disponibile per l'implementazione. Sospetto che le stesse considerazioni valgano per numeri complessi (interi e razionali complessi -> vai su bignum se necessario, float complessi -> segnala un fuori range, o restituisci un Inf o NaN).
Risposta semplice, no, anche se una scarsa applicazione utilizzando la ricorsione e non la coda ricorsione avrà un limite di stack.
A seconda della vostra implementazione + può essere implementato usando la ricorsione o come una chiamata di funzione diritta.
Non conosco abbastanza bene Common Lisp per sapere quali requisiti specifica, ma la maggior parte delle implementazioni, se usano la ricorsione, useranno la ricorsione in coda ed eviteranno qualsiasi limite di stack.
Una chiamata di funzione sarà in grado di accedere agli argomenti come una lista e quindi non v'è alcun limite al numero di argomenti che possono essere elaborati.
EDIT: Poiché qualcuno ha effettivamente fornito un riferimento Common Lisp, dovrebbe essere chiaramente una risposta migliore, ma avrei pensato che una buona implementazione avrebbe applicato automaticamente l'equivalente di (reduce #'+ arg-list) quando sono stati forniti sufficienti argomenti.
I Common Lisps non sono generalmente ricorsivi in coda. Ho la sensazione di aver letto che c'è una ragione per cui non è permesso loro di ottimizzare le code tail (anche se, potrei benissimo immaginarlo). – Marcin
Inoltre, non vi è alcun motivo per cui un'implementazione utilizzi la ricorsione, data la disponibilità di 'reduce' e' ciclo'. – Marcin
@Marcin È possibile avere un'ottimizzazione di coda e la maggior parte lo fa, se si modificano le variabili di ottimizzazione (principalmente "velocità" alta e "debug" basso, ma consultare il manuale di implementazione per le specifiche). – Vatine
Common Lisp è stato definito in modo tale da poter essere implementato in modo efficiente su una vasta gamma di sistemi hardware e software. Esempi sono processori come il Motorola 68000/20/30/40, i vari processori Intel x86, processori basati su stack di Lisp Machine, DEC VAX, processori RISC, computer super come quelli di Cray. Negli anni '80 c'erano molte famiglie di processori in competizione, inclusi processori sviluppati per l'esecuzione del codice Lisp. Oggi abbiamo ancora diverse famiglie di processori (x86, x86-64, ARM, SPARC, POWER, PowerPC, ...).
Può anche essere compilato in C, Schema o altri linguaggi di programmazione.
Può anche essere compilato su macchine virtuali come quelle di CMUCL, CLISP o JVM/Java Virtual Machine (La Java Virtual Machine sembra avere un limite di 254 argomenti).
Ad esempio, un compilatore Common Lisp potrebbe compilare il codice Lisp al codice C straight-forward. Quindi sarebbe bene se la maggior parte della funzione chiamata del compilatore C potesse essere riutilizzata il più possibile. Soprattutto per rendere più semplice la chiamata di Lisp da C.
C/C++ ha limiti che, anche:
Maximum number of parameters in function declaration
Sopra dà numeri come 127 (C) e 256 per C++. Quindi per un compilatore da Lisp a C questi potrebbero essere i limiti. Altrimenti il codice Lisp non userebbe la chiamata della funzione C.
Il primo di questi compilatore LKC (Kyoto Common Lisp, dopo questa implementazione si è evoluto in GCL/GNU Common Lisp e ECL/incorporabile Common Lisp) aveva una CALL-ARGUMENTS-LIMIT di 64.
Un'implementazione a 64 bit di LispWorks/Mac OS X per esempio ha un valore di 2047 per CALL-ARGUMENTS-LIMIT.
CALL-ARGUMENTS-LIMIT dovrebbe essere non inferiore a 50.
Così, in Common Lisp, l'elaborazione e la lista argomenti di chiamata non sono correlate. Se si desidera elaborare gli elenchi, è necessario utilizzare gli strumenti di elaborazione dell'elenco (LISTA, MAPCAR, APPEND, RIDUCE, ...). Common Lisp fornisce un meccanismo per accedere agli argomenti come un elenco utilizzando un parametro &REST. Ma di solito dovrebbe essere evitato, dal momento che potrebbe causare un sovraccarico della funzione perché è necessario un elenco degli argomenti da trattare.
Clojure fornisce un esempio di Lisp dove si può effettivamente avere un numero infinito di argomenti a una funzione, tramite l'uso di sequenze pigri:
; 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]
Non particolarmente utile, naturalmente .....
Questo esempio non mi convince. APPLY viene chiamato con due argomenti. Che + viene chiamato con argomenti infiniti non è chiaro. Forse APPLY è occupato PRIMA + viene chiamato con argomenti infiniti. Dato l'esempio di @jwinandy che mostra Clojure di "appendere" a 8192 argomenti, sospetto che lo stesso succeda qui ... –
Dipende dall'implementazione. "Suggerirei agli utenti di LISP di impiegare 5 minuti per testare la propria piattaforma".
Per 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)
Non terminare, si blocca al 8192 dato le mie impostazioni.
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
Questo è ciò che dice la specifica, ma sai di eventuali implementazioni che effettivamente applicano un limite? – Marcin
@Marcin Bene, SBCL ti garantisce un LIMITE DI ARBITRO DI CHIAMATA nella regione di 10^18 e mi aspetto che passando più argomenti che semplicemente non funzionerebbero. Non ho altre implementazioni banalmente a portata di mano, ma ricordo di aver letto di persone che hanno problemi nell'usare APPLY invece di RIDURRE con liste più corte di "nelle centinaia di elementi". – Vatine
@Vatine Mi sono appena reso conto che il titolo e la descrizione della domanda si contraddicono nei loro significati. Poiché penso che stai rispondendo al limite di valore della funzione "+", ti dispiace commentare il limite di _inputs_ che la funzione può avere? Dispiace per la confusione! – Soyuz