The Basics of a Programming Language

An empty diagram with each of our steps in a corner, numbered 1. Read, 2. Understand, (3. Cache), 4. Execute

When a program is run, several things happen:

  • Your source code (usually text files) is read
  • The computer builds a data structure (usually some kind of tree) that describes what you are actually asking of it
  • The computer walks the nodes of this tree and actually performs the operations described

In a traditional, compiled programming language, the firs two steps usually happen on the developer’s computer. The result is then written to disk somehow, and sent to the users, who then launch the program. The given result is then fed directly into the CPU, which actually executes the last step and does the work.

So really, there are 4 corner-points to running a program:

  1. Reading
  2. Understanding
  3. Caching (i.e. saving the result of a step to disk for later use)
  4. Executing

These steps all take different amounts of time, and usually we language makers try to make this time as short as possible, so computers will be fast. But not all time spent is equal. Where can time be spent?

  • compilation overhead: Time for people writing a program until they have a runnable program for their code
  • user overhead: Time for users of the program until the program starts running
  • execution time: Time a program actually takes to produce its result on the user’s machine

Also, a programming language can have memory requirements, which usually boil down to:

  • peak RAM usage: How much RAM does the program use, worst case
  • per instruction RAM usage: How much RAM is minimally needed to run one instruction
  • disk usage: how much disk space is used for the cache

And again, these are relevant both to the developer writing the program, as well as a user running the program (which may sometimes be the same person, but e.g. in the case of your text editor aren’t).

I know this is a bit dry, just go back to these definitions when I mention them later on and you’ll be fine.

How an interpreter works

A diagram showing that an interpreter values reading the most, followed by understanding and executing, and cacheing the least.

An interpreter is a program that reads your text file, line-by-line, and as soon as it has enough information to understand a line, it will do what that line says. In fact, it may not even wait that long. If a certain expression on that line is complete, it may just do that expression, then continue reading the rest of the line.

Interpreters are basically the naïve approach to running a program, how we as a human do it each day. We have a list that describes a process, and we do each item.

If we go back to our 4 corner points above, a pure interpreter basically reads (1) a bit of code until it understands (2) it, then executes (4) it and doesn’t do any caching (3).

Picture of a stopwatch showing the alternating time slices between reading, understanding and executing

This means an interpreter is really quick at getting to the point where the first line of your program is executed in absolute time. It only needs to read the first line and can immediately run it. The compilation overhead is basically 0. You just write the script to be interpreted and send it off. The user overhead is fairly small. It includes reading and understanding the code, but only one line. Then it immediately executes.

Total execution time is a bit longer, though: Before a line can be run, it has to be read and understood on the user’s computer. So between each line is a bit of reading and understanding. Worse, since a pure interpreter performs no caching, if there are loops, each line of the loop needs to be read and understood every time it is executed.

And how is memory? An interpreter needs little disk space: Basically, only your source code. It also needs a little bit of RAM per instruction to keep the current line in RAM. Peak RAM usage is fairly low.

How a compiler works

A diagram showing that an compiler values cacheing the most, followed by understanding and executing, and reading the least.

As mentioned above, the other extreme, a pure compiler, Reads (1) the entire code once, understands (2) it, then saves that code to disk (3) and then that is sent to the user, which can just let the CPU execute (4) it.

Performance wise, that means the compilation overhead is fairly significant. The developer waits a while for the entire program to be read, understood and written. The user overhead, on the other hand, is quite low: The entire program needs to be loaded into RAM, but it is in the compact form the CPU understands. But then the user can immediately run any instruction in the program.

Picture of a stopwatch showing one time slice each for reading, understanding, caching and executing

How is memory usage? Well, the developer needs enough memory (and disk space) for the entire program to be translated. The user needs enough memory to load the entire program into RAM. But the user usually needs less disk space because the program is in a smaller, binary form than the text form of the original source code.

Hybrid Approaches

So I’ve been harping on about the distinction between the developer and the user, and overheads. Why? Isn’t it clear-cut that compilation makes for faster programs, and interpreters are crap?

