My Summer in Sunny San Diego

Let me preface this post with a warning: it's gonna get technical. It's just not possible to talk about an entire summers worth of software development without getting too technical for the average reader, so I apologize in advance. (Google is your friend!)

ViaSat's very military logo

So I had an amazing experience doing software development for ViaSat Inc this past summer, and I want to share some of the awesome technologies I got to work with! I was working with a team of two other interns---one of which, also goes to Harvey Mudd. Our initial task was to develop the equivalent of Netflix's "Chaos Monkey" but for ViaSat's core switch infrastructure. We had to switch gears completely when we got hit with the ridiculous policy that no interns could be signed into the core switch's NDA because of the 'likelihood we may work for a competitor in the future.' ... Wait? Isn't that the entire purpose of an NDA? Hmm... So we came up with a solution: Instead of writing a program like Chaos Monkey that would run various tests on the development infrastructure, we would write a highly extensible framework that allows the developers to write tests that would be run on the development infrastructure. Write code to run other people's code!

Even though our users were other developers, we wanted to make things as easy as possible for them to increase the likelihood of our project actually being useful. So we decided to allow the users to run ANYTHING! ... (that runs on Linux). Figuring out how to make this work involved learning a slew of shiny new system administration and cloud tools including Docker, Ansible, OpenStack, and did I mention Docker?

In the end, our final product was split amongst three repositories.

1. The Deployment Repository

This repository mainly consisted of Ansible playbooks and a Dockerfile. Ansible playbooks are similar to bash scripts in what they can accomplish, but they are wildly different in how they are written and how much simpler their syntax is. The playbooks would boot up a configurable number of slave and master VMs. They would configure these VMs according to their tasks, and finally pull and deploy our web interface repository, and our scheduler repository. In the end of a deploy--which could take up to 30 minutes--our entire infrastructure would be up and fully functioning. Ansible needs a few dependencies to be able to interface with Openstack, so I wrote a Dockerfile with all the dependencies that would automatically run the deployment process. This way, users would only need to have Docker installed to deploy our VM cluster.

2. The Scheduler Repository

The view from my office (just imagine a beautiful sunny day)

This repository took was deployed in the form of another job run on the infrastructure. It's task was to communicate with the web app and the database server, schedule the jobs to run randomly based on each job's configuration, and then go to sleep until it was needed next. In order to wake the scheduler up early, I had to write a signal handler, and a signal sender, that would ssh into the container that the scheduler job was running, and send the unix alarm signal (SIGALRM) to the running process. It was kind of hacky, but also very cool to figure out!

3. The Web Interface Repository

This repository contained mostly Python code, HTML, and Javascript. Our web framework was called Flask, and for pretty javascript forms and buttons we used Foundation. I'm most proud of my docker backend that I wrote to allow the web app to use the docker api and to start images for the ssh configuration feature. I used docker-py to do the api integration, and tutumcloud's images for the ssh serving docker images. This task was the most challenging part of the project. Some functions required communicating between various VMs, generating and serving secure ssh keys, and carefully testing for and catching errors. I needed to discern between server errors and user's dockerfile errors, which the system would need to handle. In the end, I am incredibly happy with how it turned out.

In hindsight, I would say that our team did a good job of avoiding hitting too many major roadblocks. We managed to be quite productive all summer. I had an incredibly fun experience at ViaSat and I'm looking forward to doing more software development in the future.

Thanks for reading!

Voxel Engines

First off, a Voxel Engine is a game engine that uses voxels, and voxels are simply 3d pixels. One of the most popular games that runs on a voxel engine is Minecraft.

A landscape from Minecraft

If you don't know, (how could you not know?!), Minecraft uses massive blocks (voxels) to form a highly sandboxed universe where players work together to build their own virtual worlds. To me, Minecraft seems to be just a demonstration of the incredible potential behind voxel-based sandbox games. I was enthralled in the game throughout high school. It was another world. A world where I was completely free to build whatever wherever and with whoever. I met people from all over the world and worked together to create complicated logistics systems and redstone circuitry, as well as beautiful mansions and cabins. All this, with voxels that are actually half the height of the characters!

Nowadays, voxel engines are getting much more complex and much more refined. These engines are able to achieve much more complicated worlds with more optimized algorithms written in higher performing programming languages than Java, which is the language Minecraft is written in. I believe that if voxel engines can continue to get more and more powerful, while remaining entirely customizable and modular, that they could soon become the future of virtual reality and video gaming in general.

