akrish

Note: I had a hard time thinking of a title, my apologies

This past Spring, I took a course on Programming Languages and Compilers which has been far and away the most challenging class I’ve taken in college. My friend (and project partner) Gary hit the nail on the head when he said something like: the project is insane, tests are incredibly hard, and even homeworks are non-trivial. However, after going through the course, both of us will tell you that we found the course incredibly valuabe. I feel like I’ve matured as a programmer and computer scientist over the course of the last semester and it’s largely because of my compilers class. I wish I could have taken it earlier because now I feel like I’ll get a lot more out of my future courses. Of course, had I taken it earlier, I wouldn’t have been able to keep up, and maybe wouldn’t have gotten as much out of it, introducing an interesting paradox.

As a background, the course covers a lot of the basics of compiler design and implementation. We don’t officially have a textbook, and our professor (Paul Hilfinger) wrote up notes that served as a text for the first half of the course. Unfortunately, as the class project heated up he spent more time working on that and didn’t get around to updating the notes. Not to rag on him, he spent more time working on the project than many of the groups and we frequently saw him responding to newsgroup posts as late as 2 AM. I hope that the next time he teaches the course, he does get to finish the notes as I like the material that he presented. Anyway, we covered most of the basic topics including lexical analysis, parsing, static semantics, types and type inference, code generation, runtime structures (functions, classes, exceptions) and some code optimizations. I actually found most of the course material very interesting which is unusual as typically I lose interest in certain parts of a course.

I mentioned we had a class project. The project was in a nutshell to build a compiler for python. Of course the project was broken into phases (lexing and parsing, static analysis, and code generation) to make sure we didn’t procrastinate and utterly fail. After each phase, the professor would release his implementation, which we could use to build the next phase, just so that we didn’t shoot ourselves in the foot with bad programming practices (which my group did for phase 1). The professor also provided us a runtime library and a virtual machine with a clean instruction set that we could use as a python interpreter, to split the challenges of code generation into two “easier” tasks.

I wanted to write a bit about this project because I feel like it’s one of my crowning acheivements so far as a young programmer. It’s one of the larger code bases I’ve worked intimately with, meaning I could tell you anything about any part of the code base without really looking at it. It’s a project that I spent so much time with in such a short period of time, that as nerdy as it sounds, I found myself dreaming about problems we had and waking up with solutions to them. And it’s definitely one of the most complex systems I’ve developed and completed successfully.

Of course, I didn’t do it alone. My partners in crime were Gary (mentioned above) and Brian, both hard workers and amicable people, the latter quality being especially important because we spent a LOT of time together. Our final project was due the Monday after the last week of class, and that weekend, we pretty much lived in our computer science building. Our hard work paid off and we submitted a mostly working final project (mostly working in the sense that we didn’t do some tricky things like using function values as keys to dictionaries, because we modified the function representation).

Apart from compiler design, our professor emphasized good programming practices that he drilled in by looking at our source code and grading us on our cleanliness. I learned some valuable lessons about documenting code, refactoring all the time, repeating yourself, thorough and systematic testing etc. Lessons that I read about all the time, but that really only get ingrained when you work on a large project and NEED to do them to maintain your productivity (and your sanity when it’s late at night). I’m happy to say that now days, I use comments wisely and am always looking for ways to avoid repeating myself.

Another auxiliary skill I developed while building this compiler was the ability to hand write ia32 assembly code. My only experience with an assembly language had been with MIPS and the two languages are very different. Hilfinger is big on practical knowledge, and since few (if any?) use MIPS outside of academia, he figured it’d be better for us to learn ia32 and use it as the target language. I, being very results oriented, wanted to learn only as much of ia32 as I needed to compile python code but we naturally ran into a lot of problems in the compilation. The only way we could figure out what we were doing wrong was to look at the assembly, figure out what it was doing, and then pinpoint what it was doing wrong, so that involved me learning a lot of the details that I didn’t set out to learn. By the end of it, my way of debugging was to look at a python program, hand-write the assembly for it, and then work to make our compiler produce similar output. I actually got pretty fast at it, much to my
surpise.

The most rewarding thing about the project was that it was really cool to see it work correctly. We tested by comparing the output of our binaries with the standard python interpreter (which actually made things really easy to test), but it was really cool to see all of our test programs compile and run correctly. When we finally got all of our tests to pass, I definitely felt a sense of accomplishment from completing such a monumental task. I don’t know if you get that sense in real software development, because your software is never “done” but the relief/joy/pride in completing almost made all the effort worthwhile.