It isn’t. I’ve been talking about “pure” compilers and “pure” interpreters here, but nobody makes a “pure” anything. That’s what the words mean, but usually you find a comfortable spot on the continuum between those two extremes, or you combine both approaches at different levels, to yield performance benefits to your users.

Scripting Languages

The idea behind a scripting language is usually that it is written by the user to automate some things on their computer. Scripts are frequently modified to suit the user’s needs, or expanded to account for newly-discovered requirements. Or they are one-offs that are written once, and run once. Yes, there are scripts that made it into production, but what I describe, again, is the ideal of a script, and what makes it different from a program. Like a film script, it orchestrates existing systems to collaborate. Scripting languages are awesome wherever things change often and fast turnaround is needed.

So scripts are usually written and run by the same person. The distinction between time and disk space taken for the developer and the user doesn’t matter here. How does the value proposition for a compiler look here?

Bad. My script is on disk as a text file. Now the compiler generates an executable from it, which will take even more disk space. It will also take its sweet time doing so. Only once that is done, and the entire program has been translated, will it deign to run my program.

Worse, if I made a mistake, I will have to recompile the entire script again after fixing the issue.

The interpreter is suddenly looking much better: It doesn’t need extra disk space just to run my script, and it starts running it right after it read the first line. If I made a mistake and the program aborts with an error, it gets even better: The interpreter didn’t even bother reading the rest of the script. If my script has several parts dealing with different things, it can even run parts and only spend time reading/understanding the parts I am actually using. The rest of my script is ignored until it is actually used.

There’s no faster way to do work than realizing you don’t need to do that work.

So you see, depending on your use case, interpreters are better. Compiled programs are mainly good for split use, like commercial application software, where one person (the software company’s developer) can do some of the work ahead of time, and thus save it for everybody else.

Virtual Machines

You’ve probably heard of Virtual Machines. They’re very popular with people who make programs that need to run on multiple different computer systems, with different operating systems, different CPU architectures etc.

They are needed because compiled software runs directly on the CPU. It is written in the language of that CPU. So if you want to run the same program on multiple CPUs, you need to provide multiple versions of your program translated into each CPU’s language (and if you speak a foreign language, you will know that translation never just involves substituting one word for another – sometimes there is no word that means the exact same thing in another language, and you have to approximate with several words what that one word meant). And you need to devise a way so each user gets the right version for their platform.

One solution for this problem is to send your source code as text to the user, and have them translate the program to machine code on their system. This is what web browsers do. They contain a scripting language named JavaScript, and will just run programs written in that language.

This works, but given programs on web sites are usually not changed by users, wouldn’t it be cool if we could compile them on the server and be faster?

That’s what Virtual Machines do. A Virtual Machine is, essentially, a program that simulates the behaviour of a CPU. It is an interpreter. It takes instructions written in a made-up CPU’s language, and reads, understands and executes them right away on the real CPU.

It is also really, really fast. Not as fast as native machine code doing the same thing running on the same CPU, but still fast enough. It is also comparatively small, and easy to port to another platform.

Usually a Virtual Machine does some more involved things than a CPU, too. Many Virtual Machines have built-in instructions that do things like create a window, draw into it etc. These translate to hundreds if not thousands of instructions of the native CPU. Why? Because those are the things we need to do on every platform, and they need to be ported as well. So everything that must be rewritten for every CPU and operating system just gets wrapped up in that single program, the Virtual Machine. And you write a new, small Virtual Machine for each CPU/operating system combination you support.

Everything else can now be written in the common language all the Virtual Machines for each platform implement. “Write once, run anywhere”, as the saying goes. And for this common language, we can write a compiler.

Yes, you heard right: A Virtual Machine consists of both an interpreter and a compiler. The compiler does a lot of work beforehand, creating a small, fast binary representation of your program that can be sent to every user, no matter what platform they’re running. It will take a slight speed hit compared to a native program, but it will make up for that because it is simpler to distribute than a real compiled binary, and smaller and faster than a script. Also, you’re not sending your source code out to everyone…

A Virtual Machine makes sense where you can assume that all your users already have the Virtual Machine on their computers, e.g. because enough other programs use the same VM that they’ve already installed it.

