Posts tagged: scheme

MSR internship and some retrospection

I feel I can finally write about: I got accepted for a three-month internship at Microsoft Research Cambridge! This means I will be developing GHC and, hopefully, doing some serious research on the subject of functional programming and compiler implementation. My internship starts tomorrow, on 1st July. I’m not yet 100% certain about the exact topic of my research, so I’ll refrain from going into any kind of technical details for now and I will focus on my personal experience with functional programming. I feel this is really a good moment to summarize the past 1,5 year. I learned about functional programming at the very beginning of 2012 and since then I progressed from knowing completely nothing to being in Cambridge – something I would have not imagined 18 months ago.

Somewhere around July 2011 I finished writing my PhD. I had yet to deal with many formalities – which in the end took 8 months – but the most important part of my work was done and I only continued research on a few minor subjects that I ran into while writing a PhD. Somewhere in October I decided I need a break from all my current research topic – I finally wanted some time to pursue topics that interested me all along and for which I never had time. Compiler construction and theory of automata were two main topics I had in mind. That was the plan, but it wasn’t meant to work out, at least not yet. Somewhere around December 2012 I stumbled upon a book “Seven languages in seven weeks”, which was my first contact with functional programming. I didn’t follow the book exactly. I read chapters about Ruby, Io, Prolog (so much fun!), Scala and Erlang, but instead of reading chapter about Clojure I went for Scheme. I read R5RS language specification and The Little Schemer and when I reached the chapter about Haskell I decided to read Learn You A Haskell instead. At that point I already knew that Haskell is the functional programming language and I think that this was the moment I started having some serious plans about functional programming. But at the same time I was figuring out how to learn about compilers. It was April when Stanford University announced their two online courses on Compilers and Automata – these were really godsend. The Compilers course ended in late June. This concludes my first six months of contact with FP and I think that these months were extremely intense. I learned theoretical and practical foundations of compilers, a new programming paradigm and some new languages designed in that paradigm. I also started reading research papers on functional programming, with a focus on implementation of GHC. At that point I didn’t even try to work on the source code, but I was trying to understand how the compiler is designed.

The next six months, from July to December, were not as fruitful. I picked up interest in doing data-parallel computations in Haskell, as this seemed to be an active topic of research and also related to my PhD work. I made a failed attempt of an efficient parallel implementation of a wavelet transform. Although I wasn’t successful, my time was not wasted: I learned how to write, test and benchmark libraries in Haskell and also read a lot of papers on FP. I also got in touch with Ben Lippmeier, who pointed me to one problem with GHC he needed fixed. This was somewhere in January 2013. I already started reading the source code of GHC in December, but now I finally had a particular problem to solve. It was the time to start working on GHC. That is mostly what I did during the last six months, although I also managed to spend some time on theory (more papers and a book on combinatory logic).

As for the internship, I decided to apply for it in February. I polished my CV and cover letter (many thanks go to my friend Marek for his help) and sent my application at the beginning of March. After an interview with Geoffrey Mainland and Simon Peyton Jones I got acceptance notification at the beginning of April. And here I am in Cambridge, over 1300km from home, waiting for my first day at Microsoft Research.

Y-combinator in Matlab

For over 3 years my main programming language was Matlab. Matlab was designed for scientific computations – it has a lot of build in functions for numerical computation as well as some syntactic sugar which allows to manipulate arrays easily. Matlab is imperative, supports object oriented programming (though the implementation is very bad) and uses dynamic typing, so all type checking is done at runtime. One of Matlab’s features is the ability to store function handles in variables. Does this ring a bell?

Yes! Functions as first-class citizens. This should allow to do some functional programming, right? I decided to give it a try and write Y-combinator in Matlab.

A few words about Y-combinator

Let me first write a few words about Y-combinator in case you’re not familiar with it. Look at this recursive definition of Fibonacci function:

function val = fib( n )
  if ( n == 0 || n == 1 )
    val = 1;
  else
    val = fib( n - 1 ) + fib( n - 2 );
  end
end

This recursive function – and probably all other recursive functions that you’ve seen – works because we are able to give name to a function, which allows the definition to refer to itself. What would happen however if we were unable to give name to a function? This might seem a bit abstract, but think about anonymous lambdas. As the name suggests they are anonymous. They have no name and therefore cannot refer to themselves. But there is a way to make anonymous recursive functions by using the Y-combinator. I will not go into details of how and why the Y-combinator works the way it does, but I strongly encourage readers to explore this subject. The best way to learn about Y-combinator is to walk through its derivation. This is a truly mind-bending exercise. I needed about 5 days to understand how Y-combinator works but when I finally did it was one of these “ooooohh” moments.

