Full Width 
Shortcuts 
Sign Up 
Log In 
Articles 
Reading List More from Paolo Amoroso's Journal
<![CDATA[My journey to using and programming computers started around 1983 with a Sinclair ZX Spectrum 48K, the very first I owned. At the time I was clueless. For example, I wondered whether, once I loaded a program from tape, I needed to write it back at the end of the session so that it didn't vanish when turning off the machine. The Sinclair ZX Spectrum Introduction and the Sinclair ZX Spectrum BASIC programming guides that came with the device were my first learning resources, complemented by the great Italian computer magazine MC-microcomputer. Aside from some books, in that pre-online era technical documentation wasn't easy to come by in Italy, especially foreign works in English. I pored over the Spectrum manuals, reread them many times, and experimented with the sample code. I've never been into gaming but did run many games to see what the machine could do. I've come a long way since then, hopefully. #retrocomputing #personal a href="https://remark.as/p/journal.paoloamoroso.com/the-origins-of-my-computing-journey"Discuss.../a Email | Reply @[email protected] !--emailsub--]]>
<![CDATA[GravityLoops, my gravity simulator in Interlisp and LOOPS, can finally show something on the screen. The program now animates a body of mass like the Moon interacting under gravity with a body of mass like the Earth. The dots in the simulation window here are the bodies after 180 days of simulated time, with the Earth at left. Watch the full run. Screenshot of a still frame of a simulation of a body like the Earth and one like the Moon interacting under the muatal gravity. Well, that's not much. But the code confirms the simulation loop with an offscreen buffer works well. After putting in place some infrastructure, to get there I wrote the simulation loop, tweaked a few methods, wrote a demo function that sets up the simulation, and fixed a few bugs. There's a lot more to do. I need to make the graphics of the body markers more complete and explanatory, control the speed of the animation, fix more bugs, and refactor to decouple some interclass dependencies. And, of course, GravityLoops will also have a user interface to control the simulation and enter the parameters. #GravityLoops #Interlisp #Lisp a href="https://remark.as/p/journal.paoloamoroso.com/early-simulations-with-gravityloops"Discuss.../a Email | Reply @[email protected] !--emailsub--]]>
<![CDATA[I started working on the class Universe of GravityLoops, my gravity simulator in Interlisp and LOOPS. I defined the class itself and the main methods, Universe.Register and Universe.Simulate. The class represents a collection of bodies and manages the parameters and state of the simulation. Universe.Register adds a body to a universe, Universe.Simulate runs the simulation. In the C++ code of the article my design draws inspiration from, an instance variable of the class UNIVERSE holds a pool of bodies in an array, with the most recently added body indexed by another instance variable. In GravityLoops the corresponding instance variable bodyPool is a list which, as the article notes, is more versatile and doesn't need the index. Universe.Simulate, just a stub for now, is the core method. It will update the state of the simulation, display the bodies in a graphical window along with status information, and check whether the user interrupts the simulation. The C++ program runs the simulation until the user presses a specific key and GravityLoops will have a similar feature. I'll also have the program accept a number of time ticks to step the simulation through. For Universe.Simulate I'll mostly follow the C++ code. But I plan to revisit the decision after I have something running to experiment with. I may want to split the simulation functionality into more than one method to separate the simulation itself from output, or redesign control around LOOPS' active values. #GravityLoops #Interlisp #Lisp a href="https://remark.as/p/journal.paoloamoroso.com/representing-the-universe-of-gravityloops"Discuss.../a Email | Reply @[email protected] !--emailsub--]]>
<![CDATA[I started working on GravityLoops, a software that simulates a collection of bodies interacting under the mutual gravity. I develop it on Medley in Interlisp and its object extension LOOPS, the Lisp Object-Oriented Programming System. GravityLoops will show an animation of the bodies and their motions, along with facilities for defining the parameters of the system and controlling the simulation. Motivation I've been meaning to do a LOOPS learning project but none of the ideas I initially came up with clicked. I wanted something more complex than a toy but easy enough to implement with reasonable effort. The project should also incorporate naturally the features of LOOPS, such as the gauges library of graphical meters and dials for displaying quantities. I finally stumbled upon the gravity simulator described in the article Force-Based Simulations by Todd King in the September, 1989 issue of Dr. Dobbs Journal. It's just perfect. I'm adapting to LOOPS the design of the sample C++ code that comes with the article. It's nice as it reads like an object-oriented domain specific language for simulation. The code is so short and clean I can fully understand it despite my minimal C++. I never thought I would say that of C++. There is much to like of King's program starting from its domain, astronomy and physics, which overlaps with some of my passions. The project is period accurate too as when Dr. Dobb's Journal published the article LOOPS was still under development. And, along with window systems, simulation was among the killer applications object-oriented programming proponents pointed to. The program comprises only two, hierarchically unrelated classes, a shallow inheritance design more in line with the later evolution of object-oriented programming. But the application does offer other potential classes that are a good fit for LOOPS. For example, I plan to specialize the LOOPS class Window to represent the simulaton window. I will likely need more classes for the GUI, such as dialogs for entering the simulation parameters. LOOPS is one of the subsystems best integrated with the Interlisp environment and comes with good documentation. I want to experience this high integration, the ability of combining tools designed to work together that comes natural once you're familiar with the environment. Adapting King's program to the Interlisp environment is also an opportunity to employ useful programming techniques like screen buffering to improve animation fluidity. Plus, anything that draws pretty graphics is fun. Design To adapt Todd's design to LOOPS I create matching classes with similar instance variables and methods, named according to the LOOPS style. I will rename a few confusing methods, such as UNIVERSE::service() to register a body with a universe which I'll call Universe.Register, and UNIVERSE::big_bang() to run the simulation which will become Universe.Simulate. The C++ code represents a 2D vector as a struct that I map to an Interlisp record. A class seems overkill. Todd's program outputs to the MS-DOS text console via the conio library. GravityLoops instead will draw graphics in a window. So far the code implements the Body class that represents a body. I'm about to start working on the Universe class that holds a collection of bodies and manages the parameters and state of the simulation. Once the core classes are in place I will turn to implementing the animated simulation. #GravityLoops #Interlisp #Lisp a href="https://remark.as/p/journal.paoloamoroso.com/gravityloops-a-gravity-simulator-in-interlisp-and-loops"Discuss.../a Email | Reply @[email protected] !--emailsub--]]>
<![CDATA[Insphex adds the Hexdump item to the File Browser menu to view the hex dump of the selected files. The initial implementation called the public API for adding commands at the top level of the menu. To later move the item to the See sumbenu that groups various file viewing commands I resorted to list surgery, as the API doesn't support submenus. The problem is internal system details can and do change, which happened to the File Browser menu and led to an Insphex load error. I fixed the issue by reverting the public API call and now the item is back at the top level of the menu. Insphex is a hex dump tool similar to the Linux command hexdump. I wrote it in Common Lisp on Medley Interlisp. #insphex #CommonLisp #Interlisp #Lisp a href="https://remark.as/p/journal.paoloamoroso.com/rearranging-the-file-browser-menu-for-insphex"Discuss.../a Email | Reply @[email protected] !--emailsub--]]>
More in programming
A clip of me singing a funny song from Gilbert and Sullivan’s Ruddigore back in 2013
In this video, we look at why fork() needs copy-on-write, how it works inside the kernel, and a memory usage problem that Instagram encountered with Python.
Comments require commitment, but they’re worth it.
An aggregation is some kind of summary of a set of data. This can be the sum, length, minimum, etc. It is quite common to want to calculate such a summary repeatedly, e.g. “the maximum noise level in dB for the past 30 seconds” for a nuisance detector. In such a case we say there is a sliding window over our data, and we want to aggregate over our window. If our aggregation is a binary operator with an inverse, like integer sums, there is a very easy solution using a double-ended queue: from collections import deque class SlidingWindowSum: def __init__(self): self.sum = 0 self.elems = deque() def push(self, x): self.sum += x self.elems.append(x) def pop(self): self.sum -= self.elems.popleft() def eval(self): return self.sum But what if our operator has no inverse? This is actually the case for most interesting summaries such as minimum, quantile, approximate unique count (for example using HyperLogLog), etc. In fact, even something as simple as a floating-point sum suffers from the fact that floating-point addition is not invertible. For example, if you ever have a NaN in your input data with the above naive algorithm your sum will forever remain NaN, even long after the bad value has left your window. Six years ago I came up with an algorithm for maintaining just the minimum/maximum in a sliding window and posted it to cs.stackexchange. I now consider this algorithm pointless, because it turns out there is a simple and efficient algorithm that solves this problem for a very wide class of aggregations. I’m writing this blog post to spread the word, because I feel it should be more widely known. Folklore I came across this algorithm while reading a far more advanced paper, Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time by Tangwongsan et al. Why is this paper titled low-latency? Because it does the same as what I’m about to describe, but in O(1) time for each step. However, in it they also described a “two-stack” algorithm, which does it in amortized O(1), and is far, far simpler. Amortized O(1) means that across many operations the total amount of work per element is constant, but an individual operation can take much longer. This is almost always fine, unless you absolutely need a low upper bound on latency. Funnily enough that paper attributes this algorithm to “adamax” from a 2011 Stack Overflow post. They in turn credit a 2001 lecture note by D. Sleator for the inspiration. However, this lecture note does not describe a sliding window aggregate, it describes the classical two-stack algorithm for implementing a FIFO queue and does amortized analysis on it. Ultimately I would not be surprised to find that this algorithm was already described in an obscure paper from the 1970s, seeing how simple and brilliant it is. Two stacks Like the authors of the paper, I will generalize the two-stack algorithm to arbitrary associative aggregation functions. By abstracting the aggregation as a set of functions, empty(), unit(x), combine(x, y) and finalize(x), you can describe many possible aggregations, for example a mean: empty = lambda: (0, 0) unit = lambda x: (x, 1) combine = lambda x, y: (x[0] + y[0], x[1] + y[1]) finalize = lambda x: x[0] / x[1] if x[1] else None I’d like to note here that these functions have the following signatures: fn empty() -> Agg; fn unit(x: Value) -> Agg; fn combine(x: Agg, y: Agg) -> Agg; fn finalize(x: Agg) -> Out; I’m making a distinction here between Value, Agg and Out because while they seem superficially similar for something like an integer sum, for an approximate unique count on strings you would have (Value, Agg, Out) = (String, HyperLogLogSketch, u64), three wildly different types. Without further ado, the algorithm: class TwoStackAgg: def __init__(self): self.values = [] self.values_agg = empty() self.cum_aggs = [] def push(self, x): self.values.append(x) self.values_agg = combine(self.values_agg, unit(x)) def pop(self): if not self.cum_aggs: cum_agg = empty() while self.values: cum_agg = combine(unit(self.values.pop()), cum_agg) self.cum_aggs.append(cum_agg) self.values_agg = empty() self.cum_aggs.pop() def eval(self): return finalize( combine(self.cum_aggs[-1], self.values_agg) if self.cum_aggs else self.values_agg ) That’s it, the entire algorithm. There’s two stacks (values and cum_aggs) and one more aggregate, values_agg. At any point in time values_agg holds the aggregate of values, and cum_aggs contains the cumulative aggregates of all values in our window that aren’t in values, in reverse order. From this we can get the aggregate over our entire window in constant time by by combining the last value of cum_aggs with values_agg. The neat part is that (assuming w is our window size) every wth operation we drain all of values and maintain a running aggregate while pushing the partial cumulative aggregates onto cum_aggs. This is what makes it amortized O(1), doing O(w) internal operations every wth pop bounds the total amount of work per element to O(1), even though a singular operation might not be constant time. I think this is best visualized. Suppose we sum [1, 2, ..., 10] with a fixed-size sliding window of four elements, then the state on each eval() call would look like this (values_agg not shown as it is simply the aggregate of the values): cum_aggs values out [] [] = 0 [] [1] = 1 [] [1, 2] = 1 + 2 [] [1, 2, 3] = 1 + 2 + 3 [] [1, 2, 3, 4] = 1 + 2 + 3 + 4 [4, 3 + 4, 2 + 3 + 4] [5] = 2 + 3 + 4 + 5 [4, 3 + 4] [5, 6] = 3 + 4 + 5 + 6 [4] [5, 6, 7] = 4 + 5 + 6 + 7 [] [5, 6, 7, 8] = 5 + 6 + 7 + 8 [8, 7 + 8, 6 + 7 + 8] [9] = 6 + 7 + 8 + 9 [8, 7 + 8] [9, 10] = 7 + 8 + 9 + 10 [8] [9, 10] = 8 + 9 + 10 [] [9, 10] = 9 + 10 [10] [] = 10 [] [] = 0 In total the memory usage is O(w), where w is your maximum window size. Note that for simplicity of analysis and the example I assumed a fixed-size window w, but there is nothing about the two-stack algorithm that requires this. You can call push(x) and pop() as many times as you’d like between each eval(), growing and shrinking the window size as needed. Floating-point non-associativity Note that we required above that our aggregate combine is associative, meaning: combine(combine(x, y), z) = combine(x, combine(y, z)) Technically speaking, floating-point addition doesn’t respect this. Nevertheless, the above algorithm is still very useful because the results closely match the expected outcome, even more so if you use a compensated summation algorithm like Kahan summation. Another neat thing about the two-stack algorithm is that it doesn’t require commutativity, if you follow the above implementation precisely. The order of operands is maintained, which can matter for things like string concatenation. However, there is a second very useful property of the above algorithm. Each aggregate is strictly a combination of the elements in the window, and none outside the window. This means if your window contains a NaN or infinity (or some other outlier), that value only poisons the windows that contain it rather than the rest of your computation. But even without NaN or infinity it is useful, due to not propagating errors endlessly. E.g. if your sliding window starts with [1e20, 1], this is what would happen with a naive rolling sum: >>> 1e20 + 1 - 1e20 - 1 -1.0 Compensated summation will reduce these effects, but not making your result depend on values outside of the window will eliminate long-term error accumulation entirely.
