[D] D Programming Language

Programski jezik jeste formalni jezik, te je model programskog jezika
(skup leskickih, sintaksnih i semantickih pravila) jedna formalna teorija.
Programski jezik je minimalan ako skup njegovih sintaksnih konstrukcija cini
bazu semanticke izrazajnosti sto znaci da svakom semantickom konceptu (uslov, iteracija,
petlja) odgovara jedna sintaksna konstrukcija.
Ako za jedan semanticki koncept imas vise sintaksnih konstrukcija gubi se minimalnost,
na primer za petlju imas FOR, WHILE i REPEAT sintaksne konstrukcije.

Neprotivurecnost programskog jezika kao formalnog jezika jeste apriorna.
Pod njom se podrazumeva to da svaki program u nekom programskom jeziku uvek na isti input daje isti output.
Da nije tako izgubio bi se toliko nam drag determinizam algoritma, tj. izgubili
bi mogucnost funkcionalnog intepretiranja, kao i kompajliranja (ovo je otprilike
objasnjenje na ono ???)
Komplentnost programskog jezika jeste kompletnost u smislu izracunljivosti, jezik
mora biti takav da pokrije skup svih izracunljivih funkcija. Zahtev komplenosti
je preteran jer postoje citave klase izracunljivih funkcija koje su beskorisne i koje
za sada nisu mogle da se ufituju da budu model bilo kakvog nama zanimljivog fenomena.

Formalna teorija je neprotivurecna ako se u njoj ne moze izvesti iskaz A i njegova
negacija. Ako bar jedna formula neke formalne teorije nije njena teorema
to ne znaci da u skupu teorema nema jednu teoremu i njenu negaciju koja je
takodje teorema.

Ima koliko god hoces neprotivurecnih i kompletnih formalnih teorija, ali krajnje
beskorisnih sa stanovista izracunljivosti. U mojoj recenici kada sam rekao da se
ne moze zahtevati potpunost formalne teorije ako zahtevamo neprotivurecnost, ono
formalne teorije se odnosilo na programski jezik. Formalno gledano recenica nije
ispravna kada se izvuce iz konteksta. Jasno je da postoje neprotivurecne i
kompletne formalne teorije, ali ne nivou ranga jednog ozbiljnijeg (funkcionalnijeg)
programskog jezika.

U C++ templetima je moguce izdrkavanje svekoliko. Ali opet podsecam da sam ja
negde izjavio da je C++ nedostojan toga da se nazove ozbiljnim programskim
jezikom. Ako je moguce bilo koju izracunljivu funkciju izracunati tokom kompajliranja
onda kompajler uopste nije kompajler, gubi se smisao naziva kompajler i
to se onda zove INTERPRETER, sto je bitno razlicito od KOMPAJLER. Na tlu INTERPRETERA
mozemo govoriti o algoritamskoj neodlucivosti, na nivou KOMPAJLERA ne mozemo,
kompajliranje je proces prevodjenja jednog jezika u drugi koje se uvek zavrsava
u konacnom vremenu, posto su programi prostorno konacni.
Stoga jedino u cemu mogu da se slozim da je algoritamski neodlucivo da INTERPRETER
zavrsi sa INTERPRETIRANJEM necega, nikako KOMPAJLER sa KOMPAJLIRANJEM necega.
Ne znam cemu potreba da uokviru jednog KOMPAJLERA imamo INTEPRETER, ako nesto
tako postoji onda se gubi smisao samog programskog JEZIKA koji tako nesto ima.
Sto opet potvrdjuje moju cinjenicu da je C++ obicno s***** i smece.

Svrha minimalizma nije da postoje neki koncepti koji prosiruju isti taj minimalizam
i cime se gubi smisao istog, nego da se svesno ogranice neke stvari zbog razno raznih
pojava i fenomena koje bi bile moguce kada iste ne bi bile ogranicene. Stoga sta ce
mi minimalni programski jezik koji mi nudi predprocesorske mogucnosti prosirenja.
Gubi se smisao i odjednom uvidjas da ti je vise koda u predprocesoru nego u samom
jeziku. Kakvo s***** :)

