Darren New <dne### [at] sanrrcom> wrote:
> That said, I've found I rarely need it

  It's not usual to need it, but sometimes it can be quite useful.
Almost anything involving things like permutations and combinations
are significantly easier to express recursively than iteratively.

> If you can handle the program crashing when you 
> give it too much data in a way that generates bogus results, then sure, feel 
> free. :-)

  As I said, if the recursion depth is O(log n), then you *can't* give it
so much data as for the stack space to run out. It's physically impossible.

  If your recursion level is O(n), then it sounds a lot like an iterative
algorithm that has been expressed recursively for no good reason. (Of
course exceptions probably exist, but are rare.)

-- 
                                                          - Warp

Post a reply to this message

>> OK. And I was just saying that Haskell /already/ lets you use libraries
>> written in C, which aren't functional at all.
>
> And can the C call back into the Haskell?

Yes. I demonstrated using the C sort() function to sort Haskell data, 
remember?

> And if so, are all the Haskell invariants and such maintained?

You have to tell the compiler whether or not you consider the C function 
to be "pure" or not. Obviously, you can lie. Don't do that.

> And can you do that without telling the
> caller whether they're calling C or compiled Haskell?

Does sort() know what it's calling?

>> What I /meant/ to write was that you start a transaction, fetch the next
>> work item, and then end the transaction. Once the transaction is over,
>> you can do as much I/O as you like.
>
> Right. But if "fetch the transaction" means "obtain it from the server
> over there using TCP/IP", then you're kind of screwed, aren't you?

Yeah. STM only works for stuff local to one machine.

Or rather, the implementations I've seen only work local to one machine. 
It's quite plausible you could extend it so that the transactional data 
you're mutating might be remote - but them it would be the STM engine 
sending network traffic, not you.

> Heck, even a regular expression match isn't functional in .NET.

Probably. In fact, I doubt much of the .NET libraries are. So you would 
probably end up using existing Haskell libraries for anything except 
actual I/O - the thing that .NET is good at.

>> The problem (I assume) that you're talking about is that all the existing
>> .NET stuff is structured under the assumption that you can do I/O
>> whenever
>> you feel like it. I can see a few ways to approach that. (Perhaps the
>> simplest possibility being "only Haskell is allows to use STM". :-P )
>
> And that's the kind of incompatibility I'm saying makes .NET much less
> useful.

Certainly it makes it less useful, yes. Whether it makes it "not worth 
it at all" is more open to debate.

Post a reply to this message

On 4/28/2012 1:33, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> That said, I've found I rarely need it
>
>    It's not usual to need it, but sometimes it can be quite useful.
> Almost anything involving things like permutations and combinations
> are significantly easier to express recursively than iteratively.

Fair enough. That said, you can usually tell by looking at the input 
structure how deeply you'll likely need to recurse for something like that.

>> If you can handle the program crashing when you
>> give it too much data in a way that generates bogus results, then sure, feel
>> free. :-)
>
>    As I said, if the recursion depth is O(log n), then you *can't* give it
> so much data as for the stack space to run out. It's physically impossible.

Oh? How deep is your stack? Are you sure your on-the-heap data structure 
hasn't used up all your potential stack space?

The point is not that if the algorithm is all you're doing, you won't run 
out of stack space. The point is that you don't know how much stack depth 
you have, what's on the stack above you, or how big your data structure is, 
even assuming you're recursing due to a data structure.

Or how much stack space the thing you're calling during the recursion takes, 
if your recursion is part of a more generic data structure. If you say 
"process each node of the DOM with this lambda", you don't know what that 
lambda is going to do.

Why does C++ limit the depth of template instantiation required to 17 
levels, or whatever it is? Clearly, it's possible to run out of stack doing 
recursion.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 4/28/2012 2:56, Orchid Win7 v1 wrote:
> You have to tell the compiler whether or not you consider the C function to
> be "pure" or not. Obviously, you can lie. Don't do that.

Fair enough.

>> And can you do that without telling the
>> caller whether they're calling C or compiled Haskell?
>
> Does sort() know what it's calling?

I don't know. That's why I'm asking. :-)

>> Heck, even a regular expression match isn't functional in .NET.
>
> Probably. In fact, I doubt much of the .NET libraries are. So you would
> probably end up using existing Haskell libraries for anything except actual
> I/O - the thing that .NET is good at.

I think .NET is good at more than just I/O. :-) Actually, I don't think .NET 
is any better at I/O that anything else on Windows is.

>> And that's the kind of incompatibility I'm saying makes .NET much less
>> useful.
>
> Certainly it makes it less useful, yes. Whether it makes it "not worth it at
> all" is more open to debate.

