Implementation of includesAll

1

I am trying to understand how the includesAll method work. I looked up the implementation:

includesAll { | aCollection |
aCollection.do { | item | if (this.includes(item).not) {^false} };
^true
}

First I thought that meant that every item is checked against the collection in all cases, but when I bench some tests SC does seem to be faster when the first item is not included but not by as much as I expected - roughly a factor 20, the tests show a factor around 5.5. I also don’t understand why the last two bench test are consistently different, in both cases the first item is not included. I must be missing something…

~list = (0, 1..99)

// this needs to check all the numbers since all are included in the list
bench{ 100000.do{ ~list.includesAll((1..19)) } } // around 0.63 seconds

// this should/could fail on first comparison since 101 is not a part of the list
bench{ 100000.do{ ~list.includesAll([100] ++ (0..19)) } } // 0.15-0.155 seconds

// Why is the above consistently slower than this:

bench{ 100000.do{ ~list.includesAll((100..119)) } } // around 0.12 seconds

// by a factor around 1.3 (on my computer)
2

the expression ([100] ++ (0..19)) is being evaluated each time.

compare

a = [100] ++ (0..19);
bench{ 100000.do{ ~list.includesAll( a ) } }

also (100…119).size != ([100] ++ (0…19)).size

3

Yes I missed that! But still I am confused by why the the difference between these two examples is not bigger:

~list = (0, 1..99);
~list2 = (0..19);
bench{ 100000.do{ ~list.includesAll(~list2) } } // around 0.59 seconds

~list3 = [100] ++ (1..19);
bench{ 100000.do{ ~list.includesAll(~list3) } } // around 0.095 seconds
4

If includes always iterates over every item in the list, then you’d expect the list2 benchmark to do 20 * 100 = 2000 iterations per benchmark loop, and list3 to do 1 * 100 = 100 iterations, in which case the 6x speed difference does seem a bit small.

But includes also does early exit, if it finds the item. In the list2 test, it’s searching at most up to item 20, and they’ll all be found. So it’s really 20 * up to 20 = up to 400, vs 100, so 6x seems a bit more reasonable. (There must be something slowing down list2, then, but I’m not sure what. We don’t have a profiler so we may never know.)

hjh

5

Ah yes, the early exit of .includes I had not thought of, that makes sense.

7

IIUC ^ in SC is basically the same as return in C/Java (except that it may be used only in methods, not functions). As such it’s practically ubiquitous in modern languages.

The one feature of ^ that’s distinct from C/Java is what happens when it’s wrapped in a function closure and passed to another part of the code. Then it means “return from the method where the ^ token appears” – in includesAll, this makes ^ behave like return = “return from method” (not “return from function within method”).

hjh

8

Is this what you meant? (Sorry in advance for any confusion)

ClassA {
    var <data;

    *new { |dataVal|
        ^super.newCopyArgs(dataVal)
    }

    methodA { |argu|
        if(argu > data, { ^"Value exceeds threshold".postln; });
        ^"Value within range".postln;
    }

    test { var a = this.methodA(data+1); "Postln.".postln;}
}

ClassB {
    var <instanceOfClassA;

    *new { |instanceA|
        ^super.newCopyArgs(instanceA)
    }

    methodB { |argu|
        instanceOfClassA.methodA(argu);
        "methodB continues execution".postln;
    }
}

/*
a = ClassA.new(10);  
b = ClassB.new(a);   
b.methodB(5); 
b.methodB(15); 
a.test;
*/


void func() {
    printf("Inside closure\n");
    return;
    printf("This line is not reached\n");
}

void someFunction() {
    printf("Inside function\n");
    func();  
    printf("Back in function\n");
}
9

If one pronounces ^ as “method return” it’s less confusing.

Sc doesn’t have a “function return”.

It could have, using a different token, but it doesn’t.

{ }.class == Function
var m = SinOsc.class.methods.[0]; m.class == Method && m.name == 'ar'
1 Like
10

But it does not perform any computation or process data. It does not belong to any object or class. Now I’m confused ))

Or the last expression is just an “implicit return”?

11

I think of it more like a “data wormhole” – wherever it is, whatever is happening in the enclosing method, ^ takes an object and pulls it to the code location immediately after the caller.

What’s fun in SC’s way of doing it is that the caller’s end of the wormhole is fixed (to the moment after the method call), but the ^ itself can be put in a closure and passed around – but the wormhole always takes the data to the same place. That’s how you can early-method-return from a do loop – as in includesAll: the function containing if(something.not) { ^false } has been passed to the do method, but ^ here belongs to includesAll, so it returns to includesAll’s caller (just like a for(...) { if(something) return xxx } construction in C).

I vaguely recall the earlier thread (about Hadron) criticizing this behavior (forgot the details though), but I think JMc knew what he was doing – it’s necessary to have this behavior available.

hjh

12

In python, I think, you can’t just leave the function when you have a function inside it. You need the function’s return checkItem in the end. it allows checkItem to remember the items list from the includesAll scope, so it is indeed a ‘closure.’

def includesAll(items):
    def checkItem(item):
        if item not in items:
            return False
        return True  
    return checkItem

\

But I don’t have clear what is so different in SC about it…

13

These two code examples are not equivalent at all. Also, in the python example you just return the checkItem function, instead of actually calling it.

The special thing about SC is that you can return from a method within a function.

1 Like
14

Yes, the second code would look very different. I was thinking about the ‘closure’ aspect mentioned before.

15

ach so, ok thanks. so that’s it…

16

And for details, perhaps see:

The distinction between the two types of return is that the former
returns to the sender of the home context while the latter returns
to the caller of the active context. (Smalltalk-80: the language
and its implementation. 1983. p.608)

https://dl.acm.org/doi/pdf/10.5555/273.C1066112

2 Likes