Generator prostih brojeva ne zahteva celu Tjuringovu masinu, ali ja to nisam ni tvrdio.
Ja sam rekao da je lakse napisati Tjuringovu masinu koja bljuje proste brojeve pa je
posle prevesti u generativnu gramatiku po standardnom algoritmu kojim se to radi,
nego napisati generativnu gramatiku koja generise proste brojeve,
kao ilustraciju cinjenice da programiranje na nivou generativnih gramatika jeste jako neintuitivno.

C++ s***** i smeće? Pa ti mora da si student ;)

Ili student ili profesor - uglavnom neko ko nema baš mnogo veze sa stvarnim svetom :)

Potpis

IOCC

U stvarnom svetu (u ovom slucaju, game development), C++ zaista ume da bude izvor velikog broja problema.

Baš kao što i stvarni svijet (tj. IT industrija) uglavnom nema veze sa kriterijima izvrsnosti prilikom (prirodnog) selektiranja softverskih proizvoda. Nažalost, dugoročno prevladavaju tehnologije koje su izvorno stvorene tek kao najbolja (kratoročno gledano) rješenja za konkretne probleme u danoj točci prostora i vremena, pri čemu se obično tokom vremena mutiliraju do neprepoznatljivosti i beskorisnosti, a zbog stvorene baze ulaganja (ljudski kadrovi, razvojni alati, literatura, ovisnost o legacy standardima/protokolima, korisnička baza) su prisutni i desetljećima nakon što je to ikad itko mogao sanjati. To vrijedi kako i za COBOL, C i UNIX, tako i za C++ i Javu.

Sa današnjeg stajališta, C++ _je_ smeće. Evo i Nrmyth je konačno (nakon duge i teške muke :) priznao da je _jedini_ razlog pro C++ templatinga dobivena compile-time učinkovitost, nauštrb odvratne sintakse, bloata i nerazumljivih stranica i stranica opskurnih grešaka kompajlera kad uradiš nešto tipa sort(2,2). Bojim se da samo taj kriterij danas više nije toliko relevantan kao i nekad.

Baš kao što bi Richard Gabriel rekao, nažalost gore jest bolje. Korisne reference:

http://en.wikipedia.org/wiki/Worse_is_Better

http://www.naggum.no/worse-is-better.html

http://www.dreamsongs.com/Files/AcceptanceModels.pdf

Ako se nekome da čitati cijeli knjigu (Richard P. Gabriel - Patterns of Software (PDF - 1.2MB, 235s)

Potpis

Put the funk in funktion.

Mene nije sram priznati promjenu misljenja. Toliko egoistican programer nisam... :)

Ali isto malo pretjerujes. Kao da su ti templatei ubili i mater i oca.


Tip<A, B, C> bla, bla, bla. Sta je tu tako odvratno u samoj sintaxi?
Mislim da nijedna konstrukcija koju su mogli smisliti, preko koje bi mi mogli prinositi tipove, ne moze biti toliko bolja od ove koju vec imamo.


Zar to nije problem nastao zbog "lijenosti kompajlera"? Onako preko oka sam uvjeren da te opskurne greske koje izbaci kompajler mogu proci jedan odredjen face-lift.

Game developmenta nebi bilo da nema C++... cemu onda ovo.



Znaci pocelo je, poceo je taj sveti rat protiv otaca nasih - C++-a. Ako se ne varam ista stvar je bila prije mnogo godina samo se rat vodio protiv assemblera.

Odgovorite sebi ovo: Dali su jos uvijek u svijetu informacionih tehnologija potrebne unmanaged aplikacije?
Ako je odgovor DA, onda nam je jos uvijek potreban C++ jer u tom podrucju mu nema boljeg.
Ako je odgovor Ne, onda bi trebali razmisliti kako cete napraviti performance konzumirajucu aplikaciju u managed svijetu, jer ja mislim da racunala jos nisu spremna za to.

Milina je pisati u C# naprema C++. Isto tako je bilo milina pisati u C poslije assemblera. I tako ce biti milna pisati u necem trecam poslije C#.
Prirodni tok vremena ide, ali JA mislim da vrijeme C++ jos nije proslo.

- Skup svih reči nad nekim alfabetom je skup svih konačnih nizova čiji su članovi slova tog alfabeta, uključujući i prazan niz kao reč dužine nula koja se ne sastoji ni od jednog slova tog alfabeta.

