Autovivification in C#

Question

Trying to wrap my head around perl's Autovivification and based on what it sounds like, It seems to work similar to dynamics in C# as a dynamic object is not assigned a type until runtime or, am I totally off here. If so then is there a comparable idea that I can bridge off of in C# that makes sense?

Edit
Okay so I'm apparently way off. So as second part of the 2 part question, is there anything conceptually comparable in C#? To be clear I'm looking for a concept in C# that is comparable to Autovivification. Doesn't have to be exactly the same but close enough conceptually to make sense. And as I stated eariler I am by no means a perl hacker or python hacker by any stretch of the imagination but, I am familar with c based languages C, C++, C#, java, javascript. I was thinking of C#'s dynamics but, as of right now I'm thinking lazy loading based on the info here if that helps....

Answer 1

I can't speak to C#, but in layman's terms, Perl's autovivification is the process of creating a container object out of an undefined value as soon as it is needed.

Despite most of Perl being quite dynamic, Perl's dereferencing syntax unambiguously specifies the type of the reference at compile time. This allows the interpreter to know what it needs out of a variable before the variable is ever defined.

my $var;  # undefined

# to autovivify to an array:
@$var = 1..5;  # @ here implies ARRAY
$$var[4] = 5;  # square brackets imply ARRAY
$#$var;        # $# implies ARRAY (returns the last index number)

# to autovivify to a hash:

%$var = (a => 1);   # % implies HASH
$$var{asdf} = 5;    # curly braces imply HASH

This list could be longer, but should give you an idea.

So basically, when you have a line like this:

my $var;
$var->[1]{x}[3]{asdf}

Perl looks on the right side of the -> and sees square braces. This means that the invocant $var must be an array reference. Since the invocant is undefined, Perl creates a new array and installs its reference into $var. This same process is then repeated for every subsequent dereferencing.

