Lisp

Wikibooks, manuali e libri di testo liberi.

Lisp, che significa "List Processor language" (linguaggio per processare liste), è un linguaggio di programmazione che nasce ad opera di John McCarthy nel 1959 molto utilizzato nel campo della A.I. (intelligenza artificiale). È molto semplice da usare ed imparare. Orientato alla logica ed ad una programmazione funzionale ricorsiva è stato impiegato per programmazione di basso livello e di alto livello ad oggetti. È stato il primo linguaggio ad adottare i concetti di Virtual Machine e Virtual Memory management.

Usato oggi per creare siti web dinamici, sistemi esperti, progetti di A.I., motori inferenziali con base dati della conoscenza al servizio di problem solving di strategia, NASA, NCSA, e Difesa Americana lo vedono ancora come strumento strategico per le potenti opportunità che ancora oggi fanno di questo linguaggio il maggior competitor di nicchia, in contrapposizione a Java, C++ e C#.

Il Lisp è un linguaggio di programmazione elegante, sintatticamente semplice e di facile apprendimento, usato per la sua flessibilità e la propensione a manipolare variabili con astrazione di oggetti complessi quali liste di dati. La sua particolare caratteristica funzionale e ricorsiva lo rende tanto flessibile da essere l'unico linguaggio in grado di interpretare/compilare se stesso con un polimorfismo nel quale i dati diventano codice e il codice viene manipolato come un dato.

Inoltre, proprio dal Lisp Andy Gavin ha inventato il GOOL (Game Object Oriented Lisp) e il suo successore GOAL (Game Oriented Assembly Lisp), i linguaggi di programmazione usati rispettivamente nelle serie di videogiochi di Crash Bandicoot e Jak & Daxter.

Per questo manuale on-line useremo vari interpreti/compilatori Lisp open-source.

Breve storia[modifica]

Tra il '59 ed i primi anni '70 il linguaggio trova interesse nelle applicazioni di ricerca finanziate dal DARPA che in seno ad alcune Università prestigiose quali il MIT e Carnegie-Mellon University creano su macchine a 36bit dell'epoca i primi porting di un interprete LISP curato personalmente da McCarthy. Qui nasce la leggenda del polimorfismo del LISP; viene creato un codice Lisp per compilare il LISP, da una idea del team il compilatore compila l'interprete ed il compilatore stesso rendendo ancora più veloce il codice esistente ed aprendo la strada ai sistemi di simulazione delle architetture dei processori. Dobbiamo comunque attendere gli anni 70 per vedere i primi progetti hardware al MIT di Lisp Machine che faranno da motore alla economia ed al settore ricerca creando anche i primi hacker della storia ed una vasta ricaduta in aziende con molteplici specializzazioni messe a punto sulle macchine Lisp di questa epoca. Dobbiamo al LISP la nascita dei sistemi esperti, del programmi di problem solving le macchine inferenziali, il math solving, i database relazionali e gli esperimenti sul linguaggio naturale di query SQL, la tecnologia di elaborazione di immagine con software di RayTracing e le prime animazioni digitali. Da questo progetto nasce anche la prima idea di open-source, la GNU Foundation, idea di Richard Stallman coinvolto ai progetti Lisp Machine del MIT, che con una Lisp Machine mise a punto in LISP "Emacs", un editor molto usato, ed i primi programmi server e client per la posta elettronica.

Negli anni '80 si sviluppano hardware dedicati con processori stack machine specializzate nella manipolazioni di liste nella quale la memoria e l'architettura sono orientate a scelte specifiche per questo tipo di linguaggio, nascono le Lisp Machine. Alle macchine LISP sono collegate le connection machine con 65535 processori, sono connesse con hardware per l'elaborazione grafica. Si crea la prima branca di esperti in elaborazione grafica e di immagini.