- Formalni jezik čine alfabet i skup reču tog jezika, koji je izvestan podskup skupa svih reči nad tim alfabetom.

- Formalnu teoriju čine alfabet, skup formula (koji je podskup skupa svih reči nad tim alfabetom i zajedno sa alfabetom čini jezik te formalne teorije), skup aksioma koji je podskup skupa formula i skup pravila izvođenja koja su relacije sa bar dva argumenta.

- Formalnu gramatiku čine dva disjunktna alfabeta, skup završnih i skup nezavršnih slova, početno slovo, koji je nezavršno slovo i skup pravila izvođenja, koja su relacije sa dva argumenta nad skupom svih reči sa slovima iz unije oba alfabeta.

- Formalnoj gramatici pridružujemo jezik sa istim alfabetom, čiji je skup reči skup svih reči nad sskupom završnih slova, koja se mogu dobiti konačnom primenom pravila izvođenja polazeći od početnog slova. Međutim, jezik se ne mora zadavati preko gramatike i različite gramatike mogu dazi isti jezik, tako da treba voditi računa o pravljenju razlike između tih pojmova.

- Formalna gramatika je, u odnosu na formalni jezik, bliži pojam formalnoj teoriji, jer osim alfabeta (koji u slučaju formalne gramatike obuhvata dve vrste slova - završna i nezavršna) ima i pravila izvođenja, kao i početni simbol kao aksiomu. Međutim, da bismo dobili formalnu teoriju, treba na neki način zadati i skup formula.

Skup formula mora biti podskup skupa svih reči nad odgovarajućim alfabetom, koji obuhvata sve reči odgovarajućeg formalne gramatike (jer će one biti teoreme te formalne teorije, kao reči izvodive u konačnom broju koraka polazeći od početnog simbola konačnom primenom pravila izvođenja). Obratiti pažnju da skup svih reči formalne gramatike nije isto što i skup svih reči nad njenim alfabetom.

Zbog toga, način pridruživanja skupa formula nije jednoznačno određen, pa ne postoji podrazumevani (dogovoreni) način pridruživanbja formalnih teorija formalnim gramatikama. No. možemo se mi dogovoriti, za potrebe ove rasprave oko načina na koji ćemo birati skup formula.

Ako skup formula definišemo kao skup svih reči date formalne gramatike, onda če se skup formula biti isto što i skup teorema, pa će ta formalna teorija svakako biti kompletna i protivrečna, bez obzira od kakve smo gramatike pošli. Ako li pak skup formula definišemo kao skup svih reči nad odgovarajućim alfabetom, onda će ta formalna teorija biti protivrečna ako isamo ako su sve reči nad tim alfabetom izvodive u toj formalnoj gramatici. Napominjem da ceo ovaj pasus nema nikave veze sa Gedelovim teoremama nepotpunosti.

Dakle, lako je formalnoj gramatici pridružiti formalnu teoriju čiji će skup teorema biti skup svih reči te gramatike, ali kompletnost te teorije bitno zavisi od toga kako joj definišemo skup formula.

Prvo, takav pojam minimalnosti zavisi od izbora semantike datog programskog jezika. Drugo, koji je programski jezik u tom smislu minimalan? Možeš ubacivati komentare i preoznačavati promenljive koliko god hoćeš. U programskim jezicima u kojima nema provere granica indeksa upotrebu n promenljivih istog tipa možeš zameniti upotrebom niza od tri elementa, jer se adrese članova sa konstantnim indeksima izračunavaju u fazi prevođenja, pa dobijaš isti izbršni fajl. Nije teško zamisliti semantiku programskog jezika BASIC u jojoj će sledeća dva BASIC programa imati istu semantiku:

Nije teško zaključiti da ni Tjuringova mašina nije u tom smislu minimalna.

A šta ćemo sa programskim jezicima kao što su Java i (sve popularniji) C#, koji zbog nepredvidivosti trenutka uključivanja skupljača đubreta gube determinizam?

I kakve onda ima veze taj pojam kompletnosti sa Gedelovim teoremama nepotpunosti? Naprotiv, po definicijama koje si ovde naveo, svi programski jezici su kompletni, a najveći broj njih je deterministički (ili "neprotivrečan", kako ti kažeš).

