Haskell, ett ofog eller inte?

Avdelningen för programmering, nätverk samt alternativa OS.
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Haskell, ett ofog eller inte?

Post by Xhargh »

Jag fick ett svar i tråden: http://www.64bits.se/forum/viewtopic.php?t=18120, men eftersom det var en bump så startar jag en ny tråd här istället.
gottegrisen wrote: Jag tycker nog närmast att Haskell bordet förbjudas. Haskell är det absolut ruttnaste språket som någonsin tillverkats, den enda andledningen jag kan komma på för att de använder det på chalmers är en ren prestige fråga. Att lära sig Haskell för att kunna träna på rekursion känns också totalt meningslöst då man kan köra rekursion på alla språk.
Jag har läst ett par kurser på Chalmers där jag använt haskell (funktionell programmering, programspråk och kompilatorkonstruktion), och jäklar vad mycket bättre jag blivit på programmera av att lära mig tänka på detta lite annorlunda sätt.
+ När man kodar haskell blir man grym på rekursion, det blir helt naturligt - vilket gör det enkelt att tänka i rekursiva datastrukturer om det behövs. (Iteration finns knappt i haskell).
+ Haskell har lat evaluering, alltså ingenting räknas ut förrän det behövs - detta gör att man lätt kan ha oändligt stora datastrukturer (tex träd som man bara behöver klättra lite i för att få ut rätt resultat).
+ Eftersom haskell ligger mycket närmare matematik är det lättare att skriva helt korrekta program. Alltså program som går att bevisa att de fungerar som de skall. Det blir färre buggar med bra haskellprogram än med andra språk (aj, vad jag kommer att få skit för detta...)
- Haskell är ett elända att lära sig. Det tar ett tag innan man förstår tillräckligt mycket för att man skall kunna skriva ett enkelt program. Det är också skitsvårt att skriva ut en debugtext under exekveringens gång (pga lat evaluering och sideffektfri tjafs).
- Monader <- nån som kan förklara vad det är? :)


http://www.haskell.org/
Till er som inte sett haskell så ser tex en quicksort ut så här:

Code: Select all

qsort []     = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Människa sluta genast upp med Haskell! Det korrupterar din själ och förstör posesin i programmeringen.

======================
Några skäl till att dumpa Haskell:

* Haskell är långsamt- Du borde byta namn på quicksort till slowsort.
* Haskell typning - Är så hårt typat att man gråter blod
* Haskell är fult - Det får mig och tänka på meningslösa matteformler
* Haskell läsbarhet - försök sätta dig in i ett program som någon annan gjort!

* Funktionellt - Kul när man gör ett program på 100 rader, men ett riktigt program krävs det mer tid på att plocka i hop delar än att lösa problem. Att göra testsnuttar är jättesvårt, så man skriver förlånga avsnitt innan test. Det är jobbigare/svårare för programmeraren att tänka funktionellt och man blir helt enkelt tröttare och gör fler misstag.

* Sideffekterna - Ja du sa det ju själv. Att skriva hello world är ju ett helt projekt.

* Rekursion - Skall i allmänhet undvikas om man inte vill vända på ordningsföljden på en operation. Alltså om man kan välja mellan att göra något iterativt eller rekursivt så skall man göra det iterativ för att optimera koden. Så det är ju knappast någon fördel att Haskell bara fokuserar på sitt rekursiva sätt.

* oändligt?? stora datastrukturer- Då Haskell är skrivet i C så torde det vara ganska uppenbart att det inte är något som ett imperativt språk inte skulle klara.

* Buggar - Då typningingen är så hård så tar säkert kompilatorn bort en del. Men oftast brukar man inte göra så mkt fel med typningar när man är van, då blir man mest förbannad för att kompilatorn gnäller.


* Meningsfullt? - Mig veterligen finns det ingen som använder haskell och klarar av att tjäna pengar på det. Det är ett totalt miserabelt språk som bara kan användas på universitet där det finns låga krav på att prestera något.
===========================

