[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Teoria jezyków programowania. Literatura.

Andrzej 'Rudy' Dabrowski

9/28/2006 8:45:00 PM

Chcia3bym poznaa jakimi prawami rz?dz? sie jezyki programowania. Chodzi mi
przede wszystkim o podwaliny matematyczne, ale nie tylko. W sumie cie?ko
zadaa pytanie, bo do konca sam nie wiem, czego chce (nic o tym nie wiem i
cie?ko mi znale?c w googlach informacje - to jest najgorsze). Jak wiadomo,
jezyki funkcyjne s? "czysto matematyczne" (nie w pe3ni, ale cze?ciowo, np.
maj? "pure functions", jak Haskell).
http://en.wikipedia.org/wiki/Programs_as_mathematic... - tutaj jest
troche o Johnie Backusie i jego dywagacjach na temat "u?ci?lenia" jezyków
programowania. Takie informacje mnie interesuj?. Szukam gdzie?
skondensowanego materia3u (na razie ogólnego, nie ma sensu wchodzia na
g3ebiny bez podstaw) na tematy dotycz?ce teorii jezyków programowania,
czyli np. teoria typów, rachunek lambda (z typami, bez), monady i ogólnie
relacje matematyka <-> programowanie. Ich historia, cel powstania. Czy da
sie np. paradygmat obiektowy i terminy z nim zwi?zane umie?cia w
przestrzeni matematycznej. Ostatnio na pclc kto? pisa3, ?e "typ" jest
terminem teoriomnogo?ciowym. (chociaz nie wiem, czy w koncu pisz?cy doszli
do porozumienia w tej sprawie ;-)). To mo?e tez teoria mnogo?ci wchodzi w
rachube. No mówie... nie znam sie i chcia3bym sie poznaa, ale kompletnie
nie wiem jak zacz?a. Skakanie po Wikipedii nie jest ani wygodne, ani 3atwe,
ani uporz?dkowane i s?dze, ?e przez to mo?e bya ma3o efektywne (w sumie to
jest).

W sumie nie chcia3bym te?, ?eby mia3o to styczno?c z super wy?sz?
matematyk?, chocia? jak sie nie da inaczej to okej ;) Jeszcze jej nie
posiadam, ale z czasem wszystko przyjdzie.

Mam nadzieje, ?e rozumiecie mój problem i przede wszystkim wiecie lepiej ode
mnie, czego chce sie nauczya ;-) Bo ja niby wiem, ale nie potrafie tego
dobrze opisaa. Z góry wielkie dzieki za zrozumienie moich rozterek!

--
Pozdrawiam, Andrzej
8 Answers

Darek Kubiczek

9/29/2006 8:56:00 AM

0


Andrzej 'Rudy' Dabrowski napisal(a):
> Chcialbym poznac jakimi prawami rzadza sie jezyki programowania. Chodzi mi
> przede wszystkim o podwaliny matematyczne, ale nie tylko. W sumie ciezko
> zadac pytanie, bo do konca sam nie wiem, czego chce (nic o tym nie wiem i
> ciezko mi znalezc w googlach informacje - to jest najgorsze).

[...]

Wydaje mi sie ze ponizsza pozycja moze byc tym czego szukasz:

http://helion.pl/ksiazki/...

D.

Rob Wolfe

9/29/2006 12:31:00 PM

0


Andrzej 'Rudy' Dabrowski wrote:
> Chcialbym poznac jakimi prawami rzadza sie jezyki programowania. Chodzi mi
> przede wszystkim o podwaliny matematyczne, ale nie tylko.

Jesli chodzi o zwiazki programowania z matematyka abstrakcyjna,
to w tym temacie rzadzi "Sztuka programowania" Donalda E. Knutha [1].
Niestety trudno nazwac te ksiazke "skondensowana", ale na dlugie
zimowe wieczory jak znalazl. :)

[1] http://www.wnt.com.pl/product.php?action=0&prod_id=86...

pozdrawiam
Rob

Sebastian Kaliszewski

9/29/2006 3:42:00 PM

0

Andrzej 'Rudy' D?browski wrote:
> Chcia3bym poznaa jakimi prawami rz?dz? sie jezyki programowania. Chodzi mi
> przede wszystkim o podwaliny matematyczne, ale nie tylko. W sumie cie?ko
> zadaa pytanie, bo do konca sam nie wiem, czego chce (nic o tym nie wiem i
> cie?ko mi znale?c w googlach informacje - to jest najgorsze). Jak wiadomo,
> jezyki funkcyjne s? "czysto matematyczne" (nie w pe3ni, ale cze?ciowo, np.
> maj? "pure functions", jak Haskell).