A šta ćemo sa formalnim teorijama u kojima nemamo negaciju? Recimo, alfabet se sastoji od slova a i b. Ako formalna teorija opisuje ili obuhvata nekakvu logiku (a ne mora opisivati, niti obuhvatati nikakvu logiku), koja obuhvata negaciju (a logika ne mora obavezno da obuhvata negaciju), onda u najvećem broju slučajeva (što je slučaj npr. kod klasične logike), a u zavisnosti od toga koja je logika u pitanju, sve formule su teoreme ako i samo ako postoji teorema čija je negacija takođe teorema.

Onako kako si definisao pojmove "neprotivrečnosti" (?) i kompletnosti programskij jezika, oni nemaju nikakve veze sa pojmovima neprotivrečnosti i kompletnosti formalnih teorija, pa ni sa Gedelovim teoremama nepotpunosti. Tjuringova mašina je deterministički i kompletan sistem izračunljivosti.

A čemu minimalizam, kada nije ostvariv?

_{[Ovu poruku je menjao Nedeljko dana 23.01.2007. u 17:34 GMT+1]}

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Slažem se da bi za PJ općenito trebala vrijediti "as simple as possible - but no simpler" škola mišljenja. Nažalost, povijest je pokazala da takvi stavovi obično dovode do izuzetno glupih zabluda koje se s vremenom toliko uvriježe da postanu vječni dio kulture "dobre prakse". Po Teoremu o strukturiranom programu, flowchart-izračunljive fje su također turing-izračunljive, pa je GOTO naredba nepotrebna, zbog čega se i dan danas programere od malih nogu uči da je s užasom izbjegavaju, čak i kad je ona neusporedivo elegantnije rješenje (recimo preskakanje između case-eva switch naredbe, ili u nekoj gadnije ugniježđenoj petlji).

Spomenuli smo već turing tarpit - ali nitko ne programira u turingovom stroju ili čistom lambda računu, i jedan i drugi su jednako zamorni. Rekurzija i iteracija su potpuno istovjetni računski modeli, samo operiraju na drugačiji način - ono što se u iteraciji ostvari promjenom stanja u rekurziji se ostvari uvođenjem novog stanja, pri čemu se uz odgovarajuću podršku (npr. tail-rekurzija koju Scheme standard propisuje za sve implementacije) dobije računski proces istovjetne prostorne/vremenske složenosti. Pa opet - jezik koji eksplicitno ne podržava rekurziju nije nimalo računski "moćniji", baš kao i onaj koji ne podržava npr. first-class funkcije i lambdu, ali za mene _kao čovjeka-programera_ jest znatno manje moćan alat zaključivanja i razmišljanja.

Minimalnost bi se IMHO jedino trebala zahtijevati na razini sintaksnih ograničenja, pri čemu bi iz minimalnog skupa dobro poznatih i shvaćenih konstrukata iznikli svi ostali uobičajeni HLL konpceti. Pogledaj npr. kako je u Schemeu napravljen LOOP makro, s obzirom da bazni jezik ne dolazi sa iterativnim konstruktima uopće (npr. ovdje). REPEAT UNTIL, WHILE etc. dobiješ na isti način.



Koliko sam ja čuo, turing-ekvivalentnost C++ templatea je otkrivena sasvim slučajno ;) Izvorno oni NISU stvoreni za sve gluposti za koje se danas koriste, no kad imaš dovoljno veliku programersku populaciju i popularnost kakvu C++ ima, svi kutovi jezika se kad-tad istraže na najgori mogući način. Strogo gledano, to "interpretiranje" odrađuje dio kompajlera (type checker), aplicirajući neke matematičke transformacije nad izrazima jezika (recimo denotacijskom semantikom - izračunavanjem nekih funkcija (denotacija) koje predstavljaju "značenje" izraza). Ako su izračuni u tom formalnom modelu koji semantički analizator koristi neodlučivi - onda je valjda i sam čin kompajliranja neodlučiv :)



Metaprogramiranje je inače prejebena stvar - problem je samo što ga C++ pruža na najodvratniji mogući način :)



Zar se generativne gramatike koriste ozbiljnije za bilo šta osim za specificiranje sintakse jezika?

Potpis

Put the funk in funktion.

Nema to veze sa egoizmom. Pametan čovjek uvijek ima pravo na promjenu mišljenja :)



