Linguaggio funzionale
Haskell è
un linguaggio funzionale originato nel 1987 dal lavoro del comitato Haskell (Hughes,
Wadler, Peterson et al), la versione 1.0 è stata definita nel
1990. Il linguaggio deve il suo nome al matematico e logico Haskell
B. Curry (1900 – 1982).
L’utilizzo di Haskell è proprio degli ambiti accademici e di ricerca, in particolare è stato utilizzato per sviluppare interpreti per linguaggi specializzati, i cosiddetti small Domain Specific Language (DSLs) come Fran un linguaggio per animazioni interattive e Haskore un linguaggio per la musica a computer.
Ogni espressione di Haskell ha un tipo, che può essere dichiarato o dedotto dall’utilizzo. I tipi nativi in Haskell comprendono i tipi numerici Int e Double, i tipi Bool e Char, inoltre Haskell prevede le classi di tipi (class type), ad esempio Int e Double appartengono alla classe Num, ma appartengono anche alla classe Eq, dalla quale derivano le possibilità di confronto per uguale (==) e diverso (/=), mentre gli operatori relazionali sono derivati dalla classe Ord. Si tratta di qualcosa di analogo agli oggetti ad ereditarietà multipla. Fra le classi è particolarmente importante il sottoinsieme di classi Monadiche (Monadic Classes).
E’ possibile dichiarare propri tipi di dato ed indicare eventualmente che ereditano i metodi di certe classi, ad esempio Eq e Show, per permetterne il confronto e la visualizzazione, ciò si ottiene o tramite la clausola deriving nomeclasse o dichiarando il tipo come istanza di una classe, con la possibilità di specificarne il comportamento:
module Main where data Assoc anytype
= Dict {key :: String, value :: anytype} deriving Show instance
(Eq a) => Eq (Assoc a) where
-- come effettuare il confronto
(Dict _ b) == (Dict _ b') = b == b' dict1 = Dict "alfa"
"aleph" dict2 = Dict "beta"
"bet" dict3 = Dict "aleph"
"aleph" dict4 = Dict
"lista" [7..13]
-- .. generatore di sequenze numeriche |
Main>[1] dict1 == dict3 True Main> dict1 ==
dict2 False Main> key dict3 -- utilizzo del nome di campo "aleph" Main> dict4 Dict{key="lista",value=[7,8,9,10,11,12,13]} |
Nell’esempio si è dichiarata il tipo di dato Assoc che contiene il costruttore Dict con un campo di tipo String, ed un campo, il cui tipo anytype indica un tipo variabile e quindi permette un qualsiasi tipo di dato. Ai due campi è stato assegnato un nome, rispettivamente key e value. In quanto alla derivazione di proprietà da altre classi, con deriving Show è stata data la possibilità di visualizzare il contenuto di un’istanza del tipo e con instance (Eq a)... si è reso possibile utilizzare l’operatore == in modo tale da considerare due istanze di dict uguali se i loro campi value sono uguali.
Sono possibili tipi di dato enumerati: data Colore = Rosso | Verde | Blu.
E’ possibile dichiarare propri tipi di
dato indicando la o le funzioni per costruirli. Si possono dichiarare dati
analoghi ai record o alle strutture di certi linguaggi, oppure dati ricorsivi
come gli alberi. In Figura
2-7
c’è un esempio del primo genere, una tupla di dati con la
sintassi per dare un nome ai componenti. Nell’esempio di Figura
2-8
il tipo di dato Compiled è utilizzato per tradurre un sorgente di un linguaggio di
programmazione ed ogni costruttore è relativo alle istruzioni da tradurre; è
un esempio di tipo con costruttori in alternativa. Qui di seguito un esempio di
dati ricorsivi, una struttura ad albero per memorizzare delle espressioni
aritmetiche con parentesi ed una funzione (frm)
per estrarre l’espressione contenuta nella istanza di Tree.
data Tree a b = Foglia a | Ramo b (Tree a b) (Tree a
b) deriving Show albero = Ramo "+"
(Foglia 3)
(Ramo "*"
(Foglia 7)
(Foglia 5)) frm
(Foglia x)
= show x frm (Ramo op
sin des) = "(" ++ frm sin ++ op ++ frm des ++ ")" |
Recurse>
albero Ramo "+" (Foglia 3) (Ramo
"*" (Foglia 7) (Foglia 5))
Recurse> frm
albero "(3+(7*5))" |
Le liste sono una componente essenziale di Haskell, i costituenti possono essere di qualsiasi tipo, anche frammenti di programma, ma omogenei; il tipo String è definito come una lista di Char. La scrittura [n..m] indica la lista formata dagli interi da n ad m. Esistono le funzioni per ottenere il primo elemento di una lista e la lista restante (head e tail), la funzione dimensione length e le funzioni con funzioni: map, filter, foldr e foldl. Queste, come molte altre, sono in realtà costruite sul nucleo del linguaggio e definite nella libreria[2] Prelude. Un esempio di map e filter è il seguente dove si è definita la funzione count per contare gli elementi di una lista che soddisfano ad una determinata condizione, cond è ovviamente una variabile booleana, ma la variabile lista può essere una lista di tipi di dato qualsiasi (polimorfismo):
count cond
lista = length (filter cond lista) Main>
map (* 3) [1..13] [3,6,9,12,15,18,21,24,27,30,33,36,39]
Main>
count odd (map (* 3) [1..13]) 7 Main>
(/= 'o') `count` "Condor"
-- count infisso 4 |
Si noti nell’esempio come Haskell permetta di utilizzare le funzioni
binarie in modo infisso ((/= 'o') `count` "Condor").
I due operatori : e ++ producono liste, il primo, più propriamente detto costruttore, genera una lista a partire da un costituente elementare ed una lista, il secondo concatena due liste:
Prelude>
1:[5] -- costruttore
[1,5]
Prelude>
[1]++[5] -- concatenatore
[1,5]
E’ possibile indicare liste aperte, di fatto, nel caso dei numeri, liste infinite: [n..], ed operare su di esse finitamente, grazie alla valutazione lazy che Haskell effettua:
Prelude> take 10 ['w'..]
-- prelevo 10 caratteri ASCII a partire da w
"wxyz{|}~\DEL\128"
Prelude> take 5
[x | x <- [3..] , odd x] -- list comprehension
[3,5,7,9,11]
Il secondo esempio illustra un modo “insiemistico” (list comprehension) di costruire una lista (equivalente a take 5 (filter odd [3..])) .
In Haskell è possibile dichiarare il tipo di dato in una funzione o lasciare al linguaggio il compito di dedurlo, ed il tipo di dato dedotto è il più generale possibile, ad esempio la funzione sole elimina gli elementi duplicati da una lista di qualsiasi tipo:
sole [] =
[] -- drops doubles
sole (x:xs) =
if (count (== x) xs) > 0 then sole xs else x:(sole xs)
Compile> sole
[1,2,3,3,2,1]
[3,2,1]
Compile> sole
"Condor Informatique - Turin"
"CdIfomatqe- Turin"
Poiché le funzioni sono tipi di dato, ci sono degli operatori su di esse, come . (punto), e $. $ permette di evitare le parentesi, . combina le funzioni:
Prelude>
sin (sqrt 2)
0.987766
Prelude>
sin $ sqrt 2
0.987766
Prelude>
(sin . sqrt) 2
0.987766
pitagora :: Int -> Int -> Int -> Bool pitagora
a b c | a^2 == b^2 + c^2 = True
| b^2 == a^2 + c^2 = True
| c^2 == a^2 + b^2 = True
| otherwise = False |
La funzione sole, vista in precedenza, è un esempio di dichiarazione di funzione per pattern, cioè basata sul formato dei valori di input; oltre a questo modo di indicare le funzioni ed a quello usuale, si può indicare un elenco di espressioni alternative dipendenti da condizioni booleane (guarded expressions) come nell’esempio qui riportato.
if condizione
then ... else ... case condizione
of True -> ...
False
-> ... |
La struttura condizionale principale è case, che implicitamente è alla base del pattern matching, anche if then else ne è un caso particolare, inoltre i tipi di dato Maybe ed Either, sono tipi di dato condizionali.
La parte procedurale di cui tutti i
linguaggi funzionali necessitano, non fosse altro che per interagire con
l’ambiente, o per catturare gli aspetti temporali di un’elaborazione, è in
Haskell risolta nel concetto di Monade, concetto che deriva dalla Teoria
delle Categorie. Le monadi sono utilizzate “nativamente” in Haskell per
l’input e l’output[3],
ed a livello programmazione per trattare problemi con eccezioni, parsificazione,
non determinismo, processi concorrenti, ecc…
Per sottolineare che le operazioni con le Monadi non sono funzioni, queste sono dette azioni, e si utilizza l’operatore <- per prelevarne il risultato: lhs <- readFile ("tpk.lz").
La classe Monad ha due operatori nativi, >>= (bind) e return. Il primo è utilizzato per rendere sequenziali una serie di operazioni sulla Monade, ed è nella pratica sostituito da do, con le azioni coinvolte scritte indentate. L’operatore return immette un valore nella monade.
Diversi
moduli di librerie offrono ad Haskell funzionalità quali accessi a servizi del
sistema operativo, funzioni di input/output, gestione di date-ore, generatori di
numeri casuali, ecc….
I
commenti sulla riga sono individuati da --,
i blocchi commentati sono racchiusi fra {-
e -},
inoltre Haskell accetta anche
programmi in forma detta literate, questi possono essere in formato LATEX
o un testo descrittivo in cui le istruzioni sono individuate da: >.
L’esempio
che segue è un’interprete di un sorgente in Laning
and Zierler System
(v. 2.39
), e produce un sorgente in ALGOL
(v. 2.5
).
module
Compile where data
Compiled = Assign String String | Comment String | Goto String |
Label String | If String | Print String | Forcycle String |
Variable String | ArrayVar String | Nulla deriving Show
instance
Eq Compiled where
-- conditions for using ==
Nulla ==
Nulla = True
Variable a == Variable a' = a == a'
ArrayVar a == ArrayVar a' = a
== a'
_ == _ = False
takelab s
= head (words (s ++ " ."))
-- take label instr s =
head (words s)
-- take command wordn n s
= if n <= length (words s) then (words s !!) (n-1) else "" clean [] =
[]
--
drops ending spaces and comma clean s
| last s == ' ' || last s == ',' = clean (init s)
| otherwise = s compile
:: String -> Compiled compile s
= examen (clean s)
examen
:: String ->
Compiled examen s
| words s == [] = Nulla
| (foldr (&&) True (map isDigit (takelab s)))
-- if label
= Label ("lb" ++ takelab s ++ ":")
| instr s == "CP" = If (last (words s))
| instr s == "SP" = Goto (last (words s))
| instr s == "PRINT" = Print (last (words s))
| tail (wordn 1 s) == "|N" = Forcycle (for (wordn 3 s)
(take 1 (wordn 1 s)))
| (wordn 2 s) == "=" = Assign (scan(instr s)) (scan(wordn
3 s))
| otherwise = Comment s
takevar
:: String -> Compiled --
take variables takevar s
| (wordn 2 s) == "=" && length (wordn 1 s) == 1
= Variable (wordn 1 s)
| (wordn 2 s) == "=" = ArrayVar (take 1 (wordn 1 s))
| otherwise = Nulla
count p l
= length (filter p l) sole []
= []
-- drops doubles (used for variable declaration) sole (x:xs)
= if (count (== x) xs) > 0 then sole xs else x:( sole xs) generate
:: Compiled -> String generate (Assign
s t) = " "
++ s ++ " := " ++ t ++ ";" generate
(Goto s)
= " goto lb"
++ s ++ ";" generate (If
s)
= " if e
< 0 then goto lb" ++ s ++ ";" generate (Label
s) = s generate (Print
s) = " vprint
(" ++ s ++
");" generate (Comment
s) = " ;comment
" ++ s ++
";" generate (Variable
s) = " real
" ++ s ++ ";" generate (ArrayVar
s) = " real
array " ++ s ++ "[0:100];" generate (Forcycle
s) = " "
++ s generate
Nulla
= "" isProd ::
Char -> Char -> Bool
-- verify product operator omission isProd x y
| isDigit x && isAlpha y = True
-- e.g. 9F or 9a
| isLower x && (isDigit y || isLower y ) = True
-- e.g. a9 or ab
| (isLower x || isDigit x) && y == '(' = True
-- e.g. a( or 9(
| (x == ')' || x == ']') && (isLower y || isDigit y) =
True
| otherwise = False takedigits
[] = []
-- take digit(s) takedigits
(x:xs) | isDigit x = [x] ++ takedigits xs
| otherwise = [] scan []
= [] --
scan and replace scan ('F':'1':'1':xs)
= "sqrt" ++ scan xs
-- F11 is square scan ('F':'1':xs)
= "abs" ++ scan xs
-- F1 is absolute
value scan
('|':y:xs) | isLower y = ['['] ++ [y] ++ scan ([']']++ xs)
| isDigit y = do let ss = takedigits ([y] ++ xs)
let ll = length ss - 1
['['] ++ ss ++ scan ([']']++ drop ll xs) scan (x:y:xs)
| isProd x y = [x]++['*']++scan ([y]++xs)
-- insert * for multiply scan (x:xs)
= [x] ++ scan xs for ::
String -> String -> String
-- generate call at sub for step until for x v =
do let forsu = (break ('('==) x)
let step = break (==')') (tail (snd forsu))
let until = tail (snd step)
"cycle("++v++","++fst forsu++","++fst
step++","++until++");" process
:: String -> (String) process
lhs = es
where bs = divide (lines lhs)
is = map compile bs
-- make instructions
vs = sole(map takevar bs)
-- take variables
js = map generate
(filter (/= Nulla) (vs ++ is))
es = unlines (js ++ ["end"])
-- add ALGOL
delimiter
divide []
= [] divide (x:xs)
= take 5 x :drop 5 x: divide xs
-- split instructions
main
:: IO () main
= do putStr("Laning Zierler System Interpreter\nCondor
Informatique Turin\n")
lhs <- readFile ("tpk.lz")
let hs = process lhs
lcs <- readFile("cycle.A60")
writeFile ("tpk.A60") (lcs++hs)
-- insert sub for step until
putStr (lcs++hs)
|
Figura
2
-
8