Programming Concepts: Garbage Collection

Continuing on in this series, today we’re going to talk about garbage collection (GC) – what it is, how it works, and what some of the algorithms behind it are. Let me just say now that there are people way smarter than me who can give you nitty-gritty details about how specific languages implement GC, what libraries alter it from the norm, etc. What I’m trying to accomplish here is to give you a bird’s eye view of this whole facet of development in the hopes that you learn something you didn’t know before – and if it genuinely interests you, then I hope you continue Googling to find those posts which dig a mile deep into specific GC implementations. Here, we’ll stick to about a few feet deep – so let’s start digging.

What is Garbage Collection?

At its core, GC is a process of automated memory management so that you as a developer have one less thing to worry about. When you allocate memory – like by creating a variable – that memory is allocated to either the stack or the heap (check out my post on the stack vs. the heap if you want to learn more about these two). You allocate to the stack when you’re defining things in a local scope where you know exactly the memory block size you need, such as primitive data types, arrays of a set size, etc. The stack is a self-managing memory store that you don’t have to worry about – it’s super fast at allocating and clearing memory all by itself. For other memory allocations, such as objects, buffers, strings, or global variables, you allocate to the heap.

Compared to the stack, the heap is not self-managing. Memory allocated to the heap will sit there throughout the duration of the program and can change state at any point in time as you manually allocate/deallocate to it. The garbage collector is a tool that removes the burden of manually managing the heap. Most modern languages such as Java, the .NET framework, Python, Ruby, Go, etc. are all garbage collected languages; C and C++, however, are not – and in languages such as these, manual memory management by the developer is an extremely important concern.

Why Do We Need It?

GC helps save the developer from several memory-related issues – the foremost being memory leaks. As you allocate more and more memory to the heap, if the program doesn’t consistently release this memory as it becomes unneeded, memory size will begin to add up – resulting in a heap overflow. Even if heap memory is diligently managed by the developer – all it takes is one variable to be consistently left undeleted to result in a memory leak, which is bad.

Even if there are no memory leaks, what happens if you are attempting to reference a memory location which has already been deleted or reallocated? This is called a dangling pointer; the best case scenario here is that you would get back gibberish, and hopefully throw or cause a validation error soon after when that variable is used – but there’s nothing stopping that memory location from being overwritten with new data which could respond with seemingly valid (but logically incorrect) data. You’d have no idea what would be going on, and it’s these types of errors – memory errors – that are often times the most difficult to debug.

That’s why we need GC. It helps with all of this. It’s not perfect – it does use up extra resources on your machine to work and it’s normally not as efficient as proper manual memory management – but the problems it saves you from make it more than worth it.

How and When does the Garbage Collector Run?

This depends entirely on the algorithm used for GC. There isn’t one hard and fast way to do it, and just like compilers and interpreters, GC mechanisms get better over time. Sometimes the garbage collector will run at pre-determined time intervals, and sometimes it waits for certain conditions to arise before it will run. The garbage collector will just about always run on a separate thread in tandem with your program – and depending on the language’s implementation of GC, it can either stall your program (i.e. stop-the-world GC) to sweep out all the garbage at once, run incrementally to remove small batches, or run concurrently with your program.

It’s difficult to get deeper than this without getting into specific languages’ implementations of GC, so let’s move onto the common GC algorithms.

Garbage Collection Algorithms

There’s a bunch of different GC algorithms out there – but here are some of the most common ones you’ll come across. It’s interesting to note how many of these common algorithms build on one another.

Reference Counting

Reference counting is perhaps the most basic form of GC, and the easiest to implement on your own. The way it works is that anytime you reference a memory location on the heap, a counter for that particular memory location increments by 1. Every time a reference to that location is deleted, the counter decrements by 1. When that counter gets to 0, then that particular memory location is garbage collected.

One of the big benefits of GC by reference counting is that it can immediately tell if there is garbage (when a counter hits 0). However, there are some major problems with reference counting; circular references just flat out can’t be garbage collected – meaning that if object A has a reference to object B, and object B has a reference back to object A, then neither of these objects can ever be garbage collected according to reference counting. On top of this, reference counting is very inefficient because of the constant writes to the counters for each memory location.

Because of these problems, other algorithms (or at least refined versions of reference counting) are more commonly used in modern GC.

Mark-Sweep

Mark-sweep – as well as just about all modern GC algorithms other than reference counting – is a form of a tracing GC algorithm, which involves tracing which objects are reachable from one or multiple “roots” in order to find unreachable (and thus unused) memory locations. Unlike reference counting, this form of GC is not constantly checking and it can theoretically run at any point in time.

The most basic form of mark-sweep is the naïve mark-sweep; it works by using a special bit on each allocated memory block that’s specifically for GC, and running through all memory currently allocated on the heap twice: the first time to mark locations of dead memory via that special bit, and the second time to sweep (i.e. deallocate) those memory locations.

Mark-sweep is more efficient than reference counting because it doesn’t need to keep track of counters; it also solves the issue of not being able to remove circularly referenced memory locations. However, naïve mark-sweep is a prime example of stop-the-world GC because the entire program must be suspended while it’s running (non-naïve tracing algorithms can run incrementally or concurrently). Because tracing GC can happen at any point in time, you don’t ever have a good idea of when one of these stalls will happen. Heap memory is also iterated over twice – which slows down your program even more. On top of that, in mark-sweep there’s no handling of fragmented memory; to give you a visual representation of this, imagine drawing a full grid representing all of your heap memory – mark-sweep GC would make that grid look like a very bad game of Tetris. This fragmentation almost always leads to less efficient allocation of memory on the heap. So – we continue to optimize our algorithms.

