stl?

stl?

[Raoul Duke]

hi,

the caml archives show discussion around C++ polymorphism wrt STL
(since Stepanov iirc said that C++ was the only language which
supported what he needed to let him implement his generic programming)
but i didn't yet see anywhere a concrete implementation or mapping
from C++ STL to O'Caml.

i'm just trying to get my head around what it might look like, and
if/how it might be useful. (it just bugs me that somebody can claim
that C++ is the /only/ language that could do it -- maybe the real
quote implied "mainstream" or something. apparently Ada wasn't up to
snuff http://www.sgi.com/tech/stl/drdobbs-interview.html)

sincerely.

Re: [Caml-list] stl?

[Yoann Padioleau]

Raoul Duke <raould@gmail.com> writes:

> hi,
>
> the caml archives show discussion around C++ polymorphism wrt STL
> (since Stepanov iirc said that C++ was the only language which
> supported what he needed to let him implement his generic programming)
> but i didn't yet see anywhere a concrete implementation or mapping
> from C++ STL to O'Caml.
>
> i'm just trying to get my head around what it might look like, and
> if/how it might be useful. (it just bugs me that somebody can claim
> that C++ is the /only/ language that could do it -- maybe the real
> quote implied "mainstream" or something. apparently Ada wasn't up to
> snuff http://www.sgi.com/tech/stl/drdobbs-interview.html)

I don't know what are the Stepanov requirements, but C++ 
can do unboxed collections like  list<int>, which OCaml can
not provide I think. a 'int list' has boxed integers in OCaml. 

Also, a maybe good thing with STL is that you can write a single 'find'
or 'sort' function that will work for every kind of collections 
(list, arrays, map, hash, etc) by using the
indirect iterator idiom, without the penalty of dynamic dispatch
solutions. I am not sure OCaml can do that too.

The question is do we really need those 2 things ? 
I've worked a little bit with C++ using unboxed objects, that
is without introducing pointers (similar to boxing) in templates, 
like list<figure> instead of list<figure*>, and passing them
as value in parameters, or returning them, 
and it was far less efficient because there was lots of copy,
and you could not use then virtual method on them. So in the
end the C++ programmer I thing manually re-introduce boxing
when using STL if he wants good performance, and he can not really
rely either on the default copy/equal implementation provided
by those templates. So, yes STL makes it possible to do things,
but programmers don't want them, or only in very few cases where
one need extreme performance. 




>
> sincerely.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] stl?

[Till Varoquaux]

ocaml's integers are never 'boxed'.... but you are right values
contained in blocks don't generally get inlined (there's a known
caveat for float who end up with the dual representation (aka
boxed/unboxed)).

Till

On Tue, Mar 3, 2009 at 5:31 PM, Yoann Padioleau <padator@wanadoo.fr> wrote:
> Raoul Duke <raould@gmail.com> writes:
>
>> hi,
>>
>> the caml archives show discussion around C++ polymorphism wrt STL
>> (since Stepanov iirc said that C++ was the only language which
>> supported what he needed to let him implement his generic programming)
>> but i didn't yet see anywhere a concrete implementation or mapping
>> from C++ STL to O'Caml.
>>
>> i'm just trying to get my head around what it might look like, and
>> if/how it might be useful. (it just bugs me that somebody can claim
>> that C++ is the /only/ language that could do it -- maybe the real
>> quote implied "mainstream" or something. apparently Ada wasn't up to
>> snuff http://www.sgi.com/tech/stl/drdobbs-interview.html)
>
> I don't know what are the Stepanov requirements, but C++
> can do unboxed collections like  list<int>, which OCaml can
> not provide I think. a 'int list' has boxed integers in OCaml.
>
> Also, a maybe good thing with STL is that you can write a single 'find'
> or 'sort' function that will work for every kind of collections
> (list, arrays, map, hash, etc) by using the
> indirect iterator idiom, without the penalty of dynamic dispatch
> solutions. I am not sure OCaml can do that too.
>
> The question is do we really need those 2 things ?
> I've worked a little bit with C++ using unboxed objects, that
> is without introducing pointers (similar to boxing) in templates,
> like list<figure> instead of list<figure*>, and passing them
> as value in parameters, or returning them,
> and it was far less efficient because there was lots of copy,
> and you could not use then virtual method on them. So in the
> end the C++ programmer I thing manually re-introduce boxing
> when using STL if he wants good performance, and he can not really
> rely either on the default copy/equal implementation provided
> by those templates. So, yes STL makes it possible to do things,
> but programmers don't want them, or only in very few cases where
> one need extreme performance.
>
>
>
>
>>
>> sincerely.
>>
>> _______________________________________________
>> Caml-list mailing list. Subscription management:
>> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>> Archives: http://caml.inria.fr
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] stl?

[Jon Harrop]

On Tuesday 03 March 2009 22:31:55 Yoann Padioleau wrote:
> I don't know what are the Stepanov requirements, but C++
> can do unboxed collections like  list<int>, which OCaml can
> not provide I think. a 'int list' has boxed integers in OCaml.

The currently OCaml implementation never boxes ints and the boxing of other 
types (like float) is an artefact of the current implementation not found in 
other language implementations like F# and my HLVM. Moreover, this is not 
even a visible difference.

> Also, a maybe good thing with STL is that you can write a single 'find'
> or 'sort' function that will work for every kind of collections
> (list, arrays, map, hash, etc) by using the
> indirect iterator idiom, without the penalty of dynamic dispatch
> solutions. I am not sure OCaml can do that too.

OCaml can do that too. Just wrap your code in a functor and parameterize it 
over the module implementing the data structure (e.g. List or Array). Modules 
and functors are second-class statically resolved constructs in OCaml so 
there is no dynamic dispatch.

> The question is do we really need those 2 things?

Parameterizing code using functors is extremely useful but it goes far beyond 
the usable capabilities of C++.

> I've worked a little bit with C++ using unboxed objects, that
> is without introducing pointers (similar to boxing) in templates,
> like list<figure> instead of list<figure*>, and passing them
> as value in parameters, or returning them,
> and it was far less efficient because there was lots of copy,
> and you could not use then virtual method on them. So in the
> end the C++ programmer I thing manually re-introduce boxing
> when using STL if he wants good performance, and he can not really
> rely either on the default copy/equal implementation provided
> by those templates. So, yes STL makes it possible to do things,
> but programmers don't want them, or only in very few cases where
> one need extreme performance.

The STL is extremely slow. If you want fast code in C++ then you drop to the C 
subset. Alex Stepanov tried and failed to implement efficient constructs in 
the STL. Furthermore, the memory consumption of his library is awful. OCaml's 
GC is far more efficient with memory whilst permitting easy sharing.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Tuesday 03 March 2009 21:40:11 Raoul Duke wrote:
> hi,
>
> the caml archives show discussion around C++ polymorphism wrt STL
> (since Stepanov iirc said that C++ was the only language which
> supported what he needed to let him implement his generic programming)
> but i didn't yet see anywhere a concrete implementation or mapping
> from C++ STL to O'Caml.
>
> i'm just trying to get my head around what it might look like, and
> if/how it might be useful. (it just bugs me that somebody can claim
> that C++ is the /only/ language that could do it -- maybe the real
> quote implied "mainstream" or something. apparently Ada wasn't up to
> snuff http://www.sgi.com/tech/stl/drdobbs-interview.html)

I spent many years programming in C++ before I learned OCaml and my first 
reaction was to try to use classes for everything and to try to reinvent the 
STL in OCaml. However, the result cannot be useful because the STL simply 
represents a poor choice of trade-offs.

For example, higher-order functions like fold and map are extremely useful, 
particularly when their function argument is a closure, but that is too 
tedious to be useful in the STL whereas the ability to reuse a single "find" 
function over many different data structures is easy in the STL but useless 
in practice because you almost always know what data structure to use before 
you write the code (so you hard code List.find) and, if you don't, you just 
rename a module and use that instead (module Bindings = List ... 
Bindings.find) so there is only one code location to update. Functors give 
you the same capability in OCaml but they are rarely used precisely because 
the functionality is not very useful.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Brian Hurt]

On Tue, 3 Mar 2009, Jon Harrop wrote:

> Functors give
> you the same capability in OCaml but they are rarely used precisely because
> the functionality is not very useful.

I think I disagree with this.  I think functors aren't used very much in 
Ocaml because:
1) They're a big, scary name, and
2) They're slightly less efficient.

The biggest difference between Haskell and Ocaml that I see is simply the 
difference between attitudes of the two communities.  The Ocaml community 
is like "Don't use functors- they disable inlining and cost you six whole 
clock cycles on a function call!  They're evil, I tell you!"  Meanwhile, 
the Haskell community is like "I used typeclasses all over my application, 
and the performance didn't completely suck- woot!  Type classes rule!" 
This is a broad generalization, and not completely accurate- but on the 
whole, the ocaml community is much more focused on (clock cycle) 
efficiency, while the Haskell community is much more focused on 
abstraction and programmer-cycle efficiency.

The type classes comparison isn't even an analogy- it's a precise 
relationship.  Anywhere you might be thinking, in Ocaml, "this would be a 
nice place to use a type class", use a functor.  You want operator 
overloading in Ocaml?  You got it: use a functor.  If this causes you a 
knee jerk reaction about performance, ask yourself this: do you know how 
type classes are implemented in Haskell, and what their performance hit 
there is?  Now, imagine programming haskell where typeclasses are only 
used in a very places- Ord, Eq, Monad.  No Num.  No Monoid.  No Show. 
That's Ocaml.  Not that it has to be.

Having actually used Haskell for a while, I think I actually like functors 
better than type classes.  But that's a rant for a different venue.  The 
big difference is that Haskell programmers use type classes, and the Ocaml 
programmers don't use Functors (very often, if at all).

Brian

Re: [Caml-list] stl?

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Tuesday 03 March 2009 06:36:52 pm Jon Harrop wrote:
> On Tuesday 03 March 2009 22:31:55 Yoann Padioleau wrote:
> > Also, a maybe good thing with STL is that you can write a single 'find'
> > or 'sort' function that will work for every kind of collections
> > (list, arrays, map, hash, etc) by using the
> > indirect iterator idiom, without the penalty of dynamic dispatch
> > solutions. I am not sure OCaml can do that too.
>
> OCaml can do that too. Just wrap your code in a functor and parameterize it
> over the module implementing the data structure (e.g. List or Array).
> Modules and functors are second-class statically resolved constructs in
> OCaml so there is no dynamic dispatch.

As usual I want to point out the alternative: objects.  Eg. you can write a 
function that takes any object with the "find" method and look for 
<whatever>.  Objects in contrast to functors are dynamically dispatched so 
they are more flexible but just a little slower (method calls are cached).  
It also lets you make calls to find without being explict.  Eg. instead of 
List.find or Array.find or Set.Make(String).find, you can just do #find.

Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFJrcfEfIRcEFL/JewRAsEzAKCfu/LbvuvPVDCCsOI8Kmi8cfHtTwCfZfEX
ffjw1sTrYzJHbr0d8QQuaQw=
=yXcr
-----END PGP SIGNATURE-----

Re: [Caml-list] stl?

[Yoann Padioleau]

Jon Harrop <jon@ffconsultancy.com> writes:

> On Tuesday 03 March 2009 22:31:55 Yoann Padioleau wrote:
>> I don't know what are the Stepanov requirements, but C++
>> can do unboxed collections like  list<int>, which OCaml can
>> not provide I think. a 'int list' has boxed integers in OCaml.
>
> The currently OCaml implementation never boxes ints and the boxing of other 
> types (like float) is an artefact of the current implementation not found in 
> other language implementations like F# and my HLVM. Moreover, this is not 
> even a visible difference.

Oh, Ok. Is it true for other types such as list of records, 
list of variants, list of pairs, etc ? 

>
>> Also, a maybe good thing with STL is that you can write a single 'find'
>> or 'sort' function that will work for every kind of collections
>> (list, arrays, map, hash, etc) by using the
>> indirect iterator idiom, without the penalty of dynamic dispatch
>> solutions. I am not sure OCaml can do that too.
>
> OCaml can do that too. Just wrap your code in a functor and parameterize it 

The interesting word in your sentence is "just". The big problem with
functors is that it's never a "just". Functors are too intrusive. If
you have somewhere a function that needs to use this 'find', then you
will be forced to functorize the whole caller chain, including other
modules. That's really really really intrusive. It's exactly why
monads in haskell are mostly a bad idea. They are too intrusive. If in
haskell you have a deep nested function that needs to do some IO, then
you need to "monadize" the whole call chain which is just painful.

Imagine if the 'list' type would be in a functor and instead of 
'a list you would have a List: functor(T). Each time you have
a function using a list you would need to put it inside a functor...
In fact this happens for OCaml data-types such as Set or Map which
is why most people have defined their own defunctorized Set or Map
that just use Pervasive.(=).

That does not mean Functors or monads are completely a bad idea, they
have their use (I used them sometimes), but they have lots 
of drawbacks.

> over the module implementing the data structure (e.g. List or Array). Modules 
> and functors are second-class statically resolved constructs in OCaml so 
> there is no dynamic dispatch.
>
>> The question is do we really need those 2 things?
>
> Parameterizing code using functors is extremely useful but it goes far beyond 
> the usable capabilities of C++.

I think the next C++ has a 'concept' mechanism quite similar to
haskell typeclasse. But as usual with C++, it's wrapped in a ugly syntax 
way, will have awful error messages, and that will probably
makes it impossible in practice to be used by mere mortals.

>> I've worked a little bit with C++ using unboxed objects, that
>> is without introducing pointers (similar to boxing) in templates,
>> like list<figure> instead of list<figure*>, and passing them
>> as value in parameters, or returning them,
>> and it was far less efficient because there was lots of copy,
>> and you could not use then virtual method on them. So in the
>> end the C++ programmer I thing manually re-introduce boxing
>> when using STL if he wants good performance, and he can not really
>> rely either on the default copy/equal implementation provided
>> by those templates. So, yes STL makes it possible to do things,
>> but programmers don't want them, or only in very few cases where
>> one need extreme performance.
>
> The STL is extremely slow. If you want fast code in C++ then you drop to the C 
> subset. Alex Stepanov tried and failed to implement efficient constructs in 
> the STL. Furthermore, the memory consumption of his library is awful. OCaml's 
> GC is far more efficient with memory whilst permitting easy sharing.

I agree. Java is also better than C++ in that respect because
it also leverages sharing.

>
> -- 
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] stl?

[Yoann Padioleau]

Brian Hurt <bhurt@spnz.org> writes:

> On Tue, 3 Mar 2009, Jon Harrop wrote:
>
>> Functors give
>> you the same capability in OCaml but they are rarely used precisely because
>> the functionality is not very useful.
>
> I think I disagree with this.  I think functors aren't used very much
> in Ocaml because:

  0) they are intrusive! putting code inside a functor may entail the
need to modify also lots of related code. That's one of the worst
thing for a programming feature. Your modification can not be local. I
hate monad for the same reason, and I like ocaml exception mechanism,
and using sometimes global refs for the same reason.

> 1) They're a big, scary name, and

I'am a man, I am not scared.

> 2) They're slightly less efficient.

I don't care so much about that anyway. 

>

Re: [Caml-list] stl?

[Raoul Duke]

> modules. That's really really really intrusive. It's exactly why
> monads in haskell are mostly a bad idea. They are too intrusive. If in

what are the current best language/research/advanced/alternative
solutions for this issue?

thanks.

Re: [Caml-list] stl?

[Pal-Kristian Engstad]

Raoul Duke wrote:
>> modules. That's really really really intrusive. It's exactly why
>> monads in haskell are mostly a bad idea. They are too intrusive. If in
>>     
>
> what are the current best language/research/advanced/alternative
> solutions for this issue?
>
>   
DDC: http://www.haskell.org/haskellwiki/DDC

PKE

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.

Re: [Caml-list] stl?

[Yoann Padioleau]

Raoul Duke <raould@gmail.com> writes:

>> modules. That's really really really intrusive. It's exactly why
>> monads in haskell are mostly a bad idea. They are too intrusive. If in
>
> what are the current best language/research/advanced/alternative
> solutions for this issue?

I would say type-classes or objects. Less intrusive.

>
> thanks.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 00:58:59 Yoann Padioleau wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
> > On Tuesday 03 March 2009 22:31:55 Yoann Padioleau wrote:
> >> I don't know what are the Stepanov requirements, but C++
> >> can do unboxed collections like  list<int>, which OCaml can
> >> not provide I think. a 'int list' has boxed integers in OCaml.
> >
> > The currently OCaml implementation never boxes ints and the boxing of
> > other types (like float) is an artefact of the current implementation not
> > found in other language implementations like F# and my HLVM. Moreover,
> > this is not even a visible difference.
>
> Oh, Ok. Is it true for other types such as list of records,
> list of variants, list of pairs, etc ?

In the current OCaml implementation, yes, but not in F# and my HLVM where all 
such types are stored unboxed. That not only removes indirections but it also 
drastically reduces the number of allocated blocks that the GC has to work 
with and, therefore, places a lot less stress on the GC.

> > OCaml can do that too. Just wrap your code in a functor and parameterize
> > it
>
> The interesting word in your sentence is "just". The big problem with
> functors is that it's never a "just". Functors are too intrusive. If
> you have somewhere a function that needs to use this 'find', then you
> will be forced to functorize the whole caller chain, including other
> modules. That's really really really intrusive. It's exactly why
> monads in haskell are mostly a bad idea. They are too intrusive.

Yes. People often call that "creep" and I agree that it can be a PITA during 
development when you do not have a clear idea of what should and should not 
go into the functor.

> Imagine if the 'list' type would be in a functor and instead of
> 'a list you would have a List: functor(T). Each time you have
> a function using a list you would need to put it inside a functor...
> In fact this happens for OCaml data-types such as Set or Map which
> is why most people have defined their own defunctorized Set or Map
> that just use Pervasive.(=).

That is a really bad workaround for a flaw in the language which, again, is 
fixed in both F# and HLVM through the introduction of per-type functions for 
printing, equality, comparison, serialization and so on.

> That does not mean Functors or monads are completely a bad idea, they
> have their use (I used them sometimes), but they have lots
> of drawbacks.

Trade-offs. Type inference is the flip side of that coin. Overloading 
like "find" in C++ destroys type inference and that makes for really horrific 
code. You see that a lot when using F# with the .NET libraries.

OCaml is a thing of beauty here. Polymorphic variants make it even nicer and, 
of course, that is another feature than Haskell does not have...

> > The STL is extremely slow. If you want fast code in C++ then you drop to
> > the C subset. Alex Stepanov tried and failed to implement efficient
> > constructs in the STL. Furthermore, the memory consumption of his library
> > is awful. OCaml's GC is far more efficient with memory whilst permitting
> > easy sharing.
>
> I agree. Java is also better than C++ in that respect because
> it also leverages sharing.

Yes.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 00:11:32 you wrote:
> On Tue, 3 Mar 2009, Jon Harrop wrote:
> > Functors give you the same capability in OCaml but they are rarely used
> > precisely because the functionality is not very useful.

Also largely because there is not enough good tutorial information available 
explaining how to leverage functors.

> I think I disagree with this.  I think functors aren't used very much in
> Ocaml because:
> 1) They're a big, scary name, and
> 2) They're slightly less efficient.
>
> The biggest difference between Haskell and Ocaml that I see is simply the
> difference between attitudes of the two communities.  The Ocaml community
> is like "Don't use functors- they disable inlining and cost you six whole
> clock cycles on a function call!  They're evil, I tell you!"

