Editing Autovivification

In the [[Perl]] programming language, '''autovivification''' is the automatic creation of new [[Array data structure|arrays]] and [[Hash table|hashes]] as required every time an undefined value is [[dereferencing|dereferenced]]. Perl autovivification allows a programmer to refer to a structured variable, and arbitrary sub-elements of that structured variable, without expressly declaring the existence of the variable and its complete structure beforehand.<ref>{{cite book|last1=Schwartz|first1=Randal L.|last2=Phoenix|first2=Tom|title=Learning Perl Objects|url=https://archive.org/details/isbn_9780596004781|url-access=registration|date=2003|publisher=O'Reilly Media, Inc|isbn=9780596004781|page=[https://archive.org/details/isbn_9780596004781/page/42 42]|quote=This process is called autovivification. Any nonexisting variable, or a variable containing undef, which is dereferenced while looking for a variable location (technically called an lvalue context), is automatically stuffed with the appropriate reference to an empty item...}}</ref>

In contrast, other programming languages either:

# Require a programmer to expressly declare an entire variable structure before using or referring to any part of it; or
# Require a programmer to declare a part of a variable structure before referring to any part of it; or
# Create an assignment to a part of a variable before referring, assigning to or composing an expression that refers to any part of it.

Perl autovivification can be contrasted against languages such as [[Python (programming language)|Python]], [[PHP]], [[Ruby programming language|Ruby]], and many of the C style languages, where dereferencing null or undefined values is not generally permitted.{{efn|For example, Python raises an TypeError if None.__getitem__ is called. [[Null_pointer#Null dereferencing|Dereferencing]] a [[null pointer]] in C results in undefined behavior; many C implementations choose to raise a [[segmentation fault]].}} It can be compared to the HTML standard's "named access on the window object"<ref>{{cite web|url=http://www.whatwg.org/specs/web-apps/current-work/#named-access-on-the-window-object|title=HTML Standard. Named access on the Window object }}</ref> which results in corresponding globally scoped variables being automatically accessible to browser-based [[JavaScript]].

==Hashes==
It is important to remember that autovivification happens when an undefined value is dereferenced.  An assignment is not necessary.  The debugger session below illustrates autovivification of a hash just from examining it:
<syntaxhighlight lang="perl">
  DB<1> x \%h
0  HASH(0x2f1a248)
     empty hash
  DB<2> x $h{1}{2}{3}{4}
0  undef
  DB<3> x \%h
0  HASH(0x2f1a248)
   1 => HASH(0x2f1a260)
      2 => HASH(0x29a3c68)
         3 => HASH(0x2dc3038)
              empty hash
  DB<4>
</syntaxhighlight>
The debugger session below illustrates autovivification of a hash from assigning to an inner hash:
<syntaxhighlight lang="perl">
  DB<1> $h{A}{B}{C}{D}=1
  DB<2> x \%h
   0  HASH(0x83c71ac)
   'A' => HASH(0x837d50c)
      'B' => HASH(0x83c71e8)
         'C' => HASH(0x83c7218)
            'D' => 1
  DB<3>
</syntaxhighlight>
Hashes several layers deep were created automatically without any declarations. Autovivification can prevent excessive typing. If Perl did not support autovivification, the structure above would have to be created as follows:
<syntaxhighlight lang="perl">
  DB<1> %h = (A => {B => {C => {D => 1}}})
  DB<2> x \%h
  0  HASH(0x83caba4)
   'A' => HASH(0x83cfc28)
      'B' => HASH(0x83cab74)
         'C' => HASH(0x83b6110)
            'D' => 1
  DB<3>
</syntaxhighlight>

==File and directory handles==
Perl 5.6.1 and newer support autovivification of file and directory handles.<ref>{{cite web|url=http://perldoc.perl.org/perl561delta.html#File-and-directory-handles-can-be-autovivified|title=perl561delta - what's new for perl v5.6.1|website=Perl Programming Documentation }}</ref> Calling <code>open()</code> on an undefined variable will set it to a filehandle. According to perl561delta, "[t]his largely eliminates the need for [[typeglob]]s when opening filehandles that must be passed around, as in the following example:
<syntaxhighlight lang="perl">
for my $file ( qw(this.conf that.conf) ) {
    my $fin = open_or_throw('<', $file);
    process_conf($fin);
    # no close() needed
}
use Carp;
sub open_or_throw {
    my ($mode, $filename) = @_;
    open my $h, $mode, $filename
        or croak "Could not open '$filename': $!";
    return $h;
}
</syntaxhighlight>

==Emulation in other programming languages==

===C++===
The [[C++ Standard Library]]'s associative containers (<code>std::unordered_map</code> and <code>std::map</code>) use <code>operator[]</code> to get the value associated to a key. If there is nothing associated to this key, it will construct it and value initialize
<ref>{{Citation | url = http://en.cppreference.com/w/cpp/language/value_initialization| contribution = Value initialization | title = C++ reference | type = wiki}}</ref>{{Rs|date=August 2024|reason=Wikipedia:Reliable_sources/Noticeboard/Archive_440#cppreference.com|certain=y}}{{Fv|date=August 2024|reason=nothing in the source about 'unordered', 'map', or 'operator'}}
the value. For simple types like int or float, the value initialization will be zero initialization.

<syntaxhighlight lang="cpp">
std::unordered_map<std::string, std::vector<int>> a;
a["the answer"].push_back(42); // Autovivifies the a["the answer"] vector and then appends to it.
</syntaxhighlight>

Another example of counting occurrences of strings:

<syntaxhighlight lang="cpp">
std::unordered_map<std::string, int> counts;
while (auto& s = GetNextString()) {
  counts[s]++; // creates counts[s] if it doesn't exist and set to zero, then increment.
}
</syntaxhighlight>

A similar trick can be achieved with the <code>insert()</code> method, which returns an iterator to the element associated to the key, even if it already exists.

===Python===
Python's built-in <code>dict</code> class can be [[Subclass (computer science)|subclass]]ed to implement autovivificious dictionaries simply by overriding the <code>__missing__()</code> method that was added to the class in Python v2.5.<ref>{{cite web | url = https://docs.python.org/2/library/stdtypes.html#mapping-types-dict | title = Mapping Types — dict | accessdate = 2016-06-13}}</ref> There are other ways of implementing the behavior,<ref>{{cite web | url = https://stackoverflow.com/a/19829714/355230 | title = What is the best way to implement nested dictionaries in Python? | accessdate = 2016-06-13}}</ref><ref>{{cite web | url = https://gist.github.com/hrldcpr/2012250 | title = One-line Tree in Python | accessdate = 2017-12-27}}</ref> but the following is one of the simplest and instances of the class print just like normal Python dictionary objects.
<syntaxhighlight lang="pycon">
>>> class Tree(dict):
...     def __missing__(self, key):
...         value = self[key] = type(self)()
...         return value

>>> # Common names by class, order, genus, and type-species
>>> common_names = Tree()
>>> common_names['Mammalia']['Primates']['Homo']['H. sapiens'] = 'human being'
>>> common_names
{'Mammalia': {'Primates': {'Homo': {'H. sapiens': 'human being'}}}}

>>> # Famous quotes by play, act, scene, and page
>>> quotes = Tree()
>>> quotes['Hamlet'][1][3][3] = 'This above all: to thine own self be true.'
>>> quotes
{'Hamlet': {1: {3: {3: 'This above all: to thine own self be true.'}}}}
</syntaxhighlight>

===Ruby===

Ruby hashes can take a block specifying an object to be returned for non-existing indexes. These can be used to implement autovivificious maps.

<syntaxhighlight lang="irb">
irb(main):001:0> tree = proc { Hash.new { |hash, key| hash[key] = tree.call } }
=> #<Proc:0x007fda528749a0@(irb):1>
irb(main):002:0> lupin = tree.call
=> {}
irb(main):003:0> lupin["express"][3] = "stand and deliver"
=> "stand and deliver"
irb(main):004:0> lupin
=> {"express"=>{3=>"stand and deliver"}}
</syntaxhighlight>

===Java===

Java Map has a method <code>computeIfAbsent</code><ref>{{cite web | url = http://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function- | title = Map (Java Platform SE 8) | accessdate = 2015-05-17}}</ref> that can be used to emulate autovivificous maps.

<syntaxhighlight lang="java">
public static <K,V> Function<K, V> defaultDict(Map<K, V> map, Supplier<? extends V> supplier) {
    return key -> map.computeIfAbsent(key, k -> supplier.get());
}

public static void main(String[] args) {
    Function<String, List<String>> dict = defaultDict(new HashMap<>(), ArrayList::new);
    dict.apply("foo").add("bar");
}
</syntaxhighlight>

===PHP===

PHP arrays are natively autovivificious.
<syntaxhighlight lang="php">
$arr = array();
$arr["express"][3] = "stand and deliver";
</syntaxhighlight>
However, this only applies to assignment, and not array access.

=== JavaScript ===
[[ES6]] introduces a new {{mono|Proxy}} class that can be used to implement autovivification. With other features of JavaScript, this can be reduced to a single line of code:
<syntaxhighlight lang="javascript">
var tree = () => new Proxy({}, { get: (target, name) => name in target ? target[name] : target[name] = tree() });

// Test:
var t = tree();
t.first.second.third = 'text';
console.log(t.first.second.third); // or t['first']['second']['third']
</syntaxhighlight>

=== C# ===
C#, using indexers and C# 4.0 dynamics,
<syntaxhighlight lang="csharp">
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"]);
</syntaxhighlight>

{{Code|DynamicObject}} can be used for implementing different syntaxes also,
<syntaxhighlight lang="csharp">
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"]);
</syntaxhighlight>

==See also==
* [[Evaluation strategy]]
* [[Variable (programming)|Variable]]
* [[Vivification]]

==Notes==
{{notelist}}

==References==
<references/>

==External links==
* [http://perldoc.perl.org/perl561delta.html#File-and-directory-handles-can-be-autovivified perl561delta: File and directory handles can be autovivified]
* [http://sysarch.com/perl/autoviv.txt Autovivification in Perl: An In-Depth Tutorial]
* [https://web.archive.org/web/20060115055718/http://moonbase.rydia.net/mental/blog/programming/ruby/autovivification.html Autovivification in Ruby] - emulate Perl's autovivification
* [http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml A Use of the Y Combinator in Ruby] - Implements autovivification in Ruby with the Y Combinator.
* [http://rdoc.info/github/rubyworks/facets/master/Hash#autonew-class_method Hash#autonew in the Ruby gem "facets" adds autovivification on hash reads]
* [http://rubygems.org/gems/xkeys The Ruby gem "xkeys" facilitates nested structure traversal and autovivifies on array or hash writes]

[[Category:Perl]]
[[Category:Evaluation strategy]]
[[Category:Management cybernetics]]
[[Category:Articles with example Perl code]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Articles with example PHP code]]
[[Category:Articles with example Java code]]
[[Category:Articles with example C++ code]]
[[Category:Articles with example Ruby code]]