Mark-Compact

Mark-compact algorithms take the logic from mark-sweep and add on at least one more iteration over the marked memory region in an effort to compact them – thus defragmenting them. This address the fragmentation caused by mark-sweep, which leads to significantly more efficient future allocations via the use of a “bump” allocator (similar to how a stack works), but adds on extra time and processing while GC is running because of the extra iteration(s).

Copying

Copying (also known as Cheney’s Algorithm) is slightly similar to mark-compact, but instead of iterating potentially multiple times over a single memory region, you instead just copy the “surviving” memory blocks of the region into an entirely new empty region after the mark phase – which thus compacts them by default. After the copying is completed, the old memory region is deallocated, and all existing references to surviving memory will point to the new memory region. This relieves the GC of a lot of processing, and brings down the specs to something even quicker than a mark-sweep process since the sweep phase is eliminated.

While you’ve increased speed though, you now have an extra requirement of needing an entirely available region of memory that is at least as large as the size of all surviving memory blocks. Additionally, if most of your initial memory region includes surviving memory, then you’ll be copying a lot of data – which is inefficient. This is where GC tuning becomes important.

Generational

Generational GC takes concepts from copying algorithms, but instead of copying all surviving members to a new memory region, it instead splits up memory into generational regions based on how old the memory is. The rationale behind generational GC is that normally, young memory is garbage collected much more frequently than older memory – so therefore the younger memory region is scanned to check for unreferenced memory much more frequently than older memory regions. If done properly, this saves both time and CPU processing because the goal is to scan only the necessary memory.

Older memory regions are certainly still scanned – but not as often as younger memory regions. If a block of memory in a younger memory region continues to survive, then it can be promoted to an older memory region and will be scanned less often.

Final Thoughts

GC isn’t the easiest topic to fully understand, and it’s something that you really don’t even need to understand when developing with modern languages – but just because you don’t need to know it doesn’t give you a good excuse for not learning about it. While it doesn’t affect much of the code you write, it’s an integral part of every language implementation, and the algorithm behind an implementation’s garbage collector is often times a large reason why people tend to like or dislike certain implementations. If you stuck with me this far, then I’m glad – and I hope you learned something. If this interested you, I encourage you to continue looking into GC – and here’s a fun resource you can start off with that shows you some animated GIFs of how different GC algorithms visually work.

Interestingly, while researching this topic, the vast majority of posts I came across talk about how GC works specifically to the main implementation of Java. GC certainly isn’t exclusive to Java, but I imagine the reason for this is because Java is often times heavily compared to C++ which isn’t garbage collected. Hopefully over time, more posts will become popular over how GC works in other languages – but for now, we’ll take what we can get!

Core Functional Programming Concepts

If you’re a developer like me, then you probably grew up learning about Object-Oriented Programming and how that whole paradigm works. You may have messed with Java or C++ – or been lucky enough to use neat languages like Ruby, Python, or C# as your first true language – so chances are that you’re at least mildly comfortable with terms such as classes, objects, instance variables, static methods, etc. What you’re probably not as comfortable with are the core concepts behind this weird paradigm called functional programming – which is pretty drastically different from not only just object-oriented programming, but also procedural, prototypal, and a slough of other common paradigms out there.

Functional programming is becoming a pretty hot topic – and for very good reason. This paradigm is hardly new too; Haskell is potentially the most corely-functional language out there and has existed since 1990. Other languages such as Erlang, Scala, Clojure also fall into the functional category – and they all have a solid following. One of the major benefits of functional programming is the ability to write programs that run concurrently and that do it properly (check out my post on concurrency if you need a refresher on what that means) – meaning that common concerns such as deadlock, starvation, and thread-safety really aren’t an issue. Concurrency in procedural-based languages is a nightmare because state can change at any given moment. Objects have state that can change, practically any function can change any variable as long as they’re in lexical scope (or dynamic scope, for the few languages that use it) – it’s very powerful, but very bad at keeping tabs on state.

Functional programming touts many benefits – but the ability to take advantage of all of a CPU’s cores via concurrent behavior is what makes it really shine compared to the other popular programming languages today – so I want to go over some of the core concepts that power this language paradigm.


Foreword: All of these concepts are language-agnostic (in fact, many functional languages don’t even fully abide by them), but if you had to associate them with any one language, it would most likely fit best with Haskell, since Haskell most strictly abides by core functional concepts. The following 5 concepts are strictly theory-driven and help define the functional paradigm in the purest sense.

1. Functions are Pure

This is easily the foremost rule of functional programming. All functions are pure in the sense that they abide by two restrictions:

  1. A function called multiple times with the same arguments will always return the same value. Always.
  2. No side effects occur throughout the function’s execution.

The first rule is relatively simple to understand – if I call the function sum(2, 3) – then it should always return the same value every time. Areas where this breaks down in more procedural-coding is when you rely on state that the function doesn’t control, such as global variables or any sort of randomized activity. As soon as you throw in a rand() function call, or access a variable not defined in the function – then the function loses its purity, and that can’t happen in functional programming.

The second rule – no side effects – is a little bit more broad in nature. A side effect is basically a state change in something other than the function that’s currently executing. Modifying a variable defined outside the function, printing out to the console, raising an exception, and reading data from a file are all examples of side effects which prevent a function from being pure. At first, this might seem like a big constraint for functional programming – but think about it. If you know for sure that a function won’t modify any sort of state outside the function itself, then you have full confidence that you can call this function in any scenario. This opens so many doors for concurrent programming and multi-threaded applications.

