Lispjobs — Lisp Engineer, MIND.AI, Seoul, Korea & L.A, USA

· 38 hours ago

MIND.AI (http://www.mind.ai) is working on a brand new paradigm in artificial intelligence. We are looking to innovate REAL AI. Not just natural language processing but Natural Language Reasoning. We need versatile talents who are interested in changing the world. This is not deep learning but something totally new. And we need people with open and creative minds.

Artificial intelligence in a brand new paradigm. NOT deep learning/neural networks, but knowledge of same a plus. Symbolic/logical AI experience will be practiced. Developing core logic based on a new theory of information. Duties will include optimization of existing code and developing new features of the AI. We require significant experience in development activities on large projects and advanced software architecture and development in a large Common Lisp codebase. To build new components and extend existing tooling to meet project needs, and implement high-quality library components and products.

Specifically, the Lisp engineer will:

• Integrate with natural language libraries and packages such as the google parser to form structured data based on our proprietary model (similar to semantic networks)
• Build data structures and algorithms to acquire new information and relate it to existing ontologies (it learns how to learn)
• Work with computational linguist to build up knowledge bases and further define knowledge representation
• Develop persistence model (using database and object serialization)
• Implementation of logical reasoning based on abductive, inductive and deductive reasoning models
• Design and develop interactive learning interface
• Optimizing existing code base

BASIC QUALIFICATIONS

• BS in Computer Science or equivalent.
• 3+ years experience in Lisp programming (5+ years programming), working in structured systems and/or software development teams (Common Lisp, LispWorks preferred)
• Thorough understanding of Lisp paradigms (eg, functional & object oriented)
• Familiarity with common software architectures, design patterns, and software development life cycles

PREFERRED QUALIFICATIONS

• Experience with persistence (database & object serialization)
• Experience with GOFAI.
• Familiarity with formal logic.
• Working with ontologies and taxonomies
• Static and/or Dynamic Analysis
• Dynamic analysis, program instrumentation, and profiling

Nicolas Hafner — Harmony - Confession 77

· 9 days ago

This is a blog entry about Shirakumo's sound system Harmony. While Harmony was released some months back, I spent the last few weeks rewriting large parts of it from the ground up, and I think it's worth it to write a short article describing how it's built and what you can do with it. So, if you're interested in doing sound processing and playback in Lisp, this is for you.

The need for Harmony arose out of me not finding any suitably powerful sound solution in Lisp. I tried doing a pure Lisp solution at first, but was not able to figure out how to make things go fast without sacrificing design. So, in the interest of performance, I first set out to write a C library that does the essential sound computations for me. This library is called libmixed.

I wanted to keep libmixed as simple and straight-forward as possible. As such, it does not do any sound file reading or writing, synthesising, or sound output to devices. Instead, it only concerns itself with the processing of sound samples. Another important factor for its design was that it should be easy to extend it with further capabilities, and to allow combining processing steps. This led to the segment pipeline model.

In libmixed, you assemble a set of segments - audio producers, consumers, or transforms - that perform the computations you need. You connect them together through buffers so that they can transparently exchange audio data. This produces a directed, acyclic graph where each vertex is a segment, and each edge is a buffer. This graph can then be serialised into a simple sequence that dictates the order in which the segments should be run.

Unfortunately, audio data comes in a variety of formats. Samples are frequently encoded as signed or unsigned integers of 8, 16, 24, or 32 bits, or in floats or doubles. The data might have multiple audio channels, and the samples can be either interleaved (LRLRLR..) or sequential (LLL..RRR..). The sample rate might be different as well. All of this can make it quite difficult to deal with the data between different audio components. Libmixed's solution to this problem is to force all the buffers to use the same sample rate, to encode samples in floats, and to only represent a single channel. Almost all segments present in a pipeline thus don't have to worry about any of these discrepancies anymore, reducing complexity tremendously. In order to allow interacting with foreign components easily, it does also include an unpacker and a packer segment.

The packer takes a set of buffers and information about the sample representation, and packs the buffer's data into a single C array, ensuring proper sample format, layout, and sample rate. The unpacker does the opposite. Thus, if for example you have a library that decodes an audio file, you most likely need to add an unpacker segment to the pipeline that decodes the audio data from the library into the proper internal format.

So, for a very simple example of taking two audio files, mixing them together, applying a reverb effect, and then playing them back, the pipeline would need to look something like this:

We can get away with assigning the same two buffers for both of the unpackers here by using a special property of the basic-mixer segment. Instead of manually processing the two unpackers in our pipeline, we can set the segment property on the basic-mixer's inputs, which tells the basic-mixer to cause the processing on the segment on its own. This way, the mixer can process the segment that produces the input as it mixes it together, reducing the need to allocate individual buffers for each input to the mixer. This is one of the design decisions that still bother me a bit, but I found it necessary after discovering that I would otherwise need to allocate a huge amount of buffers if I wanted to allow playback of a lot of sources simultaneously.

As it currently stands, libmixed includes segments to mix audio by either just adding samples, or through 3D spatial positioning of the source. It also includes segments to change volume and pan, to fade in and out, to generate simple sawtooth, square, triangle, or sine waves, and to include LADSPA plugins in the pipeline. I'd like to add a bunch more effects segments to it to make it more useful for real-time sound processing, but I haven't felt the motivation to get into that yet. If you're interested in sound processing and would be willing to do this, let me know!

Basically the idea of libmixed boils down to this: there's segments that have properties, inputs, and outputs. You can write and read properties, and connect buffers to the inputs and outputs. You can then tell the segment to process a number of samples, and it will read its input buffers, and write to its output buffers. This all works over a struct that contains a bunch of function pointers to perform these actions. It is thus very easy to add further segments to libmixed, even as an outside library: simple produce a struct that holds the appropriate function pointers to the functions that do what you want. This is also how cl-mixed allows you to write segments from Lisp out.

Ascending from the C world to the C+L world then leads us to cl-mixed, which is the bindings and wrapper library for libmixed. It takes care of all the hairy low-level stuff of interacting with the C library, tracking and allocating foreign memory, and so forth. As mentioned, it also gives you a simple interface to write your own segments from Lisp. This can be really nice in order to prototype an effect.

While libmixed is a neat framework to base your sound processing around, it doesn't exactly make most of the common tasks very convenient. Usually you have some audio files that you would like to play back, and maybe apply some effects to them. This is where Harmony comes in.

Harmony takes libmixed's generic view of segments and extends it to include sources, drains, and mixers. Sources are segments with no inputs, drains are segments without outputs, and mixers take a run-time variable number of inputs. It also greatly simplifies the pipeline construction by handling the buffer allocation for you. It does this with the help of a graph library called Flow. More on that later. Harmony also gives you a sound server object that handles the mixing in the background, allowing you to focus on just adding, removing, and changing sources in your program. Finally, Harmony includes a number of pre-made sources and drains that either connect to other libraries, or present native implementations. Currently, it supports playing back MP3, WAV, FLAC, and raw buffers, and supports outputting to out123, OpenAL, WASAPI, CoreAudio, ALSA, PulseAudio, and to raw buffers.

The easiest way to get started is to use the harmony-simple system, which assembles a default pipeline for you, allowing you to just directly play some stuff.

 (ql:quickload :harmony-simple)
(harmony-simple:initialize)
(harmony-simple:play #p"my-cool-music.mp3" :music)
(harmony-simple:play #p"kablammo.wav" :sfx)


Assembling your own pipeline isn't very difficult, though. It comes down to just telling Harmony how to connect the inputs and outputs between segments. An optimal buffer layout is automatically computed based on the segment's properties and the graph that you describe through the connections. To do this, Harmony uses the Flow library to describe segments in a graph. Unlike most graph libraries, Flow assigns distinct input and output ports to each vertex. These ports have properties like their arity, direction, and so on. For instance, the basic-mixer from the previously illustrated pipeline would be a vertex with an input port of arbitrary arity, and two output ports of single arity. Flow then employs a simple algorithm to assign colours to the edges in such a way that no input is connected to the same two colours, and no input and output on a vertex have the same colour unless the vertex is marked as in-place. This kind of allocation computation has cropped up in a couple of places, so I've been able to use Flow for it in other projects as well. I don't think it's important to know how the algorithm works, but in case you're interested, the source is commented and pretty short.

How to write new sources and segments, or how to assemble your own pipeline is already illustrated pretty succinctly in the documentation, so I suggest you check it out if you're interested in working on that kind of thing. Harmony is primarily geared towards use in games, where simple pipelines and immediate playback of a variety of audio sources is necessary. However, I can also see it being used in some kind of digital audio workstation, where a graphical user interface could allow you to put together segments and configure them, mapping to a libmixed pipeline underneath.

I feel like I've been rambling about tangents for a bit here, but I suppose the reason is that Harmony doesn't really do all that much. At best it just smooths over the last remaining corners that come from the libmixed C heritage and adds some useful segments to the library. All the concepts used and all the sound technology behind it lies more in libmixed's hands though, and I think I've already explained that all earlier.

So, to close off: if you're thinking of doing some kind of digital audio processing in Lisp, keep Harmony and cl-mixed in mind. I'm also more than open to feedback and suggestions, so if you have any ideas or things you'd like to add to the projects, head on over to GitHub's issues, or talk to us on Freenode/#shirakumo.

· 18 days ago
Here are the top 100 projects from Quicklisp for October, by "raw" download count.

16626  alexandria15213  closer-mop13436  anaphora13420  split-sequence12954  babel12879  trivial-features12719  iterate12464  cl-ppcre11798  bordeaux-threads11724  let-plus11693  trivial-gray-streams11389  cffi11281  trivial-garbage10622  puri 9884  nibbles 9732  more-conditions 9611  flexi-streams 9026  usocket 8602  cl+ssl 8544  utilities.print-items 8153  cl-base64 8130  chunga 7889  chipz 7791  drakma 7691  esrap 7635  trivial-backtrace 6308  ironclad 5910  cl-yacc 5691  cl-fad 5302  parse-number 4996  named-readtables 4984  fiveam 4959  asdf-flv 4886  log4cl 4756  bt-semaphore 4736  local-time 4701  lparallel 4647  closure-common 4638  cxml 4594  architecture.hooks 4552  lift 3784  plexippus-xpath 3586  cl-json 3569  trivial-utf-8 3322  optima 3157  parser.common-rules 3144  cl-clon 2837  uuid 2819  cxml-stp 2705  xml.location 2700  metabang-bind 2624  cl-dot 2475  utilities.print-tree 2473  slime 2458  cl-unicode 2456  cl-interpol 2273  md5 2267  cl-store 2232  fare-utils 2204  fare-quasiquote 2108  inferior-shell 2105  fare-mop 1769  cl-utilities 1706  quri 1671  ieee-floats 1625  static-vectors 1605  fast-io 1547  trivial-types 1545  cl-annot 1536  cl-syntax 1437  utilities.binary-dump 1431  trivial-indent 1364  trivial-mimes 1335  asdf-system-connections 1334  array-utils 1329  symbol-munger 1320  cl-containers 1318  metatilities-base 1318  plump 1302  cl-slice 1296  hunchentoot 1280  access 1267  arnesi 1266  collectors 1258  gettext 1236  djula 1226  cl-parser-combinators 1221  cl-locale 1187  postmodern 1164  rfc2388 1159  yason 1121  simple-date-time 1050  command-line-arguments  956  cl-sqlite  951  cl-log  947  osicat  943  salza2  913  py-configparser  903  cl-markdown  903  asdf-finalizers

Didier Verna — Standard IO syntax and the Robustness Principle

· 28 days ago

Here is a flagrant illustration of the robustness principle, or rather, of a failure to honor it.

I was investigating a bug in Declt where some floating point numbers were printed with exponent markers (e.g. 0.5f0 instead of just 0.5) in the Texinfo file, which broke the parsing of the file by Perl.

Eventually, I found out a double infringement of the robustness principle. First of all, Declt failed to comply with part 1 of the robustness principle: be lenient with the others. The Texinfo file generation routine should have been wrapped into a call to WITH-STANDARD-IO-SYNTAX and it wasn't. Always do that to be on the safe side. Lesson learnt.

This failure on my part, however, had the interesting consequence of exhibiting what I consider a serious infringement of part 2 of the robustness principle: be strict with yourself. It would have remained unnocited otherwise. The culprit here is not Declt. This time, it's the common-lisp-stat library. Problem: the simple fact of loading this library globally changes the value of *READ-DEFAULT-FLOAT-FORMAT* from SINGLE-FLOAT (the default) to DOUBLE-FLOAT. This is bad, and it can break your code in all sorts of nasty ways.

Explanation

*READ-DEFAULT-FLOAT-FORMAT* tells the reader how to read floats when no exponent marker is provided. By default, 0.5 will be read as a SINGLE-FLOAT. But this variable also influences the printer (out of a concern for printing readably I guess): when printing a float of a different format than the current default, then the appropriate exponent marker is also printed. So here is precisely what happened. Declt had been compiled with some floats (e.g. 0.5) read as SINGLE-FLOATs. Later on, those floats were supposed to be printed aesthetically as such. But right after loading common-lisp-stat, the default format changed to DOUBLE-FLOAT and all of a sudden 0.5 started to be printed as 0.5f0.

Consequences

This is bad enough already, but consider that messing with the standard IO syntax globally like this can break your code in all other sorts of even nastier ways. Imagine for instance that common-lisp-stat had been loaded before Declt, and Declt needed to be recompiled. All of a sudden, Declt would be using double floats and the bug would be gone. That is, until the next start of the REPL, after which all floats would be printed like 0.5d0!

So granted, my code wasn't robust enough. But please, don't mess with standard IO syntax globally!

· 30 days ago

uiop

The problem I had with UIOP is due to using stock SBCL ASDF (3.1.5) with UIOP 3.3.0. UIOP changed a public function’s behavior in a way that affected older ASDFs (and seemingly only older ASDFs). This is considered a bug and will be fixed in a future UIOP release.

sly

September of Sly has turned into Season of Sly. I haven’t been hacking as much with Sly as I wanted in September, so I’m going to keep going with it for October and beyond, and write up a summary Very Soon. My current hangup is C-c M-q, which is slime-reindent-defun in slime, but does nothing in Sly, and there’s no sly-reindent-defun to try to bind instead. I try to use C-c M-q a thousand times a day.

qlt

You might know that Quicklisp dists are constructed after building every project that Quicklisp tracks, and projects that don’t build (due to compile-time problems) aren’t included. This is better than nothing, but it does nothing to catch runtime problems.

Last week Quicklisp got hit with a runtime problem that broke a lot of stuff, so it prompted me to create qlt.

qlt is for collecting small files of Common Lisp code to run before a Quicklisp dist is created. If any of the files signal an error, Quicklisp generates a report with the console output and the dist is no-go until the problem is tracked down.

The project is sparse right now, but it does include a test file that catches the runtime problem from last week. I hope to include many more things to test as time goes on. If there is something you want to check, patches welcome!

Quicklisp news — October 2017 Quicklisp dist update now available

· 31 days ago
New projects:
• also-alsa — Basic ALSA bindings for Common Lisp — LGPL
• bitio — A wrapper for octet streams that enable bit level streams. — MIT License
• cl-lzma — CFFI wrapper around LZMA (de)compressor foreign library — Public domain
• cl-rules — Simple DSL for rules that can be configured without code — GPL-3.0
• html-entities — A module for encoding and decoding HTML/XML/SGML entities. — MIT License
• mtif — An interface to the MacOS MultiTouch framework — MIT
• parsley — A toolset for parsing binary data formats. — MIT
• quicksearch — Quicksearch searches CL library, and outputs results at REPL. — MIT License
• skippy-renderer — GIF renderer for SKIPPY — MIT
• trivial-macroexpand-all — Call each implementation's macroexpand-all equivalent — Unlicense
• zacl — A layer for loading and running some Allegro CL projects. — BSD

Removed projects: cl-proj, magicffi, poiu.

Neither cl-proj nor magicffi build for me any more due to foreign library changes. POIU was removed by request of the author.

To get this update, use: (ql:update-dist "quicklisp")

Enjoy!

McCLIM — Progress report #10

· 33 days ago

Dear Community,

We have many important improvements since the last iteration and even more work is pending. I want to apologise for this late progress report - it has been almost three months since the last update. I'll try to improve in this regard.

Some highlights for this iteration:

• various utilities have been replaced with alexandria equivalents
• distinct frames don't shadow *accelerator-gestures* of their children
• accepting-values refinements - better handling of errors and return values
• refactor and small fixes of the recording implementation code
• refinements in class hierarchy for streams, medium and graphics state
• slider from 30.4.5 spec section has been implemented
• scrolling implementation refinements
• tab-layout extension refactor
• improvements related to drei text editing substrate
• user manual refinements and improvements of its building scripts
• improvements related to the PDF backend
• MOP code has been ported to use closer-mop portability layer
• numerous editorial fixes in bundled specification sources
• improvements to format-graph-from-roots
• better Unicode support in CLX for frame title
• general code base cleanup to decrease number of warnings during compilation
• transparency handling in CLX backend and alpha channel support in images
• small Listener improvements (bug fixes and cleanups)

We want to thank everybody who has contributed to the project (by improving the code base, discussions, issue reporting, providing advice and suggestions, monetary contributions etc). We are especially grateful to the following people: Nisar Ahmad, Alastair Bridgewater, John Carroll, Cyrus Harmon, Philipp Marek, Elias Mårtenson, Piotr Mieszkowski, Jan Moringen, Nick Patrick, Alessandro Serra and last but not least Robert Strandh.

Bounties:

All McCLIM bounties (both active and already solved) may be found here. Default bounty expiration date is 6 months after publishing it (a bounty may be reissued after that time period).

Bounties solved this iteration:

• [$300] Replace MOP things with closer-mop portability layer • [$100] Keystroke accelerators may shadow keys even if inactive

Active bounties ($1800): • [$100] drag-test demo: dragging square to the empty position invokes the debugger (new)
• [$100] Text field pane height is too small, clipping the bottom off characters (new) • [$300] Listener: repl blocks when long process runs (new)
• [$500] Windows Backend • [$400] Fix Beagle backend
• [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size • [$150] clx: input: english layout
• [$100] Add PDF file generation (PDF backend) Our current financial status is$1089 for bounties and $264 recurring monthly contributions from the supporters (thank you!). I have been asked a question about who decides which issues have bounties on them and how the reward amounts are decided. If anyone has been wondering about the same here goes the answer: issues and prices are based on my subjective opinion indicated by problems users encounter and what I consider being worth putting bounty on it. Note though, that I'm open to suggestions (see the next paragraph). I hope that despite some potential doubts the community is generally satisfied with the progress and decisions we make. If there is some lack of transparency, please let me know what you want to know and I'll do my best to help. Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you would like to work on an issue that is not covered by the existing bounties, feel free to suggest a new bounty. If you have any questions, doubts or suggestions - please contact me either by email (daniel@turtleware.eu) or on IRC (my nick is jackdaniel). McCLIM developers and users hang out on #clim IRC channel on Freenode. Sincerely yours, Daniel Kochmański Zach Beane — UIOP 3.3.0 problems · 37 days ago Ok, here’s something that is causing problems when I build this month’s Quicklisp dist. UIOP 3.3.0 was recently released, and it’s causing some stuff to apparently compile over and over again. Here’s a real simple thing to try: $ cd ~/quicklisp/local-projects/
$curl -O https://common-lisp.net/project/asdf/archives/uiop.tar.gz$ tar xzvf uiop.tar.gz


Then:

CL-USER> (ql:quickload "circular-streams")


On my setup, I see cffi and babel stuff compiled twice:

To load "circular-streams":
circular-streams
[package uiop/package]............................
..................................................
..................................................
[package alexandria.0.dev]........................
..................................................
[package babel-encodings].........................
[package babel]...................................
..................................................
[package cffi-sys]................................
[package cffi]....................................
..................................................
[package cffi-features]...........................
[package alexandria.0.dev]........................
..................................................
[package impl-specific-gray]......................
[package trivial-gray-streams]....................
[package uiop/package]............................
..................................................
..................................................
[package babel-encodings].........................
[package babel]...................................
..................................................
[package cffi-sys]................................
[package cffi]....................................
..................................................
[package cffi-features]...........................
[package static-vectors]..........................
[package fast-io].................................
[package circular-streams]..


If I remove uiop-3.3.0/ from local-projects, the output looks like this:

To load "circular-streams":
circular-streams
[package alexandria.0.dev]........................
[package impl-specific-gray]......................
[package trivial-gray-streams]....................
[package uiop/package]............................
..................................................
..................................................
[package babel-encodings].........................
[package babel]...................................
..................................................
[package cffi-sys]................................
[package cffi]....................................
..................................................
[package cffi-features]...........................
[package static-vectors]..........................
[package fast-io].................................
[package circular-streams]..


Any ideas?

update Commit 4ed76c32050753c8a4450c342a1592881e11d63d seems to reference this behavior, with the “fast-io” system given as an example. And indeed, when I try this with fast-io, I see similar recompilation.

Nicolas Hafner — Project Listing - Confession 76

· 48 days ago

This is a listing of projects that I've started, some of which I've completed. The intent is to spread awareness about the work I've done, as I speculate that a lot of people don't know about most of it, even though it might prove useful to their own projects. So, hopefully this article will help a bit in that regard.

I won't go into much detail in the descriptions, as that would take too much of both your and my own time. You can however click on the title of each project to get to its "homepage" if you want to find out more. Naturally, you're also free to contact me if you're interested.

Major Projects

Major projects are ones that have no completion in sight. There are always improvements and additions that could be made to improve the project. Generally they serve as a launch pad for other, minor projects that are completable.

Lichat

Lichat is an attempt at a simple, light-weight chat protocol. There's currently full implementations of the protocol available that allow you to host a TCP or WebSockets server, and to write clients in JavaScript and CL. A Java library, with the intent of writing an Android client is planned.

Maiden

Maiden is an event coordination framework and bot construction toolkit. It includes a plethora of pre-made modules to provide common chat bot functionality, as well as a couple of different backends for various chat protocols.

Parasol

Parasol is a native painting application for graphics tablet users. It has been dormant for some years now as I've still not figured out a good way to architecture everything.

Portacle

Portacle is the portable development environment for Common Lisp. It gives you an easy-to-deploy, contained development studio that you can use to program. It is especially suited and geared towards beginners that have not used Lisp before, but it's also convenient for quick setups on unconfigured machines.

Radiance is a web application environment, allowing you to easily deploy and run different web applications in the same lisp instance, increasing sharing of common resources. This article is actually hosted on an application running in Radiance. Imagine that!

Trial

Trial is an OpenGL game engine with a heavy focus on modularity. It is supposed to provide a large toolkit of useful bits and pieces from which you can create a game. I use this engine together with some of my co-conspirators to write games for the Ludum Dare game jam. Hopefully the engine will at some point also give birth to bigger games.

Minor Projects

These projects all either spawned out of the requirements of the major projects, or happened simply for fun. Most of them are already complete and thus ready for use.

3d-matrices

A library implementing common matrix calculations, with an emphasis on 2x2,3x3, and 4x4 matrices as commonly used in graphics. It provides some numerical functions as well, but those are not the focus. The library is heavily optimised, so it is not made of pretty code.

3d-vectors

This is the counter-piece to 3d-matrices, providing vector operations optimised for 2, 3, and 4-component vectors. Also just like 3d-matrices, the library is heavily optimised and thus not pretty on the eyes.

CLSS

CSS-Like Simple Selectors implements a DOM search engine using the CSS selectors as the query format. It is reasonably optimised, but only usable with the DOM provided the Plump system.

LASS

Lisp Augmented Style Sheets is a compiler for a custom CSS syntax. It allows you to write CSS files in a much more convenient and homely-feeling syntax. I've been using this to write pretty much all of my CSS for the past couple of years.

array-utils

A small library to provide vector manipulation functions that are sorely missing from the standard. Allows to push to any place in the array while maintaining the proper shifting logic.

autobuild

A Continuous Integration system with a focus on running directly on your machine, rather than in a container or otherwise segregated environment. This is currently being rewritten from scratch.

chatlog

A Radiance application for a web interface to a chatlog database. The database is recorded through the Colleen or Maiden chatlog modules.

chatter

A chat application based on the Twitter direct messages system. Allows you to chat directly with your twitter friends as if it were a regular chat room. Easy to set up, and runs on all major desktop platforms.

chirp

A client library implementing the full Twitter REST API. If you want to interact with Twitter, this is your best bet.

cl-fond

A bindings library to libfond, allowing you to use its functionality easily from Lisp out. Libfond allows the rendering of TrueType fonts onto OpenGL textures.

A bindings library to libstem_gamepad, providing easy gamepad and joystick event processing from Lisp. This is useful if you don't want to use some kind of framework that brings all sorts of other baggage with it, not just gamepad processing.

cl-gpio

A wrapper library for the Linux General Purpose IO device present on embedded systems such as the Raspberry Pi. It allows you to conveniently access and control the IO pins on the board.

cl-k8055

A bindings library for the k8055 analog input board. Allows you to read its various values and set outputs.

cl-mixed

A bindings library to libmixed, allowing you to use its functionality from Lisp. Libmixed allows you to perform digital audio mixing and processing. Thus, with this, you can do efficient DSP from Lisp.

cl-monitors

A bindings library to libmonitors, providing convenient access to information about the currently attached monitors, and giving you the ability to control the resolution thereof.

cl-mpg123

A bindings library to libmpg123, giving you fast and easy to use MP3 decoding. This covers the complete API exposed by libmpg123, and thus easily your best bet for MP3 processing.

cl-out123

A bindings library to libout123, giving you cross-platform audio output. The API is very simple to use, and can thus give you a quick start if you need to play some audio.

cl-soloud

A bindings library to SoLoud, an open source C++ sound engine for the use in video games. I've completed this, but dropped it, as it was too hostile to extension from CL. I've since developed Harmony (see below).

cl-spidev

A wrapper library for the Linux Serial Port Interface device. With this you can do serial port input/output, which is present on some embedded devices like the Raspberry Pi.

clip

Clip is an alternative approach to templating, expressing the template within valid HTML. This allows a different development approach, wherein you can hammer out a mock-up for a website in an HTML document, and then simply add templating logic through further tags and attributes, maintaining browser-viewability.

colleen

This is the predecessor to Maiden, with a more narrow focus and feature base. Since it has been superseded, and the code is quite crusty, I heavily urge you to look at the Maiden project instead.

crypto-shortcuts

A tiny library to provide commonly used cryptography functions in a more accessible format, as some of the tools provided by Ironclad & co. can be a bit cumbersome to use.

deeds

Deeds is an Extensible and Event Delivery System. It offers both flexible and performant creation of event systems. Deeds is used heavily in Maiden.

deferred

This was an attempt at making optional dependency wrangling more convenient. It gives you a few tools that attempt to make it possible to write code that is only considered once another system becomes available.

deploy

With Qtools I developed a very convenient mechanism to generate deployments of my systems. This is the evolution of that, allowing you to use it independent from Qt. It takes care of your foreign libraries and the general shutdown and boot sequence, making the whole binary deployment process much smoother.

dissect

Sadly a lot of projects use the "trivial-backtrace" system that just gives them a string with a backtrace. Dissect allows you to capture, step, and completely inspect the stack trace on a variety of Lisp implementations. The introspection abilities allow you to write a good chunk of a portable debugger. It's also very useful for logging and other situations where execution is automatically continued, but the information of the current stack is still useful to store somewhere.

documentation-utils

I like to keep my code nice and clean, and as such docstrings are quite cumbersome clutter. This library allows you to easily and conveniently put all the docstrings in a file outside of the rest of your code.

filebox

This is a Radiance application that provides you with a very simple file storage. Coupled with the filebox-client, you get a Dropbox-like system.

flare

Flare is a particle simulation framework. Unlike most particle systems, it does not focus on the emission of small dots, but rather on the precise coordination of a hierarchy of entities. It allows you to describe sequences of events, and then lets you play those sequences back, performing the actual transformations. You can even rewind time and interactively work on your sequences.

flow

This is a flowchart-like graph library. It gives you access to nodes which, unlike in mathematical graphs, have dedicated ports from which connections are made. These ports can have semantic meaning and syntactic properties. Thus, this gives you a toolkit to make flowchart-like graphs and compute with them.

for

Since I couldn't come to terms with Iterate, I decided to write my own extensible iteration construct. Unlike Loop or Iterate, For has a particular syntax to it that makes extensions feel much more integrated.

form-fiddle

This small library allows you to wrangle lambda forms and destructure them into their individual components (docstring, declarations, arguments, etc).

glsl-toolkit

A toolkit to allow you to process and manipulate OpenGL Shader Language code. It includes a full GLSL4 parser, printer, and code-walker. Using this you can even do stuff like merge separate shaders together automatically, preserving input/output semantics.

halftone

A sample application for the Qtools system, providing you with a minimal, but pretty image viewer. Works on all major desktop platforms.

harmony

Harmony is a fully-fledged audio system, allowing you to control playback of multiple sources, and even to position them in 3D space. It also allows you to build your own sound processing pipelines, to add in effects and other sound processing capabilities.

humbler

This is a client library for the Tumblr REST API. It has full coverage of the documented features and properly wrangles all the oddities and inconsistencies of the API for you.

kanji-tree

This is still in the works, but is intended to become a website (using Radiance) that provides useful information about Kanji, as well as an optimised sequence by which to learn them. Hopefully this will help me and other people to learn Japanese.

keyword-reviews

Another Radiance application that provides a very minimalist site for product reviews. The twist of this site is that your review should be very short, if possible reduced to keywords only. The idea is that this should make for interesting descriptions and interpretations.

lambda-fiddle

The counterpart to form-fiddle, this allows you to wrangle and destructure lambda-lists (argument lists).

legit

An interface to the Git binary. Using this library you can run all the available Git commands using a more convenient and streamlined function interface. An object-oriented high-level interface is also available, but doesn't cover the full API.

libfond

A small C library to allow you to render TrueType fonts to OpenGL textures. Text rendering is something that's often left out of minimal game engines, and so libfond can provide you with that aspect.

libmixed

A small C library to allow you to mix and process digital audio. It is reasonably optimised and comes with a set of processing and mixer components out of the box. One of the components also allows you to integrate LADSPA plugins, so you can use those directly as well.

libmonitors

A small C library to handle the management and information retrieval of connected Monitors. Currently Linux, Windows, and OS X are supported.

lionchat

A native GUI for the Lichat system. While this works well enough as it currently stands, I'd like to rewrite it at some point to use Maiden, and thus allow connecting to other chat systems as well.

lquery

A library modelled after jQuery to allow you to conveniently and succinctly wrangle HTML and XML documents. This is Particularly useful for web scraping tasks.

modularize

This is a system that gives you an extension to the package system, by allowing you to add other metadata to it. This should facilitate the construction of "modules," individual components of a larger system. The metadata can be used to give meaning to the modules and model their relations to the whole system.

modularize-hooks

This augments the modularize system by giving you hooks and triggers. Thus, modules can provide opaque entry points for other modules to provide additional functionality.

modularize-interfaces

This augments the modularize system by giving you "interfaces"- contract-like descriptions of the functionality provided through a package. While the interface description is abstract and only includes the signatures of functions, another module can then opt to implement the actual functionality behind the interface.

north

The successor to the South (Simple OaUTH) library, implementing the full oAuth 1.0a protocol, both client and server sides. Using North you can easily become an oAuth provider or consumer.

parachute

Parachute is a testing framework with an emphasis on being extensible. As proof of this, it includes "compatibility layers" for a couple of other popular testing frameworks. Using such a layer you can immediately convert to using Parachute by just changing a package :use and system :depends-on.

pathname-utils

A small library to help with common pathname wrangling tasks. If you need to work with pathnames a lot, you'll probably find one or two things in here that will prove useful to you. Note that the library is restricted to pathnames, so it won't provide anything that actually touches the file system.

pi-plates

A library implementing the public interface for the PiPlates DAQ plates that you can use in combination with the Raspberry Pi. The library is currently untested, but "should work" as it is a fairly straightforward translation of the official Python code. I haven't yet found the will to actually test it myself.

piping

Piping allows you to write "pipelines." Pipelines are systems of pipe segments that pass along and transform or compute based on the object currently being passed through the pipeline.

plaster

Plaster is another Radiance application. It gives you a usable paste service. The Radiance tutorial even shows you how to write the application from scratch.

plump-bundle

An implementation of a binary storage format for the Plump DOM. It allows you to save a DOM into a more efficiently parseable representation on disk.

plump-sexp

A parser and printer for an s-expression based syntax of an HTML DOM, using the Plump DOM as a back-end.

plump-tex

A parser and printer for a TeX based syntax, using the Plump DOM as a back-end. With this you can parse TeX sources into a DOM and render them as HTML.

plump

A Practically Lenient and Unimpressive Markup Parser for XML and HTML documents. It provides a fast and lenient parser, allowing you to chuck all sorts of malformed data at it. Since it integrates with a bunch of my other systems, it's a pretty good choice for HTML.

post-all

This is a small library to allow you to post content to multiple services at once. I use this to post my art online, as there's a couple of different places I'd otherwise have to upload to manually every time.

purplish

Purplish is yet another Radiance application. It provides you with a slick and simple image board software. If you ever want to run a chan, this could be a good choice.

qt-libs

This system provides you with the Qt4 library binaries. Usually all you have to do is load this system, and you'll be set up and ready to go writing Qt applications. It also includes tools to automatically build the libraries from scratch.

qtools

Qtools allows you to write Qt GUIs in a syntax and manner much more similar to how you'd write any other Lisp code. It provides all sorts of conveniences and abstractions to make life a whole lot easier.

qtools-ui

This is a collection of UI components and systems that Qt does not provide on its own. Being completely written in Lisp, it is also ripe for extension and adaptation in your own projects. If you have a reusable component that you wrote, it would be a great idea to integrate it here, so that others can benefit as well.

random-state

Random-state gives you access to a bunch of different random number generation algorithms, and allows you to portably seed them. This is primarily useful where number generation needs to be controllable.

ratify

This system allows you to verify and parse a variety of string-based formats. It is primarily geared towards validating input from web forms, or other unauthorised sources.

redirect-stream

A tiny library implementing a gray stream that redirects the output written to it to another stream. This is useful when you want to switch out the stream of a particular system on the fly.

A small library to do simple task issuing and processing. You create tasks that execute some code, and then send them off to be processed on a dedicated background thread.

trivial-arguments

This gives you a single function, which returns the lambda-list of a function, if the list is known. Useful for introspective and descriptive tasks.

trivial-benchmark

A small library to do simple benchmarking work. This library uses CLOS to be easy to extend, which incurs a bit of overhead for the benchmarks themselves. Thus, it is sadly not suitable for micro-benchmarking.

trivial-indent

If you make a macro with a bit of a more advanced syntax, it's likely Slime will not pick up the proper indentation for it. With this, you can help it out by declaring the proper indentation form manually.

Sometimes it's necessary to ensure that code is run in the main thread, especially when you want to do graphics on OS X. This library helps you with that.

trivial-mimes

The detection and handling of mime-types for files is sometimes necessary to validate the correctness of a specified content type. This library implements both a binary lookup, and a file-name lookup.

trivial-thumbnail

This tiny library uses the ImageMagick binaries to create thumbnails of images for you.

ubiquitous

Ubiquitous provides a persistent configuration storage. It gives you convenient traversal through the configuration and offers easy file-based serialisation for a good range of Lisp object types. If you need your application to be configurable through external files, or just need a simple storage, check a look!

Other Stuff

That's about it. I have a bunch of other projects that I haven't mentioned here, either because they're old, abandoned, not even close to finishing, or simply uninteresting.

Since I'm constantly doing things, this list is bound to become outdated before long. So, please be mindful of the date. When in doubt, just look at the project's own page, or contact me directly. I love to chat, so even if you don't care about any of this, I definitely wouldn't mind if you stopped by at #shirakumo on Freenode some time.

Quicklisp news — Something to try out: Quicklisp with OpenPGP and SHA verification

· 57 days ago
I've got a test version of Quicklisp available. It uses pure Common Lisp code to verify file SHA digests and OpenPGP signatures, from bootstrap to library loading.

To try it out, fetch the following file:

https://www.quicklisp.org/tmp/quicklisp.lisp

The PGP public key for Quicklisp releases is embedded directly in quicklisp.lisp, but you can also fetch it from another source and use :public-key-file "/path/to/separate/key" as an argument to quicklisp-quickstart:install to use a specific key file.

If you do try it, move your existing, working Quicklisp install out of the way first, or use the :path option to install to a test location. Otherwise, you could clobber a working Quicklisp setup.

This verification code slows things down a bit because it does a lot of arithmetic. The slowdown is most dramatic in implementations like ABCL and CLISP.

If everything works as it should, you won't notice anything very different from the normal Quicklisp install, except some slowdown during verification and some output indicating what checks were attempted and passed.

If you run into problems where something doesn't work as you expect, please let me know at zach@quicklisp.org.

Thanks!

Paul Khuong — Rendezvous Hashing: My Baseline "Consistent" Distribution Method

· 60 days ago

2017-10-15: Tweaked the hash merge function to actually deliver the claims (one-universality isn’t enough).

Whenever I mention a data or work distribution problem where I ideally want everything related to a given key to hit the same machine, everyone jumps to consistent hashing. I don’t know how this technique achieved the mindshare it has, although I suspect Amazon’s 2007 Dynamo DB paper is to blame (by introducing the problem to many of us, and mentioning exactly one decentralised solution)... or maybe some Google interview prep package.

Karger et al’s paper doesn’t help, since they introduce the generic concept of a consistent hash function and call their specific solution... “consistent hashing.” I’m not sure where I first encountered rendezvous hashing, but I vaguely remember a technical report by Karger, so it’s probably not some MIT vs UMich thing.

Regardless of the reason for consistent hashing’s popularity, I feel the go-to technique should instead be rendezvous hashing. Its basic form is simple enough to remember without really trying (one of those desert island algorithms), it is more memory efficient than consistent hashing in practice, and its downside–a simple implementation assigns a location in time linear in the number of hosts–is not a problem for small deployments, or even medium (a couple racks) scale ones if you actually think about failure domains.

Side question: why did rendez-vous have to lose its hyphen to cross the Channel?

Basic rendezvous hashing takes a distribution key (e.g., a filename), and a set of destinations (e.g., hostnames). It then uses a hash function to pseudorandomly map each (distribution_key, destination) pair to a value in [0, 1) or [0, 2^64 - 1), and picks the destination that gives the minimal hash value. If it needs k destinations for redundancy, it can pick the destinations that yield the least k hash values. If there are ties (unlikely with a good hash function), it breaks them arbitrarily but consistently, e.g., by imposing a total order on hostnames.

A Python implementation could look like the following.

basic rendezvous hashing
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  Destination = namedtuple('Destination', ['host', 'hash']) def merge_hashes(x, y): """murmurhash3 mix. Alternatively, ((x | 1) * (y | 1)) % 2**64 should be fine. """ acc = x ^ y acc ^= acc >> 33 acc = (acc * 0xff51afd7ed558ccd) % 2**64 acc ^= acc >> 33 acc = (acc * 0xc4ceb9fe1a85ec53) % 2**64 acc ^= acc >> 33 return acc def pick_destinations(key, destinations, k=1): key_hash = hash_key(key) # hash the key once, instead of hash(key + host) annotated = [(merge_hashes(key_hash, dest.hash), dest.host) for dest in destinations] ordered = sorted(annotated) # lexicographic sort on merged hash, host. return [host for _, host in ordered[:k]] # grab host from the first k 

We only need to store the list of destinations, and we can convince ourselves that data distribution is pretty good (close to uniform) and that small changes in the set of destinations only affects a small fraction of keys (those going to destinations added/removed), either with pen and paper or with a few simulations. That compares positively with consistent hashing, where a practical implementation has to create a lot (sometimes hundreds) of pseudo-nodes for each real destination in order to mitigate clumping in the hash ring.

The downside is that we must iterate over all the nodes, while consistent hashing is easily $$\mathcal{O}(\log n)$$ time, or even $$\mathcal{O}(\log \log n)$$, with respect to the number of (pseudo-)nodes. However, that’s only a problem if you have a lot of nodes, and rendezvous hashing, unlike consistent hashing, does not inflate the number of nodes.

Another thing I like about rendezvous hashing is that it naturally handles weights. With consistent hashing, if I want a node to receive ten times as much load as another, I create ten times more pseudo-nodes. As the greatest common divisor of weights shrinks, the number of pseudo-node per node grows, which makes distribution a bit slower, and, more importantly, increases memory usage (linear in the number of pseudo-nodes). Worse, if you hit the fundamental theorem of arithmetic (as a coworker once snarked out in a commit message), you may have to rescale everything, potentially causing massive data movement.

Rendezvous hashing generates pseudorandom scores by hashing, and ranks them to find the right node(s). Intuitively, we want to use weights so that the distribution of pseudorandom scores generated for a node A with twice the weight as another node B has the same shape as that of node B, but is linearly stretched so that the average hash value for A is twice that for B. We also want the distribution to cover [0, infty), otherwise a proportion of hashes will always go to the heavier node, regardless of what the lighter node hashes to, and that seems wrong.

The trick, as explained by Jason Resch at Cleversafe, is to map our hashes from uniform in [0, 1) to [0, infty) not as an exponential, but with -weight / log(h). If you simulate just using an exponential, you can quickly observe that it doesn’t reweigh things correctly: while the mean is correctly scaled, the mass of the probability density function isn’t shifted quite right. Resch’s proof of correctness for this tweaked exponential fits on a single page.

The Python code becomes something like:

weighted rendezvous hashing
 1 2 3 4 5 6 7 8 9 10 11 12 13  Destination = namedtuple('Destination', ['host', 'hash', 'weight']) def score(hash_value, weight): return -weight / math.log(hash_value / HASH_MAX) def pick_destinations(key, destinations, k=1): key_hash = hash_key(key) annotated = [(score(merge_hashes(key_hash, dest.hash), dest.weight), dest.host) for dest in destinations] ordered = sorted(annotated) return [host for _, host in ordered[:k]] 

There are obvious micro-optimisations here (for example, computing the inverse of the score lets us precompute the reciprocal of each destination’s weight), but that’s all details. The salient part to me is that space and time are still linear in the number of nodes, regardless of the weights; consistent hashing instead needs space pseudolinear(!) in the weights, and is thus a bit slower than its $$\mathcal{O}(\log n)$$ runtime would have us believe.

The linear-time computation for weighted rendezvous hashing is also CPU friendly. The memory accesses are all linear and easily prefetchable (load all metadata from an array of nodes), and the computational kernel is standard vectorisable floating point arithmetic.

In practice, I’m also not sure I ever really want to distribute between hundreds of machines: what kind of failure/resource allocation domain encompasses that many equivalent nodes? For example, when distributing data, I would likely want a hierarchical consistent distribution scheme, like Ceph’s CRUSH: something that first assigns data to sections of a datacenter, then to racks, and only then to individual machines. I should never blindly distribute data across hundreds of machines; I need to distribute between a handful of sections of the network, then one of a dozen racks, and finally to one of twenty machines. The difference between linear and logarithmic time at each level of this “failure trie” is marginal and is easily compensated by a bit of programming.

The simplicity of basic rendezvous hashing, combined with its minimal space usage and the existence of a weighted extension, makes me believe it’s a better initial/default implementation of consistent hash functions than consistent hashing. Moreover, consistent hashing’s main advantage, sublinear-time distribution, isn’t necessarily compelling when you think about the whole datacenter (or even many datacenters) as a resilient system of failure-prone domains. Maybe rendezvous hashing deserves a rebranding campaign (:

François-René Rideau — A tale of many nests

· 61 days ago

This short essay will tell you about my favorite macro, nest, discuss the modularity of syntax extension, and use the implementation of that macro as an illustration for how to use defmacro, syntax-rules and syntax-case, providing along the way a comparison between these respective macro definition systems.

Using the nest macro

When I started using Scheme as my main Lisp, the first macro I wrote was the nest macro. What macro? The nest macro. The one that in Common Lisp helps my code avoid drifting hopelessly to the right as I nest binding form inside binding form... by doing the nesting for me. To illustrate the kind of issues that I'm concerned with, consider the Common Lisp code snippet below:

(multiple-value-bind (a1 b1 p1) (foo1)
(with-open-file (f1 p1 ...)
(when x1
(multiple-value-bind (a2 b2 p2) (foo2)
(with-open-file (f2 p2 ...)
(when x2
(bar x1 x2 ...))))))))


You're doing the same thing twice, but because of all those binding forms, the code moves right, the symmetry is broken, and the line limit makes you cut your lines more and more as you nest more forms, until you run out of space. It's really ugly. So much so that it makes me miss block-oriented languages in the ALGOL tradition (like C, OCaml or Python) where all the bindings (at least simple ones) go at the same level of indentation, and symmetry is preserved between consecutive bindings, and the line limit isn't an increasing threat as my functions get more complex.

Of course, it is always better when you can break down your functions into simpler chunks, at which point it doesn't matter that you move a little bit to the right, because no function is long enough for this right shift to matter much. However, when you are really computing some correspondence between two (or more) sets of entities, there's no way around doing a lot of nested bindings before you have all the input elements aligned together in a way that you can even start your computation. That's what happened for instance with my famous macros implementing the isomorphisms between pure and stateful data structures and between interface-passing-style (typeclasses) and object-oriented style (classes): the more complex macros, to "classify" interfaces, had up to 18 levels of nesting. That's a lot of indentation, that reflects as much context to fit in your limited brain registers at once (and indeed, it took me over a month to complete the first in that series of macros). Happily there is a lot of symmetry, that will be more readily apparent if only your code doesn't have to get indented so much.

The traditional solution to this approach, in Common Lisp, was to invent a "mother of all" binding macro, that could replace all the other ones at once: Attempts at providing such universal binding form include metabang-bind, let+, at least one attempt internal at ITA that I saw, and probably many more attempts that I don't know about, not to mention pattern matchers like my old fare-matcher and its better replacements optima and trivia. Now, the problem with this approach is that whoever writes this universal binding form must offer a way to supersede each and every binding form in the language. But since the language is extensible and people keep defining new binding forms (especially using CALL-WITH-* style), the task is an endless, sisyphean endeavor. What more, it is also a modularity nightmare, as there is no clear responsible party for each of the N*M extensions of N universal binding forms to each match each of M new kinds of bindings. I believe the best universal binding system in town these days is trivia, the extensible pattern matcher; but even it has only limited mind share. (Of course, I'm partial to pattern matchers: when, decades ago, I switched from OCaml to Common Lisp, I missed pattern-matching so much that the first thing I did was to write the first ML-style pattern matcher for Common Lisp; which could of course be done within the language using macros.)

As I was discussing this topic a few years ago, and potential extensions to macro-expanders to support capture of syntactic "block" continuations so they would work well with python-like syntax, my then colleague Marco Baringer, of arnesi fame, told me about this beautiful, simple solution that he knew of: the nest macro. This one remarkable macro already supports all binding forms past, present and future, without anyone having to write any code whatsoever to extend it — because it trivially embraces the syntax of them all with one weird trick: recognizing that all binding macros end with a body of code inside which the variable are bound, and nesting each form passed to the macro inside the body of the previous form, at the end. Thus, for instance the above snippet is flattened this way:

(nest
(multiple-value-bind (a1 b1 p1) (foo1))
(with-open-file (f1 p1 ...))
(when x1)
(multiple-value-bind (a2 b2 p2) (foo2))
(with-open-file (f2 p2 ...))
(when x2)
(bar x1 x2 ...))


Notice how all these binding forms are now neatly indented at the same level! Remark that each of the forms is closed before its body ends (sometimes before its body begins), said body being present or completed in the next form. And see how it also works for forms that are not binding forms, but still provide context for the body inside, such as the when forms. And note that if you didn't want your when form to wrap around all the rest, but simply to contribute a side-effect before the rest is evaluated, then you might want to wrap your when form inside a progn form (in Common Lisp) or begin form (in Scheme), that would provide this sequential behavior. Thus the nest macro works not only with binding forms, but with all kinds of expressions. Better yet, the nest macro even works with forms that are not expressions stricto sensu (though the overall form has to be an expression for the macro to be expanded)! For instance, it will work with case or match clauses:

(nest
(for-each! list1) (lambda (elem1))
(match elem1) ((list x1 y1 z1 ...))
(for-each! list2) (lambda (elem2))
(match elem2) ((list x2 y2 z2 ...))
(begin (assert (equal x1 x2)) ...)
(case (foo y1 y2) ((A B C ...) easy-caseA ...) ((D E F ...) easy-caseD ...))
((G H I ...) (hard-caseG main-body ...)) ...)


Notice how the (list x1 y1 z1 ...) or the (G H I ...) are not expressions but one a matching pattern and the other a list of cases. Each of their syntactic roles is different from that of normal expressions, and each follows its own distinct grammar. That's some additional expressive power that the nest macro has in Lisp that other more sophisticated macros do not have in Lisp or in any other language. Notice also how this style allows to detach the lambda expressions and their bindings from the rest of their body (which covers the rest of the arguments to the nest macro), and to place the head of these lambda expressions right next to the calling expression that calls them and binds the lambda variables: thus it becomes very clear that elem1 will be bound to each of the elements in list1, or that x2 y2 z2 will be bound to elements of a list that matches the contents of elem2. Meanwhile, the body below each of these forms doesn't have to care what kind of form it is the body of. This is all a beautiful division of labor, with power, expressiveness, brevity, relevance, symmetry, etc. All that for the price of understanding one simple macro.

I like this macro so much that I made it available as UIOP:NEST, as part of UIOP, the Common Lisp "Utilities for Implementation- and OS- Portability", a library is transcluded in ASDF, the build system used by nearly all software written in Common Lisp today. Thus, every contemporary Common Lisp program can assume that this macro is readily available. And ASDF itself is making good use of the macro: the macro shines not just to keep indentation in check, but also in conjunction with Common Lisp reader conditionals, so that some wrapping forms are only used on relevant implementations and not other implementations.

Implementing the nest macro

But just how simple is the nest macro? So simple it's literally a one liner in Common Lisp:

(defmacro nest (&rest r) (reduce (lambda (o i) (,@o ,i)) r :from-end t))


That is, it is just a right fold (hence the :from-end t) on the list of forms r, to nest each (rightmost) form i into the end of the previous one o.

Now, moving to Scheme, the benefits of nest are about the same, just better, since there are even more higher-order function that call functions; if only we reorganize the order of their arguments so the function comes last (as with the for-each! variant of the standard for-each function above), then we can easily chain together the bindings and bodies of all these forms with the nest macro. And so, soon enough, I wrote a Scheme version of the nest macro. Here was my first, naive, attempt; can you tell what was wrong with it without reading what follows?

(define-syntax nest
(syntax-rules ()
((nest (x ...) y z ...) (x ... (nest y z ...)))
((nest x) x)))


This macro uses the simple but limited pattern-matching macro-defining macro syntax-rules. It recurses into each of the forms to nest by inserting itself as the head of successive shorter sub-lists of forms, that will recursively expand it, until a single form is left that is returned as the innermost form with nothing to nest in it. And the problem with this simple macro is... that the recursive inner form (nest y z ...) will only expand this inner nest if it is an expression, i.e. the kind of form that gets evaluated into a value by the evaluator (whether based on an interpreter, compiler, JIT, or whatever else), and corresponds to a single non-terminal of the language grammar. Therefore, the macro won't work when (y z ...) is a case or match clause, a type level expression, or anything but a normal expression (I was tempted to say regular expression or normal form, but these are terms of art with their own entrenched meaning). And so began my quest for a correct implementation of nest.

The difficulty here is that you really want to fold-right, starting with the inner form and bubbling up inside each consecutive outer form; but what was trivial to express recursively, yet not quite correct, was that fold-left above, assuming each nested form was an expression. My first correct solution used two macros as follows:

(define-syntax Rnest
(syntax-rules ()
;;((_ () ()) ()) ;; This case is an error, actually
((_ (rev ...) (one more ...)) (Rnest (one rev ...) (more ...))) ;; reverse the outer form list
((_ (x (y ...) z ...) ()) (Rnest ((y ... x) z ...) ())) ;; recursively nest
((_ (x) ()) x))) ;; return
(define-syntax nest
(syntax-rules ()
((_ x ...) (Rnest () (x ...)))))


The Rnest macro that does the job of nesting the forms, in two phases: first by reversing the list by accumulating its elements one by one into an accumulator list; and second by folding left on the accumulated list. Each step is tail recursive so the macro always remains in control of the expansion until the end, without having to rely on any sub-form to itself be an expression that partakes in the expansion protocol (syntax-rules, like maybe all but one macro systems, only allows macro-expansion for one kind of grammatical non-terminal, the expression; the only exception I know to this rule is Racket's syntax/parse, where multiple kind of grammatical non-terminals each can have their own macro extensions). The reverse step will be familiar to anyone who ever tried to prove correct an implementation of reverse in e.g. Coq; or to prove correct an implementation of append, which often involves the append-reverse function.

Now, exposing the binding to the Rnest macro above isn't very hygienic. Ideally, you'd like to have Rnest itself be lexically defined, such that it is seen by nest but not anything else. Here is how I eventually did it, after someone tipped me that (... ...) was the proper way of quoting the ellipsis ... so it could be present in nested macros:

(define-syntax nest
(syntax-rules ()
((_ x ...)
(letrec-syntax
((r
(syntax-rules ()
((_ (xx (... ...)) (y z (... ...))) (r (y xx (... ...)) (z (... ...)))) ;; reverse the list
((_ (xx (y (... ...)) z (... ...)) ()) (r ((y (... ...) xx) z (... ...)) ())) ;; nest
((_ (xx) ()) xx)))) ;; bottom case
(r () (x ...))))))


Note how it's essentially the same macro as previously, except for some ugly renamings: the internal version of Rnest is just called r, but its ellipsis has to be quoted as (... ...), and its variable x has to be renamed xx not to clash with the outer x that further demands to be used with an ellipsis (unless I suppose you quote it everywhere as (... x)). So, this hygienic version of nest using syntax-rules works but is particularly ugly. That said, it is not quite as ugly as what I had to go through before I was told how to quote the ellipsis...

Without quoting the ellipsis, you can still use syntax-rules to define the nest macro, but now you have to get creative, and use tail-recursion only with continuation-passing style so that all your transformations are done without requiring expansion from any subform, none of which might be an expression. That's where we actually use this tail-recursive append-reverse macro rev-app (in the body of the macro, at the bottom of the definition); its continuation will be calling the left-folding macro nest-rev that nests the reversed list of forms. It's all straightforward if you know continuation-passing style applied to macros (or even just to functions in general; macros being just source-transforming functions):

(define-syntax nest
(syntax-rules ()
((_ . forms)
(letrec-syntax
((nest-error
(syntax-rules ()
((_ . args) (error "nest error" 'args))))
(rev-app ;; k ctx lst acc ==> k ctx ,(append (reverse lst) acc))
(syntax-rules ()
((_ k ctx (hd . tl) rev) (rev-app k ctx tl (hd . rev)))
((_ k ctx () rev) (k ctx rev))
((_ k ctx x ()) (k ctx x))))
(app ;; k ctx l1 l2 ==> (k ctx ,(append l1 l2))
(syntax-rules ()
((_ k ctx l1 l2) (rev-app app-ret (k ctx l2) l1 ()))))
(app-ret ;; (k ctx l2) rev-l1 ==> (k ctx ,(append (reverse rev-l1) l2))
(syntax-rules ()
((_ (k ctx l2) revl1) (rev-app k ctx revl1 l2))))
(nest-rev ;; given the reverse list of forms, setup the recursion
(syntax-rules ()
((_ () ()) (nest-error))
((_ () (final . more)) (nest-rev2 more final))))
(nest-rev2 ;; recurse
(syntax-rules ()
((_ () done) done)
((_ (form . more) done) (app nest-rev2 more form (done))))))
(rev-app nest-rev () forms ())))))


However, straightforward or not, this macro CPS work is extremely tedious; and if you want to do non-trivial processing in this style, you'll have to develop a library of macros in continuation-passing style to mirror each of the list-transforming functions you might have wanted to use if only you had the full power of the language while meta-programming. And then debugging meta-programs written this way will be atrocious, lacking adequate debugging support from your regular tools (the only exception here being Racket, that sports dedicated support for debugging macros). This horrible situation of having a braindamaged meta-programming language completely disconnected from your base language in which you must reinvent all data structures and libraries from scratch, without proper tooling, of course is remindful of template metaprogramming in C++, which, dreadful as it is, is still one of the more powerful of blub languages with respect to metaprogramming (then there is compile-time reflection in Java, but by the time you've handled all the boilerplate to do the simplest of things, you'll either have forgotten why you were doing it in the first place, or will have committed suicide in disgust — unless you embrace the Greenspunning and re-create Clojure or such).

Of course, if you're willing to assume that your nesting level will still remain small, and that macro-expansion of nested forms won't be a significant drag on your compilation time, then you could use this much simpler version that uses an O(n²) algorithm instead of an O(n) algorithm, by expressing your fold-right in a more direct though less efficient way (implementation courtesy of gwatt on IRC #Scheme):

(define-syntax nest
(syntax-rules ()
((nest x) x)
((nest x ... (y ...) z) (nest x ... (y ... z)))))


Now, all this may have finished convincing you that while syntax-rules makes it simple to write simple macros, it might not be the best tool to write more elaborate macros that do not fit its simplistic assumptions. It is then time to unleash a more powerful macro-defining macro, syntax-case. Syntax-case, like syntax-rules, is hygienic, in that it tracks source location and naming contexts, so that you don't have to do it manually and carefully insert gensym everywhere; but unlike syntax-rules, it is not limited to a simple pattern language, it allows for metaprogramming using the very same language. Here is a straightforward version of the nest macro using syntax-case:

(define-syntax (nest stx)
(syntax-case stx ()
((nest . xs)
(let loop ((forms (syntax->list #'xs)))
(cond
((null? forms) #'xs)
((null? (cdr forms)) (car forms))
(else #(#,@(syntax->list (car forms)) #,(loop (cdr forms)))))))))


The above loop follows the same naive approach as we were initially trying to use with syntax-rules: it manually does a left fold on the list of forms; unlike the syntax-rules version, though, it works even if the forms are not expressions, because we recurse directly inside the macro-expanding function, rather than by hoping that the next form will be an expression that recursively macro-expands. Recursion is much easier and nicer to use with syntax-case, because you have the full power of your language as a meta-language, instead of an ad hoc term-rewrite engine.

Now, if the #(#,@ characters looked like line noise to you, they were quasisyntax and unsyntax-splicing, the syntax-case analogue to quasiquote and unquote-splicing that you use with Common Lisp style macros. But if quasisyntax is alien to you or unimplemented in your Scheme, you can also manipulate the syntax directly, using the datum->syntax and syntax->list primitives:

(define-syntax (nest stx)
(syntax-case stx ()
((nest . xs)
(let loop ((forms (syntax->list #'xs)))
(cond
((null? forms) #'xs)
((null? (cdr forms)) (car forms))
(else (datum->syntax #'nest
(append (syntax->list (car forms)) (list (loop (cdr forms)))))))))))


Of course, instead of doing the recursion manually, you could explicitly use a left fold, just like the reduce in Common Lisp (there again thanks to gwatt for his help):

(define-syntax (nest stx)
(syntax-case stx ()
((nest outer ... inner)
(foldl (lambda (o i) #(#,@o #,i)) #'inner (reverse (syntax->list #'(outer ...)))))))


And there again, we can write the same thing without quasisyntax:

(define-syntax (nest stx)
(syntax-case stx ()
((nest outer ... inner)
(foldl (lambda (o i) (datum->syntax #'nest (,@(syntax->list o) ,i)))
#'inner (reverse (syntax->list #'(outer ...)))))))


And of course we can directly use a right fold, instead of a left fold on the reverse. That's very similar to the Common Lisp macro, just with some extra wrapping and unwrapping to maintain hygiene.

(define-syntax (nest stx)
(syntax-case stx ()
((nest outer ... inner)
(foldr (lambda (o i) #(#,@o #,i)) #'inner (syntax->list #'(outer ...))))))


And as always, we can do it without quasisyntax, instead using quasiquote to implicitly express a call to the append function:

(define-syntax (nest stx)
(syntax-case stx ()
((nest outer ... inner)
(foldr (lambda (o i) (datum->syntax #'nest (,@(syntax->list o) ,i)))
#'inner (syntax->list #'(outer ...))))))


Now the macro is so simple, with a single trivial pattern to match, that you could even write the expander directly without syntax-case:

(define-syntax (nest stx)
(let ((forms (syntax->list stx)))
(let loop ((more (cdr forms)))
(cond
((null? more) #'stx)
((null? (cdr more)) (car more))
(else (datum->syntax (car forms) ;; in Racket, stx would do
(append (syntax->list (car more)) (list (loop (cdr more))))))))))


Also, you could use syntax->datum instead of syntax->list but that would needlessly lose syntax location data on the recursive objects:

(define-syntax (nest stx)
(syntax-case stx ()
((nest . xs)
(datum->syntax #'nest ;; Gerbil wants an identifier; Racket works well with stx.
(let ((forms (reverse (syntax->datum #'xs))))
(let loop ((acc (car forms)) (more (cdr forms)))
(if (null? more)
acc
(loop (,@(car more) ,acc) (cdr more)))))))))


Last but not least, here is the version I actually use in my code, as proposed by vyzo. It uses ellipses to do the appending directly on syntax; to achieve this, it first uses with-syntax to establish a binding between the macro's runtime variable o and i and the macro's compile-time syntax variables outer and inner; outer can then use the ellipsis to express the appending (note that Gerbil unlike Racket does not need the (syntax->list ...) wrapper):

(define-syntax (nest stx)
(syntax-case stx ()
((nest outer ... inner)
(foldr (lambda (o i)
(with-syntax (((outer ...) o)
(inner i))
#'(outer ... inner)))
#'inner (syntax->list #'(outer ...))))))


So there, we've seen a simple macro, nest, how it interestingly trivializes a problem that others tried very hard to solve with extremely elaborate macros, how it can be implemented in three different widely used macro systems, and what are some issues with writing macros in Scheme rather than Lisp — the price you pay for hygiene (mind that just because I do not discuss the benefits does not mean there aren't such very valuable benefits). Note that this macro is pretty much the worst case scenario when translating a Common Lisp macro into a Scheme macro: it doesn't use any gensym so doesn't benefit from any of the hygiene machinery, and its pattern is just a bit off from what is easy with syntax-rules. Yet in the end, it isn't too hard to translate it. Translating it was a good exercise in learning Scheme macro systems.

Nicolas Hafner — Portacle Release - Confession 75

· 78 days ago

I've written about Portacle on a previous occasion, where I talked mostly about the issues I've faced. This time, however, I'm excited to announce that Portacle has finally reached version 1.0. This means that there are no obvious remaining issues that I am aware of. Everything should Just Work™.

In case you're confused about what Portacle even is, it stands for the Portable Common Lisp development Environment. It's a combination of Emacs, SBCL, Quicklisp, GIT, and a variety of other, smaller components that together bring you a fully-fledged IDE that runs on the three major operating systems in use today. It is installable with a simple extraction and fully contained in its own directory. It can thus be loaded onto a USB stick for use on the go as well.

Portacle is primarily intended to target both complete newcomers, for which the installation procedure of a full Emacs setup otherwise involves a lot of confusing and complicated steps, and advanced users that simply need a quick way to set up a running environment on a machine. Portacle is especially convenient to test your libraries on different systems.

I have personally tested Portacle to run properly on the following platforms:

• Windows 7
• Windows 10
• OS X 10.11
• OS X 10.12
• Ubuntu 16.04
• Linux Mint 17.3
• Debian 8
• Fedora 25
• Arch Linux

Note that currently the following platform versions are supported:

• Windows 7+ x64
• OS X 10.11+ x64
• Linux 3.13+ x64

You can download the current release here. If your system falls within these constraints and Portacle won't run properly for you, please do file an issue so that I can see what else needs fixing.

If you otherwise have suggestions regarding documentation extension, adding features, or smoothing out rough edges, please file an issue as well, or hop onto the #shirakumo IRC channel on Freenode to chat directly with me. I'd be happy to hear your thoughts.

Zach Beane — September of Sly

· 78 days ago

I like the idea of sly: like slime, but cooler. Less conservative with changes, less concerned about backwards-compatibility, more features, cleaner implementation, etc. But I don’t know that much about it in detail, and I’ve never tried it - until now.

I’m going to use sly exclusively for the month of September. As I bump into differences from slime, I’m taking notes and will share them here. I hope to give people an idea about what it’s like to switch and help them decide if it’s worthwhile for them, and figure out if I’ll be switching back on October 1.

So here are a few quick notes from getting started:

• Pretty easy to install, but not as easy as quicklisp-slime-helper - I can make a sly-helper in the future
• Would not start initially because I had a reference to the swank package in my ~/.swank.lisp file. Referencing swank in a swank init file seems reasonable so it was a little annoying to have to add some #+swank/#+sly conditionalization.
• I use slime-selector a lot, and it’s moved into a keymap in sly - I like that it now uses a standard Emacs UI instead of a custom UI
• …but it’s missing the “l” binding, which I use a hundred times a day, so I wrote a little bit of elisp to add it back
• docstring of sly-selector-map helps explain what to do
• Window management in sly-selector confuses me - expect REPL to replace current window, but it seems to go somewhere else every time
• comma commands are different! I use ,chTAB and ,cdRET a hundred times a day, and now they are ,set package (which has nice completion) and ,set directory
• Much more verbose repl output for integers at least:
• (+ 1 1) => 2 (2 bits, #x2, #o2, #b10)
• M-RET in REPL history does what I expect
• Not 100% sure how to get started with stickers, but C-c C-s ? has good starting points

Stay tuned for more!

· 80 days ago

What is FiveAM?

FiveAM is a simple-yet-mature test framework. It makes test suites for your project easy to implement, maintain, organize and run.

Motivation

While it can't be said that there are no learning materials provided for FiveAM, it feels like they are lacking in both clarity and detail. Beginners are in need of gentle, friendly guidance. Experienced Lisp hackers are able to make do without it, but even they probably spend a little extra time tinkering, experimenting and skimming source code to "get" the framework. This shouldn't be necessary.

This tutorial assumes familiarity with Common Lisp and a basic understanding of ASDF system definitions.

Our building blocks

We will start with a bit of theorizing. Be not afraid, however - there won't be too much of it.

The essential terms you will need to be familiar with are:

• Checks
• Tests
• Test suites

Checks

A check is, essentially, a single assertion - a line of code that makes sure something that should be true is indeed true. FiveAM tries to make assertions as simple as possible. The form of a basic check definition looks like this:

(is test &rest reason-args)

In this case,test is the assertion we want to make. A function (or special operator) application with any number of arguments can be used as the assertion. If it returns a true value, the assertion succeeds; if it returns NIL, it fails.

If the test parameter matches any of the 4 "templates" below, FiveAM will try to reason a little about what is what and attempt to print the explanations of failures in a more readable way. Arguably.

(predicate value)
(predicate expected value)
(not (predicate value))
(not (predicate expected value))

The logic FiveAM follows when reasoning is thus:

The first expression checks whether value satisfies predicate.

In the second one, the predicate is usually some form of equality test. The assertion makes sure the value we got (by calling some function we're testing) matches the expected value according to the predicate.

The last two tests are the same things, only negated.

In practice, these declarations look like this:

(is (listp (list 1 2)))   ; is (list 1 2) a list?
(is (= 5 (+ 2 3)))        ; is (+ 2 3) equal 5?

Simple, right? If we were implementing standard Lisp functions, we could use the above to test whether list generates a list as it should, and whether + sums properly. Or, well, at least we'd ascertain that for the above cases.

And if we wanted to negate:

(is (not (listp (list 1 2))))  ; is (list 1 2) not a list?
(is (not (= 5 (+ 2 3))))       ; is (+ 2 3) not equal 5?

As you may have noticed, we haven't used the optional reason-args argument. It's used to specify what's printed as the reason for a failed check. Sometimes FiveAM's reasoning just isn't good enough. We will get back to it when we start hacking away.

Tests

We know how to write checks, but there's not much we can actually do with just this knowledge. The is syntax is only available in the context of a test definition.

A test, as defined by FiveAM, is simply a collection of checks. Each such collection has a name so that we can easily run it later. Defining one is easy:

(test test-+
"Test the + function"     ;optional description
(is (= 0 (+ 0 0)))
(is (= 4 (+ 2 2)))
(is (= 1/2 (+ 1/4 1/4))))

We're sticking to the basics for now, but you should know there are some additional keyword parameters you can pass in order to declare dependencies, explicitly specify the parent suite, specify the fixture, change the time of compilation and/or collect profiling information.

A fixture is something that ensures a test is run in a specific context. Sometimes it's necessary to reproduce results consistently. For example, if you had a pathfinding algorithm, you'd probably have to load some sort of a map before you could test it. Apparently, using FiveAM's fixture functionality isn't recommended by the current maintainer. Perhaps it's best to just set up macros for those.

As for profiling information, this functionality doesn't seem to actually be implemented yet. Instead, Metering is a good option if needed.

You'll most likely end up defining a single test for a single function, but nothing stops you from slicing the pie up differently. Maybe a particularly complex function requires a lot of checks that are best divided into categories? Maybe a set of simple, related functions can be covered by a single test for simplicity? Your common sense is the best advisor here.

Suites

The final piece of the puzzle. These are not obligatory, but very useful. Suites are containers for tests, good if you need more hierarchy - which, honestly, you will. Speaking of hierarchy: suites can parent other suites, so you can have plenty of that.

The way suites are defined and used is roughly analogous to packages.

(def-suite tutorial-suite
:description "A poor man's suite"
:in some-parent-suite)

(in-suite tutorial-suite)

The first form defines a test suite called tutorial-suite. The in keyword is used to set the parent suite.

Just like in-package sets the *package* special variable, in-suite sets the *suite* one. Test definitions pick up on it when provided. Thanks to that, any test definitions after (in-suite tutorial-suite) will be included in tutorial-suite. Other suite definitions, however, won't be automagically contained in the suite pointed to by *suite*. For that reason, you always need to explicitly set the in keyword when defining a child suite.

And that's actually all there is to suites.

The story so far

Time for a quick summary - from the top, our tests are organized like this:

• (optional) Top-level test suites defined with (def-suite)
• (optional) Child test suites defined with (def-suite) with :in set
• Tests defined with the (test) macro
• Checks (assertions) defined with (is) expressions within a (test) form

A practical example

Now that all that is clear, let's try doing something with it. Imagine you are building an RPG game according to some existing pen-and-paper system. One day, it will surely rival the likes of AAA+ titles out there.

...for now, though, you only have the character generation facility down. Oh well, got to start somewhere. According to the specification of the system you're using, the stats of a character are generated randomly, but prior to the generation, a player can choose two stats they wish to "favor". Unfavored stats are decided on with a roll of two 8-sided dice, while favored ones - a roll of three 8-sided dice. You've defined a little utility function for rolling an arbitrary number of dice with an arbitrary number of sides.

You've written this basic functionality, wrapped it up in a package, defined an ASDF system, checked that everything compiles without warnings... So far, so good. But now you want to go the extra mile to make sure this is going to be a well-built piece of software. You want to integrate tests.

If you'd like to follow all the outlined steps and integrate FiveAM with me, just clone the master branch of the quasirpg repository.

git clone https://github.com/uint/quasirpg.git

Ideally, if you have quicklisp, do that in ~/quicklisp/local-projects/. Otherwise, clone the repository to either ~/common-lisp/ or ~/.local/share/common-lisp/source/.

If you wish, you can also look through the commit history of the test branch to see exactly how I've done all the work detailed in the following sections. It might come in useful if you get stuck.

If you want to see the code in action, try these:

CL-USER> (ql:quickload 'quasirpg)
CL-USER> (in-package #:quasirpg)
QUASIRPG> (roll-dice 3 6) ; throw three 6-sided dice
QUASIRPG> (make-character)
QUASIRPG> (make-character "Bob" '("str" "int"))

In case you don't have quicklisp, you can use this to load the system:

CL-USER> (asdf:load-system 'quasirpg)

Keep in mind that without quicklisp, you will also have to download FiveAM by hand. In the same directory you cloned quasirpg to, try:

git clone https://github.com/sionescu/fiveam.git

Groundwork

Tests shouldn't be a part of your software's main system. Why would they be? People who simply want to download your application and use it don't need them. Neither do they need to pull FiveAM as a dependency. So let's define a new system for tests. We could create a separate .asd file, but I like to have just one .asd file around. In this case, any additional systems defined after the main quasirpg one should be named quasirpg/some-name. So we append this to our quasirpg.asd:

(asdf:defsystem #:quasirpg/tests
:depends-on (:quasirpg :fiveam)
:components ((:module "tests"
:serial t
:components ((:file "package")
(:file "main")))))

We also create the new files tests/package.lisp and tests/main.lisp to make true to the above declaration. As you might guess, we're planning to define a separate package for tests. This isn't as important as separate systems, but it's always good to keep namespaces separate. Nice and tidy.

;;;; tests/package.lisp

(defpackage #:quasirpg-tests
(:use #:cl #:fiveam)
(:export #:run!
#:all-tests))

And finally the star of the show:

;;;; tests/main.lisp

(in-package #:quasirpg-tests)

(def-suite all-tests
:description "The master suite of all quasiRPG tests.")

(in-suite all-tests)

(defun test-quasi ()
(run! 'all-tests))

(test dummy-tests
"Just a placeholder."
(is (listp (list 1 2)))
(is (= 5 (+ 2 3))))

Defining a simple, argument-less test runner for the whole system (test-quasi here) isn't strictly necessary, but it's going to spare us some potential headaches with ASDF.

We define a meaningless test just so we can check whether the whole setup works. If you've done everything correctly, you should be able to load the test system in your REPL

CL-USER> (ql:quickload 'quasirpg/tests)

and run the test runner

CL-USER> (quasirpg-tests:test-quasi)

Running test suite ALL-TESTS
Running test DUMMY-TESTS ..
Did 2 checks.
Pass: 2 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)

T
NIL

So far, so good!

ASDF integration

Integrating the tests with ASDF is a good idea. That way we get hooked up to the standard, abstracted way of triggering system tests. First, we add this somewhere to our quasirpg/tests system definition.

:perform (test-op (o s)
(uiop:symbol-call :fiveam :run! 'quasirpg-tests:all-tests))

From now on, we can run all-tests with:

CL-USER> (asdf:test-system 'quasirpg/tests)

Next, we tell ASDF that when someone wants to test quasirpg, they really want to run the quasirpg/tests test-op. Somewhere in the quasirpg system definition:

:in-order-to ((test-op (test-op "quasirpg/tests")))

Now all we need to do to test our game is:

CL-USER> (asdf:test-system 'quasirpg)

Most of the character generation system's math is within the dice-rolling function - it's probably a good idea to tackle that one. The only problem is it's not a very predictable one. We can, however, still do some useful things.

(defun test-a-lot-of-dice ()
(every #'identity (loop for i from 1 to 100
collecting (let ((result (quasirpg::roll-dice 2 10)))
(and (>= result 2)
(<= result 20))))))

(test dice-tests
:description "Test the roll-dice function."
(is (= 1 (quasirpg::roll-dice 1 1)))
(is (= 3 (quasirpg::roll-dice 3 1)))
(is-true (test-a-lot-of-dice)))

The first two checks simply provide arguments for which the function should always spew out the same values - we're throwing one-sided dice. Just... try not to think too hard about it.

The function test-a-lot-of-dice returns true only if every one of 100 throws of two 10-sided dice is within the expected bounds, that is 2-20. All we have to do is check whether that function returns true. We can just write (is (test-a-lot-of-dice)), but I recommend using is-true instead, since the way it prints failures is more readable in cases like this.

In all honesty, test-a-lot-of-dice could be improved in terms of optimization (for example by making it a macro that wraps the 100 checks in an and) or functionality (the parameters passed to roll-dice could be random). But this version is simple and sufficient for this tutorial.

Now let's see this thing in action.

Running test suite ALL-TESTS
Running test DICE-TESTS fff
Did 3 checks.
Pass: 0 ( 0%)
Skip: 0 ( 0%)
Fail: 3 (100%)

And there we go. We've just detected a bug that would never be caught by the compiler. A look at the first fail gives us a hint:

(QUASIRPG::ROLL-DICE 1 1)

evaluated to

0

which is not

=

to

1

A look at the function in question should be enough to see the problem.

  (let ((result (loop for i from 1 to n summing (random sides))))

What (random sides) does is generate a number from 0 to (sides - 1). That's not what we want.

  (let ((result (loop for i from 1 to n summing (1+ (random sides)))))

And now we re-run the tests:

Running test suite ALL-TESTS
Running test DICE-TESTS ...
Did 3 checks.
Pass: 3 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)

The true power of tests, however, is that if we now ever decide to modify our dice-throwing facility, any bugs we introduce by accident will most likely be caught by the tests already in place. And so we'll avoid nasty, hard-to-debug consequences further down the line. All that without having to test things by hand each time we make changes.

Handling invalid parameters

What happens when someone passes a non-positive integer to roll-dice? Or a fractional one? We should probably control that behavior. And we should probably test to make sure when the unexpected happens, it's handled as expected.

Let's say our specification tells us that when any of the arguments is fractional, it should just be rounded down. So we append two additional tests to dice-tests:

  (is (= 3 (quasirpg::roll-dice 3.8 1)))
(is (= 3 (quasirpg::roll-dice 3 1.9)))

The first one actually passes. It just so happens that loop is responsible for looping N times over the random number generation for each die. loop rounds down a fractional number if it's passed one.

The second test requires our attention. It fails. The problem is that random is passed a fractional argument, and it thinks it's meant to give a fractional number in response. Simple fix and we're back on track:

  (let ((result (loop for i from 1 to n summing (1+ (floor (random sides))))))

Now for something more interesting. Let's say our specification tells us that if any argument is not a positive number, we should get a SIMPLE-TYPE-ERROR. It's time to introduce yet another kind of check.

(signals condition &body body)

Not a lot to explain here. BODY is expected to cause CONDITION to be signaled. Our check only succeeds if it does. We can use this:

  (signals simple-type-error (quasirpg::roll-dice 3 -1))
(signals simple-type-error (quasirpg::roll-dice 3 0))
(signals simple-type-error (quasirpg::roll-dice -1 2))
(signals simple-type-error (quasirpg::roll-dice 0 2))
(signals simple-type-error (quasirpg::roll-dice -1 1))

Again, some of the work is already done for us. random will signal a SIMPLE-TYPE-ERROR in response to a non-positive arg. What's left to do is to handle the number of throws, so we add the appropriate code to the beginning of roll-dice:

(if (< n 1)
(error 'simple-type-error
:expected-type '(integer 1)
:datum n
:format-control "~@<Attempted to throw dice ~a times.~:>"
:format-arguments (list n)))

And voila. Once more, all checks pass.

Random number generators

So far, we've used specific numbers. We can do better, though. We can run a large amount of checks based on random data. This is where the fiveam:for-all check comes in that runs tests 100 times, randomizing specified variables each time.

(for-all bindings &body; body)

bindings is a list of forms of this type:

(variable generator)

generator is a function (or function-bound symbol) that returns random data. variable is the variable binding that stores the results from generator.

body can contain other kinds of checks.

For example, let's try replacing (is-true (test-a-lot-of-dice)) with something more comprehensive.

(for-all ((n (gen-integer :min 1 :max 10))
(sides (gen-integer :min 1 :max 10)))
"Test whether calls with random positive integers give results within expected bounds."
(let ((min n)
(max (* n sides))
(result (quasirpg::roll-dice n sides)))
(is (<= min result))
(is (>= max result))))

(gen-integer :min 1 :max 10) is a function provided by FiveAM that returns a random integer generator with the specified bounds. We keep the numbers small here so that the tests don't take forever trying to throw a lot of dice, and so that there's a reasonable chance of edge cases getting tested.

We can also replace the rounding checks. Since FiveAM doesn't provide a suitable generator, we have to write our own. It's not difficult, though, thanks to CL's ease of creating higher-order functions:

(defun gen-long-float (&key (max (1+ most-positive-long-float))
(min (1- most-negative-long-float)))
(lambda () (+ min (random (1+ (- max min))))))

With that definition in place, we can write the new checks:

  (for-all ((valid-float (gen-long-float :min 1 :max 100)))
"Test whether floats are rounded down."
(is (= (floor valid-float) (quasirpg::roll-dice valid-float 1)))
(is (>= (floor valid-float) (quasirpg::roll-dice 1 valid-float))))

Finally, we can replace our condition checking too:

  (for-all ((invalid-int (gen-integer :max 0))
(invalid-int2 (gen-integer :max 0))
(valid-int (gen-integer :min 1)))
"Test whether non-positive numbers signal SIMPLE-TYPE-ERROR."
(signals simple-type-error (quasirpg::roll-dice valid-int invalid-int))
(signals simple-type-error (quasirpg::roll-dice invalid-int valid-int))
(signals simple-type-error (quasirpg::roll-dice invalid-int invalid-int2))))

If you run these tests, you'll notice only a few checks in the results. That's because FiveAM treats each for-all declaration as a single check, regardless of the contents or the hundreds of tests that actually get run.

REASON-ARGS

When the tests we've written failed, the output we got was mostly descriptive enough. That's not always the case. It's hard to expect the testing framework to know what sort of information is meaningful to us, or what the concept behind the functions we write is.

So let's say when we make-character, we want the name to be automatically capitalized. We care about punctuation and won't allow our players to get sloppy with it. Pshaw.

(test make-character-tests
:description "Test the make-character function."
(let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
(is (string= "Tom" name))))

Obviously, it fails.

 Failure Details:
--------------------------------
MAKE-CHARACTER-TESTS []:

NAME

evaluated to

"tom"

which is not

STRING=

to

"Tom"

..
--------------------------------

We can understand it, but put yourself in the position of someone who isn't all that familiar with the make-character function. Imagine that person just got the above output while testing the entire game. They're probably really scratching their head trying to piece this together. Let's make life easy for them. Attempt number 2:

(test make-character-tests
:description "Test the make-character function."
(let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
(is (string= "Tom" name)
"MAKE-CHARACTER should capitalize the name \"tom\", but we got: ~s" name)))

We use the &rest reason-args parameter of the is check. You can use format directives and pass it arguments, just like in a format call. Now the test result is much easier to interpret:

 Failure Details:
--------------------------------
MAKE-CHARACTER-TESTS []:
MAKE-CHARACTER should capitalize the name "tom", but we got: "tom".
--------------------------------

Reorganizing

Let's imagine what happens when the project grows. For one thing, we'll probably write many more tests, until having all of them in one file looks rather messy.

We'll also probably eventually end up reorganizing the code. roll-dice might eventually end up a part of a collection of utilities for generating randomized results, while make-character could get moved to chargen.lisp. It would be good if the hierarchy of our tests reflected those changes and let us test only random-utils.lisp or chargen.lisp if we want to.

So above all of our dice-testing code we tuck this in:

(def-suite random-utils-tests
:description "Test the random utilities."
:in all-tests)

(in-suite random-utils-tests)

Now all-tests contains random-utils-tests, which in turn contains dice-tests.

Let's do the same for character generation:

(def-suite character-generation-tests
:description "Test the random utilities."
:in all-tests)

(in-suite character-generation-tests)

(test make-character-tests
:description "Test the make-character function."
(let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
(is (string= "Tom" name)
"MAKE-CHARACTER should capitalize the name \"tom\", but we got: ~s" name)))

You can check that running (asdf:test-system 'quasirpg) still runs all of our tests, since it launches the parent suite all-tests. But we can also do (fiveam:run! 'quasirpg-tests::make-character-tests).

The next logical step is moving the test suites to separate files. If you wish to see how I've done it, just look at this commit or at the end result in the test branch.

What else is there?

A few different kinds of checks and a way to customize the way test results and statistics are presented.

So far, we've always used run! to run all the tests, which is really a wrapper for (explain! (run 'some-test)). You can, therefore, replace the explain! function with your own.

How can you learn about those things? The best I can do is point you to the FiveAM documentation and possibly source code.

Happy hacking!

Eugene Zaikonnikov — Also ALSA

· 82 days ago

After having some issues with microphone input handling in portaudio I took a shortcut and sketched Also ALSA: an interface to Advanced Linux Sound Architecture library. As the name suggests, it's not the first CL wrapping of it. It is however small, reasonably self-contained and can handle both input and output.

LGPL to comply with alsa-lib.

Quicklisp news — August 2017 Quicklisp dist update now available

· 85 days ago
New projects:
• cl-cognito — Amazon Cognito Utilities — BSD
• cl-conllu — Common Lisp corpus conllu utilities — Apache 2.0
• cl-json-helper — Handy extras for cl-json — BSD
• cl-moss — Common Lisp submission mechanism for Stanford's MOSS system — GPLv3
• configuration.options — An extensible configuration system that supports multiple option sources. — LLGPLv3
• gamebox-sprite-packer — A spritesheet packer for games. — MIT
• jose — JSON Object Signing and Encryption (JOSE) implementation — BSD 2-Clause
• pngload — A reader and writer for the PNG image format. — MIT
• poiu — Parallel Operator on Independent Units — MIT
• shorty — Shorten URLs using third-party services. — MIT
• trivial-file-size — Stat a file's size. — MIT
• trivial-project — A simple project skeleton generator with key-value substitution — BSD Simplified (2-clause)
• trivial-renamer — rename and manage categorized named objects — BSD 3-clause license
• trivial-with — Replace nested with-xxx invocations with a single with:all form — BSD 3-clause license

To get this update, use (ql:update-dist "quicklisp").

Enjoy!

Wimpie Nortje — Getting started with Common Lisp

· 88 days ago

Are you trying to get started with Common Lisp but find it difficult to make progress? People keep on saying that there are plenty free resources available online. Maybe you have even found most of them ... and yet the questions remain ... What is the Lisp syntax? Are there any libraries and how do I find them? Can I compile my program into a binary or are users forced to install a compiler?

The list goes on: What is the meaning of those asterisks around the *VARIABLE* names? Which implementation should I use? Where do I go for help when I get stuck?

How do I connect my IDE to the debugger because really ... who in their right mind want learn Emacs just to use Common Lisp?

There are plenty learning resources on the web. For free. In the wonderful world of Common Lisp you always have multiple choices to achieve your goal. Starting with the choice of which implementation you should use.

In some aspects this post is similar to many of the other "Getting Started" articles and in some aspects it is different. This is my take on which initial choices to make and why. The choices are neither better nor worse than the alternatives but importantly, they are not binding. At any point in the future you can switch away from any of the choices I made without severe impact on your progress. The important thing is to accept some set of initial choices and to get started. You will only discover through experience whether you agree or disagree with the choices.

Common Lisp is a vast ocean of possibilities, stretching infinitely and with no horizon... And here I am pretending to understand the MOP while trying not to end up in r/badcode, like a child playing in the surf...

Comment in the Crane library's source code

The steps

Before you can start working seriously you need a functional development environment. The Portacle project can give you a jump start here. It packages all the recommended tools to provide a ready-made Lisp development environment. If you choose this option configure Portacle then start with step 4 below. Installation instructions are on the Portacle page.

I prefer to install software natively. If you choose this option follow the steps from the beginning.

1. Set up a Lisp implementation.
2. Set up the library installer.
3. Set up the development environment.
4. Locate reference documentation.
5. Pick a project.

Set up an implementation

There are a number of Common Lisp implementations available, each with its own unique features. If you don't know why you need to use a specific implementation, use CCL (Clozure Common Lisp) or SBCL (Steel Bank Common Lisp). They are easy to set up because they don't have any external dependencies. Since Common Lisp is a standardised language you can trivially switch implementations later if you really need to.

Many people prefer SBCL. If your OS has an installation package for it, use that. Otherwise you can find the installation instructions on the website.

I prefer to use CCL because it has faster compile times than SBCL.

Install CCL

$svn co http://svn.clozure.com/publicsvn/openmcl/release/1.11/linuxx86/ccl Copy the file ccl/scripts/ccl64 to a directory that is in your path. On Linux a good place is /usr/local/bin. Rename it to "ccl" $ cp ccl/scripts/ccl64 /usr/local/bin/ccl

Edit the script in /usr/local/bin. Change CCL_DEFAULT_DIRECTORY=/usr/local/src/ccl to point to the place where you installed CCL

Start CCL

$ccl In the REPL, execute ? (format t "Hello world!") The command should print Hello world! Exit the REPL with ? (quit)  Set up the library installer The easiest way to obtain and install libraries is to use Quicklisp. The following steps set up Quicklisp in your Lisp implementation: 1. Download the setup script. In Linux it would be $ wget https://beta.quicklisp.org/quicklisp.lisp

2. Install Quicklisp in CCL:

Start CCL

$ccl In the REPL, execute (load "quicklisp.lisp") (quicklisp-quickstart:install) (ql:add-to-init-file)  3. Test the installation ? (ql:system-apropos "alexandria") The command should print information about the Alexandria library. Something like this: #<SYSTEM alexandria / alexandria-20170630-git / quicklisp 2017-07-25> #<SYSTEM alexandria-tests / alexandria-20170630-git / quicklisp 2017-07-25>  Set up a development environment Picking a text editor One of Common Lisp's biggest productivity advantages is the REPL (Read-Evaluate-Print Loop). It looks and functions a lot like the operating system's command line interface which executes commands as they are entered. Variables and defined functions remain available throughout the REPL session. New functions can be defined one at time. In contrast to languages like C where your program must be compilable before you can test any change, in the REPL you can compile only the function you want to test without having a complete application. To understand the implication, suppose you have function A which is called by many other functions throughout the application and you want to change A's argument list. In C you'd have to update all the functions that call A before you can compile the program to actually test the change. In Common Lisp you can make the change, update one function and test it. Only when you are satisfied with the results you have to update the other calling functions. The described workflow is completely possible with any random text editor and loading the source files directly in the REPL. After making and testing changes in the REPL only the final modifications need to be transferred to the source files. While using Lisp in this way is possible, there is a disconnect between the text editor and the Lisp implementation which can negate the advantages brought by the REPL. When the text editor is able to control the REPL it allows you to make exploratory changes directly in the source files then compile and test only the modifications. At the end of this exploratory cycle the source files are already up-to-date and all that remain is to update the rest of the calling functions. The tool that enables control over the REPL is called SLIME1. It is the most advanced and mature tool for this purpose and it is specifically developed for Emacs. SLIME has been adapted for use in other editors2 but they have fewer users and contributors and thus always lag behind the latest SLIME development. When setting out to learn Common Lisp the path of least resistance is to use Emacs, even with all its foreign concepts and non-standard shortcut keys. Once one appreciates the power and productivity because of SLIME it is easier to look past Emacs' aged appearance and arcane user interface. Install SLIME In the CCL REPL, run the following: ? (ql:quickload "quicklisp-slime-helper") Install Emacs Installing Emacs should be trivial. Most Linux distributions provide installation packages in their repositories and the Emacs web page provides installation instructions for Windows and macOS. When Emacs is working, edit or create the file ~/.emacs. To locate the file on Windows, use the File | Visit New File menu item and type ~/.emacs as the filename. Place the following code in .emacs. ;; Set up CCL (setq inferior-lisp-program "ccl") ;;Load Quicklisp slime-helper (load (expand-file-name "~/quicklisp/slime-helper.el"))  Exit and restart Emacs. Using Emacs Emacs' key bindings (i.e. shortcut keys) differ significantly from the standard shortcut keys used in most other editors. If you don't know some basics and your menu bar happens to become hidden you will be helpless. This is a bare minimum introduction to using Emacs so that you will be able to edit Lisp files and run them with SLIME. The EmacsWiki key reference page has a much more thorough list. Emacs shortcuts are a combination of a modifier key with a normal key. The modifiers are: • C - Control key. • M - Meta key. ALT on PCs and ⌘ on Apple. • S - Shift key. Key combinations are written as C-x which means press and hold Control and then press x.  C-x C-c Exit Emacs C-x C-f Open or create file C-x C-s Save file C-x k Close file M-w Copy selected text C-w Cut selected text C-y Paste text C-/ Undo C-x h Select all C-x b Switch between buffers M-x slime Start SLIME C-c C-z Switch to SLIME from a Lisp buffer C-c C-c Compile the function at the cursor C-c M-q Indent the function at the cursor C-up/down Move through history in SLIME buffer If you really want to do copy, cut and paste with the same keys used in other applications then you can search for Emacs CUA mode. Run "Hello world" Start SLIME M-x slime The first time you run SLIME there may be some delay while it is being compiled. When it is ready you should see the following in Emacs: ; SLIME 2.19 CL-USER>  In the REPL, execute CL-USER> (format t "Hello world!") You should see Hello world! printed on the screen. Programming and debugging With the power of the SLIME / Emacs combination and Common Lisp's "vast ocean of possibilities" there are many ways to use the tools. Each programmer will eventually develop his or her own distinct technique. Without spending too much time learning Emacs or SLIME early on one can become quite productive using the following approach: Big changes: 1. Edit a file 2. Save the file - C-x C-s 3. Jump to the SLIME REPL - C-c C-z 4. Load the file - (load "app.lisp") 5. Run the code - (some-function) Small changes 1. Edit a file 2. Save the file - C-x C-s 3. Compile the function - C-c C-c 4. Jump to the SLIME REPL - C-c C-z 5. Run the code - (some-function) Locate reference documentation When you get stuck Stack Overflow can be useful but often you get answers faster if you know about other sources of information. I posted previously on the topic of finding answers. Here is another list which is more relevant if you are only getting started. Learn the language Practical Common Lisp Naming conventions Lisp-lang Cliki Find libraries and their documentation Quickdocs Common Lisp Language reference HyperSpec Help with Emacs EmacsWiki Use SLIME more effectively SLIME manual More introductory material Articulate Lisp When all these are not enough Reddit r/lisp sidebar Pick a project To learn a new language you must write a program and for that you need a project. I have posted some ideas for beginner projects before but I think it is easier to stay motivated when you work on your own idea. With the project in hand you now have everything to start programming and learning. At the very beginning it is easier to write all the code in one file. Loading the program is straightforward and it removes a lot of extra variables introduced when system definition files and multiple source files come into play. They are essential for bigger programs but they cause an unnecessary mental burden when you are still finding your feet. The moment a single file becomes too convoluted to continue, stop programming and create a project skeleton with Quickproject. It creates a minimal project with all the necessary files to make it loadable with ASDF and Quicklisp. The steps to create a project skeleton are: (ql:quickload :quickproject) (quickproject:make-project "path/to/project/")  Deploy your program Common Lisp programs can be compiled into standalone executables or they can run from source code. Buildapp is my tool of choice for creating executables. I posted before on how use it. Server-side software are usually run from source code. Depending on how your application startup code looks like it can be as simple as ccl -l app.lisp Footnotes: 1. SLIME - The Superior Lisp Interaction Mode for Emacs. 2. See the "Tools" section in the Reddit sidebar Quicklisp news — July 2017 Quicklisp download stats · 105 days ago Here are the raw download stats for the top 100 projects in Quicklisp for July: 11470 alexandria 8732 babel 8521 closer-mop 7779 split-sequence 7534 trivial-features 7197 cffi 7170 iterate 7095 cl-ppcre 7061 bordeaux-threads 6863 trivial-gray-streams 6526 anaphora 6062 flexi-streams 5589 cl+ssl 5588 trivial-garbage 5327 trivial-backtrace 5122 let-plus 5071 nibbles 4811 cl-fad 4648 usocket 4353 puri 4124 cl-base64 4119 drakma 4107 local-time 4006 named-readtables 3949 chunga 3661 chipz 3201 ironclad 3164 esrap 3058 cl-unicode 3043 cl-interpol 3010 cl-yacc 2807 more-conditions 2789 md5 2526 utilities.print-items 2523 fiveam 2511 asdf-flv 2472 log4cl 2250 slime 2198 parse-number 2178 trivial-types 2154 trivial-indent 2152 cl-annot 2122 trivial-utf-8 2113 cl-syntax 1969 array-utils 1914 cl-json 1913 gettext 1894 symbol-munger 1882 plump 1875 arnesi 1826 collectors 1825 cl-slice 1805 access 1794 djula 1767 cl-locale 1766 cl-parser-combinators 1742 cl-utilities 1732 metabang-bind 1695 lift 1668 cl-containers 1666 asdf-system-connections 1664 optima 1662 metatilities-base 1633 quri 1631 hunchentoot 1599 simple-date-time 1567 lparallel 1566 fast-io 1562 uuid 1531 cl-clon 1461 bt-semaphore 1438 trivial-mimes 1437 closure-common 1421 cxml 1409 static-vectors 1406 mcclim 1327 clack 1322 cl-vectors 1281 ieee-floats 1220 salza2 1197 fast-http 1165 clx 1160 fare-utils 1116 fare-quasiquote 1114 lack 1105 architecture.hooks 1087 prove 1087 cl-colors 1057 uffi 1040 cl-ansi-text 997 inferior-shell 997 fare-mop 991 postmodern 979 rfc2388 978 proc-parse 961 quicklisp-slime-helper 942 pythonic-string-reader 940 xsubseq 940 plexippus-xpath 934 cl-jpeg Timofei Shatrov — Your personal DIY image search · 117 days ago Hi everyone, it's been a while! I bet you forgot this blog even existed. I happen to be a big supporter of quality over quantity, so while my work on parsing Japanese counters earlier this year was pretty interesting, I already wrote way too many articles about Ichiran/ichi.moe so I decided to keep it to myself. Recently I've been working on a little side-project and now that it finally works, I think it deserves a full-fledged blog post. For a bit of a nostalgia trip, let’s go back to the early 00s. Remember when TinEye first appeared? It was amazing. For the first time you could easily find where that one image you once saved from some random phpBB forum is really from. It didn’t matter if your image was resized, or slightly edited from the original, it still worked. That shit was magic, my friends. Of course these days nobody is impressed by this stuff. Google Image Search indexes pretty much anything that exists on the Internet and even uses neural networks to identify content of an image. Back to the present day. I discovered I have an image hoarding problem. Over the years of using the Intertubes, I have accumulated a massive number of images on my hard drive. When I see an image I like my first thought is “do I have this one saved already?” because how could I possibly remember? At this point I need my own personal Google Image Search. And (spoiler alert) now I have one. First of all, I needed an actual image matching technology. These days the cloud is all the rage, so I definitely wanted to have this thing running in the cloud (as opposed to my local PC) so that I could search my images from anywhere in the world. After a cursory search, my eyes fell on a thing called Pavlov Match which runs from a Docker container, so should be pretty easy to install. I installed docker and docker-compose on my VPS, and then git-cloned Match and ran make dev according to instructions. This will actually run an Elasticsearch instance on the same VPS, and apparently the damn thing eats memory for breakfast, at least with the default settings. I’m using a cheap 2GB RAM Linode, so the memory is actually a very finite resource here, as I will find out later. The default settings will also completely expose your match installation AND elasticsearch to the world. But don’t worry, I figured this out so that you don’t have to. Let’s edit docker-compose.yml from match repository as follows: version: '2' services: match: image: pavlov/match:latest ports: - 127.0.0.1:8888:8888 command: ["/wait-for-it.sh", "-t", "60", "elasticsearch:9200", "--", "gunicorn", "-b", "0.0.0.0:8888", "-w", "4", "--preload", "server:app"] links: - elasticsearch elasticsearch: image: elasticsearch environment: - "ES_JAVA_OPTS=-Xms256m -Xmx256m" - bootstrap.mlockall=true expose: - "9200"  This will make match server only available on local network within the VPS on port 8888, and elasticsearch only available to these two docker containers. It will also restrict elasticsearch RAM consumption to 512mb and --preload flag reduces the amount of memory gunicorn workers consume. To make match server available from outside I recommend proxying it through nginx or some other proper web server. You can also add authentication/IP whitelist in nginx because the match server has no authentication features whatsoever, so anyone will be able to search/add/delete the data on it. That was the backend part. No programming required here! But this is a Lisp blog, so the next step is writing a Lisp client that can communicate with this server. The first step is reading the match API documentation. You might notice it’s a bit… idiosyncratic. I guess REST is out of fashion these days. Anyway, I started implementing a client using the trusty drakma, but I quickly hit a limitation: match expects all parameters to be sent encoded as form data, but drakma can only encode POST parameters as form data and not, say, DELETE parameters. Not to be foiled by a badly designed API, I tried dexador, and while dex:delete does not encode parameters as form data, dex:request is flexible enough to do so. Each response (a JSON string) is parsed using jsown. (defun parse-request (&rest args) (when *auth* (setf args (,@args :basic-auth ,*auth*))) (multiple-value-bind (content return-code) (handler-bind ((dex:http-request-failed #'dex:ignore-and-continue)) (apply 'dex:request args)) (cond ((<= 400 return-code 499) (jsown:new-js ("status" "fail") ("error" content) ("code" return-code))) (t (let ((obj (jsown:parse content))) (jsown:extend-js obj ("code" return-code))))))) (defun add-local (file &key path (metadata "{}")) "Add local image to Match server" (parse-request (api-url "/add") :method :post :content (("image" . ,(pathname file)) ("filepath" . ,(or path file)) ("metadata" . ,metadata))))  With this basic client in place, I can add and delete individual images, but it would be incredibly cumbersome to manage thousands of images with it. I had to write some code that would scan specified directories for images, track any changes and then add/update/delete information from Match server as needed. I already wrote something like this before, so this was pretty easy. Of course SBCL’s “sb-posix:stat doesn’t work on Unicode filenames” bug has reared its head again, but I already knew the workaround. This time I completely relied on UIOP for recursively walking directories (uiop:subdirectories and uiop:directory-files are your friends). Each image file is represented as CLOS object and saved into a hash-table which is serialized to a file using CL-STORE. The object has a status attribute which can be :new, :update, :delete, :ok and so on. Based on status, an action needs to be performed, such as uploading an image to Match server (for :new and :update). Now, I could just send a bunch of requests one after another, but that would be a waste. Remember, we have 4 gunicorn workers running on our server! This clearly calls for a thread pool. I thought PCALL would be perfect for this, but nope. It uses sb-thread:interrupt-thread which is incredibly unsafe and the result is that you basically can’t safely make http requests from thread workers. Debugging this took way too much time. In the end, I implemented a thread pool based on lparallel promises which is kind of an overkill for such a simple use case, but at least it worked.  (setf *cache* (update-cache)) (let ((lparallel:*kernel* (lparallel:make-kernel threads))) (unwind-protect (loop for value in (alexandria:hash-table-values *cache*) collect (worker value) into futures finally (map nil 'lparallel:force futures)) (lparallel:end-kernel))) (save-cache *cache*))  Note that you must be very careful when doing things that affect global state inside the threads. For example :delete action removes a key from the hash table *cache*. This is not guaranteed to be an atomic operation, so it’s necessary to grab a global lock when doing it. (defvar *cache-lock* (bordeaux-threads:make-lock "match-cache-lock")) ... (bordeaux-threads:with-lock-held (*cache-lock*) (remhash key *cache*))  Printing messages to REPL from inside threads also requires a separate lock and (force-output), otherwise it will look like a complete mess! (defun format-msg (str &rest args) (bordeaux-threads:with-lock-held (*msg-lock*) (terpri) (apply 'format t str args) (force-output)))  Now that the required functionality is implemented, it’s time to test upload a bunch of stuff… and get back a bunch of errors. It took some sleuthing to discover that gunicorn workers of my Match server are routinely getting killed by “OOM killer”. Basically, the server runs out of memory and the system in desperation kills a process that it doesn’t like. Remember, I only have 2Gb of memory there! I figured out that it’s images with very large dimensions that are the most problematic in terms of memory usage. If I were to resize these images to some reasonable size, the matching should still work pretty well. In order to execute this plan, I thought I’d use some Lisp to ImageMagick interface. There’s in fact a pure Lisp solution called OptiCL but would it really handle any image? Remind me to test that later! Anyway, back to ImageMagick. Neither lisp-magick nor lisp-magick-wand would work with the most recent ImageMagick version (seems its API has changed a bit). However the last one I tried cl-graphicsmagick, which uses a fork of ImageMagick called GraphicsMagick, has unexpectedly worked (at least on my Windows laptop. Note that you need to install Microsoft Visual C Redistributable 2008 otherwise the library wouldn’t load with CFFI) so I went with that. Using very useful temporary files functionality of UIOP (uiop:with-temporary-file), I resize each oversized image to reasonable dimensions and save into a temporary file, which is then uploaded to Match server. I also send the file’s original and resized dimensions as metadata. Thankfully this completely eradicated the memory issue. There’s a minor problem where GraphicsMagick cannot do Unicode pathnames on Windows, so I copy the original image into a temporary file with ASCII-only name in that case. (defun resize-image (input-path output-path &key (max-width *max-dimension*) (max-height *max-dimension*) (filter :%QuadraticFilter) (blur 1)) (gm::with-magick-wand (wand) (handler-case (gm::%MagickReadImage wand input-path) ;; graphicsmagick cannot read Unicode filenames on Windows so attempt to load a copy (gm::magick-error () (uiop:with-temporary-file (:pathname tmp :prefix "gm" :type (pathname-type input-path)) (uiop:copy-file input-path tmp) (setf wand (gm::%NewMagickWand)) (gm::%MagickReadImage wand (namestring tmp))))) (let ((w (gm::%MagickGetImageWidth wand)) (h (gm::%MagickGetImageHeight wand)) (res nil)) (multiple-value-bind (fw fh) (gm::fit-width-height w h max-width max-height) (unless (and (= w fw) (= h fh)) (gm::%MagickResizeImage wand fw fh filter blur) (gm::%MagickWriteImage wand output-path) (setf res output-path)) (values res w h fw fh)))))  Later I tested this code on an Ubuntu machine with GraphicsMagick installed from Apt repository and SBCL crashed into ldb debugger mode straight away… Welp. The helpful folks of #lisp told me the problem is with signal handlers established by GraphicsMagick library, somehow they confuse SBCL. Based on that advice, eventually I succeeded making this work. Uninstall apt Graphicsmagick and grab the sources. Find the file called magick.c and replace the line InitializeMagickSignalHandlers(); /* Signal handlers */  with // InitializeMagickSignalHandlers(); /* Signal handlers */  (commenting it out). Then do configure --enable-shared (see readme for possible options), make and sudo make install. This will make it work when called from SBCL on Linux. Anyways, the full code of MATCH-CLIENT can be found at my Github. It’s not installable from quicklisp for obvious reasons, in fact it’s a complete pain to install as you might’ve already guessed, but if you wanna try it, you’re welcome. The main two commands are update and match. The first is called to upload all images in your *root-dirs* to the server and then to update them if anything changes. match is used to match any image on the Internet (passed as URL string) or a local pathname (passed as pathname object) compared to the server. It returns a list of jsown objects (basically alists) that contain score (up to 100 for exact match), path (with “local tag” which can be different per device) and metadata containing original and resized dimensions. ((:OBJ ("score" . 96.00956) ("filepath" . "[HOME] d:/foo/bar/baz.jpg") ("metadata" :OBJ ("rw" . 1218) ("rh" . 2048) ("w" . 3413) ("h" . 5736))))  Anyway, this was a fun (although often frustrating) thing to build and ended up being quite useful! Thanks for reading and see you next time. McCLIM — Progress report #9 · 118 days ago Dear Community, McCLIM code is getting better on a weekly basis depending on developer time. We are happy to see the project moving forward. Some highlights for this iteration: • Scigraph code cleanup and bug fixes, • Bezier curves improvements, • PostScript and PDF improvements, • CLX-fb and mcclim-renderer speed improvements and refactor, • various code cleanups from unused and broken constructs, • editorial corrections to the CLIM 2 specification sources we bundle with McCLIM Moreover many bug fixes have been proposed and merged into the codebase. All McCLIM bounties (both active and already solved) may be found here. Default bounty expiration date is 6 months after posting it (a bounty may be reissued after that time period). To answer recurring requests for native Windows and OSX support, we have posted bountes for finishing the Windows backend and fixing the OSX backend. Moreover, to improve portability a bounty for closer-mop support has been posted. Bounties solved this iteration: • [$100] Caps lock affects non-alphabetic keys.

Active bounties ($1700): • [$500] Windows Backend (new).
• [$400] Fix Beagle backend (new). • [$300] Replace MOP things with closer-mop portability layer (new).
• [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size. • [$150] clx: input: english layout.
• [$100] Add PDF file generation (PDF backend). • [$100] Keystroke accelerators may shadow keys even if inactive.

Our current financial status is $800 for bounties and$267 recurring monthly contributions from the supporters (thanks!).

Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you would like to work on an issue that is not covered by the existing bounties, feel free to suggest a new bounty.

If you have any questions, doubts or suggestions - please contact me either by email (daniel@turtleware.eu) or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

· 121 days ago
Here are the raw download stats for the top 100 projects in Quicklisp for June:

 9081  alexandria 7797  closer-mop 7437  split-sequence 6863  cl-ppcre 6790  babel 6498  trivial-features 6303  iterate 6222  bordeaux-threads 6173  anaphora 6099  trivial-gray-streams 5522  trivial-garbage 5367  cffi 5056  flexi-streams 4911  nibbles 4729  let-plus 4702  usocket 4592  puri 4582  cl-base64 4286  trivial-backtrace 4181  chipz 4145  cl+ssl 4021  cl-fad 3959  chunga 3381  drakma 3292  named-readtables 3281  ironclad 3221  more-conditions 3153  esrap 3144  local-time 2928  utilities.print-items 2587  parse-number 2439  cl-yacc 2149  metabang-bind 2142  cl-unicode 2131  cl-interpol 2101  trivial-utf-8 2084  md5 2083  fiveam 2056  asdf-flv 1930  optima 1918  lparallel 1897  log4cl 1879  slime 1869  lift 1854  trivial-indent 1822  closure-common 1808  cxml 1795  array-utils 1746  plump 1743  uuid 1612  bt-semaphore 1561  trivial-types 1541  simple-date-time 1513  cl-clon 1472  cl-json 1429  cl-utilities 1392  architecture.hooks 1390  quri 1342  cl-containers 1340  metatilities-base 1330  cl-annot 1319  cl-syntax 1317  asdf-system-connections 1291  ieee-floats 1253  plexippus-xpath 1113  salza2 1079  trivial-mimes 1070  postmodern 1067  arnesi 1052  cl-slice 1050  fare-utils 1047  fast-io 1040  static-vectors 1027  fare-quasiquote 1015  symbol-munger 1009  djula 1007  collectors 1003  access  996  gettext  982  cl-parser-combinators  980  cl-locale  925  hunchentoot  904  cl-sqlite  896  inferior-shell  894  fare-mop  887  prove  885  rfc2388  868  cl-log  865  command-line-arguments  859  trivia  858  lisp-namespace  851  cl-colors  824  py-configparser  821  cl-markdown  821  cl-ansi-text  821  asdf-finalizers  820  dynamic-classes  819  cl-mssql  818  garbage-pools  805  cl-abnf

Quicklisp news — July 2017 Quicklisp dist update now available

· 122 days ago
New projects:
• 3bgl-shader — CL-hosted CL-like DSL for generating GLSL — MIT
• cl-forms — A web forms handling library — MIT
• cl-ksuid — K-sortable unique identifiers — GPLv3
• cl-pixman — Low-level pixel manipulation. — LLGPL
• cl-yesql — Common Lisp library for using SQL. — MIT
• easy-routes — Yet another routes handling utility on top of Hunchentoot — MIT
• laap — A Common Lisp multi-threaded event loop. — MIT
• matplotlib-cl — A 2D Plotting library for Common Lisp using Matplotlib. — MIT
• oook — Some magic on the shoulders of CLSQL — MIT
• overlord — Experimental build/module system. — MIT
• semantic-spinneret — A set of Semantic UI components for use with Spinneret — MIT
• with-setf — Macros for setting a place for the duration of a scope — Unlicense
• xlsx — Basic reader for Excel files. — MIT

Removed projects: gtfl, s-dot.

gtfl and s-dot are related projects. The website hosting them has disappeared, and the author has not responded to email queries. So they are not in Quicklisp any more.

To get this update, use (ql:update-dist "quicklisp").

Enjoy!

ECL News — Lisp (ECL) and QML (Qt5) on Android?

· 132 days ago
(please note that I'm assuming a Linux/64 bit platform or VirtualBox image)

Preamble: about a month ago, I was completely void of any android experience.
This is to say: using both QML (which is easy to learn) and Common Lisp (which I assume you already know) to develop android apps is not a difficult task at all, as you'll see.

So, if you are like me just a month ago, there are no excuses not to write your own, first android app using this new "EQL5-Android" project!

We will build a small game (Sokoban), which uses Lisp for the program logic, and QML for the UI, and build an APK for the android platform.

Being the author of that very first attempt of integrating Lisp and Qt4 (see lisp-cffi-qt4), what I would like to accomplish is providing you with a ca. 3 MB download, which can be tried out instantly.

10 years ago, the lisp-cffi-qt4.zip (a runnable win32 binary version), was a 3 MB download, including both ECL and Qt4 (UPX compressed, but still).
10 years later, this time on android, what download size is to be expected?
We will see...

Since all the documentation needed for preparing the development environment is already covered in the "EQL5-Android" project itself, I will give only the link here:

So, I'm assuming that you already have everything installed and set up (Qt 5.7.1, Android NDK 10e, Android SDK, Java JDK, and obviously the EQL5-Android sources from gitlab), in order to build android packages (APK files).

(EQL5 itself, the desktop version, is not strictly needed to follow this example; but for developing your own apps, you will obviously need it; even here it's very helpful for testing and debugging, if something doesn't work as expected.)

If you already know the process of building EQL5 apps for the desktop, you will find that building (cross-compiling) to android is very similar, with only a few more steps involved.

Since we use an example of EQL5-Android itself, everything has already been set up. But I want to remember the steps that are not obvious, if you are not familiar with Qt and EQL:

• you need to add all your external resources, like QML files, PNG files etc. to a Qt resource file (ending .qrc); this will integrate them (compressed) directly into the executable
• you need to add all your Lisp files, in exact order of loading, to make.lisp (in a future version of EQL5, I will try to integrate this step with ASDF)

And that's it, basically (except the app name, which needs to be adapted to the *.qrc file name, to your *.pro file name and contents (see TARGET and RESOURCES), and to the contents of the third script 3-build-apk.sh (see *.json file name).

Everything else will stay the same for every project.

Now I want to call your attention on the huge advantage of using Qt for your android apps: you can first build a desktop exe, with the exact same sources, and try/debug it. If the desktop version works, the android app will generally work too (the only things that may need adaption are e.g. font sizes and similar).

So, let's get practical! In the EQL5-Android sources, switch to 'examples/sokoban/'.

Building a desktop exe would be this 3 liner:


$eql5 make-desktop.lisp$ qmake sokoban_desktop.pro
$make  (To test if all resources have really been included in the sokoban_desktop executable, you need to move it to a different directory, and launch it from there.) Here's a screenshot of our app running on the desktop: But now let's do the cross-compile dance! First let's copy the needed shared libraries to the 'android-build/' directory. Just run script number 1: $ ./1-copy-libs.sh


This step needs only be done once for every new project. It will copy the cross-compiled ECL and EQL5 libs into our android build directory.

The next steps are very similar to a desktop build:


$ecl-android -shell make.lisp$ qmake-android sokoban.pro
$make  Since cross-compiling requires a special "host ECL", which needs to match the target platform (that is, 32 bit, no double floats), we would be in trouble with cross-compiling EQL5 code: we certainly don't want a seperate EQL5 32 bit version, only for cross-compiling... But there is a solution to this (see 'utils/EQL5-symbols.lisp' in sources): for cross-compiling -- which is the job of our "host ECL" -- we pretend to be the eql5 executable, by defining all packages and symbols, defining all EQL5 macros (otherwise we can't compile), and simply defining dummy-functions for all EQL5 functions, so the compiler will not complain. So, loading 'utils/EQL5-symbols.lisp' in our host ECL will be sufficient for cross-compiling EQL5 code. If you are interested in how the cross-compile environment is set up, please see: utils/cross-compile.lisp (thanks to Sylvain Ageneau, who wrote the original version; this is a simplified version not depending on ASDF; the latter will be integrated in a future version) So, the above 3 liner will build the shared library of our app, ready to be included in the android build. To copy it where the android build expects it, use script number 2: $ ./2-install-lib.sh


The last step, which will build our APK file, is a verbose one (for eventual debugging), and a little time consuming: it will create the whole package structure, and compile the whole thing into an APK file, ready to be installed on an android device.

There is this great tool (courtesy Qt) called androiddeployqt, which automates the whole and complex process of creating an APK file, with all the needed options already set in our 3rd script:


$./3-build-apk.sh  Here the contents of the above script, where you can see all the selected options: $ ~/Qt5.7.1/5.7/android_armv7/bin/androiddeployqt \
--input android-libsokoban.so-deployment-settings.json \
--output android-build \
--deployment ministro \
--verbose


If it will tell you BUILD SUCCESSFUL, then you'll find the APK file (ready for deployment) in 'android-build/build/outputs/apk/'.

The last step is copying over the APK file to your android device, and install / run it. Normally you're not allowed to do this, because it requires special developer settings (please search the web for instructions how to enable them, as they are different for every android version).

After connecting via USB and copying the APK file over to your device, just tap it from there. This will ask for installing, and then for opening the app.

Here's a screenshot of the sokoban app running on a tablet:

Above you see the splash screen, because startup will take a few seconds.

Below the game:

After seeing the result, I'd like to consider a few QML and Lisp snippets.

QML is easy to learn. You just need to declare what you want (and it will do the how behind the scenes).
Let's see this snippet for defining and placing our arrow buttons:


// container for arrow buttons
Item {
id: arrows
width: up.width * 3
height: up.height * 3
anchors.margins: 10
anchors.right: parent.right
anchors.verticalCenter: parent.verticalCenter

Ext.Button {
id: up
objectName: "up"
source: "img/up.png"
anchors.horizontalCenter: parent.horizontalCenter
}

Ext.Button {
objectName: "left"
source: "img/left.png"
anchors.verticalCenter: parent.verticalCenter
}

Ext.Button {
objectName: "right"
source: "img/right.png"
anchors.verticalCenter: parent.verticalCenter
anchors.right: parent.right
}

Ext.Button {
objectName: "down"
source: "img/down.png"
anchors.horizontalCenter: parent.horizontalCenter
anchors.bottom: parent.bottom
}
}


So, we define an Item as container for the buttons, giving it the width (up.width * 3) and height (up.height * 3), according to the button sizes: this may be any calculation or function call, and may refer to any item of the file, referred to by its id.

For placing the container itself, and the single arrow buttons, we just need to define anchors, which can be relative to other items (here: the parent item).

The Ext.Button is a user defined item class, which can be found in 'qml/ext/Button.qml. That is, the whole directory 'ext/' is imported as Ext:


import "ext/" as Ext


This means that every file in 'ext/' is now a new QML class, which can be referred to via Ext (like a namespace).

The definition of our image button class (see 'qml/ext/Button.qml') is:


import QtQuick 2.0

Image {
signal pressed()

MouseArea {
anchors.fill: parent
onPressed: { parent.pressed() }
}
}


So, we don't need a real button, but only a clickable image: adding a mouse area will allow us to capture mouse events; this event is then passed to the parent (that is, the Image class), where a Qt signal will be emitted: this will allow us to connect to it from Lisp:


(defun connect ()
(macrolet ((pressed (item function)
(qconnect (find-quick-item ,item) "pressed()"
(lambda () ,function))))
(pressed "up"       (sokoban:move :north *maze*))
(pressed "down"     (sokoban:move :south *maze*))
(pressed "left"     (sokoban:move :west *maze*))
(pressed "right"    (sokoban:move :east *maze*))
(pressed "previous" (change-level :previous))
(pressed "next"     (change-level :next))
(pressed "undo"     (undo))
(pressed "restart"  (reset-maze))
(pressed "solve"    (solve))))


If you already played the game finishing a level, you will have noticed that there are 2 animations (rotation of the player, wiggling of all boxes) which run queued.
This is a little tricky to do, but with the help of a Lisp macro, we only need these lines in Lisp (being queued a macro):


(defun final-animation ()
(queued (qml-set "rotate_player" "running" t)
(qml-set-all "wiggle_box" "running" t)))


Please see the sources for all the details. And this would not be possible without a Lisp function called from QML for notifying us whenever an animation state changes, see 'qml/ext/RotationAnimation.qml':


import QtQuick 2.0
import EQL5 1.0

RotationAnimation {
onRunningChanged: Lisp.call("qsoko:animation-change", running)
}


What I left out to explain is the dynamic (at run time) creation of QML items (see 'qml/items/*' and 'lisp/sokoban.lisp'); let's just say that this is left as an exercise to the reader, as all sources will patiently stay there to be read...

Well. But I still didn't answer the initial question: how big of a download is to be expected, 10 years later?

Since our APK file uses the ministro service for automatically installing the needed Qt libraries at the first launch of the app, it will only need to include both the ECL and EQL5 libraries (you can therefore use different ECL and EQL5 versions for every app you deploy).

So, to finally answer the question: our download will be ca. 3.5 MB (instead of 3 MB, 10 years ago, although we obviously compare apples and oranges here).

Seems acceptable.

And since I promised you to test it instantly (if you own a device with ARM processor), here you are:

sokoban.apk

Enjoy!

Quicklisp news — June 2017 Quicklisp dist update now available

· 145 days ago
New projects:
• cepl.spaces — Adds abstractions over vector spaces to CEPL — BSD 2 Clause
• cl-cpus — Get number of CPUs — ISC
• cl-diskspace — List disks, get disk total/free/usable space information. — ISC
• cl-fixtures — A simple library to create and use parameterized fixtures — MIT
• cl-fluent-logger — A structured logger for Fluentd — BSD 3-Clause
• cl-mixed — Bindings to libmixed, a sound mixing and processing library. — Artistic
• cl-rail — Unspecified — Unspecified
• cl-random-forest — Random Forest and Global Refinement for Common Lisp — MIT Licence
• cl-soloud — Bindings to SoLoud, a multi-platform, multi-backend, minimal dependencies sound mixing and output library — Artistic
• cl-ssdb — SSDB client for Common Lisp. — MIT
• deploy — Tools to aid in the deployment of a fully standalone application. — Artistic
• doplus — DO+ (doplus) is a high-level, extensible iteration construct for Common Lisp with a reasonably simple implementation, which in particular does not use a code walker. — GPLv3
• flow — A flowchart and generalised graph library. — Artistic
• gtk-tagged-streams — Text I/O using streams for GTK text buffers, including tags for styling. — BSD Simplified (2-clause)
• harmony — A common lisp sound server and sound processing library. — Artistic
• hu.dwim.zlib — Common Lisp FFI wrapper for zlib, aka http://zlib.net/ — BSD or Bugroff
• modest-config — A modest config file loader library — MIT
• nineveh — A library of common gpu functions — BSD 2 Clause
• papyrus — A Literate Programming Tool — MIT
• parseq — A parser for sequences such as strings, lists, vectors as well as trees. — GPLv2
• physical-quantities — Use lisp numbers for physical quantities with unit and error. — GPLv2
• roan — A library to support change ringing applications, including methods library support — MIT
• sanitized-params — Sanitizer for parameters — BSD 2-Clause
• sdl2-game-controller-db — Lets you easily load the lovely sdl2 gamecontroller db into cl-sdl2 — BSD 3 Clause
• trivial-battery — Getting the battery information — BSD 2-Clause
• trivial-swank — swank server communications — BSD simplified
• trivial-wish — Create 'wishes' which are requests to compute something later — BSD 2-clause

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Paul Khuong — Chubanov's Projection Methods for 0/1 Programming

· 159 days ago

I’ve long felt that compilers (and symbolic processing in general) would benefit from embedding integer programming solvers. However, I was never comfortable with actually doing so for a production system that others would have to run: industrial strength integer linear programming solvers are large systems with complex runtime behaviour, and that’s not the kind of black box you want to impose on people who just want to build their project. (That’s also true of SAT solvers, though, so maybe embedding complicated black boxes is the new normal?)

However, if we had something simple enough to implement natively in the compiler, we could hope for the maintainers to understand what the ILP solver is doing. This seems realistic to me mostly because the generic complexity tends to lie in the continuous optimisation part. Branching, bound propagation, etc. is basic, sometimes domain specific, combinatorial logic; cut generation is probably the most prominent exception, and even that tends to be fairly combinatorial. (Maybe that’s why we seem to be growing comfortable with SAT solvers: no scary analysis.) So, for the past couple years, I’ve been looking for simple enough specialised solvers I could use in branch-and-bound for large 0/1 ILP.

Some stuff with augmented lagrangians and specialised methods for box-constrained QP almost panned out, but nested optimisation sucks when the inner solver is approximate: you never know if you should be more precise in the lower level or if you should aim for more outer iterations.

A subroutine in Chubanov’s polynomial-time linear programming algorithm [PDF] (related journal version) seems promising, especially since it doesn’t suffer from the numerical issues inherent to log barriers.

Chubanov’s subroutine in branch-and-bound

Chubanov’s “Basic Subroutine” accepts a problem of the form $$Ax = 0$$, $$x > 0$$, and either:

1. returns a solution;
2. returns a non-empty subset of variables that must be 0 in any feasible solution;
3. returns a non-empty subset of variables $$x\sb{i}$$ that always satisfy $$x\sb{i} \leq u$$ in feasible solutions with $$x\sp{\star} \in [0, 1]$$, for some constant $$u < 1$$ (Chubanov sets $$u = \frac{1}{2}$$).

The class of homogeneous problems seems useless (never mind the nondeterministic return value), but we can convert “regular” 0/1 problems to that form with a bit of algebra.

Let’s start with $$Ax = b$$, $$0 \leq x \leq 1$$, we can reformulate that in the homogeneous form:

$Ax - by = 0,$ $x + s - \mathbf{1}y = 0,$ $x, s, y \geq 0.$

Any solution to the original problem in $$[0, 1]$$ may be translated to the homogeneous form (let $$y = 1$$ and $$s = 1 - x$$). Crucially, any 0/1 (binary) solution to the original problem is still 0/1 in the homogeneous form. In the other direction, any solution with $$y > 0$$ may be converted to the box-constrained problem by dividing everything by $$y$$.

If we try to solve the homogenous form with Chubanov’s subroutine, we may get:

1. a strictly positive (for all elements) solution. In that case, $$y > 0$$ and we can recover a solution to the box-constrained problem.
2. a subset of variables that must be 0 in any feasible solution. If that subset includes $$y$$, the box-constrained problem is infeasible. Otherwise, we can take out the variables and try again.
3. a subset of variables that are always strictly less than 1 in feasible solutions. We exploit the fact that we only really care about 0/1 solutions (to the original problem or to the homogenous reformulation) to also fix these variables to 0; if the subset includes $$y$$, the 0/1 problem is infeasible.

As soon as we invoke the third case to recursively solve a smaller problem, we end up solving an interesting ill-specified relaxation of the initial 0/1 linear program: it’s still a valid relaxation of the binary problem, but is stricter than the usual box linear relaxation.

That’s more than enough to drive a branch-and-bound process. In practice, branch-and-bound is much more about proving the (near-) optimality of an existing solution than coming up with strong feasible solutions. That’s why the fact that the subroutine “only” solves feasibility isn’t a blocker. We only need to prove the absence of 0/1 solutions (much) better than the incumbent solution, and that’s a constraint on the objective value. If we get such a proof, we can prune away that whole search subtree; if we don’t, the subroutine might have fixed some variables 0 or 1 (always useful), and we definitely have a fractional solution. That solution to the relaxation could be useful for primal heuristics, and will definitely be used for branching (solving the natural LP relaxation of constraint satisfaction problems ends up performing basic propagation for us, so we get some domain propagation for free by only branching on variables with fractional values).

At the root, if we don’t have any primal solution yet, we should probably run some binary search on the objective value at the root node and feed the resulting fractional solutions to rounding heuristics. However, we can’t use the variables fixed by the subroutine: until we have a feasible binary solution with objective value $$Z\sp{\star}$$, we can’t assume that we’re only interested in binary solutions with object value $$Z < Z\sp{\star}$$, so the subroutine might fix some variables simply because there is no 0/1 solution that satisfy $$Z < k$$ (case 3 is vacuously valid if there is no 0/1 solution to the homogeneous problem).

That suffices to convince me of correctness. I still have to understand Chubanov’s “Basic Subroutine.”

Understanding the basic subroutine

This note by Cornelis/Kees Roos helped me understand what makes the subroutine tick.

The basic procedure updates a dual vector $$y$$ (not the same $$y$$ as the one I had in the reformulation... sorry) such that $$y \geq 0$$ and $$|y|_1 = 1$$, and constantly derives from the dual vector a tentative solution $$z = P\sb{A}y$$, where $$P\sb{A}$$ projects (orthogonally) in the null space of the homogeneous constraint matrix $$A$$ (the tentative solution is $$x$$ in Chubanov’s paper).

At any time, if $$z > 0$$, we have a solution to the homogenous system.

If $$z = P\sb{A}y = 0$$, we can exploit the fact that, for any feasible solution $$x$$, $$x = P\sb{A}x$$: any feasible solution is alrady in the null space of $$A$$. We have

$x\sp{\top}y = x\sp{\top}P\sb{A}y = x\sp{\top}\mathbf{0} = 0$

(the projection matrix is symmetric). The solution $$x$$ is strictly positive and $$y$$ is non-negative, so this must mean that, for every component of $$y\sb{k} > 0$$, $$x\sb{k} = 0$$. There is at least one such component since $$|y|_1 = 1$$.

The last condition is how we bound the number of iterations. For any feasible solution $$x$$ and any component $$j$$,

$y\sb{j}x\sb{j} \leq y\sp{\top}x = y\sp{\top}P\sb{A}x \leq |x| |P\sb{A}y| \leq \sqrt{n} |z|.$

Let’s say the max element of $$y$$, $$y\sb{j} \geq 2 \sqrt{n}|z|$$. In that case, we have $x\sb{j} \leq \frac{\sqrt{n}|z|}{y\sb{j}} \leq \frac{1}{2}.$

Chubanov uses this criterion, along with a potential argument on $$|z|$$, to bound the number of iterations. However, we can apply the result at any iteration where we find that $$x\sp{\top}z < y\sb{j}$$: any such $$x\sb{j} = 0$$ in binary solutions. In general, we may upper bound the left-hand side with $$x\sp{\top}z \leq |x||z| \leq \sqrt{n}|z|$$, but we can always exploit the structure of the problem to have a tighter bound (e.g., by encoding clique constraints $$x\sb{1} + x\sb{2} + … = 1$$ directly in the homogeneous reformulation).

The rest is mostly applying lines 9-12 of the basic procedure in Kees’s note. Find the set $$K$$ of all indices such that $$\forall k\in K,\ z\sb{k} \leq 0$$ (Kees’s criterion is more relaxed, but that’s what he uses in experiments), project the vector $$\frac{1}{|K|} \sum\sb{k\in K}e\sb{k}$$ in the null space of $$A$$ to obtain $$p\sb{K}$$, and update $$y$$ and $$z$$.

The potential argument here is that after updating $$z$$, $$\frac{1}{|z|\sp{2}}$$ has increased by at least $$|K| > 1$$. We also know that $$\max y \geq \frac{1}{n}$$, so we can fix a variable to 0 as soon as $$\sqrt{n} |z| < \frac{1}{n}$$, or, equivalently, $$\frac{1}{|z|} > n\sp{3/2}$$. We need to increment $$\frac{1}{|z|\sp{2}}$$ to at most $$n\sp{3}$$, so we will go through at most $$1 + n\sp{3})$$ iterations of the basic procedure before it terminates; if the set $$K$$ includes more than one coordinate, we should need fewer iterations to reach the same limit.

Chubanov shows how to embed the basic procedure in a basic iterative method to solve binary LPs. The interesting bit is that we reuse the dual vector $$y$$ as much as we can in order to bound the total number of iterations in the basic procedure. We fix at least one variable to $$0$$ after a call to the basic procedure that does not yield a fractional solution; there are thus at most $$n$$ such calls.

Next step

In contrast to regular numerical algorithms, the number of iterations and calls so far have all had exact (non asymptotic) bounds. The asymptotics hide in the projection step, where we average elementary unit vectors and project them in the null space of $$A$$. We know there will be few (at most $$n$$) calls to the basic procedure, so we can expend a lot of time on matrix factorisation. In fact, Chubanov outright computes the projection matrix in $$\mathcal{O}(n\sp{3})$$ time to get his complexity bound of $$\mathcal{O}(n\sp{4})$$. In practice, this approach is likely to fill a lot of zeros in, and thus run out of RAM.

I’d start with the sparse projection code in SuiteSparse. The direct sparse solver spends less time on precomputation than fully building the projection matrix (good if we don’t expect to always hit the worst case iteration bound), and should preserve sparsity (good for memory usage). In return, computing projections is slower, which brings the worst-case complexity to something like $$\mathcal{O}(n\sp{5})$$, but that can be parallelised, should be more proportional to the number of non-zeros in the constraint matrix ($$\mathcal{O}(n)$$ in practice), and may even exploit sparsity in the right-hand side. Moreover, we can hope that the $$n\sp{3}$$ iteration bound is pessimistic; that certainly seems to be the case for most experiments with random matrices.

The worst-case complexity, between $$\mathcal{O}(n\sp{4})$$ and $$\mathcal{O}(n\sp{5})$$, doesn’t compare that well to interior point methods ($$\mathcal{O}(\sqrt{n})$$ sparse linear solutions). However, that’s all worst-case (even for IPMs). We also have different goals when embedding linear programming solvers in branch-and-bound methods. Warm starts and the ability to find solution close to their bounds are key to efficient branch-and-bound; that’s why we still use simplex methods in such methods. Chubanov’s projection routine seems like it might come close to the simplex’s good fit in branch-and-bound, while improving efficiency and parallelisability on large LPs.

McCLIM — Progress report #8

· 165 days ago

Dear Community,

During this iteration we had many valuable contributions. It's a joy to see how McCLIM gains more mindshare and people are willing to put their time and wallet in fixing issues and writing applications in McCLIM.

Some highlights for this iteration:

• many Listener fixes,
• major tab layout extension refactor,
• new extension for Bezier curves (based on older internal implementation),
• interactor improvements,
• layout improvements,
• fixes for redisplay and transformations,
• documentation cleanups,
• cleanup of the issues (closed the obsolete and fixed ones).

All McCLIM bounties (both active and already solved) may be found here.

Bounties solved this iteration:

• [$200] Interactor CLI prompt print problem Fixed by Gabriel Laddel. Waiting for a pull request and a bounty claim. • [$200] Problem with coordinate swizzling (probably).

Fixed by Alessandro Serra and merged. Waiting for a bounty claim.

• [$100] menu for input-prompt in lisp-listener does not disappear after use. Fixed by Alessandro Serra and merged. Waiting for a bounty claim. Active bounties: • [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size.

• [$150] clx: input: english layout. (someone already works on it). • [$100] Caps lock affects non-alphabetic keys. (new)

• [$100] Add PDF file generation (PDF backend). (new) • [$100] Keystroke accelerators may shadow keys even if inactive. (new)

Our current financial status is $1,429 for bounties and$267 recurring monthly contributions from the supporters (thanks!).

Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you feel that you may solve some problem, but there is no bounty on it, feel free to suggest it too.

If you have any questions, doubts or suggestions - please contact me either by email (daniel@turtleware.eu) or on IRC (my nick is jackdaniel`).

Sincerely yours,
Daniel Kochmański

ABCL Dev — ABCL 1.5.0

· 166 days ago
We are pleased to announce that we have released the Sixth Edition of the Armed Bear Common Lisp implementation as ABCL 1.5.0.

Due to the lack of a publicly available Java 5 implementation, with this release we drop support for that platform, and henceforth support running on Java 6, Java 7, and Java 8.

In addition to consolidating eight months of bug fixes, the following notable features are now also present in the implementation.

The compiler now records more complete debugging information on the SYS:SOURCE symbol property.

ABCL-INTROSPECT offers improved inspection of backtraces to the point that local variables may be inspected in Lisp debug frames.  Patches to SLIME to use this feature are in the process of being merged into the upstream repository. The OBJECTWEB system allows the user to disassemble JVM bytecode via dependencies managed by Maven.

JSS now contains a syntax for accessing Java static and member fields.

For declaring dependencies on Java artifacts ABCL-ASDF,  we have added an experimental syntax to address JRE/JDK artifacts via the ASDF:JDK-JAR class, as well as the ability to more finely control Maven dependencies with the  ASDF:MVN-MODULE class.

A complete list of changes may be viewed in the source repository.

docker run -it easye/abcl:1.5.0
Many thanks to all who have contributed to nurturing the Bear's execution of conforming ANSI Common Lisp on the Java Virtual Machine.

Nicolas Hafner — Trial "Study Session" Next Saturday, 17th of June

· 167 days ago

Next Saturday, the 17th of June, there is going to be a live "study session" about Shirakumo's game engine Trial. The intention of this event is to get people acquainted with the internal structure and features of Trial, so that they may work on it by themselves, and thus help improve it in the future.

The study session is going to be held on my regular stream from 10:00-16:00 UTC. That's 12:00-18:00 CEST, 6:00-12:00 EST, 19:00-3:00 JST. We might stop earlier if people run out of steam or there isn't as much to cover as I anticipated.

Participants that want to actively ask questions and follow along are encouraged to download and set up Mumble for voice communication, and to download the source code of Trial and its dependencies ahead of time, so that they may follow along on their own screens, rather than being subject to the stream delay.

You are expected to have a decent understanding of Common Lisp, as I won't have time to teach you that. While an understanding of modern OpenGL is advantageous, it won't be required. I'll try to explain OpenGL as much as possible or necessary as we go along. Likely there will be another stream at a later point, where modern OpenGL is explained from the ground up.

Hope to see you there!

Lispjobs — Lisp programmer, Keepit.com, Lviv, Ukraine

· 168 days ago

Keepit.com is expanding and we are looking for candidates to join our strong cloud software development team.

We use Lisp systems to implement business logic operations such as resource accounting, data mining, billing, automated operations (AI), full system test suites and more. We wish to extend our team with another skilled colleague, to work with us in this area.

We expect a strong technical mind coupled with a visionary outlook and ability to work closely together with the entire team, from architecture through development, QA and ultimately production.

Keepit can offer a passionate working environment with bright minded colleagues bringing out the next generations of data consolidation, data security and data sharing solutions coupled with the ability to bring-out real value of the data of our customers.

Required skills:

Good understanding of Common Lisp;

Good algorithmic knowledge

Will be a plus:

Good understanding of HTTP, REST and XML;

Shell scripting and ability to read/write Makefiles;

Experience with Emacs, slime/swank and SBCL;

Some knowledge of C++

Desired communication skills:

Team player, but with high degree of ability to work independently;

Upper-intermediary level of English for daily written and video calls communication;

Person who is gladly willing to share knowledge within the team;

Willingness to take initiative and suggest alternative ways of solving problems;

Quick learner, self starter.

Contact information:

e-mail: mhn@keepit.com, Skype: maryna.hnatyk

For older items, see the Planet Lisp Archives.

Last updated: 2017-11-23 02:50