Negli anni '90 avviene il declino delle macchine LISP, l'evoluzione dei processori RISC e le potenze di calcolo in continua crescita portano queste architetture ad essere soppiantate da sistemi ad alte prestazioni con processori RISC a 64bit che interpretano e compilano codice Lisp in linguaggio macchina senza l'ausilio del supporto di un hardware dedicato. Nascono tra molti dialetti di LISP un linguaggio LISP portabile tra le piattaforme Hardware il COMMON LISP ed il CLOS come linguaggio orientato agli oggetti. Java e C++ segnano definitivamente il corso delle lispmachine relegando a progetti di nicchia. Java e C++ pur avendo negli obbiettivi la flessibilità della programmazione a oggetti e il polimorfismo e l'uso dinamico della memoria restano anni luce lontani dalle performance e flessibilità che ancora oggi contraddistinguono questo potentissimo linguaggio. Testimonianze dei test effettuati da Nasa ed Ames

Per iniziare[modifica]

Appena avete installato sul vostro P.C. il CLisp (qualunque esso sia) questo vi presenta il Prompt di inserimento comandi esattamente come farebbe una shell a comandi.

 $ clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8
 Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
 Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
 Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
 Copyright (c) Bruno Haible, Sam Steingold 1999-2001
 [1]> (+ 1 2 3 4 5 6 7 8 9)
 45
 [2]>

Come abbiamo appena visto inserendo una lista composta da elementi separati da spazi tra 2 parentesi aperta e chiusa otteniamo l'esecuzione. Il processore LISP elabora (valuta) il comando inserito, sommando tutti termini che compongono la lista. Avete appena scritto il vostro primo programma in LISP. Il Lisp esegue immediatamente i comandi introdotti sotto forma di liste che voi digitate attraverso il terminale.

La sintassi e molto semplice:

(comando liste liste liste ...)

Mediante pochi passi potete imparare a scrivere i vostri comandi ed seguire i vostri programmi.

S-expression[modifica]

Le S-expression sono le liste nella loro forma più o meno semplificabile in aperta parentesi, funzione, item, item, item... chiusa parentesi e tutte le soluzioni che aprono parentesi in modo nidificato. Le S-espression sono liste.

( 1 2 )
( scuola ( nome ITIS )
         ( preside marcello turati)
         ( n.allievi 1567)
         ( didattica ( meccanica elettronica matallurgia informatica mecatronica))
)
(defun test ( a b )
 ( + a b ))

Queste sono s-expression valide per il linguaggio LISP.

Tipi dati nel Lisp[modifica]

Nel Lisp le variabili sono s-expression. Il linguaggio a differenza di tutti gli altri linguaggi interpretati o compilati non tipizza il dato. Il Lisp non assume per una variabile un tipo di dati stabile ed unico, ma consente la massima libertà di azione nell'uso delle variabili, consentendo anche cambi di tipo in corso di esecuzione del software. Questa è una proprietà che consente ad una variabile (s-expression) di creare tipi astratti ed al programmatore di trasformare variabili in codice eseguibile. Il Lisp valuta il contenuto ed il tipo delle variabili solo quando una funzione esegue una operazione con il contenuto della S-expression.

 > (setq test 12)
 12 
 > test
 12
 > (setq test 10)
 10
 > test
 10
 > (setq test "gatto")
 "gatto"
 > test
 "gatto"

Come controllare che la variabile contenga il tipo giusto di variabile che una funzione si aspetta? Esiste in Lisp una serie di funzioni booleane che consentono di testare le variabili Globali, Locali, o Passate nelle funzioni prima di attuare operazioni sulle medesime. Il sistema Lisp gestisce la creazione e la distruzione delle variabili riciclando lo spazio occupato in memoria con un sistema di Garbage-Collector.

Variabili nel LISP[modifica]

Le variabili in Lisp non sono tipizzate, cioè non assumono la tipologia (int, char, stringa, float, ecc...) sino a quando non vengono valutate (eval ...) dalla engine Lisp. Le variabili quindi assumono un significato ed un tipo solo quando il processo di EVAL le considera per l'esecuzione di una funzione.