2. Functions are First-Class and can be Higher-Order

This concept isn’t exclusive to functional programming (it’s used pretty heavily in Javascript, PHP, and among other languages too) – but it is a requirement of being functional. In fact – there’s a whole Wikipedia article over the concept of first-class functions. For a function to be first-class, you just have to be able to set it to a variable. That’s it. This allows you to handle the function as if it were a normal data type (such as an integer or string), and still be able to execute the function at some other point in runtime.

Higher-order functions build off of this concept of “functions as first-class citizens” and are defined as functions that either accept another function as an argument, or that return a function themselves. Common examples of higher-order functions are map functions which typically iterate over a list, modify the data based on a passed-in function, and return a new list, and filter functions, which accept a function specifying how elements of a list should be selected, and return a new list with the selections.

3. Variables are Immutable

This one’s pretty simple. In functional programming, you can’t modify a variable after it’s been initialized. You just can’t. You can create new variables just fine – but you can’t modify existing variables, and this really helps to maintain state throughout the runtime of a program. Once you create a variable and set its value, you can have full confidence knowing that the value of that variable will never change.

4. Functions have Referential Transparency

Referential transparency is a tricky definition to pinpoint, and if you ask 5 different developers, then you’re bound to get 5 different responses. The most accurate definition for referential transparency that I have come across (and that I agree with) is that if you can replace the value of a function call with its return value everywhere that it’s called and the state of the program stays the same, then the function is referentially transparent. This might seem obvious – but let me give you an example.

Let’s say we have a function in Java that just adds 3 and 5 together:

It’s pretty obvious that anywhere I call the addNumbers() function, I can easily replace that whole function call with the return value of 8 – so this function is referentially transparent. Here’s an example of one that’s not:

This is a void function, so it doesn’t return anything when called – so for the function to be referentially transparent, we should be able to replace the function call with nothing as well – but that obviously doesn’t work. The function changes the state of the console by printing out to it – so it’s not referentially transparent.

This is a tricky topic to get, but once you do, it’s a pretty powerful way to understand how functions really work.

5. Functional Programming is Based on Lambda Calculus

Functional programming is heavily rooted in a mathematical system called lambda calculus. I’m not a mathematician, and I certainly don’t pretend to be, so I won’t go into the nitty-gritty details about this field of math – but I do want to review the two core concepts of lambda calculus that really shaped the structure of how functional programming works:

  1. In lambda calculus, all functions can be written anonymously without a name – because the only portion of a function header that affects its execution is the list of arguments. In case you ever wondered, this is where lambda (or anonymous) functions get their name in modern-day programming – because of lambda calculus. *Brain explosion*.
  2. When invoked, all functions will go through a process called currying. What this means is that when a function with multiple arguments is called, it will execute the function once but it will only set one variable in the parameter list. At the end, a new function is returned with 1 less argument – the one that was just applied – and this new function is immediately invoked. This happens recursively until the function has been fully applied, and then a final result is returned. Because functions are pure in functional programming – this works. Otherwise, if state changes were a concern, currying could produce unsafe results.

As I mentioned earlier, there’s much more to lambda calculus than just this – but I wanted to review where some of the core concepts in functional programming came from. At the very least, you can bring up the phrase lambda calculus when talking about functional programming, and everyone else will think you’re really smart.

Final Thoughts

Functional programming involves a significantly different train of thought than what you’re probably used to – but it’s really powerful, and I personally think this topic is going to come up again and again with CPUs these days offering more cores to handle processes instead of just using one or two beefed up cores per unit. While I mentioned Haskell as being one of the more pure functional languages out there – there are a handful of other popular languages too that are classified as functional: Erlang, Clojure, Scala, and Elixir are just a few of them, and I highly encourage you to check one (or more) of them out. Thanks for sticking with me this long, and I hope you learned something!

Programming Concepts: Type Introspection and Reflection

Often times during the runtime of a program, we need to ask questions about some of our data – things like what type it is or if it’s an instance of a certain class (in object-oriented programming). On top of that, sometimes we need to perform logic based on the object in question, such as call an instance method or a class method, or even modify some data internal to the object – and we may not have the necessary object variable or constant to do that. If this doesn’t make sense, hold on tight – that’s what we’re going to get into here today (with a lot of code examples!). Everything I just discussed here illustrates the purpose of two features found in just about every modern programming language we use these days: type introspection and reflection.

Type Introspection

Type introspection is the ability of a program to examine the type or properties of an object at runtime. Just as we mentioned in the intro, the types of questions you might want to ask are what type is this object, or is it an instance of a certain class. Some languages even allow you to traverse the inheritance hierarchy to see if your object is derived from an inherited base class. Several languages have the type introspection capability, such as Ruby, Java, PHP, Python, C++, and more. Overall, type introspection is a very simple concept to understand – and you can really write powerful logic when you can query some of the metadata about your objects. Below are some examples of type introspection in the wild:

In Python, the most common form of type introspection is using the dir method to list out the attributes of an object:

Lastly, in Ruby, type introspection is very useful – largely because of how ruby is built as a language. Just about everything is an object – even a class – and that leads to some really cool inheritance hierarchies and reflective capabilities (discussed more below). If you want to see some of the raw power of ruby, such as taking type introspection and reflection to the max, then check out my mini series on Metaprogramming in Ruby.

