Linguaggi di Programmazione

PROGRAMMAZIONE FUNZIONALE

Partiamo da una considerazione: i LP imperativi sono all'apparenza simili, perché fanno riferimento ad un modello di progettazione che è quello della macchina fisica.

La famiglia dei LP imperativi sono un'estensione, un progressivo "miglioramento" del FORTRAN.

Ad un certo punto si è compreso che non è necessario aderire pesantemente ad un modello fisico, è una restrizione non necessaria al processo di sviluppo del software.

Possibilità di modelli alternativi di progettazione dei LP.

Paradigma funzionale: basato sulle funzioni matematiche, sono LP funzionali. La teoria è astratta, si basa sulle funzioni ricorsive.

Funzione matematica → La funzione matematica è un mapping fra dominio e codominio, specificata da espressione e/o tabella. Alcune espressioni non possono essere espresse da espressioni, in quanto spesso le corrispondenze sono arbitrarie, quindi si usa una tabella.

Perché non esiste una funzione matematica che esprima il codominio. La funzione è applicabile ad un elemento del dominio. La valutazione della espressione di mapping è controllata da espressioni condizionali e ricorsione.

Funzione matematica: definisce un valore, non una sequenza di operazioni su variabili in memoria per produrre un valore. Non esistono variabili ed effetti collaterali, il valore della funzione dipende solo dai suoi argomenti.

Funzioni Semplici

Definizione di funzione: nome (lista-di-parametri) expr-di-mapping

Martina Contestabile — Mat. 731044 ℛ

cubo(x) = x*x*x dominio = codominio =

Valutazione della expr di mapping: x rappresenta un (immutabile) elemento.

Applicazione della funzione: associazione f elemento-del-dominio→cubo(2.0) 8.0

Forme funzionali

Funzione di ordine superiore o i parametri sono funzioni oppure il risultato è un'espressione.

Esempi Applicare una funzione ad un'altra funzione.

Lista di funzioni applicate allo stesso dominio.

34fi fi ff fi fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Fondamenti dei LP Funzionali

L'obiettivo è massimizzazione delle similarità con funzioni matematiche. Se il linguaggio assomiglia al linguaggio matematico, è puro.

L'approccio al problem-solving è molto diverso da quello dei LP imperativi.

Il programma funzionale è esprimibile come { def di funzioni } + { applicazioni di funzioni }, ossia una lista di funzioni più l'applicazione delle funzioni definite applicate a determinati valori. In un linguaggio funzionale l'output

sono le { applicazioni di funzioni }.L’esecuzione è la valutazione delle applicazioni delle funzioni.Poiché non esistono var assegnabili, è impossibile controllare cicli (conteggio, condizionali), quindi laricorsione, e lo stato del programma, perciò il risultato dipende solo dagli argomenti. Si parla di trasparenzareferenziale.

FPL fornisce { funzioni primitive }, { forme funzionali } ossia la costruzione di funzioni complesse partendo6da primitive, operazione di applicazione delle funzioni e strutture dati.

Il problema delle funzioni nei LP imperativi sono la restrizione sui tipi di valori restituiti, cioè che le formefunzionali ridotte, ed e etti collaterali, dato che opera su variabili in ingresso e globali.

SchemeNato nel 1958 da John Mc Carthy e Marvin Minsky. Servì perché stavano lavorando al MIT AI Project,serviva la progettazione di un LP per la manipolazione di liste: nasce Lisp. Usare array per rappresentare glialberi era complesso,

ma una lista di dati rappresenta dati. Le strutture dati lo rendo semplice dal punto di vista type-system, solo atomi — fatta di identificatori o sequenze di cifre e liste — delimitate da parentesi.— Lisp adotta come paradigma di riferimento il paradigma funzionale, il quale non rende necessario l'assegnamento. Una cosa peculiare di Lisp è l'omogeneità di rappresentazione di dati e codice. Martina Contestabile — Mat. 731044 Il codice non è statico e non viene eseguito sempre nello stesso modo, ma è runtime, Lisp lo permette in modo naturale. Impatto: domina le applicazioni AI per 25 anni. Discendenti di Lisp sono Common Lisp, che contiene diversi tipi di strutture dati, scope statico e dinamico e packages, e Scheme. Subset di Scheme è senza assegnamento, si parla di FPL Turing-completo quando c'è tipo intero, creazione di funzioni, condizionali e ricorsione. Espressioni → Notazione prefissa con parentesi (+ 2 3)

Possibilità di numero variabile di argomenti

Functional Programming Language.

Le funzioni e i dati non hanno lo stesso diritto di cittadinanza, qui le funzioni non possono essere il sostituito di qualsiasi dato che compare nella computazione.

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

In in linguaggio normale, scriviamo a + b, le parentesi non sono necessarie. In scheme, invece, sono obbligatorie. La produttoria di una lista vuota è zero. L'ultimo è il fattoriale di 5.

Liste per rappresentare dati e funzioni, queste ultime il primo elemento della lista — operatore e nome funzione.

