Cobra Forums

Posted: **Wed Mar 26, 2008 6:02 pm**

One of the first things I try doing to see whether I like a language for writing algorithms in is see what a toy quicksort looks like.

Here's my effort (please ignore whether or not I've missed something in the implementation i.e. whether or not it will actually sort anything!)

class Test
        def qsort(list as List<of dynamic>) as List<of dynamic>
                test
                        #Following doesn't work (can't cast ints to dynamic)
                        #assert Test().qsort([3,4,1,2])==[1,2,3,4]
                        pass
                body
                        if list.count==1
                                return list
                        else
                                left as List<of dynamic> = []
                                right as List<of dynamic> = []
                                for x in list[1:]
                                        if x<=list[0]
                                                left.add(x)
                                        else
                                                right.add(x)
                                #return .qsort(left)+.qsort(right) <--doesn't work
                                #foo = [1,2].add([3,4]) <-- gives an incorrect compiler message
                                result = .qsort(left)
                                result.addRange(.qsort(right))
                                return result
        def main is shared
                Test().qsort([1,2,3,4])

Which doesn't work, for several reasons (perhaps it would have been more helpful if I'd posted them in a less long-winded manner, but such is life).

The issues are therefore
a) If dictionaries, sets and lists are to be first class syntactic objects (i.e. {:}, {} and []) then I'd really like to be able to perform first class algebra on them.

Simplistically therefore

Code: Select all: #addition assert [1,2]+[3,4]==[1,2,3,4] # i.e. extension assert {1,2}+{3,4}= {1,2,3,4} # i.e. union assert {1:2}+{3:4}={1:2,3:4} # i.e. union, but here I think we'd also need to specify that the second argument updates and adds to the first (though we would lose addition's expected communtivity, which I realise might be unacceptable) i.e.: assert {1:2,3:4}+{5:6,3:5}={1:2,3:5,5:6} #That said, python doesn't let you do addition on dictionaries

The other operators are more debatable, but it might be nice to use - for exclusion on Sets (and perhaps \ for intersection?)
We'd also need to specify that + on a list is equivalent to addrange rather than add (i.e. [1]+[2,3]=[1,2,3], not [1,[2,3]]) and is only meaningful for compatible types. Perhaps these are insufficiently obvious to be allowable (after all, that's why people hate operator overloading in the first place) making this a bad idea. At any rate, I do know I want + for Lists

b) I started off trying to make my list a List<of IComparable>, but then it wouldn't accept ints, so I relaxed that to dynamic, but it *still* won't accept ints (I'm assuming because an int is not an Object). (I should say at this point I come from a Java background not a C# background). I realise it's pretty sophisticated, but are there plans to add autoboxing so that this works? (i.e. I think the new versions of Java (1.5 and onwards) would autmatically turn an int into an Integer in this context).
The compiler complaint is:

Code: Select all: error: Cannot implicitly convert type "System.Collections.Generic.List<int>" to "System.Collections.Generic.List<object>"

c) Finally, a couple of compiler funnies:

Code: Select all: foo = [1,2].add([3,4]) <-- gives an incorrect compiler message

I realise that the above makes no sense (the argument to add should be of the same type as the list members, and it doesn't return anything, so assigning it is meaningless). That said, the compiler complaint is:

Code: Select all: error: Keyword "void" cannot be used in this context

Eh? I never used void!

Code: Select all: foo = qsort([1,2])

Again, this is wrong (I missed out the '.'). But the usually very helpful compiler simply tells me that there is no qsort method. It would be nice if it said 'there is no method called qsort, how about .qsort? (You see? You give people a lovely compiler that tells idiots what they got wrong, and then the idiots complain it's not idiot-proof enough. That's gratititude for you

)

I assume this is the right forum to discuss things like this? I'm assuming that it's definitely the right place for language suggestions (if not bug reports). I also realise I'm just posting what are in effect bug reports - I do promise that one day I'll try to post bug fixes

Posted: **Wed Mar 26, 2008 8:30 pm**

This is definitely the right place for reporting bugs and discussing the language. Even after the public issue tracker is up, it can't hurt to first discuss a bug here, if you like. The biggest thing I need is to know what version you're using such as "0.7.4" or "latest source". Repeating this each time also helps me since I can't remember who is using what.

Using the latest source, I'm unable to reproduce your two problems:

foo = [1,2].add([3,4])

foo.cobra(8): error: Argument 1 of method "add" expects type int?, but the call is supplying type List<of int>.

...

    def qsort(list as List<of dynamic>) as List<of dynamic>
        return qsort(list)

foo.cobra(17): error: You must refer to non-underscored members with a leading dot (.). Member name is "qsort".

These might both be post-0.7.4 improvements.