It breaks a fundamental tenet of .NET, which is that it doesn't matter what 
language the caller is written in vs the callee. MS saying that "yes, this 
.NET library works, but only if you call it from Haskell and not C# or VB or 
F#" would not fly well.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >    As I said, if the recursion depth is O(log n), then you *can't* give it
> > so much data as for the stack space to run out. It's physically impossible.

> Oh? How deep is your stack? Are you sure your on-the-heap data structure 
> hasn't used up all your potential stack space?

  As I said, if your recursion depth is O(log n), then you would need a
ridiculous amount of data in order to run out of stack space even with
a very stack-hungry recursive function. (For example, if your recursion
level were 50, then the input data, even if it took just 1 byte per element,
would require something like 1024 terabytes of RAM. How likely are you going
to run out of stack space with that few recursion levels? You could easily
have that many function calls on the stack even without recursion.)

  It's highly unusual to require enormous amounts of stack on one single
function call, especially if you are implementing a recursive algorithm.
If each function call takes exponentially more stack space than there's
input, you are doing something wrong. (And even if you did, your algorithm
would be quite slow, as each function call would be operating on a rather
large amount of local data.)

> Why does C++ limit the depth of template instantiation required to 17 
> levels, or whatever it is?

  Never heard of such a limit.

-- 
                                                          - Warp

Post a reply to this message

On 4/28/2012 9:52, Warp wrote:
> level were 50,

I understand your argument. I'm unconvinced that you're (a) not already 40 
levels of stack deep when you get invoked, and (b) know what your stack 
recursion depth can be.

Maybe I'm just used to working on machines with actual limited address space 
and RAM. 50 levels of recursion sounds like a lot of stack space used, to me.

 >   It's highly unusual to require enormous amounts of stack on one single
function call,

I would think that depends on the program. If you're making an image of your 
input data for each level, you're screwed, which is why people tend not to 
do that sort of thing. If (maybe) you're parsing a programming language, I 
can see each level having a fairly large amount of data associated with it.

> would require something like 1024 terabytes of RAM. How likely are you going
> to run out of stack space with that few recursion levels? You could easily
> have that many function calls on the stack even without recursion.)

That's my point! :-)

>> Why does C++ limit the depth of template instantiation required to 17
>> levels, or whatever it is?
>
>    Never heard of such a limit.

IIRC, template function nesting is only required to be supported to some 
realtively small depth.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> On 4/28/2012 9:52, Warp wrote:
> > level were 50,

> I understand your argument. I'm unconvinced that you're (a) not already 40 
> levels of stack deep when you get invoked, and (b) know what your stack 
> recursion depth can be.

  My point is that you are not going to get even close to 50. Perhaps
something like 20.

  If your stack can't hold hundreds of recursive function calls, then
you should upgrade your computer to the new millenium.

> Maybe I'm just used to working on machines with actual limited address space 
> and RAM. 50 levels of recursion sounds like a lot of stack space used, to me.

  What? Even if each function call took like a kilobyte of space (which is
quite a lot for one single function call), it would still be just 50 kB.
I think stack sizes are counted in megabytes in modern systems.

>  >   It's highly unusual to require enormous amounts of stack on one single
> function call,

> I would think that depends on the program. If you're making an image of your 
> input data for each level, you're

doing it wrong. (If for nothing else, then because it increases the
computational complexity of your algorithm by a factor of n, which is quite
a lot. Eg. a fast O(n log n) algorithm becomes a crawling O(n^2 log n).
Not to talk about if the original algorithm was eg. O(n^2) to begin with...)

> >> Why does C++ limit the depth of template instantiation required to 17
> >> levels, or whatever it is?
> >
> >    Never heard of such a limit.

> IIRC, template function nesting is only required to be supported to some 
> realtively small depth.

  I suppose the standard probably as a minimum recommended amount (like
it has for many other things, like the length of variable names). However,
if you surpass that limit your program won't even compile, so it's not
a question of running out of memory when running the program. (And most
C++ compilers have an option to increase the space dedicated to type
names.)

  Consider that some projects use template metaprogramming quite
extensively, and the internal type names that result from it can be
quite large (we are talking about thousands and thousands of characters).
Most C++ programs don't use type names that long.

-- 
                                                          - Warp

Post a reply to this message

On 4/28/2012 10:14, Warp wrote:
>    If your stack can't hold hundreds of recursive function calls, then
> you should upgrade your computer to the new millenium.

Well, that's what I said. If I have a machine with enough power to support 
that sort of thing, I'm probably not going to be using C. :-)

PS: Pro-tip. I work for google. Don't try to spider the web recursively. ;-) 
As the machines get bigger, so do the problems people throw at them.

