[rosedu-general] Pure mathematics and programming

[Mihai Maruseac]

2011/11/4 Adrian Scoica <adrian.scoica at gmail.com>:
> Vreau sa scriu despre acest subiect de mai multa vreme, dar abia acum
> am fereastra si chef.
>
> Ceea ce programam se imparte in doua categorii:
> a) Tool-uri tehnologice (de exemplu, shell-uri, programe de baza,
> drivere, module de kernel...)
> b) Algoritmi
>
> Eu voi vorbi aici de a doua categorie, care mi se pare nu neaparat mai
> challenging sau mai frumoasa, dar cu siguranta mai greu de pus pe
> "hartie" cand implementezi. Motivul? Majoritatea rationamentelor
> matematice frumoase sunt formalisme. Termenii fibonacci se scriu f(x)
> = f(x-1) + f(x-2), f(0) = 0 f(1) = 1. Porning de aici, notam cu un
> simbol si putem scrie ecuatii cu ei la nesfarsit fara sa ne facem
> griji de faptul ca nu incap in 32 biti, de rang, de recursivitatea
> exponentiala, etc...
>
> Cand scrii un algoritm pentru o masina fizica, lucrurile nu mai stau
> asa de simplu. Trebuie sa iti "incapsulezi" rationamentul in
> limitarile fizice ale arhitecturii, si sa scoti hack-uri oribile care
> sa profite de memorie, si alte trait-uri tehnologice.
>
> Asta inseamna sa iti poluezi limbajul in care scrii cu constructii
> sintactice care nu au legatura cu algoritmul, un lucru care mie mi se
> pare gresit deoarece amesteci doua niveluri de exprimare in acelasi
> limbaj. Limbajele imperative sufera masiv de chestia asta, si au
> aparut doua solutii care sa le adreseze:
> a) Limbajele functionale
> b) Metalimbajul
>
> Limbajele functionale sunt extrem de elegante, dar pierd putin
> contactul cu realitatea. Trebuie translatate in cod imperativ ca sa
> poata fi executate, deci apare cortina de fier a compilatorului prin
> care programatorul nu mai poate vedea decat ceea ce i se arata.

I beg to differ. M-am uitat prin vară pe GHC să văd cum compilează
ceva simplu. Face enorm de multe translatări de la un limbaj
functional la următorul și tot așa până ajunge la STG (spineless
tagless G-machine) - o mașină asemănătoare cu Turing dar care poate fi
programată functional cu un subset al lambda-calculus. De acolo până
la imperativ nu mai e decât un pas.

Și programatorul are access la oricare din pașii făcuți de GHC dacă
vrea. Cel puțin așa zicea SPJ, n-am avut timp să verific.

> Pe de alta parte, C++ a ales o cale mai... obscura si aspru criticata:
> Metalanguage. Sau cu alte cuvinte, extinderea limbajului astfel incat
> sa se poata descrie singur. Din pacate, Metalanguage este inca black
> magic si curba de invatare e aproape verticala, In template
> metaprogramming putem scrie functii care se folosesc de gramtica
> limbajului C++ si sunt complet libre de contrangeri fizice, urmand ca
> apoi sa "instantiem" respectivul cod cu specificati reale. De exemplu:
>
> template<class N>
> bool search(N key, Collection<N>& container);
>
> Metafunctia de mai sus poate fi scrisa profitand de structura
> _algebrica_ a tipurilor N si Collection, fara a tine cont de modul in
> care sunt reprezentate si operate. In momentul in care scrii in cod
> search<int>(1, v), faci fitting la grupul algebric peste ceva real:
> tipul "int".

Deci programare declarativă :) Idee luată din limbajele din această
categorie si hack-uită în C++. Curba de învățare e mai verticală decât
în Haskell doar din cauza hack-ului, dacă nu ar fi fost hack-ish
implementarea și s-ar fi gqndit la asta de la început am fi avut un
C++ functional :) La fel e și-n Haskell cu unele concepte (Comonad,
Arrow, Iteratees, etc) sau chiar cu Template Haskell.

>
> Dar asta nu e tot ceva abstract? Well..., da si nu. Metafunctiile si
> metaclasele sunt scrise in acelasi limbaj ca si codul concret. Atunci
> cand scrii in cod search<int>, de fapt compilatorul iti "genereaza"
> respectiva functie ca si cum ai fi scris-o tu de mana, deci practic
> este un nivel distinct in compilare si nu introduce overhead la
> runtime (!! foarte important asta !!). Mai mult, folosind TMP, poti
> traversa granita dintre compile-time si run-time, specificand inclusiv
> executia de cod in timpul instantierii (de exemplu, preprocesari
> :-??).

Template Haskell :)

> In template metaprogramming am vazut cele mai frumoase si elegante
> implementari pentru lazy evaluation, function closures, si alte
> concepte ce tin de programarea functionala, despre care puteti citi
> aici[0]. C++0x o sa mai depaseasca o limitare a limbajului permitand
> function literals.
>
> Is this going in the right direction? Well, in mod clar implementarile
> nu mai sunt black box, ceea ce iti da un sentiment placut de control.
> Pe de alta parte, gramaticile devin rupte din iad (fun fact: g++ nu
> parseaza corect C++, m-am lovit de mai multe ori de asta).

Deci facem un franken-C++. Exact cum o sa avem un franken-Java, un
franken-C# (numit F# acum) și tot așa. Nu sunt împotrivă, consider un
semn bun faptul că din ce în ce mai mult se împumută features din
programarea functională (oare de ce? -- e mai greu să te obișnuiești
să gândești doar așa, cqnd ai nevoie de ceva functional apelezi la un
patch de ăsta și gata). Pe viitor, din ce în ce mai mult o să se
meargă pe direcția funcțională, lightweight threads (green threads),
STM, bracket, iteratees, etc. O să vezi cum o să se introducă și de
astea în C++ în câțiva ani, după ce se testează în Racket/Scheme și
Haskell și LISP.

>
> At the end of the day, totul tine de gustul personal al fiecaruia. Eu
> daca _chiar_ am nevoie de lazy eval si inchideri functionale, le
> prefer pe cele din Boost, altcineva ar putea prefera sa se orienteze
> spre alt limbaj... eventually, matematica este _unica_ stiinta reala.
> Restul e doar... stamp collecting.

Agree. Fiecare lucrează în ce e mai performant. Mie C++ mi se pare un
monstru colosal din cauza multitudinilor de features pe care le are,
de exemplu. Haskell e atractiv pentru mine din cauza purității și a
apropierii foarte mari de matematică.

Ce-am comentat nu se vrea a fi un bashing, doar comentariile mele
scurte pe subiectul ăsta. Oricum, ce zici de un articol pe techblog?