VM Learning: Call Stack Management (V2, C version)

Hi all,

In 2016, I published a first article [1], which lead to a booklet [2] to help people learning about Call Stack Management. In short, the book includes descriptions and exercises to implement interpreters with an increasing level of difficulty. It allows the reader to understand concepts such as calling conventions, access to variables relatively to the frame pointer and stack pointer, stack pages and closure implementation.

This year, I have the chance to be a post-doc at the VUB with Elisa Gonzalez Boix. Among lots of interesting work we do together, she is teaching to Bachelor 2 x86 calling conventions and call stack management. It seems the existing practical work covered different aspects of the lecture, but not really calling conventions. The practical works associated with this lecture have to be in C, hence I ported one of the interpreter of the booklet (the one with an infinite stack but no closures) to C. With Maarten Vandercammen, the three of us built an assignment out of the C interpreter and taught it in a 2 hours practical work to Bachelor 2 students. Most students were able to implement all the given instructions of the interpreter (called stack machine in the assignment) in 2 hours. A very small subset of them made it to the “Going Further” section. Overall, the assignment went really well.

You can download the contents of the assignment here [3].

I was not allowed to share publicly a solution for the students not to cheat (they will do it next year again), but if you know me personally or request it with proper motivation I may share it. There is nothing fancy about it though, you can just implement the solution yourself, Bachelor 2 students do it in only 2 hours. I think in total only 21 lines of C code has to be written or something like that.

Difference with the original booklet

The C version is easier to implement that the Smalltalk version. It is not easier because C is easier to deal with, it is easier because the assignment covers only a subset of the booklet, but covers the most essential content.

In Smalltalk the language implemented (SmiLang) is a Smalltalk embedded DSL, in C it is a C embedded DSL. To stick closer to the C language, I did not implement metadata around functions as in Smalltalk. Function * in C is a pointer to the first instruction of the function, not to a struct which includes the number of arguments of the function and so on. This means that some instructions (PushArg, ReturnTop) had to be modified to encode extra/different information. In addition, instruction pointer, stack pointer and frame pointer are direct pointers inside data structures, and not indexes relative to the beginning of data structures as in Smalltalk. Lastly, in Smalltalk, IDE extensions are provided through GTInspector to support the work of the students, while in C debugging functions which print in the command line are provided instead.

Let me know if you questions or suggestions!

[1] https://clementbera.wordpress.com/2016/04/10/vm-learning-call-stack-management/
[2] https://files.pharo.org/books-pdfs/booklet-CallStack/2018-01-23-CallStack.pdf
[3] https://www.dropbox.com/s/a9cw1xkfyxrtcq6/SmiLang.zip?dl=0

Advertisements