Lisp
Wikibooks, manuali e libri di testo liberi.
Lisp, che significa "List interactive system process" (sistema per processare interattivamante liste), è un linguaggio che nasce ad opera di John McCarthy nel 1959 molto utilizzato per programmazione in A.I.(intelligenza artificiale) È molto semplice da usare ed a 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 WEB dinamici, sistemi esperti, progetti di A.I., motori infenziali 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#, anch'essi object oriented ma con limiti che il LISP ha da sempre sorpassato fin dalla sua prima implementazione.
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 nella quale i dati diventano codice e il codice viene manipolato come un dato.
Per questo manuale on-line useremo vari interpreti/compilatori lisp Open source.
Indice |
[modifica] Breve storia
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ù veolce 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 Lispmachine 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 fundation, idea di Richard Stallman coinvolto ai progetti lispmachine del MIT, che con una lispmachine 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 LispMachine. 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 avvine 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.
[modifica] Per iniziare
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 digiate 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.
[modifica] S-expression
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.
[modifica] Tipi dati nel Lisp
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.
[modifica] Variabili nel LISP
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 memoriza delle medesime assegnando ad esse una dimensione in funzione del tipo di variabile:
int a, b,c; float f1, Tarc, ...;
Nel lisp le varibili 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 varaibile "la casa al mare" > (+ val1 val2 ) <------- errore si tenta la somma di tipi diversi
[modifica] Numeri
Il lisp tratta in numeri solo quando li valuta nella funzione di Eval 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 priorita 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.
[modifica] stringhe
[modifica] array di dati
[modifica] liste
Introduzione da zero.
Il Lisp si basa sul concetto di elaborazione delle liste, infatti il nome Lisp deriva da "List Processing". 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 ().
[modifica] manipoliamo i numeri
[modifica] manipoliamo gli array
[modifica] manipoliamo le liste
(0(1 2 3)(4 5)6(7 8)9)
[modifica] Visione in Lisp
La visione artificiale è resa possibile da potenti stumenti del lisp a mezzo di algoritmi dedicati alla interpretazione binaria delle immagini. All'inizio si lavorava con immagini binarie composte da array bidimenionali 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 piu informazioni sulla tipologia di oggetti nel campo visivo. l'introduzione della vista binoculare ha inoltre consentito agli algoritmi di estrare 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 ricostuito.
L'immagine binary 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. Il linux existe un set di strumenti per convertire immagini da vari formati al formato testuale lisp per leggerlo ed eseguire le vostre prove( guardare sulla vostra versione linux i comandi pgmtolispm <--> lispmtopgm e formati grafici collegati a tiff, gif, png, bmp, eccc... ).
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
[modifica] Algoritmi di manipolazione di array binary di immagine
(defun vis2d_edge() ...) (defun vis2d_contour() ... ) (defun vis2d_sharp() ... )
[modifica] Algoritmi di estrazione delle infomazioni di oggetti presenti su un piano di visione
Blob.lsp racchiude in se una serie di algoritmi che ritorna una lista di oggetti estratti da una immagine che ha subito una manipolazione del'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 mettendo tutte le informazioni in forma di lista .
( 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)) )
[modifica] Algoritmi per riconoscimento tridimensionale di oggetti con telecamera binoculari
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 (vedi immagine 1) con un reticolo di punti di riferimento generati da un apposito ologramma. Nella visone senza i marker un piano inclinato bianco che occupa totalmente l'area di visione non è 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. 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.
Esempio di lista generata dopo il riconosciento delle due videocamere con oggetto il piano ed il suo versore di orientazione in linguaggio VRLM .
( lista-3d ( plane ojb1 ( 0.0 0.0 -70.789321)( -0.5289 0.502 0.8939)))
[modifica] Web e Lisp?
Un uso insolito e poco pubblicizzato è vedere un lisp come front end CGI 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 ( lisp interprete ) - 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 e dal vs. web di test lanciate
http:<mioserver>/cgi-bin/mytest.lisp
Il prodotto Web per eccellenza, stabilità e per modularità di interfaccia e potenza resta comunque Allegro della Franz Inc. della quale rimando a questo sito la trattazione di una implimentazione aziendale con database e transaction manager.
[modifica] TCP ed il lisp
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 ASCII leggibile NMEA.
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.
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)))
[modifica] Il Mercato del lisp
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
- Opengenera
- Allegro Common Lisp
- LispWorks
- Scieneer Common Lisp
- Corman Lisp
- Macintosh Common Lisp
- Ufasoft Common Lisp
- Star Sapphire Common Lisp
- OpenLisp
Download Open Source
Siti di riferimento
CD live