Tutti i linguaggi creano le variabili e allocano lo spazio di memoria delle medesime assegnando ad esse una dimensione in funzione del tipo di variabile:

 int a, b,c;
 float f1, Tarc, ...;

Nel Lisp le variabili sono memorizzate nella forma di liste e verranno usate per la tipologia
richiesta solo quando una funzione ne prende in esame il contenuto:

 > (setq val1 10)
 10
 > (setq val2 167)
 167
 > (+ val1 val2 )
 177
 > (setq val2 178)
 178
 > (+ val1 val2)
 188
 > (setq val2 "la casa al mare")  <--- cambio di tipo della variabile
 "la casa al mare"
 > (+ val1 val2 )     <------- errore si tenta la somma di tipi diversi

Numeri[modifica]

Il Lisp tratta in numeri solo quando li valuta nella funzione eval (da evaluate, valutare) per il resto restano entità astratte senza un contenuto formale di tipo. Si possono mettere insieme numeri di notazione diversa ed eseguire calcoli tra di loro, si possono creare funzioni che calcolano in modo ricorsivo e presentano la soluzione. In Lisp è stato progettato Mathlab il programma più evoluto di problem solving. Il Lisp per il suo polimorfismo dei tipi consente elaborazioni complesse di problemi matematici e rappresentazione grafiche dei risultati.
Operazioni semplici di addizioni di una lista di elementi numerici.

 > (+ 1 4 6 7)
 18

Operazioni su più elementi della lista con priorità date dalle parentesi

> (* (/ 7 6 ) (+ 4 (* 4 6)))
 98/3

Come possiamo notare il sistema ha variato la notazione per introduzione di una frazione (sette sesti)

 > (/ 1 2)
 1/2

Il meccanismo di calcolo ed il risultato sono perfettamente controllabili dal Lisp

 > (* (/ 1 2 ) 6)

Definiamo una semplice funzione per calcolare il quadrato

 > (defun pow2 (a)
        (* a a))

Ora definiamo la funzione per calcolare il cubo

 > (defun pow3 (a)
        (* a (pow2 a)))
 > (pow2 2)
 4
 > (pow3 2)
 8

Con questo sistema si possono creare funzioni per conversioni metriche ad es convertire metri in pollici

 > (defun mt2inch ( m )
       (/ m 0.0254))
 > (mt2inch .12716523)
 5.006505

Per calcolare funzioni complesse è un valido strumento interattivo adatto a trattare matrici o risolvere sistemi matematicamente complessi. Un esempio di utilizzo del lisp per la soluzione di equazioni metematiche e messa in grafica delle funzioni è riconducibile allo sviluppo di prodotti come Maxima derivato dallo sviluppo di Macsyma iniziato al MIT negli anni 80. Un Tutorial in italiano di maxima lo trovate qui

Stringhe[modifica]

Array di dati[modifica]

Liste[modifica]

Introduzione da zero.

Il Lisp si basa sul concetto di elaborazione delle liste, infatti il nome Lisp deriva da "List Processor". Una lista è un insieme di celle chiamate cons, ovvero una struttura di nodi collegati in modo sequenziale che possono essere a N livelli.

È importantissimo capire come funziona la struttura di una lista!


Esempio di lista vuota:
( ) --> apertaparentesi+chiusaparentesi significa lista vuota e corrisponde al simbolo: nil .
La struttura interna di questa lista è rappresentata dal simbolo: nil .


Esempio di lista con un solo elemento (un nodo):
(nome) --> è una lista formata da un solo elemento, un simbolo che abbiamo chiamato nome.
La medesima lista si può scrivere anche cosi: (nome . nil).

La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0
+---+---+
|car|cdr+-----> nil
+-|-+---+
  | 
  v
nome


