I recently wrote a page-replacement simulator to experiment with functional techniques to handle memory retrieval on demand, as well as explore page-fault averages for a variety of paging algorithms and learned that elisp (Emacs Lisp) does not perform tail-call optimization on tail recursions!
Wait, first of all, what is a paging system? Paging is a concept in the scope of computer Operating Systems that deals with a programs need to access (and thus load to memory) specific pages of information from memory. When simulating the concept of paging, usually we are concerns with three main variables. Assume we only have to serve pages to a single process. Unrealistic, but bare with me. In this scenario, we first need to know the sequence of pages that the process needs. This information could appear as streaming request from a process, or a process may submit a request for an ordered sequence of pages. Once we have the ordered sequence, we need to have finite memory, we need some way of managing the page requests of processes. How many pages can we store at once? How long does it take (how expensive is it) to load new pages into memory? Chances are, we don't want to load a page into memory if it is already in memory. Or maybe we do! This brings us the the third factor: the paging algorithm. There are many different paging algorithms which depend greatly on the hardware its host computer has available. Some common examples of paging algorithms are FIFO (first in, first out) and LRU (least recently used). These are two paging systems that I explore in my simulation. If you are interested about learning more about paging systems, memory management, and virtual memory, I suggest reading: http://webster.cs.ucr.edu/AoA/Windows/HTML/MemoryArchitecturea3.html.
I have to study for a final exam for database theory now, so I will save the rest for a second post. In the follow up I will illustrate how I achieved a functional (paradigm) implementation of a paging system for FIFO and LRU, introduce the idea of recursion versus tail recursion, and then vent by ranting about why it is unacceptable that Emacs Lisp doesn't have tail-call optimization.
Also, this is a reminder to myself to talk about some new projects I am working on for computational linguistics, data mining, and machine learning. Code name: Linguistipedia.
