<br>I (think) I understand the problem. What I don't have any intuition about is how much space would "Expensive Structure" take if it was basically an IO Char computation fed into a simple function (say checks for char being equal to "a"). Is there any way to guess, know the size of the buffer that is kept in the heap?<br>
<br>thanks,<br><br>Daryoush<br><div class="gmail_quote">On Wed, May 27, 2009 at 3:12 PM, Ryan Ingram <span dir="ltr"><<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
There's still the space used by the closure "b".<br>
<br>
An example:<br>
<br>
expensiveParser :: Parser Char ExpensiveStructure<br>
<br>
simple :: Parser Char Int<br>
<br>
withExpensive :: ExpensiveStructure -> Parser Char Int<br>
withExpensive _ = mzero -- actually always fails, not using its argument.<br>
<br>
example = do<br>
e <- expensiveParser<br>
simple `mplus` withExpensive e<br>
<br>
The expensive structure constructed by expensiveParser needs to be<br>
kept in memory throughout the entire parsing of "simple", even though<br>
withExpensive doesn't actually use it and would immediately fail. A<br>
smarter parser could realize that e couldn't actually ever be used and<br>
allow the GC to free it much more quickly.<br>
<br>
This example can be made arbitrarily more complicated; withExpensive<br>
could run different things based on the value of "e" that could be<br>
determined to fail quickly, simple might actually do a lot of work,<br>
etc. But during the "mplus" in the monadic parser, we can't free e.<br>
<font color="#888888"><br>
-- ryan<br>
</font><div><div></div><div class="h5"><br>
On Wed, May 27, 2009 at 12:49 PM, Daryoush Mehrtash <<a href="mailto:dmehrtash@gmail.com">dmehrtash@gmail.com</a>> wrote:<br>
> So long as the [s] is a fixed list (say [1,2,3,4]) there is no space<br>
> leak. My understanding was that the space leak only happens if there is<br>
> computation involved in building the list of s. Am I correct?<br>
><br>
> If so, I still don't have any feeling for what needs to be saved on the heap<br>
> to be able to back track on computation that needs and IO computation<br>
> data. What would be approximate space that an IO (Char) computation<br>
> take on the heap, is it few bytes, 100, 1k, ....?<br>
><br>
> Daryoush<br>
><br>
><br>
> On Tue, May 26, 2009 at 6:11 PM, Ryan Ingram <<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>> wrote:<br>
>><br>
>> On Tue, May 26, 2009 at 5:03 PM, Daryoush Mehrtash <<a href="mailto:dmehrtash@gmail.com">dmehrtash@gmail.com</a>><br>
>> wrote:<br>
>> > newtype Parser s a = P( [s] -> Maybe (a, [s]))<br>
>> (fixed typo)<br>
>><br>
>> > instance MonadPlus Parser where<br>
>> > P a mplus P b = P (\s -> case a s of<br>
>> > Just (x, s') -> Just (x, s')<br>
>> > Nothing -> b s)<br>
>><br>
>> > a)what exactly gets saved on the heap between the mplus calls?<br>
>><br>
>> Two things:<br>
>><br>
>> (1) Values in the input stream that "a" parses before failing.<br>
>> Beforehand, it might just be a thunk that generates the list lazily in<br>
>> some fashion.<br>
>><br>
>> (2) The state of the closure "b"; if parser "a" fails, we need to be<br>
>> able to run "b"; that could use an arbitrary amount of space depending<br>
>> on what data it keeps alive.<br>
>><br>
>> > b)I am assuming the computation to get the next character for parsing to<br>
>> > be<br>
>> > an "IO Char" type computation, in that case, what would be the size of<br>
>> > the<br>
>> > heap buffer that is kept around in case the computation result needs to<br>
>> > be<br>
>> > reused?<br>
>><br>
>> Nope, no IO involved; just look at the types:<br>
>><br>
>> P :: ([s] -> Maybe (a,[s])) -> Parser s a<br>
>><br>
>> (Parser s a) is just a function that takes a list of "s", and possibly<br>
>> returns a value of type "a" and another list [s] (of the remaining<br>
>> tokens, one hopes)<br>
>><br>
>> It's up to the caller of the parsing function to provide the token<br>
>> stream [s] somehow.<br>
>><br>
>> > c) Assuming Pa in the above code reads n tokens from the input stream<br>
>> > then<br>
>> > fails, how does the run time returns the same token to the P b?<br>
>><br>
>> It just passes the same stream to both. No mutability means no danger :)<br>
>><br>
>> -- ryan<br>
><br>
><br>
><br>
</div></div></blockquote></div><br>