Embedding a Lisp interpreter into a Qt app

I've been working on a few things these past few months. This includes:

• A crease pattern generator that can calculate the crease pattern a piece of paper will have based on the sequence of folds applied to it. Conceptualising the paper as a mesh of facets, and determining the operations that can be performed on facets such as splitting was the key to implementing this.

• A circuit simulator that uses an iterative process to solve the circuit. Since Verlet physics is very successful at applying physical constraints (such as ensuring a point mass is fixed in space, or ensuring two point masses are always a fixed distance apart) using little more than repeatedly pushing objects according to the pressure that each constraint is applying, I thought I would try the same idea with electric circuits and the pressures of KVL and KCL.

When I managed to embed a Lisp interpreter into my app using ECL, I decided this is a suitable thing to tell other people about.

The advantages of scripting using Lisp in this way are numerous and exciting:

• Its an excellent way to ease into the beauty of Lisp without abandoning my other work.

• Initially, I can create Lisp bindings that manipulate the interface of the simulation such as adding components to the circuit, or applying specific folds. Doing this, I get loading/saving functionality for free, because my circuit/origami folds/other simulation configuration are defined in a lisp script. Also, I can manipulate my simulation “live” in the lisp repl while the simulation is running.

• Gradually, I can transfer more and more of the simulation implementation to lisp. Doing so, I can enjoy a real “live coding” environment. I have fluxus to thank for the inspiration.

• Lisp is a magnificent programming language. Having a Lisp repl in my app means I get a beautiful customisable programming language allowing me to describe a DSL without having to write a single line of parsing code.

The possibilities having a Lisp running in your app are breathtaking. In the past, the only thing that kept me from writing my own language to control my simulations was the mind numbing drudgery of writing parsers. Now, I get all the advantages of a custom language completely for free!

Here is a binary you can run: QtEclExample.zip

You may need to install VC redistributables: vcredist_x86.exe

The “Lisp” tab is initially active. It features the Lisp REPL. The only C++ function it is hooked to is myadd – not very exciting from the user's point of view, but VERY exciting for me, since it shows that I can have lisp control the whole show!

Non lisp stuff (will be lispified later):

• In the “Crease Pattern” tab, press “Push button” repeatedly to see the effect of applying a fold sequence.

• In the “Circuit” tab, right click a component to select it, and drag the slider to change its parameter (voltage for voltage sources, current for current sources, resistance for resistors.). In between frames, the algorithm runs 100 passes to solve the circuit. You'll notice that the visualisation is inspired by Paul Falstad's circuit simulator – I just wanted to add more interactivity!

Constructive Solid Geometry program

New post!

This program demonstrates an algorithm for performing CSG (Constructive Solid Geometry) operations, and it is based on the Java CSG implementation of Danilo Balby (http://www.geocities.com/danbalby/)

I found this excellent CSG implementation written in Java many months ago. Since it is very readable, and elucidates the concepts very clearly, I thought it may be worth translating this implementation into C++, so that this library can be used in C++ projects.

After months of procrastination and occasional work, the translation is completed. This is thanks to the excellently designed, crystal clear architecture of the original Java code, and the helpful comments.

Dealing with a large chunk of another programmer's source code is a very interesting excercise. There is an algorithm in the java code which implements the face cutting, but it runs all at once. If you want to figure out the reason for a particular problem, or simply want to peer into the inner workings of the algorithm, the standard line debugger is the wrong tool for the task. I found a simple and very useful technique for peering into code that runs all at once. I built a diagnostic object which allows me to take snapshots of the various geometric calculations it is performing, in order to "play it back" later, once the algorithm has finished. This was immensely helpful, and I will use this technique again. It is especially useful for reviewing algorithms that do things with geometry in 3D space.

Controls for the program

The controls are subtly different from my other programs, to allow finer control of navigation through the 3D space.

Moving the camera with the mouse:

Left mouse + mouse move ROTATES the camera.
Holding space + holding left mouse ROTATES the camera so it points to the selected location.
Holding space + holding left mouse + mouse move ORBITS the camera around the selected location.
Holding right mouse + mouse move PANS the camera along the camera plane, anchored on the selected point.
Mouse wheel MOVES the camera forward and back, based on the distance to the selected location. This means that before using the mouse wheel, make sure the mouse is hovering over the object you are interested in, because the distance of the step is a proportion of the distance between the camera and the object the mouse is hovering over.

Controlling diagnostic tool playback:

'd' toggles rendering of the diagnostic information.
Left arrow key steps the diagnostic playback backward one step.
Right arrow key steps the diagnostic playback forward one step.
Up arrow key steps the diagnostic playback forward continuously. (~20 steps per second, 1 per frame)
Down arrow key steps the diagnostic playback backward continuously. (~20 steps per second, 1 per frame)

A note on the diagnostic tool rendering:

Naturally it is up to the programmer what is being investigated, and I found myself frequently changing what the diagnostic tool should focus on. As you try to filter the volumes of data the diagnostic tool generates, I felt I had many options with how to proceed to learn more. I could either find some fancy ways to filter the data for the information I was interested in, leaving the snapshot taking as it was, or I could look at another aspect of the algorithm by modifying what I was choosing to record from the algorithm, and how I was going to present it.

There are 4 "episodes" in the diagnostic tool playback in this program.
1) Reveal the sequence of cuts made to the faces of the cone
2) Reveal each facet indivudually and all the facets that have come before, to enable me to visually ensure that there are no duplicates, and to inspect weird constructions of the algorithm
3) and 4), same as 1) and 2), except for the cube.