Hasell stara sie bya taki "w pe3ni"

> http://en.wikipedia.org/wiki/Programs_as_mathematic... - tutaj jest
> troche o Johnie Backusie i jego dywagacjach na temat "u?ci?lenia" jezyków
> programowania. Takie informacje mnie interesuj?. Szukam gdzie?
> skondensowanego materia3u (na razie ogólnego, nie ma sensu wchodzia na
> g3ebiny bez podstaw) na tematy dotycz?ce teorii jezyków programowania,
> czyli np. teoria typów, rachunek lambda (z typami, bez), monady i ogólnie
> relacje matematyka <-> programowanie. Ich historia, cel powstania. Czy da
> sie np. paradygmat obiektowy i terminy z nim zwi?zane umie?cia w
> przestrzeni matematycznej.

Zapwene sie jako? sie da (bo i czemu nie), ale nie widzia3em rozs?dnych prób
uczynienia tego? (choa ja te? i ma3o widzia3em). Gros literatury za zakresu
ró?nych ró?nistych stricte formalnych rozwa?an dotyczy jezyków funkcyjnych,
albo "logikowych" (koledzy Prologa).

> Ostatnio na pclc kto? pisa3, ?e "typ" jest
> terminem teoriomnogo?ciowym. (chociaz nie wiem, czy w koncu pisz?cy doszli
> do porozumienia w tej sprawie ;-)).

Nie, nie doszli ;-)

Proble te? poniek?d taki, ?e to co w jezykach czysto funkcyjnych opisuje sie
3adnie matematycznie (typy = zbiory warto?ci, itd) przestaje sie tak
opisywaa w przypadku systemów obiektowych. Pierwszy ból to taki, ?e takie
systemy "nie lubi?" opisywaa zamknietego ?wiata (a ró?ne formalizmy taki
?wiat "kochaj?"), z za3o?enia mog? pojawiaa sie nowe warto?ci, nowe
podklasy, itd -- st?d np. traktowanie typów jako zbiorów robi sie bez sensu
(i mo?na 3atwo dyskusje zredukowaa do absurdu -- co te? uczyni3em na p.c.l.c
;) ).

> To mo?e tez teoria mnogo?ci wchodzi w
> rachube. No mówie... nie znam sie i chcia3bym sie poznaa, ale kompletnie
> nie wiem jak zacz?a. Skakanie po Wikipedii nie jest ani wygodne, ani 3atwe,
> ani uporz?dkowane i s?dze, ?e przez to mo?e bya ma3o efektywne (w sumie to
> jest).
>
> W sumie nie chcia3bym te?, ?eby mia3o to styczno?c z super wy?sz?
> matematyk?, chocia? jak sie nie da inaczej to okej ;) Jeszcze jej nie
> posiadam, ale z czasem wszystko przyjdzie.

Mo?e troszke z innej beczki, ale te? i mo?e to co? rozja?ni:
Niemal od pocz?tku (Fortran vs Lisp) jezyki programowania rozwijane by3y w
(przynajmniej) dwu ró?nych kierunkach i z (przynajmniej) dwu ró?nych punktów
ten rozwój ruszy3.
1. Kierunek "In?ynierski" (Fortran)
2. Kierunek "Matematyczny" (Lisp)
Co nie znaczy, ?e np. nie mo?na dowodzia poprawno?ci programu w Fortranie
anie ?e w Lispie nie robiono biznesowych systemów.

>
> Mam nadzieje, ?e rozumiecie mój problem i przede wszystkim wiecie lepiej ode
> mnie, czego chce sie nauczya ;-) Bo ja niby wiem, ale nie potrafie tego
> dobrze opisaa. Z góry wielkie dzieki za zrozumienie moich rozterek!
>

Problem jest z3o?ony. Mo?na sie zainteresowaa ró?nymi jego aspektami...

1. Modele obliczen (Teoria Jezyków, Teoria Obliczen) -- jezyki formalne,
kalsy odpowiadaj?cych im gramatyk i rozpoznaj?ce je maszyny -- jezyki
regularne, wyra?enia regularne i automaty skonczone, jezyki bezkontekstowe
gramatyki bezkontekstowe i (niedeterministyczne) automaty ze stosem, jezyki
(cze?ciowo) obliczalne i maszyny Turinga (pomiedzy dwiema ostatnimi s?
jeszcze jezyki kontekstowe i jezyki ca3kowicie obliczalne (rozstrzygalne) ).