Esempio di lista con due elementi (due nodi):
(nome cognome) --> è una lista formata da due elementi, due simboli che abbiamo chiamato nome e cognome.
La medesima lista si può scrivere anche cosi: (nome . (cognome . nil)).
La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0         nodo:1
+---+---+      +---+---+
|car|cdr+----->|car|cdr+-----> nil
+-|-+---+      +-|-+---+
  |              |
  v              v
nome           cognome


Esempio di lista composta da due liste (struttura a due livelli):
(nome cognome (località provincia)) --> è una lista composta da due liste contenenti due simboli ciascuna, e nel primo livello un link (nodo:2) che fa da puntatore alla seconda lista (nodo:3 - 4).
Infatti nel primo livello gli elementi sono 3, mentre nel secondo livello gli elementi sono 2!
La struttura interna della lista in questione può essere schematizzata nel seguente modo:

 nodo:0         nodo:1         nodo:2
+---+---+      +---+---+      +---+---+
|car|cdr+----->|car|cdr+----->|car|cdr+-----> nil
+-|-+---+      +-|-+---+      +-|-+---+
  |              |              |
  v              v              |
nome           cognome          v nodo:3         nodo:4
                                +---+---+      +---+---+
                                |car|cdr+----->|car|cdr+-----> nil
                                +-|-+---+      +-|-+---+
                                  |              |
                                  v              v
                                località        provincia


Ogni nodo di una lista corrisponde a una cella di memoria chiamata CONS. Ogni cons contiene internamente sempre due valori: un valore chiamato car e un valore chiamato cdr.