Download:

CSGTestWorld_080902_1415.zip

(password is createuniverses)

Screenshots:

I've gone screenshot happy!!

All 3 models: difference, intersection and union:



Bird's eye view of the difference model:



External of the intersection model:



The interior of the union model:



One of the diagnostic frames:

Quote from Carl Sagan

To anyone who periodically checks this blog from time to time, please excuse the lack of updates.

I'm still here, I just don't have anything coherent enough to write about at the moment.

Here is a list of topics I wish to write about and play with:

• Procedural modelling - Describing the design of everyday objects in code
• Blind watchmaker style of producing an aesthetically pleasing object, being aware of biases built into the modelling procedure
  
• Encoding knowledge generally, domain modelling, conceptualising
  
• Simulations - cognitive models
  
• Puzzles - Peg solitaire - clumping a series of moves together to get from one pattern to another (in a portion of the playing field)
  
• Puzzles - Bridges - Encode my strategy for playing this game
  
• Partitioning a plane - straight cuts, putting the pieces together, cutting along a grid, tesselations...
• Verlet Origami - crease and fold editor
  

Until then, here is a quote from a personal hero of mine, Carl Sagan:

We've arranged a global civilization in which most crucial elements - transportation, communications, and all other industries; agriculture, medicine, education, entertainment, protecting the environment; and even the key democratic institution of voting - profoundly depend on science and technology. We have also arranged things so that almost no one understands science and technology. This is a prescription for disaster. We might get away with it for a while, but sooner or later this combustible mixture of ignorance and power is going to blow up in our faces.

From Carl Sagan's book, "The Demon-Haunted World"

George Carlin will be sorely missed

A great man died today. He has had such a profound effect on so many people - I always deeply enjoyed his brilliant, mind expanding works, and he was one of those people you can point to to prove to yourself that humans aren't so bad after all.

Here is a quote of his that is in my mind at the moment:

The first thing they teach kids is that there's a God -- an invisible man in the sky who is watching what they do and who is displeased with some of it. There's no mystery why they start that with kids, because if you can get someone to believe that, you can add on anything you want.

Thank you George, for trying to set us free.

Actionscript and other stuff

Given the long time it has been since the last post, I think I'll post about some of the things I'm working on at the moment, rather than waiting until I'm finished before posting.

1. A C++ port of an excellent CSG (Constructive Solid Geometry) implementation I found written in Java called unbboolean, written by Danilo Balby.
2. Setting up a good development environment for making Flash files, and teaching myself Actionscript.

I'm using Eclipse + ASDT, which fortunately works very well - Eclipse is good to work with, and a pleasing feature is when you save your source file, the flash window and console traces are refreshed automatically.

Here is what I downloaded to get this working:

For Eclipse:
http://www.eclipse.org/downloads/ (Get Eclipse classic)