2. Poprawno?a programów (logika Hoare'a, itd...)

3. Ró?ne sposoby zapisywania semantyki (w tym typów). Rachunek lambda,
semantyki denotacyjne, operacyjne i ró?ne inne.

ad 1. Tu mamy ró?ne ciekawe rzeczy zwykle niezale?ne od jezyków -- to s?
niejako podstawy samej informatyki jako nauki (obok teorii informacji). Tu
mamy takie zagadnienia jak z3o?ono?a obliczeniowa problemów samych w sobie
(okazuje sie, ?e niezale?nie od modelu obliczen ró?ne problemy daj? sie
rozstrzygaa a inne nie; istniej? te? silnmie niezale?ne od modelów obliczen
klasy z3o?noo?ci problemów -- jedne liczy sie szybko innych nie da sie w
?adnym rozs?dnym czasie ruszya).

ad 2. Tu mamy "zabawy" zarówno formalno-matematyczne jak i in?ynierskie (np.
dowodzenie tzw. cze?ciowej poprawno?ci i systemy weryfikacji dowodów).
Stosuje sie to czasem w rzeczywistych systemach (np. w firmie Lokheed
niektóre oprogramowanie kontroluj?ce samoloty jest formalnie dowodzone).

ad 3. To w3a?ciwie domena "pozain?ynierska", co? dla tych co lubi? "babraa
sie" w "?cis3ym definiowaniu do ostatniego bitu". Wiekszo?a popularnych
jezyków kiespko tu by pasowa3a, bo tak na prawde ju? same ich definicje nie
s? ?cis3e.

pzdr
--
Sebastian Kaliszewski

pdemb

9/29/2006 6:18:00 PM

0

"Michal Przybylek" <mrp@neostrada.pl> writes:

[...]

> Dziala w druga strone - jezyki funkcyjne byly inspirowane modelami
> matematycznymi, zas jezyki obiektowe nie.

A to nie jest tak, ?e obiektowo?a 'wyros3a' z potrzeb in?ynieryjnych?

pdemb

9/30/2006 4:23:00 PM

0

"Michal Przybylek" <mrp@neostrada.pl> writes:

> Dnia 29-09-2006 o 20:18:19 "Piotr Dembinski" <pdemb@gazeta.pl>
> napisa3(a):
>
>> "Michal Przybylek" <mrp@neostrada.pl> writes:
>>
>> [...]
>>
>>> Dziala w druga strone - jezyki funkcyjne byly inspirowane modelami
>>> matematycznymi, zas jezyki obiektowe nie.
>>
>> A to nie jest tak, ?e obiektowo?a 'wyros3a' z potrzeb
>> in?ynieryjnych?
>
> Well... obiektowosc wyrosla z Simuli, a pozniej byla przez lata
> pielegnowana przez inzynierie. Ale o co chodzi... ?

Chodzi rzecz jasna o tak zwan? geneze: pomys3, który leg3 u podstaw.

Michal Przybylek

9/30/2006 4:59:00 PM

0

"Andrzej 'Rudy' D?browski" <a.r.dabrowskiSPAM@gmail.com> wrote:

> Jak wiadomo, jezyki funkcyjne s? "czysto matematyczne"

Stwierdzenie jest bez sensu. Nie powtarzaj go wiecej :-)

> Szukam gdzie?
> skondensowanego materia3u (na razie ogólnego, nie ma sensu wchodzia na
> g3ebiny bez podstaw) na tematy dotycz?ce teorii jezyków programowania,
> czyli np. teoria typów, rachunek lambda (z typami, bez), monady i ogólnie
> relacje matematyka <-> programowanie.

Tego nie da sie przejsc waska sciezka. Trzeba przedeptac cale pole.

Juz to samo co wymieniles stanowi naprawde ladny kawalek matematyki (tzn.
mysle, ze zaczynajac od zera - tj. po maturze :-) - jest to gdzies z cztery
razy tyle czego uczy sie przez cale studia matematykow na porzadnych
uczelniach).

> Ostatnio na pclc kto? pisa3, ?e "typ" jest terminem teoriomnogo?ciowym.

Kompletna bzdura. Patrz przez palce na to co pisze sie na grupach
dyskusyjnych.

Wiekszosci wypowiedzi nt. teorii (szczegolnie na grupach niscislych) to
glupkowate przepaplywanie za innymi strzpkow informacji i dorabianie co
kolejny poziom dodatkowego belkociku.

Standardowa teoria mnogosci nie mowi czegokolwiek nt. pojecia typu. Teoria
mnogosci, w ogole, nie mowi na temat pojecia typu.