Kad bi se templatei koristili isključivo za parametarski polimorfizam - skoro pa ništa. Izbroji koliko linija koda u onom primjeru C++ monada se koristi isključivo za implementiranje generičnosti pa javi.



Ne, to je zbog defekta u dizajnu samog jezika. Proguglaj za "Stepanov" i "concepts".



Smiješna zamjena teza. Bio bi neki drugi jednako gadan jezik zauzeo njegovo mjesto :)



Postoje real-time GC-ovi, već 20+ godina IIRC :)

Potpis

Put the funk in funktion.

Koliko znam, prvi je LISP imao GC. Ima ga i PROLOG, ali deterministički. Java/C# đubretari su drugo.

@FuzzyCreation

Koliko ja shvatam, cynique hoće da kaže da je moguće definisati skup C++ šablona, među kojima je šablon

template<int n> int faktorijel()

koji se pozivaju jedni na druge, tako da ako je sabloni.h zaglavlje sa tim šablonima, onda program

ispisuje na ekranu broj 120, i slično ako se umesto 5 stavi bilo koji drugi prirodan broj, pri čemu se izračunavanje vrši u fazi prevođenja, a ne izvršavanja. I slično za svaku Tjuring izračunljivu funkciju, pa da je samim tim zaustavljivost prevodioca za dati C++ program na ulazu algoritamski neodlučiva.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Ali po meni to nije problem sintaxe nego se problem javlja zato jer se pokusava stvoriti od templatea nesto za sto one nisu napravljene.

Kad smo kod toga, jeli komitet za standard C++-a razmisljao o templateima i ovim stvarima?



Ali nista se nebi promijenilo, on bi rekao da taj jezik stvara probleme, ja bi samo ponovio isto s zamjenom subjekta.


Za takvo sto nije uopce potrebna nova konstrukcija, moze sve ostati na kompajleru.
Kompajler simulira funkciju i vidi dali ona koristi ikakve runtime-promjenjive varijable, ako ne onda se izvrsava s konstantnim varijablama i moze se izvesti optimizacija. Okvirno... :)

Radi li to koji kompajler??

Ah, svi proizvođači igara su mazohisti pa rade u C/C++.

U gamedev sa novom generacijom konzola je u toku prelazak sa sekvencijalnog izvršavanja na konkurentno. Bilo je konkurentnog izvršavanja i ranije posebno sa PS2, ali ovde mislim na jednakosti procesora po mogućnostima. Već godinu dana radim na igri koja ima minimalno 6 niti i samo jednom sam naleteo na problem trenutnog C++ standarda, a to je statička promenljiva u okviru funkcije. I verujem da će ovo biti korigovano u C++0x standardu (npr. da kompajler tretira volatile kao atomic). Ovo verovatno nije rešeno ni u D jeziku, a koliko sam video iz standarda imaju ključnu reč 'synchornize' koja je u praksi function scope mutex. Ovo znači da su dodali ključnu reč za funkcionalnost koja je nepoželjna u konkurentnom programiranju i koristi se veoma retko i samo u slučajevima kada neko drugo rešenje ne postoji. Ja koristim ovo oko tri puta kroz ceo kod igre, i planiram da do izlaska igre ostane samo jedan. Znači imaju "case specific" ključnu reč u jeziku, za čiju implementaciju je potrebno oko 10-tak linija koda u C++ (ctor klase preuzme mutex, dtor ga oslobodi).

Kada smo kod C/C++, u prošlosti je trend u gamedev bio od C prema C++, jer je kod postajao sve glomazniji. Trenutni trend je od C++ ka C kako je za konkurentno izvršavanje potreban jednostavniji manji kod koji je moguće izvršavati u potpunosti odvojeno od ostatka aplikacije. Što više jezgri procesor ima, imati kod razbijen na što manje delove je sve važnije.

