Monday, October 14, 2013

Programming Language Feature Diagrams

When I first started reading about different programming languages, I tried to understand the features that differentiated them as if they were atomic and absolute in nature.  So imagine perhaps magic spells from Dungeons and Dragons or maybe Go Directly To Jail from Monopoly.  If you go directly to jail, you're not asking how or what is the mechanism that propels you to jail.  You simply move your game piece to the jail location and there you remain.  

However at some point this was no longer sufficient for my curiosity.  I started to break apart the programming language features themselves, and began to ask myself how these individual features worked.

Ultimately, everything that is encoded in a program is converted into assembly instructions.  There are instructions for modifying memory locations, moving the values in memory locations, storing values in memory locations, retrieving values from memory locations, jumping from one place in the list of instructions to another, etc.  While it is important to have an idea about what the assembly code looks like, I think for most features you encounter you can imagine things at a slightly more abstract level.

You can sort of imagine functions themselves as boxes that contain assembly instructions.  When you get to a function call, you traverse to a new box.  Once that function call is done, you return to the box that you came from.   So you kind of get a tree structure showing up.

Executing this program would look kind of like a depth first traversal.

I'm not sure it's worth the time to go through every possible feature and try to show a diagram for it (not to mention some things like call/cc, lisp macros, and compile time type checking don't really fit very neatly into this view), but here are a couple of thought provoking examples.


When a function creates a new thread, you end up with an additional stack in your program.  Time tends to progress as you would expect it[1] in each thread, but because the operating system is managing when any given thread is running (not to mention the existence of multicore computers) you don't really know where any given point in one stack relates to a point in another stack.  Without the existence of global memory addresses or a shared pointer in memory[2], these two stacks can't communicate with each other.  Because of the ubiquitous nature of multicore computers and the importance of distributed computing, new languages are starting to put a lot of thought in providing not only synchronizing and locking primitives (which allow correct communication via shared state) but also primitives that completely abstract the entire thread creation and communication process altogether.

[1] - Actually, both the compiler and the CPU reorder operations.  So time doesn't quite progress as you would expect, but it should progress in a manner which is mathematically identical to the way that you expect it to.  Things get tricky when threads are thrown into the mix, so you get to enter the dark world of atomic operations and memory fences.

[2] - Or if you're absolutely crazy, I suppose you could try to guess the location of the other stacks in memory and start dereferencing pointers.  I imagine there's probably *someone* who makes good usage of this technique, but I doubt that it's something that would lead to code that is at all comprehensible.

Global State

This one is a lot more straight forward than the threads.  At any point in time a function can set or get a value from global memory.  This state can be accessed again by the function itself or by another function in the future.  This can lead to programs which are difficult to understand especially as the number of connections made between functions via global memory increases[1].  But properly managed (like by the compiler) or used sparingly, this technique can make a lot of programs much easier to write.

[1] - The complexity that can arise from mutable global state is actually one of the motivators behind the recent interest in pure functional programming languages.  In a system like Lambda Calculus, all functions work locally or they don't work at all.  I've found this to be a very powerful way to carefully analyze the problem at hand to determine exactly how it functions.  You gain a lot more freedom with how you are able to build your program when you have separated every aspect of the problem.


I'm not sure that there is much to say about this one.  A callback is relatively simple.  You take a function (which may call other functions) and pass it as a parameter to other functions.  These functions can call the callback and the effect is very much like inserting a new function diagram at the call point of the callback.

This can get more complicated when you combine callbacks, objects, and threads.  Diagraming out your program's structure in these cases can help you understand bizarre behavior that you might encounter.  Although, as I said concerning threads, languages are beginning to add features that help the programmer manage these situations.


I'm not really a fan of exceptions.  I do have to admit that they can make the structure of your types a lot cleaner in certain situations[1].  However, exceptions really are just dynamic upward stack communication channels; unfortunately most people do not seem to think of them that way.

When a function returns normally, you end up at the location of the function call in the calling function and continue normal code execution.  But when a function throws an exception, you end up at the location of the function call in the calling function and then look for and execute an exception handler (typically called catching an exception) before continuing normal code execution.  If no exception handler is located or if there does not exist the proper function handler, then the exception goes to that functions calling function.  This continues until either the exception is handled or the program runs out of calling functions.

For simple programs like the example above, it is easy to determine that all exceptions will be handled appropriately.  However, with more dynamic features like objects, interfaces, callbacks, threads, etc, it can be very difficult to determine if all exceptions are being correctly handled.  This can lead to the program crashing unexpectedly.

My theory is that if you think of an exception as a method of dynamically communicating with the functions above you (dynamic because you don't have to know which function called you in order to try to communicate with it), then you are more likely to have all possible calling functions properly equipped with exception handlers.  On the other hand, if you consider exceptions something that should be used in "exceptional" situations or something to be used when problems show up, then I suspect that you're more likely to forget to handle all of the error cases in the appropriate places.

[1] -  For example, division fails when you try to divide any number by zero.  Instead of giving division a weird type that indicates that some failure may occur (or proving that it is never passed a zero) maybe it's better to just let an exception be thrown.


Of course in most programs of any complexity, you're not going to only see any single feature used at a time.  You're likely to see many of them used at the same time.  This can lead to complicated programs, which are very difficult to understand and maintain.  Perhaps this illustration helps explains some buggy programs you've used in the past.

I mentioned that the complexity of global state (and more generally mutable state) is something that has caused interest in functional programming.  When you eliminate all of the features that I have outlined here, you gain the knowledge that the entire program can be drawn as a relatively simple tree like the one I showed at the very beginning of this blog post.  

Personally, I don't think I'm ever going to be the same now that I have learned about lambda calculus, type theory, and the different mathematical properties of functions (reflexive et al, associative et al, injective et al, etc).  These are some very powerful tools for understanding problems, and they have allowed me to drill a lot deeper than I ever would have been able to on my own. 

But, while they do allow you to create some very comprehensible programs, it also takes a lot of work to restructure the combined diagram above into a functionally equivalent simple tree structure.  So while it would be nice to always do everything in an incredibly disciplined manner, the constraints of real life do have to be considered as well.  And I'm not just talking about time and expertise.  Even if you had sufficient time and everyone was an expert with the more mathematical tools, the functional route still requires quite a bit of mental effort.  Some problems are just very difficult to simplify, and perhaps it is better to throw an exception and move on with your life.