Pojecie typu, najblizsze temu kontekstowi, to pojecie typu z teorii typow
Martina-Lofa. Owszem, w teorii typow Martina-Lofa buduje sie "teorie
mnogosci", w ktorych pojeciu typu odpowiada pojecie zbioru (i to w bardzo
mocnym sensie, takie teorie mnogosci odpowiadaja mniej wiecej toposom
elementarnym, czyli temu o czym chcemy myslec mowiac "teoria mnogosci").

W ogole standardowa teoria mnogosci bardzo kiepsko nadaje sie do modelowania
obliczen. Np. bardzo dlugo wierzono (i dowodzono), ze nie istnieja
teoriomnogosciowe modele dla polimorficznego rachunku lambda. Dzisiaj
wiadomo, ze istnieja i to bardzo naturalne, ale trzeba sie wybic ponad
klasyke.

> W sumie nie chcia3bym te?, ?eby mia3o to styczno?c z super wy?sz?
> matematyk?, chocia? jak sie nie da inaczej to okej ;) Jeszcze jej nie
> posiadam, ale z czasem wszystko przyjdzie.

Pojdz na porzadne studia informatyczne/matematyczne :-)

"Sebastian Kaliszewski" <sk@get.it.off.to.reply.z.pl> wrote:

> > Czy da sie np. paradygmat obiektowy i terminy z nim zwi?zane
> > umie?cia w przestrzeni matematycznej.
>
> Zapwene sie jako? sie da (bo i czemu nie), ale nie widzia3em rozs?dnych
prób
> uczynienia tego? (choa ja te? i ma3o widzia3em). Gros literatury za
zakresu
> ró?nych ró?nistych stricte formalnych rozwa?an dotyczy jezyków
funkcyjnych,
> albo "logikowych" (koledzy Prologa).

Dziala w druga strone - jezyki funkcyjne byly inspirowane modelami
matematycznymi, zas jezyki obiektowe nie.

Jezyki obiektowe zazwyczaj opisuje sie (ladniej badz mnej ladnie) w sposob
koalgebraiczny (czyli niejako "w druga" strone niz jezyki funkcyjne).

> Proble te? poniek?d taki, ?e to co w jezykach czysto funkcyjnych
> opisuje sie 3adnie matematycznie (typy = zbiory warto?ci, itd) przestaje
sie tak
> opisywaa w przypadku systemów obiektowych. Pierwszy ból to taki, ?e takie
> systemy "nie lubi?" opisywaa zamknietego ?wiata (a ró?ne formalizmy taki
> ?wiat "kochaj?")

To jest juz kompletna bzdura.


mp

pdemb

9/30/2006 5:39:00 PM

0

pdemb@gazeta.pl (Piotr Dembinski) writes:

> "Michal Przybylek" <mrp@neostrada.pl> writes:
>
>> Dnia 29-09-2006 o 20:18:19 "Piotr Dembinski" <pdemb@gazeta.pl>
>> napisa3(a):
>>
>>> "Michal Przybylek" <mrp@neostrada.pl> writes:
>>>
>>> [...]
>>>
>>>> Dziala w druga strone - jezyki funkcyjne byly inspirowane
>>>> modelami matematycznymi, zas jezyki obiektowe nie.
>>>
>>> A to nie jest tak, ?e obiektowo?a 'wyros3a' z potrzeb
>>> in?ynieryjnych?
>>
>> Well... obiektowosc wyrosla z Simuli, a pozniej byla przez lata
>> pielegnowana przez inzynierie. Ale o co chodzi... ?
>
> Chodzi rzecz jasna o tak zwan? geneze: pomys3, który leg3 u podstaw.

Mo?e od razu napisze, jak ja to widze: na pocz?tku by3a idea
programowego symulowania rzeczywistych uk3adów (scalonych,
mechanicznych etc.), a pó?niej dostrze?ono tkwi?cy w podej?ciu
obiektowym potencja3 i uogólniono to podej?cie na proces opracowywania
oprogramowania w ogóle, czego efektem by3o powstanie in?ynierii
oprogramowania zorientowanej na obiekty (OOSE).

--
http://www.piotr.dembin...

Michal Przybylek

10/1/2006 3:37:00 PM

0

Dnia 29-09-2006 o 20:18:19 "Piotr Dembinski" <pdemb@gazeta.pl> napisa3(a):

> "Michal Przybylek" <mrp@neostrada.pl> writes:
>
> [...]
>
>> Dziala w druga strone - jezyki funkcyjne byly inspirowane modelami
>> matematycznymi, zas jezyki obiektowe nie.
>
> A to nie jest tak, ?e obiektowo?a 'wyros3a' z potrzeb in?ynieryjnych?

Well... obiektowosc wyrosla z Simuli, a pozniej byla przez lata
pielegnowana przez inzynierie. Ale o co chodzi... ?


mp