Efficiency is only important in the context of functors when abstracting very 
fast and common functions like arithmetic without defunctorizing your code. I 
don't think that is why people avoid functors in OCaml.

> Meanwhile,  
> the Haskell community is like "I used typeclasses all over my application,
> and the performance didn't completely suck- woot!  Type classes rule!"
> This is a broad generalization, and not completely accurate- but on the
> whole, the ocaml community is much more focused on (clock cycle)
> efficiency, while the Haskell community is much more focused on
> abstraction and programmer-cycle efficiency. 

I think that is a reflection of what the communities desire rather than what 
they already have. OCaml is already fast (particularly on amd64) but OCamlers 
always want even better performance. Haskell's development experience is a 
real sore point and they want to address that. However, I would also say that 
both communities are moving very slowly toward these goals.

> The type classes comparison isn't even an analogy- it's a precise
> relationship. Anywhere you might be thinking, in Ocaml, "this would be a 
> nice place to use a type class", use a functor.  You want operator
> overloading in Ocaml?  You got it: use a functor.

Functors do not facilitate operator overloading. You still end up with a 
combinatorial explosion in the number of operator names.

> If this causes you a 
> knee jerk reaction about performance, ask yourself this: do you know how
> type classes are implemented in Haskell, and what their performance hit
> there is?  Now, imagine programming haskell where typeclasses are only
> used in a very places- Ord, Eq, Monad.  No Num.  No Monoid.  No Show.
> That's Ocaml.  Not that it has to be.

I don't follow your breakdown. OCaml does not have Ord and Eq, it only has a 
hack for structural equality. Same for Show. Few people care about Monad, Num 
and Monoid.

However, that is trivial to fix with run-time type information that can convey 
per-type functions. Both F# and my HLVM already do that.

> Having actually used Haskell for a while, I think I actually like functors
> better than type classes.  But that's a rant for a different venue.  The
> big difference is that Haskell programmers use type classes, and the Ocaml
> programmers don't use Functors (very often, if at all).

There are some very good examples of functors out there, like ocamlgraph.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Martin Jambon]

Brian Hurt wrote:
> 
> 
> On Tue, 3 Mar 2009, Jon Harrop wrote:
> 
>> Functors give
>> you the same capability in OCaml but they are rarely used precisely
>> because
>> the functionality is not very useful.
> 
> I think I disagree with this.  I think functors aren't used very much in
> Ocaml because:
> 1) They're a big, scary name, and
> 2) They're slightly less efficient.

Functors are not used very much because they are not needed very often. OCaml
is a free market.

All sorts of reusable algorithms on arbitrary data can be nicely implemented
using functors, without more difficulty than the specialized versions of the
same algorithm. But do you often implement cool algorithms that work on
arbitrary types? Not me. Certainly less than 5% of the time. Most of the time
we have to deal with the brutality of the real world, which is all bytes and
strings.


Martin

-- 
http://mjambon.com/

Re: [Caml-list] stl?

[Brian Hurt]

On Tue, 3 Mar 2009, Yoann Padioleau wrote:

> Brian Hurt <bhurt@spnz.org> writes:
>
>> On Tue, 3 Mar 2009, Jon Harrop wrote:
>>
>>> Functors give
>>> you the same capability in OCaml but they are rarely used precisely because
>>> the functionality is not very useful.
>>
>> I think I disagree with this.  I think functors aren't used very much
>> in Ocaml because:
>
>  0) they are intrusive! putting code inside a functor may entail the
> need to modify also lots of related code. That's one of the worst
> thing for a programming feature. Your modification can not be local. I
> hate monad for the same reason, and I like ocaml exception mechanism,
> and using sometimes global refs for the same reason.

No.

Here's what you can do.  Say you had an old function:
 	let foo x = ...
and you want to functorize it for whatever reason.  But you have lots of 
code depending upon the old type signature that you don't want to change. 
First, you functorize foo:

 	module Make(X: Whatever) = struct let foo x = ... end;;

Then you include the "classic foo", like:

 	module T = Make(struct ... old defns ... end);;
 	include T;;

Where ... old defns ... is all the original types and functions that foo 
used that are now provided by the functor.  So you now have a module that 
exports both a "functorized" foo and a "classic" foo, and all the old code 
continues to just work (after a recompile, natch).

This is much the same trick you use in Haskell when adding a typeclass 
dependency to the signature of a function- so long as you provide a 
typeclass instance for the old type, the old code continues to work with a 
recompile.

I also comment, this is also a problem C++ templates have- templatizing a 
class in C++ is also an "intrusive" change.

Brian

Re: [Caml-list] stl?

[Brian Hurt]

On Wed, 4 Mar 2009, Jon Harrop wrote:

> On Wednesday 04 March 2009 00:11:32 you wrote:
>> On Tue, 3 Mar 2009, Jon Harrop wrote:
>>> Functors give you the same capability in OCaml but they are rarely used
>>> precisely because the functionality is not very useful.
>
> Also largely because there is not enough good tutorial information available
> explaining how to leverage functors.

This is another large factor.  The three reasons functors aren't used very 
much are because:
1) They're a big, scary name,
2) They're slightly less efficient,
3) There are no good tutorials about how to use them, and
4) A fanatical devotion to the pope.

I'll come in again...

> Efficiency is only important in the context of functors when abstracting very
> fast and common functions like arithmetic without defunctorizing your code. I
> don't think that is why people avoid functors in OCaml.

Arithmetic operators that are themselves very cheap.  The cost of 
functorization is large compared to, say, floating point addition- but 
small compared to the cost of, say, vector addition.  And it's expensive 
only because Ocaml lacks an obvious optimization (defunctorization).  And 
yet this whole discussion is simply proving my point- we're comparing 
clock cycles here.  Yes, if you're writing the inner loops of a numeric 
computation that'll take days to run, maybe, *MAYBE*, the cost difference 
of calling via a functor is worthwhile to worry about.  But that's the 
point where I start being really tempted to drop down to C, or even 
assembly (for SSE Vectorization).  But for the vast bulk of people 
programming, performance (at least on the clock cycle level) simply isn't 
that important- as demonstrated by all the "real work" being done in 
hideously slow languages like Ruby, Python, etc...

> I think that is a reflection of what the communities desire rather than what
> they already have. OCaml is already fast (particularly on amd64) but OCamlers
> always want even better performance. Haskell's development experience is a
> real sore point and they want to address that. However, I would also say that
> both communities are moving very slowly toward these goals.

Both languages have their annoyances.  Adjusting for the fact that I'm 
significantly more familiar with and comfortable with Ocaml, I don't find 
Haskell that much more difficult to work in.

>
>> The type classes comparison isn't even an analogy- it's a precise
>> relationship. Anywhere you might be thinking, in Ocaml, "this would be a
>> nice place to use a type class", use a functor.  You want operator
>> overloading in Ocaml?  You got it: use a functor.
>
> Functors do not facilitate operator overloading. You still end up with a
> combinatorial explosion in the number of operator names.

Bwuh?

Try this.  Let's reimplement Haskell's Fractional class, in Ocaml, and 
then do Newton's method using this new Fractional class.  Then I'll 
provide implementations that use both floats and ratios (arbitrary 
precision fractions).  First, we need to define Fractional.  That's just:

module type Fractional = sig
 	type t
 	val ( +. ) : t -> t -> t
 	val ( -. ) : t -> t -> t
 	val ( *. ) : t -> t -> t
 	val ( /. ) : t -> t -> t
 	val fabs : t -> t
 	(* other functions elided from brevity *)
end;;

Now we write our functorized Newton's method:

module Make(F: Fractional) = struct

 	open F;;

 	let rec newtons epsilon f df x =
 		let x' = x -. ((f x) /. (df x)) in
 		if (fabs (x -. x')) < epsilon then
 			x'
 		else
 			newtons epsilon f df x'
 	;;

end;;

Now we provide an instance of Fractional for floats:

module FloatFractional = struct
 	type t = float
 	let ( +. ) = ( +. );;
 	let ( -. ) = ( -. );;
 	let ( *. ) = ( *. );;
 	let ( /. ) = ( /. );;
 	let fabs x = abs_float x;;
end;;

module FloatNewtons = Make(FloatFractional);;

Now we provide an instance for Ratios:

module RatioFractional = struct
 	type t = Ratio.ratio;;
 	let ( +. ) = Ratio.add_ratio;;
 	let ( -. ) = Ratio.sub_ratio;;
 	let ( *. ) = Ratio.mult_ratio;;
 	let ( /. ) = Ratio.div_ratio;;
 	let fabs = Ratio.abs_ratio;;
end;;

module RatioNewtons = Make(RatioFractional);;

Viola.  Operator overloading.  In Ocaml.  And it's not that much worse 
than Haskell equivalent, once you realize that the definitions of 
Fractional, FloatFractional, and RatioFractional all should be in the 
standard library (and the latter two should be just called Float and 
Ratio).

And typeclasses have their problems as well- which are off topic for this 
list.

>
>> If this causes you a
>> knee jerk reaction about performance, ask yourself this: do you know how
>> type classes are implemented in Haskell, and what their performance hit
>> there is?  Now, imagine programming haskell where typeclasses are only
>> used in a very places- Ord, Eq, Monad.  No Num.  No Monoid.  No Show.
>> That's Ocaml.  Not that it has to be.
>
> I don't follow your breakdown. OCaml does not have Ord and Eq, it only has a
> hack for structural equality. Same for Show. Few people care about Monad, Num
> and Monoid.

The turn you missed was that I'm say "what if Haskell programmers used 
type classes as rarely as Ocaml programmers use functors?"  Typeclasses 
are a huge win in Haskell, but primarily because they get *used*.

>
> However, that is trivial to fix with run-time type information that can convey
> per-type functions. Both F# and my HLVM already do that.

I suppose we could sit around and whine that Ocaml doesn't have type 
classes, or reflection, or some other neat feature, that if it only had 
it, we could all these neat things with them.

Or we could use the equivalently powerfull features Ocaml *already* has...

Brian

Re: [Caml-list] stl?

[Brian Hurt]

On Wed, 4 Mar 2009, Martin Jambon wrote:

> Brian Hurt wrote:
>>
>>
>> On Tue, 3 Mar 2009, Jon Harrop wrote:
>>
>>> Functors give
>>> you the same capability in OCaml but they are rarely used precisely
>>> because
>>> the functionality is not very useful.
>>
>> I think I disagree with this.  I think functors aren't used very much in
>> Ocaml because:
>> 1) They're a big, scary name, and
>> 2) They're slightly less efficient.
>
> Functors are not used very much because they are not needed very often. 
> OCaml is a free market.

I don't think they're used anywhere nearly as often as they could 
profitably be employed, judging from Haskell's use of type classes.

>
> All sorts of reusable algorithms on arbitrary data can be nicely 
> implemented using functors, without more difficulty than the specialized 
> versions of the same algorithm. But do you often implement cool 
> algorithms that work on arbitrary types? Not me. Certainly less than 5% 
> of the time. Most of the time we have to deal with the brutality of the 
> real world, which is all bytes and strings.

I agree.  Going back to the original topic of this thread, my experience 
with C++ is that the vast majority of the time templates are used, Ocaml 
would simply use polymorphic types.  For example, you don't need functors 
to write a list library.  I'd guess 90-95% of the template uses I've seen 
in C++ have been just to do the equivalent of 'a list.

Brian

Re: [Caml-list] stl?

[Christophe TROESTLER]

On Wed, 4 Mar 2009 01:11:18 -0500, Brian Hurt wrote:
> 
> Try this.  Let's reimplement Haskell's Fractional class, in Ocaml, and
> then do Newton's method using this new Fractional class.  [...]
> 
> module type Fractional = sig
> 	type t
> 	val ( +. ) : t -> t -> t
> 	val ( -. ) : t -> t -> t
> 	val ( *. ) : t -> t -> t
> 	val ( /. ) : t -> t -> t
> 	val fabs : t -> t
> 	(* other functions elided from brevity *)
> end;;

Small point: you forgot the comparison functions — they are necessary
for Ratio.

> [...]  once you realize that the definitions of Fractional,
> FloatFractional, and RatioFractional all should be in the standard
> library (and the latter two should be just called Float and Ratio).

Well, they sort of are in the standard library already thanks to
Delimited Overloading!  http://pa-do.forge.ocamlcore.org/
With it, your code can simply be written as a macro:

  DEFINE NEWTON(M) = M.(
    let rec newton epsilon f df x =
      let x' = x - f x / df x in
      if abs(x - x') < epsilon then x'
      else newton epsilon f df x' in
    newton)
  
  let float_newton = NEWTON(Float)
  
  let ratio_newton = NEWTON(Ratio)
  
(and with no performance lost at all for those concerned with clock
cycles).

I have released a new version of Delimited Overloading with that new
example (ad-hoc-newton.ml).

Enjoy,
ChriS

Re: [Caml-list] stl?

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 04 March 2009 01:11:18 am Brian Hurt wrote:
> This is another large factor.  The three reasons functors aren't used very
> much are because:
> 1) They're a big, scary name,
> 2) They're slightly less efficient,
> 3) There are no good tutorials about how to use them, and
> 4) A fanatical devotion to the pope.
>
> I'll come in again...

Ha!  =]

But I'll add one more reason.  With functors you have extra overhead like 
having to be explicit with what function you're using.  In your example when 
you want to use Newton's method you always must write "RatioNewton.newtons" 
or "FloatNewtons.newtons".  The alternative is to functorize the call site, 
but (1) that has its own cost: lots of boilerplate functorizing code crowding 
the real code and (2) you just defer the explicit naming cost as when that 
function is called you'll still have to call either Float version or Ratio 
version.

I think objects are much closer to type classes and a much nicer solution.  
You can write:

class type ['a] num : object
	method add : 'a -> 'a -> 'a
	method mul : 'a -> 'a -> 'a
	method sub : 'a -> 'a -> 'a
	method div : 'a -> 'a -> 'a
	method abs : 'a -> 'a -> 'a
end

let rec newtons : ('a #num as 'b) -> ('b -> 'b) -> ('b -> 'b) -> 'b -> 'b 
= ...

Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFJro4RfIRcEFL/JewRAr0MAJ47aFyEvb4yzHOFVqVH/mS8w0TOfgCePNSE
HhVmyyi56RQ8y4gVpICcfXE=
=rz4T
-----END PGP SIGNATURE-----

Re: [Caml-list] stl?

[Kuba Ober]

>> i'm just trying to get my head around what it might look like, and
>> if/how it might be useful. (it just bugs me that somebody can claim
>> that C++ is the /only/ language that could do it -- maybe the real
>> quote implied "mainstream" or something. apparently Ada wasn't up to
>> snuff http://www.sgi.com/tech/stl/drdobbs-interview.html)
>
> I don't know what are the Stepanov requirements, but C++
> can do unboxed collections like  list<int>, which OCaml can
> not provide I think. a 'int list' has boxed integers in OCaml.
>
[...]
>
> The question is do we really need those 2 things ?
> I've worked a little bit with C++ using unboxed objects, that
> is without introducing pointers (similar to boxing) in templates,
> like list<figure> instead of list<figure*>, and passing them
> as value in parameters, or returning them,
> and it was far less efficient because there was lots of copy,
> and you could not use then virtual method on them. So in the

I think those are usually (or can be) implemented with
copy-on-write semantics. Heck, if the objects are large, you can have
specialized versions which use hardware-assisted copy-on-write.

This is pretty much how data structures in Qt work, say when you pass
QString around. While people usually pass a reference to a const QString
as a read-only parameter, it costs no more to pass QString by value --  
QString
won't copy much besides a pointer or two, and it's a fairly small and  
simple
class, as far as copy construction goes.

Cheers, Kuba

Re: [Caml-list] stl?

[Kuba Ober]

>> I've worked a little bit with C++ using unboxed objects, that
>> is without introducing pointers (similar to boxing) in templates,
>> like list<figure> instead of list<figure*>, and passing them
>> as value in parameters, or returning them,
>> and it was far less efficient because there was lots of copy,
>> and you could not use then virtual method on them. So in the
>> end the C++ programmer I thing manually re-introduce boxing
>> when using STL if he wants good performance, and he can not really
>> rely either on the default copy/equal implementation provided
>> by those templates. So, yes STL makes it possible to do things,
>> but programmers don't want them, or only in very few cases where
>> one need extreme performance.
>
> The STL is extremely slow. If you want fast code in C++ then you  
> drop to the C
> subset. Alex Stepanov tried and failed to implement efficient  
> constructs in
> the STL. Furthermore, the memory consumption of his library is  
> awful. OCaml's
> GC is far more efficient with memory whilst permitting easy sharing.

I don't think that STL is generally slow. There are corner cases where  
you'd do
well to use a custom allocator or somesuch, but in methinks  
contemporary STL
implementations have performance on par with C.

If you code using STL in a way which copies data all around, it will  
be no slower
than doing all the copying in C. Otherwise known as comparing apples  
to apples.

Cheers, Kuba

Re: [Caml-list] stl?

[Brian Hurt]

On Wed, 4 Mar 2009, Peng Zang wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Wednesday 04 March 2009 01:11:18 am Brian Hurt wrote:
>> This is another large factor.  The three reasons functors aren't used very
>> much are because:
>> 1) They're a big, scary name,
>> 2) They're slightly less efficient,
>> 3) There are no good tutorials about how to use them, and
>> 4) A fanatical devotion to the pope.
>>
>> I'll come in again...
>
> Ha!  =]
>
> But I'll add one more reason.  With functors you have extra overhead like
> having to be explicit with what function you're using.  In your example when
> you want to use Newton's method you always must write "RatioNewton.newtons"
> or "FloatNewtons.newtons".  The alternative is to functorize the call site,
> but (1) that has its own cost: lots of boilerplate functorizing code crowding
> the real code and (2) you just defer the explicit naming cost as when that
> function is called you'll still have to call either Float version or Ratio
> version.

Yeah.  I think of this as one of the advantages of Functors.

Here are two real problems I've hit with type classes, in only a few weeks 
banging around in Haskell.

For example, you can't have more than one instance of a type class for any 
given type.  So let's say you want to have a type class for things that 
can be converted to and from s-expressions, like:
 	data Sexp =
 		Atom String
 		| List [ Sexp ]

 	class Sexpable a where
 		toSexp :: a -> Sexp
 		fromSexp :: Sexp -> Maybe a

So then you start throwing out the standard instances, among others, you 
do one for string:
 	instance Sexpable String where
 		toSexp s = Atom s
 		fromSexp (Atom s) = Just s
 		fromSexp _ = Nothing

and, a little while later, one for generic lists:
 	instance Sexpable a => Sexpable [ a ] where
 		toSexp xs = List $ map toSexp xs
 		fromSexp (List xs) = mapM fromSexp xs
 		fromSexp _ = Nothing

Opps!  Now you have conflicting instances for type String- one the 
explicit implementation, and one via the generic list.  There are kludges 
to get around this, but they cause their own problems (Brian's first law 
of programming: kludges multiply).  A common one is to add the function 
toSexpList and fromSexpList to the fundamental type class, and drop the 
generic list implementation.  Except now you can't simply toSexp a value 
of type Map Int ([Int], Foo) despite the fact that Maps, Ints, Foos, and 
tuples all have toSexp defined over them- that list in there says that you 
have to pick things apart by hand, so you can call toSexpList instead of 
toSexp at the right point.