The project isn’t something you can show off to a lot of people (like our pacman projects from AI), because I wouldn’t even expected non-computer-saavy people to know what a compiler is, but I find this to be further validation of how cool the project is. When you build a website and show it to people, they generally react positively, but when you build something that people don’t understand and they stare blankely at you, it validates that you are good at what you do. It’s similar to how my friends were awestruck when they found out their GSI (graduate student instructor) was studying quasi-smooth derived manifolds. When you are studying something that “no one” knows about and you’re successful, it’s very rewarding.

Everyone at Berkeley warns against taking compilers, because of how hard it’s supposed to be. However, my advice to Berkeley CS undergrads: definitely take the compilers class. I think it’s the single class that I’ve learned the most in, and it’s actually pretty rewarding too. But be prepared to work really hard.

I just finished taking a compilers class (well except for the final), and it’s been the single hardest class I’ve taken in college. Homeworks were non-trivial, exams were very difficult, and the class project was to write a compiler for a subset of python. As far as class projects go, this one has been completely ridiculous, my project partners and I have devoted weeks to building this compiler and fortunately we managed to finish it, but many groups I believe did not.

Anyway, in designing the compiler, I developed a new understanding of python features, despite having programmed in python for over a year.  My group and I found a lot of really crazy features of python that lead to problems when designing our compiler. I’m not going to talk about all the cool things that everyone knows about python, like lambdas, function values, nested functions and so on. I thought it would be fun to mention some of the really cool stuff here.

Dynamically Adding to Classes

Python basically implements classes as dictionaries. Instances are simply copies of the dictionary (well technically they are copied lazily, using copy on write), but instances naturally contain all of the mappings that the class contains (as they should). However, you can dynamically add mappings to classes so I can do something like this:

And I can even do this for methods:

When we discovered this, my project partners and I were amazed. It’s a really cool feature but I can hardly see a use for it (if you do see one, please let me know). Further, it makes implementing classes pretty inefficient since you can’t use a virtual table approach that C++ and Java can use.

Differentiating functions and methods within classes

We submitted our project after thinking we were done and “thoroughly” testing everything. A couple of hours later, we got feedback from the auto-grading system saying we failed (among a couple others) a test case that did something like this:

We failed this test case because we assumed that any call to an attribute reference was a method call, and so we implicitly pushed on

as the first argument. This isn’t the correct behavior as we then pushed on one more argument than we should have. When we saw this, we were again amazed. Python somehow knows that

is a function and not a method, so it knows when it should implicitly push on

.

We hacked together a fix that I thought was pretty cool. We were representing all functions as boxed 12 byte function values, where the first byte pointed to a dummy virtual table, the second byte pointed to the code for the function and the 3rd byte was the static link for that function. Since from this perspective, functions and methods were exactly the same thing, we had no way to tell whether the object we had was a function value or a method value, so we were pretty stuck. Instead, we added a byte to all function values that kept track of whether they were functions or methods (yeah this is a huge waste of space, but performance wasn’t our priority at this point). Then at runtime, we are forced to check whether the value we’re trying to call is a function or a method, and behave appropriately in each case.

Unfortunately there’s a huge increase in code size. Now every call in python requires the check mentioned above, and two distinct call instructions, of which only one would get executed (because we were required to push on the number of arguments as a parameter to the callee function). We discovered this bug like 2 hours before the deadline, and we weren’t being graded on performance, so we didn’t really care about this issue. I am interested to know how python does it. My guess is that in the class dictionary, methods aren’t stored as “function values” so you would be able to tell right away, but I haven’t looked it up. If you know how python does it, let me know.

If-Expressions

I didn’t really use If Expressions before this class, and now that I’m more familiar with them, I think they are actually quite useful in writing concise code. I’m not talking about the standard

clauses, but more of the analogue to

syntax in C. And this feature isn’t that crazy, in fact it’s what I expect python would do. So an if expression looks like

and the semantics are that this statement returns

if

evaluates to

and otherwise it returns

. So it’s just like the

construct in many other languages. It’s cool when you use it with function values. For example:

And that’s really cool. I can really concisely choose what function I want to call at runtime. I haven’t thought of a lot of uses for this exactly, but I can definitely see myself taking advantage of it’s presence.

The global keyword
There are some really cool features with

that I think are pretty standard in most languages but that I’m not used to seeing. For example:

This means that the when you declare

as global, if it’s not already bound in the global environment, you make a binding for it. I’m not exactly sure how this works in other languages, but I can totally see a language throwing an error if

