January 22, 2013
On 2013-01-22 01:46, Michel Fortin wrote:

> And I'll confirm that it's no magic either. Avoiding cyclic references
> isn't that easy when you start mixing implicitly retained pointers with
> Objective-C's blocks (lambas in C++ or delegate literals in D).
>
> I'm a little sad Apple decided to deprecate its Objective-C garbage
> collector. Having the choice between GC and reference counting was great
> (although it surely sucks for library developers who need to support
> both modes).

Yeah I agree, but ARC works for iOS as well. They never implemented the GC on iOS. Now is MacRuby is available on iOS, which is probably due to ARC.

-- 
/Jacob Carlborg
January 25, 2013
H. S. Teoh wrote:
> The problem is that quite often, the compiler will not be able to prove
> much about the data structure, esp. when you have non-trivial
> manipulation of pointers -- it requires solving the halting problem to
> achieve that level of analysis on arbitrary code -- so it will probably
> fall back to the GC quite often, depending on what the code does.

Well I misspoke on exactly what I meant by "falling back to ref-counting".. I actually don't think you'd need anything like a typical GC's or Ref-counting system, since this memory-model is so rigid it gives a bit more guarantee on when something is allocated and deleted, therefor when references need to be cleaned can be a bit more optimized (at least I think).

For any local variables, most of the cleanup code can be statically injected (like I illustrated above). Really the only area you need to dynamically track and "nullify" references is for dynamically allocating objects, like DynamicArrays. For them we can fall-back on a sort of "Garbage Collection", however I think it can be better (doesn't need cyclic detection, is deterministic, etc). Let me illustrate...

In the compiler, our DynamicArray type might look like:

    type DynamicArray(T) # template type
    {
        ptr pointer : T
        var length : type(ptr)

        ptr refs = MemoryPool(ref T[])

        func => (index, r:ref T)
        {
            refs[index] += r
        }

        func -= (item)
        {
            ...remove item...

            var rfs = refs[getIndex(item)]

            each r in rfs
            {
                if r ==> item
                {
                    r => null
                }
            }

            refs -= rfs
        }
    }

Basically, syntax like:

    var foos = Foo[]

is just sugar for:

    var foos = DynamicArray(Foo)


You'll notice that the DynamicArray type has a reference 'refs' to a MemoryPool of type 'ref T[]'. This MemoryPool object would probably be shared across multiple/all DynamicArrays for optimization, but for now just think of it as a simple dynamic-array-of-arrays itself.

The functions: '=>' & '-=' are operators, and happen whenever a variable is referenced to an item, and when an item is removed, respectively. To illustrate:

    var nums = int[] # DynamicArray(int)
    ref a, b : int

    func main
    {
        nums += 1 # allocate
        nums += 2 # allocate
        nums += 3 # allocate

        a => nums[2] # nums.=>(2, a)
        b => a       # nums.=>(2, b)

        each i in nums
        {
            if runtime_condition
            {
                nums -= i # nums.-=(i)
            }
        }
    }

So while this would search through a list of refs every time an item was removed, it wouldn't have to do any complex cyclic detection, or other such things. The MemoryPools could be a universally managed heap of references that each DynamicArray only held a slice-reference to, therefor allocating arrays would still be cheap.

That's more of what I meant by falling back to "Ref-counting" (more like reverse-referencing) type systems in cases where you need them. Combined with all the optimizations that could occur with local variables, I think a system like this could have a lot of potential as an alternative to a thread-locking GC. Still... I have this feeling like there's some obvious flaw in the design I just can't see yet...
January 25, 2013
On Monday, 21 January 2013 at 17:37:38 UTC, F i L wrote:
>     type Foo
>     {
>         var bar = 0
>     }
>
>     func main
>     {
>         ref f : Foo
>         ref b : int
>
>         scope
>         {
>             var foo = Foo # allocates Foo
>
>             f => foo      # f points to foo
>             f.bar = 1     # foo.bar = 1
>
>             b => f.bar    # b points to foo.bar
>             b = 3         # foo.bar = 3
>
>             # auto 'clean up code' at end of scope:
>             #
>             #     Memory.delete(foo)
>             #     f => null
>             #
>         }
>
>         f.bar = 4 # ERROR: f is null

I think there should be also b => null in the implicit 'auto clean up' phase.

I think it's good to note whether errors are compilation errors or runtime errors. I assume f.bar = 4 in the end there would be a compilation error?


On Friday, 25 January 2013 at 02:12:56 UTC, F i L wrote:
>     var nums = int[] # DynamicArray(int)
>     ref a, b : int
>
>     func main
>     {
>         nums += 1 # allocate
>         nums += 2 # allocate
>         nums += 3 # allocate
>
>         a => nums[2] # nums.=>(2, a)
>         b => a       # nums.=>(2, b)

What if we now (after the code snippet above) write:

nums += 4

And nums has run out of room in its place in the heap and needs to re-allocate its data (4 ints now). I guess that would mean that the call += should nullify all refs pointing to nums (a and b). If we now write:

a = -3

...that can't be a compilation error. Because it's not known at compile-time whether or not nums += 4 forces a re-allocation. Wouldn't this mean then, that all accesses through references would require a runtime penalty for checking whether the ref is null or not?
January 25, 2013
On Friday, 25 January 2013 at 11:28:16 UTC, TommiT wrote:
> On Monday, 21 January 2013 at 17:37:38 UTC, F i L wrote:
>>    type Foo
>>    {
>>        var bar = 0
>>    }
>>
>>    func main
>>    {
>>        ref f : Foo
>>        ref b : int
>>
>>        scope
>>        {
>>            var foo = Foo # allocates Foo
>>
>>            f => foo      # f points to foo
>>            f.bar = 1     # foo.bar = 1
>>
>>            b => f.bar    # b points to foo.bar
>>            b = 3         # foo.bar = 3
>>
>>            # auto 'clean up code' at end of scope:
>>            #
>>            #     Memory.delete(foo)
>>            #     f => null
>>            #
>>        }
>>
>>        f.bar = 4 # ERROR: f is null
>
> I think there should be also b => null in the implicit 'auto clean up' phase.

b didn't need to be assigned to null because the compiler could determine it wasn't being directly accessed after that scope (it was assigned to a new var first). It was intentionally left out to illustrate how the compiler could optimize special cases like that. I wrote that in my original post a bit after that code.


> I think it's good to note whether errors are compilation errors or runtime errors. I assume f.bar = 4 in the end there would be a compilation error?

If the compiler could determine that a ref was being used directly after being cleaned up, then yes, the compiler could throw an error. But that can't happen in every case, so when it can't you'll get a runtime error. Sorry I wasn't clear about that.


> On Friday, 25 January 2013 at 02:12:56 UTC, F i L wrote:
>>    var nums = int[] # DynamicArray(int)
>>    ref a, b : int
>>
>>    func main
>>    {
>>        nums += 1 # allocate
>>        nums += 2 # allocate
>>        nums += 3 # allocate
>>
>>        a => nums[2] # nums.=>(2, a)
>>        b => a       # nums.=>(2, b)
>
> What if we now (after the code snippet above) write:
>
> nums += 4
>
> And nums has run out of room in its place in the heap and needs to re-allocate its data (4 ints now). I guess that would mean that the call += should nullify all refs pointing to nums (a and b). If we now write:
>
> a = -3
>
> ...that can't be a compilation error. Because it's not known at compile-time whether or not nums += 4 forces a re-allocation. Wouldn't this mean then, that all accesses through references would require a runtime penalty for checking whether the ref is null or not?

The specific code you're talking about is a demonstration of an area where the compiler can't (like you said) determine at compile-time the clean-up code, and therefor has to use a runtime approach to nullifying references.

The issue you raise isn't really a problem though. If the memory gets rearranged then the runtime could inform the DynamicArray, and it, in turn, could reassign those refs to the new memory address.

The idea here is that if you're writing something complex like a Container, you may need to use the unmanaged 'ptr' type to get the job done. However, such containers could still make safety guarantees to their users. So if the standard libs provided enough basic building blocks, and the compiler supported advanced meta-programming features (like in D), then programmers would rarely, if ever, need to touch a 'ptr' to make applications.
January 25, 2013
On Friday, 25 January 2013 at 12:05:42 UTC, F i L wrote:
> The issue you raise isn't really a problem though. If the memory gets rearranged then the runtime could inform the DynamicArray, and it, in turn, could reassign those refs to the new memory address.
>

Oh, of course. By the way, what exactly are those things pointed to by the refs member of DynamicArray? Are they references/pointers to reference variables, or something?

One thing I don't like this design is that even if I never make any ref variables that point to the elements of a certain DynamicArray arr, that arr still has to have the member data refs, and has to do some extra work inside func-=(item).



January 25, 2013
What if we re-assign a ref variable to another (or same) element of a DynamicArray:

var nums = int[] # DynamicArray(int)
ref foo : int

nums += 1
nums += 2

foo => nums[0] # nums.=>(0, foo)
foo = 42
foo => nums[1] # nums.=>(1, foo)

Given the definition of DynamicArray's operator =>:

func => (index, r:ref T)
{
    refs[index] += r
}

...it would mean that refs would hold two instances foo (at different indices).

Also, it looks like r is passed as a copy of a ref variable, which to me would indicate that saying r => null wouldn't nullify the original ref variable from which r was made a copy of (in this case ref variable foo).
January 25, 2013
On Friday, 25 January 2013 at 13:14:43 UTC, TommiT wrote:
> What if we re-assign a ref variable to another (or same) element of a DynamicArray:
>
> var nums = int[] # DynamicArray(int)
> ref foo : int
>
> nums += 1
> nums += 2
>
> foo => nums[0] # nums.=>(0, foo)
> foo = 42
> foo => nums[1] # nums.=>(1, foo)
>
> Given the definition of DynamicArray's operator =>:
>
> func => (index, r:ref T)
> {
>     refs[index] += r
> }
>
> ...it would mean that refs would hold two instances foo (at different indices).

Yeah I caught that bug after I originally posted the code as well. I have a solution, but it's ugly, so I'm trying to find a better one. Thanks for the input! I will let you know if I come up with anything elegant.
1 2
Next ›   Last »