For now, here’s a few simple examples of type introspection in ruby using IRB (the interactive ruby shell):

You can also ask an object which class it is, and then even “compare” classes if you so desire (among many other things).

Type introspection is not reflection, however; reflection takes these core principles of type introspection and allows us to do some really cool, powerful, and sometimes scary things with our code.

Reflection

If type introspection allows you to inspect an object’s attributes at runtime, then reflection is what allows you to manipulate those attributes at runtime. As a concrete definition, reflection is the ability of a computer program to examine and modify the structure and behavior (specifically the values, meta-data, properties and functions) of a program at runtime. In layman’s terms, what this allows you to do is invoke a method on an object, instantiate a new object, or modify an attribute of an object – all without knowing the names of the interfaces, fields, methods at compile time. Because of the runtime-specific nature of reflection, it’s more difficult to implement reflection in a statically-typed language compared to a dynamically-typed language because type checking occurs at compile time in a statically-typed language instead of at runtime (you can read more about that in my post). However it is by no means impossible, as Java, C#, and other modern statically-typed languages allow for both type introspection and reflection (but not C++, which allows only type introspection and not reflection).

Just as reflection is easier to implement in dynamically-typed languages as compared to statically-typed languages, it’s also easier to implement in interpreted language implementations compared to compiled language implementations. This is because as functions, objects, and other data structures are created and invoked at runtime, some sort of runtime system must exist to allocate memory properly. In an interpreted language implementation, this is simple because the interpreter by default usually provides the runtime system, but compiled language implementations must provide an additional compiler and interpreter that watches program execution throughout its runtime to allow reflection to occur (this can often be done through program transformation as well).

I feel like we’ve stated a lot of technical definition about reflection, and it may or may not make much sense. Take a look at some more code examples below (both with reflection, and without), all of which involve instantiating an object of class Foo and invoking the hello instance method of that object.

All of these examples show reflection being used, and it is by no means an extensive list of languages with reflective capabilities. Reflection is a very powerful concept which allows you to write some very powerful code, and it is considered a metaprogramming practice. Beware though, reflection can easily lead you down a rabbit hole of poor coding practices if you let it. While it has obvious benefits, code that uses reflection is much more difficult to read than non-reflective code, it may make documentation-searching and debugging more difficult, and it opens the doors for really bad things such as code-injection via eval statements.

Eval Statements

Some reflective programming languages ship with the ability to write eval statements – statements that evaluate a value – usually a string – as though it were an expression and returns a result. Eval statements are often the most powerful concept of reflection – and even metaprogramming – that languages have, but they are also the most dangerous, as they pose massive security risks. While very powerful, you can just about always accomplish your goal without having to resort to an eval statement.

Take the following Python code for example, which accepts data from some third-party source such as the Internet (this is usually one of the only reasons why people consider using an eval statement):

If someone provides the following string to the get_data() method, then the program’s security has been compromised:

In order to safely use an eval statement, you usually need to heavily limit the scope that the eval statement can execute in – which usually makes it more of a hassle than it’s worth to even use it at all then.

Conclusion

Type introspection and reflection are very powerful concepts seen in modern programming languages, and understanding how to take advantage of them will allow you to write some really cool code. Just to review their difference one more time, type introspection is just inspecting an object’s attributes, and reflection is the actual manipulating or invoking of an object’s attributes or functions. They go hand in hand, but make sure you are aware of how you use reflection, as your code can get pretty unreadable (and potentially insecure) if you abuse it. With great power comes great responsibility – that’s the motto for everything metaprogramming-related. Now go forth young padawan, and reflect!

Programming Concepts: Static vs. Dynamic Type Checking

When learning about programming languages, you’ve probably heard phrases like statically-typed or dynamically-typed when referring to a specific language. These terms describe the action of type checking, and both static type checking and dynamic type checking refer to two different type systems. A type system is a collection of rules that assign a property called type to various constructs in a computer program, such as variables, expressions, functions or modules, with the end goal of reducing the number of bugs by verifying that data is represented properly throughout a program.

Don’t worry, I know that all sounds confusing, so before we get further let’s start at the beginning. What is type checking, and while we’re at it, what’s a type?

A Type

A type, also known as a data type, is a classification identifying one of various types of data. I hate to use the word type in its own definition, so in a nutshell a type describes the possible values of a structure (such as a variable), the semantic meaning of that structure, and how the values of that structure can be stored in memory. If this sounds confusing, just think about Integers, Strings, Floats, and Booleans – those are all types. Types can be broken down into categories:

  • Primitive types – these range based on language, but some common primitive types are integers, booleans, floats, and characters.
  • Composite types – these are composed of more than one primitive type, e.g. an array or record (not a hash, however). All composite types are considered data structures.
  • Abstract types – types that do not have a specific implementation (and thus can be represented via multiple types), such as a hash, set, queue, and stack.
  • Other types – such as pointers (a type which holds as its value a reference to a different memory location) and functions.

Certain languages offer built-in support for different primitive types or data structures than other languages, but the concepts are the same. A type merely defines a set of rules and protocols behind how a piece of data is supposed to behave.

Type Checking

The existence of types is useless without a process of verifying that those types make logical sense in the program so that the program can be executed successfully. This is where type checking comes in. Type checking is the process of verifying and enforcing the constraints of types, and it can occur either at compile time (i.e. statically) or at runtime (i.e. dynamically). Type checking is all about ensuring that the program is type-safe, meaning that the possibility of type errors is kept to a minimum. A type error is an erroneous program behavior in which an operation occurs (or trys to occur) on a particular data type that it’s not meant to occur on. This could be a situation where an operation is performed on an integer with the intent that it is a float, or even something such as adding a string and an integer together:

