Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 20.Un linguaggio Lazy: Il linguaggio Miranda


Storia

  • Sviluppato nel 1986 da Turner.
  • Obiettivo: realizzare una versione commerciale di un linguaggio funzionale e di un conseguente ambiente di sviluppo flessibile e facile da usare

Perché il nome “Miranda”

  • Miranda è una parola latina che significa “essere chiesti a” (dal verbo miror). È stato in uso in Inghilterra e in America come un nome femminile personale fin dai primi del XVII secolo. Il suo primo utilizzo, come nome di una ragazza è dovuto a Shakespeare, in “The Tempest “(1611).
  • Nell’opera “The Tempest”, Miranda è la figlia del mago Prospero. Vive su un isola incantata, protetta da tutti i mali del mondo (che nel contesto dei linguaggi di programmazione può significare l’essenza di effetti collaterali).
  • Nell’Atto 5, Scena 1 dell’opera, Miranda fa un discorso che contiene la frase (più tardi resa celebre da Huxley, come titolo per un suo romanzo): “O Brave New World!”
  • L’idea è che il linguaggio Miranda apre a un nuovo mondo coraggioso (Brave New World), appunto quello commerciale, da parte dei linguaggi di programmazione funzionali.

Caratteristiche fondamentali

  • Puramente funzionale.
  • Basato su liste e tuple.
  • Linguaggio di tipo “Lazy”.
  • Fortemente tipato.

Concetti base: Caratteristiche

  • E’ un linguaggio di programmazione puramente funzionale.
  • Non esistono cicli, solo ricorsione
  • E’ composto da una collezione di equazioni che definiscono le varie funzioni e le strutture di dati che vogliamo elaborare.
  • L’ordine in cui le equazioni vengono date non è, in generale, significativo.

Concetti base: Caratteristiche

Esempio:

z = quad x / quad y
quad n = n*n
x = 5
y = 3

Come si vede dall’esempio l’ordine delle dichiarazioni non è importante e inoltre non ci sono dei “;” alla fine delle definizioni. Questo perché l’algoritmo per il parsing fa un uso intelligente della disposizione del testo (e quindi dell’indentazione).

Funzioni di ordine superiore

  • Miranda è un linguaggio di ordine superiore. Le funzioni possono essere passate sia come parametri, sia essere restituite come risultati.
  • L’applicazione delle funzioni si associa a sinistra, e dunque quando scriviamo “f x y”, viene interpretato come “(f x) y” il che significa che l’applicazione di f ad x dà come risultato una funzione, che viene poi applicata ad y.
  • Ogni funzione di due o più parametri è una funzione di ordine superiore. Questa tecnica è utile poiché ammette l’applicazione parziale delle funzioni.

Concetti base: Liste

  • La struttura di dati maggiormente usata è la lista che si scrive con le parentesi quadre e le virgole.
  • ++ concatena le liste.
  • : inserisce in testa alla lista un elemento.
  • # restituisce la lunghezza della lista.
  • nomeLista!i. restituisce l’i-mo elemento della lista.

Concetti base: esempio lista

  • Esempio di costruzione:

giorni_feriali= ["lunedi","martedi","mercoledi"]
giorni=giorni_feriali++["giovedì"]

  • Per le liste i cui elementi formano una serie aritmetica c’è una notazione abbreviata .. , cioè:

fatt n= product [1..100]

  • E’ possibile comprimere le liste utilizzando la teoria degli insiemi.

Compressione delle liste

  • Le liste possono essere compresse secondo le regola della teoria degli insiemi.
  • La compressione fornisce una sintassi concisa per una classe piuttosto generale di iterazioni sulle liste.

Esempio compressione

  • Se volessimo costruire una lista che contiene ordinatamente i quadrati di tutti i numeri da 1 a 100 utilizzando la compressione avremmo:

quadrato=[n*n | n <- [1..100]]

Compressione delle liste sintassi

  • La forma generale di una compressione di una lista è:

[corpo | qualificatori]

  • Ogni qualificatore è un generatore della forma “variabile <- espressione”, oppure è un filtro (espressione booleana).
  • Per comprimere la lista possiamo scegliere e utilizzare più generatori alla volta. Se sono presenti più generatori si utilizza il punto e virgola per separarli.

Vantaggi della compressione

  • La compressione permette espressioni molto concise.
  • Esempio 1: “Quicksort”:

sort [ ] =[ ]
sort (a : x) = sort [ b | b <- x; b <=a]
++ [ a ] ++
sort [ b | b <- x; b>a ]

Vantaggi della compressione

Esempio 2: il problema delle 8 regine.

  • Il problema delle 8 regine è un Costraint Satisfaction Problem (CSP) molto noto in Sistemi ad intelligenza distribuita.
  • Ha come scopo quella di assegnare una posizione ad 8 regine su una scacchiera in modo che nessuna regina dia “scacco” all’altra.
  • In entrambi gli algoritmi utilizziamo un euristica per abbassare il grado di complessità.

Esempio 8 regine (1)

  • In Miranda