Here's another example, slightly translated.  Newton's method is actually 
a very widely applicable algorithm.  There is a variant of it, called 
Newton-Kantorovich, which solves systems of non-linear equations. 
Basically, the function f has type vector -> vector, with it's inputs the 
current values of all the variables used by all the equations (as a 
vector), and it's output the computed values of all the equations (as a 
vector).  The derivative of this function, f', has the type vector -> 
matrix, the input being the current values of all the variables, and the 
output being the matrix of partial derivatives.  Basically, the element at 
row i, column j of the matrix is the old fasioned, single-variable 
derivitive of equation i, assuming that all variables except variable j 
are constants (with their current value).  Then, instead of just doing x' 
= x - (f x)/(f' x), we first solve for (f' x)*y = f x for y, which is just 
your standard linear algebra solve Ax = b for x problem.  You can then 
calculate x' = x - y using standard vector subtraction.

But when you try to implement this, you realize that you have not one, but 
three (arguably four), different types all co-variant.  You have the type 
of x, which is a vector (and arguable the different type of f x, which can 
be a different size of vector- is the vector length an aspect of it's type 
or not?), the type of the differential (matrix, in this case), and the 
type of the norm of x, which is generally a real of some sort.  In my 
original example, I assumed that all three of these were the same type- 
but I may not want to.  And actually, you start wanting to split some of 
the various types off earlier- for example, if your function uses 
complexes or quaterions, the type of the values and the types of the 
derivitives may be the same, but you may want a different type (a real 
number type) for the norm.

Now, I comment you *can* do this in Haskell- using GHC specific 
extensions.  But you don't need fancy extensions (which cause problems in 
the type checker, if I understand things correctly) to do this, quite 
easily, with functors.

>
> I think objects are much closer to type classes and a much nicer solution.
> You can write:

If only Ocaml implemented objects!

Oh, wait.  Never mind.

Brian

Re: [Caml-list] stl?

[Andreas Rossberg]

[-- Attachment #1: Type: text/plain, Size: 956 bytes --]

On Mar 4, 2009, at 17.14 h, Brian Hurt wrote:
>
> So then you start throwing out the standard instances, among others,  
> you do one for string:
> 	instance Sexpable String where
> 		toSexp s = Atom s
> 		fromSexp (Atom s) = Just s
> 		fromSexp _ = Nothing
>
> and, a little while later, one for generic lists:
> 	instance Sexpable a => Sexpable [ a ] where
> 		toSexp xs = List $ map toSexp xs
> 		fromSexp (List xs) = mapM fromSexp xs
> 		fromSexp _ = Nothing
>
> Opps!  Now you have conflicting instances for type String- one the  
> explicit implementation, and one via the generic list.

To be fair, your String instance is using a GHC extension. It is not  
legal in plain Haskell.

IMO, in this particular example, the problem is caused not so much by  
limitations of type classes as such (which exist, of course), but by  
the somewhat questionable idea of defining a fundamental type like  
String as a list of chars, transparently.

- Andreas


[-- Attachment #2: Type: text/html, Size: 2133 bytes --]

Re: [Caml-list] stl?

[Mikkel Fahnøe Jørgensen]

2009/3/3 Raoul Duke <raould@gmail.com>:
> hi,
>
> the caml archives show discussion around C++ polymorphism wrt STL
> (since Stepanov iirc said that C++ was the only language which
> supported what he needed to let him implement his generic programming)
> but i didn't yet see anywhere a concrete implementation or mapping
> from C++ STL to O'Caml.

As I recall, Stepanov did originally work containers in Lisp or
similar, but realized this would never help "real world" programmers.
The C++ template is far more powerful than originally anticipated and
Stepanov took advantage of that. Clearly, the choice of C++ has
affected the design of STL, so it would be pointless to try to port
STL directly to OCaml.

In fact, I think that OCamls basic Array, List, containers and
polymorphic algorithms does exactly what Stepanov intended to do,
without having to introduce Functors or other overhead. However, OCaml
could do with a more precisely defined container duck typing interface
(not an interface just convention) which I think will happen with
Batteries. I think perhaps OCaml could have a library of algorithms
that are not specific to one container type, but again that requires
better duck typed containers, and perhaps it is just better and more
efficient to implement the most important operations for each
container type instead of trying to generalized the entire world.

Scripting languages were not so hot at the time, short of Perl, but
Ruby would easily fit well into the STL idea, just like Lisp also did.

There was a discussion by STL insiders about wether algorithms (simple
example is the min function) should be template parameterized. They
ended up not having explicit type arguments because this was much
simpler to work with. Containers (like vector) have type arguments
because they were necessary in C++.

As to whether STL is well designed or not, fast or not, I think STL at
the time solved a great problem. Of course you could do something
faster, but often a map or set would be just what needed, just like
OCamls current Map and Set is usually good enough.

Mikkel

Re: [Caml-list] stl?

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Wednesday 04 March 2009 11:14:50 am Brian Hurt wrote:
> Yeah.  I think of this as one of the advantages of Functors.
>
> Here are two real problems I've hit with type classes, in only a few weeks
> banging around in Haskell.
>
> For example, you can't have more than one instance of a type class for any
> given type.  So let's say you want to have a type class for things that
> can be converted to and from s-expressions, like:
>  	data Sexp =
>  		Atom String
>
>  		| List [ Sexp ]
>
>  	class Sexpable a where
>  		toSexp :: a -> Sexp
>  		fromSexp :: Sexp -> Maybe a
>
> So then you start throwing out the standard instances, among others, you
> do one for string:
>  	instance Sexpable String where
>  		toSexp s = Atom s
>  		fromSexp (Atom s) = Just s
>  		fromSexp _ = Nothing
>
> and, a little while later, one for generic lists:
>  	instance Sexpable a => Sexpable [ a ] where
>  		toSexp xs = List $ map toSexp xs
>  		fromSexp (List xs) = mapM fromSexp xs
>  		fromSexp _ = Nothing
>
> Opps!  Now you have conflicting instances for type String- one the
> explicit implementation, and one via the generic list.  There are kludges
> to get around this, but they cause their own problems (Brian's first law
> of programming: kludges multiply).  A common one is to add the function
> toSexpList and fromSexpList to the fundamental type class, and drop the
> generic list implementation.  Except now you can't simply toSexp a value
> of type Map Int ([Int], Foo) despite the fact that Maps, Ints, Foos, and
> tuples all have toSexp defined over them- that list in there says that you
> have to pick things apart by hand, so you can call toSexpList instead of
> toSexp at the right point.

Yeah, I can see the problem with Haskell type classes.  In OCaml though, I 
don't see how this is an issue.  Let's say we are building the class for 
StringObj.  We have a field for the data (type String) and now we implement 
the methods for working on Strings.  When it comes to the sexp methods, 
either implementation can be used.  You can choose.  If the implementation is 
written else where and we want to use inheritance, we can inherit both 
implementations and the last one is the effective one.  It's not a big issue.

Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFJrq7ufIRcEFL/JewRAi9zAJ96Ur/f79pFWJRaXGXwJMHcU1eTNgCg0rNo
JPEqD48wWiD8XVaafSVwdrc=
=tBvY
-----END PGP SIGNATURE-----

Re: [Caml-list] stl?

[Yoann Padioleau]

Mikkel Fahnøe Jørgensen <mikkel@dvide.com> writes:

> 2009/3/3 Raoul Duke <raould@gmail.com>:
>> hi,
>>
>> the caml archives show discussion around C++ polymorphism wrt STL
>> (since Stepanov iirc said that C++ was the only language which
>> supported what he needed to let him implement his generic programming)
>> but i didn't yet see anywhere a concrete implementation or mapping
>> from C++ STL to O'Caml.
>
> As I recall, Stepanov did originally work containers in Lisp or
> similar, but realized this would never help "real world" programmers.
> The C++ template is far more powerful than originally anticipated and
> Stepanov took advantage of that. Clearly, the choice of C++ has
> affected the design of STL, so it would be pointless to try to port
> STL directly to OCaml.
>
> In fact, I think that OCamls basic Array, List, containers and
> polymorphic algorithms  does exactly what Stepanov intended to do,

I don't think so. I've read the last "history of C++" by Stroustrup
in HOPL-III, who discusses quite a lot about the STL and Stepanov,
and from what I remember unboxing was a big issue
and having "generic" (which is slightly different from polymorphic)
algorithms without introducing performance
penalty that object-solution has with dynamic dispatch was also
a big issue. Those people are not stupid. They know about ML.
C++ even has some advanced dependent types in some way (array<n>).

I hate C++ with a passion, but the C++ designers are far from stupid.

> without having to introduce Functors or other overhead. However, OCaml
> could do with a more precisely defined container duck typing interface
> (not an interface just convention) which I think will happen with
> Batteries. I think perhaps OCaml could have a library of algorithms
> that are not specific to one container type, but again that requires
> better duck typed containers, and perhaps it is just better and more
> efficient to implement the most important operations for each
> container type instead of trying to generalized the entire world.
>
> Scripting languages were not so hot at the time, short of Perl, but
> Ruby would easily fit well into the STL idea, just like Lisp also did.

No, because of the performance penalty of dispatch. Again, those C++
designer guys have strong requirments on performance. Most
of us can live with those overheads, but apparently they don't.

> There was a discussion by STL insiders about wether algorithms (simple
> example is the min function) should be template parameterized. They
> ended up not having explicit type arguments because this was much
> simpler to work with. Containers (like vector) have type arguments
> because they were necessary in C++.
>
> As to whether STL is well designed or not, fast or not, I think STL at
> the time solved a great problem. Of course you could do something
> faster, but often a map or set would be just what needed, just like
> OCamls current Map and Set is usually good enough.

Sure (when they are defunctorized ... :) )

>
> Mikkel
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 06:11:18 Brian Hurt wrote:
> On Wed, 4 Mar 2009, Jon Harrop wrote:
> > Efficiency is only important in the context of functors when abstracting
> > very fast and common functions like arithmetic without defunctorizing
> > your code. I don't think that is why people avoid functors in OCaml.
>
> Arithmetic operators that are themselves very cheap.  The cost of
> functorization is large compared to, say, floating point addition- but
> small compared to the cost of, say, vector addition.

Depends how big your vectors are.

> And it's expensive only because Ocaml lacks an obvious optimization
> (defunctorization). 

If you neglect the enormous disadvantages: whole program analysis => no 
incremental compilation and no DLLs.

You can resolve the abstraction as soon as possible, as Haskell, does but then 
you're on the slippery slope to wildly unpredictable performance that renders 
the language too risky for a lot of real work.

> And yet this whole discussion is simply proving my point- we're comparing
> clock cycles here.

A circular argument: you brought up clock cycles.

> Yes, if you're writing the inner loops of a numeric 
> computation that'll take days to run, maybe, *MAYBE*, the cost difference
> of calling via a functor is worthwhile to worry about.

Definitely, not "maybe". The cost is over an order of magnitude for the 
fastest operations. Therefore, many forms of arithmetic including 
low-dimensional vector/matrix and interval arithmetic will suffer significant 
performance degradation.

> But that's the 
> point where I start being really tempted to drop down to C, or even
> assembly (for SSE Vectorization).

If you want to drop to anything, drop to LLVM because it is faster than C and 
easier than assembler.

> But for the vast bulk of people 
> programming, performance (at least on the clock cycle level) simply isn't
> that important

For some definition of "programming" that includes website design, maybe.

> - as demonstrated by all the "real work" being done in hideously slow
> languages like Ruby, Python, etc... 

Real work is done mostly in C++, Java and C# and proven predictable efficiency 
is a huge part of that.

> > I think that is a reflection of what the communities desire rather than
> > what they already have. OCaml is already fast (particularly on amd64) but
> > OCamlers always want even better performance. Haskell's development
> > experience is a real sore point and they want to address that. However, I
> > would also say that both communities are moving very slowly toward these
> > goals.
>
> Both languages have their annoyances.  Adjusting for the fact that I'm
> significantly more familiar with and comfortable with Ocaml, I don't find
> Haskell that much more difficult to work in.

F# can be much easier to work with than both OCaml and Haskell.

> >> The type classes comparison isn't even an analogy- it's a precise
> >> relationship. Anywhere you might be thinking, in Ocaml, "this would be a
> >> nice place to use a type class", use a functor.  You want operator
> >> overloading in Ocaml?  You got it: use a functor.
> >
> > Functors do not facilitate operator overloading. You still end up with a
> > combinatorial explosion in the number of operator names.
>
> Bwuh?
>
> Try this.  Let's reimplement Haskell's Fractional class, in Ocaml, and
> then do Newton's method using this new Fractional class.  Then I'll
> provide implementations that use both floats and ratios (arbitrary
> precision fractions).  First, we need to define Fractional.  That's just:
>
> module type Fractional = sig
>  	type t
>  	val ( +. ) : t -> t -> t
>  	val ( -. ) : t -> t -> t
>  	val ( *. ) : t -> t -> t
>  	val ( /. ) : t -> t -> t
>  	val fabs : t -> t
>  	(* other functions elided from brevity *)
> end;;
>
> Now we write our functorized Newton's method:
>
> module Make(F: Fractional) = struct
>
>  	open F;;
>
>  	let rec newtons epsilon f df x =
>  		let x' = x -. ((f x) /. (df x)) in
>  		if (fabs (x -. x')) < epsilon then
>  			x'
>  		else
>  			newtons epsilon f df x'
>  	;;
>
> end;;
>
> Now we provide an instance of Fractional for floats:
>
> module FloatFractional = struct
>  	type t = float
>  	let ( +. ) = ( +. );;
>  	let ( -. ) = ( -. );;
>  	let ( *. ) = ( *. );;
>  	let ( /. ) = ( /. );;
>  	let fabs x = abs_float x;;
> end;;
>
> module FloatNewtons = Make(FloatFractional);;
>
> Now we provide an instance for Ratios:
>
> module RatioFractional = struct
>  	type t = Ratio.ratio;;
>  	let ( +. ) = Ratio.add_ratio;;
>  	let ( -. ) = Ratio.sub_ratio;;
>  	let ( *. ) = Ratio.mult_ratio;;
>  	let ( /. ) = Ratio.div_ratio;;
>  	let fabs = Ratio.abs_ratio;;
> end;;
>
> module RatioNewtons = Make(RatioFractional);;
>
> Viola.  Operator overloading.  In Ocaml.

No, that is not overloading at all. You just replaced the functions wholesale.

Operator overloading is about being able to reuse an identifier to refer to 
different functions where the resolution depends upon the argument types. You 
have not accomplished that at all and your solution is uselessly fragile, 
which is precisely it is practically unheard of in real OCaml code in this 
context.

Look at another example, Knuth's algorithm for numerically robust variance:

  let f (m, s, k) x =
    let m' = m + (x - m) / float k
    m', s + (x - m) * (x - m'), k + 1

The "+" operator is used to mean both floating point addition and integer 
addition in the same expression. Functors cannot do that. You can replace "+" 
with float and int versions but only when they are in separate modules, so 
you not only end up breaking this simple expression into separate functions 
but even into separate modules. That's obviously crazy useless and, indeed, 
is precisely the motivation behind Christophe Troestlers's delimited 
overloading syntax extension.

So OCaml adopted + for int and +. for float. Sounds good but it scales really 
badly when you introduce 2D and 3D homogeneous vectors and matrices, 
arbitrary-dimensional vectors and matrices, quaternions, complex numbers and 
even a 32-bit float type. You need something closer to genuine overloading.

> >> If this causes you a
> >> knee jerk reaction about performance, ask yourself this: do you know how
> >> type classes are implemented in Haskell, and what their performance hit
> >> there is?  Now, imagine programming haskell where typeclasses are only
> >> used in a very places- Ord, Eq, Monad.  No Num.  No Monoid.  No Show.
> >> That's Ocaml.  Not that it has to be.
> >
> > I don't follow your breakdown. OCaml does not have Ord and Eq, it only
> > has a hack for structural equality. Same for Show. Few people care about
> > Monad, Num and Monoid.
>
> The turn you missed was that I'm say "what if Haskell programmers used
> type classes as rarely as Ocaml programmers use functors?"  Typeclasses
> are a huge win in Haskell, but primarily because they get *used*.

Right.

> > However, that is trivial to fix with run-time type information that can
> > convey per-type functions. Both F# and my HLVM already do that.
>
> I suppose we could sit around and whine that Ocaml doesn't have type
> classes, or reflection, or some other neat feature, that if it only had
> it, we could all these neat things with them.
>
> Or we could use the equivalently powerfull features Ocaml *already* has...

If you mean OCaml's objects, they also do not solve this problem.

IMHO, the only real solution is to build a new infrastructure for OCaml and 
its relatives that provides everything we want. Once you have something the 
community can contribute to efficiently, industry will back it and we can 
build something better using today's technology in a relatively short amount 
of time.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 16:48:18 Yoann Padioleau wrote:
> I don't think so. I've read the last "history of C++" by Stroustrup
> in HOPL-III, who discusses quite a lot about the STL and Stepanov,
> and from what I remember unboxing was a big issue
> and having "generic" (which is slightly different from polymorphic)
> algorithms without introducing performance
> penalty that object-solution has with dynamic dispatch was also
> a big issue. Those people are not stupid.

If they were not stupid, why were their innovations were dropped, e.g. Java, 
C# and even VB.NET provide parametric polymorphism from ML (aka generics) 
instead of C++ templates?

> They know about ML.

IIRC Alex Stepanov claimed to know ML but then made a series of factually 
incorrect statements about it, e.g. "phantom types do not exist". His 
published work includes nothing on anything related to ML:

  http://www.stepanovpapers.com/

I do not believe they knew about ML.

> C++ even has some advanced dependent types in some way (array<n>).

I would not call it "advanced". C++'s type system was accidentally Turing 
complete in a very practically limited way.

Haskell is similar in this respect: check Oleg's 600-line GHC-extended Haskell 
equivalent of the OCaml code:

  `a

That's what the "power" of Turing completeness buys you.

> I hate C++ with a passion, but the C++ designers are far from stupid.

C++ is the pedagogical example of bad language design. I've learned about 20 
programming languages now and every one taught me something new. C++ taught 
me what happens when you let idiots loose on programming language design and 
get industry to hype the result regardless of its objective value.

I'm very happy to see C++ dying.

> > Scripting languages were not so hot at the time, short of Perl, but
> > Ruby would easily fit well into the STL idea, just like Lisp also did.
>
> No, because of the performance penalty of dispatch. Again, those C++
> designer guys have strong requirments on performance.

Their performance requirements were: destroy the performance of anything we 
are not familiar with in order to preserve the performance of familiar 
features regardless of the relative merits of the different approaches. That 
is really stupid and very counter productive, of course.

> Most of us can live with those overheads, but apparently they don't.

No, we don't just live with the overheads. We reap the benefits of objectively 
well-engineered features like fast exceptions and fast garbage collection 
that C++ is incapable of.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Yoann Padioleau]

Brian Hurt <bhurt@spnz.org> writes:

>>>> Functors give
>>>> you the same capability in OCaml but they are rarely used precisely because
>>>> the functionality is not very useful.
>>>
>>> I think I disagree with this.  I think functors aren't used very much
>>> in Ocaml because:
>>
>>  0) they are intrusive! putting code inside a functor may entail the
>> need to modify also lots of related code. That's one of the worst
>> thing for a programming feature. Your modification can not be local. I
>> hate monad for the same reason, and I like ocaml exception mechanism,
>> and using sometimes global refs for the same reason.
>
> No.
>
> Here's what you can do.  Say you had an old function:
> 	let foo x = ...
> and you want to functorize it for whatever reason.  

my point is I don't want to functorize it; I want to solve
a problem, and I am looking for the fastest way to get there.
If you start with the assumption that you want to functorize
something, then indeed you will need a functor ...

> But you have lots
> of code depending upon the old type signature that you don't want to
> change. First, you functorize foo:
>
> 	module Make(X: Whatever) = struct let foo x = ... end;;
>
> Then you include the "classic foo", like:
>
> 	module T = Make(struct ... old defns ... end);;
> 	include T;;
>
> Where ... old defns ... is all the original types and functions that
> foo used that are now provided by the functor.  So you now have a
> module that exports both a "functorized" foo and a "classic" foo, and
> all the old code continues to just work (after a recompile, natch).

My goal is not being backward compatible. Of course you can
keep your old function and define new functions ... 
My goal is to evolve code, so I want to change the behavior of 'foo',
and I want to benefit from this new behavior, 
but I want this evolution to have the less collateral effects on
the structure of the rest of the program. 

For instance I got a set of functions that were working on some 'a
stuff, and I was using somewhere a naive list as a first draft. Later
I want to optimize things, and put those 'a in a more efficient
data-structure, but if use the Map data-structure, then I will be
forced to change lots of things. Argh, damned. Well, wait, I will just
use the defunctorized interface of Hashbtl :)

Again, just imagine one second that 'a list were not present in OCaml,
and that the only way you had to make a list would be to use
a functorized interface of a List module. Would you like that ? 
(that's what we are forced to do when using Map and that's why
I always use Hashtbl instead).

>
> This is much the same trick you use in Haskell when adding a typeclass
> dependency to the signature of a function- so long as you provide a
> typeclass instance for the old type, the old code continues to work
> with a recompile.
>
> I also comment, this is also a problem C++ templates have-
> templatizing a class in C++ is also an "intrusive" change.
>
> Brian

Re: [Caml-list] stl?

[Richard Jones]

On Wed, Mar 04, 2009 at 08:07:43PM +0000, Jon Harrop wrote:
> I would not call it "advanced". C++'s type system was accidentally Turing 
> complete in a very practically limited way.

(To prove Jon's point ...)

http://web.archive.org/web/20030501231817/www.annexia.org/freeware/cpptemplates/template-turing.cpp

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[Yoann Padioleau]

Jon Harrop <jon@ffconsultancy.com> writes:

> On Wednesday 04 March 2009 16:48:18 Yoann Padioleau wrote:
>> I don't think so. I've read the last "history of C++" by Stroustrup
>> in HOPL-III, who discusses quite a lot about the STL and Stepanov,
>> and from what I remember unboxing was a big issue
>> and having "generic" (which is slightly different from polymorphic)
>> algorithms without introducing performance
>> penalty that object-solution has with dynamic dispatch was also
>> a big issue. Those people are not stupid.
>
> If they were not stupid, why were their innovations were dropped, e.g. Java, 
> C# and even VB.NET 

First, who cares about Java or C# or VB.NET ? Last time I checked,
all the software I use on my machine (linux, mozilla, apache, mysql, emacs, 
X-windows, gtk, gnome, git, transmission, ...) are written in 
C and sometimes C++ (well except the beautiful ocamlopt and ocamldebug).
>From what I know, most Microsoft software are still written in C++
(Office, Visual Studio, the kernel, etc), and most Apple software
too (with sometimes some objective C stuff). Do we have an example
of a Java killer-app ?

> provide parametric polymorphism from ML (aka generics) 
> instead of C++ templates?

But haven't they added generics in Java because Java programmers
wanted some of the capabilities of C++ templates ? They even
use its syntax, and recent Java has added some ugly extensions
with some star-stuff around it that I don't understand. So I think
Java generics are closer to C++ templates than ML parametric polymorphism
and its inference. 

And Java has decided to not follow C++ on many things, they also
don't have overloading, they have a GC, etc. It's just not the
same target.

>
>> They know about ML.
>
> IIRC Alex Stepanov claimed to know ML but then made a series of factually 
> incorrect statements about it, e.g. "phantom types do not exist". 

I know ML and I don't know those phantom types thing. And if they are
"phantom", isn't he right indeed that they do not actually exist ? 

Do ML designers really know C++ and all its lastest features too 
as in C++0x ?

> His 
> published work includes nothing on anything related to ML:
>
>   http://www.stepanovpapers.com/
>
> I do not believe they knew about ML.

I think at least Stroustrup mentions in its "the design and
evolution of C++" book some comparisons with ML. 
But probably at that time ML didn't
have yet the functor stuff, just the parametric polymorphism. 



>
>> C++ even has some advanced dependent types in some way (array<n>).
>
> I would not call it "advanced". C++'s type system was accidentally Turing 
> complete in a very practically limited way.
>
> Haskell is similar in this respect: check Oleg's 600-line GHC-extended Haskell 
> equivalent of the OCaml code:
>
>   `a
>
> That's what the "power" of Turing completeness buys you.

:) Indeed. Many of those typing-guru tricks are as ugly and incomprensible 
than all the tricks people use with C++ expression templates.


>
>> I hate C++ with a passion, but the C++ designers are far from stupid.
>
> C++ is the pedagogical example of bad language design. 

That's what I was thinking before reading Stroustrup's HOPL-III paper
where you can a chance to get inside the head of stroustrup and the
rationale for many of his decisions. 

Stroustrup wanted a transition path from C to OO, and he wanted
to make that possible without introducing any bit of performance
penalty versus a hand crafted C program, because he knew
the programmers he targeted were really stubborn on performance
and then even a 1% overhead would not be accepted (you can call
those programmers morons, but that's the kind of people he 
wanted to have an impact on). He succeeded. 

> I've learned about 20 
> programming languages now and every one taught me something new. C++ taught 
> me what happens when you let idiots loose on programming language design and 
> get industry to hype the result regardless of its objective value.

C++ taught me that if you want to be really successful, you need a migration
path (or you need to wait for old programmers to die or that a
very different kind of platform arrives so that legacy code 
does not matter any more, e.g. the web).

>
> I'm very happy to see C++ dying.

Is it ? 

>
>> > Scripting languages were not so hot at the time, short of Perl, but
>> > Ruby would easily fit well into the STL idea, just like Lisp also did.
>>
>> No, because of the performance penalty of dispatch. Again, those C++
>> designer guys have strong requirments on performance.
>
> Their performance requirements were: destroy the performance of anything we 
> are not familiar with in order to preserve the performance of familiar 
> features 
> regardless of the relative merits of the different approaches. That 
> is really stupid and very counter productive, of course.

Did Stroustrup did that ? I never saw Stroustrup criticizing
other languages (but I've seend many Java people trashing C++).

>
>> Most of us can live with those overheads, but apparently they don't.
>
> No, we don't just live with the overheads. We reap the benefits of objectively 
> well-engineered features like fast exceptions and fast garbage collection 
> that C++ is incapable of.
>
> -- 
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] stl?

[Andreas Rossberg]

On Mar 4, 2009, at 21.49 h, Yoann Padioleau wrote:
>
> But haven't they added generics in Java because Java programmers
> wanted some of the capabilities of C++ templates ? They even
> use its syntax, and recent Java has added some ugly extensions
> with some star-stuff around it that I don't understand. So I think
> Java generics are closer to C++ templates than ML parametric  
> polymorphism
> and its inference.

Java Generics were originally designed by Wadler & Odersky, both of  
which came from functional programming.

> And Java has decided to not follow C++ on many things, they also
> don't have overloading, they have a GC, etc. It's just not the
> same target.

Java has overloading.

> I think at least Stroustrup mentions in its "the design and
> evolution of C++" book some comparisons with ML.
> But probably at that time ML didn't
> have yet the functor stuff, just the parametric polymorphism.

ML modules, including functors, where invented around 83/84 (by  
MacQueen), more than half a decade before macros evolved into  
templates, and a decade before D&E was published. Interestingly,  
Stroustrup even had his office down the hall from MacQueen at AT&T at  
that time. So he knew _about_ ML, but that's probably as far as it goes.

- Andreas

Re: [Caml-list] stl?

[Brian Hurt]

On Wed, 4 Mar 2009, Jon Harrop wrote:

> On Wednesday 04 March 2009 06:11:18 Brian Hurt wrote:
>> On Wed, 4 Mar 2009, Jon Harrop wrote:
>>> Efficiency is only important in the context of functors when abstracting
>>> very fast and common functions like arithmetic without defunctorizing
>>> your code. I don't think that is why people avoid functors in OCaml.
>>
>> Arithmetic operators that are themselves very cheap.  The cost of
>> functorization is large compared to, say, floating point addition- but
>> small compared to the cost of, say, vector addition.
>
> Depends how big your vectors are.

Less than it might seem.  First of all, you have the allocation costs to 
hold the new vector- there's 3-5 clocks right there.  Let's say the 
vectors are 3 elements long.  So you have six loads and three stores- 
assume stores are free, and loads cost 1 clock apeice- they're in L1 
cache, and they're getting preloaded.  Plus the 3 clocks for the floating 
point adds.  So that's 12-15 clock cycles right there.  Say I'm being 
pessimistic by a factor of 2, and it's really only 6-8 clock cycles.  Vr.s 
10 clock cycles or so for the call via functor.  Now we're down into the 
realm of only doubling the cost of the operation, not an order of 
magnitude increase.  A single mispredicted branch or L1 cache miss that 
has to go out to L2 cache- not even main memory, just L2!- would blow the 
overhead of calling via functor out of the water.

Premature optimization is the root of all evil.

>
>> And it's expensive only because Ocaml lacks an obvious optimization
>> (defunctorization).
>
> If you neglect the enormous disadvantages: whole program analysis => no
> incremental compilation and no DLLs.
>
> You can resolve the abstraction as soon as possible, as Haskell, does but then
> you're on the slippery slope to wildly unpredictable performance that renders
> the language too risky for a lot of real work.

That explains why no one uses C++ for real work- since it resolves 
template abstractions as soon as possible, it' performance is so 
unpredictable that it renders the language too risky for a lot of real 
work.

>
>> And yet this whole discussion is simply proving my point- we're comparing
>> clock cycles here.
>
> A circular argument: you brought up clock cycles.

Yes.  Because it's only at the point where you're counting clock cycles 
that the overhead of calling via a functor matters.

>
>> But for the vast bulk of people
>> programming, performance (at least on the clock cycle level) simply isn't
>> that important
>
> For some definition of "programming" that includes website design, maybe.

Compare the number of people writing CRUD web applications in Ruby on 
Rails to the *entirity* of the professional Ocaml, SML, Haskell, and F# 
communities.  I dare you.

But no, not just web applications.  Most business logic applications. 
Large chunks of the embedded world.  Most desktop applications.  Most code 
doesn't need to be "as fast as possible", it simply needs to be "fast 
enough".

>
>> - as demonstrated by all the "real work" being done in hideously slow
>> languages like Ruby, Python, etc...
>
> Real work is done mostly in C++, Java and C# and proven predictable efficiency
> is a huge part of that.

You should have warned me before mentioning "Java" in the same sentence as 
"proven predictable efficiency".  I was drinking when I read that, and now 
I have to clean my keyboard.

It's a negligable part of that.  Try this experiment.  Go to J. Random 
software manager in Java/.Net/C++ shop.  Ask them to list the reasons they 
use the language of choice.  Don't prompt them, just let them list things 
in the order that comes to mind.  Wait and see how long it is before 
"performance" comes up as an issue.

Java currently has a decent- not great, but decent- performance story. 
Now.  But Java became popular, and got into all of these coding shops, 
back when Java was either hideously slow, or radically unpredictable in 
performance.

> F# can be much easier to work with than both OCaml and Haskell.

Yep.  And Ocaml can be much easier to work with than Haskell or F#.  And 
Haskell can be much easier to work with then F# or Ocaml.

> No, that is not overloading at all. You just replaced the functions wholesale.
>
> Operator overloading is about being able to reuse an identifier to refer to
> different functions where the resolution depends upon the argument types.

OK.  So now we have a definition of what operator overloading is.  Now, my 
question: what's it good for?  It's obviously not necessary to write 
generic code- for example, a Newton's method that works on both floats and 
ratios.

The only advantage I see is that you're able to use + instead of +. in 
many places.  OK, this is an advantage- but hardly a major one.

> You
> have not accomplished that at all and your solution is uselessly fragile,
> which is precisely it is practically unheard of in real OCaml code in this
> context.
>
> Look at another example, Knuth's algorithm for numerically robust variance:
>
>  let f (m, s, k) x =
>    let m' = m + (x - m) / float k
>    m', s + (x - m) * (x - m'), k + 1
>
> The "+" operator is used to mean both floating point addition and integer
> addition in the same expression. Functors cannot do that. You can replace "+"
> with float and int versions but only when they are in separate modules, so
> you not only end up breaking this simple expression into separate functions
> but even into separate modules. That's obviously crazy useless and, indeed,
> is precisely the motivation behind Christophe Troestlers's delimited
> overloading syntax extension.

