LP: CS51 – Laziness and Infinite Data Structures; also Music!

CS51 just keeps on with the surprises. I guess not CS51, but Ocaml and functional programming in general, but you get the point.

Lecture 8 was about infinite data structures. Consider:

type ‘a stream = Cons of ‘a * (‘a stream)

Finished reading it? So basically, we are recursively defining our type using the type itself, making it cyclic and therefore infinite. It was a pretty cool concept and it has an almost mysterious aura about it due to the fact that it’s something that by logic would be impossible – we are representing infinite data on finite memory! Of course, there is floating point numbers which are also infinite, but I digress.

As the end nears I see the more familiar paradigms I have become comfortable with. The next lectures tackled objects and events, showing that we do in fact, sometimes need to introduce side effects to our code.

Problem set 6 was quite challenging but a lot of fun, using infinite data structures to represent music as a stream of events. It was strangely satisfying to be able to produce music through code, and I had to admit I couldn’t move on from the problem set without playing a song in it first.

LP: CS51- Midterm, Moogle, and a three-day hiatus

Midterms

I survived my midterms for CS51!

CS51’s midterm was a closed book, no computer exam which was in stark contrast to CS50x‘ open book exams. The midterm was actually pretty easy: the beginning was mostly a matter of syntax (though still quite tricky!) while the latter parts did prove quite a challenge.

Since I’m only taking CS51 through the available online courseware, the midterm was provided in a pdf file. While I could have just dropped annotations for my answer, I figured that we could be a little bit more savvier than that and actually made myself an examination webpage! Strapped with time, I only bundled together the page with a WYSIWYG editor and while it won’t compete with Edx’ exams anytime soon, it gets the job done, and it’s quite pretty too!

You can view my midterm here!

Moogle

Told you Prof. Greg loves cows.

Problem Set 5 of CS51 is Moogle, a search engine a la Google. It really does show the power of Modules; we define a 2-3 Tree module once and have it be used in not only the dictionary and sets, but also in the graphs. We also have to implement the crawler for Moogle, among other things.

Hiatus

I had a bit of a cold these past days that I had a bit of a hiatus and wasn’t really able to continue the class. It’s an understatement that it’s quite a bit of a schedule slip.

LP: CS51 – Modules: Binary Tree, Heap, and Queue

Binary Heap Diagram

Visualizing binary heaps made it easier for me to code it.

Problem set 4 aimed to reinforce the idea of modules, which are cool little things that packages related definitions into one.

To really hammer the point about abstractions, the pset involves writing a Stack using a Binary Search Tree and lists, while making a Priority Queue using a Tree and a Binary Heap. The cool thing about all of these is they only have a single signature, meaning that the client can be using our module and not be afraid of having the code be broken as we increase the sophistication of our algorithms, which was really the case as we moved to the binary heap (that had O(log n) running time).

It took me quite some time to code all of these, and the binary heap was particularly tricky. The diagram I have is actually quite imperative, and the steps and branches int it are actually made as I moved through the coding process. It was basically a snap shot of white-boarding  the problem set.

Next up on my CS51 course is the mid term! Hope I’ll pass 🙂

LP: CS51 – RSA, Bignum, and the Substitution Model

The third problem set involves something BIG

The third problem set involves something BIG

Lecture 4 was about the Substitution model of evaluation, which started out pretty uninteresting (the concept was a bit obvious). Nonetheless it strengthened my knowledge, particularly the bit towards the end which translated how ocaml handled values to code. It involved a meta-circular interpreter, and even intuitively showed how a let statement is turned to a function call.

The problem set was a HUGE problem set; it was HUGE not only in the datatype we need to implemented but also a HUGE pain in the ass.

Anyway, the first part of the problem set was implementing the bignum datatype, a type which can hold an arbitrary amount of integers (as opposed to the standard 2^31 give or take of a standard int). Basically, we translate an int like:

123,456,789

into:

{neg=false;coeffs=[123;456;789]}

In base 1000. Of course, the beauty of this is we can input a crazily HUGE integer like 123,453,126,358,127,854,342,733,193,420 without getting integer overflows, which is necessary for RSA algorithms, the second problem set.

Wait What!

Yup, the second part of Problem Set 3 is implementing the RSA algorithm. Let me just quote the problem spec:

 Not bad for your third CS51 problem set!

Not bad Indeed. So here I am, armed with 5 CS51 programming lectures and emacs (now I try to save everything with C+x C+s, doh!), to implement the RSA algorithm to prevent baddies from stealing important info. Oh, and with a pretty tight schedule of like one hour. Secret Agent 101.

As always, you can view my code on this github link: HERE

LP: CS51– Polymorphism and Higher-Order Functions

When you’re completing a whole 4 year course in one year, the difference between completing a course in 10 days vs 7 days can be quite astonishing. And I feel like I’m lagging a bit.

Right now I’m at Lecture 4 of CS51, while also completing the third Problem set.

Problem Set 2 (which is the third one because of zero-indexing) is divided into two parts, the first part involving writing Higher Order Functions.

