tag:blogger.com,1999:blog-75734550958586509972024-03-16T01:23:04.465-06:00Real World AcademiaEvanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-7573455095858650997.post-14536174637274614262014-12-25T09:43:00.001-07:002014-12-25T09:43:07.749-07:00Scratching an itch with GolangI frequently find mp3's of conference talks, or discussions online that I want to listen to, but listening to plain mp3's posted on the internet on my phone is cumbersome. I'd really prefer the mp3's wrapped up in a podcast. My phone's podcast application is much more feature rich than my phones mp3 player. I decided that it was time to scratch this itch and write a program that would take directories of mp3s and turn them into ad-hoc podcasts.<br />
<br />
I decided to write the program using Go. The last time I really wrote in Go I was writing C/C++ code for my day job and Go felt magical. Now I'm using Python so I thought it would be interesting to see how my perceptions of the language would change now that I'm accustomed to writing in Python. So here is what I've discovered or rediscovered about Go after not having not used it for a while.<br />
<br />
<br />
<ol>
<li>Go's support for concurrency still feels magical, and the tools for detecting data races are wonderful. With Python I've avoided concurrency altogether and instead opted to use multiple Python processes. With C/C++ I would use threads, but do so knowing that sometime in the future I or whomever maintained the code would encounter a deadlock, or a data race issue.</li>
<li>I felt was less productive in Go than I would have been in Python. As I tried to figure out why I thought about three issues. First I realized that I'm simply not as familiar with Go's standard packages as I am with Python's so I spend more time looking up standard functions. The second is that Go forces me to decide whether to handle or ignore errors and I feel guilty ignoring errors. With Python it's much easier to ignore (intentionally or not) exceptions that are raised. With Go most of the time I either assign returned errors to a variable and handle it or assign it to '_' and am constantly reminded of the ignored error. Third I think that Go may simply be more verbose than Python.</li>
<li>The ability to run and modify examples directly from Go's documentation pages is really helpful. With python when I want to experiment with an API, I would bring up a REPL. That's great but being able to do it directly from the documentation page with Go is more convenient because all of the setup code has already been written.</li>
<li>Spending time formatting code in Python feels like a waste of time when I'm accustomed to using Go's automatic code formatting.</li>
</ol>
<div>
The code for ad-hoc podcasts is on <a href="https://github.com/efarrer/adhoccasts" target="_blank">github</a>. The code is not not pretty nor well factored, but it's working (on my machine). Patches of course are welcome.</div>
Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-41434647542182746232013-10-17T22:11:00.000-06:002013-10-17T22:11:07.876-06:00Announcing Testosterone Driven Development (TDD)<br /><br />It seems like every few months someone announces a new development methodology that will result in drastic improvements to software production and is the "one true" way to develop software. Perhaps creating your own development methodology is a rite of passage that all mindful developers must pass through. You may be reading this and thinking "Oh great here we go again. Some nutjob is going to announce his new development methodology." Well, I'm sorry to disappoint but I am not going to announce a new creation today. The development methodology that I'm introducing today is not one that I created but one that exists naturally in the universe. I am not its creator. I am only its discoverer and spokesperson. This development methodology exists as a fundamental building block, like atoms, quarks, energy and bacon. Today I'm proud to announce a development methodology I lovingly call "Testosterone Driven Development".<br /><br />I would love to tell you about how Testosterone Driven Development will change the world, but that's unnecessary. It already has. I'd love to tell you about how it will become so popular it will sweep the globe, but it already has. It's only a matter of time before you encounter this methodology, so you better start studying now, or you risk being left behind. There's a chance some members of your team are using it already, but perhaps, like the spinning of your CPU's fan, its presence is so constant and unchanging that it's become invisible to you, only noticeable when you focus your caffeine sharpened senses on it.<br /><br />As your humble guide, I will share with you the gospel of Testosterone Driven Development (hereafter called TDD, because no one has ever used that acronym before).<br /><h2>
1. TDD'ers never profile before optimizing</h2>
Because you have intimate working knowledge of your program, and all of the libraries it uses, and the libraries they use, and the kernel your program is running on, and the machine code instructions that will be generated by the compilers and the number of cycles each machine code instruction will take, and the scheduling of threads, the lock contention, the interaction of the garbage collector, and its I/O latency. Since you have all of that in your head, you know exactly where the bottleneck is and can optimize it by injecting hand written assembly into your code. Anyone that doesn't hold all of that state in their brain is a wuss and should not be allowed on your team.<br /><h2>
2. TDD'ers never compile before pushing</h2>
Your fingers are so full of testosterone that they simply can't type code that doesn't compile. In fact your code is so manly it will even compile in the presence of syntax errors. Does anyone really think the 98 pound weakling of a compiler will even be able to emit a warning with your code? NO!<br /><h2>
3. TDD'ers never write unit tests</h2>
Unit tests are for developers that write bugs. TDD'ers don't write bugs. If you think your code needs unit tests, you should put your keyboard back in your purse and go home.<br /><h2>
4. TDD'ers never write comments</h2>
Comments only encourage the weak to modify your code. You don't want them leaking any of their estrogen on your manly code, so don't encourage them by adding comments.<br /><h2>
5. TDD'ers always use global variables</h2>
Your testosteronian influence is global. Why shouldn't your variables be too? Yes there are some little pre-pubescent boys that can't hold global state and every execution path that could mutate the global state in their tiny immature minds while simultaneously hammering out studly man code. But do you really want those little boys hanging around? Of course not! Their screams might interrupt your flow and their tears might fall into your keyboard. Or worse, your Red Bull.<br /><h2>
6. TDD'ers never use third party libraries</h2>
<div>
You wouldn't use a junkie's syringe now would you? You don't want their diseased guts in your pristine god-like body. You know third party libraries are nothing more than binary encoded diseased guts. They were written by people who are dumber and weaker than you. You know that third party libraries only work for other developers that don't write manly software.<br /><h2>
7. TDD'ers never consult with the team before making big changes</h2>
</div>
<div>
Real men don't ask permission to go to the bathroom. Why would ask permission to make sweeping architectural changes to your team's code base? You know they aren't smart enough to understand your plan anyway, just make the change and let them bask in your glory when you're done.<br /><h2>
8. TDD'ers never use revision control</h2>
Sure if you start at a company and they keep their code in git, mercurial or some other garbage system, you'll clone the repo and get to work. But you certainly aren't going to merge or check in small changes on a daily or weekly basis, you'll wait until it’s all done. Delivering source code to the team is like giving your mom a puppy for Christmas. Sure you could give her the puppy in bits and pieces and then on the last day give her a needle and thread for her to assemble the fur and guts. But you know your mother will want the puppy delivered in one piece. Likewise your team won't be able to comprehend the brilliance of your code unless you deliver it in its final state.<br /><h2>
9. TDD'ers only use revision control to revert other people's changes</h2>
OK so there is one and only one reason for a man to use revision control and that is it makes it really easy to throw away others' crap commits. Let's go back to the puppy analogy. So here you are boxing up a puppy to mail to your mother and one of your "teammates" says it would be a smart idea to to shove his pet cockroach right in the puppy's eye socket. Do you try and "merge" the roach into the puppy's eye? Do you try and make the puppy's eye work around the roach? No! You’d never allow someone to do that to the puppy and so you should never allow anyone to do that to your code. If someone commits some code that conflicts with your masterpiece, revert it immediately and then get back to the job of being a real man.<br /><h2>
10. TDD'ers don't need bug trackers</h2>
Bug trackers track bugs. You don't write bugs, you write beautifully crafted perfection. Setting up software to track the zero bugs you are going to write is a waste of time. Even if you did write a bug just for fun, there are no bug trackers which are manly enough to be able to track the hypothetical bug that you would write. You would crash the bug tracker, and reporting that bug back to the sissy that wrote the bug tracker would crash it too.<br /><h2>
11. TDD'ers modify production code</h2>
Sure you could first modify the code on your machine and then push the code to a staging area for some idiot to "test" and then push your code to production. You could also not date that hot girl in your class but first date her grandmother, and then her mother and then finally date her. But you testosterone doesn’t play stupid games. It’s laser focused on getting hot chicks and writing sick code. You focus your testosterone fueled laser beams on hand optimizing the code for the production server environment. You make your change to production then go home early to take that hot girl to the monster truck rally.<br /><br />My hairy man friend. Keep your eyes open for examples of TDD in the wild, your testosterone focused on radiating chiseled bits of code, your Red Bull close, and don't you ever let sissies tell you how to do your job.<br /><br /><i>Special thanks to <a href="http://thesmithfam.org/blog/">Dave Smith</a> for his encouragement, ideas, and understanding of the English language.</i></div>
Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-62833470221119647852012-06-13T22:22:00.000-06:002012-06-21T23:29:19.462-06:00Unit testing isn't enough. You need static typing too.When I was working on my research for my Masters degree I promised myself that I would publish my paper online under a free license, as soon as I had graduated. Unfortunately there seems to be an unwritten rule of Graduate School research. You spend so much time focusing on a single topic of study that by the time you graduate you are sick of it. So more than year later I'm finally putting my paper online. For those that don't want to read the full paper (it's not terribly long for a research paper at 60 pages, but it's no tweet either) I'll include a shorter summary below. The summary will omit some important information and so if you would like to provide constructive or destructive feedback I ask that the feedback be directed towards the full paper and not the quick summary.<br />
<div>
<br /></div>
<div>
For me research I wanted to test the frequently cited claim by proponents of dynamically typed programming languages that static typing was not needed for detecting bugs in programs. The core of this claim is as follows:</div>
<div>
1. Static typing is insufficient for detecting bugs, and so unit testing is required.</div>
<div>
2. Once you have unit testing static type checking is redundant.</div>
<div>
3. Because static typing rejects some valid programs static typing is harmful.</div>
<div>
<br /></div>
<div>
Despite the fact that I had heard and read this claim many times I couldn't find any research to back this claim up. So I decided to conduct an experiment to see if in practice unit tests really did obviate static typing for error detection. I also wanted to see if developers frequently use dynamic constructs that can't be expressed in a statically typed programming language.<br />
<br />
My experiment would consist of finding examples of open source, unit tested programs written in a dynamically typed programming language and manually translating them into a statically typed programming language. I would then quantify how many (if any) defects were detected by the type checker, and how many dynamic constructs couldn't be directly expressed due to being rejected by the static type checker. I should emphasize that for this experiment I would *not* be simply rewriting the program, but doing a direct line by line translation from one programming language to another. I would not count defects that were not detected by the type checker, nor any defects that could not be reproduced in the original program.<br />
<br />
Before starting the experiment I needed to choose a dynamically typed programming language that I would translate programs from. I also needed to choose a statically typed programming language that I would translate those programs to. The criteria for the dynamically typed programming language were as follows:<br />
<ul>
<li>The language should be dynamically typed</li>
<li>The language should have support for and a culture of unit testing</li>
<li>The language should have a large corpus of open source software for studying</li>
<li>The language should be well known and considered a good language among dynamic typing proponents</li>
</ul>
<div>
With this criteria in mind I selected Python. The next step is to chose the statically typed programming language. For this selection I used the following criteria:</div>
<div>
<ul>
<li>The language should be statically typed</li>
<li>The language should execute on the same platform as Python</li>
<li>The language should be strongly typed</li>
<li>The language should be considered a good language among static typing proponents</li>
</ul>
</div>
I selected Haskell for the statically typed programming language.<br />
<br />
The next step was to choose some unit tested programs to translate from Python into Haskell. I randomly picked four projects, <a href="https://python-gpsd.googlecode.com/" target="_blank">The Python NMEA Toolkit</a>, <a href="https://code.google.com/p/midiutil/" target="_blank">MIDIUtil</a>, <a href="https://code.google.com/p/grapefruit/" target="_blank">GrapeFruit</a> and <a href="https://bitbucket.org/sirpengi/pyfontinfo" target="_blank">PyFontInfo</a> from the <a href="https://code.google.com/" target="_blank">https://code.google.com/</a> and <a href="https://bitbucket.org/" target="_blank">https://bitbucket.org</a> source code hosting sites.<br />
<br />
<h2>
The Python NMEA Toolkit</h2>
<div>
The translation of the Python NMEA Tookit from Python to Haskell led to the discovery of nine type errors. Three of them could be triggered by malformed input and the other six by an incorrect usage of the API. Only one of the type errors would have been guaranteed to have been discovered had full unit test coverage been employed. Additionally there was one run time error that could be eliminated once static typing was applied. Two unit tests could have been eliminated as their only function was to perform type checking. No dynamic constructs were used that could not be directly translated into Haskell.</div>
<div>
<br /></div>
<h2>
MIDIUtil</h2>
<div>
The translation of MIDIUtil led to the discovery of 2 type errors. Only one of the type errors would have been certainly been caught had full unit test coverage been employed. An additional run time error could also be eliminated by static typing. None of the unit tests only tested for type safety and so none of them could be eliminated. The MIDIUtil code did use <i>struct.pack</i> and <i>struct.unpack </i>which could not be directly translated as they both rely on format strings that determine the type of arguments and return values. However in all cases the format strings were hard-coded, so the Haskell version could instead use hard-coded functions instead of the hard-coded format strings with no loss in expressiveness. Had the MIDIUtil code stored these format strings in external configuration files then the program would likely have required a re-design to express it in a statically typed language.</div>
<div>
<br /></div>
<div>
<h2>
GrapeFruit</h2>
</div>
<div>
The translation of GrapeFruit to Haskell did not result in the discovery of any type errors. A single run time error could be eliminated by static typing. Additionally a single unit test could have been eliminated that only tested for type safety. No dynamic constructs were used that could not be directly translated into Haskell.<br />
<br />
<h2>
PyFontInfo</h2>
<div>
The translation of PyFontInfo resulted in the discovery of six type errors. Two run time errors could be eliminated by static typing. A single unit test could have been eliminated. The PyFontInfo code also used <i>struct.pack</i> and <i>struct.unpack </i>which can not be directly translated, but a simple work around exists.</div>
<div>
<br /></div>
<div>
<h2>
Results</h2>
</div>
<div>
The translation of these projects revealed that all of these projects could have been written in a statically typed programming language with only minor code changes. Furthermore, unit testing did not seem to be an adequate replacement for static type checking. A total of seventeen type errors were discovered. All of the type errors that were discovered were the result of bugs in the original Python code that were not discovered by the unit tests. Many of the bugs existed in code that did have unit test coverage.</div>
<div>
<br /></div>
<div>
<div>
<h2>
Conclusion</h2>
</div>
</div>
<div>
The results of this experiment indicate that unit testing is not an adequate replacement for static typing for defect detection. While unit testing does catch many errors it is difficult to construct unit tests that will detect the kinds of defects that would be programatically detected by static typing. The application of static type checking to many programs written in dynamically typed programming languages would catch many defects that were not detected with unit testing, and would not require significant redesign of the programs.<br />
<br />
<h2>
Future Work</h2>
The translation of these four projects do provide an interesting data point on the effectiveness of unit testing for defect detection. I hope that others will try to conduct similar experiments on more samples of dynamically typed programs.<br />
<br /></div>
<div>
<br /></div>
<div>
The full length paper is located <a href="https://docs.google.com/open?id=0B5C1aVVb3qRONVhiNDBiNUw0am8" target="_blank">here</a>.</div>
<div>
The original Python code and the Haskell translation are <a href="https://docs.google.com/open?id=0B5C1aVVb3qROS2dib0NtbzZCaVE" target="_blank">here</a>.</div>
<div>
<br /></div>
</div>
</div>Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com124tag:blogger.com,1999:blog-7573455095858650997.post-59519330305268315222012-05-24T07:42:00.002-06:002012-05-24T07:42:34.715-06:00The Go Programming Language Has ExceptionsIt seems like every other post I read about Go states that the Go programming language doesn't have exceptions. This is followed by either an excited explanation on why exceptions are bad and why you don't want them anyway, or an explanation on why Go is deficient because it doesn't have exceptions. It's time to set the record straight. Go has exceptions. Now I really want to believe it. So close your eyes and repeat the following ten times "Go has exceptions". It's OK I'll wait for you to finish. Are you done? Do you believe it? OK now that you know that Go has exceptions in your heart of hearts. I should probably point out that Go really doesn't have exceptions. If you look at the <a href="http://golang.org/ref/spec" target="_blank">language spec</a> you'll see that there is no section on exceptions. There is no "try", "catch" or "throw" keywords, and nothing on "finally". Even though Go doesn't have exceptions it does have constructs which exhibit exception like semantics that can be used when you want to use exceptions for error handling. Their just not called exceptions.<br />
<br />
In the Go language spec there is a section on <a href="http://golang.org/ref/spec#Handling_panics" target="_blank">handling panics</a>. If you read it carefully you'll notice that the description of "panic" sounds a lot like the description of "throw". You may also notice that "recover" sounds lot like "catch", and you can use "defer" in place of "finally". There is no replacement for the "try" key word as Go's "panic", "recover" and "defer" work on function boundaries not on "try/catch" scopes. So there you have it. Even though Go doesn't have exceptions it does have constructs that can be used to handle exceptional error conditions and that closely resemble exceptions.<br />
<br />
This raises the question. If Go has exception like constructs, why do people frequently claim that it doesn't have exceptions and you only handle errors via returning an "error" value? I think there are two reasons for this. First of all in the early days of Go there was no "recover" keyword. Any call to panic would terminate the program so people got used to the idea that Go didn't have an exception mechanism. Secondly the convention is for packages to handle any uses of "panic" internally and then to return error values to their callers. This convention means that you never have to worry about recovering from someone else's panic when calling into a Go package. You can however use exception handling internal to your package or in your application, but you don't have to. So it's possible to write Go code and never encounter exceptions. Ensuring that a libraries panics won't leak into your code solves many of the problems with exceptions.<br />
<br />
So can we please stop saying that Go doesn't have exceptions? While it may be technically accurate it's misleading. Instead why don't we just say that Go has two complementary error handling mechanisms, one is by returning error values, but much nicer than C's, the other is exception like, but it solves many of the issues with exceptions.<br />
<br />Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com9tag:blogger.com,1999:blog-7573455095858650997.post-30210215843304545012012-05-01T22:45:00.000-06:002012-05-01T22:46:09.004-06:00Making Elastic Applications More Friendly in GoMany networked applications are elastic. They'll use as much or as little bandwidth as available. For example web browsing, email and ssh sessions will continue to function properly over lower bandwidth connections. However many applications such as audio or video streaming are inelastic and require a minimum bandwidth in order to work properly. If you download email over a dial-up connection it may take a long time but it will still work. If you stream video over a dial-up connection it will likely not play correctly. Unfortunately many elastic applications are written to use as much bandwidth as possible and so they may interfere with inelastic applications. For example if you run iTunes while streaming video in a browser iTunes will use as much bandwidth as it can, even if ends up interrupting the streaming video. A simple solution to this problem is to add controls to elastic applications to limit how much bandwidth they'll use. Both the curl and wget command line utilities provide such controls, but applications with such controls seem to be the exception rather than the rule.<br />
<br />
A few weeks ago I started rewriting an application in Go for managing podcasts. As I frequently get internet connection over a 3G connection I wanted to make sure that this application didn't monopolize my network connection. I needed a way to limit the amount of bandwidth that my podcast application would use. As I started working on a solution I recognized that it may be beneficial to others. A bit of work and a lot of fun later <a href="https://github.com/efarrer/iothrottler" target="_blank">iothrottler</a> was born.<br />
<br />
Using <a href="https://github.com/efarrer/iothrottler" target="_blank">iothrottler</a> is quite easy. You create an 'IOThrottlerPool' with the maximum amount of bandwidth that should be used by clients of the pool, and then add clients by calling the 'AddReader', 'AddWriter', 'AddReadWriter', or 'AddConn' methods. These methods return types who's bandwidth are limited by the pool. Of course the pools bandwidth limitation can be dynamically adjusted by calling the 'SetBandwidth' method. More detailed documentation and examples are provided by the package.<br />
<br />
Implementing this package in Go was really fun. Go's interfaces make it easy to add network bandwidth control to both new and existing applications. Go's interfaces also mean that you can use <a href="https://github.com/efarrer/iothrottler" target="_blank">iothrottler</a> to limit other types of IO such as file IO.<br />
<br />
If you're writing an elastic application in Go please consider bandwidth throttling to your application. Bandwidth throttling makes your user's lives much better.<br />
<br />
Bug reports, pull requests, feature requests and questions about <a href="https://github.com/efarrer/iothrottler" target="_blank">iothrottler</a> are always welcome.<br />
<br />
Happy Hacking!Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com2tag:blogger.com,1999:blog-7573455095858650997.post-34289082705115176242012-04-03T17:07:00.000-06:002012-04-03T17:07:35.920-06:00Object Oriented GoBecause Go doesn't have classes some have concluded that it's not an object oriented language. This is simply not true. I thought I'd share a simple problem that I needed to solve in Go in an object oriented way. Note that this won't demonstrate all of it's object oriented capabilities but it shows how one can create simple objects with methods.<br />
<br />
When writing code I've frequently used a technique for poor mans profiling where you start a timer, perform a set of operations and then see how much time has elapsed. This technique is not a substitute for real profiling tools like valgrind, but it sometimes is handy and sufficient. In C++ or Java I'd create a Timer class that will get the current time when it's constructed and then add an elapsed() method which will return how many nano/milli seconds have passed since the object was constructed. I needed this for a Go project I'm working on and this is how I did it:<br />
<br />
First of all I define a new type.<br />
<br />
<script src="https://gist.github.com/2294489.js">
</script>
This code defines a new type Timer that will have the same representation in memory as the time.Time structure but it's treated as a new type by the type checker. This means that if you try to call a time.Time method on a Timer object you'll get a compiler error. You can however convert a time.Time to a Timer and vice-versa by type casting.<br />
<br />
Now that we have a new type lets create a function for creating a new Timer. In Java we'd probably call this method timerFactory, but will just call it StartTimer().<br />
<br />
<script src="https://gist.github.com/2294549.js">
</script>
The time.Now() call returns a new time.Time object representing the current date and time, which we then type cast to a Timer and return it.<br />
<br />
Now we want to add a method to our Timer object that will return the number of nanoseconds that have elapsed since the Timer was created.<br /><br />
<script src="https://gist.github.com/2294587.js"></script>
The ElapsedNanoseconds() method gets the new date and time with time.Now() and subtracts the original time. We must cast the Timer to time.Time because it's a different type, and then we return the number of nanoseconds that have elapsed.<br />
<br />
We can now use our new Timer type as follows:<br /><br />
<script src="https://gist.github.com/2294614.js">
</script>
That's it! This works great as is but sometimes you don't need nanosecond resolution, millisecond resolution might be just fine. So lets add a new method to our Timer type to get the elapsed time in milliseconds instead.<br />
<br />
<script src="https://gist.github.com/2294655.js">
</script>
<br />
While this code works perfectly fine, the code will make it easy for us to write a bug. Consider the following:<br />
<br />
<script src="https://gist.github.com/2295466.js">
</script>
This code creates two Timer objects and attempts to compare the elapsed time between them. Unfortunately the units on the shortDelay are nanoseconds and the units on the longDelay are milliseconds. Comparing these values this way would make our High School Algebra teachers sad. Luckily we can fix this by defining new types for the nanosecond and millisecond delays.
<br />
<script src="https://gist.github.com/2295532.js">
</script>
We defined two new types Nanosecond and Millisecond. Each are based off of int64 so they'll have the same memory layout as an int64, but they're treated as different types by Go's type system. Now if we try and write code to compare these values we get an error message like "invalid operation: shortDelay > longDelay (mismatched types Nanosecond and Millisecond)". We're using the type system to enforce units on time! Now wouldn't it be nice to be able to convert from a Nanosecond to a Millisecond? We can do that by adding conversion methods to the Nanosecond and Millisecond types.<br /><br />
<script src="https://gist.github.com/2295568.js"></script>
We can now fix our buggy use of Timer like so.
<br /><br /><br />
<script src="https://gist.github.com/2295575.js"></script>
<br />
That's it! We created three new types Timer, Millisecond, Nanosecond (they would be classes in C++/Java) and one factory function and three new methods. The full code with the example usage can be downloaded and executed by typing "go run main.go".
<script src="https://gist.github.com/2295653.js"></script>Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-41716477502831793282011-12-20T23:23:00.002-07:002011-12-20T23:24:21.284-07:00Android development on Ubuntu 11.10 OneiricI decided to play around with Android development but I had a hard time finding good instructions on how to set up the Android development environment on Ubuntu 11.10. With a little trial and error I've figured it out. I'm posting my notes in hopes that they will be useful to me in the future and possibly to others also. The aren't a complete step-by-step guide and they assume you're comfortable with the Linux command line, but hopefully they'll be useful.<br />
<br />
<ol>
<li>Download and untar/gzip the Android SDK</li>
<li>Install the JRE</li>
<ol>
<li>sudo apt-get install icedtea6-plugin openjdk-6-jre openjdk-6-jdk ia32-libs</li>
</ol>
<li>Install ant</li>
<ol>
<li>sudo apt-get install ant</li>
</ol>
<li>Set your JAVA_HOME and CLASSPATH</li>
<ol>
<li>export JAVA_HOME=/usr/lib/jvm/java-6-openjdk</li>
<li>export CLASSPATH=/usr/lib/jvm/java-6-openjdk/lib</li>
</ol>
<li>Update the build tools</li>
<ol>
<li>cd android*; ./tools/android update sdk --no-ui</li>
</ol>
<li>Download eclipse (Helios release) (Note the one in the Ubuntu repositories doesn't seem to work)</li>
<ol>
<li>google-chrome www.eclipse.org/downloads/</li>
</ol>
<li>Untar eclipse</li>
<ol>
<li>tar -xvf ./eclipse*.tar.gz</li>
</ol>
<li>Install the eclipse Android plugin</li>
<ol>
<li>eclipse : Help -> Install New Software ...</li>
<li>enter: "Android Plugin"</li>
<li>enter: "https://dl-ssl.google.com/android/eclipse/"</li>
<li>Select 'Developer Tools'</li>
<li>Click "Next"</li>
</ol>
<li>Restart eclipse</li>
<li>Select the Android SDK</li>
</ol>
<div>
At this point you should have the Android SDK and eclipse installed and configured for Android development.</div>
<div>
<br /></div>
<div>
Here are some notes on doing Android development if you prefer to live on the command line instead of living in eclipse.</div>
<div>
<br /></div>
<div>
<ol>
<li>Create and Android Emulator</li>
<ol>
<li>cd android*; ./tools/android -> Tools -> Manage AVDs</li>
</ol>
<li>Start the Android Emulator</li>
<ol>
<li>cd android*; ./tools/emulator -avd <emulator_name></emulator_name></li>
</ol>
<li>Create a new Android project</li>
<ol>
<li>cd android*; /tools/android create project --target android-14 --name HelloAndroid --path ../HelloAndroid.git --activity HelloAndroidActivity --package com.mydomain.helloandroid</li>
</ol>
<li>Compile your project</li>
<ol>
<li>cd ../HelloAndroid.git; ant debug</li>
</ol>
<li>Push your project onto your running Android emulator</li>
<ol>
<li>ant debug install</li>
</ol>
</ol>
</div>Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com3tag:blogger.com,1999:blog-7573455095858650997.post-8872257668828984902011-08-23T22:48:00.000-06:002011-08-23T22:48:11.224-06:00Why you should get a college degree<span class="Apple-style-span" style="font-size: large;">Introduction</span><br />
I've been thinking about why it's important to get a college degree for many years and have finally decided to write down why I think it's important. I've heard many arguments over the years both for and against college. I'll try and address those arguments here. I should point out that my arguments may only apply to those going into a technical field (Computer Science, Electrical Engineering, Mechanical Engineering), but many of the arguments may apply to non-technical fields. Since I don't fully understand these fields, nor do I fully understand the college experience for non-technical degrees, I am likely not qualified to discuss the related benefits or costs.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">Background</span><br />
Since many of my arguments will be based on empirical evidence, I believe my personal background is relevant. My career goals have been to be a Software Engineer. Computer Programming has been a long hobby and passion of mine. I started working as a Computer Programmer before I started college. Since I was working in my desired field, I didn't think that college would be that important. I did, however, decide to get my bachelors degree as career insurance in case I later needed or wanted to change careers. At the time, I didn't think there would be much educational benefit (I felt I already had many of the skills and knowledge that I would need for my career), but it seemed like a good idea. Many of the advanced CS courses I took showed me that I did have a lot to learn from college and I continue to use the knowledge I gained from my undergraduate studies at work.<br />
<br />
A few years after getting my bachelors degree, I decided to go back to get my Masters Degree. Graduate school was more of a hobby than a career advancement strategy. I enjoyed reading papers and learning new things, and I wanted to get experience doing academic research and writing academic papers on my research. Just like with my Bachelors degree, I've been pleasantly surprised at how much I've learned while getting my Masters Degree. I've now graduated, and since my school work is done, I have had a lot of time to review my schooling and to think of the costs and benefits of my undergraduate and graduate work.<br />
<br />
<span class="Apple-style-span" style="font-size: large;">Addressing the Myths</span><br />
Over the years I have heard repeated many arguments against college which I simply don't believe are valid. Here are the common myths that I've heard along with my counter argument.<br />
<br />
<b>1. A degree is just a piece of paper</b><br />
This is simply not true. A degree is a certification from an educational institution that you have successfully completed an academic program. A degree is intangible, a diploma is tangible and is typically a piece of high quality paper.<br />
<br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"> <b>2. A diploma is just a piece of paper</b></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"> This is true, but the diploma is not really the goal of going to college. The diploma is a token that represents something of greater value. The diploma is nothing more than a certificate to show you have a degree. The concept of a token that represents something of value is not only limited to college diplomas. Cash, paychecks, car and house titles are all just pieces of paper, but their value is much greater than the cost of the paper that they're printed on. There is also a greater probability that you will be able to obtain the later pieces of paper such as cash, titles, paychecks if you have first obtained the first piece of paper a diploma.</div><div><br />
</div> <b>3. Just because you have a degree doesn't mean you're smart.</b><br />
This is certainly true. I have met and interviewed many degreed Software Engineers who managed to make it through college without retaining much of what they studied. Many of these unqualified Software Engineers were even able to pass their classes with good grades. So, I completely agree that the process of getting a degree will not guarantee competence. I have also met and interviewed non-degreed Software Engineers who were also incompetent and unqualified. So if a degree does not guarantee competence then why bother getting a degree? The answer is that a degree can help you become more competent, and therefore, a degreed individual is much more likely to be competent. My experience in talking and interviewing Software Engineers leads me to believe that there are a higher percentage of degreed Software Engineering that are competent than there are non-degreed Software Engineers that are competent. Just like safe driving habits won't guarantee you won't die in an auto accident a degree won't guarantee you'll be competent, but both will increase the likelihood of safety and competency respectively.<br />
<br />
<b> 4. I don't have a degree, and I'm smarter than those that do.</b><br />
This is entirely possible. As I mentioned before, I've met non-degreed Software Engineers who surpassed the average degreed counterparts in ability and competency. I do, however, think that this scenario is rare and unlikely. Of the non-degreed Software Engineers that I've known and interviewed, I have observed that there are many more who had an exaggerated perception of their abilities then those who's abilities we're above the average degreed Software Engineer. The idea that there are a lot non-degreed Software Engineers who erroneously think they are extra competent should not come as a surprise to those that are familiar with <a href="http://en.wikipedia.org/wiki/Illusory_superiority">illusory superiority</a> where people tend to overestimate their abilities or the <a href="http://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect">Dunning-Kruger effect</a> where the least competent tend to overestimate their abilities the most. If college degrees do in fact increase competency, then it would be expected that non-degreed individuals would not only be less competent, but would also not have the knowledge required to grasp the depth of their incompetence.<br />
<br />
<b>5. College is a waste of money. They don't teach anything that you can't learn on your own.</b><br />
<b> </b>While I agree that college doesn't teach you anything that you can't learn on your own. I do not think that it is a waste of money. I believe that college provides several benefits over self learning. Namely:<br />
<blockquote> <b>A. Access to experts.</b> Many of my classes were taught by professors who were considered experts in their fields. They kept up to date on the latest research and technology and shared that with their students. I remember discussing with a professor at the University of Utah an idea that I had for a research project for my Masters Thesis. He not only was able to quickly point out that my research topic had already been fully explored about 10 years earlier (a fact that I was not able to discover on my own despite several internet searches), he was also able to point me to that research. If I didn't have access to this professor, I would have spent a lot of time gaining knowledge that could have been gained in much less time by reading a handful of academic papers. This professor helped me to focus my research on areas that had not already been extensively explored.<br />
<b>B. Immediate feedback.</b> More that once I've done an assignment, taken a test, or participated in a class lecture thinking that I fully understood a subject, only to find out the next week when the graded work was returned that I didn't. If you study on your own you may likewise misunderstand a topic, but you may not get the feedback that you need.<br />
<b>C. A well rounded curriculum.</b> Both my Masters and Bachelors degrees surprised me at not only the depth of learning that I received but also the breadth. I think it would be possible (although much more difficult) for me to<b> </b>learn those topics on my own, but I'm less confident I would have known that some of those topics even existed or that they were important. I didn't know what I didn't know. It is impossible to study a topic that you don't know exists. A good example of this is big-O notation. Many un-degreed Computer Scientists have never heard of big-O notation or have shallow or incorrect understanding of what it is. In my job we use it all the time, if you don't know what it is you'll be left behind in the conversation or you'll require us to stop work and teach you about the topic (at work we pay you to be effective, we don't want to pay you to get an education). It's not a terribly difficult topic, but you won't learn it if you don't know it exists, and it's easy to get confused about what it really means. A good degree in Computer Science will guarantee the exposure to the topic and a good professor will give ample feedback to ensure a proper understanding.<br />
<b> D. Access to equipment and technologies.</b> Somethings you just can't learn (adequately) from books. You need to get you hands dirty and work with it. Many of these equipment and technologies are out of the price range for many people. Colleges can provide access to these technologies at a cheaper cost than if you purchased all the technologies on your own.</blockquote><b><br />
</b><br />
<b> 6. But if you did learn it all on your own and you are competent why don't employers just interview you so you can prove that you're qualified? </b>They could but interviewing is expensive. I believe the right way to interview for a technical position is to have your most qualified employees ask candidates technical questions. This process is likely to result in hiring a qualified candidate. First of all, your most qualified employees are also likely your highest paid employees, so you're paying them a lot of money to interview. They are also likely to be overworked as they can perform the most tasks (hence the most qualified) and if they weren't overworked you wouldn't be hiring. If you interview every candidate you will spend a lot of money paying your existing employees to interview and it is likely that your employees will get tired of interviewing and they may leave for another job where they can do real work and not perform job interviews. Because interviewing is expensive you must be selective with who you interview, so it makes sense to only interview those candidates that are most likely to be qualified. In my experience degrees individuals are most likely to be qualified and so it may make good business sense to toss the resumes of the candidates that don't have degrees. An obvious exception to this rule is if you simply do not have enough candidates, in which case, you may end up interviewing all candidates, but you should start with those who are most likely to be qualified first.<br />
<b> </b><br />
<b> 7. What about professors who live in their ivory towers and know nothing about the real world?</b> This is a common criticism about professors, and one that I've probably uttered a time or two. Such professors do exist, but I've found that often what they teach isn't applicable to today's real world problems but it often becomes applicable in the future. I remember learning about closures while working on my Bachelors degree. At the time I didn't think I'd ever use them as C/C++ Java ruled the industry. Since then Perl, Python, Ruby, JavaScript, Google Go have all become more predominant and all support closures. Even C++ recently added support for lambdas which in C++ are close to full grown closures. Had I ignored this topic, I would have had a more difficult time learning these languages and taking advantage of the power of closures. Additionally many of the students that are complaining about ivory tower professor do not have any real experience in the "real world" either. They are college students, who haven't spent a lot of time working in the "real wold," and, therefore, likely unqualified to determine what knowledge will have real world significance.<br />
<b><br />
</b><br />
<b><span class="Apple-style-span" style="font-weight: normal;"></span></b><br />
<div style="display: inline !important;"><b><span class="Apple-style-span" style="font-size: large;">Conclusion</span></b></div><br />
<br />
While I don't think college is perfect, I do believe the vast majority of people entering technical fields would greatly benefit from obtaining a college degree. I've talked to many who don't have degrees who feel that they aren't useful, but very few who have earned a technical degree who question the benefit. If there are additional augments against earning a college degree in a technical field that I haven't addressed, I would love to hear them.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-61330951053557799932011-07-14T15:31:00.000-06:002011-07-14T15:31:02.674-06:00Using gnuplot to make simple line graphs.Gnu plot is an amazing tool. It's great for generating quick plots from bash. I've had my programs generate statistical data and then thrown it into gnuplot so I can better understand how my program is behaving. Unfortunately every time I use it I end up having to go back to the web to relearn the basic syntax of creating a line graph. I'm going to try and save myself some time by documenting the basic usage here.<br />
<br />
To draw a simple line graph first place the points to draw in a separate file in this case named "gnuplot.data"<br />
<script src="https://gist.github.com/1083443.js?file=gnuplot.data">
</script><br />
<br />
Now create the gnuplot script:<br />
<script src="https://gist.github.com/1083451.js?file=gistfile1.txt">
</script><br />
<br />
The pause line at the end keeps the gnuplot from flashing the graph and then immediately exiting. When you execute gnuplot you'll see the following:<br />
<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_hVa8L5lABz99WVSZEomjOUjqYJqQRNkQ87HXA5pzD7lOskUfsQzXD-EAE8QdLXYcQr5NZIXokNbg_30xnYqXiVMF65NxFJYGpqfkUmcELsnAIbiPUWyk7GIo9EIGVYm2gdL9IsqgldSW/s1600/gnuplot.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="233" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_hVa8L5lABz99WVSZEomjOUjqYJqQRNkQ87HXA5pzD7lOskUfsQzXD-EAE8QdLXYcQr5NZIXokNbg_30xnYqXiVMF65NxFJYGpqfkUmcELsnAIbiPUWyk7GIo9EIGVYm2gdL9IsqgldSW/s320/gnuplot.png" width="320" /></a></div><br />
There is a ton more you can do with gnuplot like generate png files, create different types of graphs, but I've found that as a simple programming tool this gets me 90% there. For more information checkout the <a href="http://www.gnuplot.info/">gnuplot homepage</a>. Happy plottingEvanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com1tag:blogger.com,1999:blog-7573455095858650997.post-18624679574642865562011-06-08T21:44:00.000-06:002011-06-08T21:44:18.387-06:00Test Second DevelopmentLet me start off by stating that I'm a big fan of test-first development. I think that a (the?) major benefit of writing unit-tests is the fact that the first person to use a new API is the developer herself/himself. By first writing tests against the API before it has written you increase the likely hood of creating a unable, testable and bug free code. Test-first development is valuable even if you <b>never</b> ran any of the unit-tests that you wrote. The purpose of this post is not to extol the virtues of test-first development but to share a scenario where I feel it may be better to not write the unit-tests right away.<br />
<br />
Several weeks ago I started to work on a simple command line utility. Nothing fancy but just something to scratch an itch that I've had for a while. I had a vague idea of what I wanted it to do but hadn't quite worked out all of the details. Additionally I wasn't sure how the utility would involve. Finally I was writing the utility in Google Go, which I have done a bit of development but I certainly haven't played with it long enough to fully think in the language. In short I simply didn't know what I was doing and I knew it would be some time before I fully understood the problem I was trying to solve. I started to write the code and neglected to start by writing unit-tests. After some time of hacking on the utility I finally got to the point where I had a working prototype and I finally understood the problem. At that point I reviewed the code of my program and I realized that I had (not surprisingly) got the architecture of the program wrong. I figured out the right architecture of the program and started on the refactor. During the refactor the majority of the original code and internal API's was radically changed. If I had written any unit-tests they would have been discarded as the code and API's they would have tested simply did not exist in the refactored program. I could have preserved end-to-end tests but not any unit-tests. During the refactor I wrote unit-tests and I now have a program that has good unit-test coverage. I'll call this development process "Test Second Development". I'd like to propose the following criteria for when test-second development <b>may</b> be appropriate.<br />
<br />
<ol><li>You don't understand the program you are writing.</li>
<li>You don't understand the language you are writing the program in.</li>
<li>You will have the luxury of refactoring the program once you understand it, and before it "ships".</li>
<li>You're disciplined enough to write unit-tests when you do your rewrite/refactor.</li>
</ol><div>In other words I think it may be OK to delay writing unit-test when you are writing a true *prototype.</div><div><br />
</div><div>My thoughts on test-second development are still immature and evolving, but I thought I'd jot them down for future reference. In my case I don't think that I would have gained any benefit to using test-first development and I can definitely see how test-first development would have slowed down the discovery process.</div><div><br />
</div><div>* If you are writing code for your job and anyone else will know about your project, then I really doubt you will ever write a prototype. As soon as someone sees or hears about your project they'll want to ship it. I once worked for a company that shipped a simple utility that I had written to aid in testing my code. I only found out that they had shipped it after my manager came and talked with me about the utility and told me that I needed to pretty up the GUI. When I told him that it was a testing utility and was never meant to be shipped he told me that since it was shipped we'd have to support it. I started prettying up the GUI and started on a new testing utility. The new testing utility had a big banner across the front stating that it was for internal testing only. I later learned that calling testing tools something like "The enema tester" was a good strategy for ensuring that internal testing tools never got shipped. </div><div><br />
</div>Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-26230842600300788602011-04-23T21:23:00.000-06:002011-04-23T21:23:26.763-06:00Cross Compiling Google Go CodeThis is more of a note to self, so I can look up this information in the future as needed. Google Go makes it really easy to cross-compile. Here is how you an compile your Go project for another architecture. The first step is to compile the cross compiling compilers (I can't believe I just typed that). So lets checkout the source code for the go compiler.<br />
<pre class="brush: bash">hg clone -r release https://go.googlecode.com/hg/ go</pre><br />
Now to compile the Go compiler for the architecture of your machine, simply cd into the go/src directory and run the all.bash script<br />
<pre class="brush: bash">cd go/src; ./all.bash</pre>If you want to create compilers for a different architecture you set the GOARCH environment variable and then run the make.bash script.<br />
<pre class="brush: bash">GOARCH=arm ./make.bash</pre><pre class="brush: bash">GOARCH=386 ./make.bash</pre><pre class="brush: bash">GOARCH=amd64 ./make.bash</pre><br />
The all.bash script compiles the compiler and runs the unit tests, the make.bash script just compiles the compilers.<br />
<br />
This will create separate compilers, linkers and assemblers for each of the three architectures. Because each compiler, linker and assembler have a different name you can have support all architectures simultaneously. <br />
<br />
Once you have the Go compilers compiled you can now compile your project for different architectures by creating a Go Makefile and setting the GOARCH environment variable before typing make.<br />
<br />
<pre class="brush: bash">GOARCH=arm make</pre><pre class="brush: bash">GOARCH=386 make</pre><pre class="brush: bash">GOARCH=amd64 make</pre><br />
That's it! You can now cross compile your Go code. More information on the Go compilers, creating a Go Makefile and getting started with Go can be found <a href="http://golang.org/cmd/">here</a>, <a href="http://golang.org/doc/code.html">here</a>, and <a href="http://golang.org/doc/install.html">here</a> respectively. Happy Hacking!Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com1tag:blogger.com,1999:blog-7573455095858650997.post-19663243663046079602011-04-22T21:17:00.000-06:002011-04-22T21:17:54.378-06:00I'm backLast year I decided that it was time to finish up my Masters degree. I recognized that in order to finish in a timely manner I would need to forgo all hobbies for a while and so this blog has been on hold. I'm now done, or at least I'm at the stage where I'm waiting for the final announcement that I'm done and so I'm now returning to normal life. After having dropped out more than a year ago I'm finding that it's taking some time to get adjusted to normal non-academic life. I'm also slowly starting to remember all the non-homework activities that I used to participate in. I wonder how long it will be before I become as busy as I was before.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-52129200172613024392010-03-16T22:41:00.000-06:002010-03-16T22:41:22.116-06:00Developer EtiquetteI created a list of etiquette guidelines for Software Engineers. These etiquette guidelines are not for social interactions, but are instead for writing code. Like most etiquette guidelines these are designed to minimize the discomfort for others. So here they are.<br />
<br />
Before committing I will:<br />
<br />
<ol><li>Review the patch.</li>
<li>Review the list of files that are not being committed, but have been modified or are new.</li>
<li>Compile the code.</li>
<li>Run any affected unit-tests.</li>
<li>Test the code to make sure it does not break core functionality.</li>
</ol>The reason behind #1 is simple. It's very easy to accidentally commit code that's not ready, or that contains printf debug code. It's quite obnoxious to have your terminal sprayed with hundreds of "XXX Hey I'm executing function foo()." By following guideline number #1 you will rarely accidentally commit half-baked code. The git add --patch command makes this really easy.<br />
<br />
Guideline #2 saves you from forgetting to commit some critical patch, or more commonly forgetting to add a new file to the repository. I've found that most of the time when code compiles on the developer's computer but not anyone else's, it's because they forgot to add a file. The git status command helps here.<br />
<br />
Guideline #3 is simple. Committing code that doesn't compile turns a O(1) problem into a O(n) where n is the number of developers on your team. Don't ever check in code that doesn't compile.<br />
<br />
Guideline #4 ensures that you don't accidentally break the unit-tests. It is much easier to fix bugs earlier rather than later. So if you break the tests it's better to find out before you commit.<br />
<br />
Guideline #5 is similar to #4 but assumes that not all of your code is covered by unit-tests. Even if you test every line of code with unit-tests, your unit-tests won't tell you that you just made your GUI look like puke. So run the code and make sure nothing broke.<br />
<br />
If you follow these guidelines you can still write horribly broken code and be a terrible developer, but at least you won't prevent your co-workers from being competent.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com2tag:blogger.com,1999:blog-7573455095858650997.post-11902335149768480022010-01-20T22:42:00.001-07:002010-02-22T21:07:34.269-07:00Easy to UseI've noticed that when choosing a tool for software development one of the criteria that's often proposed is the tool should be "easy to use". While I agree that ease of use should be a criteria for choosing a tool I've come to realize that I have a different opinion on what "easy to use" means than others. When I say a tool is "easy to use" I mean it literally. A tool that is easy to use should make it really easy for me to do what I want. Here are some of the development tools that I use that I consider easy to use:<br />
<br />
<ol><li>vim</li>
<li>git</li>
<li>The command line (bash)</li>
</ol>All three of these tools let me do my job as quickly and painlessly as possible. If you asked others for a list of similar tools that are easy to use you may get the following:<br />
<br />
<ol><li>notepad</li>
<li>svn</li>
<li>GUI's</li>
</ol>By my definition the above tools are not easier to use than my list (they don't allow me to do my job as quickly or painlessly) but they are easier to <b>learn</b>. I'm not sure if easy to learn and easy to use must be mutually exclusive but I can't think of any tools that I use frequently that have both qualities. There is nothing wrong with choosing a tool that's easier to learn over one that's easier to use as long as you use the tool infrequently. Investing years to fully learn vim is a waste of time if you only edit text files for a few minutes every month. If your going to use a tool frequently over a long period of time then you should spend the time to learn the tool that's easy to use even if it isn't easy to learn.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-63960497525693847902010-01-05T21:34:00.000-07:002010-01-05T21:34:30.973-07:00Recursion and Inductive ProofsI've discovered that programmers frequently stumble when writing recursive algorithms. There are some simple rules that programmers can steal from mathematics to make writing recursive algorithms easy. I should point out that I'm only talking about writing recursive algorithms for interacting with recursive data-structures (lists, trees, etc.). Let's get started by reviewing some basic steps for proving a statement holds for all natural numbers <i>n</i> using an inductive proof.<br />
<ol><li>Base case: Show the statement holds for a value of <i>n</i> (usually <i>n</i>=1 or <i>n</i>=0).</li>
<li>Inductive step: Assuming the statement holds for any value of <i>n</i> then show it also holds for a value of <i>n</i>+1</li>
</ol>Rule 2.5 would be to make sure that the inductive step reduces the problem space. Using a base case of <i>n</i>=0 and then and inductive step of <i>n</i>-1 wouldn't be a valid proof because the inductive step does not really reduce the problem space (remember we're talking about natural numbers for this example). So let's use an inductive proof to show that 0+1+2...<i>n</i>=(<i>n</i>(<i>n</i>+1))/2.<br />
<br />
Base case: Show the statement holds for <i>n</i>=0<br />
<pre class="brush: cpp">0=0(0+1)/2
</pre>This equation clearly holds.<br />
<br />
Inductive step: Assuming the statement holds for any value of <i>n</i> then show it will also hold for <i>n</i>+1.<br />
<pre class="brush: cpp">0+1+2...n+(n+1) = ((n+1)((n+1)+1)/2
</pre>If we assume that the statement holds for <i>n</i> then we can reduce the expression.<br />
<pre class="brush: cpp">(n(n+1))/2 + (n+1) = ((n+1)((n+1)+1)/2
</pre>Using some basic algebra we can reduce both sides and discover that the inductive step holds.<br />
<br />
Now we can apply same (perhaps slightly tweaked) rules to writing a recursive algorithm for finding the length of a linked-list (a recursive data-structure).<br />
<br />
Let's start out with the function signature.<br />
<pre class="brush: cpp">int length(Node *node)
{
// Do stuff here
}
</pre>Base case: Write the algorithm for <i>n</i>=0 (the linked-list with 0 nodes).<br />
<pre class="brush: cpp">int length(Node *node)
{
if (NULL == node)
{
return 0;
}
// Do more stuff here
}
</pre>Congratulations! If you've make it this far you're above average. You've solved the base case without dumping core.<br />
<br />
Now onto the inductive step: Assume that your length function will work for lists of length <i>n</i> now write code to make it work for lists of length <i>n</i> + 1.<br />
<pre class="brush: cpp">int length(Node *node)
{
if (NULL == node)
{
return 0;
}
else
{
return 1 + length(node->next);
}
}
</pre>Notice that if we assume that "length(...)" works for lists of length <i>n</i> then for lists of length <i>n</i> + 1 all we need to do is add 1 to the length. You should also notice that we passed <i>node->next</i> to the "length(...)" function not just <i>node</i> because rule 2.5 states that the inductive step must reduce the problem space and just passing <i>node</i> would not reduce the problem space. Congratulations! If you've make it this far you're now well above average. Now not only will your algorithm not core dump, but it won't hang either.<br />
<br />
So let's review what we've done. We've used the rules for inductive proofs to guide us in writing a recursive algorithm. Does this mean we've proved that this algorithm is correct? The answer is, not really or at least, not formally. Even though we haven't proved this algorithm is correct we can be much more confident that it will work. <br />
<br />
If we were to write unit-tests for this algorithm (which you should *always* do before writing the algorithm) we could use the rules of induction to guide our unit tests. We could write a test for testing the base case and another test for testing the inductive case.<br />
<br />
Since math has been around longer than computers, it makes sense that we could borrow a few ideas from it to make our jobs easier.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com1tag:blogger.com,1999:blog-7573455095858650997.post-14274959954076633472009-11-27T22:27:00.000-07:002009-11-27T22:27:21.771-07:00Google's Go trying to be too clever.I've discovered a couple of cases where Google's Go is trying to be too clever. There are two expressions who's behavior changes based upon what is done with evaluated results. Lets look at a bit of code.<br />
<br />
<pre class="brush: cpp">package main
import . "fmt"
// Define a simple struct
type foo struct {
a int;
}
// Define an interface
type plus1 interface {
add1() int;
}
func any(a interface{}) {
v := a.(plus1).add1();
Printf("%v\n", v);
}
func main() {
f := foo{1};
any(f);
}
</pre><br />
So this code defines a simple struct "foo" with a single member a. It defines a "plus1" interface that says that any struct that implements the interface must implement an add1 method that returns an int. The main function instantiates a "foo" and passes it onto the any function. Because "foo" doesn't implement the "plus1" interface the first expression in the function "any" will fail with a runtime exception. the "a.(plus1)" is called a type assertion and it fails if the "a" doesn't implement the "plus1" interface. Now we can switch this code so the type assertion won't assert by assigning the results of the type expression to some variables. Consider the following:<br />
<br />
<pre class="brush: cpp">package main
import . "fmt"
// Define a simple struct
type foo struct {
a int;
}
// Define an interface
type plus1 interface {
add1() int;
}
func any(a interface{}) {
a1, ok := a.(plus1);
if ok {
v := a1.add1();
Printf("%v\n", v);
}
}
func main() {
f := foo{1};
any(f);
}
</pre><br />
The only difference in this code is that the type assertion will not assert but instead return two values (yes Go can return multiple values!). The second value is of type bool which indicates whether the first value is "a" cast to "plus1". If "a" isn't of type "plus1" then instead of asserting the type assertion will just return false for the second parameter. While this is clever, it feels like assigning the return value to a variable magically alters the behavior of the expression. I think this will just make the language too difficult to learn. The second operation has to do with go-routines and I'll talk about it next time.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-10408159814500006302009-11-18T15:06:00.001-07:002009-11-18T15:09:09.349-07:00Letting the compiler find the bugsLets start by looking at a bit of contrived C/C++ code. See if you can spot the (hopefully obvious) bug.<br />
<pre class="brush: cpp">#include <stdio.h>
int main()
{
float fieldLength = 120; // yards
float fieldWidth = 48.77; // meters
float yardsInAMile = 1760; // yards per mile
printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));
return 0;
}
</pre><br />
It probably shouldn't take you too long to realize that in the above code I'm mixing units. I'm adding yards to meters. While bugs like this are obvious in trivial code they can be difficult to track down in more complex software. What can we do to prevent bugs like this from creeping into code? One solution is to use coding standards to reduce ambiguity. For example you could decide to use metric units for all data in your project. You could also use 'typedefs' and variable naming conventions to make errors even more obvious. Consider the following:<br />
<br />
<pre class="brush: cpp">#include <stdio.h>
typedef float yards;
typedef float meters;
int main()
{
yards fieldLengthYards = 120; // yards
meters fieldWidthMeters = 48.77; // meters
float yardsInAMile = 1760; // yards per mile
printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
26.2 * (yardsInAMile / ((fieldLengthYards * 2) + (fieldWidthMeters * 2))));
return 0;
}
</pre><br />
By including the units in the variable names and types it makes the programmers intentions clear. It's also easier to spot bugs in code audits. For even more safety you could define Meters and Yards classes that encapsulate the floats and prevent mixing of types. The advantage of defining new types/classes is the compiler can now ensure that you don't mix types. The disadvantage is that you'll end up writing a class for each type, with lots of overloaded operators. Writing a class for every unit feels to burdensome for all but the most critical code (nukes, airplane firmware, surgery robots, etc.). The problem with the above 'typedef' solution is that C/C++'s 'typedef' really only defines an alias for the type. Both the type-checker and the compiler will treat 'meters' the exact same way it treats 'yards', we want the type-checker to treat 'meters' and 'yards' as distinct types and the compiler to treat them both as floats. Google's new system language Go lets you do just that. Lets reproduce the original bug in Google Go.<br />
<br />
<pre class="brush: cpp">package main
import "fmt"
func main() {
var fieldLength float = 120; // yards
var fieldWidth float = 48.77; // meters
var yardsInAMile float = 1760; // yards per mile
fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
26.2 * (yardsInAMile / ((fieldLength * 2) + (fieldWidth * 2))));
}
</pre><br />
This has the same bug as the C/C++ code above. The code should be readable to a C/C++ developer, the only really "weird" thing is that the type follows the variable name. Now let's use Go's strong typing to let the compiler catch the bug for us.<br />
<br />
<pre class="brush: cpp">package main
import "fmt"
type yards float
type meters float
func main() {
var fieldLength yards = 120;
var fieldWidth meters = 48.77;
var yardsInAMile float = 1760; // yards per mile
fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
26.2*(yardsInAMile/((fieldLength*2)+(fieldWidth*2))));
}
</pre><br />
Notice that all we did is define two new types 'yards' and 'meters' all which should act like 'floats', but should be treated differently by the type-checker. When we compile we get the following error:<br />
<pre>invalid operation: fieldLength * 2 + fieldWidth * 2 (type yards + meters)
</pre><br />
The most important part of the error is at the end where it tells us we're trying to add 'yards' with 'meters'. The type checker found the bug for us! So how do we fix it? We need some conversion routines. So lets add some methods to the types and fix the bugs.<br />
<br />
<pre class="brush: cpp">package main
import "fmt"
type yards float
type meters float
type miles float
func (m meters) toYards() yards { return yards(m * 1.0936133) }
func (y yards) toMiles() miles { return miles(1760.0 / y) }
func main() {
var fieldLength yards = 120;
var fieldWidth meters = 48.77;
fmt.Printf("You must run around the perimeter of an American football field %f times to run a marathon\n",
26.2*((fieldLength*2)+(fieldWidth.toYards()*2)).toMiles());
}
</pre><br />
With the corrected program we see that you only have to run around the field 133 times instead of 136.6 times!<br />
<br />
Go isn't the first nor the only programming language that allows you to encode units as types, but it's close enough to C/C++ for a good comparison. So what's the runtime overhead of the change? Well there are a couple of method calls (toYards(), toMiles()) where the original version did the conversions inline. The error checking happens at compile time because Go is statically typed so there's no runtime performance hit. Personally I'd much rather wait for my program to call a couple of functions than to run around an American football field 3.6 more times.<br />
<br />
By carefully using Go's (or any other language with a good type system) type system you can spend more time writing code and less time tracking down bugs.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com1tag:blogger.com,1999:blog-7573455095858650997.post-36820243176103896222009-11-09T22:34:00.002-07:002009-11-09T22:35:57.673-07:00More fun with C/C++In order to write a program it's useful (but not necessary) to have an accurate mental model of how the language works, so you can mentally interpret your code before handing it off the compiler. So if you're a C/C++ programmer take a look at the following code and see if you can correctly identify the output:<br />
<pre class="brush: cpp">#include <stdio.h>
int foo(int a, int b, int c, int d)
{
if (a>b)
{
return c;
}
else
{
return d;
}
}
int main(int argc, char * argv[])
{
int x = 2;
int y = 1;
printf("Result: %d\n", foo(x+=y, y+=x, x+=y, y+=x));
return 0;
}
</pre>In this case the output is non-deterministic. While C/C++ specify what order arguments will be pushed onto the stack it doesn't specify what order they'll be evaluated in. So there are several possibilities for the output. This flexibility allows compiler writers to order the evaluation of operations in the most efficient way. If you want to avoid confusing/broken code don't mutate variables in argument positions. The person that ends up maintaining your code will thank you for it.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-78581889224486357052009-10-21T22:33:00.008-06:002009-10-22T21:13:45.772-06:00Coding ChallengeHere is a little coding challenge. Learning how to solve this probably won't make you a better programmer (it may make you worse) but it's fun anyway. You are given a file named "helloworld.cxx" that contains the following code.<br />
<br />
<pre class="brush: cpp">#include <stdio.h>
#include "muck.h"
int
main(int argc, char **argv)
{
printf("%s\n", "Hello World!");
}
</pre><br />
You <b>can't</b> edit this file! Your job is to write the "muck.h" header file. When you're done compile "helloworld.cxx" and run it and the output should be "Goodbye!" followed by a newline. Nothing more nothing less. Remember you can only modify "muck.h" and you must compile "helloworld.cxx" unmodified. My <a href="http://www.cs.utah.edu/~farrer/coding_challenge/muck.h">solution</a> and it's <a href="http://www.cs.utah.edu/~farrer/coding_challenge/Makefile">Makefile</a>.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-25604174473388278892009-10-06T12:56:00.001-06:002009-10-06T12:58:34.666-06:00The Essence of Scheme (part two)This post is a continuation of <a href="http://evanfarrer.blogspot.com/2009/09/essence-of-scheme.html">part one.</a> You probably want to read <a href="http://evanfarrer.blogspot.com/2009/09/essence-of-scheme.html">that post</a> first. So in my previous post I walked you through a nifty little though experiment on why Scheme is so expressive, and why those pesky ('s and )'s are actually useful. In this post I hope to provide some concrete examples of using Scheme's macros to do interesting things. So lets start with a simple example. The Scheme programming language (R5RS) doesn't have a built in "while" loop. It does have a "do" loop which is kind of like a "for" loop but I don't think it gets used much. Most Schemers use recursion instead. Lets say you're just learning Scheme and recursion hurts your brain and you really really just want to use a "while" loop just this one time and you promise that you'll pay better attention when you CS professor talks about recursion. It turns out it's quite easy to implement a "while" loop as a Scheme macro<sup>1</sup>.<br />
<pre class="brush: cpp">;; A while loop
(define-syntax while
(syntax-rules ()
[(_ (cnd ...) body ...)
(letrec ([tmp (lambda () (if (cnd ...) (begin body ... (tmp)) (void)))])
(tmp))]))
</pre>If you want to try it out here is a bit of code that uses the while loop to count from 10 down to 1.<br />
<pre class="brush: cpp">(define count 10)
(while (> count 0)
(printf "~a\n" count)
(set! count (- count 1)))
</pre>So in 10 lines of code you can define a "while" loop that works just like the "while" loops built into C/C++/Java/Python/Insert_Your_Favorite_Language_Here.<br />
<br />
So that doesn't seem to hard. If C didn't have a built in "while" loop you could always create you're own with a C style macro as follows.<br />
<pre class="brush: cpp">#define WHILE(cond) for(;cond;)
</pre>Lets try something more difficult. Scheme also doesn't have a C/C++ "#include" directive. So lets write our own.<br />
<pre class="brush: cpp">;; Define include
(define-syntax include
(lambda (stx)
(define (read-all port)
(let ([exp (read port)])
(if (eof-object? exp)
'()
(cons exp
(read-all port)))))
(define read-file
(lambda (fn ctx)
(let ([port (open-input-file fn)])
(begin0
(datum->syntax ctx (read-all port))
(close-input-port port)))))
(syntax-case stx ()
((ctx filename)
(with-syntax ([(exp ...) (read-file (syntax->datum #'filename) #'ctx)])
#'(begin exp ...))))))
</pre>Once you've defined this you can use it as follows.<br />
<pre class="brush: cpp">(include "extern.ss")
</pre>Once you've defined the "include" macro any include expression will get evaluated at <b>compile</b> time which opens up the included file reads in the text and injects it into the the source file at the location of the "include" call. Spend a little time thinking about that. A Scheme programmer can write code that gets evaluated at compile time and that code can open, close, and read from files. So if Scheme's macro language allows you to read from files what else can it do? It turns out anything that a Scheme program can do. The above macro can read from files because any old PLT-Scheme program can read from files. A Scheme macro is just a chunk of regular old Scheme code that gets executed at compile time. If your Scheme allows you to open up a TCP/IP socket then you can write a macro to do this at compile time<sup>2</sup>. If your Scheme allows you to rotate images then you can do it at compile time. If your Scheme allows you to play music then you can play music at compile time<sup>3</sup>. OK so lets look at some more examples.<br />
<pre class="brush: cpp">(define current-catch
(make-parameter
(lambda (exn)
(printf exn)
(exit 1))))
(define (throw exn)
((current-catch) exn))
(define-syntax try
(syntax-rules (catch throw)
[(_ body ... (catch exn cbody ...))
(let/cc k
(parameterize ([current-catch (lambda (exn) cbody ... (k (void)))])
(begin body ...)))]))
</pre>This chunk of code allows users to throw and catch exceptions using "try", "catch" and "throw"<sup>4</sup>. Scheme doesn't have a built in exception mechanism, but in 13 lines of code you can write your own. The following code will use the above macro and functions.<br />
<pre class="brush: cpp">(try
(printf "Yes\n")
(throw "Error\n")
(printf "No\n")
(catch exn
(printf exn)))
</pre>It will print "Yes" followed by "Error" the "No" will not be displayed because of the "Error" exception will be thrown. OK lets look at one more.<br />
<pre class="brush: cpp">(define-syntax define-generator
(lambda (stx)
(syntax-case stx ()
((_ (name args ...) body ...)
(with-syntax ([yield (datum->syntax #'name 'yield)])
#'(define (name args ...)
(define yield-k #f)
(define return-k void)
(define (yield retval)
(let/cc k
(set! yield-k k)
(return-k retval)))
(lambda ()
(let/cc ret
(set! return-k ret)
(if yield-k
(yield-k '())
(begin
body ...
(set! yield-k (lambda (x) (void)))))))))))))
</pre>This allow you to define Python style <a href="http://www.python.org/dev/peps/pep-0255/">generators</a>. Here is a simple example that defines a "range" generator that will reuturn 0 he first time it's called and 1 the next.<br />
<pre class="brush: cpp">(define-generator (range init limit)
(let loop ([i init])
(yield i)
(when (< i limit)
(loop (+ i 1)))))
(define foo (range 0 1))
(foo)
(foo)
</pre>
I hope these examples give some insight at how expressive and malleable the Scheme programming language is. There is one more issue I'd like to address. If you're a Python programmer you may be thinking to yourself. "Hey Python has loops, exceptions, generators and import which is kind of like #include. If python has these built in then why should I use Scheme?" That is a valid but slightly myopic question. The point of Scheme's macro system is not to create another Python with funnier syntax. The real point is that you the developer can extend and grow the language to meet your needs. You may extend the language by adding features that are found in other programming languages, but you may also add features that don't exist in any language, and that don't have a name, and that may not be generally useful but really make the current program you're working on really really easy to write. In Python, Perl and Java users have the power to create and extend libraries, in Scheme users have the power to create and extend languages<sup>5</sup>. Power to the people!<br />
<br />
[1] All examples tested in in PLT-Scheme 4.1.3.<br />
[2] Implementing "http-include" is left as an exercise for the reader.<br />
[3] Playing music at compile time is possible but not recommended by the author.<br />
[4] Anyone want to try implementing exceptions in C?<br />
[5] There is one major downside to learning Scheme. Eventually you'll find yourself writing a program in C/C++/Python/Java and you'll realize that you could solve some problem really elegantly if you could just extend the language just a little bit. Then you'll realize that you can't and you'll spend the next hour wishing you we're never enlightened.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-71168622036079714402009-09-28T14:25:00.000-06:002009-09-28T14:25:16.622-06:00The Essence of SchemeNote that throughout this post "Scheme" could be replaced with "Lisp" without changing it's meaning.<br />
<br />
<b><span style="font-size: x-large;">My Introduction to Scheme</span></b><br />
My first exposure to Scheme was in college at the University of Utah. At that time they taught a Programming Languages course that was based on the book <a href="http://mitpress.mit.edu/sicp/">Structure and Interpretation of Computer Programs</a>, and the <a href="http://www.plt-scheme.org/">Dr. Scheme</a> programming environment. While I enjoyed the class I never understood why some people thought Scheme was so special. In my defense the class really didn't teach us Scheme they just used a small subset of the language to teach us about programming language features such as exceptions, continuations, closures, loops, recursion, conditionals, first class functions etc. It really was a great class, you learned about these features by writing and modifying interpreters that implemented these features. The only problem is that many students including myself left that class thinking they knew Scheme, but we didn't. I didn't get re-introduced to Scheme again until a few years later when I was learning Perl. I kept on learning about features of Perl that I really liked, and then I realized that all of these features were also in Scheme. I decided that I needed to go back and tinker with Scheme. <br />
<br />
<br />
<b><span style="font-size: x-large;">Learning Scheme</span></b><br />
I started learning Scheme by writing programs and reading a lot of blogs, and articles in an attempt to get my brain wrapped around the programming language. Almost everyone talked about how powerful Scheme is, but it took me a long time before I really understood why Scheme is such an expressive language. Because it takes a lot of work and study to reach Scheme enlightenment, many developers simply give up on the language, before they really understand it. I don't know if it's possible to reach Scheme enlightenment, without all the hard work, but I hope this post will at least will give you a peek at why Scheme is so expressive, and why those that really learn it have a tendency to turn into <a href="http://www.google.com/search?q=smug+lisp+weenie">Smug Lisp Weenies</a>. In short this is the blog post that I wish I could have read when I was working towards Scheme enlightenment. <br />
<br />
<br />
<b><span style="font-size: x-large;">A shortcut to Scheme enlightenment</span></b><br />
Lets get started. Consider the following snippet:<br />
<pre class="brush: cpp">(if val
0
1)
</pre><br />
Now if you're an experienced programmer or a Schemer you were probably tempted to just glance at the above snippet and move on, but take a minute and really think about what you're looking at. As a Schemer I can see three different interpretations of the snippet.<br/><br />
The most obvious interpretation of the above snippet is an 'if' expression. The expressions condition is the 'val' value, the consequence is the integer '0' and the alternate is the integer '1'.<br/><br />
The second interpretation that I see is a linked-list<sup>1</sup> of 4 elements. The first elements in the list are the symbols<sup>2</sup> 'if' and 'val' followed by the integers '0' and '1'.<br/><br />
The third interpretation is a tree data structure. A linked-list can represent a tree structure by putting the first element in the list as the root and all other elements in the list as child notes of the root. Because Scheme allows a linked-list to have another linked-list as an element arbitrary tree structures can be represented using linked-lists. So the above snippet could also represent the following tree: <br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhduug-JmlDj243AkCxWhN4FTUc535W-jwUJLmuCoa__ZsuoYPKl1q_WZScXMpjxLjQovf8b3JGp7Ug_x069MOlwtWfaQIh4oumseBRmq1PsQjrNicILLtwW9RKFwtFdGCdIMfbOovcJEB5/s1600-h/if.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhduug-JmlDj243AkCxWhN4FTUc535W-jwUJLmuCoa__ZsuoYPKl1q_WZScXMpjxLjQovf8b3JGp7Ug_x069MOlwtWfaQIh4oumseBRmq1PsQjrNicILLtwW9RKFwtFdGCdIMfbOovcJEB5/s320/if.png" /></a><br />
</div>This tree also happens to be the <a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree">Abstract Syntax Tree</a> for the previously mentioned 'if' expression. At this point you may be wondering why this is important, and we'll get to that but for know just consider that every expression in Scheme is an expression, a linked-list and the AST for that expression. Now lets explore the consequences of that fact.<br />
<br />
<br />
<b><span style="font-size: x-large;">Scheme and linked-lists</span></b><br />
Scheme is one of many dialects of Lisp. The name List is short for "List Processing". Although Lisp dialects do support other data-structures, they have very powerful constructs that make them an ideal language for processing linked-lists<sup>3</sup>. Because every Scheme expression is also a linked-list and Scheme is an ideal language for processing linked-lists we can conclude that Scheme is an ideal language for processing Scheme expressions<sup>4</sup>.<br />
<br />
<b><span style="font-size: x-large;">Compilers and AST</span></b><br />
When you write a compiler for a language one of the first things you may do will be to build an AST for the tokenized and parsed text. An AST is a simplified representation of the code that is in a format that is easily to manipulate. When the code has been transformed to an AST it is easy for the compiler to perform optimizations, static analysis and transform complex language features into more basic language features.<br />
<br />
<b><span style="font-size: x-large;">Bringing it all together</span></b><br />
So we've discussed that all Scheme expressions are linked-lists and Scheme is a great language for manipulating linked-lists. We've also discusses that all Scheme expressions are also the AST for that expression, and AST's are a great data-structure for compiler writers to do complex transformations. It shouldn't be too hard to see that Scheme is an excellent language for performing complex transformations on Scheme expressions. In fact Scheme allows you to easily extend the programming language in ways that are only reserved for language designers and compiler writers in other languages. When I learn about some new programming language feature in Python that I wish was in C++, my only choices is to hope that the great C++ language design committee will include the feature in some future version of the C++ spec and that g++ will implement that feature quickly, and my distro will ship the updated version, and ... If I want to use that same feature in Scheme, I can simply implement it and I don't need to ask the language design committee for permission, I don't need to modify the Scheme compiler/interpreter, I don't need to modify any Makefiles, I just implement the feature and start using it immediately! That IMHO is <b>the</b> feature that makes Scheme such a powerful tool!  In my next post we'll look at some examples of how easy it is to <a href="http://video.google.com/videoplay?docid=-8860158196198824415#">grow your own language</a> with Scheme.<br />
<br />
<br />
[1] I know that for this to be treated as a list in code it would need to be quoted, but if it was simply read in from a file with a 'read' call it would come in as a list.<br />
[2] Scheme symbols are like read-only strings that can be efficiently compared for equality by simply comparing their pointers. Symbols are often used like enums in C++.<br />
[3] A proof of this statement is left as an exercise for the reader.<br />
[4] Yep, you should prove this one too while you're at it.Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com0tag:blogger.com,1999:blog-7573455095858650997.post-50818980771541491782009-09-16T22:08:00.005-06:002009-10-06T12:58:03.931-06:00A(nother) counter intuitive C++ (mis)featureI've been using C++ for about 12 years now. Which means I don't know if very well. Early on in my C++ career I thought I had a good grasp of the language, but C++ is one of those languages that the more you learn the more you understand how hopeless it is to fully understand it. Every month or so I'm confronted with some new corner case that I didn't know about. Last months mis-feature had to due with overloading and overriding. <br />
Consider the following code:<br />
<pre class="brush: cpp">class Bar
{
public:
virtual void method(int a)
{
std::cout << "Bar " << a << std::endl;
}
};
class Baz : public Bar
{
public:
virtual void foo(std::string a)
{
std::cout << "Baz " << a << std::endl;
}
};
int main()
{
int i = 9;
std::string s = "9";
Baz *b1 = new Baz();
b1->method(i);
b1->method(s);
}
</pre><br />
If you compile this code (with g++) you'll get the following errors:<br />
<pre class="brush: cpp">error: invalid conversion from ‘int’ to ‘const char*’
error: initializing argument 1 of ‘std::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const _Alloc&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]’</char></char></pre><br />
<br />
This caught me by surprise. I had assumed that the compiler would match the method signatures <b>after </b>the method names were mangled, and thus method(std::string) would not hide method(int). It turns out that methods are matched only by the name, and after the match has been found (in this case finding the method(std::string) the type checker validates the parameter types. While I can understand this could make the compiler more efficient, it seem that by default the C++ compiler does the wrong (non-intuitive) thing.<br />
<br />
So how do you make the compiler do what you want? You just need to add a "using" line right before Baz's method as follows:<br />
<pre class="brush: cpp">...
using Bar::method;
virtual void method(std::string a)
{
...
}
...
</pre><br />
Of course you could have guessed that. Right?Evanhttp://www.blogger.com/profile/03848709590438147138noreply@blogger.com1