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
 
 
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