A landscape from Voxel Farm

I recently stumbled upon the incredibly impressive voxel engine called Voxel Farm. Voxel Farm is written in C and C++ and is a highly advanced engine that allows relatively intuitive world building in a much more continuous sandbox world than Minecraft. As you can see from the image on the left, Voxel Farm looks just like a typical gaming engine. In many ways, Voxel Farm is a typical gaming engine. For example, it can output meshes in real time and work in tangent with many popular game engines like Unity or Cryengine, however in its backend, it is still a fully voxelized world.

Voxel Farm is being developed as a game engine and not as a game. While this is an obvious point, it definitely makes a huge difference. The developers are targeting other developers with much of their programming time, which will have some interesting effects. Now, I'm sure you might say, well how come someone couldn't simply use this game engine to build the next Minecraft? While I agree that this is a distinct possibility, it simply doesn't offer the huge potential that you get when you are in control of absolutely everything about a game. It is a freedom that cannot be matched, and it is one of the main reasons why Minecraft was such a success. Also, it is worth mentioning that the Pro package distributes the full source code to the buyer, so it is technically possible to change the inner workings of the game engine, however I have doubts that even this will be enough.

Despite my doubts, I really hope we get to see some great games come out of this project. And either way, I think the work that is being put into Voxel Farm is an excellent investment. It is pushing the limits of what voxels are capable of, and because of this, I believe it has some incredible potential! So look out for the future of Voxel Farm because it could be making some waves in the world of gaming in the next couple years.

More Cellular Automata

I'm back after a little more developing on my CA program, (see my previous post entitled 'Cellular Automata'), and a very educational conversation with reddit user /u/slackermanz, someone with much more experience making cellular automata that me. (Seriously, look at /r/cellular_automata, they have some very impressive patterns on there, and most of them are made by /u/slackermanz).

The modifications I have made to my program are making it such that each cell will not move, but will be able to eat cells in its near vicinity, and reproduce in a random direction. As mentioned previously, I implemented an energy value, which each cell starts out with, and if they run out of energy, they become food for other cells. If the cell has an excess of energy, they will reproduce. This produces the following pattern.

As you can see, there is an exponential expansion, and I am working to minimize this, since I think there will be more interesting patterns in an energy starved environment.

Another problem I am working to fix is an over-lapping of cells. Somehow in my code, multiple cells are able to occupy the same space, which is causing an over-creation of cells and lagging my program. I believe to make this more efficient, I will initially spawn cells for all spaces, then have my program set the cells in a state of dead, alive, or food, that way the number of cells is constant.

As always my code is on my github. Stay tuned for these modifications and optimizations in the near future, until then, thanks for reading.

What I did over winter break, and why it was a massive waste of time.

I want to talk about the myriad of obstacles that I encountered over winter break (2014 - 2015). Ever since the end of my senior year of high school, after writing a pretty dinky little 2D physics simulator, I had been really wanting to give it another dimension, but held back by the complexity of it. 3D graphics and physics gets quite complex, so simplify the enormous task, there are a host of tools that one could use, ranging from closed source production-quality game engines like CryEngine or Unity to the free and open-source tools that I chose to use, Ogre3D and Open Dynamics Engine. I chose the open sourced libraries because, (a) I exclusively use Linux, and Unity isn't available for Linux and (b) I am a Linux SysAdmin, what do you expect?.

An image of what some of the starter code rendered
This Ogre is a pain in my ass!

So at the beginning of my sophomore year, I decided upon Ogre3D after learning Cinder was unfortunately Windows and OSX only. So I tried to start working through the beginner tutorials but the provided starter code wouldn't even compile. The starter code's Makefile was just broken, with about four lines of options needing to be added to the autotools makefile.am and configure.ac. After getting in touch with a developer, who kept insisting I use CodeBlocks, a graphical IDE (ew gooey), I noticed that there were some very helpful comments on one of the autotools configuration pages that included exactly what I needed to get the starter code compiling. My question is, why hadn't these changes been made to the code? Finding this and getting it to work took up most of the first half of my semester, just to get the starter code compiling!

