Slides from LASER 2012

[Timon Gehr]

On 09/20/2012 04:23 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> In particular, Martin has been quite impressed with our approach to
>> purity and immutability. We are considering a collaboration with one
>> of his students on a paper to formalize the approach and possibly
>> adapt it to Scala.
>
> Formalizing D purity is probably possible, but it already has many
> special cases, and few more are coming (see Bugzilla on this)!
>

Formalising it is not hard, but the D implementation will have to be
fixed. Just decouple 'immutable' and 'pure' completely,

int foo()pure{
     int x;
     immutable int y;
     void bar()pure{
         x++; // ok
     }
     int baz()pure immutable{
         return y; // ok
     }
     int foo()pure immutable{
         return x; // error
     }
}

then rename pure to somethingother and make pure a synonym for
somethingother immutable and add that to Scala.


> Regarding cross pollination with Scala: despite I generally don't like
> lazy lists in high-performance code, in many other kinds of code they
> are very handy, as in Haskell, Perl6 and Scala (in Scala they are named
> purely functional lazy streams).
>
> If you take a look at Python/Scala/C# code that generates values lazily,
> the Range-based version in D is sometimes several times longer, much
> more easy to get wrong, harder to write, etc.
>
> This is Haskell code to test if just the leaves of two binary trees
> contain the same data, this code is lazy:
>
> data Tree a = Leaf a | Node (Tree a) (Tree a)
>
> fringe :: Tree a -> [a]
> fringe (Leaf x) = [x]
> fringe (Node n1 n2) = fringe n1 ++ fringe n2
>
> sameFringe :: (Eq a) => Tree a -> Tree a -> Bool
> sameFringe t1 t2 = fringe t1 == fringe t2
>
>
> Doing the same thing in D, using ranges, is possible, but the code is
> ten times longer or more:
> http://rosettacode.org/wiki/Same_Fringe#Strong_Lazy_Version
>

The translation is (spaces added for your convenience, you won't get me
to use parens though):

mixin ADT!q{ Tree(T): Leaf(T x), Node(Tree a, Tree b) };

DynRange!T fringe(T)(Tree!T t){
     return t.match!(
         (Leaf l) => cons(l.x, empty),
         (Node n) => chain(n.a.fringe, n.b.fringe).dynRange,
     );
}

bool sameFringe(T)(Tree!T t1, Tree!T t2){
     return equal(t1.fringe, t2.fringe);
}

for suitable definitions of ADT, DynRange/dynRange, cons and empty.  So
those would be nice additions to Phobos. Obviously this would look even
better:

mixin ADT!q{ Tree(T): Leaf(T x), Node(Tree a, Tree b) };

DynRange!T fringe(T)(Tree!T t) => t.match!(
     (Leaf l) => cons(l.x, empty),
     (Node n) => chain(n.a.fringe, n.b.fringe).dynRange,
);

bool sameFringe(T)(Tree!T t1, Tree!T t2) => t1.fringe == t2.fringe;

The number of lines equals the Haskell example in this case.
Interestingly, you have opened an enhancement request on this and then
argued against it.


> Similar code is possible in Scala (and in this case most of the saving
> of lines of code doesn't come from pattern matching and algebraic data
> types, but from the good support for lazy lists/streams). This kind of
> code is very common, even when you aren't coding in functional style.
>
> --------------------
>
>> So, these are the slides I've used (though of course they don't tell
>> much of the story).
>>
>> http://laser.inf.ethz.ch/2012/slides/Alexandrescu/2-D%20course%20parts%201%20and%202.pdf
>>
>
> Thank you for the slides.
> I hope we'll have the range-based min(), and argmin/argmax in Phobos :-)
>
> --------------------
>
> At page 33:
>
> auto m = s.argmin!((x) => x.length);
>
> This isn't compiled with -property. So what's the right way to write D
> code?
>

There is no 'right' way. But this is the pretty way, the way you use to
show off the language at a presentation (otherwise you'll get questions
like: "that is all well, but what on earth is that second pair of
parens for?")

> In Python to avoid that lambda there is a len() global function, that
> just calls the __len__ attribute/property of collections and objects. So
> an equivalent Python version is:
>
> auto m = s.argmin!len;
>
> Bye,
> bearophile