La funzione car restituisce sempre il primo elemento di una lista, sia esso un simbolo o una lista:

 >('''car''' '()) => nil
 >('''car''' '(uno)) => uno
 >('''car''' '(uno due tre)) => uno
 >('''car''' '((uno) due tre)) => (uno)

La funzione cdr invece restituisce sempre il resto della lista racchiuso fra parentesi:

 >('''cdr''' '()) => nil
 >('''cdr''' '(uno)) => nil
 >('''cdr''' '(uno due tre)) => (due tre)
 >('''cdr''' '(uno (due tre))) => ((due tre))


N.B. quasi tutto in Lisp viene rappresentato attraverso le liste!

Ora proviamo a scrivere alcuni comandi direttamente nell'interprete Lisp:

 >('''car''' '(nome cognome (località provincia)))
 >nome
 
 >('''cdr''' '(nome cognome (località provincia)))
 >(cognome (località provincia))
 
 >('''car''' ('''cdr''' '(nome cognome (località provincia))))
 >cognome
 
 >('''cdr''' ('''cdr''' '(nome cognome (località provincia))))
 >((località provincia))
 
 >('''car''' ('''cdr''' ('''cdr''' '(nome cognome (località provincia)))))
 >(località provincia)
 
 >('''car''' ('''car''' ('''cdr''' ('''cdr''' '(nome cognome (località provincia))))))
 >località

N.B. L' apostrofo serve per passare una costante letterale o strutturata ().

Manipoliamo i numeri[modifica]

Manipoliamo gli array[modifica]

Manipoliamo le liste[modifica]

(0(1 2 3)(4 5)6(7 8)9)

Visione in Lisp[modifica]

La visione artificiale è resa possibile da potenti strumenti del Lisp a mezzo di algoritmi dedicati alla interpretazione binaria delle immagini. All'inizio si lavorava con immagini binarie composte da array bidimensionali di stati binari (pixel on/pixel off). Nel tempo l'evoluzione ha comportato miglioramenti nella gestione adattativa dell'immagine tali da ricavare da immagini a colori più informazioni sulla tipologia di oggetti nel campo visivo. l'introduzione della vista binoculare ha inoltre consentito agli algoritmi di estrarre oggetti 3D nello spazio di visione con riferimento a solidi simulati che orientassero poi sistemi decisionali di analisi del comportamento ed azione in uno spazio virtuale ricostruito.

L'immagine binaria può essere rappresentata da un array binario come questo

 (camera-right '( (1 0 1 1 1 1 1 1 0 ... )
                 (0 0 1 1 1 1 1 1 0 ... )
                 (1 0 1 0 1 1 1 1 0 ... )
                 (0 0 1 1 0 0 0 1 0 ... )
                 ...
                 (0 0 1 0 1 1 1 1 0 ... )
                 (0 0 1 0 1 1 0 1 0 ... )
                 (0 0 1 0 1 0 1 1 0 ... )
                 (1 0 1 1 1 1 1 1 0 ... ))

Array di dimensione finite 800x600 che rappresenta la risoluzione del sistema di visione. In Linux esiste un set di strumenti per convertire immagini da vari formati al formato testuale Lisp per leggerlo ed eseguire le vostre prove (guardare sulla vostra distribuzione Linux i comandi pgmtolispm <--> lispmtopgm e formati grafici collegati a tiff, gif, png, bmp, ecc.).

Un esempio di integrazione Lisp su Linux con acquisizione da WebCam e rilevazione dei profili in tempo reale

  (libload "video4linux/v4l")
  (new-window)      ; apre una finestra grafica
  (setq image (ubyte-matrix 240 320 3))  ; alloca lo spazio per l'immagine
  (setq video-device (new v4ldevice "/dev/video" "NTSC" 1 320 240))
  (while t
    (==> video-device grab-into-rgb image)  ; cattura del frame e inserimento nella area immagine allocata
    (rgb-draw-matrix 0 0 image))            ; visualizzazione della imagine nella finestra

Algoritmi di manipolazione di array binary di immagine[modifica]

 (defun vis2d_edge() ...)
 (defun vis2d_contour() ... )
 (defun vis2d_sharp() ... )

Algoritmi di estrazione delle informazioni di oggetti presenti su un piano di visione[modifica]

Blob.lsp racchiude in se una serie di algoritmi che ritorna una lista di oggetti estratti da una immagine che ha subito una manipolazione dell'informazione mediante una filtrazione del contenuto e una definizione dei contorni con un algoritmo di level detection. Dopo questa azione il sistema identifica nella lista i singoli oggetti ricavando ( posizione x, y, dimensione, area, perimetro, orientazione, assi morfologici, peso caratteristico della forma ) e pone tutte le informazioni ricavate nella forma di lista S-expression.

 ( object2d ((obj1 (-16.7882 2.3789) 78.78 71.898 197.789 271.1 ( 37.23 89.78 ) 1023.7879)
             (obj2 (6.8233 3.9780) 78.78 71.898 197.789 90.0 ( 37.23 89.78 ) 1023.7879)
             (obj2 (-6.1827 -10.7976) 78.78 71.898 197.789 30.6 ( 37.23 89.78 ) 1023.7879))
  )

Algoritmi per riconoscimento tridimensionale di oggetti con telecamera binoculare[modifica]

L'analisi di una forma tridimensionale basandosi sulla vista binoculare presenta alcuni problemi superabili con l'adozione di una tecnica mista di marcatura laser della scena con un reticolo di punti di riferimento generati da un apposito ologramma. Nella visione senza i marker un piano inclinato bianco che occupa totalmente l'area di visione è un problema, la mancanza di elementi quali la valutazione del riflesso e della discontinuità del colore sono superati dai marker del laser. Con l'inserimento dei punti del retinolo di marcatura laser il piano viene descritto in modo perfetto sia nella distanza dal sistema di visione sia nel verso di orientazione delle superfici inscritte nel campo visivo. La proiezione dei punti assume un andamento prospettico tale che agli algoritmi agganciano i punti del marker laser e da questi estraggono le posizioni nello spazio del piano o di oggetti in esso contenuti. La traduzione avviene assimilando le forme a piani, cilindri, sfere, coni, tronchi di cono, mezze sfere o porzioni, piramidi, tronchi di piramide e toroidi. Il sistema aggiorna una lista di oggetti ogni tash di fine identificazioni oggetti.

Esempio di lista generata dopo il riconoscimento delle due videocamere con due oggetti il piano ed il cilindro in linguaggio VRLM .

 ( lista-3d ( plane ojb1 ( 0.0 0.0 -70.7893)( -0.5289 0.5022 0.8939))
            ( cyl obj2 ( 1.7123 7.1127 3.5421) ( 0.711 17.234) ( -0.5289 0.5022 0.8939))
            ....
  ))

Web e Lisp?[modifica]

Un uso insolito e poco pubblicizzato è vedere un linguaggio Lisp come CGI front-end di un server Apache. La procedura per la realizzazione di un CGI in Lisp è semplice e di facile test è scopo di questa sezione. Per il test abbiamo usato un ottimo interprete GNU come Guile ben integrato con Apache.

Prerequisiti:
- Installare nel proprio server Linux Guile ( interprete Lisp )
- installare in apache il supporto dei CGI per lisp mod_lisp
- nella Vs. directory di apache ../www/cgi-bin/..ecc... copiate il file qui sotto
 #!/usr/bin/guile -s
 !#
 ;;;
 ;:;  guile test simple interface web
 ;;;  on /var/www/cgi-bin
 ;;;
 ;:;
 (display '"'Content-type: text/html\n\n'"')
 (display ''<html><head><title>lisp test tutor</title>\n'')
 Ecc....
 (display "</html>\n")

cambiate i right per l'esecuzione in 755 con # chmod 755 mytest.lisp

Dal vs. Browser web fate il test lanciando:

http:<mioserver>/cgi-bin/mytest.lisp


Questo è solo un esempio anche se esistono prodotti di eccellenza, stabilità e modularità con potenti interfacce e strumenti disgnostici di interfaccia. Allegro di Franz Inc. è uno di questi potenti strumenti di gestione WEB con potenti interfacce verso i sistemi a database che rendo professionali applicazioni per uso aziendale.

TCP ed il Lisp[modifica]

Lo sviluppo di internet e dei sistemi di comunicazione coinvolge anche linguaggi come il Lisp che in potenti macro consente di conversare in client/server tra sistemi in rete. In questo esempio mettiamo in campo un codice server che mette a disposizione di alcuni client nella rete delle letture rilevate da una seriale che prende il flusso dati da una testa GPS in codice NMEA leggibile in ASCII.

Un ottimo test per vedere la semplicità della chiamate al Layer TCP/IP e per provare la stabilità di questo codice che trasmette indisturbato all'infinito tra un client e un server.

Codice lato client

 (defun open-socket (host port)
  (socket-connect port host))
 (defun client (server port a-string)
  ;; Open connection
  (let ((socket (open-socket server port)))
    (unwind-protect
     (progn
       (format socket "~A~%" a-string)
       (force-output socket)
       (let ((response (read-line socket)))
       (format t "Response from server: ~A~%" response))))
    ;; Close socket before exiting.
    (close socket)))
 (defun test ()
  (client "clavius.ess.prv" 25 "helo"))

Codice lato server

 (defun server()
  (let ((a-server-socket (socket-server 8000)))
    (dotimes (i 2) 
      (let ((connection (socket-accept a-server-socket)))
        (let ((line (read-line connection)))
          (format t "Line from client: ~A~%" line )
          ;;; 
          ;;; send 
          (format connection "response from serveri~%"))
          (close connection )))
    (socket-server-close a-server-socket)))

Il mercato del Lisp[modifica]

Oggi sul mercato esistono diversi interpreti/compilatori commerciali e Open Source che consentono di fare esperienza con questo linguaggio e di produrre codice stabile e adatto ad applicazioni commerciali.

Prodotti Commerciali
Download Open Source
Siti di riferimento
I linguaggi di programmazione su Wikibooks

Ada | Assembly| C | C++ | C# | CSS | HTML | Java | JavaScript | Lisp | LOGO | Pascal | Perl | PHP | Prolog | Python | XML