So I went into winter break hoping that my experience would smooth out, or that I would get over some threshold and finally understand how to make Ogre do exactly what I want in an intuitive way. After all it is object based, why shouldn't it be intuitive? Well, long story short: I was wrong. Ogre's syntax is incredibly verbose and complex. It's objects are not used in an intuitive way--it's data structures are sort of hybrids between self contained objects and nested-scoped static methods. For example, I struggled to be able to simply print to the program log, and that is because printing requires the following line of code in Ogre:

    Ogre::LogManager::getSingletonPtr()->logMessage("### Error parsing config file ###");

 "Ogre::LogManager::getSingletonPtr()" is a call to a static method within the LogManager scope, which is itself within the Ogre scope. That method will return a pointer to the Ogre::LogManager object, which can only be initialized once in the program. Then you can use that pointer to call logMessage(), which will add your message to the log. Here is the initialization of the LogManager object:

    Ogre::LogManager* logMgr = new Ogre::LogManager();
    Ogre::Log* myLog = Ogre::LogManager::getSingleton().createLog("myLog.log", true, true, false);

Honestly, I don't even have a complete understanding of what this code is really doing, I mean is logMgr a deferenced LogManager pointer to a pointer to the new LogManager object? What? After that line, we can completely ignore the existence of the logMgr object, because of course we will just use getSingleton() whenever we need to log. (what was the point of even making us write that line then?) But initializing the LogManager wasn't enough, because we need to create the log file, and put it into myLog, which we will never use again. If the logManager object was only meant to be initialized once, and used through getSingleton(), then why even make us be so verbose about it. These kinds of options should not need to be written explicitly. I mean, if I wanted to rename my log's filename, or specify whether to add debugger output to it, then I should be able to via these complicated ways. However, if I just want to print some message and don't really care, I am forced to add these highly complicated lines of code to my file just to do that. 

My entire winter break went like this. There was no way I had the time to fully understand all of the highly complicated syntax of Ogre, while also trying to tie in Open Dynamics Engine.

Open Dynamics Engine (ODE) is a rigid body physics engine, written in C. Naturally, it's interface was  incredibly different than Ogre's. While it was much less complicated and slightly much more straightforward, I ran into serious difficulties when trying to get it to play nice with the big bad Ogre. For example, all the calculations ODE ran would be returned to my program in the ODE-defined 3d coordinate object const dReal* and I was tasked with the requirement to decompose that object and turn it into what Ogre wants, Ogre::Vector3 s, in order for the object to be re-rendered in the corrected location. It was a constant battle trying to make the two get along, and even today they still don't behave. 

Well that got long and complex... In summary, I dove head first into the deep end of two very complicated and very different C and C++ libraries, and I emerged with a buggy hunk of code, from which I understand <60% and have written <40% myself. I previously thought that if I forced myself to use C++ then I would be a better programmer than all those cheaters using the easy languages like Python. I even started the break off with a few OpenGL tutorials before realizing that it was far too low level for the kind of things I wanted to do. Clearly, the same was true for Ogre and ODE. I learned C++ and C are production-level languages and programs that are even mildly complicated are usually written by many people over the course of many months, not by a hobbyist experimenting with 3D programming with a low work ethic (winter break is a break after all). 

All of this is ironic, of course, because the reason this blog exists is because of my research at ASU. At ASU, I was researching the differences between Java and C++ and concluded that C++ was more geared towards businesses with more value in their software and many more programmer (wo)man-hours to devote to it, NOT lazy CS majors trying to have some fun making a realistic 3D world. I guess this whole experience was a lesson in believing the results of actual research... 

Well, thanks for reading, and if you have any questions feel free to comment and I will try to answer them if I can. 

-Jeff

Cellular Automata

What is Cellular Automata? To define it I will take directly from wolfram:

"A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired."

It is pretty much the study of Conway's Game of Life. And there's a lot more to study than you'd expect. There are repeating patterns which return to their original states after a certain number of steps, and patterns in stable states that just don't move at all. The most interesting of all are the stable patterns that move, called spaceships or gliders, they will work their way across the grid until they collide with other things or just go off screen. Here are some examples.

A poor lost and lonely cell

So I decided to make my own implementation, with a twist. I would like to make the cells just slightly smarter than your average Conway's Game of Life cells. My rules are much more complicated that the typical rules in a cellular automaton, but I believe that it will still be possible to study some interesting interactions among the cells.

So, to each cell I have added the properties of hunger, and energy. I plan to have a cell that is out of energy and food to become food itself, and I plan to make cells that are fully energized and full of food to make new cells. Perhaps eventually the reproduction will require other cells around, but for now they will reproduce asexually. You can see the code on my Github.

