Posts Tagged 'Scheme'

SICP Study Group, Weeks 4 & 5

I don’t know where to start…

First of all, I must say that this is one of the most interesting books on programming I’ve ever read. (and yes, I haven’t read so many books on programming, for now) In the last few days I constantly go to bed around 3:00 am, (it’s 1:30 am, as I’m writing this). I’m getting worried, that I may end up in an asylum, muttering „cadr“, „cdadr“, „cddar“, and so on, which the doctors will take for some kind of ill-spoken obscenities, and will put me to sleep with… Wait, what? Yes, it’s that worse. 🙂

I’ll start the sensible part of this post with my „infrastructure changes“, which I made during the last week. I’m finally using tests! I used this library, and switched to GNU Guile as a Scheme implementation. This shouldn’t be a problem, since I’m not using anything specific. I should mention that Guile tends to have somewhat tight constraints on it’s stack size, since I encountered twice „STACK OVERFLOW“, when I tried to run recursive versions of „sum“ and „accumulate“ with larger volumes of data. The iterative implementations work fine, but I will search for a way to increase the stack size.

One of the ways the tests show their usefulness is that they remove the testing from the source file with the solution, leaving much more clean code there. The other one is the easier refactoring, of course. It’s a win-win all the way, so I recommend them to anyone, that has at some previous experience with Scheme. I also wrote a simple Emacs LISP after-save-hook, that runs the tests (if any) for an exercise after each save. I also tried to abstract it as a separate function, that could be attached to a key combination, and I failed, but I’ll launch another offensive on my Emacs soon. 🙂

And for the tiny list of interesting stuff, that can be found in the exercises of Chapter 2:

  • cons, car and cdr can all be expressed as simple procedures, as shown in ex. 2.4. Stefan showed a problem here – how can we define pair? to work with this implementation?
  • I knew from before, that we can encode pairs of positive integers with positive integers (ex. 2.5), but is was fun to do a simple implementation of the idea in Scheme. It reminded me of the university course of Computability and Complexity, where we used this idea to encode programs for Registers Machines with single numbers. (like, the number (228234 + 217532) can represent a program, that takes two numbers and finds their average.) It was one of the most interesting courses I’ve ever attended. 🙂
  • If the previous two where not enough, you get Church Numerals (ex. 2.6). I’m curious how one can implement comparison of Church numerals.
  • Practically all the exercises in 2.2.3 were very contenting, although most of them were „fill the missing function in the slots“, it was like learning to ride a bicycle, with stabilizing wheels. 🙂

There are other interesting things, of course, but I’m tired and it 2:30 AM now. So, as a compensation, here is a link with resources on Scheme – The entire site is worth checking, if you are interested in programming languages and have free time.

Happy Scheming! 🙂

SICP Study Group, Week 3

Chapter 1 is over! 🙂

It was loads of fun at the end – higher-order functions that abstract so many tedious tasks, (like repetitive application of a function, for instance), which are later used to describe so naturally ideas from numerical analysis. To me, the first chapter shows that Scheme is little, but very powerful language, and you can do so much work only with simple procedures, because of Scheme’s treatment of procedures as „first-class citizens“. The last one means, that procedures can be named, passed as arguments to other procedures and returned as results from other procedures. (They may also be part of data structures, but we won’t see it until somewhere in Chapter 2).

A brief look through the things I found most interesting:

  • „average-damping“ (ex. 1.36) is some kind of sorcery, that will speed up your searching for fixed-points of functions. Neat!
  • There may be worse things then Ackerman’s function – I evaluated the expression ((double (double double) inc) 5)
    (ex. 1.41) by hand, because we did it this way back with my first SICP Study group. Now I feel more confident in my understanding of the applicative-order evaluation.
  • „accumulate“ (ex. 1.32) is very useful abstraction – it goes beyond simple accumulation of numbers, and can be used for accumulation of other objects, like in my third solution of ex. 1.43 – (define (repeated f n) (accumulate compose id (lambda (x) f) 1 inc n)), where compose is from ex. 1.42, and id is the „identity“ function (id(x)=x).  I found this both simple and cool. 🙂

But some unfinished exercises remain – we are still struggling with the time complexity of the procedures in ex. 1.14 and 1.20,  I still haven’t managed to make sensible improvements to the ex. 1.23 and 1.28, and there are a few other obstacles left. At least for the first, I hope that we will come up with something at our next meeting.

I can’t wait to play with the data abstractions, that wait ahead!

SICP Study Group, Week 1 & 2

Since I failed to write something last week, here are the last two weeks, combined:

To begin with, I find the book extremely interesting and motivating. The authors talk of programming as a craft, even an art, to some extent. You get the feeling that you, as a programmer (or to-be-programmer) are part of something bigger, that stretches back to the first mathematicians. There are beautiful metaphors („the spirit, that lives in the computer„), and interesting quotes („I think that it’s extraordinarily important that we in computer science keep fun in computing...“, Alan Perlis). Fun is the word. ☺