Sama činjenica da C/C++ verovatno postoji za skoro svaki procesor ikada (ok 'ajd da se ograničim, pa kažem od devedesetih) napravljen ga čini veoma važnim jezikom. Problem D je da ne rešava nijedan moderan problem (npr. konkurentno izvršavanje), nema podršku velikih firmi (npr. MS neće izbaciti Visual D), oni što koriste GCC verovatno koriste C/C++ već godinama i znaju da reše sve probleme u C/C++, itd. D rešava probleme C++ iz prošlosti koje je svaki iskusan C++ programer već rešio, zna da reši ili zaobiđe. I na kraju nekome kome bi D bio od koristi (a.k.a. VB programerima kojima se C++ ne dopada), će verovatno nedostatak IDE-a i komandna linija teže pasti od učenja C++. ;)

Potpis

https://github.com/bkaradzic/bgfx

Ako prevodilac tako radi (izvrši funkciju sa konstantnimparametrima, pa u kod ubaci gotov rezultat), onda je zbog algoritamske nerešivosti problema zaustavljanja zaustavljivost prevodioca za dati C++ program na ulazu algoritamski nerešiv problem, jer se ne zna da li će se izvršavanje takvih funkcija za vreme prevođenja okončati. No, nisam mislio na to (a mislim da nije ni cynique).

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Neka to bude prije kompajla i neka se postavi timeout - tim se dobije optimizirajuci facility koji se lako ugasi/upali po potrebi.
Meni je to sad zabavna teorija koja nije daleko od prakse, ali svrha je minimalna.

@cynique
Ako kažeš da boost gurui znaju zašto su onako napisali Monad, kaži mi da li misliš da je Microsoft pogrešio stvorivši C++/CLI?
I sam je stvoren za one kojima je još uvek neophodan unmanaged kod i koji bi i dalje (manje-više) želeli da imaju moć C++-a. Ako su templejti isuviše ružni, zašto uopšte postoje sada genericsi?

-- Moje mišljenje: C++ možda jeste preobiman, samim tim i pruža mnogo, ALI daleko od toga da je uklonjena mogućnost da ti u njemu pišeš jednostavan kod.

Izbor semantike programskog jezika je uglavnom jednostavan i univerzalan i svodi se
na izracunljive funkcije. U svim programskim jezicima pises izracunljive
funkcije bilo da je to neki struktuirani, objektno-orjentisani, funkcionalni
ili logicki programski jezik. Minimalnost znaci onda dati za svaku
klasu izracunljivih funkcija samo jednu formu zapisivanja. Ako u programskom
jeziku postoje duplikacije te forme, na primer IF i SWITCH ili IF i COND onda
jezik nije minimalan jer je omogucio dve forme za pisanje jednog semantickog
sadrzaja.
Uostalom ja sam i rekao da je minimalnost za svaki semanticki smisao jednu
sintaksnu konstrukciju. Kakvu ces ti semanticke smislove izabrati i podrzati
nema veze sa minimalnoscu. Minimalnost se odnosi na sintaksne konstrukcije.

Ubacivanje komentara i preoznacavanje promenljivih nema veze sa minimalnoscu.
Mozes u programu imati i 50 IFova ako zelis, ono sto je bitno jeste da postoji
jedna forma u kome se semanticki smisao IFa moze zapisati i da postoji jedan
nacin zapisivanja komentara. To je minimalnost.

SVI PROGRAMSKI JEZICI JESU DETERMINISTICKI I NE MOGU IZGUBITI DETERMINIZAM.
Ne postoji PROBABILISTICKI programski jezici jer je to u koliziji sa pojmom ALGORITAM,
programi u tom programskom jeziku ne bi onda bili implementacija ALGORITAMA.
I random() funkcija jeste deterministicka i brojevi koje ona proizvodi su
deterministicki sa statistickim osobinama slucajnih brojeva.

Ne postoji NEPREDVIDIVOST trenutka ukljucivanja garbage kolektora. I taj program
koji njega ukljucuje radi po nekom algoritmu i moze koristiti i random() funkcije
ali i one opet rade po nekom algoritmu. Svaki algoritam (a ovde se vec podrazumeva
da je to algoritam koji se zavrsava) je PREDVIDIV jer je
DETERMINISTICKI. Uostalom to sto ti radi garbage collector ne znaci da ces ti
u svom algoritmu za input a dobiti drugaciji output kada se ukljuci garbage collector.
Cak mozes i da izracunas i trenutak kada se on ukljucuje ako znas po kojem algoritmu
radi. Determinizam tu nije narusen, jer je determinizam nemoguce narusiti jer kao sto
sam vec rekao kod algoritama je on aprioran i podrazumeva se u samom pojmu algoritma.


Generativne gramatike se mogu koristiti i kao mehanizam za racunanje. Proces
izvodjenja neke reci jeste simbolicko racunski proces, a gramatika zapis funkcije koja
se racuna.
U krajnjoj liniji program jeste model. Kada napises proceduru u Moduli-2 koja generise proste brojeve
ona jeste model prostih brojeva, kada napises generativnu gramatiku koja opisuje skup
reci koji imaju duzinu koja je prost broj opet dobijes model prostih brojeva.

Izvini, da li ćeš ti za svaki iole veći program da računaš gde će se i kada desiti sakupljanje otpada?
Takođe, najverovatnije ćeš za isti input dobiti isti output, ali nikako ne možeš da znaš kako će program svaki sledeći put kada ga pokreneš za isti input da upravlja memorijom. Što će reći, neki algoritam GC-a zavisi od "spoljašnjih" uticaja (odnosno onoga što se dešava na sistemu van programa). E sada, mislim da možeš napisati takav program koji će imati promenljivo ponašanje u zavisnosti od toga kako se manifestuje rad GC-a, što opet povlači da rad programa sa GC-om može biti varijabilan. E sada, ako ti obradiš sve moguće situacije startovanja GC-a, moći ćeš teorijski da se izboriš sa svim eventualnim problemima. A onda se postavlja pitanje, da li je prednost nekog jezika to što je on u poziciji da UVEK mesto tebe odlučuje šta će se dešavati.

Izgleda da si u životu imao velikih problema sa C++-om, čim neki tvoji komentari počinju da liče na religijska ubeđenja... :)