Espressioni complesse mediante liste innestate

Espressione parentetica con operatori ssi. La corrispondenza è molto semplice fra albero ed espressione.

Valori globali (define d 120) cambia l'ambiente (unica nel nostro subset)

Si lega il nome di un'espressione all'espressione. Quando scriviamo quello, ogni volta

Che scriviamo dusiamo il valore associato, cioè 120. Il valore 120 è legato intimamente alla variabile d. A d si può anche associare una lambda astrazione, ossia un’espressione.

Valutazione delle espressioni

Governate da 3 regole

Nomi sostituiti dai loro binding correnti

Un nome deve essere associato ad un valore, non sono variabili, ma costanti.

Martina Contestabile — Mat. 731044

Liste valutate come chiamate di funzioni scritte in forma pre ssa

È una cosa che avviene di default, l’istruzione è il primo elemento della lista.

Qui stiamo invocando il + agli argomenti della lista. Siccome nella quarta riga abbiamo 5 come primo elemento, c’è errore perché 5 non è una funzione. Anche per l’ultimo esempio vale lo stesso ragionamento, perché d è una costante.

Costanti sono valutate come se stesse 36fi fi

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Inibizione della valutazione

Per avere una stringa noi in Java facevamo «alfa», in Scheme si fa con apice, si può anche definire una lista di dati.

Liste

Albero in cui il nodo punta a due puntatori. Ci sono due liste piatte, pari e dispari. In testa c’è un elemento, 0 per pari e 1 per dispari, mentre a seguire c’è una coda con gli altri valori. La coda può a sua volta essere composta in testa o coda.

Martina Contestabile — Mat. 731044

Costruzione (cons elem lista)

Funzione di costruzione che costruisce una lista attraverso la «composizione» di un elemento in testa e una lista come coda. Quando abbiamo una funzione Scheme, anche se, apparentemente, sembra che la funzione cambi gli argomenti, non è cosi: una funzione non ha mai effetti collaterali sugli elementi di una lista. Un linguaggio funzionale opera su elementi per ottenere un risultato.

cons viene usato spesso anche nei temi esame. Il modo in cui opera è fare una copia degli

elementi già presenti e creare una nuova lista con il recente elemento desiderato in testa.

37 ff fiMartina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Il car genera la testa, mentre il cdr la coda. car e cdr possono essere solo applicati a liste non vuote.

(car pari) è il primo numero pari, 0.

(cdr pari) è la lista dei numeri pari, esclusa la testa.

(car (cdr pari)) tira la coda di pari e preleva la testa della coda, 2. (cadr pari) è la stessa cosa.

(cdr (cdr pari)) preleva la coda di pari e preleva la coda della coda di pari, (4 6 8). (cddr pari) è lo stesso.

(car '(6 8)) è la testa della lista, 6.

(cdr '(6 8)) è la coda della lista, 8.

(car '(8)) è la testa della lista, 8.

(cdr '(8)) genera errore.

I progettisti di Lisp hanno deciso di rappresentare il descrittore, il nodo, usando per il puntatore testa il contenuto dell'address part, mentre per la coda la decrement part.

Martina

Contestabile — Mat. 731044

list e append sono altri operatori utili. Invece di applicare cons numerose volte, usiamo list per impacchettare tanti elementi in un'unica volta.

(list pari dispari) ; ((0 2 4 6 8) (1 3 5 7 9)) è la lista di due liste.

(list 'pari 'dispari) ; (pari dispari) è la lista di due atomi.

(append pari dispari) ; (0 2 4 6 8 1 3 5 7 9) concatena due liste.

Spesso si fa confusione fra append e cons, tuttavia, c'è una grossa differenza: se abbiamo una lista e una testa, usiamo l'append, se si fa il cons abbiamo le parentesi che sottolineano la differenza fra le strutture.

38 ff ff

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Se la lista è vuota è zero, altrimenti è la testa + la sommatoria della coda. La somma, a ritroso, rappresenta il risultato. Quando una funzione è booleana, si mette il ?, ma non è strettamente necessario. La lista vuota non necessita dell'apice.

perché è ben definita, non pone ambiguità. Se non è vuota, il null ritorna false, true altrimenti. Equal restituisce true se uguali e false se non lo sono, ossia sono di tipo differente. Una lista Scheme è polimorfa, non è come un array di interi ecc, Scheme essendo typeless, può avere elementi di qualsiasi tipo nella lista. Un linguaggio di tipo typeless si paga in sicurezza. (equal? 5 '(5)) sono differenti perché uno è un atomo e l'altro una lista. (equal? '(1 2 3) '(1 (2 3))) perché uno è una lista con tre elementi, l'altra no. Martina Contestabile — Mat. 731044 (equal? () ()) due liste vuote sono uguali. Per sapere se in testa ho un atomo o una lista uso queste funzioni. list? dice se è una lista, symbol? se è un simbolo, number? se è un numero e