The first chapter teaches us about „Building Abstractions with Procedures“. So we tackled a lot with procedures, the processes they generate, and their orders of growth. The little downside is that only with procedures you cannot make very interesting examples and exercises (with a few exceptions, mentioned below), so there is lots of mathematics in the first chapter. Not to be considered as a bad thing, but it gets pretty tedious after a while.

A few years ago I participated in another  SICP study group, although we didn’t label ourself with such fancy names back then. ☺ The experience there was quite different. First, we had a teacher, who was profound in Scheme and in programming in general. Second, he had composed lectures, and guide us carefully through each one. Third, we had diverse backgrounds and hadn’t attained courses in university-level mathematics, which is somewhat required for the material. So our teacher swapped some of the examples and exercises in favour of more intelligible ones.

This time all the participants have studied Computer Science, or Informatics, so we all have some understanding of Calculus, Numerical Analysis, Abstract Algebra, etc. We are going through each exercise, be it some mathematical proof, or some other task, that does not require coding. Also, we are moving very fast through the material, because we are able to understand most of it on our own. The approach is different from my last experience, but I feel that it works equally well for me.

Anyway, here are some things, that I found interesting during the last two weeks:

  • Ackerman’s function (ex. 1.10)! We still can’t think of a real-world application of this beast (except as an example in the courses on Computability and Complexity, of course ☺)
  • Invariant quantity (ex. 1.16). Actually, I can’t recall the last time I used this technique somewhere (if I ever used it anywhere), except in the previous course on SICP. It was very contenting to find the solution for this one, although I’m ashamed to admit that it took me nearly an hour. ☺
  • You can find the n-th Fibonacci number in logarithmic number of steps (ex. 1.19). This is awesome! Alas, I already knew it and couldn’t experience the same bedazzlement once again. ☺
  • It’s very fun to tackle with the order of evaluation of arguments (ex. 1.5, 1.6 and 1.20). You can see that in normal order evaluation some procedures work as expected, while in applicative order they fall into infinite recursion. Yet, functions with a constant space complexity can become functions with linear space complexity, if they are evaluated in normal order. Awesome! ☺
  • Fermat test and Carmichael’s numbers. (ex. 1.27) Curious stuff from Number theory.
  • Higher-order functions are very fun. (ex. 1.32, 1.33). I enjoyed watching how tedious sums and products become simple one-liners.
  • You can do miracles with Unicode! 😃

Aside from the fun and curious stuff, I also encountered some not-so-funny issues, which have nothing to do with the book, but more to do with me:

  • Time management. I encounter difficulties with this since high-school. So as of yesterday I started using the Pomodoro Technique. For now, I just strive to develop the habit of focusing on some task (like this post) for 25 minutes and tracking the number of pomodoros, which is fun and contenting, so I think this will help me. Also, I am finally stimulated to stop staring at my screen every 25 minutes, to stand up and stretch a little. This is bliss! ☺
  • My written English is not very good, which is normal, since I don’t practice it very much. These posts are a chance to do it, and that is the reason I’m writing in English. The lack of experience takes it’s toll. First, I spend most of the time trying to remember (or find) specific words. I’m through my fourth pomodoro for this post, which is too many, I fear. Second, I don’t want to imagine what my style will look to some more profound than me. I probably look like some archaic, snobbish illiterate. I’m pretty decent writer in my native language, so such thoughts are almost painful. But everything will get better with time.
  • Talking of style, I must do something for the commit messages in GitHub. „Add solution for exercise X.“ is not very helping, especially when I browse the repository to recall the interesting exercises. I will try to redact them as soon as possible.
  • I also didn’t manage to finish all exercises, I actually skipped few of them. This will also be corrected as soon as possible.
  • Stefan set an example by using test-driven approach in his solutions. I still can’t find the time and motivation to do the same, but this is on my TODO list, too.
  • I also felt the need to take notes while I’m doing the exercises, not days after that. Point taken.

There may be other things that I can’t remember now, so I may redact this post in a few days.

All in all, there are many benefits from the study group – both technical (abstract concepts, fun facts, etc.) and personal (self-improvement, meeting new people, exchanging ideas and so on). I’m eager to see what will come next!

SICP Study Group

I’m participating in a newly created SICP study group (discussions are in Bulgarian), in Sofia.

The point is to read the book „Structure and Interpretation of Computer Programs“ by Hal Abelson and Gerald Sussman and to do all the exercises. Great stuff! 🙂

Now and then I will write here what I’ve learned from the past week’s material, what I’ve found interesting, etc. My solutions can be found at GitHub.

I’ve tried reading the book on my own many times, but I never got past chapter 2. The benefit of doing the reading and exercising in a group is that you have extra motivation to get your work done, and that there are people to help you, of course. I look forward to it with anticipation.

To be continued.