Autoboxing does in fact work in both Cobra and C#. What doesn't work in either is promoting/boxing a type nested inside a generic. I've thought about this many times and it seems fairly fundamental, e.g., hard to do it otherwise. And even if I enhanced Cobra to construct a copy of the specifically typed list so that .NET wouldn't complain, such automatic behavior will fail to respect side effects like a method that modifies a list argument.

The real solution is to make the method itself generic like so:

def qsort<of T>(list as List<of T>) ...

C# has this, but unfortunately Cobra does not yet. I did get part way through implementing this, but have not had a chance to finish it.

Another potential solution is to use a non-generic class like ArrayList which will require a "use System.Collections" up above.

Here is an example of autoboxing working:

class X

    shared
    
        def main
            .takeDynamic(5)
            .takeObject(6)

        def takeDynamic(d as dynamic)
            assert d == 5
    
        def takeObject(o as Object)
            assert o == 6

Btw you can say "left = []" instead of "left as List<of dynamic> = []" if you like.

Regarding your commutativity comment, we lose addition's expected commutativity not only for dictionaries, but for strings and lists as well. What's really going on is that in computing, there is a "concatenate" operation for sequences, and there is an "addition" operator for numeric types.

Concatenate applies to sequences, is not commutative and preserves the content of both operands in the result. Addition is commutative and the result completely obscures the operands. (Is 5 from "2 + 3" or "1 + 4"?)

(Sorry if you already know this, but it's for everyone's benefit.)

These are conceptually different operations, but + gets used for both. & | ^ are already used for bitwise operators, although since + already overlaps with addition, I'm wondering if & wouldn't be a better choice for "concatenate". It would prevent people from confusing concatenation with addition. It would be a less offensive overlap since "bitwise and" is less commonly used.

I see that you want to treat "+" as an all around "combine" operation that has semantics related to the operands, but I don't have a good impression of that approach. And I think words work fine: set1.union(set2)

Getting back to dictionaries, that's neither addition nor concatenation! Python has an "update" method for this which .NET lacks. However, Cobra is getting extension methods "real soon" and I'll be happy to add that to the standard library.

Posted: **Wed Mar 26, 2008 8:41 pm**

Btw you might also try making the list itself dynamic. I've used this trick a few times when generic lists were getting more pedantic on me than I would have liked:

class Test
        def qsort(list as dynamic) as dynamic
            # implement left as an exercise for the reader

You can index it and anything coming out of it is considered dynamic. Anything coming out of it can be compared with < > <= etc.

If you run into any problems with this approach, I'll be interested to hear.

Posted: **Wed Mar 26, 2008 11:13 pm**

Here you go. Squeaky clean code:

class Sort

    def main is shared
        Sort().run
    
    def run
        assert .insertionSort([3, 4, 2, 5, 3]) == [2, 3, 3, 4, 5]

    def insertionSort(list) as dynamic
        # <!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Insertion_sort">http://en.wikipedia.org/wiki/Insertion_sort</a><!-- m -->
        for i in 1 : list.count
            value = list[i]
            j = i - 1
            while j >= 0 and list[j] > value
                list[j+1] = list[j]
                j -= 1
            list[j+1] = value
        return list

It would run faster if strongly typed with a generic method, but for exploration--and even many applications--you won't notice or care.

It might be interesting to Cobrify the various sorting algorithms that Wikipedia covers in one super sorting example.

HTH

Posted: **Thu Mar 27, 2008 2:52 pm**

Have now switched to using the latest svn, and was playing around writing sorting algorithms and came across the following bug (I think)

Try compiling

Code: Select all: def main is shared num as dynamic? num = 1 print num to IComparable print num to IComparable < 2

and you get

Code: Select all: error: Unexpected "<" after type name. If you are naming a generic, use "of " right after "<" as in "IComparable<of ...".

Posted: **Thu Mar 27, 2008 5:03 pm**

I confirm the bug. This is intended to help C# and other programmers who say "List<int>" in a method signature instead of "List<of int>". Obviously, it's getting in the way when parsing expressions.

The workaround is to put parens around the type cast.

Also, you can condense the num local var to:

num = 1 to dynamic?
# or:
num as dynamic? = 1

And you don't actually need any casting to use the comparison operators on dynamic types. If either operand of an operator is dynamic then the operator will be looked up at run-time (well not counting assignment!).

HTH

Posted: **Fri Mar 28, 2008 12:16 am**

Fixed.

Posted: **Fri Mar 28, 2008 9:02 am**

I've thought about this many times and it seems fairly fundamental, e.g., hard to do it otherwise. And even if I enhanced Cobra to construct a copy of the specifically typed list so that .NET wouldn't complain, such automatic behavior will fail to respect side effects like a method that modifies a list argument.

Not sure I quite understand you. I assume what you're saying is that it's a fundamentally hard problem.

