On 7/21/2014 3:25 PM, Timon Gehr wrote:
> The example just uses the ST Monad which is quite similar to weakly pure
> statements in D.

D doesn't have weakly pure statements - it has weakly pure functions.

On 07/22/2014 05:02 AM, Walter Bright wrote:
> On 7/21/2014 3:25 PM, Timon Gehr wrote:
>> The example just uses the ST Monad which is quite similar to weakly pure
>> statements in D.
>
> D doesn't have weakly pure statements - it has weakly pure functions.

The type checker distinguishes between statements that are allowed in 'pure'-qualified functions and statements that are not.

On Monday, 21 July 2014 at 22:10:06 UTC, bearophile wrote:
> Tobias Müller:
>
>> Wouldn't it be more useful to have a modified/annotated return statement for that?
>
> I don't know.

I see what you're saying, and it works for the quick sort example. I'm not sure it covers all tailrec cases, but it seems useful.

On 7/21/14, 3:22 PM, Timon Gehr wrote:
> On 07/21/2014 06:40 AM, Andrei Alexandrescu wrote:
>> On 7/20/14, 8:15 PM, Timon Gehr wrote:
>>> On 07/20/2014 10:50 PM, Walter Bright wrote:
>>>> On 7/20/2014 3:27 AM, Dmitry Olshansky wrote:
>>>>> Functional programming is full of simple recursion and it would be
>>>>> nice not to
>>>>> stack overflow in debug builds.
>>>>
>>>> Traditional FP languages don't have loops, and so must do recursion.
>>>
>>> Uh...
>>>
>>>> D has loops, even in pure functions,
>>>
>>> So does Haskell.
>>>
>>> import Control.Monad
>>> import Control.Monad.ST
>>> import Data.STRef
>>>
>>> factorial :: Integer -> Integer
>>> factorial n = runST $ do
>>>    r <- newSTRef 1
>>>    forM_ [1..n] $ \i->
>>>      modifySTRef r (*i)
>>>    readSTRef r
>>>
>>> main = print $ factorial 5 -- "120"
>>
>> And that doesn't look awkward at all :o). -- Andrei
>>
>>
>
> Indeed.

Code sucks. It's its own destruction. -- Andrei

>>> My understanding is that it can be done
>>> but only with annotations or whole program analysis.

I think that's true but you don't necessarily have to annotate every function.

a) possibly there's something interesting to do at the module level. I think more than one thing. E.g. A module that doesn't have any callbacks in its interface is 'interesting'. E.g. 'Layering' of modules.

b) Some situations are particularly dangerous and so a function annotation could be encouraged for those. E.g. If you have a recursive function without tail recursion, and the possible recursion depth is substantial, then while it is deep in its recursion, it should limit what other functions it calls. Someone could come along later and add a logging statement to it, which usually isn't dangerous but here it could be.


Quick sort is an instructive example because it has the security weakness that, although you expect the stack depth to typically be O(log n), an attacker in control of the input can force it to be O(n). Of course with tail recursion that doesn't threaten stack overflow, but it suggests that there are recursion cases we think are safe, and typically don't fall over, but are actually vulnerable. Which means if we don't feel like annotating them in defense, we're being irresponsible in a way.

On 07/22/2014 05:49 PM, Andrei Alexandrescu wrote:
> On 7/21/14, 3:22 PM, Timon Gehr wrote:
>> On 07/21/2014 06:40 AM, Andrei Alexandrescu wrote:
>>> On 7/20/14, 8:15 PM, Timon Gehr wrote:
>>>> On 07/20/2014 10:50 PM, Walter Bright wrote:
>>>>> ...
>>>>> D has loops, even in pure functions,
>>>>
>>>> So does Haskell.
>>>>
>>>> import Control.Monad
>>>> import Control.Monad.ST
>>>> import Data.STRef
>>>>
>>>> factorial :: Integer -> Integer
>>>> factorial n = runST $ do
>>>>    r <- newSTRef 1
>>>>    forM_ [1..n] $ \i->
>>>>      modifySTRef r (*i)
>>>>    readSTRef r
>>>>
>>>> main = print $ factorial 5 -- "120"
>>>
>>> And that doesn't look awkward at all :o). -- Andrei
>>>
>>
>> Indeed.
>
> Code sucks. It's its own destruction. -- Andrei
>

It is easy to understand and works correctly, but of course this is not a canonical implementation of factorial.

Timon Gehr:

> It is easy to understand and

It's easy to understand because you are very intelligent Timon :-)

Bye,
bearophile

On 7/20/2014 8:15 PM, Timon Gehr wrote:
> So does Haskell.
>
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef
>
> factorial :: Integer -> Integer
> factorial n = runST $ do
>    r <- newSTRef 1
>    forM_ [1..n] $ \i->
>      modifySTRef r (*i)
>    readSTRef r

Would you rather write that or:

  int factorial(int i) pure {
    auto r = 1;
    foreach (i; 1..n + 1)
	r *= i;
    return r;
  }

And I'd love to see what native code is generated for the Haskell example.

Walter Bright:

> Would you rather write that or:

How much experience do you have in writing Haskell programs longer than 50 lines of code? I have a large respect for your experience and your intelligence, but be careful with comments like that, to not show just your ignorance...

If you are a Haskell programmer you usually don't write code like that, so in practice it's not a problem. And even if sometimes you have to write awkward code, the Haskell programmers can assure you that on average the advantages given by Haskell purity far outweighs the disadvantages.

On overall I prefer D over Haskell, but if you want to criticize Haskell you need much much better arguments and way bigger cannons :-)

Bye,
bearophile

On Tue, Jul 22, 2014 at 11:34:20AM -0700, Walter Bright via Digitalmars-d wrote:
> On 7/20/2014 8:15 PM, Timon Gehr wrote:
> >So does Haskell.
> >
> >import Control.Monad
> >import Control.Monad.ST
> >import Data.STRef
> >
> >factorial :: Integer -> Integer
> >factorial n = runST $ do
> >   r <- newSTRef 1
> >   forM_ [1..n] $ \i->
> >     modifySTRef r (*i)
> >   readSTRef r
> 
> Would you rather write that or:
> 
>   int factorial(int i) pure {
>     auto r = 1;
>     foreach (i; 1..n + 1)
> 	r *= i;
>     return r;
>   }
> 
> And I'd love to see what native code is generated for the Haskell example.

I'd rather write:

	int factorial(int n) pure {
		return reduce!((a,b) => a*b)(1, iota(2, n));
	}

;-)

With gdc -O3, this produces almost the same code as your looped version. But I can barely read the disassembly, because it appears that gdc -O3 triggers aggressive vectorization, so there are tons of instructions manipulating xmm registers and the loop is unrolled by 8 iterations.

I have this lurking suspicion that this may actually perform more poorly than the naïve version for small values of n. :-) DMD, with -release -O -inline, was unable to inline the call to reduce, but was at least able to optimize reduce+iota into the equivalent of a simple foreach loop. So it looks quite promising.

We should push for more aggressive optimizations of functional-style constructs in D; I think there's a lot of potential here.


T

-- 
My program has no bugs! Only unintentional features...