At the moment my project is sort of halfway there, and needs another day or two of love and attention. I will try and get some work done this week and perhaps post my progress here when that happens. Thank you for reading, and feel free to comment if you have questions or comments.

Revival of my blog

Even though I originally created this blog to update my professors and advisers on my senior research project with Dr. Rida Bazzi at ASU, I have decided that the URL jeffmilling.blogspot.com is a perfect URL to use as a personal blog. Why let it go to waste?

I will be posting interesting things that I learn about, and small projects that I am working on. I can't guarantee regular posts, but I do feel like maintaining a blog is a good way to document stuff that I am working on and things that inspire me. These will likely be various things from my ridiculous range of interests. To list a few of the topics that I would like to post about: quantum information, quantum field theory, voxel programming, virtual reality, artificial intelligence, cellular automata, graphics programming, and last but not least linux. So thanks for reading, and I hope you learn a thing or two.

Multi-Core Computing

Most modern Central Processing Units (CPUs) are multi-core, and are advertised as such. For example, Intel's processors are usually advertised as "Intel i3 Dual-Core Processor" or "Intel i5 Quad-Core Processor" and even more recently they now have "Intel i7 Hexa-Core Processor." These processors can get a bit extreme, but what does it really mean, let's say, to run a Hexa-Core Processor? Well, on the right you can see a hand-drawn example of a single-core of a CPU, this core can execute a certain number of operations-per-clock-cycle (which used to be 1, but has since increased). Operations can be in the form of a logical operation (like ADD, AND, or XOR) on two binary values of a certain size and then reporting the result to wherever it needs to be. There are many different forms of CPU operations, but most of the actual computing is spent doing the previous example. Processing is just a bunch of math. Adding a second core to a CPU, as you should expect, can theoretically double your operations-per-clock-cycle value. Adding four can quadruple that value. Adding six can sextuple it, and so on and so forth. Within the last year, an exciting new engineering startup company by the name of Parallella began work on a 64-core processor, connected in a square matrix and multiplexed together. The future of multi-core computing is definitely an exciting one.

So at this point, it seems like the more cores, the better. Right? Not exactly, as there are many complications when it comes to programming for multi-core architectures. As an example, take a simple fibonacci sequence calculation. Inside the main loop, the current calculation, which is to add the two previous numbers, relies on the two previous numbers to already have been calculated, and so on and so forth. This greatly limits the amount of multi-tasking that is possible. So computer programs need to specify when multi-core, or "threaded" operations is allowed.

Below are two graphs showing ASU's computer's cores and their usage in a percentage. The graph on the top was recorded during testing of C++ programs, and on the bottom are Java Programs.

CPU usage per core during testing of C++ Applications

CPU usage per core during testing of Java Applications

So, clearly, there are staunch differences in these two pictures. So what exactly is happening that is causing these differences? 

Well, the difference lies in the languages. C++ requires the programmer to explicitly say when operations can be threaded, and when no specific allowances are written, no multi-core optimization takes place. On the contrary, Java allows the programmer to define specific threaded operations, but it does not require that in order to use multi-core optimization. Java's VM will run on multiple cores and distribute operations as they are compiled and executed. So, in conclusion, while C++'s graphs look clean and tidy, and Java's look like a mess, Java is actually optimizing it's code and taking more advantage of the CPU's architecture. 

So now I need to mention the program samples I ran. The CSE students wrote the programs to perform correctly, not efficiently. Maybe some over-achievers might optimize their code, but most students would just try to make the program do what it is supposed to, and when that works they turn it in. If this code were written by an actual software company, like Microsoft or Apple, they would almost certainly invest time in optimizing their code with multiple core architecture in mind. Students on the other hand, would not. 

This brings to mind some pros and some cons. On one hand professional companies have slightly more control over threaded optimization using C++, but on the other hand Java's automatic optimizations make programming much more convenient and can cut down significantly on runtimes of programs that maybe were written by one programmer who otherwise wouldn't have had the time to program lines and lines of code for threaded optimizations.

Of course, this topic will be more deeply analyzed and explained in my upcoming presentation.

Thanks for reading.

- Jeff 

Debugging: What is it?

Debugging is the process of removing "bugs" from code. There are many different ways to do this, and sometimes it can be a long, drawn-out, and frustrating struggle. The problem is: everybody makes mistakes. No one can sit down and write 1000+ lines of code without something going wrong and misbehaving. What distinguishes good coders from great coders, among other things, is their ability to debug. Over the past few weeks I have been doing a lot of debugging, and I have been working on my techniques. I have been getting faster and faster at identifying the root of the problem. There are a few ways that I have become familiar with to watch your code as it executes.