So, let's rewrite the above code to use different operators for floating 
point and integer operations:

   let f (m, s, k) x =
     let m' = m +. (x -. m) /. float k
     m', s +. (x -. m) *. (x -. m'), k + 1

Oh yes, I see now.  How much better it is if only we had operator 
overloading.

>
> So OCaml adopted + for int and +. for float. Sounds good but it scales really
> badly when you introduce 2D and 3D homogeneous vectors and matrices,
> arbitrary-dimensional vectors and matrices, quaternions, complex numbers and
> even a 32-bit float type. You need something closer to genuine overloading.

My experience in general has been that operators don't scale in complex 
cases.  Number operators for number types scale better, but in any 
complicated case, and especially in most non-numeric cases, I prefer 
pseudo-english names.

And I note that by far the most popular language for writing numeric code 
in, the all time champ for numerics, is Fortran.  A language that didn't 
allow operator overloading or redefinition at all, and which forced you to 
use pseudo-english named functions if you wanted to add two matrixs 
together.  For a definition of pseudo-english which is loose enough to 
include names like "dgemm".

>
> Right.
>
>>> However, that is trivial to fix with run-time type information that can
>>> convey per-type functions. Both F# and my HLVM already do that.
>>
>> I suppose we could sit around and whine that Ocaml doesn't have type
>> classes, or reflection, or some other neat feature, that if it only had
>> it, we could all these neat things with them.
>>
>> Or we could use the equivalently powerfull features Ocaml *already* has...
>
> If you mean OCaml's objects, they also do not solve this problem.

Wow.  Just... wow.  I spend page after page, message after message, 
singing the praises of functors, with out nearly a peep about the objects 
the whole time.  And then, at the end of a message that was all about how 
great functors are, I mention "equivalently powerfull features", you 
immediately assume I'm refering to...

objects.

Truly, you have a dizzying intellect.

Brian

Re: [Caml-list] stl?

[Nicolas Pouillard]

Excerpts from Brian Hurt's message of Wed Mar 04 17:14:50 +0100 2009:
> 
> 
> On Wed, 4 Mar 2009, Peng Zang wrote:
> 
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > On Wednesday 04 March 2009 01:11:18 am Brian Hurt wrote:

[...]

> > But I'll add one more reason.  With functors you have extra overhead like
> > having to be explicit with what function you're using.  In your example when
> > you want to use Newton's method you always must write "RatioNewton.newtons"
> > or "FloatNewtons.newtons".  The alternative is to functorize the call site,
> > but (1) that has its own cost: lots of boilerplate functorizing code crowding
> > the real code and (2) you just defer the explicit naming cost as when that
> > function is called you'll still have to call either Float version or Ratio
> > version.
> 
> Yeah.  I think of this as one of the advantages of Functors.
> 
> Here are two real problems I've hit with type classes, in only a few weeks 
> banging around in Haskell.
> 
> For example, you can't have more than one instance of a type class for any 
> given type.  So let's say you want to have a type class for things that 
> can be converted to and from s-expressions, like:

[...]

> Now, I comment you *can* do this in Haskell- using GHC specific 
> extensions.  But you don't need fancy extensions (which cause problems in 
> the type checker, if I understand things correctly) to do this, quite 
> easily, with functors.

Haskell `newtype's is a pretty reasonable answer to this problem.

A `newtype' is a bit like a type with only one constructor of only one argument,
except that there is no runtime cost for it. However by being a *new* type one
can define different instances of type classes for it. Moreover since the
deriving feature is extended on `newtype's, retrieving all the goodness of
the wrapped type is costless (deriving newtype is easy since generally the
code justs virtually unpacks and re-packs using the constructor and call
the same functions on the wrapped value).

Examples:

\begin{code}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Data.List
import Data.Function

newtype MySet a = MkMySet { toList :: [a] } -- here toList is an accessor
                                            -- function (MySet a -> [a])
  deriving (Read,Show,Functor,Monad) -- ...

norm :: Ord a => MySet a -> [a]
norm = nub . sort . toList

instance (Ord a) => Eq (MySet a) where (==) = (==) `on` norm
instance (Ord a) => Ord (MySet a) where compare = compare `on` norm

propMySet = MkMySet [1,2,3,4] == MkMySet [1,1,2,4,3]
\end{code}

Or another one:

\begin{code}
newtype DownInt = DownInt { fromDownInt :: Int }
  deriving (Eq,Read,Show,Enum,Num)

instance Ord DownInt where compare = flip compare `on` fromDownInt
  -- same as compare x y = fromDownInt y `compare` fromDownInt x

propDownInt = DownInt 4 < DownInt 2

-- this example is contrived since sortBy would be simpler here
-- however in larger examples the benifit is clearer, for instance
-- List.sort is not in a functor in OCaml.
sortDownInt :: [Int] -> [Int]
sortDownInt = map fromDownInt . sort . map DownInt

propDownInt' = [4,3,2,1] == sortDownInt [1,2,3,4]

-- since DownInt is in the Num class (an explicit choice
-- from the definition of DownInt), literals can be
-- freely lifted to DownInt.
propDownInt'' = [4,3,2,1] == sort [(1::DownInt),2,3,4]
\end{code}

Note that one can generalize `DownInt' as `Down' and get an easy
way to reverse the order on a type.

Since that, I personally consider type-classes goodness more valuable
than functors usage that doesn't fall in that category.

All the best,

-- 
Nicolas Pouillard

Re: [Caml-list] stl?

[Pal-Kristian Engstad]

