Here are the functions we'll need to compute our probabilities in C#:
double PH1 ()
{
return Utility.Product<string> (this.TermWeight, Globals.AllTerms);
}
double D ()
{
return Globals.TuningAlpha * Utility.Gamma (N ())
+ leftChild.D () * rightChild.D ();
}
double Pi ()
{
return Globals.TuningAlpha * Utility.Gamma (N ()) / D ();
}
double P ()
{
double pi_k = Pi ();
return pi_k * PH1 () + ((1.0 - pi_k) * leftChild.P () * rightChild.P ());
}
double R ()
{
return Pi () * PH1 () / P ();
}
double ProbabilityToOdds (double p)
{
return p / (1.0 - p);
}
double ROdds ()
{
return ProbabilityToOdds (R());
}
The marginal probability of clustering is given by function
R, and the marginal odds of clustering is given by
function ROdds.In the Scheme version, I proceeded to convert the program to odds space by substituting the definitions of
R, probability->odds,
Pi, etc. and then rewriting and simplifying the resulting
code. This is because in Scheme the name of the function and
the function itself are interchangable.Let's see how this works in C#. First let's try ProbabilityToOdds. In Scheme, we have this:
(define probability->odds
(lambda (p) (/ p (- 1.0 p))))
(define r-odds
(lambda (cluster)
(probability->odds (R cluster))))
And we simply replace the name with the definition:
(define r-odds
(lambda (cluster)
((lambda (p) (/ p (- 1.0 p))) (R cluster))))
But in C#, what exactly is ProbabilityToOdds defined as?
ProbabilityToOdds = ????It's a static method, not a first-class object. But C# has
delegate objects that can be used to act as if they were
first-class methods. We can do this:
Func<double,double> P2O = ProbabilityToOdds;And now we have a
delegate for ProbabilityToOdds. The
delegate is a first-class object. We can use it just
like we used ProbabilityToOdds. For example
double ProbabilityToOdds (double p)
{
return p / (1.0 - p);
}
static Func<double,double> P2O = ProbabilityToOdds;
double ROdds ()
{
return P2O (R());
}
That didn't get us very far. We sort of want to go in the reverse
direction. We want to make an unnamed delegate. You can do this in
C#.
static Func<double,double> P2O =
delegate (double p)
{
return p / (1.0 - p);
}
double ROdds ()
{
return P2O (R());
}
This is a little weird because it seems that the delegate
doesn't have a declared return type. It gets weirder. Let's
substitute P2O with the delegate.
double ROdds ()
{
return delegate (double p)
{
return p / (1.0 - p);
} (R());
}
Compiler error: ``Method name expected.''
It seems that the compiler is playing some tricks on us. Anonymous
delegates weren't originally in the language, and they aren't directly
supported by the runtime. However, the compiler understands what it
is we're trying to accomplish and arranges to create a good
simulation. At least in the first case. We confused it with the
second. With a couple of hints to the compiler, we can say what we
mean:
double ROdds ()
{
return ((Func<double,double>)
delegate (double p)
{
return p / (1.0 - p);
}) (R());
}
We can substitute R, too.
double ROdds1 ()
{
return ((Func<double, double>)
delegate (double p)
{
return p / (1.0 - p);
}) (((Func<double>) delegate ()
{
return Pi () * PH1() / P ();
}) ());
}
We'd better simplify this. It's getting a little messy. That second
function takes no arguments and is being applied to an empty argument
list. We can η-reduce it.
double ROdds1 ()
{
return ((Func<double, double>)
delegate (double p)
{
return p / (1.0 - p);
}) (Pi () * PH1() / P ());
}
It might not be immediately clear what I just did, so I'll re-set
this.
double ROdds1 ()
{
return ((Func<double, double>)
delegate (double p)
{
return p / (1.0 - p);
}) (((Func<double>) delegate ()
{
return Pi () * PH1() / P ();
}) ());
}
η-reduction is removing the function call apparatus (in green) and
using the computed value (in red) directly:
double ROdds1 ()
{
return ((Func<double, double>)
delegate (double p)
{
return p / (1.0 - p);
}) (Pi () * PH1() / P ());
}
When invoking a function, we compute the value of the operands, bind
them to the formal paramaters, and evaluate the body. In essence, we
do this:
double ROdds1 ()
{
return ((Func<double>)
delegate ()
{
double p = Pi () * PH1 () / P ();
return p / (1.0 - p);
}) ();
}
Now we can η-reduce, or we could if this were
syntactically allowed:
double ROdds1 ()
{
return
double p = Pi () * PH1 () / P ();
p / (1.0 - p);
}
I removed the function call apparatus just as I did before, but this
time it didn't work. The body of a function in C# consists of a
series of statements, but a call invoking a function is an
expression. You can't use a statement where an expression is
expected. Then why did it work before? There was a single statement
in the function body and it was a return statement. When we removed
the return, we serendipitously converted the return statement to an
expression. Since there were no preceeding expressions, we got away
with it. In the current case, however, have a problem.
We'll have to move any statements that were in the body of our delegate to a context where statements are permitted. With luck, there will be a context close enough that it won't change the semantics of the code. As it turns out, we're in luck this time.
double ROdds1 ()
{
double p = Pi () * PH1 () / P ();
return
p / (1.0 - p);
}
We were lucky because the context of the call to the delegate was the
first subexpression of a statement and we didn't have to move the code
very far. But if it were something more complicated, like, say,
this:
for (int i = 0; i < ((Func<int>)
delegate ()
{
object x = foo();
return bar (x, x);
})(); i++)
We're going to have more problems. The nearest place to hoist the
binding of x is outside of loop, and this will likely change the
semantics.
There is a hack to work around this limitation, but it is really very nasty. In C#, as in C, assignment is an expression rather than a statement. We can separate the binding of
p from
computing the value if we can figure out how to sequence the
expressions.
double ROdds1 ()
{
double p;
return
First
p = Pi () * PH1 () / P ()
then
p / (1.0 - p);
}
In C and C++, you can sequence expressions with a comma. This is one of those
things people use all the time in for statements, but
forget that it can be used elsewhere as well. You would write this:
double ROdds1 ()
{
double p;
// In C or C++ this will work.
// NOT IN JAVA OR C#
return (
p = Pi () * PH1 () / P (),
p / (1.0 - p));
}
Unfortunately, Java and C# have overlooked the comma expression.
Fortunately, they did not overlook the conditional
expression. We can abuse it to force our sequencing because the
predicate in the conditional is required to be evaluated first.
double ROdds1 ()
{
double p;
return ((p = Pi () * PH1 () / P ()) == 0.0 || true)
? p / (1.0 - p)
: 0.0;
}
The assignment is put in the predicate as part of boolean expression
that is always true, then the second expression is put in the true
branch of the conditional. The false branch is a dummy value of the
correct type.
I did say it was very nasty, but sometimes programming is a dirty job.
Obviously, we don't need to go this far for the problem at hand, this:
double ROdds1 ()
{
double p = Pi () * PH1 () / P ();
return p / (1.0 - p);
}
will do just fine.
Ok. This is ridiculous. People don't do this sort of stuff when they hack C, C# or Java. The reason is obvious. It's far too hard and confusing, even in this toy example. It would be insane to try to do this in real life code. Instead, of just cutting and pasting code from here to there, we'd look at the destination context, reason about how the return value is going to be used and how it could be best computed in the new context, and then rewrite the code at the destination to have the desired effect.
More to follow...
No comments:
Post a Comment