For code with lots of conditional branching, when something goes wrong, you need to know exactly where something goes wrong. In this case, a programmer can insert code that writes to the console at specific points in their code in order to follow-along. I am quite fond of just printing single "*" characters or maybe "+" or "-" characters after condition checks, this allows me to tell exactly which branch of code is being executed when the undesired behavior occurs.

Another way to do this is to print out all the objects involved in an event, and do the condition checks manually. This process can be quite tedious because the programmer needs to define how the object "prints" in text. But thanks to Eclipses' brilliant generate toString() functionality, this process is pretty pain-free.

The last process I have been using to debug my code is really only useful for visual programs such as my Physics Engine. I have defined a few methods in my Entity class that allow me to draw either the entity's previous path or the entity's velocity vector, or both. This allows me to visually watch what is happening behind-the-scenes of my application. In this picture, you can see the path and the velocity vectors of the balls, along with their direction, converted to degrees and printed above their image for clarity. This allows me to slow down their motion, and carefully watch their behavior. This technique has come in quite handy, as I've recently discovered and fixed more than a few minor bugs in my program.

Thanks for reading!

-Jeff

More Work on Collisions!

Scrawlings of a mad man

I have been struggling to successfully implement collisions between objects in my physics engine. It turned out a lot harder than I originally thought it would be. So after many revisions and a hours of frustration, I decided I needed to just sit down and write everything out. On the right is a picture of my desk, taken from my phone. This is how I tested out different mathematical algorithms and discerned which ones work all the time, which ones work some of the time, and which ones don't work at all. Writing down everything certainly helped my thought process, but I suspect that my peers here at ASU now think I am insane.

The red ball was placed 1 unit to the left of the blue one.

Here's what I managed so far. I have written a function of the Entity class that takes the angle of incidence of a collision and calculates its new angle for movement. This method took ages to get right, and now works on all 360 degrees. I have yet to add a dampening force yet, so currently the collisions seem overly explosive, but I'll get to it eventually! I have also written an event handler for the collision event which calculates the angles of incidence of both entities and calls their respective functions. This handler, however, needs a lot of work, because after only a little testing I have found some strange issues that most likely stem from there being no delay between bounces. Sometimes this results in the balls getting stuck inside of each other and weirdly vibrating off of the screen. A rather traumatic bug if you ask me. Here's a screenshot of a successful collision! Woo!


As always, thanks for reading!

- Jeff

Standardized Engines

Since I will be writing two copies of my physics engine, one in Java and one in C++, myself and my professor have found it necessary to attempt to keep the programs relatively similar. This will allow for the visual segment of my presentation to be as accurate as possible.  Dr. Bazzi asked me recently if I had based my programs on any standard foundations.  And I figured the best way to do that would be to keep the programs as true-to-life as possible, and avoid any over optimizations. The programs' calculations will be based on floating point calculations of the kinematic equations. These equations will keep the behavior of the objects in my engine as real-life as possible, and the floating-point variables will keep the values highly accurate. I will try to keep these physics calculations the bulk of the program's performance. In this way, I can maintain a relatively similar program between two different programming languages. The reason that is necessary is so that the comparisons between the two programs are relatively fair and equal, as we will be doing the same benchmark tests on them both.

I am aware things are getting quite technical as we approach the end of the project and begin work on the presentation. Thanks for reading.

- Jeff

Entity Collision

So I have been working on my Physics Engine recently, and I've happened upon a rather interesting conundrum. In logic, it is rather simple to detect when an falling entity collides with a box; It's easy tell when the ball hits the ground. However, it is not at all easy to tell when a ball hits another ball, the algorithms just don't work that way. After a little bit of research, I have discovered that no Java library handles anything to do with collision boxes of circles, and I have to write my own. My approach right involves a rather tedious and heavyweight process of calculating the distance from center to center of one ball to every other ball, then comparing that distance to the sum of their respective radii. If that number is greater than the distance, then I must do further calculations to determine the angle of collision. Like the picture on the left, I can use the differences in x and y coordinate values to calculate that angle, but what do I do from there? Well, once I have that angle, I plan to apply the great and powerful Law of Conservation of Momentum, to determine the outcome, and here comes the tricky part. In Physics, many of the collision problems we are required to solve are called elastic collisions, in which no kinetic energy is lost during the collision.

