Joe MarshallDecode a Float (Solution)

· 2 days ago

We can multiply or divide a floating point number by 2 without changing the bits in the mantissa. So we can rescale the number to be in the range [1, 2) by repeatedly multiplying or dividing by 2. The leftmost bit of the mantissa is always 1, but next bit determines whether the number is in the top half of the range or the bottom half. So if the number is equal to or greater than 1.5, the next bit is 1, otherwise it is 0.

If the number is in the range [1, 2), we can subtract 1 from it. The remaining bits will be shifted left until the leftmost bit is 1. If the number is greater than or equal to 1.5, then subtracting 1 will shift the bits left by one. But if the number is in [1, 1.5), we won’t know how many zero bits will be shifted out when we subtract 1. What we’ll do is add .5 to the number to turn on the next bit, then subtract 1 to shift the bits left by one.

Here is the code in Common Lisp:

(defun float->bits (float)
  (cons 1 (read-bits float 0)))

(defun read-bits (float count)
  (cond ((>= count 52) nil)
        ((> float 2.0d0) (read-bits (/ float 2.0d0) count))
        ((< float 1.0d0) (read-bits (* float 2.0d0) count))
        ((>= float 1.5d0) (cons 1 (read-bits (- float 1.0d0) (1+ count))))
        (t (cons 0 (read-bits (- (+ float .5d0) 1.0d0) (1+ count))))))

Note that all these operations are exact and do not cause round off.

Joe MarshallDecode a Float

· 2 days ago

The leftmost bit of any positive binary number is always 1. So if you were to left-justify a positive binary number, the top bit would always be 1. If the top bit is always 1, there is no need to implement it. Floating point numbers use this trick.

You can determine the bits of an integer using only arithmetic operations by repeatedly dividing by two and collecting the remainders. Today’s puzzle is to determine the bits of a floating point number using only arithmetic operations (no decode-float or integer-decode-float).

Joe MarshallD-day, 80 years ago today

· 12 days ago
More than 150,000 troops, 5,000 ships, 13,000 aircraft in the largest amphibious assault in history.

Joe MarshallMultithreading and Immutable Data

· 13 days ago

I was amusing myself by looking at Lisp tutorials. They used the idea of a Tic-Tac-Toe service as a motivating example. You’d be able to play Tic-Tac-Toe against the computer or another opponent.

My immediate thought went to the issue of multithreading. If you were going to serve hundreds of people at once, you’d need to have a multi-threaded service. Multi-threaded code is hard to write and debug, and it is much better if you have a plan before you start than if you try to retrofit it later (that trick never works).

The magic bullet for multi-threading is immutable data. Immutable data is inherently thread-safe. It doesn’t need synchronization or locks. If all your data are immutable, you can pretty much ignore multi-threading issues and your code will just work.

Using a 2D array to represent a Tic-Tac-Toe board is the obvious thing that first comes to mind, but not only are arrays mutable, they virtually require mutation to be of any use. The Lisp tutorials I was looking at all used arrays to represent the board, none of them locked the board or used atomic operations to update it, and all had the potential for race conditions if two threads tried to update the board at the same time. Arrays are essentially inherently thread-unsafe.

I thought about alternative representations for the board. Different representations are more or less amenable for writing code that avoids mutation. I came up with a few ideas:

  • Use a 2d array, but copy it before each mutation. This is horribly inefficient, but it is simple.
  • Use a 1d array, again copying it before each mutation. This isn’t much different from the 2d array, but iterating over the cells in the board is simpler.
  • Keep a list of moves. Each move is a pair of player and position. To determine the state of the board, you iterate over the list of moves and apply them in order. This is a bit more complicated than the array representations, but it is inherently immutable. It also has the advantage that you can rewind the board to any prior position.
  • Encode the board as a pair of bitmaps, one for each player.
  • Encode the board as a single bitmap, with each cell represented by two bits.
  • There are only 39 ways to fill out a Tic-Tac-Toe grid, so you could represent the board as an integer.

Each one of these representations has pros and cons. I wrote up some sample code for each representation and I found that the representation had a large influence on the character of the code that used that representation. In other words, there wasn’t a single general Tic-Tac-Toe program that ended up being specialized to each representation, but rather there were six different Tic-Tac-Toe programs each derived from its own idiosyncratic representation.

In conclusion, it is a good idea to plan on using immutable data when you might be working with a multi-threaded system, and it is worth brainstorming several different representations of your immutable data rather than choosing the first one that comes to mind.

Joe MarshallRoll Your Own Syntax

· 17 days ago

Unlike most languages, Lisp represents its programs as data structures. A Lisp program is a set of nested lists. We can look at a Lisp program as a tree, with each nested list as a node in the tree. The first element of each list indicates the kind of node it is. For instance, a sublist beginning with LET binds local variables, a sublist beginning with IF is a conditional, and so on.

In most languages, it difficult or impossible to add new node types to the syntax tree. The syntax is wired into the language parser and if you even can add new syntax, you have to carefully modify the parser to recognize it. In Lisp, adding new node types is quite easy: you just mention them.

To give an example, suppose you wanted to add a new node to the syntax tree called COMMENT, which would have a string and a subexpression as components. You'd use it like this:

(comment "Avoid fencepost error" (+ x 1))

Here's how you could define the semantics of a COMMENT node in Lisp:

(defmacro comment (string expr)
  expr)

That's it. You can now insert arbitrary COMMENT nodes into your Lisp programs.

Compare that to what you would have to do in a language like Java to add a new kind of node to the syntax tree. You'd have to modify the parser, the lexer, the AST classes, and probably a bunch of other stuff. It's non trivial.

For a more complex example, consider adding transactions to a language. In a language like Java, you'd have to modify the parser to recognize the new syntax, and then you'd have to modify the compiler to generate the correct code. In Lisp, you can just define a new node type:

(defmacro with-transaction (body)
  <complex macro elided>)

And then use it like this:

(with-transaction
  (do-something)
  (do-something-else))

Now obviously you should put some thought into doing this. Adding dozens of random new node types to the language would be a bad idea: readers of the code wouldn't be expecting them. But in some cases, a new node type can be just what is called for to abstract out complexity or boilerplate. Lisp gives you that option.

Joe MarshallIf I Were in Charge

· 21 days ago

If I were in charge of Python development, here are a few things I would do:

  • Add (optional) tail recursion. This would make it easier to write pure functional code. It would also make it possible to effectively program in continuation passing style. Making tail recursion optional should placate those that feel that stack traces are important for debugging.
  • Add macros. I am thinking of Lisp-like macros that do code transformation, not C-like macros that simply do token substitution. A good macro system would allow advanced users to create new syntactic forms for the language and provide a way to abstract boilerplate.
  • Allow a way to use statements inside expressions, or beef up the expression syntax to have exception expressions, loop expressions, etc. This, too, would make it easier to write pure functional code.
  • Optional end-of-block markers. These would allow you to automatically fix indentation errors and recover indentation when it is lost.
  • Use true lexical scoping. Changing this might break legacy code that depends on the current scoping quirks, though.
  • Use modern interpretation techniques to get the performance up to a more reasonable level. Performance doesn't matter that much, but Python is notably slow.
  • Get rid of the global interpreter lock so that multithreading works better. Probably easier said than done.

I don't believe any of these necessarily involve fundamental changes to the language. They'd just make the language more flexible, though I'm sure many people would disagree with me.

But, perhaps for the best, they're not going to put me in charge.

Paolo AmorosoBuilding a GUI for Insphex

· 21 days ago

I added a GUI to Insphex, the hex dump tool I'm writing in Common Lisp on the Medley Interlisp environment.

The initial version printed the hex dump only to the standard output, now optionally to a separate TEdit window with a command menu. The menu has items for displaying the next page of output, redisplaying from the beginning of the file, and exiting the program.

Window and command menu of the Insphex hex dump tool for Medley Interlisp.

Most window, menu, and other Medley GUI facilities, like the TEdit rich text editor, provide Interlisp APIs in the IL package that Common Lisp programs such as Insphex can access. However, since the APIs usually rely on Interlisp records, from Common Lisp it's often necessary to write quite a few package qualifiers like this example to create a menu record:

(IL:CREATE IL:MENU
           IL:ITEMS IL:← '(ITEM1 ITEM2 ITEM3)
           IL:MENUFONT IL:← '(IL:MODERN 12)
           IL:TITLE IL:← "Menu"
           IL:CENTERFLG IL:← T)

The XCL:DEFINE-RECORD macro helps reduce package qualifiers by wrapping Interlisp records in equivalent Common Lisp structures with ordinary structure accessors, setters, predicates, and constructors. The structures can be in any package, not just IL like Interlisp symbols. XCL:DEFINE-RECORD is described on page 7-3 (page 143 of the PDF) of the Medley 1.0 release notes.

This way Common Lisp blends well with Interlisp and reduces verbosity. For example, this is the Insphex Common Lisp function that creates the output window:

(DEFUN CREATE-HEX-WINDOW (FILE)
   "Create and return a window to display the hex dump of FILE."
   (LET* ((IN (OPEN FILE :DIRECTION :INPUT :ELEMENT-TYPE '(UNSIGNED-BYTE 8)))
          (COMMANDS (IL:MENUWINDOW (MAKE-MENU :ITEMS '(("Next" :NEXT "Show the next page.")
                                                       ("Reread" :REREAD "Reread the input file.")
                                                       ("Exit" :EXIT "Quit the program."))
                                          :MENUFONT
                                          '(IL:MODERN 12)
                                          :TITLE "Commands" :CENTERFLG T :WHENSELECTEDFN 
                                          #'HANDLE-MENU)))
          (OUT (IL:OPENTEXTSTREAM))
          (TEDIT-PROC (IL:TEDIT OUT))
          (WINDOW (IL:WFROMDS OUT)))
     (IL:ATTACHWINDOW COMMANDS WINDOW 'IL:TOP 'IL:LEFT)
     (IL:WINDOWPROP WINDOW 'INSTREAM IN)
     (IL:WINDOWPROP WINDOW 'OUTSTREAM OUT)
     (IL:WINDOWPROP WINDOW 'BLOCK-OFFSET 0)
     (IL:WINDOWPROP WINDOW 'IL:TITLE (FORMAT NIL "Insphex ~A" FILE))
     (NEXT-HEX-PAGE WINDOW)
     WINDOW))

The INSPHEX::MAKE-MENU constructor creates a Common Lisp INSPHEX::MENU structure that wraps the Interlisp IL:MENU record.

Most of the Insphex GUI functionality is in place but I need to work on a couple of tweaks.

First, the Insphex window should be read-only whereas now the user can type into the editor buffer. Next, I need to clean up all the allocated resources when the user quits the program via various interaction flows, such as closing the window instead of clicking the Exit menu item.

#insphex #CommonLisp #Interlisp #Lisp

Discuss... Email | Reply @amoroso@fosstodon.org

Joe MarshallException Handling for Control Flow

· 22 days ago

Back when I was taking a Software Engineering course we used a language called CLU. CLU was an early object-oriented language. A feature of CLU was that if you wrote your code correctly, the compiler could enforce completely opaque abstract data types. A good chunk of your grade depended on whether you were able to follow insructions and write your data types so that they were opaque.

CLU did not have polymorphism, but it did have discriminated type unions. You could fake simple polymorphism by using a discriminated type union as the representation of an opaque type. Methods on the opaque type would have to dispatch on the union subtype. Now to implement this correctly, you should write your methods to check the union subtype even if you “know” what it is. The course instructors looked specifically for this and would deduct from your grade if you didn't check.

One subproject in the course was a simple symbolic math system. You could put expressions in at the REPL, substitute values, and differentiate them. The core of the implementation was term data type that represented a node in an expression tree. A term was a type union of numeric constant, a symbolic variable, a unary expression, or a binary expression. Unary and binary expressions recursively contained subterms.

The term data type would therefore need four predicates to determine what kind of term it was. It would also need methods to extract the constant value if it was a constant, extract the variable name if it was symbolic, and extract the operator and subterms if it was a unary or binary expression. The way to use the data type was obvious: you'd have a four-way branch on the kind of term where each branch would immediately call the appropriate selectors. But if you wrote your selectors as you were supposed to, the first thing they should do is check that they are called on the appropriate union subtype. This is a redundant check because you just checked this in the four-way branch. So your code was constantly double checking the data. Furthermore, it has to handle the case should the check fail, even though the check obviously can never fail.

I realized that what I needed was a discrimination function that had four continuations, one for each subtype. The discrimination function would check the subtype and then call the appropriate continuation with the subcomponents of the term. This would eliminate the double checking. The code was still type safe because the discrimination function would only invoke the continuation for the correct subtype.

One way to introduce alternative continuations into the control flow is through exceptions. The discrimination function could raise one of four exceptions, each with the appropriate subcomponents as arguments. The caller would not expect a return value, but would have four catch handlers, one for each subtype. The caller would use the try/except syntax, but it would act like a switch statement.

The TA balked at this use of exceptions, but I appealed to the professor who saw what I was trying to do and approved.

There is some debate about whether exceptions should be used for control flow. Many people think that exceptions should only be used for “exceptional” situations and that it is poor form to use them for normal control flow. I think they are taking too narrow a view. Exceptions are a way to introduce alternative paths of control flow. One can use them to, for instance, handle an exceptional situation by jumping to a handler, but that's not the only way to use them.

Of course you should think hard about whether exceptions are the right way to introduce alternative control flow in your use case. Exception syntax is usually kind of klunky and you may need to rewrite the code to insert the exception handling at the right point. Readers of your code are likely to be surprised or baffled by the use of exceptions for control flow. There is often a significant performance penalty if an exception is thrown. But sometimes it is just the trick.

Joe MarshallECS in CLOS

· 23 days ago

Object systems make a natural fit for the game programming domain, but over time people have found that the object-oriented model provided by their favorite language doesn't always fit the use case. So developers have come up with “entity-component systems” (ECS) of varying complexity to fill the gap.

The basic idea is that a game object, called an “entity”, contains or refers to a set of “components” that define its behavior. Entities are too varied to be captured by a single class hierarchy, so we abandon inheritance in favor of composition. An entity that can be displayed on the screen has a “sprite” component, an entity that can move has “position” and “velocity” components, an entity that you can attack has a “hitbox” component and a “health” component. A entity that can attack you has an “attackbox” component. You can play mix and match the components to customize the behavior of the entity. We don't have a hierachy of components because each component can be added more or less independently of the others.

An ECS is an alternative or an augmentation to the built-in object system of a language, but it is an admission that the built-in object is insufficient.

CLOS provides an elegent way to implement an ECS without abandoning CLOS's built-in object system. We define a component as a “mixin” class that can be inherited from using multiple inheritance. We define mixin classes for each component, and then we define entity classes that inherit from the mixin classes. We would define a “sprite” mixin class, a “position” mixin class, etc. So the class of enemy entities would inherit from “sprite”, “position”, “velocity”, “hitbox”, “health”, and “attackbox” classes. A trap entity would inherit from “sprite”, “position”, and “attackbox” classes. A container entity that you could smash open would inherit from “sprite”, “position”, and “hitbox” classes. Etc.

Mixin classes aren't intended to be instantiated on their own, but instead provide slots to the classes that inherits from them. Furthermore, methods can be specialized on mixin classes so that instances derived from the mixin will respond to the method. This allows you to inherit from a mixin providing the particular desired behavior. For example, the “health” mixin class would provide a slot containing the entity's health and a “damage” method to decrease the health. Any entity inheriting from the “health” mixin will react to the damage method. Mixin classes can provide functionality similar to interfaces.

Mixin classes are an exception to Liskov's Substitution Principle, but they are a useful exception. Entities that inherit from a mixin do not have a “is-a” relationship with the mixin, but rather a “has-behavior-of” relationship. An entity inheriting from the “health” mixin is not a “health”, but it has the “health” behavior.

One feature of an ECS is that you can dynamically change the components of an object. For example, once an enemy is defeated, you can remove the “health” and “attackbox” components and add a “corpse” component. Is CLOS you could accomplish this by changing the class of the entity object to a class that doesn't have those mixins.

Of course care must be taken or you will end up with CLOS “soup”. But if you are careful, CLOS can provide a powerful and flexible system for implementing an ECS.

Joe MarshallWhy I Want Tail Recursion

· 25 days ago

The reason I want tail recursion is not to write loops (I can do that with a while loop), but to write in continuation passing style if I need to. Continuation passing style allows you to implement any control flow pattern you can imagine, not just the ones intrinsic to the language. You don’t want to use it all the time, but it’s a valuable fallback when you need some ad hoc advanced control flow. Without tail recursion, any non-trivial use of continuation passing style risks blowing the stack.

Iteration is just the special case of linear recursion that doesn’t accumulate state. 99 percent of the time, you know beforehand that you are looping and can use a looping construct, but sometimes you have the general case where whether you loop or not depends on the data at runtime. If you have tail recursion, you just write the code recursively and the tail recursion mechanism will turn it into a loop if it notices that you aren’t accumulating state.

If your language has lambda and tail recursion, it can implement any other control flow that might have been overlooked by the language designer. If it doesn’t, you're limited to the control flow the language designer bothered to implement.

Joe MarshallRewrite rules

· 26 days ago

I like rewrite rules. They are simple to understand and easy to implement. If you have a rewrite rule (or a set of them) that makes incremental progress in making an expression "simpler" in some sense, you can keep applying it (or them) repeatedly until you have finished the calculation.

If a function directly returns the result of calling another function, we say that the call is in "tail position". We can view this as a simple rewrite rule. Consider the fact-mul function which computes the factorial of a number n and multiplies it by another number m:

fact-mul (n, m) = n! * m

We can define two rewrite rules for this function. If n is 0, then the factorial is 1, so we just rewrite this as m. If n is not 0, we can rewrite this as fact-mul (n-1, n*m). This translates directly into Lisp:

(defun fact-mul (n m)
  (if (zerop n)
      m
     (fact-mul (- n 1) (* n m))))

The rewrite rule doesn't have to rewrite into the same function. For instance, we can rewrite odd? (x) to even? (x-1) and even? (x) to odd? (x-1):

(defun odd? (x)
  (if (zerop x)
      nil
      (even? (1- x))))

(defun even? (x)
  (if (zerop x)
      t  
      (odd? (1- x))))

Yes, this is bog-simple tail recursion, but somehow it seems even simpler to me if I think of it as a rewrite rule.

Even if you don't have tail recursion, or if you have disabled it, it still works, but the number of rewrites is limited by the stack depth.

Joe MarshallIf only ...

· 28 days ago

I have a problem with Lisp. It doesn’t do what I want. Whenever I write a Lisp program, I always find myself wanting new special forms that aren’t in the language. The object system almost never does exactly what I want. The control structures never cover all my use cases.

If only I could add new syntactic forms to the language. If only I could tweak the internals of the object system. If only I could add new kinds of control structure.

Oh, wait. I can.

Joe MarshallMaybe machine (part 2)

· 29 days ago

At the end of 6.004, we had a contest for improving the performance of the Maybe machine. There was an 8-bit ALU included in the chip set we were given, so the logical thing to do was to incorporate it into the machine in place of the shift register. This would naturally improve the performance of arithmetic operations, but there were other reasons that the Maybe machine was slow.

One of the rules of the contest was that we were not allowed to change the clock speed. But the Maybe machine had a four phase clock. The first phase would address the device driving the bus, the second phase would connect it to the bus, the third phase would clock the receiving device, and the fourth phase would keep the data asserted to obey the hold time on the logic.

The four phase clock was technically unnecessary. We had built it in this manner to illustrate set-up and hold times for the bus, but the TTL chips we were using were specifically designed to be used on an open collector bus with no hold time, so you could actually clock the bus on every other phase rather than divide by four and still be within valid hardware specs. The fundamental clock speed was not changed, but the machine would run twice as fast.

The microcode word on the Maybe machine had four parts. The first part loaded the shift register from memory. The second part operated on the shift register. The third part wrote the shift register back to memory, and the fourth part was the next microcode address. But much of a typical microinstruction was wasted time. More often than not, the shift register was loaded from the last location it was written to, so it already contained the data it needed. The load cycle was often unnecessary. If you just left the data in the shift register, it would already be there for the next instruction. A memory to memory move involved a no-op on the shift register, which took clock cycles. Advancing to the next instruction took more clock cycles.

Instead of a four part microinstruction, I made a one-part microinstruction. True, this meant that I would occasionally need more microinstructions, but each one was smaller, and I could omit the no-ops, so I could accomplish the same amount in fewer clock cycles. I eliminated the next-instruction field by replacing the microcode address register with a counter.

The original Maybe machine had a two-address microcode — each instruction would specify a separate load and store address. Most people retained the wide microcode and could specify each input to the ALU independently. But I wanted to squeeze each microinstruction into 16 bits, so I turned the machine into a one-address machine with an accumulator. This made my microcode one quarter of the size, but it made it difficult to find enough bits in the microcode to accomplish all the tasks it needed to do. I didn’t have enough bits to directly address the accumulator, so I attached the accumulator to the output of the ALU. One ALU input came from the bus, the other was fed back from the accumulator. To load the accumulator, you had to pass the data through the ALU.

There weren’t enough bits for jump instructions, but I did a hack: I incremented the instruction address half way through the instruction cycle. This way, you could read the bits of the next instruction while you were still executing the current instruction. So you could do an unconditional jump by placing the target in the next instruction. There still weren’t enough bits for a conditional jump, so the microcode address space ended up being partitioned into sixteen segments and you could only conditionally jump within the same segment. To jump between segments you had to use an unconditional jump.

I obviously had to do a complete rewrite of the microcode. My friend Bob Baldwin helped me out by writing an assembler for the new microinstruction format.

The new microcode ran substantially faster than the original. When the contest came, my machine was clearly faster than the competition. Unfortunately, it crashed on the third benchmark and I ended up disqualified. I think it was a bug involving switching between the segments of microcode, but I never had the opportunity to debug it fully. I learned a hard lesson about keeping things simple.

Joe MarshallMaybe machine

· 29 days ago

When I took 6.004, Computation Structures, we built the “Maybe” machine, a pedagogical microcomputer made from discrete TTL. It had no CPU. It had no ALU. It had a shift register. The microcode could load the shift register from memory, test the low bit, shift the register, and store the register to memory. That was it. It was universal (Turing complete), but it was primitive. If I recall correctly, Steve Ward, Chris Terman, and Dan Nussbaum designed it.

We each built our own Maybe machine on a “nerd kit” — a large briefcase/small suitcase with a power supply, some solderless breadboards, some switches and LEDs, and a bunch of TTL chips. We had to wire up the chips ourselves. I was maybe a bit anal about wiring it up. I color coded the wires, made neat right angle bends, and ran the wires in parallel in the troughs between the breadboards. But when it came to testing the gates, this made it easier to find the wires that had ended up in the wrong place.

When we were building it, we had a test PROM with microcode that would just exercise the logic gates. It had no functional program in it. If the gates were wired correctly, certain patterns would appear on the LEDs.

At last I had it all wired up. Each gate responded appropriately to the test PROM. I double checked to make sure I ran each and every test. I was ready to try the real microcode now. I put my EEPROM under the UV light to erase it, and then programmed it with the microcode. I verified that the PROM contained the correct bits. I popped the PROM into the socket, and powered up the machine. Nothing. The machine did not display the expected pattern of LEDS. It didn’t display anything. Crap.

I erased the EEPROM and reprogrammed it as a test PROM again. I ran all the tests to find which one was failing. All passed. I ran them again. Everything checked out. I started to think maybe a loose wire? I ran the tests again and wiggled the wires. The tests still passed.

Confused, I erased the EEPROM and reprogrammed it with the microcode. I put it back in the Maybe machine and powered it up. Nothing. I was stumped. I had no idea what was wrong. I tried wiggling the wires. I tried wiggling the chips. Nothing.

I reprogrammed the test PROM. Each reprogramming of the test PROM took at least 15 minutes as I waited for the UV light to erase the old program and then wrote in the new one. I verified one last time that all the tests ran correctly and went to consult the TA.

The TA had heard it all before. Some freshman can’t follow instructions, wires it up wrong, and is sloppy about running the tests. He was going to demonstrate the right way to thoroughly test the machine. He had a checklist of each and every test. He was going to exhaustively go through the checklist and tally each one as he went. He was going to show me how to do it right.

He was a little surprised that he didn’t find the problem right away. As each test passed, be became more and more puzzled. Finally, he got to the end of his checklist and every test had passed. So he programmed the microcode into the EEPROM and powered up the machine. Nothing.

Ok, it was a challege. The machine made him look foolish in front of this lower classman. He was going to find the problem. He reprogrammed the test PROM and ran the tests again. As he ran each test, he’d wiggle the wiring and the chips involved in the functional unit being tested. Everything was in order. But when he put in the microcode ROM, everything was dead.

We went through a couple of cycles of this, but it was getting to be dinner time so we decided to call it a night. I could only think that I was going to have to rewire the whole thing from scratch. I was dreading it. I headed back to my dorm room.

But...

It was odd that when you tried to run the microcode, although you didn’t get the expected pattern of LEDs, they did briefly flicker when you powered up the machine. The instruction after loading the LEDs was a conditional branch to itself. The LEDs would be loaded and then stay on until the conditional became true when the user pressed a button. It was almost as if the conditional was taken immediately rather than waiting for the button press. Maybe the conditional was backwards? If the conditional were backwards, the LEDs would flicker because they’d be loaded and the mahine would immediately branch.

When I got to my dorm room, I opened the nerd kit and checked. Sure enough, the conditional was wired to the inverted output of a flip-flop. Every conditional branch would be taken the wrong way. The non-inverted output was the next hole over. The test PROM checked that the wire was connected, but didn’t check that it was connected to the positive sense of the conditional bit.

The next day, I went back to the lab with the fix. I reprogrammed the EEPROM with the microcode and powered up the machine. The LEDs lit up in the expected pattern and the machine ran as expected.

Tim BradshawMonochrome

· 29 days ago

Or, why limitations matter.

After we released Štar, my friend Zyni had a rather distressing and inconclusive exchange with someone on reddit. Apart from making me feel even better about walking away from reddit a decade and more ago, I realised an interesting thing when talking to her about her experience.

Limitations

Here are some curious things that people do.

  • Why, in 2024, would anyone use a digital camera which can only make monochrome pictures?
  • Why, in 2024, would anyone use a film camera?
  • Why, in 2024, would anyone record music in a studio which uses tape?
  • Why, in 2024, would any guitarist use a collection of flaky old FX pedals connected by noisy and unreliable cables, and a valve amplifier which occasionally catches fire1?
  • Why, in 2024, would anyone shoot a movie on film?

Yet people do all these things: there are at least two manufacturers of dedicated monochrome cameras, and you can pay to have your colour digital camera converted to monochrome by removing the filter array; many people use film; studios which use tape still exist and probably are becoming more common; too many guitarists to count use elderly FX pedals, a nest of cables and a valve amplifier; many very famous recent movies have been made on film.

There is, of course, a lot of myth and lore about the special magic properties of these things: people go on endlessly about how monochrome digital sensors have more effective resolution than Bayer sensors, as if anyone needs more resolution today, or how the effective sensitivity is higher, as if anyone needs more sensitivity today. The same for film (no, it’s not magic, no, it’s not somehow better than digital in any objective way), analogue recording, old FX pedals and amplifiers, and movies made on film. If you really think movies made on film are somehow better or ‘more natural’, watch The Holdovers, which was shot digitally but is a really beautiful simulacrum of what movies looked like in about 1972.

The awful truth is that none of these technologies get you anything objectively better, even if what you want to do is reproduce what people did when those technologies were all there was. You can simulate film so well it is impossible to tell the difference, you can simulate analogue tape just as well. Modern digital FX/amplification systems for guitar are a wonder. You can produce really beautiful monochrome images from colour files.

So why, really, do people do these things?

The clue, for me, is in the first one: why would anyone use a dedicated monochrome digital camera? Why would I use one if I could afford to? The answer, for me and others, is because it restricts what you can do. If your camera will only do monochrome, then that’s all you can do, and somehow that matters. I can’t afford a monochrome-only digital camera, but I do use a digital camera which has a monochrome-only workflow (this is why I bought it, in fact): the camera sets a ‘monochrome’ flag in its files which the raw-conversion tool understands, and unless you work hard you never see a colour version of the photographs you’ve taken. And this matters to me: it needs to be difficult to overcome the limitation, so I can think in monochrome2.

And of course I use film as well, and mostly black and white film with some recent excursions into colour reversal (slide) film. Partly I do this because I enjoy working in the darkroom and the tactile quality of film cameras from the 1980s and before, but more important, I think, is how limiting film is. Once you’ve taken a picture, it’s there: you can’t chimp and decide to do it again. You have 36 (or 10, or 1) exposures before you have to change film: every frame matters. Film can’t see in the dark. Mostly it can’t even see in colour (reversal film is now absurdly expensive). 35mm film is always going to have grain. Making photographs using film is a festival of limitations.

It turns out that, for many people, limitations matter. If you take them away, then suddenly you can do anything. So you spend your time fiddling with the parameters of what you can do, and doing nothing as a result, rather than being forced to pull your finger out and do something.

That’s why many people make photographs with monochrome cameras, or on film. That’s why people still make movies on film. That’s why people paint or draw, rather than using some vast digital image-creation system. That’s why people write books on typewriters, or with a pen. That’s why Colin Chapman designed cars the way he did, and why more than 160 companies have made (and still do make) replicas of one of his designs.

Not everyone: not even most people. But some people. Enough people.

And it’s not enough to simply say ‘I won’t use all the features I do not want’: those features need not to be there. Using a camera which can only make monochrome images is not like using a camera which can make colour images but choosing not to. Choosing not to chimp is not like being unable to chimp. Using a film camera is not like using a digital camera and film simulation. Drawing with a pencil on paper is not like using a drawing program but choosing only to use the pencil tool, however good that tool is. Limitations have to be, well, limitations. I don’t know why this is, but they do.

Štar

And that’s why Štar exists: because it’s limited, because it does one thing. Because there is as little syntax as we could make there be. In Štar everything is an iterator3 so any expression like

(for ((<var/s> <iterator>))
  ...)

can be turned into

(multiple-value-bind (v c) <iterator>
  (for ((<var/s> (values v c)))
    ...)

And it will mean exactly the same thing, although often it will be slower4. And all clauses are like that. There is only one case: the form on the right-hand side of a clause is a perfectly general expression evaluated, once, in the way you think it will be. There is no magic syntax, at all. And because Štar does only one thing — iterate — it forces you to use other tools to do other things, and to make sure all these tools compose well with each other. There was once a famous operating system whose designers played the same trick.

Richard Gabriel’s famous essay, usually known as Worse is better, is celebrated for describing the difference between right thing systems and worse is better systems5. It is less celebrated for another distinction it made amongst the right thing systems. That distinction is between big complex systems and diamond-like jewel systems:

The big complex system scenario goes like this:

First, the right thing needs to be designed. Then its implementation needs to be designed. Finally it is implemented. Because it is the right thing, it has nearly 100% of desired functionality, and implementation simplicity was never a concern so it takes a long time to implement. It is large and complex. It requires complex tools to use properly. The last 20% takes 80% of the effort, and so the right thing takes a long time to get out, and it only runs satisfactorily on the most sophisticated hardware.

The diamond-like jewel scenario goes like this:

The right thing takes forever to design, but it is quite small at every point along the way. To implement it to run fast is either impossible or beyond the capabilities of most implementors.

The two scenarios correspond to Common Lisp and Scheme.

Štar aspires to be the diamond-like jewel of iteration frameworks. Its interface is tiny: org.tfeb.* exports six symbols, four of which could be removed with no loss of functionality6. But it aims to be general and to be able to turn this clean, minimal syntax into fast code: apart from the catalogue of built-in iterators, almost all the rest of the interface is to the tools that let you do this for your own iterators.

It may seem odd that Štar is written in Common Lisp, not Scheme, but CL is what we actually use and so producing tools which turn CL into the system we’d like to have is what we care about. In my case, I also remember the movement to reexpress CL as a small core language combined with libraries.

Štar is not for everybody. If you like loop you probably will hate it (but you have no taste, so we don’t care). If you are an adherent of the big complex system school you probably won’t like it either (and we respect your opinion). That’s not who Štar is for: Štar is for the people who appreciate the diamond-like jewel, who believe that limitations matter, in a deep way.

If that’s not for you, that is completely fine: not everybody is the same: not everyone wants a monochrome camera, and not everyone knew, or liked if they did know, that famous operating system7. Some people even like loop, apparently. But understand that it is for some people, and try to avoid sneering at them, if you can.


  1. Well-maintained valve amplifiers hardly ever catch fire. Often they are also electrically safe. 

  2. Why a photographer or a movie maker would want to work in monochrome is another, related question: why, in 2024, intentionally throw away all the colour information in a scene? 

  3. In this way, Štar is like some Scheme compilers which turn everything into \(\lambda\) expressions and then try to make those expressions quick. 

  4. One of the things Štar’s tests do is exactly this transformation as a way of testing that iterator optimizers do not change the semantics of the program. 

  5. Entertainingly, that famous operating system is often disparaged as an example of worse is better. In terms of its implementation that may be justified: its ideas are certainly not examples of worse is better. 

  6. We have argued, at length, about this. We decided that, just as Scheme includes let and, even more extravagantly, let*, Štar should include final, for* and final*. In the language of the Scheme reports, they are library syntax (for*) and library procedures (final, final*, next* which serves no purpose without for*). 

  7. There’s a book about that. 

Joe MarshallReadability at Google

· 33 days ago

Over the years I was a developer at Google I never once tried to pass “readability” for any language. If you didn’t have “readability”, then any code you checked in would need an additionally review by someone who did have “readability”. The theory was that the code base would turn into an unreadable patchwork of different styles if everyone didn't adhere to the same set of rules. By having a “readability” requirement, the code base would be uniform and understandable. In practice, however, it was a social signal that indicated whether you were a card carrying member of the “in” group or not. Having “readability” meant you were a nobleman. Not having it meant you were a commoner.

To get “readability” you had to endure a struggle session with a current holder of “readability”. You would submit a not insubstantial amount of code for review and the reviewer would go over it with a fine-tooth comb pointing out every little syntactic rule you broke. It was a game of gotcha designed to make the reviewer feel smarter than you. You’d then return to your office or cubicle, make changes and iterate. If you were lucky, you would only need two or three iterations before you were bestowed with “readability”. The point was not to demonstrate that you knew how to write readable code, but to demonstrate that you were willing to submit to the authority of the reviewer and follow a set of arbitrary rules, no matter how absurd. It was a hazing ritual, a way to show that you were willing to be a team player.

A problem with having “readability” was that you were expected to uphold the “readability” guidelines. Not only did you have to play the game, you had to perpetuate it. I disagreed with a lot of the guidelines because they were poorly thought out rules for the sake of having rules. There were many situations in which they would reduce the comprehensibility of the code. By not having “readability”, I was free to write code that was easier to understand and maintain, even if bent or broke the codified rules.

This isn’t to say that I ignored Google’s style. It is hard to understand code that switches styles every few lines. I tried to make my code fit in to the surrounding code and look like it was part of it. I wrote new files with same general layout, curly brace conventions, and indentation that a typical Google file has. I didn’t worry about following “readability” guidelines at all, but I didn’t flout the guidelines either. I more concerned about my code being comprehended by the next developer than following a set of ad hoc rules to the letter.

So I got used to submitting my code for “readability” review, in addition to the normal code review. I off-loaded the entire responsibility of “readability” to the reviewer and let them tell me what to do. I didn’t argue with them. I simply followed the directions of the reviewer and made whatever changes were suggested. Often, though, changes to the code to more strictly follow the guidelines would result in noticeably worse code and the reviewers would soon withdraw their suggestions.

Another problem of being a nobleman with “readability” is that you had the obligation to review the code written by the commoners. The people with “readability” was a small enough group that they soon became the bottleneck in the review process. They were constantly overworked with code reviews. We commoners, on the other hand, weren’t expected to review code. Nor were we to blame if someone else is holding up the code review.

Frankly, I didn’t see any upside of having “readability” and many downsides. I was able to get my code checked in without too much trouble and I just didn’t have the time or inclination to get involved in the high-school politics of “readability”. Plenty of other companies do not have a “readability” ritual. They seem to get along just fine by hiring people who can write code that is easy to understand and maintain.

Tim Bradshaw&#352;tar: an iteration construct for Common Lisp

· 34 days ago

Štar is a concise and extensible iteration construct for Common Lisp which aims to be pleasant to use, easy to understand, fast if needed, general, and not to look like Fortran.

Common Lisp has multiple iteration constructs: mapping functions such as mapcar, special-purpose constructs such as dotimes and dolist, the general but somewhat clumsy construct which is do and do*, and finally the extended loop macro which aims to embed a ‘more friendly’ iteration language into CL and succeeds in being so complex that it is often hard to know whether a given form is legal or not without poring over loop’s grammar.

None of these constructs manage to be all three of pleasant to use, easy to understand and general. loop somehow fails to be any of these things in many cases. None are extensible1.

But Common Lisp is a Lisp, and Lisp’s huge advantage is that it is a programming language in which it is easy to write programming languages, or parts of them, like iteration constructs. That is, after all, how most or all of the existing constructs started life.

Lots of these have been written, of course. Štar tries to distinguish itself by being as simple as possible: it has as little special syntax as I could work out how to give it - there is no special little language you need to learn. It also has no inherent knowledge about how to iterate over any particular structure: it doesn’t know how to iterate over lists, or ranges of numbers. Rather it knows that iterating has to answer two questions:

  • is there more?
  • what is the next thing?

In addition it knows how to ask another question:

  • is there any information I can use to make asking the first two questions faster?

What it looks like

(for ((e (in-list l)))
  (print e))

(for (((k v) (in-hash-table h)))
  ...)

(for* ((entry (in-list entries))
       (element (in-list entry)))
  ...)

(defun in-alist (alist)
  (values
    (lambda () (not (null alist)))
    (lambda ()
      (destructuring-bind ((k . v) . more) alist
        (setf alist more)
        (values k v)))))

(for (((k v) (in-alist ...)))
  ...)

These are some simple examples: the last shows how easy it is to teach Štar to iterate over new things, or over existing things in new ways. Not shown here is that it’s also pretty easy to teach it how to optimize new iterators and to make various declarations about things.

What Štar is not

Štar is an iteration construct: what it does is to iterate. It has nothing to do with collecting values. For Štar, iteration and value accumulation are orthogonal problems which should be solved by orthogonal constructs. In particular if you wanted to make a list of the even numbers from a list, you might to this by using Štar together with a value-collection macro:

(collecting
  (for ((e (in-list ...)))
    (when (evenp e)
      (collect e))))

This is yet another way in which Štar differs from loop and many other constructs. In particular Štar’s point of view is that mixing together iteration and value accumulation results in a system that is not very good at either.

Similarly, Štar doesn’t contain a mass of syntax letting you select only certain values, or allowing you to terminate iteration early: you don’t write

(loop for x in l while (numberp x) do ...)

Instead you write

(for ((x (in-list l)))
  (unless (numberp x) (final))
  ...)

The body of an iteration is exactly like the body of defun, except there are some local functions which you can call to skip to the next iteration or finish the iteration.

Štar, of course, doesn’t bundle some destructuring system which will inevitably be subtly incompatible with other destructuring systems while also not being usable independently. If you want destructuring, use a full-fat system of your choice.

You probably get the idea: Štar is a tool whose job is to iterate: not some leaking bag of broken abstractions.

Multiple values

One thing that Štar does do is to take multiple values seriously. A clause which specifies a list of variables will bind them to the multiple values returned by the iterator. Multiple values, unlike destructuring, are something you really have to have in the iteration construct itself.

The thing that doesn’t really matter but everyone cares about

So, OK, Štar is an extensible, general, iteration construct. Obviously it will have traded performance for all this. I mean, it’s the old Lisp story, the one Gabriel told us long ago. Right?

* Running benchmarks
** lists of length 2000, nesting 3
what                                                  seconds      ratio
star                                                   30.312      1.000
loop                                                   30.071      0.992
dolist                                                 21.594      0.712
** range 100000, nesting 2
what                                                  seconds      ratio
star/with-step                                          9.414      1.000
star/no-step                                            9.406      0.999
loop                                                   18.412      1.956
dotimes                                                 9.469      1.006

A sketch of Štar

Štar has three parts, four if you count the iterators:

  • the iteration constructs themselves and bindings they make;
  • a protocol for defining new iterators;
  • a protocol for defining optimizers for iterators;
  • a collection of predefined iterators and optimizers for them.

The first three parts are much more finished than the fourth: most of the existing iterators were written as proofs of concept and may well change, get better, or go away.

Iterators

These are forms (usually, named function calls) which return two values, both functions of no arguments:

  • the first value is called and should return true if there is more to do;
  • the second value is called to return the next value or values of the iterator.

These functions answer the first two questions Štar needs to ask: is there more, and if there is, what is it? These two functions obviously share state in general.

To answer the third question - how do I make things faster? - named iterator functions can have optimizers: these are functions called by Štar at macroexpansion time which tell it how to make things faster. It’s up to an optimizer to ensure the semantics are the same for the optimized and unoptimized versions. Optimizers can specify a set of bindings to make, declarations for them, how to iterate, and some other things.

It’s possible to install and remove optimizers, and to dynamically bind sets of them. This might be useful, for instance, to compile a file where some particular assumptions (‘all vectors are vectors of floats’) are true.

Iteration constructs

There are two:

  • for iterates in parallel;
  • for* defines nested loops: (for* ((...) (...)) ...) is like (for ((...)) (for ((...)) ...)).

Note that because of the way iterators work, sequential binding within one loop makes no sense.

The first argument of for or for* specifies a number of clauses: each clause is of the form <var/s> <iterator>). Multiple values are supported, and it is possible to make various declarations about variables: this matters for for*, where there is no room for declarations for other than the last (innermost) clause. Variables whose name is "_" are ignored by default.

Within the body of an iteration there are four local functions:

  • next skips to the next iteration;
  • next* skips to the next outer-level iteration for for* and is the same as next for for;
  • final returns zero or more values from the current iteration
  • final* returns zero or more values for the outer-level iteration for for* and is the same as final for for.

Provided iterators

There are iterators which work for lists, vectors, general sequences, hash tables, ranges of reals, as well as some more interesting ones. Not all iterators currently have optimizers. You only need to care about writing optimizers if you need to make iterators very fast: they can be significantly fiddly to write.

The iterator over ranges of reals has an optimizer which tries hard to make things pretty fast.

As well as this there are some more interesting iterators. An example is sequentially:

(for ((a (sequentially 1 2)))
  ...)

will bind a sequentually to 1 and 2. But this iterator is a macro which has the behaviour of a FEXPR, so it evaluates its arguments only when needed (and as many times as needed). A variant of sequentially is sequentially* which ‘sticks’ on its last argument. So for instance:

> (let ((v 0))
    (for ((a (sequentially* (incf v)))
          (_ (in-range 3)))
      (print a)))

1 
2 
3 

Another way to write this is:

> (for ((a (let ((v 0)) (sequentially* (incf v))))
        (_ (in-range 4)))
    (print a))

1 
2 
3 
4 

And of course there is a meta-iterator (also implemented as a macro), in-iterators:

> (for ((a (in-iterators
            (in-list '(1 2))
            (in-list '(3 4)))))
    (print a))

1 
2 
3 
4 

It’s possible to construct very general iterators with tools like this.

As I said above, Štar’s current iterators are in a fairly rough state: a lot of this might change.


Notes

Declarations

A form like

(for* ((a (in-range 10))
       (b (in-range 10)))
  ...)

corresponds roughly to

(for ((a (in-range 10)))
  (for ((b (in-range 10)))
    ...)

The problem is now how to make declarations which apply to a. This is hard because CL doesn’t provide the tools you need to know whether a declaration refers to a variable or not: to know whether (declare (foo a)) refers to a or not you need to know, at least, whether foo names a type, which you can’t do. You often can guess, but not always.

So, rather than trying to solve an intractable problem, Štar lets you specify some properties of a variable in the clause that binds it: you can say

(for* (((a :type fixnum) (in-range 10))
       (b (in-range 10)))
  ...)

for instance. This is a bit ugly, but it solves the problem. It is only useful for for*.

Binding

Štar binds, rather than assigns:

(collecting
  (for ((a (in-list 1 2)))
    (collect
      (lambda (&optional (v vp))
        (if vp (setf a v) a)))))

will return two closures over independent bindings.

Epilogue

Štar’s source code is here. The manual is included with the source code but also here.

Štar is pronounced roughly ‘shtar’.

Much of the inspiration for Štar came from my friend Zyni: thanks to her for the inspiration behind it, actually making me write it and for many other things.

Štar is dedicated to her, and to Ian Anderson.


  1. Some implementations have mechanisms for extending loop

Paolo AmorosoInsphex, a hex dump tool in Medley Common Lisp

· 38 days ago

I'm developing the new program Insphex (inspect hex), a hex dump tool that is created with and runs on the Medley Interlisp environment.

Similarly to the Linux command hexdump, it shows the contents of files as hexadecimal values and the corresponding ASCII characters. An early version of the program prints the hex dump to the standard output like this.

Output of the Insphex hex dump tool for Medley Interlisp.

I plan to enhance Insphex to optionally display the dump in a separate window one page at a time. An attached menu will have options for showing the next page and exiting. I'll also provide an Exec command for running the program.

The code is in Common Lisp but will include some Interlisp to access the required system functionality.

Although Insphex is useful in itself, I have three main goals for it. First, I want a real project to practice the process for writing Common Lisp with the residential environment of Medley. This is the native way of coding on Medley and takes full advantage of its development environment and features such as the File Manager and the SEdit editor.

Most Medley tools and facilities are written in Interlisp or expose Interlisp APIs through which the functionality can be invoked. So another goal is to interface with Interlisp from Common Lisp to access the functionality I need like windows and menus.

My third goal is to experiment with displaying textual output in TEdit, the Medley word processor where the hex dump will optionally go.

Although the Interlisp API of TEdit supports advanced editing and formatting, Insphex does only basic text output. The primary feature I want is TEdit's ability to automatically handle repainting the window after it's resized or a hidden portion is exposed. This is handy as by default Interlisp windows mostly don't handle the repaint.

Now that the basic functionality of Insphex is in place I will implement displaying the hex dump in a TEdit window.

#insphex #CommonLisp #Interlisp #Lisp

Discuss... Email | Reply @amoroso@fosstodon.org

Joe MarshallThe Way of Lisp or The Right Thing

· 39 days ago
Interpreting Richard Gabriel with a nod to Tim Peters

Keep it simple.
A simple interface is better than a simple implementation.
Complete is better than simple.
Consistent is better than complete.
Correctness trumps all. Incorrectness is simply not allowed.
If the interface is hard to use, it is probably a bad idea.
If the interface is easy to use, it may be a good idea.
A weak language makes it hard to write good code, but a powerful language makes it easy to write bad code that looks good.
The first thing that comes to mind is not always the best thing.
When performance matters, get your declarations right.
There is always another way to do it, and maybe a better one.
Lists aren’t the only data type.
The right thing and 2 shillings will get you a cup of tea.

Marco AntoniottiELS 2024 in Vienna

· 41 days ago

I just got back from the 2024 European Lisp Symposium in Vienna. After many years it was good to meet again in person with so many talented and interesting people (all interested in parentheses).

Many, many thanks to Beppe Attardi, Philipp Marek, Georgiy Tugai, Yukari Hafner, and, especially, Didier Verna, for pulling this together.

Joe MarshallMotion without Integration

· 43 days ago

A game where things move around has equations of motion that describe how objects move. We need to solve these to produce the locations of the objects as a function of time, and we have to do it in lock step real time. Fortunately, we usually don’t need highly realistic models or highly accurate results. Game phyiscs, while inspired by real world physics, can be crude approximations.

If the velocity of an object changes over time, we need to integrate the velocity to determine the position. This is typically done with forward Euler integration: the current velocity is multiplied by a small Δt and this is added to the current position. In other words, we assume the object moves linearly over the amount of time represented by Δt. If Δt is small enough, the linear segments of motion will approximate the actual curve of motion.

In a game, we use the game loop, which runs every few milliseconds, as our source of time. We subtract the current time from the previous time the game loop was run to obtain our Δt. We update each object’s state using forward Euler integration over Δt.

Our game loop keeps track of the last time it was run and subtracts that from the current time. It runs entity-step! on each entity in the game, passing in dticks.

(let ((start-tick (sdl2:get-ticks)))
  (let ((last-tick start-tick))
    (loop
      (let* ((tick (- (sdl2:get-ticks) start-tick))
             (dticks (- tick last-tick)))
        (map nil (lambda (entity)
                   (entity-step! entity dticks))
                 entities)
        (setq last-tick tick)))))

entity-step! performs our forward Euler integration:

(defun entity-step! (entity dticks)
  (incf (position entity) (* (velocity entity) dticks)))

Assuming the game loop runs reasonably frequently, the position of the entity will be a reasonable approximation of the integral of the velocity. If the game loop gets delayed for some reason, e.g. garbage collection, the corresponding increase in the value of dticks will make up for it.

But sometimes we have the fortune of having a closed form solution to the time integral. If this is the case, we can compute the entity’s state directly and we don’t need to integrate the state changes on every iteration of the game loop. Let me give two examples.

In the platformer game, there are potions that the player can take to restore his health. A potion appears as a vial that floats above the ground. A “bobbing” effect is achieved by changing the height above the ground in a time varying manner. Now we could implement this by having the game loop modify the y position of the potion on each iteration, but there is a closed form solution. We can compute the y position at any time by adding a constant base y position to a factor of the sine of the current time. This is easily done by specializing the get-y method on potions:

;;; Make potions bob up and down.
(defmethod get-y ((object potion))
  (+ (call-next-method)
     (* 5 (sin (* 2 pi (/ (sdl2:get-ticks) 1000))))))

call-next-method invokes the next most specific method — in this case, the get-y method of the entity class, which returns the base y position. We add a sine wave based on the current time.

This is only thing we need to modify to make a potion bob up and down. Values dependent on the y position, such as the attackbox, will bob up and down with the potion because it uses the get-y method to determine what the potion is.

A second example is cannonball motion. Cannonballs travel linearly away from the cannon at a constant velocity. Rather than stepping the cannonball by adding its velocity to its position on each update, we specialize the get-x method on cannonballs

(defmethod get-x ((cannonball cannonball))
  (+ (call-next-method)
     (* (get-speed cannonball)
        (- (sdl2:get-ticks) (get-start-tick cannonball)))))

If we specialize both the get-x and get-y methods we can easily get objects to trace out any desired parametric curve, like a Lissajous figure.

Joe MarshallAnimation: Two Methods

· 44 days ago

Animated sprites are much cooler that static ones and really make your game come to life. They are pretty easy to implement, but there are a couple of ways to implement them, and I've seen several projects use the less optimal strategy.

The less optimal strategy is straightforward. We keep a time counter in the animated entity and increment it every time we update the entity. When the counter exceeds the amount of time for an animation frame, we advance to the next frame and reset the ticker.

(defclass entity ()
  ((animation-ticker :initform 0 :accessor animation-ticker)))

(defun entity-step! (entity dticks)
  (incf (animation-ticker entity) dticks)
  (when (> (animation-ticker entity) ticks-per-frame)
    (advance-to-next-frame! entity)
    (decf (animation-ticker entity) ticks-per-frame)))

Now this works, but the reason it is less optimal is that it involves maintaining time varying state in the entity. Recall that the game has two primary threads running: a render thread which runs 60 times a second and draws the game on the screen, and an game loop thread which runs maybe 200 times a second and updates the state of the entities in the game. The point of this is to separate and abstract the drawing of the game from the running of the mechanics of the game. By using this less optimal method, we involve the game loop thread in maintaining state that is used only by the render thead. To anthromorphize, the entity “knows” that it is animated and is taking an active role in keeping things moving.

A better way is to put the responsibility of animation solely within the render thread by having it select which animation frame to display when it draws the sprite. The sprite contains a vector of animation frames and a timestamp at which the animation was started. When redrawing the sprite, the elapsed time is computed by subtracting the start timestamp from the current time, and the frame to display is computed by dividing the elapsed time by the time per frame modulo the length of the frame vector.

(defclass animation ()
  ((start-tick :initform (get-ticks) :reader start-tick)
   (frames :initarg frames :reader frames)))

(defun display-animation! (animation)
   (let* ((elapsed-time (- (get-ticks) (start-tick animation)))
          (absolute-frame (floor elapsed-time ticks-per-frame))
          (frame (mod absolute-frame (length (frames animation)))))
     (display-frame! (svref (frames animation) frame))))

This way of doing it no longer needs time varying state, and we’ve abstracted the display of the animation from the handling of the entity’s state. The entity no longer has to “know” that it is animated or do anything about it. There no longer has to be communication between the game loop thread and the render thread on every animation frame. This could be important if the render thread is running on a different machine than the game loop thread. If the game loop thread lags (maybe because of garbage collection or entering the error handler), we still get smooth animation.

Joe MarshallStatements and Expressions

· 49 days ago

In some languages, like Lisp and OCaml, every language construct is an expression that returns a value. Other languages, like Java or Python, have two kinds of language constructs: expressions, which combine compositionally and which have return values, and statements, which combine sequentially and which have no return values and thus must operate by side effect. Having statements in your language needlessly makes things more complicated, but language designers seem to want to go much further and add complexity that just seems capricious.

You cannot usually use a statement in a context where an expression is expected because there is no return value. You can use an expression where a statement is expected by simply discarding the return value. This means there are two kinds of contexts. A sane designer would provide a way to switch between statement and expression contexts, but language designers typically omit these.

Language constructs, such as binding or iteration, must be provided as statements or expressions or both. Language designers seem to randomly decide which constructs are statements and which are expressions based on whims and ease of compiler implementation. If you need to use a construct, but aren’t in the right kind of context, you need to switch contexts, but without a way to do this, you may have to rewrite code. For example, if you have a subexpression that could raise an exception that you want to handle, you’ll have to rewrite the containing expression as a series of statements.

A sane language designer would use the same syntax for the same construct in both expression and statement form, but typically the construct will have a very different syntax. Consider sequential statements in C. They are terminated by semicolons. But sequential expressions are separated by commas. Conditional statements use if/else, but conditional expressions use ?:. When refactoring, you cannot simply move code between contexts, you have to change the syntax as well.

Writing a function adds a new expression to the language. But function bodies aren’t expressions, they are statements. This automatically destroys referential transparency because you cannot substitute the function body (statements) at the call site (expression context).

try/catch is a nightmare. Usually you only get try/catch as a statement, not an expression, so you cannot use exception handling in a subexpression. You cannot get a value out of a try/catch without a side effect. Throw, on the other hand, throws a value, so it could throw to an expression context, except that catch is a statement.

Having two kinds of language constructs and two different contexts in which you can use some of them but not others, and different syntaxes depending on the context just makes it that much more difficult to write programs. You have to keep track of which context is current and which syntax to use and constantly switch back and forth as you write a program. It would be easy for a compiler to introduce the necessary temporaries and rewrite the control flow so that you could use all language constructs in either context, but language designers don’t bother and leave it up to the programmer to do it manually.

And all this mess can be avoided by simply making everything be an expression that returns a value.

Eugene ZaikonnikovThe World's Loudest Lisp Program to the Rescue

· 49 days ago

It is interesting that while I think of myself as a generalist developer the vast portion of my career has been towards embedded and systems programming. I'm firmly a Common Lisp guy at heart but embedded tech landscape is the entrenched realm of C sprinkled with some C++ and nowadays Rust. However I had incredible fortune to work for the last few years on a substantial embedded system project in Common Lisp.

The story starts in Western Norway, the world capital of tunnels with over 650 located in the area. Tunnels are equipped and maintained to high standard and accidents are infrequent but by the nature of quantities serious ones get to happen. The worst of these are naturally fires, which are notoriously dangerous. Consider that many of single bore tunnels have length over 5km (and up to 24km). Some of them are undersea tunnels in the fjords with inclination of up to 10 degrees. There are no automatic firefighting facilities. These are costly both in installation and maintenance, and while they might work in a country with one or two tunnels total they simply do not scale up. Hence the policy follows the self evacuation principle: you're on your own to help yourself and others to egress, hopefully managing to follow the signage and lights before the smoke sets in and pray the extractor fans do their job.

Aftermath of a fire

So far Norway have been spared of mass casualty tunnel fires but there have been multiple close calls. One of particularly unlucky ones, the 11.5km long Gudvangatunnelen had experienced three major fires in span of a few years. Thus national Road Administration put forth a challenge to develop a system to augment self-assisted evacuation. Norphonic, my employer, had won in a competition of nine contenders on the merits of our pre-existing R&D work. In late 2019 the project has officially started, and despite the setbacks of the pandemic concluded in 2021 with series production of the system now known as Evacsound. The whole development on this project was done by a lean team of:

  • software engineer who could also do some mechanical design and basic electronics
  • electrical engineer who could also code
  • two project engineers, dealing with product feasibility w.r.t. regulation and practices, taking care of SCADA integration and countless practicalities of automation systems for tunnels
  • project coordinator who communicated the changes, requirements and arranged tests with the Road Administration and our subcontractors
  • logistics specialist ensuring the flow of scores of shipments back and forth on the peak of pandemic

Live hacking Wesley, our EE patching up a prototype live

Atop of this we were also hiring some brilliant MEs and EEs as contractors. In addition two Norway's leading research institutes handled the science of validating psychoacoustics and simulating fire detection.

At this point the system is already installed or is being installed in 6 tunnels in Norway with another 8 tunnels to some 29km total on order. We certainly do need to step up our international marketing efforts though.

In the tunnels

The Concept

How do you approach a problem like this? The only thing that can be improved under self-evacuation is the flow of information towards people in emergency. This leaves us with eyesight and hearing to work with. Visual aids are greatly more flexible and easy to control. However their huge drawback is their usefulness expires quickly once the smoke sets in.

Sound is more persistent, although there are numerous challenges to using it in the tunnels:

  • The background noise from smoke extraction fans can be very high, and if you go for speech the threshold for intelligibility has to be at least 10dB over the noise floor
  • Public announcement messages alone are not very efficient. They are great in the early phase of fire to give heads up to evacuate, but kind of useless once the visibility is limited. At that point you also know you are in trouble already.
  • Speech announcements rely on comprehension of the language. In one of Gudvangatunnelen fires a bus full of foreign tourists who spoke neither English nor Norwegian had been caught in the thick of it. Fortunately a local lorry driver stopped by to collect them.
  • Acoustic environment in tunnels ranges from poor to terrible. Echo of 4-5 seconds in mid-range frequencies is rather typical.

In addition to above, the system should have still provided visual clues and allow for distributed temperature sensing for fire detection. It has also to withstand pressure wash along the tunnel wall, necessitating IP69 approval. On a tangent IPx9 is 100 bar 80C water jet pressure at 18 cm distance for 3 minutes, so Evacsound is of the most water protected speaker systems in the world.

We decided to start our design from psychoacoustics end and see where it falls for the rest. The primary idea was to evacuate people by aiding with directional sound signals that propagate towards the exits. The mechanism was worked out together with SINTEF research institute who conducted live trials on general population. This method was found effective, with over 90% of tests participants finding the way out based on directional sound aids alone. A combination of sound effect distance requirements and technical restrictions in the tunnel has led us to devices installed at 3m height along the wall at 25m intervals. Which was just as well, since it allowed both for application of acoustic energy in least wasteful, low reverberation manner and provided sensible intervals for radiated heat detection.

Node dissected

A typical installation is a few dozen to several hundred nodes in a single tunnel. Which brings us to the headline: we have projects that easily amount to tens of kilowatts acoustic power in operation, all orchestrated by Lisp code.

Tech Stack

The hardware took nearly 20 design iterations until we reached what I would immodestly call the Platonic design for the problem. We were fortunate to have both mechanical and electronic design expertise from our other products. That allowed us to iterate at an incredible pace. Our software stack has settled on Yocto Linux and Common Lisp. Why CL? That's what I started our earliest design studies with initially. Deadlines were tight, requirements were fluid, the team was small and I can move in Common Lisp really, really fast. I like to think that am also a competent C programmer but it was clear doing it in C would be many times the effort. And with native compilation there's no performance handicap to speak of, so it is hard to justify a rewrite later.

Design iterations

Our primary CL implementation is LispWorks. There are some practical reasons for that.

  • Its tree shaker is really good. This allows our binaries to run on a system with 128 Mb RAM with room to spare, which at the scale of thousands devices manufactured helps keep the costs down.
  • It officially supports ARM32 with POSIX threads, something only it and CCL did at the time.
  • The garbage collector is very tunable.
  • There is commercial support available with implementors within the earshot. Not that we ended up using it much but the thought is soothing.

We however do use CCL liberally in development and we employ SBCL/x86 in the tests matrix. Testing across the three implementations has found a few quirks on occasions.

System Design

At its heart Evacsound is a soft real time, distributed system where a central stages time synchronized operation across hundreds of nodes. Its problem domain and operational circumstances add some constraints:

  1. The system shares comms infrastructure with other industrial equipment even though on own VLAN. Network virtualization abstraction breaks down in real time operation: the product has to tolerate load spikes and service degradation caused by other equipment yet be mindful of network traffic it generates.
  2. The operations are completely unmanned. There are no SREs; nobody's on pager duty for the system. After commissioning there's typically no network access for vendors to the site anyway. The thing have to sit there on its own and quietly do its job for the next couple decades until the scheduled tunnel renovation.
  3. We have experience designing no-nonsense hardware that lasts: this is how we have repeat business with Siemens, GE and other big players. But with sheer scale of installation you can count on devices going dark over the years. There will be hardware faults, accidents and possible battle attrition from fires. Evacsound has to remain operational despite the damage, allow for redundant centrals and ensure zero configuration maintenance/replacement of the nodes.

The first point has channeled us to using pre-uploaded audio rather than live streaming. This uses the network much more efficiently and helps to eliminate most synchronization issues. Remember that sound has to be timed accounting for propagation distances between the nodes, and 10 millisecond jitter gives you over 3 meters deviation. This may sound acceptable but a STIPA measurement will have no mercy. Then, the command and control structure should be flexible enough for executing elaborate plans involving sound and lighting effects yet tolerate inevitable misfortunes of real life.

The system makes heavy use of CLOS with a smattering of macros in places where it makes a difference. Naturally there's a lot of moving parts in the product. We're not going into the details of SCADA interfacing, power and resource scheduling, fire detection, self calibration and node replacement subsystems. The system has also distinct PA mode and two way speech communication using a node as a giant speakerphone: these two also add a bit of complexity. Instead we're going to have an overview on the bits that make reliable distributed operation possible.

Test of fire detection

Processes

First step in establishing reliability baseline was to come up with abstraction for isolated tasks to be used both on the central and on the nodes. We built it on top of a thread pool, layering on top of it an execution abstraction with start, stop and fault handlers. These tie in to a watchdog monitor process with straightforward decision logic. An Evacsound entity would run a service registry where a service instance would look along these lines:

(register-service site
		  (make-instance 'avc-process :service-tag :avc
				 :closure 'avc-execution
				 :suspend-action 'avc-suspend
				 :resume-action 'avc-resume
				 :process-name "Automatic Volume Control"))

...and the methods that would be able to spin, quit, pause or resume the process based on its service-tag. This helps us ensure that we don't ever end up with a backtrace or with an essential process quietly knocked out.

Plans

To perform its function Evacsound should be able to centrally plan and distributed execute elaborate tasks. People often argue what a DSL really is (and does it really have to have macros) but in our book if it's special purpose, composable and is abstracted from implementation details it is one. Our planner is one example. We can create time distributed plans in abstract, we can actualize abstract plans with specific base time for operations, we can segment/concatenate/re-normalize plans in various ways. For instance, below is a glimpse of abstract plan for evacuation generated by the system:

(plan-modulo
 (normalize-plan
  (append (generate-plan (left accident-node)
			 :selector #'select-plain-nodes
			 :time-shift shift
			 :direction :left
			 :orientation :opposite)
 	  (generate-plan (right accident-node)
			 :selector #'select-plain-nodes
			 :time-shift shift
			 :direction :right
			 :orientation :opposite)))
 (* 10 +evacuation-effect-duration+))

We can see above that two plans for each evacuation direction are concatenated then re-normalized in time. The resulting plan is then modulo adjusted in time to run in parallel subdivisions of specified duration.

Generated plans are sets of node ID, effect direction and time delta tuples. They do not have association of commands and absolute times yet, which are the job of ACTUALIZE-PLAN.

Command Language

The central and nodes communicate in terms of CLOS instances of classes comprising the command language. In simplest cases they have just the slots to pass values on for the commands to be executed immediately. However with appropriate mixin they can inherit the properties necessary for precision timing control, allowing the commands to be executed in time synchronized manner across sets of nodes in plans.

It is established wisdom now that multiple inheritance is an anti-pattern, not worth the headache in the long run. However Evacsound make extensive use of it and over the years it worked out just fine. I'm not quite sure what the mechanism is that makes it click. Whether it's because CLOS doesn't suffer from diamond problem, or because typical treatment of objects using multiple dispatch methods, or something else it really is a non-issue and is a much better abstraction mechanism than composition.

Communication

The next essential task is communication. Depending on the plan we may communicate with all or subsets of nodes, in particular sequence or simultaneously, synchronously or async, with or without expectation of reported results. For instance we may want to get a noise estimation from microphones for volume control, and that would need to be done for all nodes at once while expecting a result set or reports. A PA message would have to be played synchronized but the result does not really matter. Or a temperature change notice may arrive unprompted to be considered by fire detection algorithm.

This diverse but restricted set of patterns wasn't particularly well treated by existing frameworks and libraries, so we rolled our own on top of socket library, POSIX threads and condition variables. Our small DSL has two basic constructs, the asynchronous communicate> for outgoing commands and communicate< for expecting the result set, which can be composed as one operation communicate. A system can generate distributed command such as

(communicate (actualize-plan
	      (evacuation-prelude-plan s)
	      'fuse-media-file
	      (:base-time (+ (get-nanosecond-time) #.(2ns 1.8)))
	      :sample-rate 32000
	      :media-name "prelude"))

What happens here is that previously generated plan is actualized with FUSE-MEDIA-FILE command for every entry. That command inherits several timing properties:

  • absolute BASE-TIME set here explicitly
  • DELTA offset which is set from the plan's pre-calculated time deltas
  • TIME-TO-COMPLETE (implicit here) which specifies expected command duration and is used to calculate composite timeout value for COMMUNICATE

If any network failure occurs, a reply from the node times out or node reports a malfunction an according condition is signaled. This mechanism allows us to effectively partition distributed networked operation failures into cases conveniently guarded by HANDLER-BIND wrappers. For instance, a macro that just logs the faults and continues the operation can be defined simply as:

(defmacro with-guarded-distributed-operation (&body body)
  `(handler-bind ((distributed-operation-failure
		   #'(lambda (c)
		       (log-info "Distibuted opearation issue with condition ~a on ~d node~:p"
				 (condition-name c) (failure-count c))
		       (invoke-restart 'communicate-recover)))
		  (edge-offline
		   #'(lambda (c)
		       (log-info "Failed to command node ~a" (uid c))
		       (invoke-restart 'communicate-send-recover))))
     ,@body))

This wrapper would guard both send and receive communication errors, using the restarts to proceed once the event is logged.

So the bird's eye view is,

  • we generate the plans using comprehensible, composable, pragmatic constructs
  • we communicate in terms of objects naturally mapped from the problem domain
  • the communication is abstracted away into pseudo-transactional sets of distributed operations with error handling

Altogether it combines into a robust distributed system that is able to thrive in the wild of industrial automation jungle.

TL;DR Helping people escape tunnel fires with Lisp and funny sounds

Joe MarshallState Machines

· 54 days ago

One of the things you do when writing a game is to write little state machines for objects that have non-trivial behaviors. A game loop runs frequently (dozens to hundreds of times a second) and iterates over all the state machines and advances each of them by one state. The state machines will appear to run in parallel with each other. However, there is no guarantee of what order the state machines are advanced, so care must be taken if a machine reads or modifies another machine’s state.

CLOS provides a particularly elegant way to code up a state machine. The generic function step! takes a state machine and its current state as arguments. We represent the state as a keyword. An eql specialized method for each state is written.

(defclass my-state-machine ()
  ((state :initarg :initial-state :accessor state)))

(defgeneric step! (state-machine state))

(defmethod step! ((machine my-state-machine) (state (eql :idle)))  
  (when (key-pressed?)
    (setf (state machine) :keydown)))

(defmethod step! ((machine my-state-machine) (state (eql :keydown)))
  (unless (key-pressed?)
    (setf (state machine) :idle)))

The state variables of the state machine would be held in other slots in the CLOS instance.

One advantage we find here is that we can write an :after method on (setf state) that is eql specialized on the new state. For instance, in a game the :after method could start a new animation for an object.

(defmethod (setf state) :after ((new-state (eql :idle)) (machine my-state-machine))
  (begin-idle-animation! my-state-machine))

Now the code that does the state transition no longer has to worry about managing the animations as well. They’ll be taken care of when we assign the new state.

Because we’re using CLOS dispatch, the state can be a class instance instead of a keyword. This allows us to create parameterized states. For example, we could have a delay-until state that contained a timestamp. The step! method would compare the current time to the timestamp and go to the next state only if the time has expired.

(defclass delay-until ()
  ((timestamp :initarg :timestamp :reader timestamp)))

(defmethod step! ((machine my-state-machine) (state delay-until))
  (when (> (get-universal-time) (timestamp state))
    (setf (state machine) :active)))

Variations

Each step! method will typically have some sort of conditional followed by an assignment of the state slot. Rather that having our state methods work by side effect, we could make them purely functional by having them return the next state of the machine. The game loop would perform the assignment:

(defun game-loop (game)
  (loop
    (dolist (machine (all-state-machines game))
      (setf (state machine) (step machine (state machine))))))

(defmethod step ((machine my-state-machine) (state (eql :idle)))  
  (if (key-pressed?)
      :keydown
      :idle))

I suppose you could have state machines that inherit from other state machines and override some of the state transition methods from the superclass, but I would avoid writing such CLOS spaghetti. For any object you’ll usually want exactly one state transition method per state. With one state transition method per state, we could dispense with the keyword and use the state transition function itself to represent the state.

(defun game-loop (game)
  (loop
    (dolist (machine (all-state-machines game))
      (setf (state machine) (funcall (state machine) machine)))))

(defun my-machine/state-idle (machine)
  (if (key-pressed?)
      (progn
         (incf (kestroke-count machine))
         #'my-machine/state-keydown)
      #'my-machine/state-idle))

(defun my-machine/state-keydown (machine)
  (if (key-pressed?)
      #'my-machine/state-keydown
      #'my-machine/state-idle))

The disadvantage of this doing it this way is that states are no longer keywords. They don’t print nicely or compare easily. An advantage of doing it this way is that we no longer have to do a CLOS generic function dispatch on each state transition. We directly call the state transition function.

The game-loop function can be seen as a multiplexed trampoline. It sits in a loop and calls what was returned from last time around the loop. The state transition function, by returning the next state transition function, is instructing the trampoline to make the call. Essentially, each state transition function is tail calling the next state via this trampoline.

State machines without side effects

The state transition function can be a pure function, but we can remove the side effect in game-loop as well.

We keep parallel lists of machines and their states (represented as state transition functions).

(defun game-loop (machines states)
  (game-loop machines (map 'list #'funcall states machines)))

Now we have state machines and a driver loop that are pure functional.

Joe MarshallPlaformer Game Tutorial

· 59 days ago

I was suprised by the interest in the code I wrote for learning the platformer game. It wasn’t the best Lisp code. I just uploaded what I had.

But enough people were interested that I decided to give it a once over. At https://github.com/jrm-code-project/PlatformerTutorial I have a rewrite where each chapter of the tutorial has been broken off into a separate git branch. The code is much cleaner and several kludges and idioticies were removed (and I hope none added).

Paolo AmorosoTesting the Practical Common Lisp code on Medley

· 65 days ago

When the Medley Interlisp Project began reviving the system around 2020, its Common Lisp implementation was in the state it had when commercial development petered off in the 1990s, mostly prior to the ANSI standard.

Back then Medley Common Lisp mostly supported CLtL1 plus CLOS and the condition system. Some patches submitted several years later to bring the language closer to CLtL2 needed review and integration.

Aside from these general areas there was no detailed information on what Medley missed or differed from ANSI Common Lisp.

In late 2021 Larry Masinter proposed to evaluate the ANSI compatibility of Medley Common Lisp by running the code of popular Common Lisp books and documenting any divergences. In March of 2024 I set to work to test the code of the book Practical Common Lisp by Peter Seibel.

I went over the book chapter by chapter and completed a first pass, documenting the effort in a GitHub issue and a series of discussion posts. In addition I updated a running list of divergences from ANSI Common Lisp.

Methodology

Part of the code of the book is contained in the examples in the text and the rest in the downloadable source files, which constitute some more substantial projects.

To test the code on Medley I evaluated the definitions and expressions at a Xerox Common Lisp Exec, noting any errors or differences from the expected outcomes. When relevant source files were available I loaded them prior to evaluating the test expressions so that any required definitions and dependencies were present. ASDF hasn't been ported to Medley, so I loaded the files manually.

Adapting the code

Before running the code I had to apply a number of changes. I filled in any missing function and class definitions the book leaves out as incidental to the exposition. This also involved adding appropriate function calls and object instantiations to exercise the definitions or produce the expected output.

The source files of the book needed adaptation too due to the way Medley handles pure Common Lisp files.

Skipped code

The text and source files contain also code I couldn't run because some features are known to be missing from Medley, or key dependencies can't be fulfilled. For example, a few chapters rely on the AllegroServe HTTP server which doesn't run on Medley. Although Medley does have a XNS network stack, providing the TCP/IP network functions AllegroServe assumes would be a major project.

Some chapters depend on code in earlier chapters that uses features not available in Medley Common Lisp, so I had to skip those too.

Findings

Having completed the first pass over Practical Common Lisp, my initial impression is Medley's implementation of Common Lisp is capable and extensive. It can run with minor or no changes code that uses most basic and intermediate Common Lisp features.

The majority of the code I tried ran as expected. However, this work did reveal significant gaps and divergences from ANSI.

To account for the residential environment and other peculiarities of Medley, packages need to be defined in a specific way. For example, some common defpackage keyword arguments differ from ANSI. Also, uppercase strings seem to work better than keywords as package designators.

As for the gaps the loop iteration macro, symbol-macrolet, the #p reader macro, and other features turned out to be missing or not work.

While the incompatibilities with ANSI Common Lisp are relativaly easy to address or work around, what new users may find more difficult is understanding and using the residential environment of Medley.

Bringing Medley closer to ANSI Common Lisp

To plug the gaps this project uncovered Larry ported or implemented some of the missing features and fixed a few issues.

He ported a loop implementation which he's enhancing to add missing functionality like iterating over hash tables. Iterating over packages, which loop lacks at this time, is trickier. More work went into adding #p and an experimental symbol-macrolet.

Reviewing and merging the CLtL2 patches is still an open issue, a major project that involves substantial effort.

Future work and conclusion

When the new features are ready I'll do a second pass to check if more of the skipped code runs. Another outcome of the work may be the beginning of a test suite for Medley Common Lisp.

Regardless of the limitations, what the project highlighted is Medley is ready as a development environment for writing new Common Lisp code, or porting libraries and applications of small to medium complexity.

#CommonLisp #Interlisp #Lisp

Discuss... Email | Reply @amoroso@fosstodon.org

Joe MarshallYou May Not Need That :around Method

· 77 days ago

I’ve seen this “anti-pattern” a few times in CLOS code. A superclass ’super will have a subclass ’sub and there will be a primary method specialized to the superclass.

(defmethod foo ((instance super) arg)
  (format t "~&Foo called on ~s." arg))

Then I’ll see an :around method defined on the subclass:

(defmethod foo :around ((instance sub) arg)
  (format t "~&Start foo...~%")
  (call-next-method)
  (format t "~&End foo.~%"))
The intent here is clearly that code in the method specialized on the subclass is invoked “around” the call to the method specialized on the superclass.

But the :around qualifier is not necessary and probably doesn’t do what is intended. If we remove the :around qualifier, then the most specific primary method will be the foo method specialized on ’sub. And the (call-next-method) invokation will chain up to the foo method specialized on ’super. It will work as was likely intended.

:around methods are useful when the superclass wants to run a method “around” the subclass. :around methods are combined from least specific to most specific — the opposite order of primary methods — so that the superclass can wrap the call to the subclass. An good example of where an :around method would be handy is when you need to sieze a lock around the call to the method. The superclass would sieze the lock in an :around method that would run before any of the subclass primary methods ran.

Ordinary chaining of methods doesn’t need the :around qualifier. Just chain the methods.

Joe MarshallWith- vs. call-with-

· 84 days ago

In Common Lisp, there are a lot of macros that begin with the word “with-”. These typically wrap a body of code, and establish a context around the execution of the code.

In Scheme, they instead have a lot of functions that begin with the words “call-with-”. They typically take a thunk or receiver as an argument, and establish a context around a call to the thunk or receiver.

Both of these forms accomplish the same sort of thing: running some user supplied code within a context. The Scheme way accomplishes this without a macro, but “call-with-” functions are rarely used as arguments to higher order functions. Writing one as a function is slightly easier than writing one as a macro because the compiler takes care of avoiding variable capture. Writing one as a macro leaves it up to the implementor to use appropriate gensyms. Writing one as a macro avoids a closure and a function call, but so does inlining the function. The macro form is slightly more concise because it doesn’t have a lambda at every call site. The function form will likely be easier to debug because it will probably involve a frame on the stack.

There’s no need to commit to either. Just write a “with-” macro that expands into a call to an inline “call-with-” function. This should equally please and irritate everyone.

Joe MarshallPorting a Game from Java (update)

· 89 days ago
I didn’t expect anyone would be interested, so I just pushed the code that I had with little thought about anyone trying to use it. It turns out that some people actually wanted to run it, so I polished off some of the rough edges and made it easier to get working. Feel free to email me if you have questions or suggestions.


For older items, see the Planet Lisp Archives.


Last updated: 2024-06-16 19:19