is not bound in the global environment. Here though, python is smart enough to make the binding for you, and then you can use it after the call to g. This means that there are some really interesting ways that you can dynamically add names to the global environment.

So I’m sure there are more really interesting features of python that I haven’t discovered, and I’m pretty sure there are some that I have found that I’m just no remembering right now but these are some of the coolest language features I’ve seen. As I mentioned throughout, some are definitely more useful than others and I’m sure that in some cases these may be undesirable. If you know of any crazy python features that I didn’t highlight, I’d be interested in hearing about them.

So haven’t written a techy/nerdy post in awhile and I presume that’s because my life outside of work hasn’t been that nerdy during the summer. But I thought it’s time to return to my normal self and so… lets talk about python.

This article is titled the way it is because I’ve heard that phrase uttered so many times in the past year or two that it’s insanse. So I spent a little bit of time last summer learning python and the interns and I worked on a project in python, but it wasn’t too involved and I promptly forgot a lot of it in the months to come. I still used php or perl for a lot of my scripting purposes because I was familiar with them and my friends would continuously nag me to make the move over to python, but I never really got around to it.

So this summer, I was initially given the option to write in whatever language I wanted and thought that it would be a good time to learn python, especially because it’s used in a class I’m taking next semester anyway. I took about a week in the beginning of my internship to learn about python and ported some of my old code over to python. I already knew that python was pretty cool, but it seriously makes programming much much faster. And even though I ended up using perl for my intern project, I’m pretty happy that I learned python and I think I’ll be using it more in the years to come.

Ok so why is python so cool. First there are the reasons that everyone says, it’s like writing pseudo-code, but then it actually works. That’s pretty cool because programmers learn to think in pseudo-code but then have to translate that to whatever language. The closer the language is to pseudo-code the better.

It’s interpreted, which has pros and cons. Interpreted languages are generally slower than compiled languages, and yes I think python is slower than C, but for internal scripts where performance isn’t that critical, python being interpreted is pretty helpful.

Python is a lot like scheme/lisp with

expressions and functions as first-class data. I was disappointed that you can only have 1 line lambdas, but they’re still pretty useful. And passing functions around is amazing and extremely useful. Also has built in functions like

and

which just make list manipulation so much easier.

Consider this, lets say I have a list of numbers and I want to make a sorted list of all the even numbers. In python…

In most other languages (except lisp)… I’m pretty sure it would be a lot less concise. And yes the same sort of thing can be done in scheme, but I like scheme a lot too.

I like the way that python allows me to include my test cases of a module within that actual module. The

feature is pretty cool. You can’t really do that in perl and it’s annoying because I need to have a testModule.pl script for every Module.pm. With python I pretty much reduce the number of files I have to worry about by a factor of 2.

Also python is pretty easy to read and that makes your programs easier to maintain. I’ve been experiencing this problem where perl isn’t that easy to read (especially if you use a lot of the uncommon features) and now that I have to go back and make changes to my code it’s pretty hard to figure out where I’m supposed to look and how I’m supposed to make the change. And not that I’ve done this, but I think it’d be a lot easier if I wrote in python.

Anyway, I’m not really an expert on python or programming languages in general. In fact I haven’t even used python for a substantial project or anything, but I have been reading about it and playing with it so I found some things that I like. And I think I’ll be using python more in the future so I’ll become more and more familiar with it and probably find more things I like and also some things that I can’t stand.

Disclaimer: If my facts are wrong here please feel free to correct me because these were the impressions that I got and it would be good if I got them corrected.

During this break, I’ve had a pretty hard to keeping myself occupied. I’ve been playing a lot of music and hanging out with my friends a lot, but I haven’t really been in touch with my nerdy programming self apart from this company that I’m working on. At the same time, my brother has been talking about this whole “viral” movement and we’ve been discussing strategies to get your product out to tons of users with minimal effort. One of the obvious solutions is to make a Facebook application which is immediately available to the however-many-million users there are on Facebook and is also easily spreadable via the invitation process. I decided that I too would jump on this all-too-techie bandwagon and make myself a Facebook application.

Over the summer, I was very against the whole Facebook platform movement (you can read about it here) and I’m still not really happy with a lot of things that I’ve heard about Facebook, but I made this app more for entertainment than for anything else. I’m also not very good at using client libraries and api’s and whatnot (I’m really impatient and don’t like to read things) so I figured this would give some practice at working with an api that I definitely needed for the success of my app.