I have noticed, however, that in the simulation, this results in an unreal behavior of bouncing, which makes sense, considering all real-life collisions (including the one one the right) are inelastic. This means that I need to assign some arbitrary dampening value to collisions (in the previous post, this value was set to 10%). So, like I said, this wasn't easy, and I haven't quite got the algorithm working perfectly, yet. But I plan to keep working on it and get it nice and optimized for my presentation.

Thanks for reading!

- Jeff 

A Visual Conclusion

The time has come to start considering how to structure my presentation. While it is necessary to show my data that I have collected and show my statistical analysis, I need to keep it interesting. I plan to show, as well as prove, the complicated differences in Java and C++. It may be easier for me to stand up in front of a powerpoint full of numbers, and explain how I derived my conclusions, but I want to allow my audience to make those conclusions as well. It is for this reason that I have been working on a couple programs, one in Java and one in C++. These programs, called Physics Engines are designed to replicate the behavior of real objects (in my case, in two dimensions). Having the ability to visual demonstrate the differences in Java vs. C++, I think, is going to make my presentation that much more compelling. As Mr. Mac said to our Physics class, "You want to make your audience feel smart at the end of your presentation." I think that this is the best way to do that. To allow my audience to see for themselves the numbers and data that I can rattle off like an auctioneer, will make the biggest impact to my audience.

Thanks for reading,
- Jeff

// Commenting Code

Comments segments of text placed inside of source code that are not compiled. They serve simply to help the programmer and user to understand what the code is doing and why. There are many different types of comments, as well. Among others, there can be title comments, documentation comments, even legal comments. For example, many commercial Open Source projects must add in the GNU Public License, in the form of a large block comment, to the top of every file in their code.

/*
* This is a block comment.
* It is not compiled. It is only used for    
* notation purposes.
*/

