C# equivalent of some SML code
Jon Harrop
I am trying to translate the SML code from Chris Okasaki's excellent
book "Purely Functional Data Structures" into F# and am finding it almost
impossible to write using .NET's OOP.
Okasaki defines a lazy stream type, then a QUEUE module signature, then
BatchedQueue and RealTimeQueue modules that implement the QUEUE signature
and, finally, a CatenableList functor that uses a given QUEUE
implementation to create a catenable list implementation.
The lazy stream was easy because it is a simple generic container but I am
actually stuck on the queues (let alone the functor!).
I tried defining an IQueue interface that all queues could implement in
order to expose their commonality and allow them to be interchangeable. But
the interface's members need to be parameterized over both the type of
elements and the type of queue because they have members like:
method PushBack : 'a -> 'a queue -> 'a queue
The latter cannot be expressed in terms of the former so you end up with an
ugly and inexpressive:
IQueue<ELT, QUEUE>
interface when you really want is a recursive type parameterized *only* over
ELT:
IQueue<ELT, QUEUE> as QUEUE
Furthermore, the queues provide a static value representing the polymorphic
empty queue which hits two more limitations of .NET:
. Apparently you cannot put anything static in an interface.
. .NET has some kind of value restriction that means this value must be
replaced by a function that creates empty values for each element type.
I believe I am getting closer to a working implementation of queues but it
is horrific.
How would you implement a set of compatible purely functional queue
implementations in C# such that you could parameterize other data
structures over them?
Am I correct in assuming that none of the existing collections in .NET have
members that return another collection of the same type?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Peter Duniho
wrote:
> [...]
> I tried defining an IQueue interface that all queues could implement in
> order to expose their commonality and allow them to be interchangeable.
> But
> the interface's members need to be parameterized over both the type of
> elements and the type of queue because they have members like:
>
> method PushBack : 'a -> 'a queue -> 'a queue
>
> The latter cannot be expressed in terms of the former so you end up with
> an
> ugly and inexpressive:
>
> IQueue<ELT, QUEUE>
Why do you end up with that? What's wrong with:
class MyQueue<T> : IQueue<T>
{
MyQueue<T> PushBack() { ... }
}
> interface when you really want is a recursive type parameterized *only*
> over
> ELT:
>
> IQueue<ELT, QUEUE> as QUEUE
Type parameters can be constrained recursively, but it's unusual to need
to do so. With such a vague question, it's hard to know whether you're in
a situation where you need to do that.
> Furthermore, the queues provide a static value representing the
> polymorphic
> empty queue which hits two more limitations of .NET:
>
> . Apparently you cannot put anything static in an interface.
>
> . .NET has some kind of value restriction that means this value must be
> replaced by a function that creates empty values for each element type.
> I believe I am getting closer to a working implementation of queues but
> it
> is horrific.
>
> How would you implement a set of compatible purely functional queue
> implementations in C# such that you could parameterize other data
> structures over them?
>
> Am I correct in assuming that none of the existing collections in .NET
> have
> members that return another collection of the same type?
No, that's not a correct assumption. See the Enumerable extension method
class for one obvious example (not a collection class per se, strictly
speaking, but it's the same pattern you're describing).
Also, see Eric Lippert's blog entries on immutable types, including queues
and lists. I'm sure Google can find them for you as easily as it would
for me.
Beyond that, your post is fairly vague and includes no actual example code
to describe what you're talking about. I don't know if it's simply that
you're not descriptive enough, or perhaps at least some of the statements
would be less vague to someone with a strong functional language
background. But either way, you need to consider your audience better if
you expect to receive useful answers. There's very little in your post
that seems to have a direct answer relevant to C#.
Depending on your exact needs, if you want a static member of something
that's like an interface, you may be able to use an abstract class (which
acts like an interface but also can provide implementation, so you can
include static members).
The fact is, your requirement that the _interface_ provide a "static value
representing the polymorphic empty queue" just seems wrong to me, at least
in a language like C#. The strong typing in C# precludes the idea of a
single instance that is compatible with arbitrary type parameters for a
generic type. C# 4.0 will include some support for variance with
generics, so it's possible that if you can restrict your queue type
parameters, you can support a base-type implementation of the interface
from which you can get such an "empty queue" instance, depending on
exactly what you're trying to do.
As for ".NET has some kind of value restriction", again...without a code
example, it's impossible to understand what you're talking about. What
"kind of value restriction" are you referring to? Assuming you could come
up with an instance that properly represents your "empty queue" value, why
could you not have that instance be stored as the static value member for
the value? What exactly are you trying to do, what code is working for
you, and why is that code different from the code you would like to have
written?
Hint: "horrific" is not a technically precise term.
Pete
Jon Harrop
> On Sat, 02 May 2009 06:58:08 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>> IQueue<ELT, QUEUE>
>
> Why do you end up with that? What's wrong with:
>
> class MyQueue<T> : IQueue<T>
> {
> MyQueue<T> PushBack() { ... }
> }
The PushBack member should come from the (abstract) IQueue interface in
which case it cannot have a (concrete) return type like MyQueue. If it did,
all concrete queue implementations would have to return objects of the
class MyQueue which is obviously not the desired behaviour.
In fact, that mistake hits upon the core of this problem and I have now
resolved it. Essentially, .NET is incapable of expressing the compile-time
techniques that the SML code relies upon. The only alternative is to move
everything to run time and that injects a lot of unnecessary checks and
dispatches. I now have a working translation but it is 5x slower on .NET
compared to OCaml (and MLton is probably much faster still).
> Hint: "horrific" is not a technically precise term.
100 lines of SML code becomes over 600 lines of F# code and runs 5x slower.
The F# team have now worked on my example and, apparently, I did the best
that can be done within the limitations of .NET.
This was actually a very educational exercise and I'd recommend trying to
translate Okasaki's code for anyone who wants to learn about the
limitations of OOP.
Peter Duniho
wrote:
> Peter Duniho wrote:
>> On Sat, 02 May 2009 06:58:08 -0700, Jon Harrop <j...@ffconsultancy.com>
>> wrote:
>>> IQueue<ELT, QUEUE>
>>
>> Why do you end up with that? What's wrong with:
>>
>> class MyQueue<T> : IQueue<T>
>> {
>> MyQueue<T> PushBack() { ... }
>> }
>
> The PushBack member should come from the (abstract) IQueue interface in
> which case it cannot have a (concrete) return type like MyQueue. If it
> did,
> all concrete queue implementations would have to return objects of the
> class MyQueue which is obviously not the desired behaviour.
Fine. Make the return type IQueue<T> instead and put the method in the
interface.
> In fact, that mistake hits upon the core of this problem and I have now
> resolved it.
What mistake?
> Essentially, .NET is incapable of expressing the compile-time
> techniques that the SML code relies upon.
Such as?
> The only alternative is to move
> everything to run time and that injects a lot of unnecessary checks and
> dispatches. I now have a working translation but it is 5x slower on .NET
> compared to OCaml (and MLton is probably much faster still).
C# is a strongly, statically typed language. If you have techniques that
rely on dynamic techniques, then yes...C# isn't going to be appropriate
for you. What a surprise.
Though, you may find the new DLR stuff helpful. Hard to say without
knowing exactly what it is you're complaining about.
>> Hint: "horrific" is not a technically precise term.
>
> 100 lines of SML code becomes over 600 lines of F# code and runs 5x
> slower.
Why is F# relevant here? This is a C# newsgroup.
> The F# team have now worked on my example and, apparently, I did the best
> that can be done within the limitations of .NET.
See above.
> This was actually a very educational exercise and I'd recommend trying to
> translate Okasaki's code for anyone who wants to learn about the
> limitations of OOP.
The fact that you use the word "limitations" simply proves your bias.
Assuming there is some difference you're unable to resolve (which frankly,
has not been demonstrated here yet), it's not so much a "limitation" as
simply a different way of approaching the problem. Each language and
programming paradigm has different things it supports and things it
doesn't.
Frankly, so far all I see in this thread from you is the same troll-like
behavior you've engaged in in the past. Lots of vague statements about
how .NET and C# are inferior, without any specifics to support the
statements, never mind anything that approximates an actual on-topic
discussion.
More recent posts from you in various forums had led me to believe that
you'd toned down your attitude and that you were more willing to engage in
productive discussions. I admit, after this exchange I'm not sure I was
right about that.
Pete
Arne Vajhøj
> On Sun, 03 May 2009 12:15:06 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>> Peter Duniho wrote:
>>> Hint: "horrific" is not a technically precise term.
>>
>> 100 lines of SML code becomes over 600 lines of F# code and runs 5x
>> slower.
>
> Why is F# relevant here? This is a C# newsgroup.
I think his point is that if one ML variant uses 100 lines while
another ML variant implemented on top of .NET uses 600 lines,
then he blames .NET for the difference.
F# is still not on topic for this group.
>> This was actually a very educational exercise and I'd recommend trying to
>> translate Okasaki's code for anyone who wants to learn about the
>> limitations of OOP.
>
> The fact that you use the word "limitations" simply proves your bias.
> Assuming there is some difference you're unable to resolve (which
> frankly, has not been demonstrated here yet), it's not so much a
> "limitation" as simply a different way of approaching the problem. Each
> language and programming paradigm has different things it supports and
> things it doesn't.
>
> Frankly, so far all I see in this thread from you is the same troll-like
> behavior you've engaged in in the past. Lots of vague statements about
> how .NET and C# are inferior, without any specifics to support the
> statements, never mind anything that approximates an actual on-topic
> discussion.
>
> More recent posts from you in various forums had led me to believe that
> you'd toned down your attitude and that you were more willing to engage
> in productive discussions. I admit, after this exchange I'm not sure I
> was right about that.
Usually the first step to solve a problem is to be able to
precisely describe the problem.
The original post did a very poor job of describing what the
problem was.
And as a result the later conclusions lacks credibility.
So trollish sounds as an accurate description.
Arne
Jon Harrop
> On Sun, 03 May 2009 12:15:06 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>> Peter Duniho wrote:
>>> On Sat, 02 May 2009 06:58:08 -0700, Jon Harrop <j...@ffconsultancy.com>
>>> wrote:
>>>> IQueue<ELT, QUEUE>
>>>
>>> Why do you end up with that? What's wrong with:
>>>
>>> class MyQueue<T> : IQueue<T>
>>> {
>>> MyQueue<T> PushBack() { ... }
>>> }
>>
>> The PushBack member should come from the (abstract) IQueue interface in
>> which case it cannot have a (concrete) return type like MyQueue. If it
>> did,
>> all concrete queue implementations would have to return objects of the
>> class MyQueue which is obviously not the desired behaviour.
>
> Fine. Make the return type IQueue<T> instead and put the method in the
> interface.
>
>> In fact, that mistake hits upon the core of this problem and I have now
>> resolved it.
>
> What mistake?
Putting MyQueue as the return type (which is what we want but .NET cannot
express).
>> Essentially, .NET is incapable of expressing the compile-time
>> techniques that the SML code relies upon.
>
> Such as?
The ability to express this factoring without incurring dynamic (run-time)
overheads.
>> The only alternative is to move
>> everything to run time and that injects a lot of unnecessary checks and
>> dispatches. I now have a working translation but it is 5x slower on .NET
>> compared to OCaml (and MLton is probably much faster still).
>
> C# is a strongly, statically typed language. If you have techniques that
> rely on dynamic techniques, then yes...C# isn't going to be appropriate
> for you. What a surprise.
This is a limitation of .NET's type system that C# inherited. The only known
workaround in .NET languages today is to resort to dynamic techniques that
are slow and fragile. I don't want to do that for obvious reasons.
>>> Hint: "horrific" is not a technically precise term.
>>
>> 100 lines of SML code becomes over 600 lines of F# code and runs 5x
>> slower.
>
> Why is F# relevant here? This is a C# newsgroup.
For the purposes of this discussion, there is no difference between C# and
F# because they both inherited this same limitation from .NET's type
system. If anything, a C# solution would be even longer than the F# and
just as slow.
>> This was actually a very educational exercise and I'd recommend trying to
>> translate Okasaki's code for anyone who wants to learn about the
>> limitations of OOP.
>
> The fact that you use the word "limitations" simply proves your bias.
This is a known limitation of the .NET type system according to the people
who designed it. That is a fact, not a bias.
> Assuming there is some difference you're unable to resolve (which frankly,
> has not been demonstrated here yet), it's not so much a "limitation" as
> simply a different way of approaching the problem. Each language and
> programming paradigm has different things it supports and things it
> doesn't.
Other languages can solve this statically with no run-time overhead
whatsoever. C# and F# cannot solve it statically at all and force the
programmer to resort to dynamic techniques with run-time overheads
everywhere instead.
> Frankly, so far all I see in this thread from you is the same troll-like
> behavior you've engaged in in the past. Lots of vague statements about
> how .NET and C# are inferior, without any specifics to support the
> statements, never mind anything that approximates an actual on-topic
> discussion.
>
> More recent posts from you in various forums had led me to believe that
> you'd toned down your attitude and that you were more willing to engage in
> productive discussions. I admit, after this exchange I'm not sure I was
> right about that.
Please don't bother replying to any of my posts again, including this one.
Jon Harrop
> Peter Duniho wrote:
>> On Sun, 03 May 2009 12:15:06 -0700, Jon Harrop <j...@ffconsultancy.com>
>> wrote:
>>> Peter Duniho wrote:
>>>> Hint: "horrific" is not a technically precise term.
>>>
>>> 100 lines of SML code becomes over 600 lines of F# code and runs 5x
>>> slower.
>>
>> Why is F# relevant here? This is a C# newsgroup.
>
> I think his point is that if one ML variant uses 100 lines while
> another ML variant implemented on top of .NET uses 600 lines,
> then he blames .NET for the difference.
MLs like OCaml and SML have higher-order module systems. F# does not.
Moreover, that is actually the exact language feature used to solve this
problem in ML that I wanted a .NET alternative to.
> F# is still not on topic for this group.
I wanted a solution in C#.
>> More recent posts from you in various forums had led me to believe that
>> you'd toned down your attitude and that you were more willing to engage
>> in productive discussions. I admit, after this exchange I'm not sure I
>> was right about that.
>
> Usually the first step to solve a problem is to be able to
> precisely describe the problem.
The problem is:
How can you translate the code from Okasaki's book into C#?
> The original post did a very poor job of describing what the
> problem was.
The first paragraph of my first post said:
"I am trying to translate the SML code from Chris Okasaki's excellent
book "Purely Functional Data Structures" into F# and am finding it almost
impossible to write using .NET's OOP."
> And as a result the later conclusions lacks credibility.
>
> So trollish sounds as an accurate description.
If you feel that way and have no idea what the problem is, let alone how to
solve it, please don't reply.
Peter Duniho
wrote:
> [...]
>> Fine. Make the return type IQueue<T> instead and put the method in the
>> interface.
>>
>>> In fact, that mistake hits upon the core of this problem and I have now
>>> resolved it.
>>
>> What mistake?
>
> Putting MyQueue as the return type (which is what we want but .NET cannot
> express).
That makes no sense. Outside the type MyQueue, why would you need to
declare the return type as MyQueue? What is it about IQueue<T> that isn't
appropriate? Why _would_ you want MyQueue to be the return type when you
don't know for a fact MyQueue is the implementing type?
>>> Essentially, .NET is incapable of expressing the compile-time
>>> techniques that the SML code relies upon.
>>
>> Such as?
>
> The ability to express this factoring without incurring dynamic
> (run-time)
> overheads.
What factoring? So far, you haven't given any actual example of what
you're talking about.
> This is a limitation of .NET's type system that C# inherited.
What is a limitation? You haven't actually stated any specific
limitation. You've said that one exists.
> [...]
>> Why is F# relevant here? This is a C# newsgroup.
>
> For the purposes of this discussion, there is no difference between C#
> and
> F#
Then present your question in the context of C# instead of F#.
> [...]
>> The fact that you use the word "limitations" simply proves your bias.
>
> This is a known limitation of the .NET type system according to the
> people
> who designed it.
What is a known limitation of the .NET type system? Again, you haven't
stated any specific limitation.
> That is a fact, not a bias.
You're missing my point. I'm not saying it's not a "limitation" in some
sense of the word. I'm pointing out that the fact that you choose to
describe is as a "limitation" as opposed to using less-judgmental language
shows your bias.
There are plenty of examples that could be offered as an "education
exercise...for anyone who wants to learn about the limitations of ML-based
languages" as well. But I'm sure you'd be the first to agree that for
applications where those ML-based languages are appropriate, the
"limitations" aren't really a problem at all.
Likewise, what you perceive as a "limitation" in .NET (inasmuch as your
perception is even correct) is simply "the way it works". It's only a
"limitation" for specific situations, and describing it as "the
limitations of OOP" as if a) all OOP languages share .NET's design, and b)
all functional languages are not similarly limited in some way, is simply
inaccurate at best, and (when stated in this context) trollish at worst.
> [...]
> Other languages can solve this statically with no run-time overhead
> whatsoever.
Can solve what? Until you provide a specific example, you're just blowing
smoke.
> [...]
> Please don't bother replying to any of my posts again, including this
> one.
If you don't want a reply, don't post in the first place. If you do post,
don't make trollish statements unless you are prepared for your posts to
be called trollish.
Like I said, if you have some specific issue you'd like to discuss and/or
receive help with, by all means post about that. But if all you've got
are your vague, unsubstantiated claims of inferiority of C#/.NET, take it
somewhere else. That kind of behavior doesn't have any place in any
technical forum, never mind this one.
Pete
Jon Harrop
> I am trying to translate the SML code from Chris Okasaki's excellent
> book "Purely Functional Data Structures" into F# and am finding it almost
> impossible to write using .NET's OOP.
To answer my own question: a faithful translation is impossible due to the
limitations of .NET's static type system. Specifically, a literal OOP
equivalent of SML's functors would be able to parameterize classes over
classes but .NET is only capable of parameterizing objects over objects
and, as a dynamic technique, that severely degrades performance and
introduces many unnecessary sources of run-time type errors.
There are three possible workarounds:
. Solve the problem efficiently at the cost of asymptotically more code due
to the lack of factoring by inlining the classes by hand, i.e. cut and
paste.
. Sacrifice performance but retain the elegant factoring by resorting to
dynamic typing.
. Write a new compiler for a language that supports these features and
expand them at compile time, i.e. automating the cut and paste of the first
workaround.
Jon Harrop
> On Sun, 03 May 2009 14:21:51 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>> [...]
>>> Fine. Make the return type IQueue<T> instead and put the method in the
>>> interface.
>>>
>>>> In fact, that mistake hits upon the core of this problem and I have now
>>>> resolved it.
>>>
>>> What mistake?
>>
>> Putting MyQueue as the return type (which is what we want but .NET cannot
>> express).
>
> That makes no sense. Outside the type MyQueue, why would you need to
> declare the return type as MyQueue?
Ideally, the return type should be that of the concrete class, e.g. the
PushBack member should return MyQueue in MyQueue and YourQueue in
YourQueue.
> What is it about IQueue<T> that isn't appropriate?
It appears at run-time in the return types of all of these functions. I want
it to be resolved statically at compile time and not appear at run time at
all.
> Why _would_ you want MyQueue to be the return type when you don't know for
> a fact MyQueue is the implementing type?
I want the return type to be the implementing type in all cases.
>> The ability to express this factoring without incurring dynamic
>> (run-time) overheads.
>
> What factoring? So far, you haven't given any actual example of what
> you're talking about.
Okasaki's book gives an abstract QUEUE signature and concrete BatchedQueue
and RealTimeQueue modules implementing QUEUE as well as a CatenableList
functor that is parameterized over a module than implements QUEUE.
A BatchedQueue has better average case performance in the absence of
persistence. A RealTimeQueue has better worst case performance.
Consequently, a user might want to build a CatenableList from either kind
of queue.
The factoring I am referring to is the ability to instantiate CatenableList
from either BatchedQueue or RealTimeQueue.
In C#, you would create an IQueue interface and BatchedQueue and
RealTimeQueue classes that implement IQueue. Then you would create a
CatenableList class with a constructor that accepts an object implementing
IQueue. This provides the factoring.
However, if you cut and paste the code from the two queue implementations
into new BatchedCatenableList and RealTimeCatenableList classes then the
user gets the same functionality but with much better efficiency because
you have removed the run-time overheads (e.g. of dispatch when calling a
member of an IQueue).
Okasaki's SML code benefits from the best of both worlds, i.e. factored code
and no run-time overheads. I want that in C#.
>> This is a limitation of .NET's type system that C# inherited.
>
> What is a limitation? You haven't actually stated any specific
> limitation. You've said that one exists.
You cannot parameterize a class over another class in any .NET language,
including both C# and F#. The obvious workaround is to parameterize over
objects but, as run-time concepts, that incurs run-time overheads.
>> [...]
>>> Why is F# relevant here? This is a C# newsgroup.
>>
>> For the purposes of this discussion, there is no difference between C#
>> and
>> F#
>
> Then present your question in the context of C# instead of F#.
I already did in my first post:
"How would you implement a set of compatible purely functional queue
implementations in C# such that you could parameterize other data
structures over them?"
>> That is a fact, not a bias.
>
> You're missing my point. I'm not saying it's not a "limitation" in some
> sense of the word. I'm pointing out that the fact that you choose to
> describe is as a "limitation" as opposed to using less-judgmental language
> shows your bias.
>
> There are plenty of examples that could be offered as an "education
> exercise...for anyone who wants to learn about the limitations of ML-based
> languages" as well. But I'm sure you'd be the first to agree that for
> applications where those ML-based languages are appropriate, the
> "limitations" aren't really a problem at all.
I was not expecting to struggle with the implementations of basic data
structures in .NET languages.
> If you don't want a reply, don't post in the first place.
I was hoping for a reply from anyone who has hit the same problem,
preferably whilst performing the same exercise.
Peter Duniho
wrote:
> To answer my own question: a faithful translation is impossible due to
> the
> limitations of .NET's static type system.
You have made, previously in this forum, statements of impossibility which
have proven to be wrong. Why should we expect this to be any different?
Until you have stated the problem in a clear, understandable way, there is
no way to have a productive discussion on the topic.
If you refuse to provide such a clear, understandable problem statement,
then you must not be interested in a productive discussion on the topic.
And you wonder why we might characterize your posts as "trollish"?
Pete
Peter Duniho
wrote:
> [...]
>> Usually the first step to solve a problem is to be able to
>> precisely describe the problem.
>
> The problem is:
>
> How can you translate the code from Okasaki's book into C#?
You are essentially assuming that anyone reading you post a) has access to
Okasaki's book, and b) is familiar with the language (SML, I take it?)
used in the book.
That is an extremely poor way to present a question in a forum like this.
If you want a real answer, you need to present your question in a format
suitable for this forum, without prerequisites like the above.
Describe the code you want to implement in C#, without requiring that the
reader have access to the book in question, and in a high-level way (e.g.
pseudocode), rather than in a specific programming language unknown to
practically everyone reading your post.
>> The original post did a very poor job of describing what the
>> problem was.
>
> The first paragraph of my first post said:
>
> "I am trying to translate the SML code from Chris Okasaki's excellent
> book "Purely Functional Data Structures" into F# and am finding it almost
> impossible to write using .NET's OOP." [...]
That's true. You first post did say that. And as Arne said, that was a
very poor way to describe what the problem is. It still is a very poor
way to describe what the problem is.
Pete
Jon Harrop
> On Sun, 03 May 2009 14:52:42 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>> To answer my own question: a faithful translation is impossible due to
>> the
>> limitations of .NET's static type system.
>
> You have made, previously in this forum, statements of impossibility which
> have proven to be wrong.
I assume we have disagreed about something here in the past but, if I was
wrong, why are your hackles up and not mine?
> Until you have stated the problem in a clear, understandable way, there is
> no way to have a productive discussion on the topic.
In what way was my problem statement unclear?
> If you refuse to provide such a clear, understandable problem statement,
> then you must not be interested in a productive discussion on the topic.
Does replying to all of my posts with a series of baseless accusations and
petty insults constitute "productive discussion" where you are from?
In reality, your failure to understand my question does not imply anything
about my interests.
> And you wonder why we might characterize your posts as "trollish"?
If I wonder anything it is why you said you did not understand my posts and
then attempted to characterize them. The answer is obvious, of course: you
do not want me to question your religious beliefs about the only
programming languages you know.
Now I'm wondering why technical discussions elicit such primal responses
only from unaccomplished programmers...
Peter Duniho
wrote:
> Ideally, the return type should be that of the concrete class, e.g. the
> PushBack member should return MyQueue in MyQueue and YourQueue in
> YourQueue.
Why? Simply stating the requirement isn't useful. You need to explain
_why_ you're imposing the requirement.
>> What is it about IQueue<T> that isn't appropriate?
>
> It appears at run-time in the return types of all of these functions. I
> want
> it to be resolved statically at compile time and not appear at run time
> at
> all.
See above. Simply because you "want" something doesn't explain why you
"want" that something.
Also, what do you mean by "I want it to be resolved statically"? You want
what to be resolved statically? The return type IQueue<T> is most
definitely resolved statically, but it's resolved to an interface. If you
don't want that to appear at run time, what _do_ you want to appear at
run-time? If you want the concrete class type to appear at run-time, then
what is code that is compiled separately from the concrete class, or which
at run-time has conditional use of one or another of the possible
interface implementations supposed to do? Do you simply not care about
that scenario at all? If not, why not just #ifdef the implementation
details and have a single type containing your implementation of choice?
Note that I'm not proposing "#ifdef" is the answer to your question. I'm
simply pointing out how vague your problem statement is, and how
impossible it is to have any sort of useful discussion as long as you
continue to fail to provide the necessary details.
>> Why _would_ you want MyQueue to be the return type when you don't know
>> for
>> a fact MyQueue is the implementing type?
>
> I want the return type to be the implementing type in all cases.
If the calling code knows the implementing type, then why bother with the
interface at all? Conversely, if the calling code doesn't know the
implementing type, how _could_ the return type be that of the implementing
type? What would the caller do with that?
> [...]
> However, if you cut and paste the code from the two queue implementations
> into new BatchedCatenableList and RealTimeCatenableList classes then the
> user gets the same functionality but with much better efficiency because
> you have removed the run-time overheads (e.g. of dispatch when calling a
> member of an IQueue).
Your sole complaint is the cost of a virtual method dispatch?
> Okasaki's SML code benefits from the best of both worlds, i.e. factored
> code
> and no run-time overheads. I want that in C#.
I agree that virtual dispatch is a fundamental aspect of polymorphism in
all the major OOP languages (possibly all OOP languages period). But
there's nothing about your question that demonstrates why this overhead is
significant, nor why SML doesn't suffer from the same overhead, nor why
SML doesn't trade some other type of overhead for this overhead.
Again, the question is far too vague.
> [...]
>> Then present your question in the context of C# instead of F#.
>
> I already did in my first post:
>
> "How would you implement a set of compatible purely functional queue
> implementations in C# such that you could parameterize other data
> structures over them?"
That's not a clear problem statement. But more importantly, it doesn't
have anything do with your other comments about F#. If F# isn't relevant
to your question, then don't bring it up. I didn't write "present your
question in the context of C# in addition to F#". I wrote "instead of".
The fact that you mentioned C# elsewhere doesn't have anything to do with
whether the F# references were relevant.
> [...]
>> There are plenty of examples that could be offered as an "education
>> exercise...for anyone who wants to learn about the limitations of
>> ML-based
>> languages" as well. But I'm sure you'd be the first to agree that for
>> applications where those ML-based languages are appropriate, the
>> "limitations" aren't really a problem at all.
>
> I was not expecting to struggle with the implementations of basic data
> structures in .NET languages.
As near as I can tell, you are not struggling with the implementations of
basic data structures in .NET languages. The only concrete thing you
stated so far is that you don't want to have to suffer the virtual
dispatch inherent in an interface. That's hardly a data structure
problem. It's an implementation detail.
>> If you don't want a reply, don't post in the first place.
>
> I was hoping for a reply from anyone who has hit the same problem,
> preferably whilst performing the same exercise.
Your problem domain is so specific, it amazes me that you think you'd find
someone else who has run into the same thing in a general-purpose C#
newsgroup like this one.
In any case, if you only want replies from someone with specific
experience dealing with porting SML code to C#, state that at the outset,
and leave out the inflammatory comments about how C# or .NET is inferior,
limited, etc.
If you can make an honest statement about what sort of audience you intend
for your question, and do so without being judgmental, I'm more than happy
to comply and just ignore the question (not having that functional
language experience myself). But, if you fail to describe your intended
audience accurately, and especially when you start engaging in
language/framework bashing, it's unrealistic for you to expect the general
audience in this newsgroup to simply stay quiet.
Pete
Peter Duniho
wrote:
>> You have made, previously in this forum, statements of impossibility
>> which
>> have proven to be wrong.
>
> I assume we have disagreed about something here in the past but, if I was
> wrong, why are your hackles up and not mine?
It wasn't a matter of disagreement. You simply made an assumption about
what was and what wasn't possible in C#, without first learning what was
and what wasn't possible in C#. Your assumption was wrong then, and I see
no reason to take as granted that your assumption now is correct.
As for "hackles", the only thing that's gotten me irritated with you is
your repeated judgments of C# and .NET as inferior, and especially your
insistence on posting those judgments here while refusing to offer any
actual explanation.
>> Until you have stated the problem in a clear, understandable way, there
>> is
>> no way to have a productive discussion on the topic.
>
> In what way was my problem statement unclear?
In every way. There was no way in which it was clear.
>> If you refuse to provide such a clear, understandable problem statement,
>> then you must not be interested in a productive discussion on the topic.
>
> Does replying to all of my posts with a series of baseless accusations
> and
> petty insults constitute "productive discussion" where you are from?
No one has done that, least of all me. The only person in this thread who
has posted insults at all, petty or otherwise, has been you. In fact, the
post to which I'm replying at the moment is a great example of that.
> In reality, your failure to understand my question does not imply
> anything
> about my interests.
You have been given repeated opportunities to clarify your question, and
continue to refuse to do so. My failure to understand your question is a
direct consequence of those refusals and certainly does imply something
about your interests.
>> And you wonder why we might characterize your posts as "trollish"?
>
> If I wonder anything it is why you said you did not understand my posts
> and
> then attempted to characterize them.
I don't need to understand the question in order to be able to
characterize your statements describing C# and .NET as inferior as such.
> The answer is obvious, of course: you
> do not want me to question your religious beliefs about the only
> programming languages you know.
>
> Now I'm wondering why technical discussions elicit such primal responses
> only from unaccomplished programmers...
So, not satisfied with denigrating C# and .NET, you have now moved on to
denigrating actual people?
Again...you wonder why we might characterize your posts as "trollish"?
Pete
Jon Harrop
> On Sun, 03 May 2009 15:49:11 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>>> You have made, previously in this forum, statements of impossibility
>>> which have proven to be wrong.
>>
>> I assume we have disagreed about something here in the past but, if I was
>> wrong, why are your hackles up and not mine?
>
> It wasn't a matter of disagreement. You simply made an assumption about
> what was and what wasn't possible in C#, without first learning what was
What assumption?
> As for "hackles", the only thing that's gotten me irritated with you is
> your repeated judgments of C# and .NET as inferior, and especially your
> insistence on posting those judgments here while refusing to offer any
> actual explanation.
I explained in full in my first post.
>>> Until you have stated the problem in a clear, understandable way, there
>>> is
>>> no way to have a productive discussion on the topic.
>>
>> In what way was my problem statement unclear?
>
> In every way. There was no way in which it was clear.
Did you understand that I was referring to the code in Okasaki's book?
>>> If you refuse to provide such a clear, understandable problem statement,
>>> then you must not be interested in a productive discussion on the topic.
>>
>> Does replying to all of my posts with a series of baseless accusations
>> and petty insults constitute "productive discussion" where you are from?
>
> No one has done that, least of all me.
Except in the first paragraph quoted in this post, for example.
>> In reality, your failure to understand my question does not imply
>> anything about my interests.
>
> You have been given repeated opportunities to clarify your question, and
> continue to refuse to do so.
I have made every attempt to clarify it for you.
>>> And you wonder why we might characterize your posts as "trollish"?
>>
>> If I wonder anything it is why you said you did not understand my posts
>> and then attempted to characterize them.
>
> I don't need to understand the question in order to be able to
> characterize your statements describing C# and .NET as inferior as such.
Then you are retrospectively classifying my question according to its answer
despite the fact that I obviously did not know the answer when I asked the
question or I would not have bothered asking it...
>> Now I'm wondering why technical discussions elicit such primal responses
>> only from unaccomplished programmers...
>
> So, not satisfied with denigrating C# and .NET...
Stumbling upon something that cannot be done on .NET is not "denigrating"
it.
> Again...you wonder why we might characterize your posts as "trollish"?
I wonder why you think I would care.
Jon Harrop
> On Sun, 03 May 2009 15:28:07 -0700, Jon Harrop <j...@ffconsultancy.com>
> wrote:
>
>> Ideally, the return type should be that of the concrete class, e.g. the
>> PushBack member should return MyQueue in MyQueue and YourQueue in
>> YourQueue.
>
> Why? Simply stating the requirement isn't useful. You need to explain
> _why_ you're imposing the requirement.
Performance.
>>> What is it about IQueue<T> that isn't appropriate?
>>
>> It appears at run-time in the return types of all of these functions. I
>> want
>> it to be resolved statically at compile time and not appear at run time
>> at
>> all.
>
> See above. Simply because you "want" something doesn't explain why you
> "want" that something.
Performance.
> Also, what do you mean by "I want it to be resolved statically"? You want
> what to be resolved statically?
The parameterization, e.g. of CatenableList over a queue.
> The return type IQueue<T> is most
> definitely resolved statically, but it's resolved to an interface. If you
> don't want that to appear at run time, what _do_ you want to appear at
> run-time?
The concrete type.
> If you want the concrete class type to appear at run-time, then
> what is code that is compiled separately from the concrete class, or which
> at run-time has conditional use of one or another of the possible
> interface implementations supposed to do?
There is no such code in my case.
> Do you simply not care about
> that scenario at all? If not, why not just #ifdef the implementation
> details and have a single type containing your implementation of choice?
That is not extensible.
> Note that I'm not proposing "#ifdef" is the answer to your question. I'm
> simply pointing out how vague your problem statement is, and how
> impossible it is to have any sort of useful discussion as long as you
> continue to fail to provide the necessary details.
If you ask for any specific details I will do my best to provide them.
>>> Why _would_ you want MyQueue to be the return type when you don't know
>>> for
>>> a fact MyQueue is the implementing type?
>>
>> I want the return type to be the implementing type in all cases.
>
> If the calling code knows the implementing type, then why bother with the
> interface at all?
The interface exists on .NET only as a workaround for the absence of module
signatures. It is used to express the common API provided by queue
implementations.
> Conversely, if the calling code doesn't know the
> implementing type, how _could_ the return type be that of the implementing
> type? What would the caller do with that?
Parametric polymorphism (aka generics).
>> [...]
>> However, if you cut and paste the code from the two queue implementations
>> into new BatchedCatenableList and RealTimeCatenableList classes then the
>> user gets the same functionality but with much better efficiency because
>> you have removed the run-time overheads (e.g. of dispatch when calling a
>> member of an IQueue).
>
> Your sole complaint is the cost of a virtual method dispatch?
Yes.
>> Okasaki's SML code benefits from the best of both worlds, i.e. factored
>> code and no run-time overheads. I want that in C#.
>
> I agree that virtual dispatch is a fundamental aspect of polymorphism in
> all the major OOP languages (possibly all OOP languages period).
Only of subtype polymorphism.
> But
> there's nothing about your question that demonstrates why this overhead is
> significant, nor why SML doesn't suffer from the same overhead, nor why
> SML doesn't trade some other type of overhead for this overhead.
Higher-order modules in SML effectively allow you to parameterize one class
over another in order to create new classes. The effect occurs entirely at
compile time and the generated code is as if the programmer had cut and
pasted the code from BatchedQueue into CatenableList in order to create a
specialized BatchedCatenableList. Consequently, there is no virtual
dispatch because each instantiation creates a single concrete class with
the desired implementation entirely self-contained.
If you know C++ then the equivalent would be parameterizing CatenableList
using a template and passing the queue class in as a template parameter.
> Again, the question is far too vague.
I am more than happy to explain what higher-order modules are and how they
work. Hopefully the above explanation is sufficient.
>> [...]
>>> Then present your question in the context of C# instead of F#.
>>
>> I already did in my first post:
>>
>> "How would you implement a set of compatible purely functional queue
>> implementations in C# such that you could parameterize other data
>> structures over them?"
>
> That's not a clear problem statement. But more importantly, it doesn't
> have anything do with your other comments about F#. If F# isn't relevant
> to your question, then don't bring it up. I didn't write "present your
> question in the context of C# in addition to F#". I wrote "instead of".
> The fact that you mentioned C# elsewhere doesn't have anything to do with
> whether the F# references were relevant.
Ok.
>> [...]
>>> There are plenty of examples that could be offered as an "education
>>> exercise...for anyone who wants to learn about the limitations of
>>> ML-based
>>> languages" as well. But I'm sure you'd be the first to agree that for
>>> applications where those ML-based languages are appropriate, the
>>> "limitations" aren't really a problem at all.
>>
>> I was not expecting to struggle with the implementations of basic data
>> structures in .NET languages.
>
> As near as I can tell, you are not struggling with the implementations of
> basic data structures in .NET languages. The only concrete thing you
> stated so far is that you don't want to have to suffer the virtual
> dispatch inherent in an interface. That's hardly a data structure
> problem. It's an implementation detail.
That is my only remaining problem now, yes.
>>> If you don't want a reply, don't post in the first place.
>>
>> I was hoping for a reply from anyone who has hit the same problem,
>> preferably whilst performing the same exercise.
>
> Your problem domain is so specific, it amazes me that you think you'd find
> someone else who has run into the same thing in a general-purpose C#
> newsgroup like this one.
On the contrary, I expected to see a vast body of experience about the
idiomatic implementation of well-factored and efficient data structures
using OOP in C#.
> In any case, if you only want replies from someone with specific
> experience dealing with porting SML code to C#, state that at the outset,
> and leave out the inflammatory comments about how C# or .NET is inferior,
> limited, etc.
What you perceive as inflammatory comments were the correct answer to my
technical question and, consequently, they did not appear in the question.
> If you can make an honest statement about what sort of audience you intend
> for your question, and do so without being judgmental, I'm more than happy
> to comply and just ignore the question (not having that functional
> language experience myself).
You should ignore anything I ask unless you want to learn about it.
namekuseijin
> resolved it. Essentially, .NET is incapable of expressing the compile-time
> techniques that the SML code relies upon. The only alternative is to move
> everything to run time and that injects a lot of unnecessary checks and
> dispatches. I now have a working translation but it is 5x slower on .NET
> compared to OCaml (and MLton is probably much faster still).
>
> > Hint: "horrific" is not a technically precise term.
>
> 100 lines of SML code becomes over 600 lines of F# code and runs 5x slower.
>
> The F# team have now worked on my example and, apparently, I did the best
> that can be done within the limitations of .NET.
>
> This was actually a very educational exercise and I'd recommend trying to
> translate Okasaki's code for anyone who wants to learn about the
> limitations of OOP.
well, that's surprising coming from you and all your pro-F#
enthusiasm... :P
Jon Harrop
> well, that's surprising coming from you and all your pro-F#
> enthusiasm... :P
I miss OCaml's structural typing even more than its functors though. I don't
know how people survive without polymorphic variants. ;-)
namekuseijin
wrote:
Trollish or not, he has a point: .NET's type system is well suited for
OO programming languages and that means static typing with lots of
late binding at runtime.
He used to advocate a lot for F# in Lisp forums but seems to have
become a bit disillusioned at a Microsoft solution, what a surprise.
Jon Harrop
> He used to advocate a lot for F# in Lisp forums but seems to have
> become a bit disillusioned at a Microsoft solution, what a surprise.
I don't think there is any confusion: the advantage of .NET over the likes
of Lisp is commercial viability.