This is amazing! Looks like the symbol table is just a linked list that grows and shrinks with lexical scope? That’s a surprise, I was expecting something more involved like a hash map. Makes perfect sense though, from a kiss perspective.
I still vividly remember the day that Wirth decided to replace the elegant data structure used in the compiler’s symbol table handler by a mundane linear list. In the original compiler, the objects in the symbol table had been sorted in a tree data structure (in identifier lexical order) for fast access, with a separate linear list representing their declaration order. One day Wirth decided that there really weren’t enough objects in a typical scope to make the sorted tree cost-effective. All of us Ph.D. students were horrified: it had taken time to implement the sorted tree, the solution was elegant, and it worked well – so why would one want to throw it away and replace it by something simpler, and even worse, something as prosaic as a linear list? But of course, Wirth was right, and the simplified compiler was both smaller and faster than its predecessor.
This is amazing! Looks like the symbol table is just a linked list that grows and shrinks with lexical scope? That’s a surprise, I was expecting something more involved like a hash map. Makes perfect sense though, from a kiss perspective.
On this there’s a funny story in The School of Niklaus Wirth: The Art of Simplicity By László Böszörményi
I had no idea this book existed, thanks!