Garbage Collector Month Wrap-up!

Friday night we had garbage collector show and tell to show our implementations and ideas for garbage collectors to close off our month of delving into garbage collector development.

Next week we will kick off our new Polymorphic month with part 1 of Cardelli and Wagner’s paper, “On understanding types, data abstraction, and polymorphism” (http://phobos.ramapo.edu/%7Eldant/oop/cardelli_wegner.pdf) 6:30pm Friday night at Bento Miso. You can check out the full reading list over on the github page, https://github.com/CompSciCabal/SMRTYPRTY/wiki/Reading-Schedule.

Earlier in the month, Chris gave a talk at papers we love on teaching garbage collectors (http://www.meetup.com/Papers-We-Love-Toronto/events/219961100/) and he introduced us to an excellent environment for building garbage collectors called plai (http://docs.racket-lang.org/plai/collector.html.), built on top of Dr. racket. Chris couldn’t make it out unfortunately but when working on this myself I referred to his excellent blog posts, talk notes and he also has a few collectors implemented all findable from his blog (http://learningtolearn.sndrs.ca/blog/2015-02-11-garbage-collector-notes-plus-pwl-content/).

Leo showed us his mark and sweep collector which he built in C and which he has used as part of a larger interpretor implementation he also showed us. His mark and sweep collector is checked into the github, https://github.com/CompSciCabal/SMRTYPRTY/blob/master/experiments/inaimathi/memory-management/g.c. Leo brought up a lot of interesting questions from his experience of putting this collector to use in an interpretor. For instance, how do you handle symbols? What about special symbols that are defined by the language? Do they get garbage collected the same as everything else or do you give them there own little box of memory? As just a couple of examples of issues that can arise, among others. It underlined for me just how much the plai environment must help with teaching about garbage collection, as it lets you focus on the collector aspect without worrying about how to build the interpretor at the same time.

We then spent some time going over the trio of collectors I wrote in racket, the mark and sweep, stop and copy, and then a mark and compact approach (https://github.com/CompSciCabal/SMRTYPRTY/tree/master/experiments/scott/garbage_collector/plai/tests/gc/good-collectors). These are all somewhat ancient approaches to garbage collection but seemed like the right place to start for learning about these things. Implementing them in the plai environment was rather fun and helped me understand the subtleties involved a lot better. A couple of comments about the plai environment; one it’s awesome, two the heap visualizer is really cool and useful, and three the assert and test features are boss, I just wish I had used them. I found it quite satisfying to use the heap profiler in debug mode and see the GC mutating the heap step by step. In future if I try a more complex design I would definitely try to break things down into a bit smaller chunks that can be tested individually as it will likely pay off very rapidly in time savings. Debugging by using the heap profiler was cool, but I don’t know that I want to depend on that for debugging again as it can be quite time consuming.

We finished off the night by discussing Dann’s very interesting proposal for a concurrent garbage collector inspired by the field of vermiculture. This was really cool, though we may still be some distance away from an implementation.

See you all next week! Scott

Recap!

Friday night we had a great turnout for part 2 of Wilson’s Uniprocessor garbage collection survey paper. Chris did a great job of taking us through some of the intricacies of generational garbage collection putting us in a good place to start reading next week’s paper, “A Unified Theory of Garbage Collection”by Bacon, Cheng, and Rajan (http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon04Unified.pdf). We will meet at the usual time and place, Friday night at 6:30pm at Bento Miso.

Chris mentioned a couple of tools worth bringing up as I’m going to start playing with them as we work towards hopefully having some sort of garbage collector for show and tell day at the end of February. Chris gave a talk recently on McCarthy’s paper, “Teaching Garbage Collection without Implementing Compilers and Interpretors” (http://jeapostrophe.github.io/home/static/cooper-sigcse2013.pdf) and the author’s related environment for building a testing garbage collectors in racket, http://docs.racket-lang.org/plai/collector.html . Please add in the comments any other resources that may be useful.

Until next time, Scott?

Hey everyone, apologies on dropping the ball last week, so we have two recaps in one this week, let’s get caught up!

First off next week Chris will moderate installment 2 of Wilson’s survey paper, “Uniprocessor Garbage Collection Techniques” (http://www.cs.rice.edu/%7Ejavaplt/311/Readings/wilson92uniprocessor.pdf), and we meet as usual Friday Feb 13, 6:30pm at Bento Miso. You can check the reading list for everything else we have covered, https://github.com/CompSciCabal/SMRTYPRTY/wiki/Reading-Schedule .

Jan 27, Ben helped us navigate some intriguing ideas in the realm of language semantics in Strachey’s excellent paper, “Fundamental Concepts in Programming Languages”. As this topic was I think outside many of our comfort zones there were a lot of diversions where Ben helped explain some of the basics of this field. For instance, a new idea for me was the idea that one should try to identify precisely the true meaning of a given program in a mathematical sense. This is a fascinating concept to me, that I will likely keep thinking about for some time to come, as in my mental model, I think I’ve tended to think of a program as instructions to be performed, and the semantics of what the code does would live at a higher level of abstraction, maybe involving some documentation or some helpful comments in the source code.

Feb 6, Leo started us out on our month of garbage collecting by covering the first 2 sections of Wilson’s survey paper, “Uniprocessor Garbage Collection Techniques”. Garbage collection has a long history in computing, and covers quite a broad spectrum of topics, and Leo did a great job of pulling us through in spite of our many attempts to diverge into tangential discussions. From our perspective today, I think it’s clear that the author’s motivating statements that languages with an effective GC make it easier for programmers to reason abstractly about their programs are quite true. Just imagine trying to teach a high school class on programming, and you ask the students to copy an array. In Python you just tell them to set the new array equal to the old one “A=B”, whereas in C you first have to teach them about how memory works, what a pointer to memory means, and then how to free the pointer later. This is not necessarily a problem, but it isn’t at all what you wanted to teach them. The C programmer is never free to reason completely at the higher level of abstraction as there is always some additional cognitive load to deal with the memory. Section 2 covers several different approaches to GC and their pros and cons and I think helped give us a clearer picture of how we will proceed with our own implementations later this month. There are a lot of subtleties to the different approaches and a lot of trade-offs that need to be considered and I think we will all be going over this section again before the end of the month.

Until Next Time, Scott?

Hey Team!

Last week’s topic of “Open, exendible object systems” garnered a lot of interesting discussion! At first inspection the topic bears resemblance to many concepts near to our hearts and text editors, but the paper contains many subtleties, that may take some time to fully digest, possibly more time than we can pack into one Friday after work session.

This week, Ben will be moderating the discussion of Chris Strachey’s beautiful paper, “Fundamental Concepts in Programming Languages”, (http://www.itu.dk/courses/BPRD/E2009/fundamental-1967.pdf), through to section 3.7. We will meet at the usual time and place, Bento Miso at 6:30pm on Friday Jan 30.

Following up on the discussion from last week’s paper (http://piumarta.com/software/cola/objmodel2.pdf), Leo brought up some interesting videos: Guy Steele on how to grow a language, http://youtu.be/_ahvzDzKdB0, and Gerald Sussman on human computational abilities http://www.infoq.com/presentations/We-Really-Dont-Know-How-To-Compute .

In general, it felt like we only scratched the surface of really understanding the thought process behind the paper, but some attendees (we won’t out you publicly :) were excited to try using the code provided for a couple of projects, so we know at least 1 mysterious “end-user” mentioned in the paper. I’m not sure how much we agreed on many of the aspects discussed, however Dann provided a nice summary of the elegant approach they take in the paper with their message passing object model:

“My big takeaway was that we can factor a message-passing object oriented system down to 8 primitives, and from those build up any kind of inheritance or dispatching we might like. We might not always want to use that exact model, but knowing that it exists – much like knowing that all of Lisp can be built up from 9 primitives – provides a known point in the design space which we can use as a guide on our hill-climbing.”

Thanks Dann! And hope to see you all again Friday, Scott?

Friday night was the exciting round 2 of Cabal for 2015. We ventured forth, coloured pens in hand, into the realm of mathematical problem solving and the Josephus problem from Chapter 1.3 of Concrete Mathematics. Inspired by the getting your hands dirty approach taken in the text, we worked through the problem together, tackling a few different variations and related ideas with varying degrees of success, and enjoying ourselves and learning a few things in the process.

Next Friday, January 23 at 6:30pm we will back at Bento Miso and Leo will be moderating the discussion of the paper “Open, extensible object models” ( http://piumarta.com/software/cola/objmodel2.pdf ).

The Josephus problem for those unfamiliar with it is actually quite grim, it concerns a group of people in a circle under desperate circumstances who have decided to collectively commit suicide. They decide to do so by going around the circle and killing every third person until only one person is alive. Yikes! Josephus finds himself in this circle but has no desire to end his life, so he has to work out where to stand in the circle in order to survive.

One of the most interesting aspects of the chapter is that in the text, they follow a quite refreshing approach to introducing their results. Rather, than simply state the problem and the answer, they instead take us along on their problem solving process, first deciding on the problem to try and solve, making tables to look for patterns, trying out various hypothesis, and using induction to prove them once they have some degree of confidence in the result. In so doing we see several other approaches to the problem, some more amenable to programming the result into a computer others nicer for people to understand.

One thing we noticed about the text, was that after introducing the every 3rd person problem, they immediately switch to every 2nd person without any discussion of why and continue to work out the mathematics for that similar problem. We decided to follow their problem solving approach, but target the every 3rd person case right from the outset. We used a variety of methods to work things through; coloured pen and paper, Dann coded up a solver quickly, and we used these tools to explore some of the different variations on the problem introduced in the exercises. Hopefully, we will get some of this stuff up onto github to save for posterity.

Until next time, Scott

p.s. Dann has included some code he did to brute force things: https://raw.githubusercontent.com/CompSciCabal/SMRTYPRTY/master/experiments/dann/josephus.js

Hi, everyone!

Firstly, remember that this coming Friday, Jan 16, we’re meeting at Sud Forno instead of Bento Miso. Very important!

Secondly, we now have a mailing list! Sign up here: https://groups.google.com/forum/#!forum/cs-cabal

We’ve decided we’re going to themes for the next few months. February is memory management. Leo has been volunteered to curate a list of GC-related papers, taking us from the beginnings of the field to the state of the art in three easy pieces. On the fourth week we’ll all build our own garbage collectors!

Coincidentally, February’s theme ties in with the paper being read at our local Papers We Love meetup group, so be sure to check that out as well.

We’ll be discussing themes and papers for future months on the mailing list, so make your voice heard there! The “What’s Next?” wiki section has also been recently revamped, so feel free to add your ideas there as well.?

Happy New Year! Welcome back everyone!

Friday night marked our first Cabal meeting of 2015 as well as the first meeting without sicp, though it will remain forever with us in spirit. We had a great time discussing ideal hash tries, as well as some suitable divergence towards transhumanist philosophy, quantum computing, and Asimov (Thanks Colin!).

Dann moderated our discussion of Phil Bagwell’s excellent paper, Ideal Hash Tries (http://lampwww.epfl.ch/papers/idealhashtrees.pdf). This paper introduces using Array Mapped Tries (AMT) to implement a hash table interface as well as covers a variety of applications and extensions of the basic data structure.

We spent most of our time covering the basic principles by which AMTs operate, so maybe we should have started with the AMT paper. Confusingly for the non initiated the H in (Hash Array Mapped Trie) HAMT does not refer to the hashing that goes on in the AMT algorithm, but rather to the hash table interface that is implemented using the AMT. Although, this does mean we could easily come back to this paper and cover some other topics in the future. Dann also sketched out how this data structure could be used to implement persistent data structures which is an important application for HAMTs.

Clear low level implementation details are given in the paper for all aspects of the algorithm which we spent some time digesting into a more abstract representation we could understand. Over on github I’ve added a basic implementation of the Trie in python (https://github.com/CompSciCabal/SMRTYPRTY/blob/master/experiments/scott/Idealhashtrie/trie_v2.3.py). This implementation is not efficient, but does present the basic flow of the algorithm without implementing the efficient compressed array data structures used in each node. Implementing an AMT would require a bit more work replacing the python dicts with the bit maps and fixed size hash tables described in the paper.

Next week, we learn how to always get picked last for the baseball team, and be proud of it! Concrete Mathematics Chapter 1.3 ‘The Josephus Problem’ delves into the mathematical reasoning behind the Roman philosopher Josephus’ brush with death in a cave near Jerusalem.

Until next week!

Scott

We finished off the year with the awarding of the first official comp sci cabal pins (Thanks Leo!), recapping our favourite parts of sicp (impossible to choose so we took longer than usual), and enjoying ourselves with a few loved ones in attendance as well. Special mention should go to Andre’s favourite footnote, footnote 6 of chapter 4.1.1, wherein the authors consider the notion of truth in a meta circular evaluator.

This takes us to a break for the holidays, and we will reconvene the Cabal on Friday January 9th around 6:30pm at the usual location of Bento Miso. Dann is going to moderate a discussion of Phil Bagwell’s paper “Ideal Hash Trees”, http://lampwww.epfl.ch/papers/idealhashtrees.pdf .

This is a great opportunity for newcomers to join the group as in the new year we are starting out by covering a wider variety of shorter papers, excerpts, or chapters, rather than starting another epic like sicp right away.

Until next time, Happy Holidays Everyone! ?

Hi Everyone! We made it! Yesterday marked the end of our year long relationship with sicp, as we finished reading and discussing the final chapter. Though there may be no more pages to turn, I’m sure the ideas we’ve learned will continue to percolate for a long time to come.

Thanks Dann for taking the lead and taking on the moderation most of the time. And Andre thanks for being a champ and powering through all of the final chapter exercises, we spent a good chunk of the session reading over your code on github, too bad you couldn’t make it.

Next week is the final celebratory session of the year, so we ask those attending to: a) Bring some food as this is a celebration b) go through the book again and pick out your favourite parts from each chapter to discuss and review.

In the new year, the plan is to shift from the single book deep dive approach and spend some time doing shallower dips into selected chapters or articles. Look on the github for the current list of ideas, or come out and join us in the new year and tell us what you are interested I reading.

Until next Time, Scott