My Pages

Wednesday, November 24, 2010

Dynamic versus Static Scoping

Dynamic and static scoping both have specific places in programming. We're going to discuss what the difference is and why the differences can make a difference in your program.

What is scoping
When we are talking about scoping, we are mainly concerned about the bindings of variables. In other words, where they have been defined. In some languages such as Perl there is no actual need to define a variable but that is a discussion for a different day. Regardless, bindings of variables show that they are variables and of what type they are. Below you can see the bindings of the variable x and variable y as being an integer and float respectively.

int x;
float y;

x = 10;
y = 3.14;


When we begin talking about scoping, we are specifically talking about scoping within higher order functions, closures, and Lambda Functions. Why? Because this is where scoping really matters within the variables. For example, in a language such as C, there is no purpose to talk about static versus dynamic scoping because everything is static. It will make more sense once we begin talking about it. Essentially variable bindings decide what variable a specific variable is talking about. For example, we KNOW that x is referring to int x.

Static Scoping
This is the scoping style that most people are used to and is the standard. So let's look at an explanation; essentially, the variable that is free (so during a closure or higher order function) is bound to the closest variable when the function is defined. An example is shown below.

var x=20;
var newfunc = f();
newfunc();

function f() {
  var x = 10;
  return function s() { print x; };
}


So, what prints out? You may or may not be surprised to find out that "10" will be printed out. Why? Because the x that is bound is the x from within f(); this is because the variable is bound statically and usually at compile time.

Dynamic Scoping
This is the scoping style that most people are not used to and can sometimes provide really strange results during programming. So let's look at an explanation; essentially, the variable that is free (so during a closure or higher order function) is bound to the closest variable in the activation records during run time. So what does this mean? The variable is bound to whatever the closest variable name is when the function is executed.

function d() {
  var x=20;
  var newfunc = f();
  newfunc();
}

var x=30;
d();

function f() {
  var x = 10;
  return function s() { print x; };
}


In the example shown above, one may be surprised to see that the output would be "20"; but why? the reason is quite surprising. The x is a free variable that must be bound at runtime; so when we actually execute newfunc() we look back through the activation records until we find a variable x that can be used. So we look at the AR for newfunc but find no x. We then check the AR for d and find that there is a local variable x defined as 20. This becomes the binding for our x. Now below you can see one more example of this.

function d() {
  var newfunc = f();
  newfunc();
}

function n() {
  var x=30;
  d();
}

n();

function f() {
  var x = 10;
  return function s() { print x; };
}


In this instance, the output changes again; now we see "30" as the output. Why? Let's step through it. We execute newfunc() and we see the free variable x that we need to bind. We then check the AR of newfunc but find no definition of x. We then look in the AR of d. Again, we see no definition of x so we continue up the AR's to n's definition. Here we now find an x which we then use which was defined as "30."

Let's get an example of both in Perl; static scoping is done via the my operator and the local operator provides dynamic scoping. Please note that by using the local operator, "use strict" will cause an error with using the variable and will say that the variable is not declared. Let's look at both examples.

Static
The output is "10", again, notice that the $x is bound to 10 from when the Lambda function is created.

sub f() {
  my $x = 10;
  return sub { print $x . "\n"; };
}

my $func = f();
my $x = 20;
&{$func}();


Dynamic
The output is "20", again, notice that the $x is bound to 20 from when the Lambda function is actually executed.

sub f() {
  local $x = 10;
  return sub { print $x . "\n"; };
}

my $func = f();
local $x = 20;
&{$func}();


Why is this useful?
Well... Let's be honest, essentially it's like passing a variable to a function. However, you could set it up so that you could dynamically change a function's internal variable if all variables were free dynamically scoped variables. This would allow for other functions to change the meanings of the functions without having to pass all the variables in. In my experience this is really not that useful. But knowing what the difference is and knowing how to tell which mode a variable is assigned to (in languages like Lisp and Perl that support both) is important. Or if you end up having to maintain a piece of code that uses dynamic scoping, you will know what exactly it means and the side effects of them.

