LISP

Lisp

•Ispirato da funzioni ricorsive e lambda calcolo•Inventato da John McCarthy•Progenitore dei linguaggi di programmazione funzionale

LISP: LISt Processor

LISP è stato disegnato originariamente per l’Intelligenza ArtificialeHa vari dialetti: Common Lisp, FranzLisp, AutoLisp, etc.E’ basato su un approccio ricorsivo ed incrementalePrevalentemente utilizzato mediante interpreti

LISP: Stile interattivo

• Utente: definisce funzioni o richiede un calcolo

• Interprete: accetta la definizione o esegue il calcolo

Tipi di dato in Lisp

Liste

S - espressioni

Floating point

Integer

Lista non vuota

Lista vuota

Atomi

Simboli

Numeri

Esempi

• Lista vuota: ‘()’ anche chiamata ‘NIL’

• Atomo: ‘ALPHA’

• Lista (piatta): ‘( A B D )’

• Lista: ‘( A B ( D E ) A)’

• Intero: 3

• Floating point: 3.14

Liste

• Liste:– Una lista può contenere come

elementi atomi o altre liste.– Gli elementi sono racchiusi tra

parentesi.– Una lista può essere vuota.

Operazioni su liste

• CAR : restituisce il primo elemento di una lista– (CAR ‘(5 2 9)) 5

• CDR : restituisce la lista senza il primo elemento.– (CDR ‘(5 2 9)) (2 9)

• Possiamo mescolare CAR e CDR in ogni combinazione.

Esempi:(CAR (CDR L)) = (CADR L)Es. : (CAR (CDR ‘(1 2 3 4)))

2

(CDR (CAR L)) = (CDAR L)Es. : (CDR (CAR ‘((1 2) (2 3) (3 4) (4 5))))

(2)

•CAR restituisce un ELEMENTO (atomo o lista)•CDR restituisce una LISTA•(CAR NIL) = (CDR NIL) = NIL

Che cos’e’ l’apice che precede le liste di numeri?

QUOTE (‘)

•Notazione prefissa: il primo elemento di una lista e’

la funzione, gli altri elementi sono gli operandi.

•Come distinguo (+ 1 1) (= somma dei numeri 1 e

1) dalla lista costituita dai simboli “+”, “1” e “1”?

•Soluzione: operatore QUOTE (abbreviato con

l’apice):

(QUOTE (1 2 3)) = ‘(1 2 3)

La lista (1 2 3) non viene “valutata” (= non si cerca

una funzione 1 da applicare a 2 e 3)

Altre operazioni su liste: CONS

CONS: Accetta un elemento e una lista e restituisce la lista con l’elemento inserito al primo posto

(CONS ‘A ‘(B C))(A B C)

(CONS ‘A (CDR ‘(B C)))(A C)

Funzioni aritmetiche(+ 3.14 2.5)5.64

(+ 2 (+ 3 6))11

(* 6 4)24

(/ 25 5)5

Float e Integer

(/ 27 9) Divisione tra interi con risultato intero3

(/ 14.0 4.0) Divisione tra reali3.5

(/ (FLOAT 14) (FLOAT 4)) Equivalente al precedente3.5

Altre funzioni matematiche

(MAX 7 6 8)8

(MIN 7 6 8)6

(ABS -8)8

(EXPT 2 3)8

(SQRT 25)5

(ROUND 1.25)1

(ROUND 1.75)2

X intero:X=(ROUND (FLOAT X))

Altre funzioni matematiche

(TRUNCATE 14 4) Divisione tra interi3

(REM 14 4) REMainder: resto2

X,Y interi; Y diverso da 0:(+ (* (TRUNCATE X Y) Y) (REM X Y)=X

Funzioni predefinite su liste: LIST

LIST prende n operandi e restituisce la lista i cui elementi sono gli n operandi

(LIST ‘A)(A)

(LIST ‘A ‘B)(A B)

(LIST ‘A (CDR ‘(A B C)))(A (B C))

Funzioni predefinite su liste: APPEND

APPEND prende n liste e restituisce la lista composta dagli elementi delle n liste

(APPEND ‘(1 2) ‘(3 4))(1 2 3 4)

(APPEND ‘(1 2) ‘(CDR (1 2)))(1 2 CDR (1 2))

Predicati True/False

In Lisp la lista vuota (NIL) è False; tutto il resto è True.

Per indicare esplicitamente il valore True si usa T.

Esempi di predicati

• ATOM verifica se l’operando è un atomo• LISTP verifica se l’operando è una lista• NULL verifica se l’operando è una lista vuota• EQ verifica se gli operandi (S-espressioni)

sono ugualiOltre a questi ci sono, tra gli altri, gli operatori

relazionali: =, >,< che operano su numeri

Numero di operandi

• N: +,*,-,\,MAX, MIN, APPEND, LIST, AND

• 2: TRUNCATE, REM, EXPT, EQ, =, >,<

• 1: ABS, SQRT, FLOAT, NOT, NULL, ATOM, LISTP

Definizione di funzioni: DEFUN

• Sintassi:

• (DEFUN <nome_funzione> (<operando1> <operando2>…<operandoN>) (<corpo_della_funzione>) )

Esempio di definizione di funzione

(DEFUN Secondo (L) (CADR L))

Esempio:

(Secondo ‘( A C D))

C

Espressioni condizionali: COND

Sintassi

(COND (<espressione1> <azione1>)

(<espressione2> <azione2>)

…

(<espressioneN> <azioneN>))

Esempio: funzione PARI

PARI(X)= T se X è pari

NIL altrimenti

(DEFUN PARI (X)

(COND ((= (REM X 2) 0) T)

(T NIL)))

Ricursione

APPARTIENE(A,L)= T se A appartiene alla lista L NIL altrimenti

(DEFUN APPARTIENE (A L)(COND ((NULL L) NIL)

((EQ A (CAR L)) T)(T (APPARTIENE A (CDR L)) )))

(APPARTIENE 'A '(A B C))T

Altri esempi

(DEFUN UNIONE (L1 L2)

(COND ((NULL L1) L2)

((APPARTIENE (CAR L1) L2) (UNIONE (CDR L1) L2))

(T (UNIONE (CDR L1) (CONS (CAR L1) L2)))))

(UNIONE '(A B C) '(C D E))

(B A C D E)

Cenni sull’interprete

Valutazione di S-espressioni:• Atomi: la valutazione di numeri (simboli)

restituisce il numero (simbolo) stesso.• Liste: vengono valutati tutti gli elementi di primo

livello (a meno di QUOTE)– Il primo elemento è sempre un nome di funzione; viene

valutato il corpo della funzione corrispondente.– Tutti gli altri elementi vengono valutati e i risultati

corrispondenti vengono usati come argomenti della funzione