While in many languages both strings and integers can make use of the + operator, this would often result in a type error because this expression is usually not meant to handle multiple data types.

When a program is considered not type-safe, there is no single standard course of action that happens upon reaching a type error. Many programming languages throw type errors which halt the runtime or compilation of the program, while other languages have built-in safety features to handle a type error and continue running (allowing developers to exhibit poor type safety). Regardless of the aftermath, the process of type checking is a necessity.


Now that we have a basic understanding of what types are and how type checking works, we can start getting into the two primary methods of type checking: static type checking and dynamic type checking.

Static Type Checking

A language is statically-typed if the type of a variable is known at compile time instead of at runtime. Common examples of statically-typed languages include Ada, C, C++, C#, JADE, Java, Fortran, Haskell, ML, Pascal, and Scala.

The big benefit of static type checking is that it allows many type errors to be caught early in the development cycle. Static typing usually results in compiled code that executes more quickly because when the compiler knows the exact data types that are in use, it can produce optimized machine code (i.e. faster and/or using less memory). Static type checkers evaluate only the type information that can be determined at compile time, but are able to verify that the checked conditions hold for all possible executions of the program, which eliminates the need to repeat type checks every time the program is executed.

A static type-checker will quickly detect type errors in rarely used code paths. Without static type checking, even code coverage tests with 100% coverage may be unable to find such type errors. However, a detriment to this is that static type-checkers make it nearly impossible to manually raise a type error in your code because even if that code block hardly gets called – the type-checker would almost always find a situation to raise that type error and thus would prevent you from executing your program (because a type error was raised).

Dynamic Type Checking

Dynamic type checking is the process of verifying the type safety of a program at runtime. Common dynamically-typed languages include Groovy, JavaScript, Lisp, Lua, Objective-C, PHP, Prolog, Python, Ruby, Smalltalk and Tcl.

Most type-safe languages include some form of dynamic type checking, even if they also have a static type checker. The reason for this is that many useful features or properties are difficult or impossible to verify statically. For example, suppose that a program defines two types, A and B, where B is a subtype of A. If the program tries to convert a value of type A to type B, which is known as downcasting, then the operation is legal only if the value being converted is actually a value of type B. Therefore, a dynamic check is needed to verify that the operation is safe. Other language features that dynamic-typing enable include dynamic dispatch, late binding, and reflection.

In contrast to static type checking, dynamic type checking may cause a program to fail at runtime due to type errors. In some programming languages, it is possible to anticipate and recover from these failures – either by error handling or poor type safety. In others, type checking errors are considered fatal. Because type errors are more difficult to determine in dynamic type checking, it is a common practice to supplement development in these languages with unit testing.

All in all, dynamic type checking typically results in less optimized code than does static type checking; it also includes the possibility of runtime type errors and forces runtime checks to occur for every execution of the program (instead of just at compile-time). However, it opens up the doors for more powerful language features and makes certain other development practices significantly easier. For example, metaprogramming – especially when using eval functions – is not impossible in statically-typed languages, but it is much, much easier to work with in dynamically-typed languages.

Common Misconceptions

Myth #1: Static/Dynamic Type Checking == Strong/Weak Type Systems

A common misconception is to assume that all statically-typed languages are also strongly-typed languages, and that dynamically-typed languages are also weakly-typed languages. This isn’t true, and here’s why:

A strongly-typed language is one in which variables are bound to specific data types, and will result in type errors if types to not match up as expected in the expression – regardless of when type checking occurs. A simple way to think of strongly-typed languages is to consider them to have high degrees of type safety. To give an example, in the following code block repeated from above, a strongly-typed language would result in an explicit type error which ends the program’s execution, thus forcing the developer to fix the bug:

We often associate statically-typed languages such as Java and C# as strongly-typed (which they are) because data types are explicitly defined when initializing a variable – such as the following example in Java:

However, ruby, python, and javascript (all of which are dynamically-typed) are also strongly-typed languages and the developer makes no verbose statement of data type when declaring a variable. Below is the same java example above, but written in ruby.

Both of the languages in these examples are strongly-typed, but employ different type checking methods. Languages such as ruby, python, and javascript which do not require manually defining a type when declaring a variable make use of type inference – the ability to programmatically infer the type of a variable based on its value. Some programmers automatically use the term weakly typed to refer to languages that make use of type inference, often without realizing that the type information is present but implicit. Type inference is a separate feature of a language that is unrelated to any of its type systems.

weakly-typed language on the other hand is a language in which variables are not bound to a specific data type; they still have a type, but type safety constraints are lower compared to strongly-typed languages. Take the following PHP code for example:

Because PHP is weakly-typed, this would not error. Just as the assumption that all strongly-typed languages are statically-typed, not all weakly-typed languages are dynamically-typed; PHP is a dynamically-typed language, but C – also a weakly-typed language – is indeed statically-typed.

Myth officially busted.

While they are two separate topics, static/dynamic type systems and strong/weak type systems are related on the issue of type safety. One way you can compare them is that a language’s static/dynamic type system tells when type safety is enforced, and its strong/weak type system tells how type safety is enforced.

Myth #2: Static/Dynamic Type Checking == Compiled/Interpreted Languages

