Laboratorul de Limbaje

Haskell este limbajul functional succesor al LISP-ului, Scheme-ului si ML-ului !!!
Cel mai productiv limbaj functional ! Limbajul folosit de autorii limbajului Perl 6 si ales de echipa Linspire, utilizat la Inteligenta artificiala, prelucrari multimedia, Retele Petri, programare functionala in Robotica, sinteza de circuite electronice ...
V-am starnit curiozitatea ? Cititi: Intrebarile incepatorului. Am adaugat raspunsuri noi (16 dec. 2007- 10 feb. 2008). Avem si Capitole de manual

. Haskell - instrument de realizare a interpretoarelor limbajelor

Datorita modului atat de simplu in care se pot defini in Haskell elementele unui translator limbajul Haskell se recomanda de la sine ca un DSL (domain specific language) pentru realizarea interpretoarelor si compilatoarelor. Astfel, in Haskell se definesc foarte usor:
- Textul de intrare vazut ca string si simultan ca lista de caractere (in Haskell tipul String avand ambele semnificatii)
- Atomii lexicali sunt recunoscuti de parsere specializate, deja existente in biblioteci cum sunt ParseLib si Parsec (sau altele ...)
- Gramaticile, inclusiv cele ambigue sunt imediat transcrise (in asa-zisa do-notatie) sub forma unor secvente de parsere corespunzatori neterminalelor gramaticii. Alternativa "|" beneficiaza de un operator special (+++ in ParseLib) Suportul teoretic, structura algebrica ce permite combinarea efectelor parserelor este Monada Parserelor.
- Arborii sintactici, inclusiv cei polimorfici, se transcriu imediat in Haskell folosind declaratia "data" (destinata tipurilor utilizator). Descrierea structurilor de date pentru reprezentarea arborilor sintactici se poate face pe unul - doua -trei randuri. Deoarece in Haskell la o declaratie "data" se poate adauga "deriving Show", noul tip de date va fi implicit inzestrat cu functie de afisare, pe care programatorul nu mai este obligat s-o scrie el. Simpla modificare a declaratiei "data" a arborilor modifica automat (transparent) functia de afisare. Ideal pentru realizarea prototipurilor.
- Semantica se poate transcrie in do-notatie, dar folosind de obicei o alta monada decat monada parserelor. Nu sunt necesari operatori specializati pentru lifting-ul functiilor uzuale in universul monadei, asa cum se proceda pe vremea cand Espinosa scria la teza sa de doctorat, celebra teza despre "Semantic Lego". Descarcati de aici Transcrierea_semanticii_in_do_notatie.pdf un capitol dintr-o carte de Dan Popa, destinat a introduce cititorul in tehnicile de exprimare a semanticilor in do-notatie(163KB, MIME type: application/pdf). Dovedeste totodata superioritatea Haskell-ului asupra altor limbaje functionale mai vechi (LISP,SCHEME), in priviinta posibilitatilor de a transcrie semantici in el si explica necesitatea indeplinirii Legilor Monadei.
- Prelucrarile recursive de arbori atat de necesare la parcurgerea arborilor, la listarea unui arbore sintactic (pretty printing) se scriu imediat deoarece Haskell permite definirea de functii recursive, ca succesiuni de ecuatii.
La urma dar nu in cele din urma: Compilatorul de Haskell GHC este el insusi scris in Haskell. Ceea ce spune tot ce este de spus despre Haskell ca limbaj (DSL) de scriere a compilatoarelor.
Cum sa scrii un mic limbaj, aici era o implementare de Scheme. A aparut si sub forma de wikibook. Vedeti si pagina de proiecte.

. Lisp si Scheme

Interpretor pentru Scheme (un fel de Lisp), versiune pentru Windows. Compilata din surse ale Comunitatii Haskell asa cum sunt ele prezentate intr-un faimos Wikibook. - Download pe riscul dumneavoastra. Atentie: au fost probleme la download-uri.

1)Cum se despacheteaza: Fisierul descarcat este numit: Scheme-listing10.arhivagz. Dati un click dreapta, alegeti redenumire si stergeti cuvantul arhiva din extensie. Ramane: Scheme-listing10.gz. Dezarhivati fisierul cu orice arhivator care admite formatul .gz - GZip. Sub Linux cu interfata grafica se poate folosi File Roller. Sub Linux cu interfata text recurgetiu la gunzip. Arhivatoarele Windows care reunosc .zip-uri pot dezarhiva si fisiere .gz. Verificati totusi. Inauntru arhivei gasiti un fisier: Scheme-listing10.exe.