If you write your own Virtual Machine, you’ve only pushed the problem down one level of abstraction: Instead of having to distribute your program for each platform, you need to distribute the VM for each platform, and then your users also need to download the actual program. That doesn’t make sense unless you expect the average user to download several programs written against the same VM, or the VM rarely changes, while your program frequently does.

Just-in-Time Compilers

Just-in-Time compilers, or JITs are another hybrid approach. They can be applied to any interpreter (even to our Virtual Machine above). What they basically do, is add a level of cacheing to an interpreter. Yes, a JIT-compiler is actually a component of an interpreter.

Basically, what a JIT does is address the case of interpreted code being executed several times. If it notices a piece of code that is being run a second time, or encounters code that is expected to be run repeatedly (like a loop), it actually compiles that code into native machine code and keeps that native machine code cached in RAM.

Which means that, the initial user overhead of loops becomes a bit larger, but you likely get the time spent compiling the entire loop body back due to the faster execution time later on.

This is a very specific optimization you can make for an interpreter, but a surprisingly effective one, particularly for Virtual Machines, where the only reason you didn’t compile to native is that you need a common CPU architecture for easier distribution of your software to a varied selection of hardware. Many VMs compile all code you run (e.g. each function), keep it cached in RAM, and then purge the code that hasn’t been run in a while if the cache exceeds a certain size.

The Wild Mixing and Matching of Modern Web Browsers

There are many ways you can combine compilers and interpreters, and steps of the process that you can cache, and also with contextual knowledge of your application, you can choose different optimizations in different situations. Take scripts on web sites, for instance.

They are scripts, because the original idea was that everyone would have their own web site and write the scripts themselves. Having a bunch of text files on a server and running the actual code in the client just seemed easiest and was how things were done back when the web was invented in the 90ies. They are scripts because that’s most accessible and it makes it easy to learn from other web sites when you make your own.

They are also scripts because they were to be embedded in HTML text files.

But most web sites these days are used by millions of users, none of which edit these scripts, so it actually makes more sense to optimize to reduce user overhead and execution time instead of quick turnaround for the developers.

As a compromise, browsers’ JavaScript “interpreters” now contain JIT compilers of various forms, and decide on a per-function-level which one to apply.

For example, the onLoad() script on a web page is run exactly once, when the page is loaded. So we just run that in a traditional interpreter.

On the other hand, the onKeyUp() handler on a web page is called for each key press in a text field. Given text fields usually contain more than one character, we can assume that any onKeyUp() function gets called several times. So it makes sense to compile any such function and keep it around as long as the page is loaded.

And many functions on a web page are only run when you actually use that feature on the page. So the browser will just do a quick cursory scan over the entire script (so it knows where each function’s text starts and ends and what its name is) and defer actually compiling and optimizing and running its code until you actually call it. And if you call it from e.g. onLoad() or onUnload(), it won’t even bother compiling/optimizing them, and will just interpret them.

And of course there is the browser itself, a program that is developed by a company and used by users to run web pages, a classic compiled application. A lot was spent on a developer’s computer making it smaller and faster before it gets to you, and you can just run its native code right away.

In Closing

So that’s the difference between compilers and interpreters: Two sides of a spectrum, that can even be used together. Two points in the four-corner diagram square of “Read, Understand, Execute, Cache”.

Note: This post came out of my answer to a Stackoverflow question, in case you are looking for a shorter, slightly different answer to this question.

Disclaimer

The goal of this article is not to promote good usability practices or to explain how your operating system’s program loader works.

Therefore, I have simplified a few things from those domains and focused on explaining compilers and interpreters. For example, most operating systems do not load an entire program file into RAM to run it, but rather transparently load parts using “virtual memory”. The general issue holds true, the order of magnitude may just be lower.

Similarly, cross-platform code can be very convenient but suffers from several issues, like looking and feeling the same on all platforms, even if your user only uses it on their platform, where they are used to a different look-and-feel. Or the additional abstractions you build on top of the operating system-specific instructions may slow things down on platforms which have a more efficient abstraction (To return to our foreign language metaphor: your phrases may become longer if your translation needs several words to describe your language’s one-word concept, making you take longer to say the same thing, despite there being a way for a native speaker to re-order the whole sentence that would result in one much shorter).