I’ll cut to the chase. You should add this application. Now you may ask: what exactly is it? Well, it’s called Rumor Mill and essentially it’s a way for you to make up, or publicize rumors about your friends. It’ll also keep you up to date with all the latest rumors (real or not) about your friends and let you determine if the rumor is true or not. Once you make this judgment, it’ll show you what other people thought about the rumor. So, why should you add it? Well first of all, what’s the harm? It’s very unobtrusive; it takes no space on your profile page and it remains dormant until someone makes up a rumor about you, when you’ll get a mini-feed notification about aforementioned rumor. Secondly, it’s fun; who doesn’t enjoy make up random stories about your friends and seeing what other people think about them? I think that there’s tons of potential in this application and hope to see the subscriptions skyrocket in the near future.

In reality, I didn’t spend that much time making the application (Sunday and Monday) and I don’t really plan to spend much more fixing it or doing any other Facebook development. I kind of wanted to see what all the commotion about Facebook development was about. I thought I could see how popular it gets (you should add it! and use it!). I also want to switch hosting companies and this other company has a discount (it’s free) if you’re hosting a facebook app on your server.

Anyway that’s my little bit of publicity, add the Rumor Mill!

I haven’t had much time to work on any personal projects in the past couple of weeks so I figured I would write about the research project that I’ve been working on during this semester. I’m working with one grad student and another undergraduate on a new language that’s supposed to make it easier for developers to reason about security issues in their code. The other undergraduate and I have so far been working on a documentation system for the new language and we’re just about done with that and starting up a much more challenging project.

The language (called Joe-e) is a subset of Java that gives the developer less power in dealing with the system. Joe-e code ascribes to the principle of least authority, which means that objects should by default be given no power (authority) and should be granted authority on a need only basis. Compared with the norm, where objects typically have access to everything and must be explicitly restricted, applying the principle of least authority makes it substantially easier for a developer to reason about which objects have access to other objects. In this sense developers can determine more about each of their classes and thus they have a better idea of what would happen to their code if something went wrong in one of the classes. As I haven’t explicitly worked on the security features yet, I don’t know much more about the language itself, but if you’re interested, feel free to read more about it on the language website.

My partner (the other undergraduate in the group) and I have until now been working on a automated documentation generating system for the language. Since the language is a subset of Java, it makes sense to use javadoc (java’s documentation system) but we had to augment it to include some of the other features that we required. We made our documentation look very similar to Java’s API, so that java developers don’t have a hard time switching from java to Joe-e. Everything that we’ve done has just been added to the standard Java API look in a nice and clean way.

In Joe-e, a lot of the Java library classes have been restricted in accordance with the security principles of Joe-e, and our documentation system needs to indicate which parts of classes have been suppressed and why. So one of the main things that we’ve done in our documentation is mark which methods, constructors and fields have been suppressed and why. Another feature of Joe-e is that library classes can have honorary implementations of certain interfaces that provide information about the classes authority. We’ve added a section in the documentation to indicate which of the Joe-e interfaces this class honorarily implements as well. Other than that, there aren’t many differences between the joe-e API and the java API.

When we started working on this project, both my partner and I thought it would be really easy, but it’s taken us almost three months to finish. We’ve been working on it pretty regularly and dedicatedly, but we’ve run into tons of problems with javadoc’s source code that were serious roadblocks to our progress. For example, one such problem is that the javadoc’s API has been locked making it “impossible” to extend the standard javadoc classes and create your own documentation generation system. We ended up spending a lot of time looking at different ways to bypass this lock without re-writing a lot of code ourselves and finally came up with a pretty good solution. Another big problem was that on sun’s website, the information about customizing javadoc applies to java 1.3 and the javadoc tool has completely changed since then. As a result we had to look through tons of source code in order to figure out all the details of javadoc when all we really needed was an overview of it. There were a couple of other stupid problems that we had to deal with which I guess were pretty educational because I got to see how larger software projects worked but overall I found them to be very annoying.

When we got down to writing our own code, it was very straightforward. We ended up extending all the classes in the javadoc source code and just modified a couple of methods in some of the classes to provide the behavior that we wanted. It really wasn’t that challenging of a project, it was just that we had to deal with all of this random problems that made the project take so much longer than I expected.

So I hope to finish up the project this week and put it up on the Joe-e website on Monday (which will be really cool). My partner and I have already started work on our next project, which sounds a lot more challenging and interesting. Overall, I’m really enjoying my research this semester, and am excited to stay with the team next semester and for the future.