[-- Attachment #1: Type: text/plain, Size: 1854 bytes --]

Yoann Padioleau wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
>   
>> I'm very happy to see C++ dying.
>>     
>
> Is it ? 
>   
C++ is definitely not dying.

Here are some reasons:

    * Most high-level languages decide the format of your data for you.
      This is good for most things, but if a large part of your
      application needs specific data layouts, then you are out of luck.
    * Most high-level languages can not support multiple forms of data
      allocations. Some applications need a range of allocation
      strategies, ranging from completely automatic (garbage collection)
      to completely manual.
    * Most high-level environments do not allow for fine-grained control
      of computing resources, e.g. soft real-time guarantees.
    * Most high-level languages do not allow for C/C++ intrinsics, for
      instance leveraging access to the SSE registers.
    * Most high-level languages do not allow for fine-grained control,
      for instance allowing different forms of threading mechanisms.

Of course, you can always say that you can use the foreign function 
interface, but then you lose inlining and speed. More importantly, you 
end up with a project with several different languages. That is 
generally a very bad idea.

In short, most high-level languages will remain used for only for toys 
and applications where speed and resource constraints is of no concern. 
Which is sad, because C++ has many, many problems - the most major one 
being that it is so easy to produce bugs.

Thanks,

PKE.

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.



[-- Attachment #2: Type: text/html, Size: 2487 bytes --]

Re: [Caml-list] stl?

[Brian Hurt]

On Wed, 4 Mar 2009, Yoann Padioleau wrote:

> My goal is not being backward compatible. Of course you can
> keep your old function and define new functions ...
> My goal is to evolve code, so I want to change the behavior of 'foo',
> and I want to benefit from this new behavior,
> but I want this evolution to have the less collateral effects on
> the structure of the rest of the program.
>
> For instance I got a set of functions that were working on some 'a
> stuff, and I was using somewhere a naive list as a first draft. Later
> I want to optimize things, and put those 'a in a more efficient
> data-structure, but if use the Map data-structure, then I will be
> forced to change lots of things. Argh, damned. Well, wait, I will just
> use the defunctorized interface of Hashbtl :)

Especially in the realm of data structure libraries (like the STL), I 
really question the utility of this.  Data structures vary wildly in the 
performance characteristics of their various operations.  For example, 
accessing a arbitrary element of a map is O(log N), doing so in a list is 
O(N).  But accessing the first element of a map is O(log N) in a map, but 
O(1) in a list.  So if I write my algorithm to always only need the first 
element of the sequence, but never need an arbitrary element, then 
replacing a list with a map is a real bad idea- and I don't need to 
perform actual comparisons to tell this.

Where this does come up is when what you're really doing is refactoring 
code.  Say I originally thought that I was only going to need the first 
element, but it turns out that I'm doing a lot more arbitrary accesses 
than original thought.  In this case, however, you're not just swapping 
this data structure out for that one, you're also changing more or less 
large chunks of the code to reflect the new assumptions.

Ocaml's huge advantage here then is not functors, or objects, or even type 
variables- it's just strong static typing.  This allows you to change 
things and just see where things break.

>
> Again, just imagine one second that 'a list were not present in OCaml,
> and that the only way you had to make a list would be to use
> a functorized interface of a List module. Would you like that ?
> (that's what we are forced to do when using Map and that's why
> I always use Hashtbl instead).

Humorously enough, I'm doing exactly this.  In a bunch of code I'm playing 
with, I've implemented an NeList module- nothing fancy, just a few dozen 
lines of code and the basic list operations, only the lists can not be 
empty.  They always have to contain at least one element.

But seriously, you hate functors that much?  The overhead of doing:

module StringMap = Map.Make(String);;

is so high to you, that you simply don't do it?

Mind if I ask why?

Brian

Re: [Caml-list] stl?

[Yoann Padioleau]

Brian Hurt <bhurt@spnz.org> writes:

> On Wed, 4 Mar 2009, Yoann Padioleau wrote:
>> Again, just imagine one second that 'a list were not present in OCaml,
>> and that the only way you had to make a list would be to use
>> a functorized interface of a List module. Would you like that ?
>> (that's what we are forced to do when using Map and that's why
>> I always use Hashtbl instead).
>
> Humorously enough, I'm doing exactly this.  In a bunch of code I'm
> playing with, I've implemented an NeList module- nothing fancy, just a
> few dozen lines of code and the basic list operations, only the lists
> can not be empty.  They always have to contain at least one element.
>
> But seriously, you hate functors that much?  

With a passion :) I don't like functors for generic data structures
such as Map.

If you have some code that you want to parametrize over multiple types,
and each of this type has some complex constraints, then I like functors.
But when the only constraints on your type is that you want a Ord, or a Eq
(or a Show), then I think functors are overkill, and I am fine with the default
Pervasives.compare

Also I tend to find harder to understand code using functors ...
You can get many signatures, functors taking functors, ... I am not
evolved enough to handle that. 

> The overhead of doing:
>
> module StringMap = Map.Make(String);;
>
> is so high to you, that you simply don't do it?

I do that sometimes, and I also have a IntMap and IntIntMap.

The problem is when your code has some 'a involved, and that
your key is for instance a pair, or triple of stuff having
a polymorphic type. Then, before, I had a function taking
some 'a and returning some 'b, and internally it was using
a list and everything was fine. Then one day I want to optimize
this and use internally a Map and then everything goes down ...
I have to change the signature of my function taking a 'a
into a functor now taking a T, and also do that for its caller,
etc, etc. With typeclass, most of this tedious boilerplate
work would be done behind the scene for me thanks to type inference.
Haskell will just propagate the need to have a    Ord a => 
in addition to the original signature of  'a -> ...

In a similar way, you have some complex code polymorphic in a 'a
and at some point, deep inside a call chain, you want to print
some debugging information about this tiny 'a,  so you really
want to do a      generic_print x, but you can not.
Or if you want to do that you have to turn that into a functor
taking a T where the T is contrained to have a 'print' method/function. 
With haskell you just write 'show x', and haskell inference will
do the work to add the Show a =>. So right now in OCaml
I tend to use the Dumper module of Richard Jones. When I can
avoid functors, I do so.


>
> Mind if I ask why?
>
> Brian

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 21:51:40 Pal-Kristian Engstad wrote:
> Yoann Padioleau wrote:
> > Jon Harrop <jon@ffconsultancy.com> writes:
> >> I'm very happy to see C++ dying.
> >
> > Is it ?
>
> C++ is definitely not dying.

C++'s job market share has fallen 50% in 4 years here in the UK:

  http://www.itjobswatch.co.uk/jobs/uk/c++.do

> Here are some reasons:
>
>     * Most high-level languages decide the format of your data for you.
>       This is good for most things, but if a large part of your
>       application needs specific data layouts, then you are out of luck.

That is not true for all high-level languages (e.g. .NET languages convey 
low-level data representations and XNA uses them directly) and it is a 
dominant concern for only a tiny number of applications.

>     * Most high-level languages can not support multiple forms of data
>       allocations. Some applications need a range of allocation
>       strategies, ranging from completely automatic (garbage collection)
>       to completely manual.

C++ cannot provide efficient automatic GC.

>     * Most high-level environments do not allow for fine-grained control
>       of computing resources, e.g. soft real-time guarantees.

Many high-level languages make it easier to satisfy soft 
real-time "guarantees", e.g. incremental collection vs destructor avalanches.

>     * Most high-level languages do not allow for C/C++ intrinsics, for
>       instance leveraging access to the SSE registers.

That is easily resolved if it is not already present (which it is in Mono and 
LLVM already).

>     * Most high-level languages do not allow for fine-grained control,
>       for instance allowing different forms of threading mechanisms.

F# offers the .NET thread pool, asynchronous workflows and wait-free 
work-stealing queues from the TPL. What more do you want? :-)

> Of course, you can always say that you can use the foreign function
> interface, but then you lose inlining and speed.

The same is true of C/C++. You can get much better performance from assembler 
but calling assembler from C or C++ not only costs inlining and speed but 
even functionality because you have an ABI to conform to.

> More importantly, you end up with a project with several different
> languages. That is generally a very bad idea.

A common language run-time is the right solution, not C/C++.

> In short, most high-level languages will remain used for only for toys
> and applications where speed and resource constraints is of no concern.

You cannot feasibly parallelize or manage the resources of a non-trivial 
application in C/C++. The development cost of even attempting to do so is 
already prohibitively high and the result would be completely unmaintainable.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 21:59:51 Brian Hurt wrote:
> But seriously, you hate functors that much?  The overhead of doing:
>
> module StringMap = Map.Make(String);;
>
> is so high to you, that you simply don't do it?
>
> Mind if I ask why?

Your example is fragile: it doesn't work with Int and Float because they were 
never written:

$ ocaml
        Objective Caml version 3.09.1

# module IntMap = Map.Make(Int);;
Unbound module Int
# module FloatMap = Map.Make(Float);;
Unbound module Float

So you have to define a temporary module by hand in general:

# module IntMap = Map.Make(struct type t = int let compare = compare end);;
module IntMap :
  sig
    type key = int
    type +'a t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  end

You want a mapping to IntMaps but IntMap is parameterised and the Map.Make 
functor cannot handle that:

# module IntMapMap = Map.Make(IntMap);;
Signature mismatch:
Modules do not match:
  sig
    type key = int
    type 'a t = 'a IntMap.t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  end
is not included in
  Map.OrderedType
Type declarations do not match:
  type 'a t = 'a IntMap.t
is not included in
  type t

So you have to create another temporary module from the IntMap one:

# module IntMapMap = Map.Make(struct
                                type t = string IntMap.t
                                let compare =
                                  IntMap.compare compare
                              end);;
module IntMapMap :
  sig
    type key = string IntMap.t
    type +'a t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  end

All of that code is completely redundant. In F#, you write nothing at all and 
get the same functionality with more safety.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 21:23:53 Brian Hurt wrote:
> On Wed, 4 Mar 2009, Jon Harrop wrote:
> > Depends how big your vectors are.
>
> Less than it might seem.  First of all, you have the allocation costs to
> hold the new vector- there's 3-5 clocks right there.  Let's say the
> vectors are 3 elements long.  So you have six loads and three stores-
> assume stores are free, and loads cost 1 clock apeice- they're in L1
> cache, and they're getting preloaded.  Plus the 3 clocks for the floating
> point adds.  So that's 12-15 clock cycles right there.  Say I'm being
> pessimistic by a factor of 2, and it's really only 6-8 clock cycles.  Vr.s
> 10 clock cycles or so for the call via functor.  Now we're down into the
> realm of only doubling the cost of the operation, not an order of
> magnitude increase.  A single mispredicted branch or L1 cache miss that
> has to go out to L2 cache- not even main memory, just L2!- would blow the
> overhead of calling via functor out of the water.

2x slower, yes.

> Premature optimization is the root of all evil.

That is not a premature optimization.

> >> And it's expensive only because Ocaml lacks an obvious optimization
> >> (defunctorization).
> >
> > If you neglect the enormous disadvantages: whole program analysis => no
> > incremental compilation and no DLLs.
> >
> > You can resolve the abstraction as soon as possible, as Haskell, does but
> > then you're on the slippery slope to wildly unpredictable performance
> > that renders the language too risky for a lot of real work.
>
> That explains why no one uses C++ for real work- since it resolves
> template abstractions as soon as possible, it' performance is so 
> unpredictable that it renders the language too risky for a lot of real
> work.

The unpredictability stems from allowing the Haskell compiler to choose 
whether it resolves the abstraction statically or dynamically. C++ prohibits 
dynamic resolution (greatly limiting its capabilities) so it is entirely 
predictable and your analogy is invalid.

> >> But for the vast bulk of people
> >> programming, performance (at least on the clock cycle level) simply
> >> isn't that important
> >
> > For some definition of "programming" that includes website design, maybe.
>
> Compare the number of people writing CRUD web applications in Ruby on
> Rails to the *entirity* of the professional Ocaml, SML, Haskell, and F#
> communities.  I dare you.

Irrelevant. This was about performance not specific functional programming. 
Compare the number of people using Ruby and Python for anything at all to the 
number of professional C++, Java and C# programmers.

> But no, not just web applications.  Most business logic applications.
> Large chunks of the embedded world.  Most desktop applications.  Most code
> doesn't need to be "as fast as possible", it simply needs to be "fast
> enough".

Ruby and Python are not common there either.

> >> - as demonstrated by all the "real work" being done in hideously slow
> >> languages like Ruby, Python, etc...
> >
> > Real work is done mostly in C++, Java and C# and proven predictable
> > efficiency is a huge part of that.
>
> You should have warned me before mentioning "Java" in the same sentence as
> "proven predictable efficiency".  I was drinking when I read that, and now
> I have to clean my keyboard.
>
> It's a negligable part of that.

Not true.

> Try this experiment.  Go to J. Random software manager in Java/.Net/C++
> shop. 

Like me.

> Ask them to list the reasons they 
> use the language of choice.  Don't prompt them, just let them list things
> in the order that comes to mind.  Wait and see how long it is before
> "performance" comes up as an issue.

Ask them why they don't use Ruby and Python and they'll say "performance".

> Java currently has a decent- not great, but decent- performance story.
> Now.  But Java became popular, and got into all of these coding shops,
> back when Java was either hideously slow, or radically unpredictable in
> performance.

On a scale with Ruby and Python, Java has never been "hideously" slow.

> > Operator overloading is about being able to reuse an identifier to refer
> > to different functions where the resolution depends upon the argument
> > types.
>
> OK.  So now we have a definition of what operator overloading is.  Now, my
> question: what's it good for?  It's obviously not necessary to write
> generic code- for example, a Newton's method that works on both floats and
> ratios.

Overloading is not about abstraction, it is about syntactic convenience. That 
is precisely why functors are not a viable alternative.

Type inference is closely related to overloading in that sense: both are 
designed to improve clarity and brevity.

> The only advantage I see is that you're able to use + instead of +. in
> many places.  OK, this is an advantage- but hardly a major one.

That is a huge advantage when you have a lot of numerical types.

> > Look at another example, Knuth's algorithm for numerically robust
> > variance:
> >
> >  let f (m, s, k) x =
> >    let m' = m + (x - m) / float k
> >    m', s + (x - m) * (x - m'), k + 1
> >
> > The "+" operator is used to mean both floating point addition and integer
> > addition in the same expression. Functors cannot do that. You can replace
> > "+" with float and int versions but only when they are in separate
> > modules, so you not only end up breaking this simple expression into
> > separate functions but even into separate modules. That's obviously crazy
> > useless and, indeed, is precisely the motivation behind Christophe
> > Troestlers's delimited overloading syntax extension.
>
> So, let's rewrite the above code to use different operators for floating
> point and integer operations:
>
>    let f (m, s, k) x =
>      let m' = m +. (x -. m) /. float k
>      m', s +. (x -. m) *. (x -. m'), k + 1
>
> Oh yes, I see now.  How much better it is if only we had operator
> overloading.

Now consider changing one of the types:

. I replace "float" with "float32" and I'm done.

. You have to replace every instance of every float operator with a different 
one, such as a function call to Float32.add.

> > So OCaml adopted + for int and +. for float. Sounds good but it scales
> > really badly when you introduce 2D and 3D homogeneous vectors and
> > matrices, arbitrary-dimensional vectors and matrices, quaternions,
> > complex numbers and even a 32-bit float type. You need something closer
> > to genuine overloading.
>
> My experience in general has been that operators don't scale in complex
> cases.  Number operators for number types scale better, but in any
> complicated case, and especially in most non-numeric cases, I prefer
> pseudo-english names.

I prefer "+" whereever you see "+" in mathematics.

> And I note that by far the most popular language for writing numeric code
> in, the all time champ for numerics, is Fortran.  A language that didn't
> allow operator overloading or redefinition at all, and which forced you to  
> use pseudo-english named functions if you wanted to add two matrixs
> together.  For a definition of pseudo-english which is loose enough to
> include names like "dgemm".

Ironically, Fortran has not only had overloaded operators and functions for 50 
years but they are used in the Fortran 77 definition of the DGEMM function 
and have even been user-defineable since Fortran 90.

Regardless, if you want to see overloading done right in the context of ML, 
look at F# and not Fortran.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Pal-Kristian Engstad]

Jon Harrop wrote:
> C++'s job market share has fallen 50% in 4 years here in the UK:
>
>   http://www.itjobswatch.co.uk/jobs/uk/c++.do
>   
Sure -- those are probably not jobs that require performance, nor have 
resource constraints.
>> Here are some reasons:
>>
>>     * Most high-level languages decide the format of your data for you.
>>       This is good for most things, but if a large part of your
>>       application needs specific data layouts, then you are out of luck.
>>     
>
> That is not true for all high-level languages (e.g. .NET languages convey 
> low-level data representations and XNA uses them directly) and it is a 
> dominant concern for only a tiny number of applications.
>   
I did say most. By the way, XNA is a toy. A good toy, but a toy, 
nonetheless. I'm not sure that all the products in my industry 
constitutes "a tiny number" of applications. Also, bear in mind that in 
my industry, a single game comprise about 500,000-1,000,000 LOC.
>>     * Most high-level languages can not support multiple forms of data
>>       allocations. Some applications need a range of allocation
>>       strategies, ranging from completely automatic (garbage collection)
>>       to completely manual.
>>     
>
> C++ cannot provide efficient automatic GC.
>   
That's not true. We run GC on all of our game tasks. It's "manual"-ish, 
but doable.
>>     * Most high-level environments do not allow for fine-grained control
>>       of computing resources, e.g. soft real-time guarantees.
>>     
>
> Many high-level languages make it easier to satisfy soft 
> real-time "guarantees", e.g. incremental collection vs destructor avalanches.
>   
Call me cynical, but I simply don't buy it.
>>     * Most high-level languages do not allow for C/C++ intrinsics, for
>>       instance leveraging access to the SSE registers.
>>     
>
> That is easily resolved if it is not already present (which it is in Mono and 
> LLVM already).
>   
Indeed. But then there are target specific control registers, timers, 
etc. etc. Usually, these are not supported well.
>>     * Most high-level languages do not allow for fine-grained control,
>>       for instance allowing different forms of threading mechanisms.
>>     
>
> F# offers the .NET thread pool, asynchronous workflows and wait-free 
> work-stealing queues from the TPL. What more do you want? :-)
>   
Well, first of all - something that doesn't suck performance wise. And 
it is essential that it works on non-Intel platforms. F# is indeed 
promising, but again - I would not use it for performance critical code 
- which is about 30-50% of a game's code base.
>> Of course, you can always say that you can use the foreign function
>> interface, but then you lose inlining and speed.
>>     
>
> The same is true of C/C++. You can get much better performance from assembler 
> but calling assembler from C or C++ not only costs inlining and speed but 
> even functionality because you have an ABI to conform to.
>   
This is not true. Pretty much all C++ compilers have both intrinsic and 
inline assembly support.
>> More importantly, you end up with a project with several different
>> languages. That is generally a very bad idea.
>>     
>
> A common language run-time is the right solution, not C/C++.
>   
That is exactly my point. It needs to be *one* language that can cover 
the broad base from non-performance critical AI code to performance 
critical culling, animation and physics code. But the sad fact is that 
there is no competitor to C++. Mind you - I *want* to have something 
else - it is just not feasible.
>   
>> In short, most high-level languages will remain used for only for toys
>> and applications where speed and resource constraints is of no concern.
>>     
>
> You cannot feasibly parallelize or manage the resources of a non-trivial 
> application in C/C++. The development cost of even attempting to do so is 
> already prohibitively high and the result would be completely unmaintainable.
>   
That depends on how skilled you are as a programmer. I'd venture to say 
that professional game programmers have exactly that skill. Now, I do 
agree that it is costly - but it is by far not "completely 
unmaintainable". It just requires a lot of discipline, care and and a 
set of good tools and libraries.

Thanks,