Comments must be led by a specific language-defined character or characters that tells the compiler, "This is a comment, please ignore." As an example, Java uses double slashes (//), and Shell Scripts use pound symbols (#). In the picture is my testing script that I wrote two weeks ago. All the gray text is commented code. Obviously, I went a little overboard on the comments, as most of what was said in them can be easily inferred from the actual code. This style of commenting is typically frowned upon in larger programming projects, because some say that it clutters the code even more. A popular saying among programmers is, "Don't comment code, comment decisions." This limits comments to only the most important statements.

Interestingly enough, the Java JDK includes a tool, called Javadoc, that allows programmers to make code documentations from their comments, using keywords like "@params ... " and "@returns ... ." Using Javadoc may be one of the only times where it is necessary for the programmer to heavily comment every public method in all their classes.

In conclusion, comments are a good way for a programmer to write down what his intentions are for the code, and note any important or confusing code. As long as they are not overdone, comments can be incredibly helpful.

// Thanks for reading, as always!
// -Jeff

C++ Test Results Are In!

Feel free to click on this photo to enlarge it!

Above you can see some results that I have collected from the students of Dr. Bazzi. I concealed their full names for privacy reasons.  And of couse, Dr. Bazzi has many more students than just nine; I only used the programs that passed all of his tests and received 100%.

In the above tests, I had the compilers compile and run my own custom-written programs, which were considerably more cpu-intensive than the default test files. It is important to note that the students wrote these programs to pass the tests, not for speed, so optimization was not a factor in their programming. However, I believe that this fact does not ruin the integrity of the tests, as both Java and C++ programs will have been written sans-optimizations.

The runtimes are measured in seconds, using the GNU "time" command specified for "User Time." This means that the run times do not include system I/O, only pure computation times. The reason we do not want to record system I/O time is because that time can vary huge amounts on different machines and different hardware. It can even vary based on where the program is reading/writing in the computers file system!

 I find it quite interesting to see the massive amount of differences in runtimes between the programs (ak vs. cm, for example). And I will be going into much more detail about the nature of the tests run in my presentation, and this is by no means a formal explanation of the data. I just thought that you may want to see a little glimpse of some of the data I am collecting. Thanks for reading, and stay tuned!

-Jeff

Fighting bugs

For the last few days I've been fighting bugs. I've started work on a secret Java project (oh boy!), and as with any big project, there are always bugs. I've squashed a few of 'em, yet more seem to keep working their way out of the cracks, those sneaky little punks. Below is one of the nastiest bugs I've encountered so far. It's a null pointer exception seemingly coming from within the Java virtual machine, but I highly doubt that. Usually, these kinds of exception print out exactly which line of code is causing the issue, but this one is a little more difficult. What I have to do is retrace all my steps and work my way through the flow of variables until I find it, because someone somewhere is calling a method on a null object and it's my job to hunt it down and squish it.

So rather than fix it right this minute, I'm going to blog about it. Because why not?

When a critical error occurs within any higher-level programming language, the code does something called "throwing an exception." When the code throws an exception, it immediately stops what it's doing and follows its path all the way up the program stack, recording every step it takes so that it can print out something useful for the debugger. In the picture, all the lines that start with "at" are steps that the exception took before it printed this error message. If the exception works its way all the way up the program stack without being caught, it kills the program and prints its message to the computer's console. If the programmer is expecting an error like this and wants to handle it in a specific way, he can put the problematic code inside a try{} catch{} statement, and any exception that matches the exception specified in the catch's parameters will stop right there and execute the code inside the catch's block.

 Using these techniques it is possible to make a program more "robust" by being very thorough and catching any error that could possibly occur during normal program usage. If your program is designed for security reasons, like a bank account application, it is imperative that it catch any and all exceptions, so that the bank's servers can remain operational. Otherwise, it would be easy for any hacker to input some malformed code and gain access to the bank's private information and money. So yeah, in today's society, programmers can have just as much responsibility as an armed guard in a bank.

Well, thanks for reading, and everyone enjoy your spring break! (I know I will) 

-Jeff

A day in the life of a Computer Science student.

So today I impersonated a Computer Science student, and attended CSE 340, a class that Dr. Bazzi teaches. It was very interesting, and quite different from my current Computer Science class at BASIS. First of all, at the 340 level, the students are assumed to know how to program, so the course is not teaching students to program. Instead, it is much more abstract and theoretical, like the difference between learning Calculus and learning Calculus-based Physics. It is already assumed that you know Calculus when you enter a Calculus-based Physics class. For example, in my current CS class we learned about variable types and their significance. In CSE 340, we learned about what makes data types equivalent and to what extent can we allow them to be equivalent. Let me explain.

Equivalence Types:

There are two basic forms of equivalency, name equivalency and structural equivalency.

According to name equivalency, we can say that two types are equivalent if they are declared to be of the same built-in types or the same programmer-named type. This is a simple definition, created by the syntax and semantics of specific programming languages, but why are they defined this way? What are the underlying reasons for name equivalency? That's where structural equivalency comes into play.

Structural equivalency is where the definitions get much more complicated. When we got to this point in Dr. Bazzi's class, he projected a sheet of information onto the board that looked more to me like Math than Computer Science. I quickly copied down five definitions of structural equivalency.

The following are the limitations that Computer languages must follow when defining their variable's equivalency rules, called permissive structural equivalency.

We can say T1 and T2 are structurally equivalent if
1. T1 and T2 are the same basic type 

2. T1 = pointer to t1
     T2 = pointer to t2 

3. T1 = struct {
a : t1;
a2 : t2
}
     T2 = struct {
         a : t1
 a2 : t2
    }
    and ti is tructurally equivalent to t'i for i'=1 to k 

4. T1 is array range1 of t1
     T2 is array range2 of t2
     AND
  a) range1 and range2 have (1) the same number of dimensions and (2) the same number of entries in each dimension

  b) t1 and t2 are structurally equivalent 

5. T1 = fuction of (t1, t2, ... tk) returns t
     T2 = function of (t'1, t'2, ... t'l) returns t'
 AND
  a) is structurally equivalent to t'i and
  b) t is structurally equivalent to t'

It's amazing how much Computer Science is similar to Math. As Dr. Bazzi told me in our first meeting, "Math is very important. Computer Science is just another way to write Math."

I enjoyed getting a glimpse into the world of a Computer Science student at ASU, and I hope you enjoyed reading about it. Stay tuned!

-Jeff

Finally, Data!

Below, you are seeing a Terminal output of one of ASU's Ubuntu servers. I ran my new and improved script on it, and finally, I got data! After hours of debugging my stupid mistakes, I finally got it to work. On the top of the screen is my verbose output version I had to write in order to debug the problems, and on the bottom is the data. It's not much now, but it will grow. With this tool that I have written I can easily modify the commands to test different aspects of the computer language, and print it to the terminal. I plan to gather all this information into spreadsheets and use it to create both comprehensive and comprehendible graphs for my audience.

Ubuntu's XTerm successfully running Jeff's Testing Script v2.0