It is true that most statically-typed languages are usually compiled when executed, and most dynamically-typed languages are interpreted when executed – but you can’t always assume that, and there’s a simple reason for this:

When we say that a language is statically- or dynamically-typed, we are referring to that language as a whole. For example, no matter what version of Java you use – it will always be statically-typed. This is different from whether a language is compiled or interpreted, because in that statement we are referring to a specific language implementation. Thus in theory, any language can be compiled or interpreted. The most common implementation of Java is to compile to bytecode, and have the JVM interpret that bytecode – but there are other implementations of Java that compile directly to machine code or that just interpret Java code as is.

If this still is unclear, hop on over to my previous post on Compiled vs. Interpreted Languages, where we dig into this topic at length.

Conclusion

I know we went over a lot – but you’re a good developer, so I knew you could handle it. I debated on breaking strongly-typed and weakly-typed languages out from this post, but that topic alone isn’t large enough to warrant its own post – plus I needed to break up the myths that a strong/weak type system is related to type checking.

There’s no answer to if statically-typed languages are better than dynamically-typed languages, and vice versa – they’re just different type systems with their own sets of pros and cons. Some languages  – like Perl and C# – even allow you to choose between static and dynamic type safety throughout your code. Understanding the type systems of your favorite programming languages will allow you to better understand why some errors may or may not pop up in the places that they do, and why.

I hope you learned a little bit today – I promise reviewing core programming concepts like these will help make you a better developer because you’re getting more of a grip on what’s going on behind the scenes of your code. Thanks for reading, and stick around for more posts in this Programming Concepts series!

Programming Concepts: Concurrency

For the third post in this Programming Concepts series, we’ll be discussing concurrency. Concurrency is a property of systems (program, network, computer, etc.) in which several computations are executing simultaneously, and potentially interacting with each other. The computations start, run, and complete in overlapping time periods; they can run at the exact same instant (e.g. parallelism), but are not required to.

Concurrency in Programming

Concurrency is implemented in programming logic by explicitly giving computations or processes within a system their own separate execution point or thread of control. This allows these computations to avoid waiting for all other computations to complete – as is the case in sequential programming.

Concurrent Computing vs. Parallel Computing

Although concurrent computing is considered a parent category that encompasses parallel programming, they share some distinct differences.

In parallel computing, execution occurs at the exact same instant typically with the goal of optimizing modular computations. This forces parallel computing to utilize more than one processing core because each thread of control is running simultaneously and takes up the core’s entire clock cycle for the duration of execution – and thus parallel computing is impossible on a single-core machine. This differs from concurrent computing which focuses on the lifetime of the computations overlapping and not necessarily their moments of execution. For example, the execution steps of a process can be broken up into time slices, and if the entire process doesn’t finish during its time slice then it can be paused while another process begins.

Why use Concurrent Programming?

The ultimate benefit of concurrent programming is to utilize the resources of the executing machine to the fullest extent. This typically results in a speed boost in execution time because the program is no longer subject to normal sequential behavior. Starting in the early 2000’s, a common trend in personal computers has been to use multi-core processing units instead of a single omni-powerful CPU core. This helps to optimize the total execution time of a process with multiple threads by spreading the load across all cores. How processes and threads get scheduled is best left to its own discussion and getting down to that level of task scheduling is OS-specific, so I won’t dig deeper into how processes and threads are scheduled – but feel free to read up on some of the synchronization patterns employed.

The concept of concurrency is employed in modern programming languages typically through a process called multithreading. Multithreading allows a program to run on multiple threads while still under the same parent process, thus providing the benefits of parallelization (faster execution, more efficient use of the computer’s resources, etc.) but also carrying with it the problems of parallelization too (discussed more below), which is why some languages make use of a mechanism called the Global Interpreter Lock (GIL). The GIL is found most commonly in the standard implementations of Python and Ruby (CPython and Ruby MRI, respectively), and prevents more than one thread from executing at a time – even on multi-core processors. This might seem like a massive design flaw, but the GIL exists to prevent any thread-unsafe activities – meaning that all code executing on a thread does not manipulate any shared data structures in a manner that risks the safe execution of the other threads. Typically language implementations with a GIL increase the speed of single-threaded programs and make integrations with C libraries easier (because they are often not thread-safe), but all at the price of losing multithreading capabilities.

However, if concurrency through a language implementation with a GIL is a strong concern, there are usually ways around this hindrance. While multithreading is not an option, applications interpreted through a GIL can still be designed to run on different processes entirely – each one with their own GIL.

Problems with Concurrent Programming

It has been said that the first rule of concurrent programming is it’s hard. Because the idea behind concurrency is to execute computations simultaneously, the potential exists for these separate tasks to access and unintentionally distort shared resources among them (e.g. thread-unsafe behavior). When shared resources are accessed, a programmatic arbiter is typically involved which handles the allocation of those resources – but this type of activity can ultimately create indeterminacy and lead to issues such as deadlock (where multiple computations are waiting on each other to finish, and thus never do), and starvation (where resources are constantly denied to a certain task).

This makes coordination when executing concurrent tasks extremely important because even areas where the developer has little control – such as memory allocation on the stack or the heap – can become indeterminate.

The Future of Concurrent Programming

Concurrent programming is incredibly powerful even given its obvious flaws, and thus it has been a very active field in theoretical computer science research. In programming, several languages have provided phenomenal support to give developers the tools to take advantage of concurrent behavior; this is perhaps most evident in the API behind Go, one of the newest popular languages created by developers at Google. Other languages, such as Python and Ruby, see the negative power of concurrency and thus default to using a GIL.