Chalmers är nog den enda Tekniska Högskolan som använder Haskell som förstaspråk(är dock inte säker på detta). Detta är ju knappast för sin lämplighet som språk, utan mer det faktum att John Hughs har snurrat omkring i korridorerna. Några förvirrade själar kom ju sedan på, efter att ha blivit gödade med Haskell att dra i gång Erlangspråket hos Ericsson. Detta blev ju en ekonomisk katastrof i tid, pengar och magsår. Hade istället eleverna vant sig med lite C/C++ från början så hade det nog inte hänt. Jag vågar inte ens tänka på hur mkt pengar som har hamnat i Erlang grisen, suck. Jag försökte att att gå in på erlang sidan, och kom inte ens in längre.
---
Chalmers har genom åren visat prov på stelbenhet och inkompetens i valen av undervisings språk. De fortsatte med Modula-2 alldeles för länge när de skulle använt C. När de sent om sider bytte, bytte de till nästa utdöende språk, ADA. Av din artikel döma, så har de numera gått över till JAVA vilket är ett någorlunda val, men jag skulle hellre sett C / C++. Det finns så mkt kod i C numera att alla programmerare kommer någongång råka ut för det och även ifall det inte är särskillt svårt att gå mellan C och JAVA så finns det skillnader. Om någon säger att han har 4.5 års erfarhet av C eller 4.5 års erfarhenhet av Haskell, vilken tror du en arbetsgivare helst vill ha?

Nåja, jag kom kanske lite ifrån ämnet som var:

Död åt funktionella språk, i synnerhet Haskell!


Hoppas att du tar detta med Glimten i ögat :)
/mvh Gottegrisen
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

gottegrisen wrote: Hoppas att du tar detta med Glimten i ögat :)
Självfallet... Förresten så är Hughes fortfarande och dräller på Chalmers... :)

Men jag håller inte med om att c/c++ är bättre som nybörjarspråk i programmeringsteknikkursen, inte heller att haskell (+funktionella språk borde dö).
User avatar
mirza*
Posts: 1267
Joined: 2002-04-19 15:46:47

Post by mirza* »

Wow, Haskell (funktionell programmering överhuvudtaget) verkar skitcoolt! (och skitsvårt? =))

Den där quicksorten var rätt intressant (och verkligen imponerande) måste jag säga.

Imperativa språk är ju bara för code monkeys ;D ;)
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Xhargh wrote: Självfallet... Förresten så är Hughes fortfarande och dräller på Chalmers... :)

Men jag håller inte med om att c/c++ är bättre som nybörjarspråk i programmeringsteknikkursen, inte heller att haskell (+funktionella språk borde dö).
Ahh då är du inte ensam om att vilja ha kvar Haskell på chalmers då:)

Jag vet inte om C/C++ är bättre än Haskell som nybörjar språk, men det finns ingen professionell nytta av att kunna Haskell. C räknas däremot som programmerings-basen hos både elektro och data ing(assembler undandtaget).

Men så länge som "JH" spankulerar i korridorerna så är det Haskell som gäller.... :)

Motsvarande, om Bill Gates gått på Cth, då hade alla elever kört win....
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

Man har troligen ingen professionell nytta av att kunna haskell, det stämmer kanske. Men jag anser fortfarande att man blir bättre på att programmera om man kan programmera i andra språk än imperativa (så även flera av mina vänner som också läst funk.prog)

Ang. oändligt stora datastrukturer så kan man tex ha en lista med alla talen från 1 och uppåt.

Code: Select all

a = [1..]
Antag nu att du vill göra en lista med alla jämna tal större än 0. Då kan man lätt göra detta genom att använda den oändligt stora listan i a:

Code: Select all

b = map (2*) a
(det man gör är att man applicerar funktion (2*) på varje element i a)
Sen om man vill fortsätta jobba på detta så kan man ta bort första elementet genom att göra så här

Code: Select all

c = tail b
Att göra något sådant i ett vanligt imperativt språk skulle ta oändlig tid, men i haskell går det på ett kick, pga lat evaluering. Försök inte skriva ut den oändliga listan bara - då har datorn att göra ett tag.
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Hehe haskell i ett nötskal, räkna med oändligheten:)