PKE.

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 22:42:15 Yoann Padioleau wrote:
> Brian Hurt <bhurt@spnz.org> writes:
> > On Wed, 4 Mar 2009, Yoann Padioleau wrote:
> >> Again, just imagine one second that 'a list were not present in OCaml,
> >> and that the only way you had to make a list would be to use
> >> a functorized interface of a List module. Would you like that ?
> >> (that's what we are forced to do when using Map and that's why
> >> I always use Hashtbl instead).
> >
> > Humorously enough, I'm doing exactly this.  In a bunch of code I'm
> > playing with, I've implemented an NeList module- nothing fancy, just a
> > few dozen lines of code and the basic list operations, only the lists
> > can not be empty.  They always have to contain at least one element.
> >
> > But seriously, you hate functors that much?
>
> With a passion :) I don't like functors for generic data structures
> such as Map.
>
> If you have some code that you want to parametrize over multiple types,
> and each of this type has some complex constraints, then I like functors.

Exactly.

> But when the only constraints on your type is that you want a Ord, or a Eq
> (or a Show), then I think functors are overkill,

Yes.

> and I am fine with the default Pervasives.compare

No, that is really error prone.

You want "compare" to run-time dispatch to the appropriate comparison function 
(e.g. Set.compare) when it hits a reference type.

> In a similar way, you have some complex code polymorphic in a 'a
> and at some point, deep inside a call chain, you want to print
> some debugging information about this tiny 'a,  so you really
> want to do a      generic_print x, but you can not.
> Or if you want to do that you have to turn that into a functor
> taking a T where the T is contrained to have a 'print' method/function.
> With haskell you just write 'show x', and haskell inference will
> do the work to add the Show a =>. So right now in OCaml
> I tend to use the Dumper module of Richard Jones. When I can
> avoid functors, I do so.

Right. Generic printing in HLVM is nice. :-)

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 20:49:14 Yoann Padioleau wrote:
> Jon Harrop <jon@ffconsultancy.com> writes:
> > On Wednesday 04 March 2009 16:48:18 Yoann Padioleau wrote:
> >> I don't think so. I've read the last "history of C++" by Stroustrup
> >> in HOPL-III, who discusses quite a lot about the STL and Stepanov,
> >> and from what I remember unboxing was a big issue
> >> and having "generic" (which is slightly different from polymorphic)
> >> algorithms without introducing performance
> >> penalty that object-solution has with dynamic dispatch was also
> >> a big issue. Those people are not stupid.
> >
> > If they were not stupid, why were their innovations were dropped, e.g.
> > Java, C# and even VB.NET
>
> First, who cares about Java or C# or VB.NET?

About 60% of all professional developers.

> Last time I checked, 
> all the software I use on my machine (linux, mozilla, apache, mysql, emacs,
> X-windows, gtk, gnome, git, transmission, ...) are written in
> C and sometimes C++ (well except the beautiful ocamlopt and ocamldebug).

Of course, most of those programs predate .NET.

> >From what I know, most Microsoft software are still written in C++
>
> (Office, Visual Studio, the kernel, etc), and most Apple software
> too (with sometimes some objective C stuff). Do we have an example
> of a Java killer-app ?

Does Java need a killer app?

> > provide parametric polymorphism from ML (aka generics)
> > instead of C++ templates?
>
> But haven't they added generics in Java because Java programmers
> wanted some of the capabilities of C++ templates ? They even
> use its syntax, and recent Java has added some ugly extensions
> with some star-stuff around it that I don't understand. So I think
> Java generics are closer to C++ templates than ML parametric polymorphism
> and its inference.

Java's generics were by Wadler (Haskell) and Odersky (Scala) and .NET's 
generics were by Syme (F#). They all followed ML and not C++.

> And Java has decided to not follow C++ on many things, they also
> don't have overloading...

Java has overloading but not overloaded operators.

> >> They know about ML.
> >
> > IIRC Alex Stepanov claimed to know ML but then made a series of factually
> > incorrect statements about it, e.g. "phantom types do not exist".
>
> I know ML and I don't know those phantom types thing. And if they are
> "phantom", isn't he right indeed that they do not actually exist?

No. :-)

> Do ML designers really know C++ and all its lastest features too
> as in C++0x ?

The designers of ML obviously didn't know any C++ because they designed ML 
before C++ had been invented. I'm not sure there is much for anyone to learn 
from C++98/C++03/C++0x. They are just flogging a dead horse.

> > His published work includes nothing on anything related to ML:
> >
> >   http://www.stepanovpapers.com/
> >
> > I do not believe they knew about ML.
>
> I think at least Stroustrup mentions in its "the design and
> evolution of C++" book some comparisons with ML.
> But probably at that time ML didn't
> have yet the functor stuff, just the parametric polymorphism.

Stroustrup may well have not known about functors when he was designing C++ 
but not being familiar with parametric polymorphism was silly.

> > I've learned about 20
> > programming languages now and every one taught me something new. C++
> > taught me what happens when you let idiots loose on programming language
> > design and get industry to hype the result regardless of its objective
> > value.
>
> C++ taught me that if you want to be really successful, you need a
> migration path (or you need to wait for old programmers to die or that a
> very different kind of platform arrives so that legacy code
> does not matter any more, e.g. the web).

Indeed. Which raises the question of how I should put an OCaml front end onto 
HLVM...

> > I'm very happy to see C++ dying.
>
> Is it ?

Yes.

> >> > Scripting languages were not so hot at the time, short of Perl, but
> >> > Ruby would easily fit well into the STL idea, just like Lisp also did.
> >>
> >> No, because of the performance penalty of dispatch. Again, those C++
> >> designer guys have strong requirments on performance.
> >
> > Their performance requirements were: destroy the performance of anything
> > we are not familiar with in order to preserve the performance of familiar
> > features
> > regardless of the relative merits of the different approaches. That
> > is really stupid and very counter productive, of course.
>
> Did Stroustrup did that? I never saw Stroustrup criticizing
> other languages (but I've seend many Java people trashing C++).

Stepanov, IIRC, gave a list of languages that he claimed were incapable and 
was wrong. I would not trust his opinion on such matters and consider C++ to 
be more of a get-rich-quick scam than a valuable constribution to 
programming. C++ is one of the few languages I would advise people to not 
bother learning.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Wednesday 04 March 2009 23:18:21 Pal-Kristian Engstad wrote:
> Jon Harrop wrote:
> > C++'s job market share has fallen 50% in 4 years here in the UK:
> >
> >   http://www.itjobswatch.co.uk/jobs/uk/c++.do
>
> Sure -- those are probably not jobs that require performance, nor have
> resource constraints.

I do not believe that C++ is significantly faster or better at handling 
resources than higher-level languages.

> >> Here are some reasons:
> >>
> >>     * Most high-level languages decide the format of your data for you.
> >>       This is good for most things, but if a large part of your
> >>       application needs specific data layouts, then you are out of luck.
> >
> > That is not true for all high-level languages (e.g. .NET languages convey
> > low-level data representations and XNA uses them directly) and it is a
> > dominant concern for only a tiny number of applications.
>
> I did say most. By the way, XNA is a toy. A good toy, but a toy,
> nonetheless.

Note the irony that games are toys. :-)

> >>     * Most high-level languages can not support multiple forms of data
> >>       allocations. Some applications need a range of allocation
> >>       strategies, ranging from completely automatic (garbage collection)
> >>       to completely manual.
> >
> > C++ cannot provide efficient automatic GC.
>
> That's not true. We run GC on all of our game tasks. It's "manual"-ish,
> but doable.

If it is "manual-ish" then it is not automatic!

> >>     * Most high-level environments do not allow for fine-grained control
> >>       of computing resources, e.g. soft real-time guarantees.
> >
> > Many high-level languages make it easier to satisfy soft
> > real-time "guarantees", e.g. incremental collection vs destructor
> > avalanches.
>
> Call me cynical, but I simply don't buy it.

I found that when porting Smoke from C++ to OCaml. The worst case performance 
(which was the problem) got 5x faster in OCaml because the GC did the 
incremental work that I never managed to get my STL allocators to do 
effectively. I realised I was just Greenspunning what modern languages 
already had and that prompted me to drop C++.

> >>     * Most high-level languages do not allow for C/C++ intrinsics, for
> >>       instance leveraging access to the SSE registers.
> >
> > That is easily resolved if it is not already present (which it is in Mono
> > and LLVM already).
>
> Indeed. But then there are target specific control registers, timers,
> etc. etc. Usually, these are not supported well.

So C++ has legacy support for them but they change as hardware evolves and 
there is no reason why VMs cannot also support them.

> >>     * Most high-level languages do not allow for fine-grained control,
> >>       for instance allowing different forms of threading mechanisms.
> >
> > F# offers the .NET thread pool, asynchronous workflows and wait-free
> > work-stealing queues from the TPL. What more do you want? :-)
>
> Well, first of all - something that doesn't suck performance wise. And
> it is essential that it works on non-Intel platforms. F# is indeed
> promising, but again - I would not use it for performance critical code
> - which is about 30-50% of a game's code base.

Those are quite tame requirements, IMHO. I'd recommend Cilk.

> >> Of course, you can always say that you can use the foreign function
> >> interface, but then you lose inlining and speed.
> >
> > The same is true of C/C++. You can get much better performance from
> > assembler but calling assembler from C or C++ not only costs inlining and
> > speed but even functionality because you have an ABI to conform to.
>
> This is not true. Pretty much all C++ compilers have both intrinsic and
> inline assembly support.

Ok but that is not specific to C++.

> >> More importantly, you end up with a project with several different
> >> languages. That is generally a very bad idea.
> >
> > A common language run-time is the right solution, not C/C++.
>
> That is exactly my point. It needs to be *one* language that can cover
> the broad base from non-performance critical AI code to performance
> critical culling, animation and physics code.

A common intermediate representation shared between different front-end 
languages would suffice.

> But the sad fact is that 
> there is no competitor to C++. Mind you - I *want* to have something
> else - it is just not feasible.

I really don't see why. For example, surely OCaml+LLVM beats C++ in every way 
that you have described.

Moreover, something like my HLVM, which is specifically designed for 
high-performance computing, should make that vastly easier than C++. It even 
supports features like optional GC because my GC is written in my IR (and I 
don't want to GC my GC ;-).

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Pal-Kristian Engstad]

Jon Harrop wrote:
> On Wednesday 04 March 2009 23:18:21 Pal-Kristian Engstad wrote:
>   
>> Sure -- those are probably not jobs that require performance, nor have
>> resource constraints.
>>     
>
> I do not believe that C++ is significantly faster or better at handling 
> resources than higher-level languages.
>   
Have you ever tried to conform to a specific memory layout? We are often 
talking directly to hardware, and in those cases it is a prerequisite to 
be able to produce data that is in the exact format prescribed. Often 
these things are, put an 17-bit ID followed by a 3-bit CODE followed by 
a 12-bit LENGTH field, after which follows LENGTH items each of size 
that is some-function-of CODE.

This is usually not a problem when a small part of your data needs to be 
described this way, but when a large portion of your data needs this 
formatting, you can see that OCaml or Haskell records simply doesn't 
work very well.

>> I did say most. By the way, XNA is a toy. A good toy, but a toy,
>> nonetheless.
>>     
>
> Note the irony that games are toys. :-)
>   
For the consumer, yes, games are toys. Making games (as well as toys) is 
quite a different story. We're talking multi-million dollar projects here.
>>>>     * Most high-level languages can not support multiple forms of data
>>>>       allocations. Some applications need a range of allocation
>>>>       strategies, ranging from completely automatic (garbage collection)
>>>>       to completely manual.
>>>>         
>>> C++ cannot provide efficient automatic GC.
>>>       
>> That's not true. We run GC on all of our game tasks. It's "manual"-ish,
>> but doable.
>>     
>
> If it is "manual-ish" then it is not automatic!
>   
It is automatic in the sense that it garbage collects automatically at a 
specific time in the frame. It is manual in the sense that you have to 
annotate pointers and other reference like things (e.g. indexes).

>>>>     * Most high-level environments do not allow for fine-grained control
>>>>       of computing resources, e.g. soft real-time guarantees.
>>>>         
>>> Many high-level languages make it easier to satisfy soft
>>> real-time "guarantees", e.g. incremental collection vs destructor
>>> avalanches.
>>>       
>> Call me cynical, but I simply don't buy it.
>>     
>
> I found that when porting Smoke from C++ to OCaml. The worst case performance 
> (which was the problem) got 5x faster in OCaml because the GC did the 
> incremental work that I never managed to get my STL allocators to do 
> effectively. I realised I was just Greenspunning what modern languages 
> already had and that prompted me to drop C++.
>   
It is fairly rare for us to use STL (at least for the run-time portion 
of a game), probably for the reason that you mention. We tend to make 
algorithms and data-structures targeted for the use case.

>> Indeed. But then there are target specific control registers, timers,
>> etc. etc. Usually, these are not supported well.
>>     
>
> So C++ has legacy support for them but they change as hardware evolves and 
> there is no reason why VMs cannot also support them.
>   
True. But do they? Usually not. It is forgotten, deemed a non-important 
thing. The thing is, when you /need/ a hardware specific feature, there 
is usually no out. That was what I was trying to address.

>> Well, first of all - something that doesn't suck performance wise. And
>> it is essential that it works on non-Intel platforms. F# is indeed
>> promising, but again - I would not use it for performance critical code
>> - which is about 30-50% of a game's code base.
>>     
>
> Those are quite tame requirements, IMHO. I'd recommend Cilk.
>   
Cilk supports programming multi-threaded applications on shared-memory 
multiprocessors. That doesn't seem to be applicable to the CELL/SPU 
architecture, for instance. However, I will investigate it further.
>>>> Of course, you can always say that you can use the foreign function
>>>> interface, but then you lose inlining and speed.
>>>>         
>>> The same is true of C/C++. You can get much better performance from
>>> assembler but calling assembler from C or C++ not only costs inlining and
>>> speed but even functionality because you have an ABI to conform to.
>>>       
>> This is not true. Pretty much all C++ compilers have both intrinsic and
>> inline assembly support.
>>     
>
> Ok but that is not specific to C++.
>   
Just another thing that language developers "forget" on the way.

>>>> More importantly, you end up with a project with several different
>>>> languages. That is generally a very bad idea.
>>>>         
>>> A common language run-time is the right solution, not C/C++.
>>>       
>> That is exactly my point. It needs to be *one* language that can cover
>> the broad base from non-performance critical AI code to performance
>> critical culling, animation and physics code.
>>     
>
> A common intermediate representation shared between different front-end 
> languages would suffice.
>   
Are you talking about JIT? Unfortunately, for most consoles you are not 
allowed to write to code-pages, which precludes JIT. Everything must be 
pre-compiled to assembly.

>> But the sad fact is that 
>> there is no competitor to C++. Mind you - I *want* to have something
>> else - it is just not feasible.
>>     
>
> I really don't see why. For example, surely OCaml+LLVM beats C++ in every way 
> that you have described.
>   
LLVM is very interesting indeed, and would be my preferred back-end.
> Moreover, something like my HLVM, which is specifically designed for 
> high-performance computing, should make that vastly easier than C++. It even 
> supports features like optional GC because my GC is written in my IR (and I 
> don't want to GC my GC ;-).
>   
Nice... :-) When will you release your first version?

PKE.

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.

Re: stl?

[Stefan Monnier]

> Less than it might seem.  First of all, you have the allocation costs to
> hold the new vector- there's 3-5 clocks right there.  Let's say the vectors
> are 3 elements long.  So you have six loads and three stores- 
> assume stores are free, and loads cost 1 clock apeice- they're in L1 cache,
> and they're getting preloaded.  Plus the 3 clocks for the floating point
> adds.  So that's 12-15 clock cycles right there.  Say I'm being pessimistic
> by a factor of 2, and it's really only 6-8 clock cycles.  Vr.s 10 clock
> cycles or so for the call via functor.  Now we're down into the realm of
> only doubling the cost of the operation, not an order of magnitude increase.
> A single mispredicted branch or L1 cache miss that has to go out to L2
> cache- not even main memory, just L2!- would blow the overhead of calling
> via functor out of the water.

This presumes that the indirect function call only happens once
per vector.  But it may very well be once per vector plus once
per element (think of parameterizing list traversal over `map': since
it's abstracted, not only is the call to `map' indirect, but map's own
calls to the loop body are indirect as well).


        Stefan

Re: [Caml-list] stl?

[Jon Harrop]

On Thursday 05 March 2009 02:15:20 Pal-Kristian Engstad wrote:
> Jon Harrop wrote:
> > On Wednesday 04 March 2009 23:18:21 Pal-Kristian Engstad wrote:
> >> Sure -- those are probably not jobs that require performance, nor have
> >> resource constraints.
> >
> > I do not believe that C++ is significantly faster or better at handling
> > resources than higher-level languages.
>
> Have you ever tried to conform to a specific memory layout? We are often
> talking directly to hardware, and in those cases it is a prerequisite to
> be able to produce data that is in the exact format prescribed. Often
> these things are, put an 17-bit ID followed by a 3-bit CODE followed by
> a 12-bit LENGTH field, after which follows LENGTH items each of size
> that is some-function-of CODE.
>
> This is usually not a problem when a small part of your data needs to be
> described this way, but when a large portion of your data needs this
> formatting, you can see that OCaml or Haskell records simply doesn't
> work very well.

I agree with the symptoms but not with C++ as the treatment. Granted you 
cannot write such code directly in OCaml or Haskell but you can generate the 
code using tools like LLVM without losing the benefits of high-level 
programming and I definitely prefer that to writing C++ by hand.

> >> That's not true. We run GC on all of our game tasks. It's "manual"-ish,
> >> but doable.
> >
> > If it is "manual-ish" then it is not automatic!
>
> It is automatic in the sense that it garbage collects automatically at a
> specific time in the frame. It is manual in the sense that you have to
> annotate pointers and other reference like things (e.g. indexes).

Ok, if you're doing the annotations by hand then it is not automatic memory 
management IMHO.

> > I found that when porting Smoke from C++ to OCaml. The worst case
> > performance (which was the problem) got 5x faster in OCaml because the GC
> > did the incremental work that I never managed to get my STL allocators to
> > do effectively. I realised I was just Greenspunning what modern languages
> > already had and that prompted me to drop C++.
>
> It is fairly rare for us to use STL (at least for the run-time portion
> of a game), probably for the reason that you mention. We tend to make
> algorithms and data-structures targeted for the use case.

Yes, I'm not surprised.

> >> Indeed. But then there are target specific control registers, timers,
> >> etc. etc. Usually, these are not supported well.
> >
> > So C++ has legacy support for them but they change as hardware evolves
> > and there is no reason why VMs cannot also support them.
>
> True. But do they? Usually not. It is forgotten, deemed a non-important
> thing. The thing is, when you /need/ a hardware specific feature, there
> is usually no out. That was what I was trying to address.

I see. Yes, definitely sounds like you need an extensible performant 
high-level language implementation.

> >> Well, first of all - something that doesn't suck performance wise. And
> >> it is essential that it works on non-Intel platforms. F# is indeed
> >> promising, but again - I would not use it for performance critical code
> >> - which is about 30-50% of a game's code base.
> >
> > Those are quite tame requirements, IMHO. I'd recommend Cilk.
>
> Cilk supports programming multi-threaded applications on shared-memory
> multiprocessors. That doesn't seem to be applicable to the CELL/SPU
> architecture, for instance. However, I will investigate it further.

I have no idea about CELL/SPU, sorry.

> >> This is not true. Pretty much all C++ compilers have both intrinsic and
> >> inline assembly support.
> >
> > Ok but that is not specific to C++.
>
> Just another thing that language developers "forget" on the way.

