I think this is a very important question, because it's so critical to keeping things straight and Perl's syntax doesn't make it very obvious what's going on. I have many scripts that I can easily dive back into as a result of my data structure comments, and that I wouldn't have a hope of interpreting a month later without the comments.

I use something sort of similar to what you are proposing, except I don't use $placeholders, I keep it English-like, and I modify some of the syntax.

In brief, quoted strings are literals, unquoted strings are abstract data type descriptions (possibly defined explicitly later). (parens) mean a list, [brackets] mean an array ref, and {curlies} mean either a hash or hash ref (they're easily distinguished by a human, since it can only be a hash at the outermost level.) <angle brackets> mean an array ref with a fixed number of elements -- in other words, a tuple. If things get complicated, I use a simple word or phrase as a symbol that I expand later (using a colon to denote "is of type").

So for example:

# { student name => grade }
my %grades = ( "Bob" => 3.2, "Alice" => 3.9 );

# { node name => [ child node ] }
my %graph = ( A => [ "B", "C" ], B => [ "D" ] );

# { student name => { "age" => age, "grade" => GPA } }
my %students = ( "Bob" => { age => 34, grade => 3.2 } );

# { name => <age, children, dirty flag> }
# where children : { child name => 1 }
my %table = ...;
print "Bob is $table{Bob}->[0] years old.\n";
print "His children are ", join(" ", keys %{ $table{Bob}[1] }), "\n";
print "Is Guido his child? ";
print ($table{Bob}[1]{Guido} ? "yes" : "no"), "\n";

# My version of your example
#
# Returns: [ stat chunk ]
#  where stat chunk :
#    { "originals" => { id => value },
#      "changes" => { id => value },
#      "means" => <mean of originals, mean of changes>,
#      "variances" => <variance of originals, variance of changes>
#    }
#
# or you could give a symbolic name to the { id => value } things.
[download]

This loses some nice properties of what you wrote -- eg, you can no longer use it as a direct template for constructing expressions. But I find that being able to drop into English for anything complicated is a good tradeoff for losing the additional rigor.

Then again, I do see the use of a rigorous description -- a couple years back, I wrote a tool that took a syntax somewhere between yours and mine and automatically applied it to a value to extract out the desired data. I won't describe the exact syntax, but it allowed things like:

  my %map = ( a => 1, b => 3, c => 2 );

  # Set @keys to ('a', 'b', 'c')
  # and @values to (1, 3, 2)
  match('{ @keys => @values }', \%map);

  my %map2 = ( a => { name => "Bob", children_ids => { Alice => 132, M
+abel => 81 } });
  # Set $etty to "Mabel"
  match('{ ? => { children_ids => { $etty => 81 } } }', \%map2);
[download]

and similar tricks. I found it quite handy, except that I really wanted it to declare the variables (@keys, @values, $etty) lexically in addition to initializing them, and I did this before I had heard of source filters. Or perhaps before they existed; I'm not sure.