Finishing it was a lot of fun! (Which was literally my commit message in github).  Robert Fischer once said that “Ocaml” will warp your mind, and my mind had successfully been. Implementing Higher Order Functions- in which we were not allowed to touch signatures mind you, have opened my thinking to a very different programming paradigm. It was surprisingly exciting to use function composition and list mapping to what otherwise could be solved by a simple for loop, and function currying was both yummy and useful. The level of abstraction that feels always within reach is a very deep one, and I feel I understand recursion in a much more meaningful way.

However, there was an ominous message in the very beginning that seem to warn of a challenge coming in the horizon:

(* TIME ADVICE:
* Part 2 of this problem set (expression.ml) can be difficult, so be careful
* with your time. *)

Part 1 was fun! It was intuitive! It was great! Until I reached part 2.

The second part involved writing a freaking Language for Symbolic Differentiation!
Now, now, with all the things I learned up top, I should be able to do it right? However that doesn’t change the fact that it is both time-consuming AND challenging. I just discovered Scott Young, my big senpai in taking this course, took some of the programming assignments in parallel to other courses, which makes a butt-load of sense really. As stated in the very start of this particular learning project (that is, CS51), I was still deciding whether or not I take another course in parallel, and this option is appealing a bit more to me right now.

DerivRules

The Calculus. Be afraid of the Calculus!

LP: CS51– Function signature and Tuple fun!

I’m chugging along just fine in this CS51 class, but man, does Prof. Greg, not kid when he said he’ll make you feel uncomfortable by pulling out the rug. Functional Programming is very different. It’s not really hard per se, but it forces you to think in a different way than an imperative programming language does.

I spent a lot of time working back and front on the lecture slides and the official course reading (which is the official OCaml Reference) to understand this quirky language. I’ve just worked on the  problem set 1 (zero-index) tasked with writing functions that work with tuples, functions, and types. It was brain melting.

And it was damn fun. Weird return types? No loops? Weird syntax that bites beginners? It’s lovable! Function currying and pattern matching is what I used most in the assignments, but I can already see the elegance of functional programming.

Because of the nature of the course, and the language in general, I cannot be objective in giving a fair estimate of my code by just checking if it works. Imagine my joy when I discovered Code Review, which was part of the Stack Exchange family. Now I’ll even have a group of people who could review my code, and see if it’s good, readable, and smooth!

Not much to show visually, but emacs has a lot going for it that makes it's following understandable.

Not much to show visually, but emacs has a lot going for it that makes it’s strong following understandable.

Another thing that’s trippy is the editor itself. While I’ve heard of emacs before and its reputation for having a cult-y following, this course was the perfect excuse for me to try it out. Most of the key bindings are esoteric, i.e., saving involves pressing Crtl+x Crtl+s, while copy-pasting involves Alt+w, Crtl+y, respectively.

With regards to the problem set itself, the first few ones are easy enough (relatively easy, still a bit challenging) while the latter ones involve writing functions themselves. Here’s a list of them (non-exhaustive):

  • reversed – checks if an int list is in descending order.
  • merged – merges an int list. (involves currying)
  • unzip – unzip a list of int tuples. (okay, ‘unzip’)
  • variance – checks variances within a float list.
  • … and many more.

My favorite among them (the ones that made my head hurt the most) was the last two, which was writing a Run-length encoding algorithm, and a function that computes all the permutations of a list.

The course also teaches you practical programming practices! It is required to write assertions for your functions to make sure it actually works. Now it’s not just about making sure it compiles, but having a sharp eye on different test-cases!

All in all I’m really digging the course, not in the same way as 50, but in a different, much more “down the rabbit hole” way.

LP: CS51 – Abstraction and Design in Computation, First Day, First Impressions

CS-Harvard is coming along just fine! 16 more courses to go!

XKCD on CS51

I have yet to take a technical Harvard course that does not link to XKCD

For this particular month (or 2 weeks, I’m still experimenting whether or not taking two courses in parallel per month or 1 course per month is better), I’m taking CS51, fulfilling my CS systems course requirements (along with CS50).

CS51 is formally labeled as an Introduction to Computer Science II: Abstraction and Design. We will be using Ocaml, a ‘functional & higher order programming language’. From what I’ve seen so far, Ocaml does seem to be quite ‘different’. It is stated at the very beginning that Ocaml is in fact, an ‘academ-y’ language, which might not necessarily increase one’s viability in the job market. However, learning a different programming paradigm can only prove to increase one’s ability as a programmer, so I’d say it’s all good.

Prof. Greg Morrisett, despite the serious aura about him, actually also has a funny air, linking to XKCD, and cracking a joke every now and then. And he likes COWS!!!

Here is the link to the site, though as with other classes, I’m not sure if it’s going to be available at the time of your reading.

Assignment 0

Zero-Index Fun! Anyway, the first assignment simply involves setting up the environment and getting up to speed with the course, running a few commands in the terminal to set up the appliance for CS51.

Interestingly enough, the first assignment involves not only writing my very first Ocaml program but also version control in the form of git. I simply used Github, and here is a link to my repository if you’re interested.

All in all I finished the assignment in about half an hour, though it’s not really fair to be taking note of that since the first assignment is too damn easy.

Keep learning! Until Next Time.

XKCD on Laziness

Laziness is a virtue. Does that mean I can be lazy and just read XKCD strips all day? Pretty please ^_^