Higher Order Functions (in Perl)

What is a higher order function and why exactly would I use one? Well let's look first at what a higher order function is.

What is a higher order function?


There are many languages that support higher order functions (2nd order, 3rd order etc...) and many of them are pretty straight forward. Languages such as Ruby, Lisp, Scala, and Javascript fully support higher order functions. In languages such as Lisp they are normally referred to as Lambda functions. Now that we've been talking tons about different names and who supports higher order functions; let's look at the original question. What is a higher order function?

A higher order function is a function that does processing on another function. To be exact, depending on the order of the function will depend on whether IT is calling or returning a function. We'll look at both of these examples later, but for right now just know that there are many different orders of functions. Let's look at an example of a higher order function (NOTE: This is not code from an actual language but resembles Javascript)

Returning a function
function f() {
  return function (y) {
    return y * y;
  }
}
var newfunc = f();
var x = newfunc(10);




Passing a function to a function
function f(x) {
  return x(10);
}

function t(n) { return n * n; }

f(t);
f(function (n) { return n * n;});


Let's take apart both of these examples, first we see another function defined within f() without a name (this is known as a Lambda or anonymous function). The function itself does a very simple y * y calculation where y is defined as a parameter that the function takes when being executed. As you can see by the next portion, we execute this by running f() which returns the newly created function which we can then execute at any other time.

Looking at the second example, we can see that f(x) is defined as x(10). This means that we are assuming that x will be a function which takes at least one argument. Continuing in the code where can see where we created another function t(n) which takes a single argument and return n * n. As we can see, we execute f() by passing t as the function to execute. The last portion shows that we can actually pass a Lambda function to f(x) denoting that we do not actually have to have a full function to execute it.

Now, in both of these examples we've looked at 2nd order functions; this means that the functions we are returning and the functions we are accepting are 1st order functions themselves. 1st order functions do not accept or return any other functions, these are just your normal everyday functions. So what would it mean to have a 3rd order function? This would be a function that either accepts a function that accepts/returns a function or a function that returns a function that accepts/returns a function.

Examples in Perl
The first question you might be asking is why am I explaining this in Perl? Well mainly because this is what I program in on a day to day basis right now and as such I felt that it would be best in a specific project to create higher order functions which forced me to figure out how to do them. I couldn't find a whole lot of information online about creating them which is why I am writing this now.

So the example that we have below is a simple function that returns a function and is called immediately afterwards. The key is the dereferencing of the CODE() object which is what the return value is of function f().

sub f() {
  return sub { my $x = shift; return $x * $x; }
}
my $duplicate = f();
print &{$duplicate}(10) . "\n";


As shown above, we can see that the Lambda takes a single argument and multiplies itself by itself. We store that code piece in the variable $duplicate then dereferences and executes the code "&{...}" We're going to look at another example where we have a hash and for one element of the hash we store the new function.

my %tvar = {};
$tvar{'newfunc'} = f();
print $tvar{'newfunc'}(10) . "\n";


In the example shown below, we have a second order function accepting a function.

f2($) {
  print $_[0](10) . "\n";
}
f2(f());
my $newfunc = f();
f2($newfunc);


Notice that f2 takes a single argument. This argument is then treated as a function and is executed. We don't need to dereference when we call the execution of the parameter. The important thing to note here is that we can take the function that is passed to f2 and call it at some other point in the future.

Quick overview of Closures
Since Lambda functions are so closely intertwined with Closures; I'll give a quick overview of what a Closure is. This should give you a much better view of what you can really do with higher order functions. Closures are really simple in theory, a function that is considered a Lambda function can reference variables contained in the containing function. (Again, we are using a fake language resembling Javascript).

function f() {
  var x = 10;
  return function (y) { x *= y; return x; };
}
var newfun = f();
print newfun(10) . "\n";
print newfun(10) . "\n";
print newfun(10) . "\n";