You will find a derivation of Y-combinator in the 9th chapter of “The Little Schemer”. The book might be a bit hard to find and I consider this derivation to be a bit criptic (though the book itself is great). Luckily Peteris Krumins extended derivation from “The Little Schemer”. I will base my post on his results. So, the final version of the Y-combinator written in Scheme is:

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

and the example of usage (also in Scheme) is:

((Y (lambda (length)
     (lambda (list)
       (cond
         ((null? list) 0)
         (else
          (add1 (length (cdr list))))))))
 '(a b c d e f g h i j))

The above listing shows an anonymous recursive function that calculates the length of a list.

I will present my results to match those above as closely as possible.

Anonymous functions in Matlab

In order to work with Y-combinator we will have to define anonymous functions. In the Scheme code above an anonymous function for calculating the length of a list is passed as a parameter to Y-combinator. It turns out however that anonymous functions in Matlab have some limitations. Let’s take a look at the documentation:

The syntax for creating an anonymous function from an expression is

fhandle = @(arglist) expr

Starting from the right of this syntax statement, the term expr represents the body of the function: the code that performs the main task your function is to accomplish. This consists of any single, valid MATLAB expression.

The fact that Matlab allows anonymous functions to consist of only one expressions has serious consequences. Imperative languages divide all their language constructs into two categories: expressions, which return some value and statements, which don’t return any value1. Sadly, the control-flow constructs like if and for are statements, which means that we can’t include them in an anonymous function. This is problem, because length function shown above needs a conditional instruction to check if the list passed to it is empty or not.

Therefore, our first step is to create a new version of if construct which will be an expression and not a statement. There are a few different ways to achieve this. I decided to use cell arrays. Cell arrays are Matlab’s data structure similar to arrays, except for the fact that every cell can hold different type of value. My custom if instruction will take two parameters: a predicate that evaluates either to 1 (Matlab’s true) or 0 (Matlab’s false) and a cell array with two function handles. The code looks like this:

if_ = @( pred_, cond_ ) cond_{ 2 - pred_ }();

The pred_ variable is the predicate – either 0 or 1 – and cond_ is a cell array. If the predicate is 0 then second function in cond_ cell array will be used. If the pred_ is 1 then if_ will use first function in cond_ cell array2. Notice that there’s () after cell array index. This is a function application. This means that after selecting one of two function handles, the function pointed by it is executed immediately and if_ returns value returned by that function. Here’s an example3:

 >> if_ ( 1 == 2, { @() disp( 'The predicate is true'), @() disp( 'The predicate is false' ) } )
The predicate is false

Had we removed the parens, if_ would return a function handle allowing it to be evaluated later:

 >> if_ ( 1 == 2, { @() disp( 'The predicate is true'), @() disp( 'The predicate is false' ) } )
ans =
  @()disp('The predicate is false')

This is somewhat similar to lazy evaluation.

These are not the only limitations of Matlab. Consider the example below.

f = @(x) x == 1
g = @(x) x

We created two functions: f tests its parameter for equality with 1, while g is the identity function – it returns its parameter. If we apply g to f, we should get f, that is a handle to a function that tests its parameter for equality with one:

>> g(f)
ans =
  @(x)x==1

That is what we expected. We got a function handle to anonymous function that accepts one parameter. It is reasonable to expect that we can now pass parameter to that handle. Unfortunately, Matlab will not allow us to do so:

 >> (g(f))(1)
(g(f))(1)
|
Error: Unbalanced or unexpected parenthesis or bracket.
 
>> g(f)(1)
Error: ()-indexing must appear last in an index expression.

So we cannot chain anonymous function calls that easily. We have to use Matlab’s feval function, that evaluates a function handle with given parameters:

>> feval(g(f), 1)
ans =
  1

The Y-Combinator

With this knowledge we are now able to rewrite Scheme code presented earlier. Here’s how Y-combinator looks like:

Y   = @( le ) feval(            ...
          @( f ) f( f ),        ...
          @( h )                ...
            le( @( x ) feval( h( h ), x ) ) );

This is almost the same as Scheme code presented earlier. We just replaced lambda with @ (both denote anonymous function declaration) and changed function application syntax to match Matlab. Before we rewrite the length function in Matlab let us define some helper functions:

if_  = @( pred_, cond_ ) cond_{ 2 - pred_ }();
add1 = @( x ) x + 1;
cdr  = @( list ) list( 2 : end );

We’ve already seen if_, but it’s here just to remind you that we need that declaration. The add1 function increments its parameter by one, while cdr emulates Scheme’s cdr function that returns tail of a list. Finally we can see Y-combinator in action:

feval( Y ( @( length_ )                           ...
  @( list )                                       ...
    if_(                                          ...
      isempty( list ), {                          ...
        @() 0,                                    ...
        @() add1( length_( cdr( list ) ) ) } ) ), ...
  ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' ] )

This code can be placed into a script (say Y_combinator.m) and evaluated:

 >> Y_combinator
ans =
  10

Conclusions and further reading

As you can see, Matlab’s support for function handles allows to write Y-combinator. The result looks fairly simple, but I must admit that it wasn’t straightforward and I had some hard time struggling with syntax. Matlab’s functional programing capabilities are very limited, but there are a few more things that can be done. A more in-depth treatment can be found on A Page of Insanity blog here. The solution presented there is very similar to mine. Check out also this gist to see a different approach. See also Mike Vanier’s blog for more details on Y-combinator. I find Mike’s derivation a bit harder to follow, but Mike discusses both strict ans lazy versions of Y-combinator (I used only strict version).

  1. Please tell me if there exists an imperative language that does not have this distinction. []
  2. Matlab uses 1-based indexing []
  3. Text preceded by >> is typed into Matlab prompt []

Stanford opens new online courses about Compilers and Automata

A few months ago Stanford University started a great initiative: it offered free online courses for everyone. Courses were mostly about computer science stuff (Natural Language Processing, Machine Learning, Computer Vision etc.). If you didn’t take part in these courses, then you must know that they are just like normal classes at the university. There are lectures (about 2 hours per week), tests after each week, final exams and rather demanding programming assignments. I enrolled to Natural Language Processing, but I have to admit that I couldn’t keep the pace and stopped following the course after about 3 weeks. Perhaps I wasn’t motivated enough, since I NLP has no connection to my research and I wouldn’t be able to use the gained knowledge in practice. Yesterday however my motivation jumped to maximum, because I got a newsletter about a whole bunch of new courses. Among them are two courses, which are of high interest two me: Compilers and Automata.

Recently I got very interested in the compiler construction subject. I got myself the Dragon Book, but it’s really huge so I think I wouldn’t read all of it. I also visited #compilers IRC channel and got some very valuable hints on how to dig into the subject of constructing a compiler. I was suggested to begin with reading some sort of “Lisp interpreter in Lisp” tutorial. I chose Scheme as my Lisp dialect and – knowing nothing about Scheme – I read the R5RS language specification (only 50 pages!) and The Little Schemer (chapter 10 shows how to do a Scheme interpreter in Scheme). I’ve also found Write Yourself a Scheme in 48 Hours tutorial, which shows how to write Scheme interpreter in Haskell. This is a bit more advanced and, despite what author claims, is not suitable for Haskell newbies like myself. I decided to get back to that tutorial after learning some more Haskell, especially monads and Parsec, both used heavily by the author. Guys at #compilers further suggested that after reading this kind of tutorial I should read Niklaus Wirth’s “Compiler Construction”. Indeed, the book looks very accessible. Another usefull advice I received was “the older the better” since fundamentals of compilers haven’t changed much and the only substantial progress was achieved in the back-end1 development. However, the most motivating was the estimation that writing a simple compiler from scratch should take about 6 months. Nevertheless, learning everything by myself from scratch was a very slow process and I wish I had someone who would teach me. The course on Compilers from Stanford is therefore a real blessing. Well, looks like my wish was granted.

The course about Automata is also something very exciting. I have a book “Introduction to Automata Theory, Languages, and Computation” by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. I approached this book twice but always got stuck around third chapter. Not that I couldn’t understand it. It was my motivation that failed. Anyway, I feel that as a computer scientist I should have a basic knowledge of this subject. Believe it or not, but my studies didn’t cover the subject of automata and computations!

There’s a lot of other courses, not only about computer science, so I suggest to take a look. Perhaps you’ll find something interesting for yourself. Participating in NLP course had showed me that these courses are very demanding and require a lot of time and effort. This means that I’m going to pick only the Compilers course and concentrate solely on it, hoping that the Automata course will be repeated in the future. Both courses start this Monday (April 23rd).

  1. back-end is the part of compiler responsible for generating the final code (most often a machine code) []

Staypressed theme by Themocracy