These are conceptually different operations, but + gets used for both. & | ^ are already used for bitwise operators, although since + already overlaps with addition, I'm wondering if & wouldn't be a better choice for "concatenate". It would prevent people from confusing concatenation with addition. It would be a less offensive overlap since "bitwise and" is less commonly used.

And indeed perl recognises this problem (because it is context sensitive between scalars, arrays and dictionaries). Thus string concatenation is done using the . operator.

That said, I think that given that everyone expects 'foo' + 'bar' = 'foobar', it would be reasonable for [1,2,3]+[4,5,6]=[1,2,3,4,5,6]

re: my points on 'arithmetic' on sets, dictionaries etc, it seems you're on the 'overloading is bad' side of the fence, which is fair enough (but still, please can we have list addition).

And while we're on it, can we please have negative list positions? i.e.

Code: Select all: list=[1,2,3] assert list[-1]=3 assert list[-2:-1]=[2,3] #So much more elegant (imho) than assert list[list.count-1]=3

Btw, in the cast bug I posted earlier I was just putting in the unnecessary cast as a way to demonstrate the problem, not because I would code it like that.

In fact, I came up against the problem because my solution to my earlier issue was

Code: Select all: def sorter(list as IList) as IList #Can be passed any type of list, whatever the contents, and seems better than leaving list as dynamic # method contents if list[i] as IComparable < list[j] as IComparable #test # etc.

The cast is necessary as the contents of the IList are assumed to be Object?

Would it be desirable/possible to make the contents of the list dynamic?

btw, I implemented most of the sorting algorithms - do you want them?

Posted: **Sat Mar 29, 2008 1:53 pm**

themaniac wrote:
I've thought about this many times and it seems fairly fundamental, e.g., hard to do it otherwise. And even if I enhanced Cobra to construct a copy of the specifically typed list so that .NET wouldn't complain, such automatic behavior will fail to respect side effects like a method that modifies a list argument.

Not sure I quite understand you. I assume what you're saying is that it's a fundamentally hard problem.

Given a class C, a subclass of it SC, and a generic class G, .NET does not allow G<of SC> to be passed where G<of C> is expected. Nor does .NET have any idea about "dynamic"--that's a pure Cobra compile-time feature which becomes System.Object to .NET/C#.

themaniac wrote:re: my points on 'arithmetic' on sets, dictionaries etc, it seems you're on the 'overloading is bad' side of the fence, which is fair enough (but still, please can we have list addition).

Well I think overloading in the manner described was questionable, but I'm not against it in general, even if it can be abused. Operator overloading is in Cobra's future. It's just not a high priority right now (and the usual: patches welcome). The first step will actually be consuming operator overloads. The step after that will be their declaration.

Yes, we can have list addition. Not sure when, but we'll have it.

themaniac wrote:And while we're on it, can we please have negative list positions? i.e.
[code]
list=[1,2,3]
assert list[-1]=3
assert list[-2:-1]=[2,3]

Cobra already has them for slicing, but not for a single index. I plan on addressing this differently. Consider that:

Adding this will slow down indexing everywhere.
Cobra will have class extensions soon.
The number 1 case for a negative index is to get the last element.

Hence, in the future there be a .last property on lists and arrays. Instead of t[-1] like in Python, or t[t.count-1] like in C# (and current Cobra), you will be able to write t.last.

Of course, you may want the "second to last element" but that can also be done with an extension method. Maybe "last" becomes an overloaded method so you can write t.last or t.last(-2). Unless we can think of a better name for this method than "last" or "reverseIndex".

themaniac wrote:The cast is necessary as the contents of the IList are assumed to be Object?

Would it be desirable/possible to make the contents of the list dynamic?

You can always typecast with "to dynamic" or dictate the type with "for x as dynamic in someList". So far I've refrained from tweaking Cobra to interpret certain return types in the standard library as "dynamic" instead "System.Object?", but I've also considered it...

themaniac wrote:btw, I implemented most of the sorting algorithms - do you want them?

Definitely. What I'm shooting for is a new How To with around 5 sorting algorithms pulled from Wikipedia with URLs referenced in the comments. The idea is to show how using Cobra's dynamic binding and clean syntax allows one to quickly implement an algorithm described by psuedo-code.

Posted: **Sun Mar 30, 2008 1:16 pm**

I've attached a sorting howto. It doesn't compile at the moment, as the compiler complains about the mixture of tabs and spaces in the middle of the comments. Is this a bug or a feature? (I'd be enclined to call it a bug; if the compiler isn't going to allow the comments to be entirely freeform, I think it should check that there is the same indentation at the beginning of the line and then ignore any leading whitespace on the comment line).

Cobra Forums

(Mostly) operator overloading & autoboxing

(Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing

Re: (Mostly) operator overloading & autoboxing