Notice that x is defined within f() and is used within the returned Lambda function. This works because although x will be out of scope once f() completes; this is called a closure where the Lamdba function "closes over" the variable x within its scope with the variable x that is out of scope. Now I am not going to go into dynamic versus static binding but that might be something to look at on another post. Essentially, x lives on within the Lambda function and the only thing that will be able to access it will be the Lambda call.

So what happens when this runs? We end up with the output "100", "1000", "10000"; why? Because we can continue to operate on x as if it were a real variable that we had originally declared. How is this useful? Imagine if f() took a parameter that set x. Now we can set the starting position of x for the returned function. This allows us to limit the number of times that we would need to create a function explained next.

Why is all of this useful?
In the previous example, if we had added that parameter to f(); we can now create tons of functions by just changing the parameter being sent to f(). Let's look for example at the example below where we define f().

function f(x) {
  return function (y) { x *= y; return x; };
}
var start10 = f(10);
var start20 = f(20);
var start30 = f(30);

print start10(10) . "\n";
print start20(20) . "\n";
print start10(10) . "\n";
print start30(30) . "\n";
print start10(10) . "\n";


Notice that we just created 3 different functions where x {10,20,30}. Also note that the results of running the code above is "100","400","1000","900","10000". See how the x is its own in each new function, this gives us the ability to create many different functions by creating a higher order function which can generate our other functions.

Sunday, November 21, 2010

Where is FOSS now?

According to Mozilla 86% of it's revenue comes from Google. This made me wonder what would happen to Mozilla if Google decided to revoke funding and focus on developing Chrome more. Many people are already starting to switch to Chrome which, at some point, one would consider this to be a conflict of interest. Why? Well, if they put an ad for Chrome on Google homepage and the homepage of Mozilla links to Google... Well you get the idea.

Mozilla (Firefox, Thunderbird) are one of the best examples of FOSS (Free/Open Source Software). Users have never once paid for the software that they are using; however, I would like to point out that they ARE paying for it with ad sales. What are Ad Sales? If you use Facebook then you'll notice the adds on the right hand side of the page. These are paid advertisements (i.e. the company that the Ad is supporting paid Facebook to put that ad up) that are targeted towards people whom Facebook feels will purchase those products or click on the ad itself.

Of course, many people get angry about the ads and how annoying they are. Many others feel that software should be free and should not have to have ads. The problem with this thinking is that you end up with software that is either 1/2 done, full of bugs, or worse becomes vaporware. This occurs because if the developer(s) are not receiving any funding from the users of the product; then they must have a full or multiple part time jobs as their main source of income.

This is bad because the developers are usually unable to focus directly on the software itself. Even if there is a group of 2-3 people it becomes hard to make decent progress. So why am I talking about this? Because I feel like people who complain that all software should be free and there shouldn't be all of this marketing on the sites really don't understand what it takes to create and support a piece of software.

I do believe in paying for software; I believe that if I am going to own a copy of Microsoft Office or Windows then I should have a legitimate copy of it. One might ask why I would prefer to pay for the software; my comment is that I know I am keeping another developer employed as long as I purchase the software. Now I am a Unix user and I do quite a bit of development in Unix; and to this I would be more than happy to address.

In my time of developing for Unix; I have seen many changes within libc between 4,5,6 and libssl, regex.h etc... Some of the things that I've seen are when functions get deprecated or when functionality gets changed and you are forced to go back and make changes in your code, notably with #ifndef's, to get around the changes depending on where the application will reside (i.e. you need to now support 3 different versions of a function call that changed in each version). This is the life of FOSS developers.

The FOSS community is pretty soulless in their ability to make things backward compatible. Many times the people who work on the *nix kernel or some other development library don't really care that much for preserving the original functionality and usually don't care. Their facet is that you are using their library and you are at their mercy if they decide to change something. Note that this is where I see the disconnect in the FOSS community. Watching some application that someone wrote that I found really useful that the guy doesn't want to keep up anymore fail because I did an apt-get upgrade.

Sadness then ensues when a function that was linked against no longer exists etc... As such, I'm now have 2 choices; either A) I settle for some half-assed solution, or B) I fix the code from the original application. This of course is what some would reason I should do, pick up the code and fix it, this is noted but if I was not a developer then this would be much harder than anything (as I would have to learn how to program). So why would I bring this up? Because if you look at the Window system; they provide a level of backward compatibility that is completely redeculous.