Jag ifrågasätter inte din ståndpunkt, men vad exakt tycker du att man blir bättre på när man programmerar funktionellt än imperativt?.
Själv har jag ju också suttit en obligatorisk del haskell på chalmers, men skulle inte ens funderat på valt det språket om jag hade haft några alternativ. Om ditt resenomang stämmer skulle ju Cth elever dessutom vara bättre än Kth elver när de är klara? :)
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

Man blir bättre genom att man ser att det finns flera olika angreppssätt på problem man kanske har löst tidigare - man lär sig ett annat sätt att tänka.
User avatar
phubuh
Posts: 198
Joined: 2002-10-02 19:04:05

Post by phubuh »

Det glädjer mig att åtminstone ett universitet i Sverige förstår vad de sysslar med. Haskell är utmärkt för att lära ut programmering via, men för verkliga projekt är O'Caml bättre. Effektivitet i klass med C och oftast snabbare än C++, ett genomtänkt objektsystem, bindings till skojiga saker som SDL och OpenGL, ett type-inferrande Hindley-Mindler-system, och en preprocessor som slår allt annat.
User avatar
IcePic
Hedersbit
Posts: 6061
Joined: 2002-03-08 16:09:38

Post by IcePic »

phubuh wrote:Det glädjer mig att åtminstone ett universitet i Sverige förstår vad de sysslar med. Haskell är utmärkt för att lära ut programmering via, men för verkliga projekt är O'Caml bättre. Effektivitet i klass med C och oftast snabbare än C++, ett genomtänkt objektsystem, bindings till skojiga saker som SDL och OpenGL, ett type-inferrande Hindley-Mindler-system, och en preprocessor som slår allt annat.
Får man då får reiterera gottegrisens fråga:
"vad exakt tycker du att man blir bättre på när man programmerar funktionellt än imperativt?"

Du verkar ju också vara på "haskells sida" i den här debatten, så lite mer info
än "det är utmärkt" och "det är genomtänkt" vore intressant att höra.
Jag kan tycka m68k-asm är utmärkt och genomtänkt (jmf med andra assemblers)
men skulle ändå inte rekommendera det för folk som rent allmänt vill programmera.
Oh give me a clone, my very own clone,
with the Y chromosome changed to X!
And since she's my own, of my own flesh and bone,
she'll be thinking of nothing but sex!
durand
Posts: 34
Joined: 2002-09-30 18:11:47
Location: Luleå
Contact:

Post by durand »

Även Luleå Tekniska Universitet har funktionell programmering (Haskell) som första språk. Om det är jättebra eller inte kan man ju diskutera men i mitt tycke kan det faktiskt vara ett nyttigt språk att börja med om man aldrig har hållt på med programmering tidigare. Inte för att det är ett bra och användbart språk i sig, utan för att de får en inblick på programmering utifrån ett annat perspektiv än vad man vanligen får. Det är i alla fall min uppfattning.

För att kommentera kursen i Luleå måste jag säga att den faktiskt var helt ok, men det beror bara på en sak, vår föreläsare, som var/är fruktansvärt pedagogisk och bra på alla sätt.
User avatar
phubuh
Posts: 198
Joined: 2002-10-02 19:04:05

Post by phubuh »

IcePic wrote: Får man då får reiterera gottegrisens fråga:
"vad exakt tycker du att man blir bättre på när man programmerar funktionellt än imperativt?"

Du verkar ju också vara på "haskells sida" i den här debatten, så lite mer info
än "det är utmärkt" och "det är genomtänkt" vore intressant att höra.
Jag kan tycka m68k-asm är utmärkt och genomtänkt (jmf med andra assemblers)
men skulle ändå inte rekommendera det för folk som rent allmänt vill programmera.
Haskell representerar inte alla funktionella språk och det är inte på alla jag syftar. Det finns många funktionella språk som inte lämpar sig speciellt bra som introduktioner till programmering, bland andra XSLT och Unlambda.

Jag anser att Haskell är en bra början för att det är så transparent. Algoritmer kan översättas till elegant Haskell-kod genom nästan mekanisk notationsöversättning, och typer är intuitivt deklarerade. Detta gör att utbildningen kan fokusera mer på de egentliga algoritmerna och datatyperna, i stället för att som många imperative kurser ägna tiden åt att lära ut syntaxen för loopar och att läsa in och skriva ut via konsolen.
iman
Posts: 2
Joined: 2003-06-02 23:25:55

Post by iman »

Haskell har sina för och nackdelar precis som vilka andra språk som helst.
det kan ju vara bra att kunna ett funktionellt och ett imperativt då kan man ju anävnda båda där det bäst behövs, eller?
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Ser ingen mening överhuvudtaget med att kunna haskell och funktionella språk generellt. Programutveckkling i haskell och erlang är både tråkigt krävande och omständigt. Detta avspeglar sig i verkligheten, där de funktionella språken för en tynande tillvaro.

Rent principiellt går det ju att programmera funktionellt i imperativa språk, skillnaden är ju att man bara har ett returvärde. Nu är det nog ganska få som kommer på den "brillanta" tanken att bara använda sig av funktioner i ett imperativt språk.

Att sedan tro att det är viktigare att kunna lösa algoritmer innan man ens kan en repetionssats/rekursion verkar något ologiskt. Jag är även helt övertygad om att det är lättare att lära sig en while sats än än rekursion vilket torde vara ett argument för ett imperativt språk. När sedan program blir snabbare av att använda iteration än rekursion vete fan om det ens är en fördel att kunna rekursion.

Jag tror också att man blir bättre för varje nytt språk, man lär sig nya saker för varje språk. Man jämför fördelar och nackdelar mellan dem. Det som jag har lärt mig med funktionella språk, är det är omständigt och ett felaktig sätt att programmera.
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

iman wrote:Haskell har sina för och nackdelar precis som vilka andra språk som helst.
det kan ju vara bra att kunna ett funktionellt och ett imperativt då kan man ju anävnda båda där det bäst behövs, eller?
Håller helt och hållet med.
I en av systemutvecklingskurserna jag har läst (där vi fick välja språk ganska fritt, dock helst java/ada) så gav de som exempel på att man skall använda det språk som passar bäst för det projekt man skall göra att det var ett system med livsuppehållande funktioner på något sjukhus - alltså mycket beroende av att det inte skall bli fel, förut var programmet skrivet i c, det blev dock fel ibland så de beslutade att de skulle skriva om programmet. Denna gång blev det implementerat i haskell/ml - då minskade helt plötsligt antal fel (och fler människor klarade sig). (kommer inte ihåg exakta detaljer...). För fler exempel på haskell, se här http://www.haskell.org/practice.html (fast att göra quake i haskell känns fel)
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

gottegrisen wrote:Ser ingen mening överhuvudtaget med att kunna haskell och funktionella språk generellt. Programutveckkling i haskell och erlang är både tråkigt krävande och omständigt. Detta avspeglar sig i verkligheten, där de funktionella språken för en tynande tillvaro.
http://www.research.avayalabs.com/user/ ... index.html <- här verkar dock finnas mest forskningsprojekt...
En anleding till att det inte finns så mycket funktionell programmering i industrin är att det finns så få som kan programmera funktionellt. För att kunna göra en jämförande test på vilken mjukvara som blir "bäst" krävs det att de som testar kan programmera funktionellt, då helst precis lika bra som de som programmerar imperativt.
Haskell vs. Ada vs. C++ vs. Awk vs... - An Experiment in Software Prototyping Productivity (16 sidor, postscript)
gottegrisen wrote: Rent principiellt går det ju att programmera funktionellt i imperativa språk, skillnaden är ju att man bara har ett returvärde. Nu är det nog ganska få som kommer på den "brillanta" tanken att bara använda sig av funktioner i ett imperativt språk.
Har du lat evaluering i imperativa språk?
gottegrisen wrote: Att sedan tro att det är viktigare att kunna lösa algoritmer innan man ens kan en repetionssats/rekursion verkar något ologiskt. Jag är även helt övertygad om att det är lättare att lära sig en while sats än än rekursion vilket torde vara ett argument för ett imperativt språk. När sedan program blir snabbare av att använda iteration än rekursion vete fan om det ens är en fördel att kunna rekursion.
Ja, visst sjutton är det bra att kunna programmera lite innan man börjar med algoritmer och funktionell programmering.
Men vad som är mest logiskt - en while-sats eller rekursion beror på vem man frågar. En självlärd programmerare skulle nästan med säkerhet säga att while-satsen är mer logisk, medan en van programmerare (som kan en del matematik och lite funktionell programmering) skulle i många fall säga att rekursion är bra då det passar och while-satsen är bra då den passar. Min erfarenhet är att rekursion är jättesvår i början - men har man väl förstått rekursion ordentligt så är det väldigt trevligt.

Angående att ett program blir snabbare med iteration än med rekursion så kan jag säga att kompilatorerna idag är riktigt duktiga på att optimera.
Sen är det väldigt många saker som är väldigt svåra att skriva mha iteration, som är lätta mha rekursion. Att traversera träd är i många fall enkelt och smidigt med rekursion men ett härke med iteration.
För att kunna ersätta rekursion helt med iteration så krävs det (i en del fall) att man använder memorisering, man simulerar en rekursion...
Det är inte några problem att simulera iteration mha rekursion.
gottegrisen wrote: Jag tror också att man blir bättre för varje nytt språk, man lär sig nya saker för varje språk. Man jämför fördelar och nackdelar mellan dem. Det som jag har lärt mig med funktionella språk, är det är omständigt och ett felaktig sätt att programmera.
Det låter som att du inte har så goda erfarenheter av haskell...

Jag får väl för sakens skull tillägga att jag inte använder Haskell allt för ofta, det var första gången på nästan två år jag skrev lite haskell för att kunna skriva exemplen tidigare i tråden :)
User avatar
phubuh
Posts: 198
Joined: 2002-10-02 19:04:05

Post by phubuh »

gottegrisen wrote:Ser ingen mening överhuvudtaget med att kunna haskell och funktionella språk generellt.
Jag ser ingen anledning att inte lära sig nya saker.
Programutveckkling i haskell och erlang är både tråkigt krävande och omständigt.
Extensiv forskning har många gånger kommit fram till motsatsen; se till exempel Ericssons dokument om produktivitet med Erlang, eller dokumentet Xhargh länkade till.
Detta avspeglar sig i verkligheten, där de funktionella språken för en tynande tillvaro.
Argumentum ad populus.
Rent principiellt går det ju att programmera funktionellt i imperativa språk, skillnaden är ju att man bara har ett returvärde. Nu är det nog ganska få som kommer på den "brillanta" tanken att bara använda sig av funktioner i ett imperativt språk.
Du verkar inte över huvud taget förstå vad funktionell programmering innebär.
Att sedan tro att det är viktigare att kunna lösa algoritmer innan man ens kan en repetionssats/rekursion verkar något ologiskt.
Det är helt självklart att eleverna måste lära in syntaxen och semantiken av språket; min poäng är att till akademiskt inriktade är det mycket lättare med Haskell, då dess syntax, semantik, och kanoniska stil ligger mycket närmare matematikens.
Jag är även helt övertygad om att det är lättare att lära sig en while sats än än rekursion vilket torde vara ett argument för ett imperativt språk.
Jag håller inte med, men om vi antar att ditt påstående är sant: är latin sämre som exempelspråk i en kurs i linguistik än tyska, för att det är svårare att lära sig?
När sedan program blir snabbare av att använda iteration än rekursion vete fan om det ens är en fördel att kunna rekursion.
Min dator vill inte riktigt hålla med:

Code: Select all

test.ml:

let rec loop = function
  | 0.0 -> ()
  | n -> print_float (sqrt n); print_newline (); loop (n -. 1.0)

let _ = loop 100000.0
Den tar 4.324 sekunder att köra.

Code: Select all

test.cpp:

#include <iostream>
#include <cmath>
using namespace std;

void
print (float n) {
    cout << sqrt(n) << endl;
}

int
main (int argc, char **argv)
{
    float i = 100000.0;
    while (i > 0.0) {
        print(i);
        i -= 1.0;
    }
}
Den tar 5.5 sekunder.
Jag tror också att man blir bättre för varje nytt språk, man lär sig nya saker för varje språk.Man jämför fördelar och nackdelar mellan dem.
Japp.
Det som jag har lärt mig med funktionella språk, är det är omständigt och ett felaktig sätt att programmera.
Funktionella språk är intrinsikt behagliga att programmera i, till skillnad från de absolut populäraste imperativa språken jag kan komma på: C, C++, Java, et al. Ska vi tävla i att implementera quicksort? Dessa är stolparna som juryn kommer att bedöma efter: tid det tar att implementera; effektivitet; elegans; läsbarhet; och genericitet.
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Xhargh:
Jag tycker att du håller en bra nivå på dina inlägg, mkt trevligt att höra dina åsikter.

Vad det gäller människor som kan funktionella språk kan åtminstone alla dataingengörer som lämnar chalmers det. Totalt sett inom landet har du självklart rätt i att det är mindre som kan funktionella. Jag ser detta som en sund och logisk siffra, då haskell inte har ett egentligt användningsområde utanför högskolorna.

Vad det gäller artiklar från nätet kan jag säkerligen hitta några smaskiga exempel på att haskell rockar ännu mer än dina:)
Men faktum kvarstår. När det gäller erlang var problemen många, ett problem var att ericsson hade svårt att få personal att vilja arbeta med det.(undra varför:) ) Ett annnat var att det var inte lönsamt. Numera sker ingen nyutveckling med erlang på eriksson. Ericsson har även lagt ner själva språket erlang. Försök att gå in på de gamla addresserna. Det sitter folk på det jobbet jag är nu och pillar med gamla buggia erlangprogram, tro mina ord, det är helt totalt värdelöst som språk.

Som nybörjare, skall man då börja med svåra saker eller lätta? Jag ser det naturligt att börja med loopar och sedan rekursion.

Självklart är det mkt lättare att ta till rekursion i vissa lägen, så som om man som man skall traversera ett helt träd i något syfte. Men faktum kvarstår, rekursion är långsammare. Denna optimering du pratar om, finns inte inom någon av de vanligaste C kompilatorera. I själva verket tror jag inte det finns någon sådan otpimering överhuvudtaget. Självklart kan du bevisa mig att ha fel genom att använda dig av fibinachi talen rekursivt och iterativt(nybörjarkurs inom algoritmer).

Jag säger inget som att rekursion är förbjudet, men skall man skall försöka hålla sig till iteration så länge som det är praktiskt möjlig om man vill optimera koden.
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

phubuh:

Jag försökte hitta lite fakta i dina svara men de flesta var nog bara nedlåtande kommentarer. Känner inget behov av att kommentera dem.

När det gäller ditt totalt menlösa försök att bevisa att jag skulle ha fel om rekursion vet jag inte om jag ska skratta eller gråta. Du har på sin höjd bevisat att du är otroligt okunnig i frågan.

För det första: Vilken nybörjare som helst inser att man inte kan jämföra tiden mellan två olika språk. Du får ju göra båda exemplerna i samma språk, samt samma dator.

För det andra: Du gör ett extra funktionsanrop i C++ delen och därför utjämnar effekten av rekursionen.
------------------------------------------------------------------------------
Vad som skiljer rekursion och iteration åt i optimering är själva anropet och parameterpassningen.

iteration:
int i = 100;
while (i > 0)
i = i -1;
Vad händer här? Jo mkt förenklat
kan man säga att koden laddar 100 till ett register och jämför samt minskar och hoppar 100 gånger.

rekursion:
/* antar att ett anrop med minska(100) kommer */
void minska(int i)
{
if(i != 0)
minska(i-1);
}

Förutom att göra allt som det tidigare exemplet gjorde så kan detta exempel 100 gånger lägga upp variabel "i" på stacken samt retur address. Själva anropet och returen skall utföras. Brukligt är att man även sätter basepointern samt återställer dem. Har vi riktig otur och kompilatorn är sunkig kommer även register att skyddas i onödan vilket innebär att de skall upp och ner på stacken.

Numera finns även optimering som gör att man skickar parametrar via register, vilket hade fungerat bättre i detta fallet. Men oftast hanterar man mer data än detta fallet och åker på att spara fler register.
User avatar
phubuh
Posts: 198
Joined: 2002-10-02 19:04:05

Post by phubuh »

gottegrisen wrote:Xhargh:
Men faktum kvarstår, rekursion är långsammare. Denna optimering du pratar om, finns inte inom någon av de vanligaste C kompilatorera. I själva verket tror jag inte det finns någon sådan otpimering överhuvudtaget. Självklart kan du bevisa mig att ha fel genom att använda dig av fibinachi talen rekursivt och iterativt(nybörjarkurs inom algoritmer).

Code: Select all


let benchmark f n =
  let t0 = Sys.time () in
    for i = 0 to n do
      f n
    done;
    let t1 = Sys.time () in
      t1 -. t0

let rec_fib n =
  let rec aux a b = function
    | 0 -> b
    | x -> aux b (a + b) (x - 1)
  in
    aux 1 0 n

let iter_fib n =
  let a, b, c = ref 1, ref 1, ref 2 in
    for i = 1 to n - 2 do
      c := !a + !b;
      a := !b;
      b := !c
    done;
    !b
Detta är resultaten av benchmark med de olika funktionerna när n = 50000:

Code: Select all

phubuh@igloo phubuh $ ./ml.test.rec
5.16
phubuh@igloo phubuh $ ./ml.test.iter
22.54
EDIT: Två triviella fel gjorde så att funktionerna returnerade ogiltiga resultat. Program och tider uppdaterade.
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

gottegrisen wrote: Jag tycker att du håller en bra nivå på dina inlägg, mkt trevligt att höra dina åsikter.
Tackar :)

gottegrisen wrote: Men faktum kvarstår, rekursion är långsammare. Denna optimering du pratar om, finns inte inom någon av de vanligaste C kompilatorera. I själva verket tror jag inte det finns någon sådan otpimering överhuvudtaget.
Gcc får väl räknas som en ganska vanlig c-kompilator. Den kan iaf optimera en del rekursiva anrop:
url till nedanstående text

Code: Select all

-foptimize-sibling-calls 
  Optimize sibling and tail recursive calls. 
  Enabled at levels -O2, -O3, -Os. 
Nu kommer jag dock inte ihåg vad "sibling and tail recursive calls" är för typ av rekursion.

Sen en annan sak... vill man alltid optimera koden så att den går så snabbt som möjligt/tar så lite minne som möjligt? Jag skulle vilja påstå att man borde skriva felfria program - och det gör man lättast genom att välja rekursion eller iteration beroende på vilket som är mest naturligt i situationen.

Du skriver också att alla dataingenjörer som lämnar chalmers kan funktionell programmering... detta tror jag är sanning med modifikation. Visst att alla har läst funkprog, men att alla skulle kunna det när de slutar är nog att ta i. Sen kan de nog något annat språk mycket bättre.

Jag skulle nog vilja påstå att prolog är bra i vissa fall också (även om inte jag kan komma på något), detta bara för att blanda in fler programmeringsparadigmer i diskussionen. :)
User avatar
phubuh
Posts: 198
Joined: 2002-10-02 19:04:05

Post by phubuh »

gottegrisen wrote:phubuh:
Jag försökte hitta lite fakta i dina svara men de flesta var nog bara nedlåtande kommentarer. Känner inget behov av att kommentera dem.
OK.
När det gäller ditt totalt menlösa försök att bevisa att jag skulle ha fel om rekursion vet jag inte om jag ska skratta eller gråta. Du har på sin höjd bevisat att du är otroligt okunnig i frågan.
Det är jag inte.
För det första: Vilken nybörjare som helst inser att man inte kan jämföra tiden mellan två olika språk. Du får ju göra båda exemplerna i samma språk, samt samma dator.
Vilken nybörjare som helst kan se att den rekursiva funktionen inte har någon större algoritmskomplexitet. Det här är fortfarande ett slag mellan funktionella språk och iterativa språk. Jag gjorde samma sak med rekursion i ett funktionellt språk och med iteration i ett imperativt språk och visade att det funktionella var snabbare.
För det andra: Du gör ett extra funktionsanrop i C++ delen och därför utjämnar effekten av rekursionen.
Med outputen direkt i loopen tar programmet 5.1 sekunder.
rekursion:
/* antar att ett anrop med minska(100) kommer */
void minska(int i)
{
if(i != 0)
minska(i-1);
}

Förutom att göra allt som det tidigare exemplet gjorde så kan detta exempel 100 gånger lägga upp variabel "i" på stacken samt retur address. Själva anropet och returen skall utföras. Brukligt är att man även sätter basepointern samt återställer dem. Har vi riktig otur och kompilatorn är sunkig kommer även register att skyddas i onödan vilket innebär att de skall upp och ner på stacken.
Visste du något om fältet skulle du förstå att om kontinuationen när rekursionen sker är ekvivalent med identitetsfunktionen kan allt stacktrams hoppas över.
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

Xhargh wrote:
gottegrisen wrote: Jag tycker att du håller en bra nivå på dina inlägg, mkt trevligt att höra dina åsikter.
Tackar :)

gottegrisen wrote: Men faktum kvarstår, rekursion är långsammare. Denna optimering du pratar om, finns inte inom någon av de vanligaste C kompilatorera. I själva verket tror jag inte det finns någon sådan otpimering överhuvudtaget.
Gcc får väl räknas som en ganska vanlig c-kompilator. Den kan iaf optimera en del rekursiva anrop:
url till nedanstående text

Code: Select all

-foptimize-sibling-calls 
  Optimize sibling and tail recursive calls. 
  Enabled at levels -O2, -O3, -Os. 
Nu kommer jag dock inte ihåg vad "sibling and tail recursive calls" är för typ av rekursion.

Sen en annan sak... vill man alltid optimera koden så att den går så snabbt som möjligt/tar så lite minne som möjligt? Jag skulle vilja påstå att man borde skriva felfria program - och det gör man lättast genom att välja rekursion eller iteration beroende på vilket som är mest naturligt i situationen.

Du skriver också att alla dataingenjörer som lämnar chalmers kan funktionell programmering... detta tror jag är sanning med modifikation. Visst att alla har läst funkprog, men att alla skulle kunna det när de slutar är nog att ta i. Sen kan de nog något annat språk mycket bättre.

Jag skulle nog vilja påstå att prolog är bra i vissa fall också (även om inte jag kan komma på något), detta bara för att blanda in fler programmeringsparadigmer i diskussionen. :)
Den optimeringing har jag inte testat måste jag medge, men skriver man det iterativt så är det redan optimerat:)

Vad det gäller prolog är jag helt bortdribblad :)
User avatar
gottegrisen
Posts: 221
Joined: 2002-03-11 12:47:17
Location: Mölnlycke

Post by gottegrisen »

phubuh wrote:
gottegrisen wrote:Xhargh:
Men faktum kvarstår, rekursion är långsammare. Denna optimering du pratar om, finns inte inom någon av de vanligaste C kompilatorera. I själva verket tror jag inte det finns någon sådan otpimering överhuvudtaget. Självklart kan du bevisa mig att ha fel genom att använda dig av fibinachi talen rekursivt och iterativt(nybörjarkurs inom algoritmer).

Code: Select all


let benchmark f n =
  let t0 = Sys.time () in
    for i = 0 to n do
      f n
    done;
    let t1 = Sys.time () in
      t1 -. t0

let rec_fib n =
  let rec aux a b = function
    | 0 -> b
    | x -> aux b (a + b) (x - 1)
  in
    aux 1 0 n

let iter_fib n =
  let a, b, c = ref 1, ref 1, ref 2 in
    for i = 1 to n - 2 do
      c := !a + !b;
      a := !b;
      b := !c
    done;
    !b
Detta är resultaten av benchmark med de olika funktionerna när n = 50000:

Code: Select all

phubuh@igloo phubuh $ ./ml.test.rec
5.16
phubuh@igloo phubuh $ ./ml.test.iter
22.54
EDIT: Två triviella fel gjorde så att funktionerna returnerade ogiltiga resultat. Program och tider uppdaterade.
Ser inte ut som C det där...
Tar den rekursiva lösningen 25 % av tiden av den den itertiva, har jag tre möjliga alternativ:
*Sunkigt program
*Sunkigt språk
*Sunkig test
Värsta fall en kombination...
Xhargh
Posts: 1177
Joined: 2002-10-21 15:05:32
Contact:

Post by Xhargh »

gottegrisen wrote:Vad det gäller prolog är jag helt bortdribblad :)
Det är du inte ensam om.. men det skall vara effektivt i ai-sammanhang har jag hört
Post Reply