_{[Ovu poruku je menjao Goran Arandjelovic dana 24.01.2007. u 15:41 GMT+1]}

Pa, svi programski jezici opisuju istu klasu izračunljivih funkcije.

I radi se o istoj klasi izračunljivih funkcija.

Da li si čuo za Rajsovu teoremu i njene posledice? Jedna je da za svaku izračunljivu funkciju postoji beskonačno mnogo Tjuringovih mašina koje je izračunavaju. Recimo, postoji puno algoritama za sortiranje konačnih nizova celih brojeva. Funkcija je ista.

Ako ti se semantičke forme svode samo na osnovne konstrukcije, onda IF nije zamena za SWITCH. Ako pod semantičkim formama podrazumevaš i složene konstrukcije, minimalizam je neostvariv.

Opet se vraćamo na pitanje da li se pod konstrukcijama podrazumevaju isključivo proste, ili i složene.

Ovo je vrlo rasprostranjena zabluda. A šta ćemo sa kvantnim algoritmima, koji dobijaju sve više na važnosti i koji jesu probabilistički. Za datu kvantnu mašinu i njen ulaz mogu se predvideti samo verovatnoće da se dobije ovaj ili onaj rezultat. Pojam algoritma se vezuje za određenu klasu mašina. Neke od klasa su:

- Determinističke (podrazumevaju se ako se ne kaže drugačije).
- Nedeterminističke. Možeš ih zamisliti kao mašine koje mogu da ispale proizvoljan broj niti koje rade u paralelnom (ne u razdeljenom) vremenu, pri čemi sve niti dele istu memoriju.
- Verovatnosne. Možeš ih zamisliti kao determinističke snabdevene još i generatorom slučajnih (ne pseudoslučajnih) brojeva, kao hardverskim proširenjem.
- Kvantne. One zahtevaju duži opis, ali se i o njima može dosta izguglati.

Sve od nabrojanih mašina mogu biti konačne ili beskonačne u zavisnosti od toga da li im je memorija (recimo, broj mogućih stanja mašine) ograničena ili ne. Opet, mašina može biti automat ili ne, u zavisnosti od toga da li joj je izlaz binaran, ili na izlazu možemo imati i više od dve mogućnosti.

Svaka od klasa mašina ima svoju klasu algoritama. Determinističke i nedeterminističke mašine su operisane od slučajnih brojeva, pa onda kada im nizovi slučajnih brojeva zatrebaju, aproksimiraju ih niziovima pseudoslučajnih brojeva, koji nisu ni najmanje slučajni, već sasvim predvidivi (tu se slažemo). Računar na kome ovo pišem spada u klasu konačnih determinističkih mašina. Međutim, postoje i druge klase mašina, pa samim tim i algoritama.