Countless models have been built to better understand concurrency and describe various theories, such as the Actor Model, CSP Model, and Disruptor Model. However, just as with most programming concepts, there is no silver bullet for concurrent programming. If you build an application that employs concurrency, be sure to plan it carefully and know what’s going on at all times – or else you risk the cleanliness of your data.

Programming Concepts: Compiled and Interpreted Languages

As with my previous Programming Concepts post over the Stack vs. the Heap, in this series I’m aiming to look back at core computing topics that affect everything about how we develop today, but are topics that most developers using higher level languages don’t ever need to deal with and thus may not fully understand them (myself included). In the same way that learning another programming language will make you a better developer, understanding the core of how different programming languages work will teach you a lot. Today’s topic: Compiled Languages and Interpreted Languages.

As developers, we often come across terms such as the compiler or the interpreter as we read blog posts, articles, StackOverflow answers, etc., but I feel like these are terms that we gloss over these days without really understanding them. Compilation and Interpretation are at the core of how all programming languages are executed; let’s take a look at how these concepts really work.

Introduction

We depend on tools such as compilation and interpretation in order to get our written code into a form that the computer can execute. Code can either be executed natively through the operating system after it is converted to machine code (via compilation) or can be evaluated line by line through another program which handles executing the code instead of the operating system itself (via interpretation).

A compiled language is one where the program, once compiled, is expressed in the instructions of the target machine; this machine code is undecipherable by humans. An interpreted language is one where the instructions are not directly executed by the target machine, but instead read and executed by some other program (which normally is written in the language of the native machine). Both compilation and interpretation offer benefits and pitfalls, which is mainly what we’re going to talk about.

Before we get further, it needs to be said that most programming languages have both compiled implementations and interpretated implementations, and thus you can’t really classify an entire language as being compiled or interpreted – only a specific implementation. For the sake of simplicity however, I’ll be referring to either “compiled languages” or “interpreted languages” for the remainder of the post.

Compiled Languages

The major advantage of compiled languages over interpreted languages is their execution speed. Because compiled languages are converted directly into machine code, they run significantly faster and more efficiently than interpreted languages, especially considering the complexity of statements in some of the more modern scripting languages which are interpreted.

Lower-level languages tend to be compiled because efficiency is usually more of a concern than cross-platform support. Additionally, because compiled languages are converted directly into machine code, this gives the developer much more control over hardware aspects such as memory management and CPU usage. Examples of pure compiled languages include C, C++, Erlang, Haskell, and more modern languages such as Rust and Go.

Some of the pitfalls of compiled languages are pretty substantial however. In order to run a program written in a compiled language, you need to first manually compile it. Not only is this an extra step in order to run a program, but while you debug the program, you would need to recompile the program each time you want to test your new changes. That can make debugging very tedious. Another detriment of compiled languages is that they are not platform-independent, as the compiled machine code is specific to the machine that is executing it.

Interpreted Languages

In contrast to compiled languages, interpreted languages do not require machine code in order to execute the program; instead, interpreters will run through a program line by line and execute each command. In the early days of interpretation, this posed a disadvantage compared to compiled languages because it took significantly more time to execute the program, but with the advent of new technologies such as just-in-time compilation, this gap is narrowing. Examples of some common interpreted languages include PHP, Perl, Ruby, and Python. Some of the programming concepts that interpreted languages make easier are:

The main disadvantage of interpreted languages is a slower program execution speed compared to compiled languages. However, as mentioned earlier, just-in-time compilation helps by converting frequently executed sequences of interpreted instruction into host machine code.


Bonus: Bytecode Languages

Bytecode languages are a type of programming language that fall under the categories of both compiled and interpreted languages because they employ both compilation and interpretation to execute code. Java and the .Net framework are easily the most common examples of bytecode languages (dubbed Common Intermediate Language in .Net). In fact, the Java Virtual Machine (JVM) is such a common virtual machine to interpret bytecode that several languages have implementations built to run on the JVM.

In a bytecode language, the first step is to compile the current program from its human-readable language into bytecode. Bytecode is a form of instruction set that is designed to be efficiently executed by an interpreter and is composed of compact numeric codes, constants, and memory references. From this point, the bytecode is passed to a virtual machine which acts as the interpreter, which then proceeds to interpret the code as a standard interpreter would.

In bytecode languages, there is a delay when the program is first run in order to compile the code into bytecode, but the execution speed is increased considerably compared to standard interpreted languages because the bytecode is optimized for the interpreter. The largest benefit of bytecode languages is platform independence which is typically only available to interpreted languages, but the programs have a much faster execution speed than interpreted languages. Similar to how interpreted languages make use of just-in-time compilation, the virtual machines that interpret bytecode can also make use of this technique to enhance execution speed.


Overview

Most languages today can either be compiled or interpreted through their various implementations, making the difference between the two less relevant. One language execution style isn’t better than the other, but they certainly have their strengths and weaknesses.

In a nutshell, compiled languages are the most efficient type of programming language because they execute directly as machine code and can easily utilize more of the hardware specs of the running machine. In turn, this forces a significantly stricter coding style and a single program usually can’t be run on different operating systems. Interpreted languages on the other hand offer much more diversity in coding style, are platform-independent, and easily allow for dynamic development techniques such as metaprogramming. However, interpreted languages execute much slower than compiled languages – though just-in-time compilation has been helping to speed this up.