About the Script: 

I rewrote my first shell script to be much more robust and much more comprehensive. I cracked down on integer overflow and avoided executing any commands inside my timing loop besides the target program. On top of that, I rewrote my timing function to average the results of over 20 tests, giving me much more accurate, and much more trustable data. While testing my script, I noticed that the first result  of the timing tests was always slightly slower than the others, I suspect this is due to some program initializations that go way over my head. Regardless, I took this into account in my script and subtracted the first value from every test in order to reduce any inaccuracies caused by it.

In conclusion, I have finished construction of my program testing script, a tool that is going to help me collect the necessary data I need to back up claims in my report. Next thing I need to do is begin gathering all the data on as many programs as necessary. That's all for this week, and thanks for reading!

-Jeff

More Shell Scripting!

A quick program I wrote for testing runtimes.
Actually, I was testing the testing of runtimes.
Gotta love testing!

So I wrote version one of my testing script on Monday and ran it on ASU's server. It did alright but there were some errors and I was not certain that the runtime data I was getting could be trusted. This is because I was using the GNU date command, which is supposed to fetch the current UNIX time in milliseconds since the last epoch, in 1970. As you can probably tell, that is a very large number. So large, in fact, it would sometimes overflow the variable's range, and I was sometimes getting ridiculous negative numbers. So, back to the drawing board. Today I built a small program in C++, as shown to the right, that calculates the first million Fibonacci numbers, which only takes about 0.117 milliseconds. I can use this program as a target for my runtime testing script while I'm debugging it.

So that's what I've been doing, testing and writing and testing and writing. I'm learning a lot about shell scripting, about C++, and about Computer Science in general. I've been using an amazing tool I found, called TextMate. It is an open source text editor specifically designed for programmers. It can compile and run just about any programming language you throw at it, all inside the app. It's very impressive. I actually just talked to the main developer, Allan Odgaard, yesterday on IRC and told him so. I would highly recommend this to any of my fellow programmers running OSX.

Thanks for reading!

- Jeff

I am compiling compiled compilers.

On Friday, Dr. Bazzi offered me the opportunity to run some tests on some of his student's programs from the compiler project. So I have begun work on that. Basically, what I need to do is test the programs to make sure they are functioning correctly, then I need to time their execution and compile all of that data into a spreadsheet for further use. It's quite interesting how the student's compilers are tested. What I am given is a list of programs written in a simplified code that the student's compilers should be able to work with. I am also given a list of expected outputs of the student's programs. So I need to compile all the programs, run them on every test file, and make sure that their output matches the expected output. Sounds kind of tedious, right? Wrong!

Instead of doing all that work manually which would take hours and probably days, I'm doing it with a bash script. A bash script is a very high-level kind of code that is written in a computer's command prompt. Bash scripts are incredibly useful for automating tasks.

My friend and fellow researcher, Mohsen, showed me a script that he wrote in order to grade his students on their project. He ran the script and a few minutes later it had generated a huge matrix of 0s and 1s, which he could directly import into a spreadsheet for grading. I found it incredibly fitting that Computer Science students were graded in 0s and 1s.

So I'm writing a bash script to test the programs, and I'm also writing one to time the programs, so that I can take data regarding their typical run times. Although these programs are not designed to be fast, I feel that I have a large enough sample to record an typical run time for both Java and C++.

My goal for this project is to generate plentiful data that I can use for graphs on my presentation. To do so, I must congregate all of the student's programs into one spread sheet for data, which leads me to the title: I am compiling compiled compilers. Thanks for reading!

-Jeff

I am compiling a compiler.

I started my first large-scale programming project today. The problem I am solving was made by Dr. Bazzi for his Computer Science class 340. It is essentially a simplified version of a compiler. If you don't know, a compiler is the program that turns a source code, written by a programmer, into something that the computer can execute. What this program has to be able to do is input a file of source code, and output a file of compiled code. An additional task that Dr. Bazzi has issued to his student was that the program must also be able to execute that file of compiled code.

The only difference between the assigned compiler and a real compiler is simplified programming languages. The input file is written in a very bare-bones and basic language, and the compiled code does not have to be machine code, but rather an intermediate type of code that the program can execute at a later date.

So in conclusion I am writing a compiler that compiles a simplified programming language into another language, and then executes it. The compiler that I am writing, as with all programs, must be compiled, which leads me to the statement: I am compiling a compiler.

Thanks for reading,
- Jeff