regine 0 = [ [ ] ]
regine (n+1)= [q: b | b <- regine n ; q <- [0..7]; sicura q b ]
sicura q b = and [ _da_scacco q b i | i <- [0..#b-1] ]
da_scacco q b i = b ! I / abs (q – b!i)=i+1

Esempio 8 regine (2)

  • In Pseudocodice ling. Imperativo

function Min-Conflicts (csp, max_passi) returns una soluzione, o un fallimento
input: csp, la definizione del problema delle 8regine
max_passi: il numero di passi consentiti prima di abbandonare l’esecuzione
Current <- un assegnamento completo iniziale per csp
For i = 1 to max_passi do
if current è una soluzione del csp then return current
var <- una variabile in conflitto, scelta a caso in Variabili [csp]
valore <- il valore v di var che minimizza i conflitti(var,v,current,csp)
scrivi var=valore dentro current
Return fallimento
In più vanno ulteriormente aggiunte e specificate le funzioni di appoggio utilizzate e la definizione del problema in CSP.

Concetti base: Tuple

  • Se gli elementi da inserire in una lista non sono tutti dello stesso tipo allora bisogna utilizzare il concetto di tuple.
  • Una tupla si costruisce, anziché con le parentesi quadre, con le parentesi tonde:

impiegato = (“rossi”,true, false, 39)

  • Per fare un analogia possiamo vedere le tuple come record in pascal.

Le equazioni con guardia e la struttura a blocchi

  • Una equazione può avere più “lati destri”, scelti alternativamente grazie ai comandi con guardia.
  • La guardia si scrive ovviamente a destra dopo una virgola.

mdc a b = mdc (a-b) b, if a>b
= mdc a (b-a), if a
=a, if a=b


Nell’esempio precedente si esegue il massimo comune divisore, si sceglie una delle parti destre in base al comando con guardia.

  • E’ possibile aggiungere anche delle clausole where nei comandi con guardia, eventualmente anche annidati.

Pattern Matching alternativa alle guardie

  • Miranda permette di definire una funzione dando più alternative distinte dall’utilizzo di pattern diversi nei parametri formali.
  • Spesso questo metodo risulta più elegante rispetto all’uso delle guardie.

Pattern Matching VS Guardie

  • Esempi
    • Pattern Matching

fatt 0 =1
fatt (n+1) =(n+1)*fatt n

  •  
    • Guardia

fatt n= 1, if n=0
= n* fatt n-1, if n>0

Valutazione di tipo Lazy e liste infinite

  • Il meccanismo di valutazione di Miranda è lazy: nessuna sottoespressione viene valutata fino a quando non è necessario il suo valore analitico.
  • Conseguenza di questa scelta sono la possibilità di definire funzioni che sono capaci di restituire una risposta anche quando uno dei suoi parametri non è stato definito, e la possibilità di scrivere liste, o comunque strutture infinite di dati.

Valutazione di tipo Lazy e liste infinite

  • Esempio: Lista infinita di tutti i numeri primi, usando il crivello di Eratostene.
  • La lista dei potenziali numeri primi inizia con la lista dei numeri interi dal due in avanti; dopo che è stato restituito ciascun numero primo, tutti i numeri che possono essere divisi in modo esatto per esso vengono eliminati dalla lista dei candidati.

primes = sieve [2..]
sieve (p:x) = p : sieve [n | n <- x; n mod p ~= 0]

I tipi

  • Fortemente tipato: al momento della compilazione ogni espressione è di un tipo.
  • Tipi primitivi: num, bool e char.
  • Se T1 e T2 sono dei tipi, allora
  • T1->T2 è il tipo della funzione con parametri in T1 e risultati in T2
  • E’ possibile dichiarare i tipi di un espressione con il comando “::” per es:

sq :: num->num
sq n = n*n

Tipi definiti dall’utente

  • Si possono introdurre nuovi tipi con “::=”, per esempio:
    • albero ::= Nila | Nodo (num tree tree)

Questo introduce tre nuovi qualificatori, albero che è il nome del tipo, Nila e Nodo che sono i costruttori dell’albero

Ridefinizione di un tipo

  • E’ possibile anche ridefinire un tipo già esistente, grazie all’operatore “==” per esempio:
    • Stringa == [char]
    • Matrice == [[num]]

Così una lista di caratteri diventa di tipo stringa, e una lista bidimensionale di numeri una matrice.

Tipi di dati astratti (1)

  • Si possono anche definire tipi di dati astratti, vediamolo con un esempio
    • Dichiarazione astratta

Abstype pila * whit
vuota :: pila *
e_vuota :: pila * -> bool
push :: * -> * -> pila * -> pila *
pop:: pila * -> *
top:: pila * -> *

Tipi di dati astratti (1)

 

  • Implementazione

 pila * == [ * ] //* indica qualunque tipo
vuota = [ ]
e_vuota x = (x=[ ])
push a x = ( a: x)
pop (a:x)= x
top (a:x)=a

Compilazione separata e Linkaggio

  • Gli script Miranda possono essere inclusi in altri script con
    • %include “pathname”
  • E’ possibile esportare anche solo delle variabili o funzioni da un altro scritp con
    • %export name
  • La compilazione separata e il linkaggio degli script inclusi viene gestita automaticamente dal compilatore.

Ambiente di sviluppo iniziale

  • E’ un sistema interattivo che girava sotto Unix come sottosistema autosufficiente.
  • Il compilatore lavora con l’editor di testo (Vi, Vim, etc..), e una volta salvato lo script esso viene compilato segnalando immediatamente gli eventuali errori di sintassi o di tipo, e grazie al sistema di tipo polimorfico di rilevare anche alcuni errori logici.
  • Una volta salvato lo script, esso può essere invocato da terminale.
  • I compilatori sono disponibili al sito Miranda.

Stato attuale

  • Fino al 1997 è stato largamente utilizzato in ambito accademico.
  • Attualmente viene utilizzato per lo sviluppo di prototipi usa e getta.

I materiali di supporto della lezione

Clark, Myers, “Programming with Miranda”, Prentice Hall 1995

Thompson, “Miranda: The Craft of Functional Programming”, Wesley 1995

Thompson, “Laws in Miranda” ACM International Conference, august 1986

Springer Lecture Notes in Computer Science 201:1-16. Nancypaper

FROM SIGPLAN NOTICES, 21(12):158-166, December 1986. Overview

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion