mbishop changed the topic of #ocaml to: Discussions about the OCaml programming language | http://caml.inria.fr/ | Grab Ocaml 3.10.0 from http://caml.inria.fr/ocaml/release.html (featuring new camlp4 and more!)
rwmjones has quit [Read error: 110 (Connection timed out)]
seafoodX has joined #ocaml
buluca has joined #ocaml
screwt8 has joined #ocaml
Abo-Marwan has joined #ocaml
rwmjones has joined #ocaml
crabstick has joined #ocaml
Smerdyakov has quit ["Leaving"]
yminsky has joined #ocaml
yminsky has quit [Client Quit]
olegfink has joined #ocaml
jlouis has quit [Read error: 110 (Connection timed out)]
ednarofi has joined #ocaml
seafoodX has quit []
seafoodX has joined #ocaml
nuncanada has quit [Read error: 110 (Connection timed out)]
buluca has quit [Read error: 113 (No route to host)]
lde has quit [Remote closed the connection]
lde has joined #ocaml
slipstream-- has joined #ocaml
slipstream has quit [Read error: 110 (Connection timed out)]
seafoodX has quit []
ednarofi has quit [Read error: 110 (Connection timed out)]
ednarofi has joined #ocaml
tty56 has quit [Read error: 60 (Operation timed out)]
buluca has joined #ocaml
olegfink has quit [Read error: 104 (Connection reset by peer)]
olegfink has joined #ocaml
m3ga has joined #ocaml
SgtTFK is now known as TFK
ednarofi has quit [Read error: 110 (Connection timed out)]
ednarofi has joined #ocaml
jedai has joined #ocaml
<bla> I wonder what stack depth is reachable with ocaml? (compiled with ocamlopt)
TFK has quit []
<bla> I'd need about 100,000 frames on stack. And it ends with Stack_overflow at about 87,000.
<bla> Is there anything I can improve?
<bla> (except for algorithm. ;p)
Demitar has quit [Read error: 110 (Connection timed out)]
<flux> bla, ulimit?
<flux> increase stack size
Demitar has joined #ocaml
<bla> flux, hm, ok; will see that. But it's not perfect solution -> program is going to work in environment I can't modify.
<flux> bla, maybe you can run ulimit from your program? (does the Unix-module provide that)
<bla> It's program for spoj.sphere.pl (something like a 'problem solver site') maybe you know it.
<bla> It works with ulimit -s 20000 (was about 8MB)
<bla> But spoj disallows Unix module.
<flux> bla, another option is to convert the program to CPS
m3ga has quit ["disappearing into the sunset"]
<flux> bla, that way you keep the call stack in your own data structures and all calls are subject to tail call optimization
<bla> That's an option;
<bla> I'll start with checking what's their setting.
<bla> Maybe it will suffice, and problem was plainly on mine site.
<bla> Then, there's no problem. ;d
<bla> In most pesimistic case 10MB of stack space is enough.
<bla> So it's not bad.
|Jedai| has joined #ocaml
buluca has quit [Read error: 113 (No route to host)]
jedai has quit [Read error: 110 (Connection timed out)]
buluca has joined #ocaml
EliasAmaral has joined #ocaml
buluca has quit [Read error: 113 (No route to host)]
seafoodX has joined #ocaml
smimou has joined #ocaml
seafoodX has left #ocaml []
smimou has quit ["bli"]
smimou has joined #ocaml
crathman has joined #ocaml
Tetsuo has joined #ocaml
crathman_ has joined #ocaml
yminsky has joined #ocaml
yminsky has quit []
crathman has quit [Read error: 110 (Connection timed out)]
smimou has quit ["bli"]
Smerdyakov has joined #ocaml
CRathman has joined #ocaml
pango has quit [Remote closed the connection]
pango has joined #ocaml
Tetsuo has quit ["Leaving"]
ita has joined #ocaml
<jonathanv> is it possible that my ocaml interpreter does not support tail recursion
<rwmjones> jonathanv, no, but it is very possible that your function isn't written in a tail-recursive way
<rwmjones> post it please
<jonathanv> it's simple, it's just a reimplementation of map
<jonathanv> i already rewrote it with loops
<jonathanv> but it'd have been let rec mymap f lst = match lst with [] -> [] | head :: tail -> f head || mymap f tail;;
<jonathanv> er the || should be ::
<Smerdyakov> Not tail recursive.
<jonathanv> no?
<Smerdyakov> It's obvious if you think about the compiled code, but let me see if the manual has an official source-level characterization.
screwt8 has quit [Remote closed the connection]
Abo-Marwan has quit [Remote closed the connection]
pango has quit [Remote closed the connection]
<Smerdyakov> Well, no easy solution found.
<Smerdyakov> This should be a safe way to think about it: Convert to CPS mentally and see if the recursive call has the same continuation as the original.
<Smerdyakov> This should be a hazier way to do it: Ask yourself if there's work left to do after the recursive call but before returning from the original.
<jonathanv> i'm not sure what CPS is
<Smerdyakov> Then read about it or ignore the more precise explanation. The choice is yours. :-)
<jonathanv> okay
<Smerdyakov> I hope the hazier explanation makes clear why your example isn't tail recursive.
pango has joined #ocaml
<Smerdyakov> What definition of "tail recursive" have you been using that led you to think your example was tail recursive?
<jonathanv> the recursive call is the last thing in the function
leo037 has joined #ocaml
<Smerdyakov> If you mean in the linear, ASCII syntax, then that is definitely a great misunderstanding.
<Smerdyakov> Tail recursiveness must be expressed in terms of AST (syntax tree) structure. There's no easy description in terms of flat text.
<Smerdyakov> Your description is helpful, though informal, if you are talking about _execution_order_, not textual order.
<jonathanv> so uh
<jonathanv> okay
<jonathanv> f head :: mymap f tail would execute after mymap f tail
<Smerdyakov> Yup.
<jonathanv> okay i got it
Abo-Marwan has joined #ocaml
screwt8 has joined #ocaml
Demitar has quit [Read error: 110 (Connection timed out)]
ednarofi has quit [Connection timed out]
schme has quit [Remote closed the connection]
schme has joined #ocaml
|Jedai| is now known as jedai
buluca has joined #ocaml
seafoodX has joined #ocaml
<jonathanv> okay, my mergesort is now completely tail recursive and incredibly inefficient
<jonathanv> and it still blows the stack on 10 million ints
<jonathanv> oh well
ygrek has joined #ocaml
<jonathanv> mergesort isn't very memory friendly anyway
<Smerdyakov> I would like to see your tail-recursive merge sort.
<jonathanv> are you sure.
<Smerdyakov> Yes.
<jonathanv> You're going to be blown away
<ita> do not look!
<ita> :-)
<jonathanv> maybe merge2 is not properly tail recursive?
<jonathanv> also @ seems to have trouble
<Smerdyakov> Yup, that's ugly.
<Smerdyakov> But every 'rec' function _is_ tail recursive.
<Smerdyakov> Anyway, gotta go.
<jonathanv> WOO
<bla> ?
<bla> _every_ 'rec' function is tail recursive?
<bla> Since when?
<jonathanv> he's referring to my crappy mergesort implementation
<bla> Uh. Ok. I though it was generalisation.
<bla> ;)
<jonathanv> it would be nice
buluca has quit [Read error: 113 (No route to host)]
grirgz has quit [Read error: 104 (Connection reset by peer)]
jlouis has joined #ocaml
seafoodX has quit []
crathman_ has quit ["ChatZilla 0.9.78.1 [Firefox 2.0.0.6/2007072518]"]
CRathman_ has joined #ocaml
CRathman_ has quit [Remote closed the connection]
<pango> jonathanv: mymap2 is List.rev_map
<pango> jonathanv: List.rev lst2 @ accum is List.rev_append lst2 accum
<jonathanv> are those tail recursive? that's the only reason i did those
<pango> look at list.mli, it's documented
<jonathanv> okay
<pango> in merge2, you could match both lists at once match lst1, lst2 with | [], _ -> ... etc.
CRathman has quit [Read error: 110 (Connection timed out)]
<jonathanv> oh, i didn't know you could do that
<jonathanv> i'm way newbie.. i wrote the mergesort to learn ocaml better
<ita> i hate when the compiler starts talking about inconsistent assumptions over interfaces
<flux> the last time I had it was because I was missing one .mli-file from the generated dependencies
<flux> (it didn't go away with make clean, I had to fix it :))
crabstick_ has joined #ocaml
<pango> jonathanv: it works because you can pattern match on tuples, and that match lst1, lst2 with ... is the same as match (lst1, lst2) with ... (parens are optional around tuples in several contexts)
cannedfish has joined #ocaml
ygrek has quit [Remote closed the connection]
Maldoror_ has quit [Read error: 110 (Connection timed out)]
crabstick has quit [Read error: 110 (Connection timed out)]
bzzbzz has quit ["leaving"]
cannedfish has quit [Remote closed the connection]
cannedfish has joined #ocaml
bzzbzz has joined #ocaml
Demitar has joined #ocaml
Demitar has quit [Dead socket]
smimou has joined #ocaml
cannedfish has quit ["leaving"]
leo037 has quit ["Leaving"]
mbishop_ has joined #ocaml
buluca has joined #ocaml
mbishop has quit [Remote closed the connection]
mbishop_ has quit ["leaving"]
mbishop has joined #ocaml
mbishop has quit ["leaving"]
rwmjones has left #ocaml []
mbishop has joined #ocaml
ita is now known as ita|zzz