2) Biblioteca minimala cu definitii de functii Scheme este data mai jos. (dupa carte :). Salvati acest text cu multe paranteze sub numele: stdlib.scm

Stdlib.scm
----------------------------------------
(define (caar pair) (car (car pair)))
(define (cadr pair) (car (cdr pair)))
(define (cdar pair) (cdr (car pair)))
(define (cddr pair) (cdr (cdr pair)))
(define (caaar pair) (car (car (car pair))))
(define (caadr pair) (car (car (cdr pair))))
(define (cadar pair) (car (cdr (car pair))))
(define (caddr pair) (car (cdr (cdr pair))))
(define (cdaar pair) (cdr (car (car pair))))
(define (cdadr pair) (cdr (car (cdr pair))))
(define (cddar pair) (cdr (cdr (car pair))))
(define (cdddr pair) (cdr (cdr (cdr pair))))
(define (caaaar pair) (car (car (car (car pair)))))
(define (caaadr pair) (car (car (car (cdr pair)))))
(define (caadar pair) (car (car (cdr (car pair)))))
(define (caaddr pair) (car (car (cdr (cdr pair)))))
(define (cadaar pair) (car (cdr (car (car pair)))))
(define (cadadr pair) (car (cdr (car (cdr pair)))))
(define (caddar pair) (car (cdr (cdr (car pair)))))
(define (cadddr pair) (car (cdr (cdr (cdr pair)))))
(define (cdaaar pair) (cdr (car (car (car pair)))))
(define (cdaadr pair) (cdr (car (car (cdr pair)))))
(define (cdadar pair) (cdr (car (cdr (car pair)))))
(define (cdaddr pair) (cdr (car (cdr (cdr pair)))))
(define (cddaar pair) (cdr (cdr (car (car pair)))))
(define (cddadr pair) (cdr (cdr (car (cdr pair)))))
(define (cdddar pair) (cdr (cdr (cdr (car pair)))))
(define (cddddr pair) (cdr (cdr (cdr (cdr pair)))))

