Lisp: i vantaggi degli elenchi come codice su array come codice?

4

Domanda per i programmatori lisp:

Il codice Lisp è costituito da dati lisp, di solito elenchi. C'è un vantaggio nel codice di essere liste su codice come matrici?

Le macro sarebbero più facili da scrivere / più veloci da eseguire?

Si può presumere che, in un tale linguaggio (si potrebbe chiamarlo "arrap"), gli elementi possono essere cancellati o inseriti negli array e che gli array crescono e si riducono se necessario.

    
posta compman 09.07.2011 - 05:37
fonte

3 risposte

12

Le liste sono molto più versatili degli array. Con gli elenchi, puoi recurse (ad es. Per mappare o piegare) facendo scorrere un elenco verso il basso. Questo non funziona per gli array; dovresti passare anche nell'indice dell'array.

Ad esempio, questa è una semplice implementazione di map e fold che richiede solo una lista:

(define (map1 f l)
  (if (null? l) l
      (cons (f (car l)) (map1 f (cdr l)))))

(define (left-fold1 f init l)
  (if (null? l) init
      (left-fold1 f (f (car l) init) (cdr l))))

Come lo faresti per gli array, senza dover passare un altro argomento (per l'indice)? (Ricorda, Lisp e Scheme non hanno puntatori, almeno nessuno che il codice utente possa toccare.)

Inoltre, gli elenchi possono condividere lo spazio di archiviazione, ma gli array no. Prendi questo codice Schema per esempio:

(define (x-world x)
  (cons x '(world)))

(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))

Qui, hello-world ha il valore (hello world) e goodbye-world ha il valore (goodbye world) .

C'è un fatto importante, tuttavia: in molte implementazioni di Schema, la parte (world) di entrambe le liste è effettivamente condivisa. Questa condivisione sarebbe impossibile per gli array.

Addendum: Per rispondere al punto di Compman che la ricorsione è in qualche modo "non di produzione", in Schema, tutto il ciclo / iterazione standard viene eseguito utilizzando la ricorsione della coda. Ecco una versione ricorsiva di% di map1 , ad esempio:

(define (map1 f l)
  (let loop ((r '())
             (l (reverse l)))
    (if (null? l) r
        (loop (cons (f (car l)) r) (cdr l)))))

o, ancora più semplicemente, usando left-fold1 :

(define (map1 f l)
  (left-fold1 (lambda (e r) (cons (f e) r))
              '() (reverse l)))

reverse è uno schema integrato, ma la sua implementazione è ugualmente banale (e utilizza anche solo l'iterazione):

(define (reverse l)
  (left-fold1 cons '() l))
    
risposta data 09.07.2011 - 06:19
fonte
2

L'inserimento stesso è O (1) all'inizio della lista.

(cons x '(world))

Inserisce "x" all'inizio della lista che contiene il mondo. Se si dispone di un array e si desidera inserire un elemento all'inizio, è necessario spostare tutto di uno. Non così con le liste!

    
risposta data 09.07.2011 - 06:24
fonte
1

Alcune lisp utilizzavano una tecnica nota come codifica CDR rappresentazione di una lista fro. Questo, in sostanza, sostituisce la metà CDR della cella con il contenuto della cella puntata, permettendoti di rappresentare una lista con quello che è effettivamente un array di puntatori CAR, pur preservando la semantica delle liste (puoi avere parte di un elenco CDR codificato, condividi le code con codice CDR e altre cose che possono essere gestite da liste normali)

Tuttavia, l'implementazione efficiente della codifica CDR richiede il supporto hardware, quindi (a quanto ho capito) è uscito praticamente con macchine Lisp dedicate.

Per quanto riguarda la lisp-the-language-family, no, non penso che le macro sarebbero più facili da scrivere. Nel migliore dei casi, penso che non sarebbe più difficile scrivere macro.

    
risposta data 21.07.2011 - 15:39
fonte

Leggi altre domande sui tag