Slažem se ako posmatramo ceo računar kao zatvoren sistem. Ali, sa stanovišta jadne aplikacije, ona ne zna kada će naići komunalci, jer o tome odlučuje .NET, koji radi po algoritmu, ali izvan same aplikacije.

Tako je, ali samo uz odgovarajuću semantiku. Kada se dogovorimo šta nam znači koje stanje trake Tjuringove mašine, onda je program zaista jedan konačan model jedne izračunljive funkcije, čiji domen i slika mogu biti i beskonačni. U tom smislu postoji konačan, a tačan, zapis beskonačnog decimalnog zapisa broja

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Vrlo kratko:
Rekao sam za svaku klasu izracunljivih funkcija a ne za svaku izracunljivu funkciju.

Naravno da postoji beskonacno algoritama za sortiranje niza. Od jednog algoritma
koji radi nesto uvek moze napraviti beskonacno algoritama koji rade to isto na
osnovu tog algoritma.

Koje su to slozene konstrukcije? verovatno kombinacije iteracije, uslova i petlji.
Sto znaci da nam je dovoljno IF, WHILE i ; (ili mehanizam rekurzije).
Da li postoji slozena konstrukcija koja nije kombinacija iteracija, uslova i petlji.
Odgovor: NE, stoga minimalizam je moguc jer je potrebno obezbediti
sintaksne konstrukcije za IF, WHILE i ;
Sta je SWITCH, nego gomila IFova. Treba li nam SWITCH, ne treba njime
ne mozemo nista vise reci nego gomilom IFova. Da li nam treba iteracija
kao mehanizam ako imamo rekurziju. Ne. Da li nam treba rekurzija ako imamo
iterativni mehanizam. Ne. TO JE MINIMALIZAM i itekako je MOGUC. Uostalom
Niklaus Wirth je zagovornik MINIMALIZMA (pogledati njegov rad o Oberon-2
na http://www.ssw.uni-linz.ac.at/Research/Papers/Moe91a.html), gde covek
lepo kaze, citiram:
"Oberon-2 covers most terms of object-oriented languages by the established
vocabulary of imperative languages in order to minimize the number of notions for similar concepts"

Pod konstrukcijama podrazumevam i proste i slozene. Slozene konstrukcije
se prave kao konstrukcija ciji su sastavni elemetni proste konstrukcije, slozene konstrukcije
su one koje se mogu redukovati na proste konstrukcije + graf njihove povezanosti.
Proste konstrukcije to ne mogu, on su atomi semantike.

Kada govorimo o algoritmu ja vidim Cerc-Tjuringovu hipotezu, po njoj su algoritmi opisi izracunljivih funkcija,
a izracunljive su one funkcije koje su rekurzivne. Ne postoji dobra definicija algoritma, postoji
samo njeno ogranicenje i socijalni konsenzus po tom pitanju. Ovde je bila rasprava o tome imamo programski jezik koji narusava
determinizam, a da programi iz tog programskog jezika rade na masini iz prve kategorije u kategorizaciji
koju si naveo, sto je po meni 100% netacno. Jos nisam video C#, Java kompajler/interpreter koji radi na nekom
kvantnom racunaru. U stvari ja jos nisam video kvantni racunar. A i skeptican sam po tom pitanju na osnovu
dosadasnjih iskustava. Matematicki modeli postoje, ali konkretne realizacije nema.

Mozda cemo mi kvantnim ili dnk racunarima prosiriti granicu
izracunljivosti, ali sve je to jos neizvesno. Cuo sam na jednom predavanju o Tjuringovim masinama u
Novom Sadu, da su neki madjari oborili Cerc-Tjuringovu hipotezu na nekom modelu racunara koji ukljucuje
brzine svetlosti, kvantne efekte i bog zna sta, ali nisam video da je to bas nesto odjeknulo u
naucnom svetu koji se bavi teorijom izracunljivosti. Sve je to jos fikcija.

@FuzzyCreation

Hajde, molim te, kaži ti lepo meni zašto je C++ smeće i s*****? :-)
I šta ti zapravo više preferiraš od C++-a?

Elem, izražajnosti nekog jezika doprinosi i njegova pragmatičnost, što bi sa minimalizmom izgubio.