But you have a database with a B-Tree index? Sure, chances are you're not 
going to blow the stack walking down that tree.

I'm not saying recursion isn't useful. I'm saying that one must keep in mind 
the possible depth of recursion, because C doesn't tell you when you overrun 
the stack. You just get the same random errors you get when you run off the 
end of an array, except you haven't actually violated the spec, as far as I 
know.

>> Maybe I'm just used to working on machines with actual limited address space
>> and RAM. 50 levels of recursion sounds like a lot of stack space used, to me.
>
>    What? Even if each function call took like a kilobyte of space (which is
> quite a lot for one single function call), it would still be just 50 kB.
> I think stack sizes are counted in megabytes in modern systems.

Depends on the system. Credit card terminal? No. Last card terminal I worked 
on had 14K of space free for code and data and stack. :-)

In any case, would you call malloc() inside each level of recursion as you 
go without checking whether malloc() returned NULL? I wouldn't think so. So 
if malloc() can fail and you want to check, why not recursion? Why not just 
use the returned value from malloc() and let it crash out when you try to 
write to offset 0?

> doing it wrong.

Yep. As I said, that's why people don't do it that way.

Note, however, that we're also comparing to things like Haskell, where the 
"naive recursive algorithm" *is* the iterative algorithm.

>    I suppose the standard probably as a minimum recommended amount (like
> it has for many other things, like the length of variable names). However,
> if you surpass that limit your program won't even compile, so it's not
> a question of running out of memory when running the program. (And most
> C++ compilers have an option to increase the space dedicated to type
> names.)

Yep. All to get around problems with naive recursive algorithms.

In any case, that's the sort of thing I'm talking about. If you add a level 
of template indirection and your compiler crashes, that's one thing. If you 
add another web page to the list of web sites you're selling ads on and your 
revenue stream collapses, that's another thing.

Hope that you don't wind up adding another level to your templates and your 
compiler finishes but generates the incorrect code.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

>>> Heck, even a regular expression match isn't functional in .NET.
>>
>> Probably. In fact, I doubt much of the .NET libraries are. So you would
>> probably end up using existing Haskell libraries for anything except
>> actual I/O - the thing that .NET is good at.
>
> I think .NET is good at more than just I/O. :-) Actually, I don't think
> .NET is any better at I/O that anything else on Windows is.

Well, I haven't ever used .NET, so I couldn't say.

>>> And that's the kind of incompatibility I'm saying makes .NET much less
>>> useful.
>>
>> Certainly it makes it less useful, yes. Whether it makes it "not worth
>> it at
>> all" is more open to debate.
>
> It breaks a fundamental tenet of .NET, which is that it doesn't matter
> what language the caller is written in vs the callee. MS saying that
> "yes, this .NET library works, but only if you call it from Haskell and
> not C# or VB or F#" would not fly well.

Well, another possibility would be "you can use this library, but it's 
up to you to not do any I/O within transactions. If you do, anything 
could happen, and it will be Your Fault."

Post a reply to this message

>> When will we see the Haskell# language?
>
> I'm pretty sure the whole .NET bit is too OO to make that useful.There's
> way too much stateful stuff (like I/O) that you'd want to use from .NET
> to make it reasonable to have a purely function .net language.

I've been thinking for years that it would be cool to write a Haskell to 
Java compiler.

Yesterday night, I discovered that somebody has actually done this.

Specifically, there is a compiler which translates a language called 
"Frege" into Java. Frege is basically the same as Haskell, with a few 
tiny syntax changes. The compiler takes your Frege source code and turns 
it into Java source code, which the standard Java compiler then compiles 
as normal.

At the moment, it's all quite experimental. There's basically one person 
maintaining it, and it's still brand new. Documentation is nearly 
non-existent. The compiler is fairly slow, and error reporting leaves a 
lot to be desired. But it /works/.

I wrote 2KB of Frege code. The Frege compiler translated this into 47KB 
of Java code. The Java compiler then translated this into 12 class files 
totalling 30KB. The compilation process took just under 6 seconds.

Of course, the program I wrote is only a simple CLI thing for test 
purposes. The interesting question is "how easily can I use the features 
of Java?"

It looks like it only takes 1 line of code to turn an existing Java 
class into a valid Frege data type. (A data type which Frege then knows 
nothing about.) It takes a further 1 line of code to turn any Java 
method into a valid Frege function. I haven't actually attempted to use 
this yet, but there's some example code showing the creation of a Swing 
GUI from Frege. The example is only 50 lines long.

Clearly I'm going to have to play with this for much, much longer before 
I can say how truly /useful/ it is. It's pretty damned exciting though! :-D

Post a reply to this message