Windows has a level of backward where you could run an application from Windows 3.1 on Windows 7. Why? Because the developers for Microsoft has ensured that all changes to library functions fix an error in the function but do not change the underlying functionality of the function. They also do not remove functions after they have been created. So what is the difference here? Easy, one is a fully supported application that people develop all the time and are paid for the supported and continued development of the product (Microsoft) versus an application that people are asked to donate money to (Linux Kernel).

Why did I bring up the example with Facebook/Mozilla earlier? This was to show that although people THINK that Facebook is free; someone is still paying for the product.

Sunday, November 7, 2010

New Computer & Post about new project!

So I have finally rebuilt my main rig and it is currently a beastly machine. I am of course no stranger to gaming as I have gamed for most of my life. Starting with the ever popular Commander Keen up to the Halo [123] etc... Although increasingly I find myself more infatuated with the older games than the newer ones. Which of course makes me ponder why I spend some odd chunk of change to rebuild a rig that clearly does not need to be this powerful. But then I remember, ah yes I want to code.

My machine is an Antec 900 case with a Corsair 850w power supply. The video card is an older BFG GTX275 with a 160GB Raptor and 1TB WD 7500 and Edirol MA-10D monitors. All of this was previous hardware and now on to the new stuff.


  • Intel Core-i7 950

  • 12GB DDR3 1600MHz

  • ASUS Sabretooth x58

  • Zalman 9700 (with i7 kit)

  • LG DVD Burner



So, why the DVD burner you ask? Because the newer motherboards no longer come with PATA connectors. So of course, my previously purchased DVD Burner is no longer useful and I am forced to purchase another SATA drive. So much fun, but hey $35 isn't bad for a DVD Burner now.

The machine is running quite well; everything works except of course my keyboard. The fun part about doing an upgrade (especially because of catastrophic hardware failure) is that you tend to find a piece of hardware that had some other issue which may have caused your actual failure. In this case I am convinced that my keyboard shorted out my old Fatal1ty board. Regardless, I threw that one out and settled in with my old Dynex until I remembered that I had a Cherry ML4100 lying around. I put that on and am currently typing with it until my wife gives me my card back and I can purchase a Space Saver 104 from Unicomp.

Regardless, I don't see much use in complaining; the machine is running fantastically and I cannot wait to see what this thing can do with some VM's. Right now I am more concerned about getting VS2010 up and running with XNA4.0 so that I can work on getting a new game out. Hopefully that will be my next project and this machine will last me until the end of it.

This is the topic of my discussion today. Currently I am working out the details of my game; I want to pay homage to the old school Mario/Sonic style games but I don't want to just create some basic knockoff. Instead I think I am going to instantiate some uses of static variables within classes in managed languages and do what would be "enmity" on a global scale. As your enmity increases for a specific enemy type, the more they will try to kill you in crazy ways. For example, based on your enmity, as jump to try and jump on the head of an enemy they will try to navigate faster/slower to be right next to you when you land. The faster they move, the better reaction they will have to being able to be directly next to you.

Or in some instances, being able to force you off a ledge early etc... Of course, with enmity comes a way to decrease it; each enemy type will have a foe enemy type. If you kill an enemies foe, you will decrease your enmity for that enemy of course increasing your enmity for the foe type. Of course you will be able to gain points and finish the game, however the majority of points will come from killing enemies. This means that to get any kind of decent score, you will have to increase your enmity.

What will be interesting is to have multiple endings based on the amount of enmity you have for each enemy type (i.e. if you have more enmity from turtles than mushrooms or koopas etc...). This will also give the ability for harder achievements since one could be made for finishing the game with the most/least enmity from XXX enemy group. The holy grail basically being to finish the game with 0 enmity across the board. This would mean that you would have to finish the game without killing a single enemy.

Can't wait to start working on this, should be quite interesting to see what happens!