Bytecode languages are common as well, and try to utilize the strong points in both compiled and interpreted languages. This allows for programming languages that are platform independent like interpreted languages, while still executing at a speed significantly faster than interpreted languages.

I know there were no code examples here – but I really wanted to dig into this topic because I feel that this is one of those programming concepts that will always be relevant to us, no matter how abstract our higher-level languages get from the hardware level. Feel free to leave a comment if you want to see any specific Programming Concepts posts in the future!

Programming Concepts: The Stack and the Heap

As we continue to use more advanced programming languages, we’re able to get some seriously powerful development done with much less code that does increasingly more awesome stuff, but that comes at a price. Since we don’t deal as often with low-level computation and processing anymore, it’s only normal that we don’t always have a full understanding about topics like what the stack is versus the heap, or how compilation really works, or what static vs dynamic typing is, or type introspection, or garbage collection, etc. Now I’m not saying every developer is ignorant of these, as most of us certainly aren’t, but I do feel like it’s worth revisiting some of the old-school important topics that we may miss out on these days.

I know I’ve opened up a wormhole of topics just now, but right now I’m only focusing on one: the stack vs. the heap. Both the stack and the heap refer to different locations where memory (typically for variables) is managed, but with significantly different strategies.

The Stack

The stack is a region of RAM that gets created on every thread that your application is running on. It works in a LIFO (Last In, First Out) manner, meaning that as soon as you allocate – or “push” – memory on to the stack, that chunk of memory will be the first to be deallocated – or “popped.” Every time a function declares a new variable, it is “pushed” onto the stack, and after that variable falls out of scope (such as when the function closes), that variable will be deallocated from the stack automatically. Once a stack variable is freed, that region of memory becomes available for other stack variables.

Due to the pushing and popping nature of the stack, memory management is very logical and is able to be handled completely by the CPU; this makes it very quick, especially since each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor’s cache. However, there are some cons to this form of strict management. The size of the stack is a fixed value, and allocating more onto the stack than it can hold will result in a stack overflow. The size of the stack is decided when the thread is created, and each variable has a maximum size that it can occupy based on its data type; this prevents certain variables such as integers from ever growing beyond a certain value, and forces more complex data types such as arrays to specify their size prior to runtime since the stack won’t let them be resized. Variables allocated on the stack also are always local in nature because they are always next in line to be popped (unless more variables are pushed prior to the popping of earlier variables).

Overall, the stack really exceeds in managing memory in the most efficient way possible – but what if you need data structures that can be dynamic, such as a dynamically sized array, or what if you need global variables? This is where the heap comes into play.

The Heap

The heap is a memory store also in RAM that allows for dynamic memory allocation, and does not work on a stack-like basis; this means there is no notion of pushing and popping variables, and it’s more just a hub of storage for you to define your variables. Once you allocate a memory location on the heap to store a variable, that variable can be accessed at any point in time not only throughout just the thread, but throughout the application’s entire life. This is how you can define global variables. Once an application ends, all of the allocated memory locations are reclaimed by the CPU. The heap size is set on application startup, but unlike the stack there are no size restrictions on the heap (aside from the physical limitations of your machine), which means it can get ever larger as you allocate more memory to it. This is what allows you to create variables that can be dynamically resized, since the heap itself is dynamic in size.

You interact with the heap via references typically called ‘pointers,’ which are variables whose values are the address of another variable, such as a memory location. By creating a pointer, you ‘point’ at a memory location on the heap, which is what signifies the initial location of your variable and tells the program where to access the value. Due to the dynamic nature of the heap, it is completely unmanaged by the CPU aside from initial allocation and heap resizing; in non-garbage collected languages such as C and C++, this requires you as the developer to manage memory and to manually free memory locations when they are no longer needed. Failing to do so can create memory leaks and cause memory to become fragmented, which will cause reads from the heap to take longer and makes it difficult to continuously allocate more memory onto the heap.

Compared to the stack, the heap is slower to access because variables are scattered across memory instead of always sitting at the top of the stack. Improper memory management of the heap can also slow down reading from the heap; however, this shouldn’t detract from its importance – you absolutely need it to create any type of variable dynamically, or a global variable.

Final Thoughts

So there you have it – the basics of the stack and the heap. In a nutshell, the stack is an amazingly fast memory store with a LIFO allocation algorithm that is managed completely by the CPU, and you don’t have to manage it at all. However, these benefits force the stack to have a limited size and a specific method for retrieving values, so you are only allowed to allocate fixed memory sizes (i.e. fixed-length variables) and local variables on it. To make up for these limitations, the heap allows you to create dynamically allocated variables during runtime, as well as global variables – but either you or the garbage collector must handle memory management, and it is quite a bit slower than using the stack.

The importance of the stack and the heap really comes into play with non-garbage collected languages where you need to manage memory yourself – and while modern languages do abstract away the need for this, they’re all still doing it under the scenes. Different languages use the stack and the heap differently; C and C++ allocate to the stack automatically, and you as the developer manually have to allocate and deallocate from the heap, where more modern languages such as Go and Java allocate to both the stack and the heap automatically, and have a garbage collector that handles heap deallocation on its own. There are even languages like Ruby and Python where everything is allocated on the heap and don’t use a stack at all.

I hope this helped to provide some historic programming knowledge that we tend to miss out on these days! I plan on continuing this series over core programming concepts in future blog posts, which you also may enjoy if you found this interesting. For more information on the stack and the heap, google away – the answers are at your doorstep (or browser)!