So the line above really means:

    (((($var //= [])->[1] //= {})->{x} //= [])->[3] //= {})->{asdf};

which is fairly hideous, and hence autovivification. (//= is the defined-or assignment operator in perl 5.10+)

Update:

As per cjm's comment, to put this into general non-perl terms, to achieve autovivification in another language, you need a lazy object that supports indexing via [...] and {...}. When either of these indexing operations are performed, the object replaces itself with either an array or hash. Every time the object is then accessed, if the cell is empty, it should return another lazy object.

obj = new lazy_obj()

level1 = obj[4]   # sets obj to be an array, returns a new lazy_obj for level1

level2 = level1{asdf}  # sets level1 (and obj[4]) to a hash,
                       # returns a new lazy_obj for level2

So basically you need two things, the ability to create an object that supports indexing with both array and hash subscripts (or the equivalent), and a mechanism such that an object can replace itself in memory with another object (or that can lock itself to one interpretation, and then store the new object internally.

Something like the following pseudo-code could be a start:

class autoviv {
   private var content;

   method array_subscript (idx) {
       if (!content) {
           content = new Array();
       }
       if (typeof content == Array) {
            if (exists content[idx]) return content[idx];
            return content[idx] = new autoviv();
       } else {
            throw error
       }
   }

   method hash_subscript (idx) {
       if (!content) {
           content = new Hash();
       }
       if (typeof content == Hash) {
            if (exists content{idx}) return content{idx};
            return content{idx} = new autoviv();
       } else {
            throw error
       }
   }
   // overload all other access to return undefined, so that the value
   // still looks empty for code like:
   //
   // var auto = new autoviv(); 
   // if (typeof auto[4] == autoviv) {should run}
   // if (auto[4]) {should not run}
}

Answer 2

Uri Guttman's autovivification tutorial might be of some use.

Basically, it is the ability of hitherto untouched aggregates and members of aggregates to spring to life upon first use.

For example, I can do this:

#!/usr/bin/perl

use strict; use warnings;
use Data::Dumper;

my @dummy;

push @{ $dummy[0] }, split ' ', 'this that and the other';
push @{ $dummy[1] }, { qw(a b c d) };

print Dumper \@dummy;

Neither $dummy[0] nor $dummy[1] exist before they are dereferenced.

Now, if you are willing to forgo strict (which, you shouldn't be), you can also do things like:

use Data::Dumper;

@$x = qw(a b c d);
print Dumper $x;

whereby the undefined variable $x becomes an array reference because it is being dereferenced as such.

Answer 3

You can implement autovification-like behavior with creating say, an IDictionary<X,Y> that returns (and stores) a new IDictionary<X,Y> (e.g. recursively the same type) when a [] to an unset key occurs. This approach is used in Ruby to great success (an example) -- however, it's really not so useful in a statically typed language because there is no way to "get to" the leaf values cleanly -- at least in context of most existing contracts such as an IDictionary.

With the advent of dynamic, this may be possible in C# to do sanely, but I do not know.

Answer 4

How about something like this for a simple implementation of auto-vivification like behaviour of a Dictionary in C#? Obviously this doesn't handle it in the generic way that Perl does, but I believe that it has the same effect.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

//  The purpose of this class is to provide a dictionary with auto-vivification behaviour similar to Perl's
//  Using dict[index] will succeed regardless of whether index exists in the dictionary or not.
//  A default value can be set to be used as an initial value when the key doesn't exist in the dictionary

namespace XMLTest 
{
    class AutoDictionary<TKey,TValue> : Dictionary<TKey,TValue> {

        Object DefaultValue ;

        public AutoDictionary(Object DefaultValue) {
            this.DefaultValue = DefaultValue;
        }

        public AutoDictionary() {
            this.DefaultValue = null;
        }

        public new TValue this[TKey index] {
            get {
                try {
                    return base[index];
                }
                catch (KeyNotFoundException) {
                    base.Add(index, (TValue)DefaultValue);
                    return (TValue)DefaultValue ;
                }
            }

            set {
                try { 
                    base[index] = value ;
                }
                catch (KeyNotFoundException) {
                    base.Add(index, value);
                }
            }

        }
    }
}

Answer 5

I would recommend using extension methods instead of inheritance.

e.g.:

namespace DictionaryEx
{
    public static class Ex
    {
        public static TV Vivify<TK, TV>(this IDictionary<TK, TV> dict, TK key)
        {
            var value = default(TV);
            if (dict.TryGetValue(key, out value))
            {
                return value;
            }
            value = default(TV);
            dict[key] = value;
            return value;
        }

        public static TV Vivify<TK, TV>(this IDictionary<TK, TV> dict, TK key, TV defaultValue)
        {
            TV value;
            if (dict.TryGetValue(key, out value))
            {
                return value;
            }
            dict[key] = defaultValue;
            return defaultValue;
        }

        public static TV Vivify<TK, TV>(this IDictionary<TK, TV> dict, TK key, Func<TV> valueFactory)
        {
            TV value;
            if (dict.TryGetValue(key, out value))
            {
                return value;
            }
            value = valueFactory();
            dict[key] = value;
            return value;
        }
    }
}

Answer 6

Using indexers and C# 4.0 dynamics,

class Tree
{
    private IDictionary<string, object> dict = new Dictionary<string, object>();
    public dynamic this[string key]
    {
        get { return dict.ContainsKey(key) ? dict[key] : dict[key] = new Tree(); }
        set { dict[key] = value; }
    }
}

// Test:
var t = new Tree();
t["first"]["second"]["third"] = "text";
Console.WriteLine(t["first"]["second"]["third"]);

DynamicObject can be used for implementing different syntaxes also,

using System;
using System.Collections.Generic;
using System.Dynamic;

class Tree : DynamicObject
{
    private IDictionary<object, object> dict = new Dictionary<object, object>();

    // for t.first.second.third syntax
    public override bool TryGetMember(GetMemberBinder binder, out object result)
    {
        var key = binder.Name;

        if (dict.ContainsKey(key))
            result = dict[key];
        else
            dict[key] = result = new Tree();

        return true;
    }

    public override bool TrySetMember(SetMemberBinder binder, object value)
    {
        dict[binder.Name] = value;
        return true;
    }

    // for t["first"]["second"]["third"] syntax
    public override bool TryGetIndex(GetIndexBinder binder, object[] indexes, out object result)
    {
        var key = indexes[0];

        if (dict.ContainsKey(key))
            result = dict[key];
        else
            dict[key] = result = new Tree();

        return true;
    }

    public override bool TrySetIndex(SetIndexBinder binder, object[] indexes, object value)
    {
        dict[indexes[0]] = value;
        return true;
    }
}

// Test:
dynamic t = new Tree();
t.first.second.third = "text";
Console.WriteLine(t.first.second.third);

// or,
dynamic t = new Tree();
t["first"]["second"]["third"] = "text";
Console.WriteLine(t["first"]["second"]["third"]);