For ASDT (AS development tools)
http://sourceforge.net/projects/aseclipseplugin/

ASDT comes with the MTASC compiler, so there is no need to download it separately. However, if you want it, it is here: http://mtasc.org/

Getting the flash player for Win32 and Linux:
The following link is the ONLY place you should go to get the latest version of flash player from Adobe.
These zip files contain the debug and release versions of the plugin, the ActiveX control, and the standalone player for all versions of Flash, including the latest version. The zips also include debug and release shared libraries and standalone players for linux. Save yourself a lot of headaches and just get your flash playing stuff from here, and only from here.
Archived Flash Players available for testing purposes

The thing that's on this page is handy as well:
How to uninstall the Adobe Flash Player plug-in and ActiveX control

Other resources:
http://osflash.org/
http://axdt.org/

Tutorials:

http://gotoandlearn.com/ contains some excellent tutorial videos.

I found an excellent blog with a step by step tutorial - its called Open Source Actionscript
I'll work my way through it, but I hope the author keeps updating...

Happy coding!

More detail on the 15 puzzle solver

The 15 puzzle program does not do any searching as it solves a puzzle. It uses an explicitly described method. (See the original post for details of this method) However, in applying this method, the program repeatedly needs to find a way to move a numbered tile from one position to another, without disturbing the positions of certain other "locked" tiles.

To do this, the program makes use of a simple maze pathfinding algorithm.

It uses the pathfinder to plot the path a tile must take to reach its target position without disturbing "locked" tiles. Once the path is plotted, the program typically tries to move the tile along the path.

However, since the tile can only move into an empty space, the empty space must be moved to the next spot the tile needs to move into (to progress it along its path). So, the program uses the pathfinding algorithm to plot a course for the empty space as well (again, without disturbing "locked" tiles, which would now typically include the tile trying to reach its destination).

Here is a description of the simple maze pathfinding algorithm:

1) Mark the destination on the maze with the number zero.
2) Every iteration of the following represents a single step in the maze, so the number of iterations doesn't need to be any higher than the maximum number of steps you are willing to take. (Theoretical maximum is width * length of the maze) For every iteration:

• Make a pass along every cell in the maze.
• If the cell is not a "wall" cell, check its immediate 4 neighbours.
• If one of these neighbour cells is marked with the number of the previous step, mark the current cell with the number of the current step.

3) Finished.

After running this algorithm, you end up with a maze (or whatever you were writing on) marked with the number of steps it will take to reach the goal from any cell in the maze.
So to plot a course from a particular point, you simply find the neighbouring cell with fewer steps remaining than the current one, and you keep doing this until you inevitably reach the goal cell.

In the 15 puzzle solver, this number is displayed in small print at the top right corner of each cell.

Cells shaded yellow are cells that have been marked as "walls".

I may release another version which displays more details about the steps it is taking, as well as displaying the path finding being done for the empty space (which was initially omitted for clarity).

Update, Monday 29th June, 2009
Source code is now available. See this post for details.

Lights Out puzzle experiment

I wrote this program to see the effect of applying a simple rule for solving the light toggling puzzle.

The idea is, because the toggle pattern is a cross shape, you can toggle one cell in a row at a time by pressing the one below it. Working your way down, you can clear each row separately this way. (According to the rules of the light puzzle, "pressing" a cell means toggling the cells that make up the cross centered on that cell individually.)

Naturally, the interesting thing happens when you reach the bottom. Sometimes it will work itself out, sometimes it won't. When it doesn't, it can produce interesting patterns as you keep applying this algorithm. When the puzzle isn't solved, this program reapplies this technique, but in the other direction.

Press 'r' to generate a new puzzle. (It regenerates a new puzzle by "pressing" 1000 cells at random)
Press 'p' to pause the algorithm.
Press 'c' to continue the algorithm. Pressing it again will modify the speed at which the algorithm runs - whole row per frame, or single cell per frame.

Click to press the indicated cell (will toggle a cross shape at that position). You can do this during a solve as well. You can set up your own puzzle this way, and see how the algorithm handles it.

Screenshots:







Download Lights_080205_1040.zip here
(as usual, the password of the zip file is createuniverses)