(define (not x)            (if x #f #t))
(define (null? obj)        (if (eqv? obj '()) #t #f))
(define (id obj)           obj)
(define (flip func)        (lambda (arg1 arg2) (func arg2 arg1)))
(define (curry func arg1)  (lambda (arg) (func arg1 arg)))
(define (compose f g)      (lambda (arg) (f (g arg))))

(define (foldl func accum lst)
  (if (null? lst)
      accum
      (foldl func (func accum (car lst)) (cdr lst))))

(define (foldr func accum lst)
  (if (null? lst)
      accum
      (func (car lst) (foldr func accum (cdr lst)))))

(define (unfold func init pred)
  (if (pred init)
      (cons init '())
      (cons init (unfold func (func init) pred))))

(define fold foldl)
(define reduce fold)

(define zero?              (curry = 0))
(define positive?          (curry < 0))
(define negative?          (curry > 0))
(define (odd? num)         (= (mod num 2) 1))
(define (even? num)        (= (mod num 2) 0))
(define (max x . num-list) (fold (lambda (y z) (if (> y z) y z)) x num-list))
(define (min x . num-list) (fold (lambda (y z) (if (< y z) y z)) x num-list))
(define (list . objs)       objs)
(define (length lst)        (fold (lambda (x y) (+ x 1)) 0 lst))
(define (append lst . lsts) (foldr (flip (curry foldr cons)) lst lsts))
(define (reverse lst)       (fold (flip cons) '() lst))
(define (mem-helper pred op) (lambda (acc next) (if (and (not acc) (pred (op next))) next acc)))
(define (memq obj lst)       (fold (mem-helper (curry eq? obj) id) #f lst))
(define (memv obj lst)       (fold (mem-helper (curry eqv? obj) id) #f lst))
(define (member obj lst)     (fold (mem-helper (curry equal? obj) id) #f lst))
(define (assq obj alist)     (fold (mem-helper (curry eq? obj) car) #f alist))
(define (assv obj alist)     (fold (mem-helper (curry eqv? obj) car) #f alist))
(define (assoc obj alist)    (fold (mem-helper (curry equal? obj) car) #f alist))

(define (map func lst)      (foldr (lambda (x y) (cons (func x) y)) '() lst))
(define (filter pred lst)   (foldr (lambda (x y) (if (pred x) (cons x y) y)) '() lst))

(define (sum . lst)         (fold + 0 lst))
(define (product . lst)     (fold * 1 lst))
(define (and . lst)         (fold && #t lst))
(define (or . lst)          (fold || #f lst))
(define (any? pred . lst)   (apply or (map pred lst)))
(define (every? pred . lst) (apply and (map pred lst)))
----------------------------------------------------------------

Observati ca trecerea de la Lisp la Scheme nu este grea (defun devine define samd) iar trecerea de la Scheme la Haskell nu este imposibila. Multe cuvinte din Scheme se folosesc si in Haskell (le aveti marcate cu verde). Daca dati click pe le obtineti Help-ul functiilor Haskell cu acelasi nume, nu al celor Scheme. De acord, deosebirile nu sunt mari.

Urmeaza sa mai explic cate ceva...Reveniti.

. Prolog (Programming in Logic) - Programare folosind logica matematica

Prolog Este un limbaj de programare logica. Veniti de data aceasta la curs sa va spun mai multe. Personal l-am folosit in studiul matematicii ca instrument de accelerare al proceselor de deductie. A facut practic el (interpretorul Prolog) demonstratiile pentru mine, pe multiple cazuri. Este acel limbaj care in anii 80 era propus ca limbaj al generatiei a 5-a de calculatoare. Se (mai) foloseste inca in domeniul IA si nu numai acolo. A dat nastere altor limbaje: datalog. Vedeti si pe draft-ul personal in cartea despre Oberon la capitolul destinat paradigmelor limbajelor. cititi din prima carte din Romania in care am scris ceva despre Haskell PDF Pascal-ul mileniului al III-lea. de Dan Popa. Programare calculatoarelor in Oberon-2, ... Download ] La pagina 28 e un paragraf despre el.

Procurati-va o carte despre Prolog sau macar notite de curs.

Nota: Deoarece un motor de inferente Prolog (Cum este Andora engine) poate fi implementat / este implementat usor in Haskell puteti include Prolog in orice DSL (domain small language) daca sunteti constructor de limbaje.

Altfel: Mizati pe o versiune de prolog deja existenta: ... pagina in dezvoltare.

. Rodin

Limbajul Pseudocod Rodin este destinat a fi folosit la invatarea informaticii, mai exact la orele de algoritmistica din primul trimestru (de la sectiile Mate-Info). Deocamdata pina la vectori unidimensionali (inclusiv). Cautati RodinV082b sau versiunile ulterioare: Rodin Codename ExperimentExp12 din 29-31 aug 2009.. Detalii mai precise gasiti intotdeauna pe pagina Rodin.

Limbajul Rodin a fost subiectul a doua lucrari (comunicari) una didactica si una tehnica prezentate la ICMI2-2009.

. L. Expert

L. Expert

Acum catuva ani am lucrat ocazional (cam cat un concediu) la implementarea in Haskell a limbajului L.Expert. Deoarece cartea dupa care am facut documentarea era plina de greseli de tipar si tehnice si interpretorul limbajului incepuse sa dea erori (mai ales sintactice) cu propriile surse ale autorului ( caruia nu-i dam numele pentru a-l proteja) si deoarece acesta contactat nu a vrut/reusit/putut sa se implice in continuarea proiectului, acest proiect de implementare a L.Expert este deocamdata fara "maintainer" fiind suspendat. Voi decide eventual sa-l scot in zona Open source, daca e cazul. Doritori ? Scrieti un mail la domnul PopaVDan (cu minuscule) pe serverele de la yahoo.com.

. Expression problem: news from 2008-2009

Va intereseaza asazisa Expression Problem. Cititi despre o solutie a ei la pagina numita Pseudoconstructors over monadic values. O solutie data in 2008 este disponibila si o gasiti aici: Pseudoconstructors over monadic values.

. Automate

Nu puteau lipsi de la un laborator de limbaje. La Univ. din Bacau au fost descoperite automatele finite deterministe adaptive. ADFA Click pentru detalii.