I'll keep that in mind...

> >>>> More importantly, you end up with a project with several different
> >>>> languages. That is generally a very bad idea.
> >>>
> >>> A common language run-time is the right solution, not C/C++.
> >>
> >> That is exactly my point. It needs to be *one* language that can cover
> >> the broad base from non-performance critical AI code to performance
> >> critical culling, animation and physics code.
> >
> > A common intermediate representation shared between different front-end
> > languages would suffice.
>
> Are you talking about JIT? Unfortunately, for most consoles you are not
> allowed to write to code-pages, which precludes JIT. Everything must be
> pre-compiled to assembly.

It doesn't need to be a JIT and, actually, HLVM already supports both JIT and 
standalone compilation.

> >> But the sad fact is that
> >> there is no competitor to C++. Mind you - I *want* to have something
> >> else - it is just not feasible.
> >
> > I really don't see why. For example, surely OCaml+LLVM beats C++ in every
> > way that you have described.
>
> LLVM is very interesting indeed, and would be my preferred back-end.

Takes a lot of learning but LLVM is awesome once you've got to grips with it. 
I'm hoping my high-level interface can take a lot of the pain out of using 
it...

> > Moreover, something like my HLVM, which is specifically designed for
> > high-performance computing, should make that vastly easier than C++. It
> > even supports features like optional GC because my GC is written in my IR
> > (and I don't want to GC my GC ;-).
>
> Nice... :-) When will you release your first version?

I'm just writing the GC now and then I'll release a first version.

I'm hoping JLouis can make a MosML front end quickly. ;-)

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[yoann padioleau]

> On Thursday 05 March 2009 02:15:20 Pal-Kristian Engstad wrote:
> > Jon Harrop wrote:
> > > On Wednesday 04 March 2009 23:18:21 Pal-Kristian Engstad wrote:
> > >> Sure -- those are probably not jobs that require performance, nor have
> > >> resource constraints.
> > >
> > > I do not believe that C++ is significantly faster or better at handling
> > > resources than higher-level languages.
> >
> > Have you ever tried to conform to a specific memory layout? We are often
> > talking directly to hardware, and in those cases it is a prerequisite to
> > be able to produce data that is in the exact format prescribed. Often
> > these things are, put an 17-bit ID followed by a 3-bit CODE followed by
> > a 12-bit LENGTH field, after which follows LENGTH items each of size
> > that is some-function-of CODE.
> >
> > This is usually not a problem when a small part of your data needs to be
> > described this way, but when a large portion of your data needs this
> > formatting, you can see that OCaml or Haskell records simply doesn't
> > work very well.
> 
> I agree with the symptoms but not with C++ as the treatment. Granted you 
> cannot write such code directly in OCaml or Haskell but you can generate the 
> code using tools like LLVM 

Come on, can you stop all those stuff about LLVM. The guy works in a game company
with people knowing C/C++ for decades, with quite a lot of legacy code I guess, and you
arrive with your "hey you should use LLVM" that almost nobody knows about. 

Oh, and by the way, in which programming language is written LLVM ? :) 

Valgrind is written in C (and julien seward, its author knows very well 
Haskell), Qemu is written in C, because I guess indeed C struct and union
and bitfields makes it easy to match directly to the hardware (no marshalling,
there is direct mapping).


> It doesn't need to be a JIT and, actually, HLVM already supports both JIT and 
> standalone compilation.

So what you propose to his company is to switch from C++ to HLVM ? :) 
Be serious. 

Re: [Caml-list] stl?

[Raoul Duke]

> So what you propose to his company is to switch from C++ to HLVM ? :)
> Be serious.

there are some things out there that interface with c/++ but which
themselves aren't. e.g. http://felix.sourceforge.net/ (although the
last release date was 2006, it apparently still is under active
development.) as a random not entirely serious factoid.

sincerely.

Re: [Caml-list] stl?

[Erick Tryzelaar]

On Wed, Mar 4, 2009 at 11:02 PM, Raoul Duke <raould@gmail.com> wrote:
>> So what you propose to his company is to switch from C++ to HLVM ? :)
>> Be serious.
>
> there are some things out there that interface with c/++ but which
> themselves aren't. e.g. http://felix.sourceforge.net/ (although the
> last release date was 2006, it apparently still is under active
> development.) as a random not entirely serious factoid.

Yep, felix is still under active development, we've just been
busy/lazy and haven't cut a release yet. Our mailing lists are still
active.

We actually compile to c++, and then let the c++ compiler assemble the
code for us. The development has a ton of new features, like garbage
collection using judy arrays, and user extendable grammar. We're
exploring compiling straight to llvm, but that's a ways off. If we do
go that route, we'd try to preserve the ease of hooking into c and c++
libraries, but use llvm hooks to make the c/c++ call for us.

Re: [Caml-list] stl?

[Kuba Ober]

>
>> Of course, you can always say that you can use the foreign function
>> interface, but then you lose inlining and speed.
>
> The same is true of C/C++. You can get much better performance from  
> assembler
> but calling assembler from C or C++ not only costs inlining and  
> speed but
> even functionality because you have an ABI to conform to.

gcc can and does inline user functions written in assembly, as long as  
they
are wrapped in a C function. It's pretty nice in that respect, actually.

Cheers, Kuba

Re: [Caml-list] stl?

[Richard Jones]

On Wed, Mar 04, 2009 at 06:15:20PM -0800, Pal-Kristian Engstad wrote:
> Have you ever tried to conform to a specific memory layout? We are often 
> talking directly to hardware, and in those cases it is a prerequisite to 
> be able to produce data that is in the exact format prescribed. Often 
> these things are, put an 17-bit ID followed by a 3-bit CODE followed by 
> a 12-bit LENGTH field, after which follows LENGTH items each of size 
> that is some-function-of CODE.

This is the sort of thing that OCaml-bitstring might be adapted to do.
Now I'm not going to claim that bitstring does this already, because
there is no way it's currently as fast as C/C++ (it involves a copy
for a start).  But a similar language extension might make it
possible.

  http://code.google.com/p/bitstring/

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[Richard Jones]

On Thu, Mar 05, 2009 at 07:22:28AM +0100, yoann padioleau wrote:
> Qemu is written in C, because I guess indeed C struct and union
> and bitfields makes it easy to match directly to the hardware (no marshalling,
> there is direct mapping).

I was hacking on qemu last week, and wishing it wasn't written in C.

There's not much of a technical reason why it couldn't have been
written in a higher level language.  Bitfield manipulation would be
more painful unless there was a bitstring-like preprocessor added.

The real reason to use C was to get wider development support.  Qemu
also happens to be security critical (all those hacked up C device
emulations offer exploit possibilities for the guests).  And it has
frequent vulnerabilities.  Go figure ...

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[Richard Jones]

On Thu, Mar 05, 2009 at 01:06:34AM +0000, Jon Harrop wrote:
> Indeed. Which raises the question of how I should put an OCaml front
> end onto HLVM...

Use the output of camlp4 (the AST).  It's reasonably well documented
in the camlp4 wiki.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[malc]

On Thu, 5 Mar 2009, Richard Jones wrote:

> On Thu, Mar 05, 2009 at 07:22:28AM +0100, yoann padioleau wrote:
> > Qemu is written in C, because I guess indeed C struct and union
> > and bitfields makes it easy to match directly to the hardware (no marshalling,
> > there is direct mapping).
> 
> I was hacking on qemu last week, and wishing it wasn't written in C.

I'm genuinely curious as to what part of QEMU being not written in C
would have been a net win..

> 
> There's not much of a technical reason why it couldn't have been
> written in a higher level language.  Bitfield manipulation would be
> more painful unless there was a bitstring-like preprocessor added.
>
> The real reason to use C was to get wider development support.  Qemu
> also happens to be security critical (all those hacked up C device
> emulations offer exploit possibilities for the guests).  And it has
> frequent vulnerabilities.  Go figure ...

I'm sorry, but i don't see how writing device emulation in OCaml would
have made it automatically safer.

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] stl?

[Richard Jones]

On Thu, Mar 05, 2009 at 12:34:54PM +0300, malc wrote:
> On Thu, 5 Mar 2009, Richard Jones wrote:
> 
> > On Thu, Mar 05, 2009 at 07:22:28AM +0100, yoann padioleau wrote:
> > > Qemu is written in C, because I guess indeed C struct and union
> > > and bitfields makes it easy to match directly to the hardware (no marshalling,
> > > there is direct mapping).
> > 
> > I was hacking on qemu last week, and wishing it wasn't written in C.
> 
> I'm genuinely curious as to what part of QEMU being not written in C
> would have been a net win..

I'm not saying we should rewrite QEMU, but using a higher level
language would mean the code was shorter and easier to understand.

Just to take some examples from how my latest patch[1] would have been
shorter and easier to reason about:

- Could represent manpage & command line arguments in a self-documenting
  literate format, eg. Perl's perldoc + Pod::Usage

- Lists of structures are much simpler to represent and iterate over
  in functional languages.

- Parsing the command line is a lot simpler when you don't have to
  worry about manual string allocation and you have high level features
  like regexps, split, etc.

- Unnecessary initialization of structures could be removed.

- Serialization of watchdog structure could have been done automatically
  (eg. by something like sexplib)

And for balance some things that C is better at:

- (Possibly) handling 32 and 64 bit quantities.

- (Possibly) bit manipulation.

Although I'm not convinced that we couldn't do better using pa_do and
some sort of enhanced bitstring syntax extension.

And of course:

- Unlimited number of monkeys to write code (see below).

> > There's not much of a technical reason why it couldn't have been
> > written in a higher level language.  Bitfield manipulation would be
> > more painful unless there was a bitstring-like preprocessor added.
> >
> > The real reason to use C was to get wider development support.  Qemu
> > also happens to be security critical (all those hacked up C device
> > emulations offer exploit possibilities for the guests).  And it has
> > frequent vulnerabilities.  Go figure ...
> 
> I'm sorry, but i don't see how writing device emulation in OCaml would
> have made it automatically safer.

CVE-2008-0928:
| Qemu 0.9.1 and earlier does not perform range checks for block device
| read or write requests, which allows guest host users with root
| privileges to access arbitrary memory and escape the virtual machine.

CVE-2008-1945
| QEMU 0.9.0 does not properly handle changes to removable media, which allows
| guest OS users to read arbitrary files on the host OS by using the
| diskformat: parameter in the -usbdevice option to modify the disk-image
| header to identify a different format, a related issue to CVE-2008-2004.
(Arguable whether this one is really about C, but a safe extension
like bitstring would have prevented it).

CVE-2007-1320
| The cirrus_invalidate_region() routine used during video-to-video copy
| operations in the cirrus vga extension code omits bounds checking in
| multiple locations, allowing you to overwrite adjacent buffers by
| attempting to mark non-existent regions as dirty. Successful
| exploitation would result in a complete compromise of the qemu
| process. Additionally multiple bitblt operations omit bounds checking,
| where the srcpitch or dstpitch coefficients cause the operation to
| exceed the bounds of the vram buffer.

CVE-2008-5714
| Fix off-by-one bug limiting VNC passwords to 7 chars 
(Problem in C's sizeof:
http://lists.gnu.org/archive/html/qemu-devel/2008-11/msg01224.html )

CVE-2007-1366
| QEMU 0.8.2 allows local users to crash a virtual machine via the
| divisor operand to the aam instruction, as demonstrated by aam 0x0,
| which triggers a divide-by-zero error.

CVE-2007-6227
| QEMU 0.9.0 allows local users of a Windows XP SP2 guest operating
| system to overwrite the TranslationBlock (code_gen_buffer) buffer,
| and probably have unspecified other impacts related to an overflow,
| via certain Windows executable programs, as demonstrated by
| qemu-dos.com.

CVE-2008-2004
| The drive_init function in QEMU 0.9.1 determines the format of
| a raw disk image based on the header, which allows local guest
| users to read arbitrary files on the host by modifying the header
| to identify a different format, which is used when the guest is
| restarted.

Those are just from the results of the first page of Google "qemu CVE".

Rich.

[1] http://lists.gnu.org/archive/html/qemu-devel/2009-02/txtzqRjC0boEM.txt

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[malc]

On Thu, 5 Mar 2009, Richard Jones wrote:

> On Thu, Mar 05, 2009 at 12:34:54PM +0300, malc wrote:
> > On Thu, 5 Mar 2009, Richard Jones wrote:
> > 
> > > On Thu, Mar 05, 2009 at 07:22:28AM +0100, yoann padioleau wrote:
> > > > Qemu is written in C, because I guess indeed C struct and union
> > > > and bitfields makes it easy to match directly to the hardware (no marshalling,
> > > > there is direct mapping).
> > > 
> > > I was hacking on qemu last week, and wishing it wasn't written in C.
> > 
> > I'm genuinely curious as to what part of QEMU being not written in C
> > would have been a net win..
> 
> I'm not saying we should rewrite QEMU, but using a higher level
> language would mean the code was shorter and easier to understand.
> 
> Just to take some examples from how my latest patch[1] would have been
> shorter and easier to reason about:
> 
> - Could represent manpage & command line arguments in a self-documenting
>   literate format, eg. Perl's perldoc + Pod::Usage

Yes.
 
> - Lists of structures are much simpler to represent and iterate over
>   in functional languages.

You lost me here.
 
> - Parsing the command line is a lot simpler when you don't have to
>   worry about manual string allocation and you have high level features
>   like regexps, split, etc.

Yes.
 
> - Unnecessary initialization of structures could be removed.

Lost again.
 
> - Serialization of watchdog structure could have been done automatically
>   (eg. by something like sexplib)
> 
> And for balance some things that C is better at:
> 
> - (Possibly) handling 32 and 64 bit quantities.

Not possibly, definitely (in case of better being applied to current
implementation of OCaml)

> - (Possibly) bit manipulation.

Again.
 
> Although I'm not convinced that we couldn't do better using pa_do and
> some sort of enhanced bitstring syntax extension.
> 
> And of course:
> 
> - Unlimited number of monkeys to write code (see below).
> 
> > > There's not much of a technical reason why it couldn't have been
> > > written in a higher level language.  Bitfield manipulation would be
> > > more painful unless there was a bitstring-like preprocessor added.
> > >
> > > The real reason to use C was to get wider development support.  Qemu
> > > also happens to be security critical (all those hacked up C device
> > > emulations offer exploit possibilities for the guests).  And it has
> > > frequent vulnerabilities.  Go figure ...
> > 
> > I'm sorry, but i don't see how writing device emulation in OCaml would
> > have made it automatically safer.
> 
> CVE-2008-0928:
> | Qemu 0.9.1 and earlier does not perform range checks for block device
> | read or write requests, which allows guest host users with root
> | privileges to access arbitrary memory and escape the virtual machine.

I don't see how C per se is at fault here.
 
> CVE-2008-1945
> | QEMU 0.9.0 does not properly handle changes to removable media, which allows
> | guest OS users to read arbitrary files on the host OS by using the
> | diskformat: parameter in the -usbdevice option to modify the disk-image
> | header to identify a different format, a related issue to CVE-2008-2004.
> (Arguable whether this one is really about C, but a safe extension
> like bitstring would have prevented it).

Indeed.
 
> CVE-2007-1320
> | The cirrus_invalidate_region() routine used during video-to-video copy
> | operations in the cirrus vga extension code omits bounds checking in
> | multiple locations, allowing you to overwrite adjacent buffers by
> | attempting to mark non-existent regions as dirty. Successful
> | exploitation would result in a complete compromise of the qemu
> | process. Additionally multiple bitblt operations omit bounds checking,
> | where the srcpitch or dstpitch coefficients cause the operation to
> | exceed the bounds of the vram buffer.

And again.
 
> CVE-2008-5714
> | Fix off-by-one bug limiting VNC passwords to 7 chars 
> (Problem in C's sizeof:
> http://lists.gnu.org/archive/html/qemu-devel/2008-11/msg01224.html )

The problem is not C's sizeof but the one who used it.
 
> CVE-2007-1366
> | QEMU 0.8.2 allows local users to crash a virtual machine via the
> | divisor operand to the aam instruction, as demonstrated by aam 0x0,
> | which triggers a divide-by-zero error.

Well this has nothing to do with C, which brings us to another
interesting point, division by zero is UB as per 6.5.5#5, OCaml
guarantees Division_by_zero being thrown in case of second operand
by zero and the code it generates here on PPC to provide that is
consequently suboptimal (cmp + branch per every division)
 
> CVE-2007-6227
> | QEMU 0.9.0 allows local users of a Windows XP SP2 guest operating
> | system to overwrite the TranslationBlock (code_gen_buffer) buffer,
> | and probably have unspecified other impacts related to an overflow,
> | via certain Windows executable programs, as demonstrated by
> | qemu-dos.com.
> 
> CVE-2008-2004
> | The drive_init function in QEMU 0.9.1 determines the format of
> | a raw disk image based on the header, which allows local guest
> | users to read arbitrary files on the host by modifying the header
> | to identify a different format, which is used when the guest is
> | restarted.
> 
> Those are just from the results of the first page of Google "qemu CVE".

I'm still not convinced that any of the above is due to using C and
not just being lax at pre/post condition checking.

> Rich.
> 
> [1] http://lists.gnu.org/archive/html/qemu-devel/2009-02/txtzqRjC0boEM.txt
> 
> 

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] stl?

[Richard Jones]

On Thu, Mar 05, 2009 at 01:49:01PM +0300, malc wrote:
> You lost me here.

Look at the patch I linked to [1].

> > - (Possibly) handling 32 and 64 bit quantities.
> 
> Not possibly, definitely (in case of better being applied to current
> implementation of OCaml)

I'm not sure I mentioned OCaml, just a high level language.  Anyway
you can't make an argument about low level languages being better and
then arbitrarily restrict my choice of high level language based on
your definition of "current implementation".  What does that mean?
Only things published by INRIA?  Maybe we shouldn't be allowed to use
anything but the standard library too, to make this more "fair"
towards low level languages?

> > CVE-2008-0928:
> > | Qemu 0.9.1 and earlier does not perform range checks for block device
> > | read or write requests, which allows guest host users with root
> > | privileges to access arbitrary memory and escape the virtual machine.
> 
> I don't see how C per se is at fault here.

Lack of a bounds check has _everything_ to do with C being at fault.
The fact that this allows you to try out root exploits against the
host from a guest is also everything to do with C.

http://marc.info/?l=debian-security&m=120343592917055&w=2

> > CVE-2008-5714
> > | Fix off-by-one bug limiting VNC passwords to 7 chars 
> > (Problem in C's sizeof:
> > http://lists.gnu.org/archive/html/qemu-devel/2008-11/msg01224.html )
> 
> The problem is not C's sizeof but the one who used it.

The problem is entirely with C.  These fencepost errors to do with
sizeof and strlen are frequent causes of errors in C.  How many C
programmers can honestly claim they haven't written this sort of thing
at least once in their lives:

  buf = malloc (strlen (str));
  strcpy (buf, str);

Referring back to the original patch, in a high level language it
wouldn't be necessary to pass a string + length into a function,
because in a high level language we'd assume the function can just
allocate a string of the required size.  For this password case we
would pass in the desired maximum length, so just the number '8'.
_Far_ more obvious and less error prone.

It's 2009, we shouldn't expect programmers to have to think about such
stupid low-level stuff, and we shouldn't expect reviewers to check for
it.

Do you know how expensive it is to fix these security isses?

Each one requires hundreds of man-hours building and validating
packages, and then sending them out to sysadmins at all our customers
who individually verify and install them.  This is a vast undertaking
which swamps the minute % increase in performance that C may (or even
may not) give you.

> > CVE-2007-1366
> > | QEMU 0.8.2 allows local users to crash a virtual machine via the
> > | divisor operand to the aam instruction, as demonstrated by aam 0x0,
> > | which triggers a divide-by-zero error.
> 
> Well this has nothing to do with C, which brings us to another
> interesting point, division by zero is UB as per 6.5.5#5, OCaml
> guarantees Division_by_zero being thrown in case of second operand
> by zero and the code it generates here on PPC to provide that is
> consequently suboptimal (cmp + branch per every division)

I'm not sure what your point is.  Bounds checking introduces some tiny
overhead too.  But if you don't do it, your untrusted guests can own
your hosting service.  Fair trade-off?

Rich.

[1] http://lists.gnu.org/archive/html/qemu-devel/2009-02/txtzqRjC0boEM.txt

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[Wolfgang Lux]

Brian Hurt wrote:

> [...]
> Here are two real problems I've hit with type classes, in only a  
> few weeks banging around in Haskell.
>
> For example, you can't have more than one instance of a type class  
> for any given type.  So let's say you want to have a type class for  
> things that can be converted to and from s-expressions, like:
> 	data Sexp =
> 		Atom String
> 		| List [ Sexp ]
>
> 	class Sexpable a where
> 		toSexp :: a -> Sexp
> 		fromSexp :: Sexp -> Maybe a
>
> So then you start throwing out the standard instances, among  
> others, you do one for string:
> 	instance Sexpable String where
> 		toSexp s = Atom s
> 		fromSexp (Atom s) = Just s
> 		fromSexp _ = Nothing
>
> and, a little while later, one for generic lists:
> 	instance Sexpable a => Sexpable [ a ] where
> 		toSexp xs = List $ map toSexp xs
> 		fromSexp (List xs) = mapM fromSexp xs
> 		fromSexp _ = Nothing
>
> Opps!  Now you have conflicting instances for type String- one the  
> explicit implementation, and one via the generic list.  There are  
> kludges to get around this, but they cause their own problems  
> (Brian's first law of programming: kludges multiply).  A common one  
> is to add the function toSexpList and fromSexpList to the  
> fundamental type class, and drop the generic list implementation.

Just to fair to Haskell here, you should not drop the list instance  
altogether, but rather redefine it to use the new methods.

   instance Sexpable a => Sexpable [ a ] where
     toSexp = toSexpList
     fromSexp = fromSexpList

Thus, the purported problem with Map Int ([Int], Foo) is void.

Wolfgang

Re: [Caml-list] stl?

[malc]

On Thu, 5 Mar 2009, Richard Jones wrote:

> On Thu, Mar 05, 2009 at 01:49:01PM +0300, malc wrote:
> > You lost me here.
> 
> Look at the patch I linked to [1].
> 
> > > - (Possibly) handling 32 and 64 bit quantities.
> > 
> > Not possibly, definitely (in case of better being applied to current
> > implementation of OCaml)
> 
> I'm not sure I mentioned OCaml, just a high level language.  Anyway
> you can't make an argument about low level languages being better and
> then arbitrarily restrict my choice of high level language based on
> your definition of "current implementation".  What does that mean?
> Only things published by INRIA?  Maybe we shouldn't be allowed to use
> anything but the standard library too, to make this more "fair"
> towards low level languages?

What i meant is that in current OCaml implementations overhead of
using int32/64 is very high.

> > > CVE-2008-0928:
> > > | Qemu 0.9.1 and earlier does not perform range checks for block device
> > > | read or write requests, which allows guest host users with root
> > > | privileges to access arbitrary memory and escape the virtual machine.
> > 
> > I don't see how C per se is at fault here.
> 
> Lack of a bounds check has _everything_ to do with C being at fault.
> The fact that this allows you to try out root exploits against the
> host from a guest is also everything to do with C.

Erm.. I don't agree, one can easily say that OCaml is only marginally
better than C here just because `-unsafe' is not default on OCaml and
`-fmudflap' is not in GCC (Let's be honest here QEMU is not written in
C but dialect exposed by GCC)

> http://marc.info/?l=debian-security&m=120343592917055&w=2
> 
> > > CVE-2008-5714
> > > | Fix off-by-one bug limiting VNC passwords to 7 chars 
> > > (Problem in C's sizeof:
> > > http://lists.gnu.org/archive/html/qemu-devel/2008-11/msg01224.html )
> > 
> > The problem is not C's sizeof but the one who used it.
> 
> The problem is entirely with C.  These fencepost errors to do with
> sizeof and strlen are frequent causes of errors in C.  How many C
> programmers can honestly claim they haven't written this sort of thing
> at least once in their lives:
> 
>   buf = malloc (strlen (str));
>   strcpy (buf, str);

I thought we were discussing sizeof (mis)usage.

> Referring back to the original patch, in a high level language it
> wouldn't be necessary to pass a string + length into a function,
> because in a high level language we'd assume the function can just
> allocate a string of the required size.  For this password case we
> would pass in the desired maximum length, so just the number '8'.
> _Far_ more obvious and less error prone.

I think you are confusing high levelness(whatever that might mean)
with presence/lack-of GC of some sort.

> It's 2009, we shouldn't expect programmers to have to think about such
> stupid low-level stuff, and we shouldn't expect reviewers to check for
> it.
> 
> Do you know how expensive it is to fix these security isses?

Not from the perspective of distribution maintainers.

> Each one requires hundreds of man-hours building and validating
> packages, and then sending them out to sysadmins at all our customers
> who individually verify and install them.  This is a vast undertaking
> which swamps the minute % increase in performance that C may (or even
> may not) give you.

Until something like QEMU is (re)written in high-level language you have
nothing to back that claim.

> > > CVE-2007-1366
> > > | QEMU 0.8.2 allows local users to crash a virtual machine via the
> > > | divisor operand to the aam instruction, as demonstrated by aam 0x0,
> > > | which triggers a divide-by-zero error.
> > 
> > Well this has nothing to do with C, which brings us to another
> > interesting point, division by zero is UB as per 6.5.5#5, OCaml
> > guarantees Division_by_zero being thrown in case of second operand
> > by zero and the code it generates here on PPC to provide that is
> > consequently suboptimal (cmp + branch per every division)
> 
> I'm not sure what your point is.  Bounds checking introduces some tiny
> overhead too.  But if you don't do it, your untrusted guests can own
> your hosting service.  Fair trade-off?

My point is that inefficiencies like this do add up, other (weak) point
is that in OCaml you can't even opt-out of (some) checks even if you
have solid proof that, for instance,  division by zero is impossible.

I also think that device emulation would have been quite cumbersome
in OCaml (Sorry for constantly refering to OCaml, but we are in
dedicated mailing-list and i think thats the only language you
would deem high-level and at the same time i happen to know to
some degree)

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] stl?

[Raoul Duke]

> This is the sort of thing that OCaml-bitstring might be adapted to do.

ditto lisp "bit vectors"? still, seems sorta not close enough.

Re: [Caml-list] stl?

[Jon Harrop]

On Thursday 05 March 2009 06:22:28 yoann padioleau wrote:
> Come on, can you stop all those stuff about LLVM. The guy works in a game
> company with people knowing C/C++ for decades, with quite a lot of legacy
> code I guess, and you arrive with your "hey you should use LLVM" that
> almost nobody knows about.

Then they should learn about it. LLVM is already capable of generating SSE 
instructions from higher-level code more effectively than GCC and, 
consequently, several of my benchmarks run 2-4x faster than GCC-compiled C.

> Oh, and by the way, in which programming language is written LLVM ? :)

Sure. That doesn't mean we shouldn't build upon LLVM.

> > It doesn't need to be a JIT and, actually, HLVM already supports both JIT
> > and standalone compilation.
>
> So what you propose to his company is to switch from C++ to HLVM ? :)
> Be serious.

I suggest they consider using LLVM, most likely from their C++ to begin with. 
This is a low barrier to entry: they can just compile their C++ using 
llvm-gcc and write custom passes that perform the optimizations they want. 
That is ideal for applications that are willing to sacrifice numerical 
robustness for performance, for example.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jon Harrop]

On Thursday 05 March 2009 09:09:14 Richard Jones wrote:
> On Thu, Mar 05, 2009 at 01:06:34AM +0000, Jon Harrop wrote:
> > Indeed. Which raises the question of how I should put an OCaml front
> > end onto HLVM...
>
> Use the output of camlp4 (the AST).  It's reasonably well documented
> in the camlp4 wiki.

I can parse it easily enough. The type inference and checking is the hard 
part. I'm afraid that OCaml's current implementation might not be very useful 
in that respect anyway if it removes types too soon and makes assumptions 
about the run-time representation.

Perhaps the output of -dlambda would be suitable:

$ cat >a.ml
type t = A of int | B of int | C of int;;
function A n -> n | B n -> 1+n | C n -> 2+n;;
$ ocamlc -dlambda a.ml -o a 2>a.lambda
$ cat a.lambda
(setglobal A!
  (seq
    (function param/72
      (switch* param/72
       case tag 0: (field 0 param/72)
       case tag 1: (+ 1 (field 0 param/72))
       case tag 2: (+ 2 (field 0 param/72))))
    (makeblock 0)))

Is this format documented anywhere?

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Jake Donham]

On Thu, Mar 5, 2009 at 12:44 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> Is this [the lambda IL] format documented anywhere?

The ocamljs backend compiles Javascript from the lambda intermediate
language. I haven't found documentation of it, but most of it is
pretty easy to understand (a few things I've had to track down by
seeing what they compile to in bytecode). You might find the
Javascript translation a useful guide, but of course don't take it as
the final word.

You are right though that it makes some assumptions about the runtime
representation and has already erased types. It is (obviously) good
enough to be a shared IL for the bytecode and opt backends; it is
mostly good enough for ocamljs (there are some places where I wish I
knew more about the type of things); I can't say what your needs are
with LLVM.

Still it is probably a better starting point than trying to
reimplement the OCaml front-end.

Jake

Re: [Caml-list] stl?

[Pal-Kristian Engstad]

yoann padioleau wrote:
> Come on, can you stop all those stuff about LLVM. The guy works in a game company
> with people knowing C/C++ for decades, with quite a lot of legacy code I guess, and you
> arrive with your "hey you should use LLVM" that almost nobody knows about. 
>   
Not to defend Jon too much publicly ;-), but LLVM is a serious piece of 
software that deserves a lot of attention. Trust me, we do keep an eye 
out for exciting emerging technologies.
> Oh, and by the way, in which programming language is written LLVM ? :)
>   
LLVM has already a surprising amount of language support. You should 
check it out. Another interesting project related to LLVM is Clang.
> Valgrind is written in C (and julien seward, its author knows very well 
> Haskell), Qemu is written in C, because I guess indeed C struct and union
> and bitfields makes it easy to match directly to the hardware (no marshalling,
> there is direct mapping).
>   
LLVM is very low-level and perfectly capable of handling these things.
> So what you propose to his company is to switch from C++ to HLVM ? :)
That might not be feasible due to some non-technical concerns, but I 
wouldn't say that it is completely out of the question. During the 
PlayStation 2 era, Naughty Dog used its own proprietary language called 
Goal - an imperative variant of Scheme. We very much understand that 
lack of programmer productivity is a major cost, perhaps /the/ biggest, 
for game production. Therefore, anything that helps in this regard is of 
huge interest.

Thanks,

PKE.

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Emacs would be a far better OS if it was shipped with 
 a halfway-decent text editor." -- Slashdot, Dec 13. 2005.

Re: [Caml-list] OCaml's intermediate representations

[Jon Harrop]

On Thursday 05 March 2009 20:50:58 Jake Donham wrote:
> On Thu, Mar 5, 2009 at 12:44 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> > Is this [the lambda IL] format documented anywhere?
>
> The ocamljs backend compiles Javascript from the lambda intermediate
> language. I haven't found documentation of it, but most of it is
> pretty easy to understand (a few things I've had to track down by
> seeing what they compile to in bytecode). You might find the
> Javascript translation a useful guide, but of course don't take it as
> the final word.
>
> You are right though that it makes some assumptions about the runtime
> representation and has already erased types. It is (obviously) good
> enough to be a shared IL for the bytecode and opt backends; it is
> mostly good enough for ocamljs (there are some places where I wish I
> knew more about the type of things); I can't say what your needs are
> with LLVM.
>
> Still it is probably a better starting point than trying to
> reimplement the OCaml front-end.

That's very interesting advice, thanks, but the more I play with it the more I 
think it will not satisfy my needs. Consider:

  type t = A of int | B of int | C of int;;
  function A n -> n | B n -> n | C n -> n;;

which compiles to:

  (setglobal A! (seq (function param/72 (field 0 param/72)) (makeblock 0)))

The type definition is not even there and the function definition swings 
entirely on the uniform internal representation of the field. That is 
completely incompatible with HLVM. The ocamljs backend will have an easier 
time because it will be dynamically typing everything anyway (i.e. it also 
has a uniform representation). I could do that in HLVM but the performance 
would be atrocious because everything would be boxed, of course.

I'll take a look at the pattern match compiler in OCaml and see if it is 
feasible to make it retain type information. Hopefully I can reuse some of 
this stuff. :-)

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] stl?

[Richard Jones]

On Thu, Mar 05, 2009 at 01:10:18PM -0800, Pal-Kristian Engstad wrote:
> During the PlayStation 2 era, Naughty Dog used its own proprietary
> language called Goal - an imperative variant of Scheme.

I thought I'd heard of you guys before ...

http://www.gamasutra.com/features/20020710/white_01.htm

The second and third pages discuss the pros and cons of GOAL.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] stl?

[malc]

On Thu, 5 Mar 2009, Pal-Kristian Engstad wrote:

[..snip..]

> LLVM is very low-level and perfectly capable of handling these things.
> > So what you propose to his company is to switch from C++ to HLVM ? :)
> That might not be feasible due to some non-technical concerns, but I wouldn't
> say that it is completely out of the question. During the PlayStation 2 era,
> Naughty Dog used its own proprietary language called Goal - an imperative
> variant of Scheme. We very much understand that lack of programmer
> productivity is a major cost, perhaps /the/ biggest, for game production.
> Therefore, anything that helps in this regard is of huge interest.

It was a real heartbreaker for me when after finished Uncharted i went
on to read about it, hoping to see much praise of Goal, only to find
out that Naughty Dog switched to C++

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] stl?

[Brian Hurt]

Sorry for the late reply- I was out of town over the weekend.

On Wed, 4 Mar 2009, Jon Harrop wrote:

> On Wednesday 04 March 2009 21:59:51 Brian Hurt wrote:
>> But seriously, you hate functors that much?  The overhead of doing:
>>
>> module StringMap = Map.Make(String);;
>>
>> is so high to you, that you simply don't do it?
>>
>> Mind if I ask why?
>
> Your example is fragile: it doesn't work with Int and Float because they were
> never written:
>
> $ ocaml
>        Objective Caml version 3.09.1
>
> # module IntMap = Map.Make(Int);;
> Unbound module Int
> # module FloatMap = Map.Make(Float);;
> Unbound module Float

This isn't a limitation of the language, this is simply a short comming of 
the standard libraries.


>
> So you have to define a temporary module by hand in general:
>
> # module IntMap = Map.Make(struct type t = int let compare = compare end);;
> module IntMap :
>  sig
>    type key = int
>    type +'a t
>    val empty : 'a t
>    val is_empty : 'a t -> bool
>    val add : key -> 'a -> 'a t -> 'a t
>    val find : key -> 'a t -> 'a
>    val remove : key -> 'a t -> 'a t
>    val mem : key -> 'a t -> bool
>    val iter : (key -> 'a -> unit) -> 'a t -> unit
>    val map : ('a -> 'b) -> 'a t -> 'b t
>    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
>    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
>    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
>    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
>  end
>
> You want a mapping to IntMaps but IntMap is parameterised and the Map.Make
> functor cannot handle that:
>
> # module IntMapMap = Map.Make(IntMap);;
> Signature mismatch:
> Modules do not match:
>  sig
>    type key = int
>    type 'a t = 'a IntMap.t
>    val empty : 'a t
>    val is_empty : 'a t -> bool
>    val add : key -> 'a -> 'a t -> 'a t
>    val find : key -> 'a t -> 'a
>    val remove : key -> 'a t -> 'a t
>    val mem : key -> 'a t -> bool
>    val iter : (key -> 'a -> unit) -> 'a t -> unit
>    val map : ('a -> 'b) -> 'a t -> 'b t
>    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
>    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
>    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
>    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
>  end
> is not included in
>  Map.OrderedType
> Type declarations do not match:
>  type 'a t = 'a IntMap.t
> is not included in
>  type t

How do you know how to compare two generic types?  Yes, you need another 
functor here, to give a comparison function for the types being held. 
Note that the functors propogate in exactly the same way as type class 
dependencies propogate.

Here is one place where (small) changes to the language, the addition of 
some syntactic sugar, could make things a lot more usefull.  I'm thinking 
of something like making => a special operator, so that:

Ord t => let foo (x: t) (y : t) = ...

is the same as:

module Foo(X: Ord) = struct
 	type t = X.t;;
 	open X;;
 	let foo (x: t) (y: t) = ...
end;;

or something.  And some similar bit of syntactic sugar to make 
instantiating a functor lower cost as well.  Obviously this idea has some 
problems.  My point is that is that it should be possible to come up with 
some sort of reasonable extension of the language to allow functors to be 
more "type-class like".

Brian

Re: [Caml-list] stl?

[David Rajchenbach-Teller]

On Tue, 2009-03-10 at 23:16 -0400, Brian Hurt wrote:
> This isn't a limitation of the language, this is simply a short comming of 
> the standard libraries.

It works in Batteries, btw.

> Ord t => let foo (x: t) (y : t) = ...
> 
> is the same as:
> 
> module Foo(X: Ord) = struct
>  	type t = X.t;;
>  	open X;;
>  	let foo (x: t) (y: t) = ...
> end;;
> 
> or something.  And some similar bit of syntactic sugar to make 
> instantiating a functor lower cost as well.  Obviously this idea has some 
> problems.  My point is that is that it should be possible to come up with 
> some sort of reasonable extension of the language to allow functors to be 
> more "type-class like".

How would you determine that "=>" or "foo" maps to "Foo"? IMHO, that's
the main problem with getting typeclasses in OCaml.

Cheers,
 David

-- 
David Teller-Rajchenbach
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
   « Ce matin Un crétin A tué un chercheur. » (air connu)
   Latest News of French Research: System being liquidated. Researchers angry.

Re: [Caml-list] stl?

[David Rajchenbach-Teller]

On Wed, 2009-03-11 at 06:57 +0100, David Rajchenbach-Teller wrote:
> How would you determine that "=>" or "foo" maps to "Foo"? IMHO, that's
> the main problem with getting typeclasses in OCaml.

Ah, ok, I just realized that I had understood your example backwards. My
bad.

Cheers,
 David

-- 
David Teller-Rajchenbach
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
   « Ce matin Un crétin A tué un chercheur. » (air connu)
   Latest News of French Research: System being liquidated. Researchers angry.