ELS 2014 is finally settled. I have the pleasure to welcome Kent Pitman as the Programme Chair, and Gérard Assayag as a co Local Chair ! The symposium is going to be held at IRCAM, a French institute for research on music and acoustics, so I hope there's going to be a lot of Lisp & music talks!
ELS'14 - 7th European Lisp Symposium IRCAM, Paris, France May 5-6, 2014 http://www.european-lisp-symposium.org/ The purpose of the European Lisp Symposium is to provide a forum for the discussion and dissemination of all aspects of design, implementation and application of any of the Lisp and Lisp-inspired dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, Hop and so on. We encourage everyone interested in Lisp to participate. The 7th European Lisp Symposium invites high quality papers about novel research results, insights and lessons learned from practical applications, and educational perspectives. We also encourage submissions about known ideas as long as they are presented in a new setting and/or in a highly elegant way. Topics include but are not limited to: - Context-, aspect-, domain-oriented and generative programming - Macro-, reflective-, meta- and/or rule-based development approaches - Language design and implementation - Language integration, inter-operation and deployment - Development methodologies, support and environments - Educational approaches and perspectives - Experience reports and case studies Please note that IRCAM, the conference venue, is a French institute for research on music and acoustics. Submissions relating Lisp to music or other acoustical matters will hence be particularly welcome, although given no heightened favor during the review process. We invite submissions in the following forms: Papers: Technical papers of up to 8 pages that describe original results or explain known ideas in new and elegant ways. Demonstrations: Abstracts of up to 2 pages for demonstrations of tools, libraries, and applications. Tutorials: Abstracts of up to 4 pages for in-depth presentations about topics of special interest for at least 90 minutes and up to 180 minutes. The symposium will also provide slots for lightning talks, to be registered on-site every day. All submissions should be formatted following the ACM SIGS guidelines and include ACM classification categories and terms. For more information on the submission guidelines and the ACM keywords, see: http://www.acm.org/sigs/publications/proceedings-templates and http://www.acm.org/about/class/1998. Important dates: - TODAY: Mark your calendar. Start planning now! - 09 Mar 2014: Submission deadline - 31 Mar 2014: Notification of acceptance - 21 Apr 2014: Final Papers due - 05 May 2014: Symposium. Join us there! Program Committee: Chair: Kent Pitman, Hypermeta Inc., U.S.A. Local Organizers: Didier Verna, EPITA Research Lab, France Gérard Assayag, IRCAM, France Members: To be announced later Search Keywords: #els2014, ELS 2014, ELS '14, European Lisp Symposium 2014, European Lisp Symposium '14, 7th ELS, 7th European Lisp Symposium, European Lisp Conference 2014, European Lisp Conference '14 Ircam STMS Lab, IRCAM / CNRS / UPMC
Emmanuel Goossaert recently played with Robin Hood linear probing and, after failing to reproduce some of my results, emailed me for advice or comments. The discussion lead to a small tweak to his deletion routine, after which we declared replication successful.
I think the underlying confusion is frequent; I’ve seen it in a couple discussions where people report conflicting experiences with Robin Hood hashing.
The scheme described in Pedro Celis’s dissertation (PDF) is a variant of double hashing. Hashing is based on simulating random allocation with a hash function; double hashing asks for a second hash function to simulate independent random probing sequences for each key. This is really useful to reduce the worst-case probe sequence length, and Robin Hood hashing further improves the distribution’s tail by reducing the variance: better locations are given to far-off entries after bumping out well-off ones, hence the name.
Twenty-five years later, I don’t think any variant of double hashing makes sense. If we allow multiple hash functions and reads to uncorrelated addresses (and writes that bump entries out), we might as well go for simpler strategies with awesome worst-case bounds, like 2-left or cuckoo hashing. Then again, I’m not convinced that these schemes are useful in software either: we can do a lot of probing in the time it takes to read a second random address [*]. In hardware, the trade-offs seem completely different; I wouldn’t be surprised if two 128 KB SRAM chips were cheaper than a single 256 KB chip.
[*] We could hope for memory-level parallelism... but, in my experience, TLB misses are where (uncached) hash lookups hurt, and those don’t seem to be resolved in parallel. In cache, linear probing eliminates bank conflicts and is really quick.
When I looked into Robin Hood hashing, I was interested in a degenerate variant in which probing sequences are linear. This variant also seems the one others usually mean when they say “Robin Hood hashing,” nowadays. The algorithms for inserts and lookups in Celis’s dissertation still work: probe locations and distances just happen to be computed trivially. However, the analysis doesn’t hold anymore. This is where later work like Viola’s Distributional analysis of Robin Hood linear probing hashing with buckets and the associated journal paper comes in. The bounds are worse than with (pseudo)random probing sequences, but each probe is a lot quicker.
Such weaker bounds also mean that Celis’s suggestion of using tombstone (markers for deleted entries) doesn’t perform as well. Linear probing clumps up, even with Robin Hood rebalancing. Tombstones can be cleared out with a full rehash after \(\Theta(n)\) operations, or deletion instead implemented by copying later elements backwards. I’m a fan of the latter option: when ties are broken deterministically (e.g., by comparing keys), the layout of the hash table is independent of the sequence of insertions and deletions executed to get there.
When there’s a disagreement over the performance of Robin Hood hashing, it may help to specify the probing sequence. Older (pre-2000) references and experiments probably refer to the original twist on double hashing; newer ones may instead describe the linear probing variant. Robin Hood double hashing seems obsolete, and the linear probing variant isn’t what Celis described. It may be more appropriate to refer to the latter as “Robin Hood linear probing.”
I’ll be defending on Friday, December 13th; that will likely mark the end of my copious free time. I hope to write a couple more braindumps on SBCLy topics in the near future, before I forget everything.
SBCL is known for its flow-sensitive type propagation pass... or, rather, for its effects. That is probably why it can be so shocking when SBCL fails to infer obvious invariants. I feel like I can now describe the root causes of these surprising weaknesses and propose a series of fixes. Coding that up would likely take months, but the result should be more precise type propagation with improved asymptotic efficiency, and even a tunable knob between precision and compile times.
The compiler in SBCL, Python, doesn’t work on an IR in SSA form, nor does it convert internally to CPS à la Rabbit/Orbit. However, a clever – I don’t recall seeing it described anywhere else – design decision achieves similar effects. Operations receive their arguments as linear vars (LVARs) and write their results to an LVAR. Each LVAR has exactly one destination (one reader node), and, on any execution path, can only be used (written to) by one node. LVARs may nevertheless have multiple uses: these correspond to the value of conditionals and of conditional non-local exits. Assignment and access to lexical variables are represented as SET and REF nodes that receive and produce values through LVARs. This means that nearly everything can work in terms of LVARs when manipulating code and reasoning about dataflow. The conversion of read-once lexical variables to LVARs further simplifies a lot of mostly functional code.
Python takes this split to the extreme: only the constraint (type) propagation pass really handles full-blown lexical variables. Everything else depends on the flow-sensitive type information summarised in CFG nodes and joined in LVARs. Want to check whether a given argument is always positive? Simply test for subtyping on the LVAR’s derived type to implicitly leverage flow-sensitive type information. Want to insert some computation (e.g. a type assertion or an explicit modulo for overflowing arithmetic) between a value and its destination? Insert a new node in the CFG and substitute around nothing but opaque LVARs. These operations are so natural in Python that I only recently realised the design decision that makes them so easy.
However, I believe that Python went too far in relegating lexical variables to only the constraint pass. That pass only handles lexical variables (LAMBDA-VARs) and flow-sensitive information about them, and only propagates three kinds of constraints (derived information):
The importance of EQL constraints is subtle. These constraints represent the way that, e.g., information about a lexical variable is also true of the result of a lookup for that variable’s value (and vice versa), even if that information is learned after the variable is accessed. Similarly, when two lexical variables are EQL, information about one is true of the other. Finally, equality with a constant is always useful for constant propagation.
All three constraint types are centered on lexical variables. The reason is that no flow-sensitive information needs to be computed for LVARs: they are only used once. For example, if a type test is performed on an LVAR, that is the LVAR’s only appearance and there is no information to propagate... unless that information is also true of some lexical variable.
There’s some more clever engineering and the analysis is simplified by disregarding variables that may be assigned from closures, but that’s the gist of it. A vanilla dataflow analysis worklist loop propagates information around, and constraints sets for each basic block shrink until the least (in terms of types, greatest when measuring information) fixed point is reached.
The first weakness is caused by the aforementioned cleverness: knowledge about the state of the world as each basic block is entered and exited is represented with sets of constraints (bitsets indexed with consecutive indices assigned to constraints on demand). In the interest of speed, join and meet are implemented as (bit-)set union/intersection. The problem with this approach is that it completely discards information about a lexical variable when it is not identically present in both sets. For example, when one predecessor says that V is a positive integer and another that V is an integer, their successor discards all information about the type of V.
In practice, this is a lesser problem than it first appears to be: LVARs merge information about their multiple uses (writes) without any loss. The kind of code that suffers is code that does things like:
(lambda (x) (ecase x (1 ...) (2 ...)) [work on X, knowing that it is either 1 or 2])
The two branches of the ecase that eventually continue execution respectively derive that X is EQL to 1 and to 2. However, their shared successor combines that information by forgetting about both equalities rather than weakening/downgrading the two constraints into “X is of type (INTEGER 1 2).”
Another interesting case is
(lambda (x) (let ((y nil)) ; IF expression translated to an effectful IR (if x (setf y 1) (setf y 2)) y))
for which Python derives that the result is either 1, 2, or NIL (the
union of all the values ever assigned to Y). The equivalent code
(lambda (x) (if x 1 2)) compiles everything to LVARs and the result is
known to be either 1 or 2 even before constraint propagation.
This can be addressed with a redundant representation that adds, to each constraint set, a dictionary from lexical variables to the (downgradable) information known about them: their types and the types they’re known to be < or > than. When intersecting constraint sets, these dictionaries make it easy to weaken information and insert the corresponding constraints.
The second weakness is deeply embedded in the structure of the compiler: the constraint propagation pass only pushes around pre-computed flow-insensitive information. That information is valid because the flow-insensitive pass (that computes things like the type of the values produced by each CFG node) works from an older (over) approximation of the flow-sensitive information. Once a fixed point is reached in the constraint propagation pass, the flow-insensitive pass is re-executed and information refined. In the end, there is a back-and-forth between the simple flow-sensitive constraint propagation pass and the flow-insensitive “optimization” pass that leverages a huge knowledge base about Common Lisp operators and functions.
That exchange of information not only takes many (hefty) iterations to converge, but is also lossy: the constraint propagation pass is flow-sensitive, but manipulates types based on an earlier pass or on type declarations. In effect, constraint propagation computes the least fixed point of a function that is defined by an earlier coarse upper approximation... a process that ends up preserving a lot of the initial weakness. This strange choice presents an interesting characteristic: every iteration the outer communication loop between flow -sensitive and -insensitive analysis produces valid (but overly conservative) information. So convergence is slow, but at least intermediate results can guide rewrites safely.
The obvious fix is to derive node types within the constraint propagation pass, even as the final result of the flow-sensitive pass is approximated from below. For example, upon assignment to a lexical variable, the current pass adds a new constraint: the type of that variable is that of the LVAR for the assignment’s value, and the LVAR’s type is computed based on the information from the previous constraint propagation pass. Instead, it should be based on the current (overly agressive) flow-sensitive information. That would eventually converge to a smaller fixed point. This alternative design would also obviate the need for a questionable hack that improves precision for some lucky iteration variables.
A weaker form of this change would be to use preliminary (perhaps overly aggressive) information only to tentatively detect impossible conditional branches. This would enable Python to derive that the return value of
(lambda () (loop with x = 0 while (foo) do (case x (1 (setf x 2)) (2 (setf x 1))) finally (return x)))
is always 0 (and never 1 or 2), or that the expression
(if (eql x y) (eql x y) t) is always true.
With suitable handling of calls to local functions, useful types might even be derived for recursive functions. The current type propagation pass derives insanely stupid types for recursive functions and for assignment to variables in loops (unless the iteration variable hack suffices). For example
(lambda () (labels ((foo (x) (if (bar) (foo (1+ x)) x))) (foo 42)))
is derived to return an arbitrary NUMBER. Instead, the return type of local functions can be initialised to the empty type (in which case propagation must be stopped for the caller block) and extended as argument types grow and as recursion triggers more propagation.
The problem is that this more precise flow-sensitive pass loses the finite chain condition: there is no guarantee that the least fixed point will always be reached in finite time. The current constraint propagation pass operates on a finite lattice: only variables and types that exist in the input IR1 graph can appear in constraints, so the fixpointed function is defined over the powerset of this finite set of constraints for each basic block. In contrast, the full CL type universe is most definitely not finite (type tests aren’t even decidable in general).
There is a simple solution to this problem: before extending the constraint universe, widen types to satisfy the finite chain condition, i.e., make sure that types eventually stop growing. For example, when taking a non-trivial union or intersection of types, the result could be quantised to a coarse set of types (singleton types, named class types, a few key numeric ranges, etc.). Appropriate widening can also accelerate finite but slow convergence; the resulting fixed point isn’t guaranteed to be minimal, but is always valid. In fact, widening is likely to be necessary for the first improvement (with redundant dictionaries) as well.
Another issue in the constraint propagation pass is an instance of the phase ordering problem. Some source-to-source transforms help type propagation (e.g., turning complicated functions into simpler ones for which type propagation is feasible), and others hinder it (e.g., converting integer division by a constant to multiply and shift or MAPCAR to an inline loop). Worse, there’s a dependency cycle as transforms rely on type propagation to determine whether they are applicable. There’s been some academic work that exposes multiple equivalent code sequences to analyses, and it seems possible to do something similar in Python as well: source-to-source transforms generate functions, so we’d “only” have to analyse the function without splicing it in. However, that’s likely to be impractically slow (even termination is non-obvious)... perhaps it will be doable for select transforms that expand into pure expressions.
The only suggestion to accelerate constraint propagation so far is to widen types, and that mostly compensates for slowdowns (or infinite convergence) introduced by other changes. There’s a classic trick that ought to accelerate even the current pass: guide the order in which basic blocks are analysed by partitioning them in strongly connected components. Python exploits a simple ordering technique, a depth-first ordering that minimises backward edges in reducible control-flow graphs. Basic blocks could instead be partitioned into strongly connected components: contracting each strongly connected component into a single vertex leaves a directed acyclic graph. It then suffices to fixpoint on each strong component and traverse the condensed DAG so that each component is only visited after all its predecessors. Python already computes loop nests, so that’s an easy change; it’s likely even better to look at nested loops and recursively order analysis within each component. A few other passes perform some form of dataflow analysis and would benefit from that improved ordering... perhaps compile times can be really improved (Amdahl says that’s unlikely until splicing in source-to-source transformations is a lot quicker).
In terms of implementation difficulty, these changes probably go 1-6-3-4-2-5. This also happens to be the order in which I’d try to implement them.
A long time ago we talked about how to
Import fixed width data with pgloader, following up on other stories still
Postgres OnLine Journal and on
David Fetter's blog. Back then, I
showed that using pgloader made it easier to import the data, but also
showed quite poor performances characteristics due to using the
in the timings. Let's update that article with current
Let's be fair, hardware did evolve in those past 3 years, and the test that ran in 14 seconds was done with debug information level, which is the wrong way to do tests.
$ ~/dev/pgloader-v2/pgloader.py -R. -Tsc census.conf Table name | duration | size | copy rows | errors ==================================================================== fixed | 1.834s | - | 25375 | 0
I got timings anywhere betseen 1.5 seconds and 1.834 seconds here.
Now with the current version of pgloader, what do we get:
$ pgloader.exe census-place.load 2013-11-18T12:02:35.001000+01:00 LOG Starting pgloader, log system is ready. 2013-11-18T12:02:35.003000+01:00 LOG Parsing commands from file "/Users/dim/dev/pgloader/test/census-places.load" table name read imported errors time ------------------------------ --------- --------- --------- -------------- download 0 0 0 1.587s extract 0 0 0 1.010s before load 0 0 0 0.014s ------------------------------ --------- --------- --------- -------------- places 25375 25375 0 0.366s ------------------------------ --------- --------- --------- -------------- Total import time 25375 25375 0 2.977s
So the loading itself took as much as 366 milliseconds to run. To be fair that's kind of a best run, with run times varying between that and 700 milliseconds.
So the new version is about 3 to 9 times faster depending on the story you want to tell. Let's stick with much faster for the sake of this article.
The new loader takes a full command as its input, rather than a configuration file. Here's what the command I've used this time looks like:
LOAD ARCHIVE FROM http://www.census.gov/geo/maps-data/data/docs/gazetteer/places2k.zip INTO postgresql:///pgloader BEFORE LOAD DO $$ drop table if exists places; $$, $$ create table places ( usps char(2) not null, fips char(2) not null, fips_code char(5), loc_name varchar(64) ); $$ LOAD FIXED FROM FILENAME MATCHING ~/places2k.txt/ WITH ENCODING latin-1 ( -- name start length usps 0 2, fips 2 2, fips_code 4 5, loc_name 9 64, p 73 9, h 82 9, land 91 14, water 105 14, ldm 119 14, wtm 131 14, lat 143 10, long 153 11 ) INTO postgresql:///pgloader?places ( usps, fips, fips_code, loc_name text using (right-trim loc_name) );
First, the URL used in the blog post of april 2010 is no longer valid. You can find a list of other interesting data at the Census 2000 Gazetteer Files page, and of course you have more recent version of the data available. In another format entirely, this time tab-based csv-like, so better for general usage, but not for this test where I wanted to reuse the same data source as 3 years ago.
What we can see in that command is that pgloader will actually download the zip archive file from its http source URL, unzip it locally then work on the filename from the archive matching the one we know about: we don't want to hardcode in the command the name of the directory contained in the zip file.
Also, contrary to the previous version, it's quite easy to just trim the
loc_name column as we load the data. Here I've been adding a new function to
do that, because I wanted to play with optimizing it (adding type
declarations and inlining it), but the loading works about as well with just
the following (just timed 3 runs at
INTO postgresql:///pgloader?places ( usps, fips, fips_code, loc_name text using (string-right-trim " " loc_name) );
The string-right-trim function is part of the Common Lisp Standard. The optimisation here looks like:
(declaim (inline right-trim)) (defun right-trim (string) "Remove whitespaces at end of STRING." (declare (type simple-string string)) (string-right-trim '(#\Space) string))
Note that you could be providing that definition in your own
and provide it using the
--load trim.lisp command line option, pgloader
would then compile that to machine code for you before processing your data
If you're already using pgloader, you will enjoy the new version of it! The new version comes with a command line option to migrate the old configuration file into a command string, making upgrades even easier.
Of course, if you're interested, consider giving the release candidate a try, it's available on the pgloader github repository already.
Over in comp.lang.lisp Jeff writes.
With the permission and assistance of the author himself, Bernie Cosell, I have added the original Lisp Eliza to the Eliza Generations collection. Cosell wrote this Lisp version of Eliza at BBN in the mid-late 1960s. (Weizenbaum's original was written in about 1966 in SLIP, a long-dead Fortran-based symbol processing package.)
Thanks to Peter Seibel for connecting me with Bernie Cosell.
!!YOU CAN HELP!!
One way that you can help is by writing to Deborah Cotton (cot…@hq.acm.org) at the ACM permissions office and encourage them to open source Weizenbaum's paper, which is still inaccessible under copyright protections.
Second, I'm hoping to create a "perfect" OCR of this code and then macrify it to run on CL with as little modification as possible. You can help create the codebase for this by choosing a single page at random from among the 48 TIFFs, manually entering the code as precisely as possible (including indentation) into a text file, and then emailing it to me: jshr…@stanford.edu. If you decided to do this, here are a few details worth attending to: So that we get good coverage, please really choose a TIFF file at random, e.g., via the moral equivalent of (1+ (random 48)). Please don't just OCR the TIFF file; I've already tried this with very high end OCR tools, and they make terrible encodings of this sort of thing! It would help me do the reconstruction is you put the name of the TIFF file in a leading comment. Finally, if you would like to be explicitly acknowledged for your efforts, please include a comment line for yourself as well. The codebase will be released on github or some such public location. Then you'll be able to help actually hack it!
Finally, if you know of open source Elizas, in any language, roaming around the net, please send me links to them so that I can update the "more recent" section of the page.
Which is a delightful boondoggle. And, as I’ve currently got a lousy cold transcription is amount the most strenuous activity I’m up for. So, I’ve done two pages. This gave me Interlisp flashbacks, which was fun.
They are very short, so you should do a few too. Grab a random page here.
You can use this bash oneliner to pick a random page
curl -s http://shrager.org/eliza/20131112-Eliza600dpiRawScansRenamed/index.html | grep -o '>Eliz.*TIF' | sed -n $(( 1 + $RANDOM % 48 ))p
and then grab that page from here: http://shrager.org/eliza/20131112-Eliza600dpiRawScansRenamed/index.html
There were 35 candidates registered for the Minneapolis mayoral race this year. Minneapolis approved ranked-choice voting in 2006. I have great respect and deep sympathy for those who had to tabulate all of those votes. And, because there is no FEC-certified software for counting this type of vote, it was a huge human effort.
The Minnesota Secretary of State’s website has information about which candidates where eliminated in which of the 33 elimination rounds in the tabulation. I scraped the data from their Excel spreadsheet, added some Vecto, and put together some worm-trail charts. I couldn’t quite use Zach’s wormtrails library because I wanted to show how an eliminated candidates votes were redistributed (to other candidates who were lower-ranked choices or to the
exhausted bucket). Also, note: the tabulated data on the Minnesota Secretary of State’s website is insufficient to form an accurate proportioning in rounds when multiple candidates are eliminated. In those cases, I just assumed that all candidates whose votes were redistributed were redistributed in the same proportions to the candidates who gained votes because of the eliminations in that round.
The white worm-trail through the center is the
exhausted pile. Unfortunately, the eliminated candidates in the first 25 or so rounds had so few votes that I’d have to render these images wall-sized for you to get any idea what proportion of their votes went where. In the final few rounds, you can see some detail even with a semi-reasonable file size. I suppose I should see if I can wrangle the data from the St. Paul race which only had six candidates (and thus fewer than six rounds of counting).
Note for Lisp folks: I don’t like the above code. I like short functions, but I also like using
labels to make functions that are still within lexical scope of a whole mess of variables. Anyone else come to a good resolution between those two things? Is bundling data in structs and classes really the right thing or a sea of global specials?
gitrepository can be found there.
(document #P"asdf/uiop/" :documentation-title "UIOP" :everything t :exclude-files (list #P"/Path/To/asdf3/asdf/uiop/asdf-driver.asd") :special-methods-defs-files (list #P"/This/file/here/helambda-asdf3.lisp") )
documentfunction is called on a folder (
"asdf/uiop/") with an obvious title. The other arguments have the following meaning:
:everything ttells HEΛP to generate documentation pages for everything; these are stored in the
dictionarysubfolder with file-names which should be relatively obvious. Ordinarily, HEΛP would generate doc pages only for public (i.e., exported) interfaces.
:exclude-filesis a list of files to forget about; UIOP has one file with an unqualified
DEFSYSTEMin, which confuses HEΛP.
special-methods-defs-filesis a list of files containing specialized definitions to handle a library extra "definition" forms and macros. UIOP has a number of them.
Here's a neat use of CL: a bike configurator expert system. A few details are available. Here's a bit I liked:
Bike Friday builds so many bicycles that to photograph everything would not be possible. Even with the limited component selection displayed in the cartoons there are over 15,000 cartoons generated just for the ~130 starting designs so far in the system.
The cartoon generator works by using CXML to load a master SVG file, remove all but the appropriate layers for a given model, and then colorizing different parts of the bike using a mix of SVG patterns and RGB hex codes depending on the bike and color selection. It then uses ImageMagick to convert the generated SVG file to JPG.
You can read more on reddit.
A few months ago, Valeriy Zamarayev started adding support for ZeroMQ 3.2 to lisp-zmq. There is no point sticking to ZeroMQ 2.2 forever, so I recently decided to migrate to 3.2. lisp-zmq initially supported ZeroMQ 3.2 in the
zmq3 branch only, but I merged this branch into master and released a new stable version.
You can download it as always on http://wandrian.net/lisp-zmq.html. Note that Github does not provide static file hosting anymore, so this page is now the only official source for stable lisp-zmq releases.
It should still be compatible with ZeroMQ 2.2; of course the new functions of ZeroMQ 3.2 are not available in that case.
As usual, contact me if you have any problem with this new release.
A while ago I created an Atom feed for new Common Lisp projects on github. Unfortunately, the github page from which it scraped its data was removed a few months ago. Fortunately, Matt Niemeier just sent me a patch to the github scraper to make it work with the github API. Thanks, Matt!
So if you want to see a daily feed of new Common Lisp stuff on github, point your favorite feed reader here:
(I don’t usually post requests for recruiters, but this one might be ok. Send me a note or make a comment if you find out otherwise. Looks like it’s really a Lisp and Python position).
Job Title: LISP Developer
Work Location: Cambridge, MA 02142
Hourly Pay Rate Range: $60-$70/hr
Employment Terms: 1 year W2 Contract
BS degree preferred (or equivalent experience) in an Engineering or IT-related field. At least 4 years experience in software development delivering and maintaining production quality code. Familiarity with testing, QA, version control and delivery technologies. Experience in multi-tiered distributed application environments.
Demonstrable expertise in: Lisp, XML, Oracle, SQL
Strong analytical, problem-solving, negotiation, and organizational skills. High attention to detail, the ability to focus and deliver, and agility under pressure. Strong communication and collaboration skills.
[Note that this position requires demonstrated expertise and skills in the Lisp programming language.]
Notes from the Manager:
Seeking experience in supporting and maintaining data bases and for mission critical software. Must have python. Seeking someone assertive to manage client expectations and deadlines. Take ownership of the projects
Contact: Tyler Goulet | firstname.lastname@example.org | 650-598-5603
Runa is now Staples Innovation Lab. For the past 5+ years, Runa has been a visible member of the Clojure community, having built their entire e-commerce optimization stack on Clojure. We were recently acquired by Staples, the second largest internet retailer in the world.
We now have the resources to take the Clojure + Big Data + Machine Learning + Real Time Predictive Modeling engine to the next level. We’re looking for experienced engineers with knowledge of Clojure. More details at www.staplesinnovationlab.com
From: "R. Matthew Emerson"
Subject: [Openmcl-devel] ccl and recent Apple updates
To: openmcl-devel Development
Date: Thu, 24 Oct 2013 13:49:11 -0400
Some people have reported problems building ccl after updating to Xcode 5, or after updating to OS X Mavericks.
The version of Subversion that is included with Xcode 5 uses a new working copy format. Past versions of Subversion would upgrade working copies automatically and silently, but this time, the Subversion developers decided to require manual intervention.
Go to your ccl directory and run "svn update" by hand, and note that it prints out a message prompting you to run "svn upgrade". Run "svn upgrade" as it prompts.
On OS X Mavericks, it appears that installing Xcode does not install include files in /usr/include. It used to be the case that you could solve this problem by downloading the Command Line Tools from Xcode's preference panel. On Mavericks, this no longer appears to be an option. Instead, you must run "xcode-select --install" from a terminal. This will show a dialog, make you agree to some license or other, and then offer to download the files that ccl needs in order to build. It may even be the case that you don't need to download Xcode just to install the command-line tools, which would save you a 2 GB download if you only want to rebuild ccl. </blockqoute>
Hello, the fooble project has a bug that breaks the barble project. Please use my fixed version at ...I would much rather get an email like this:
Hello, I created the fooble project but will not be working on it any more. The new maintainer is making updates in a new repo at ...This is next best:
Hello, I contacted the original maintainer of the fooble project and have agreed to become the new maintainer. The new repo is at ...This isn't feasible if the original maintainer is unavailable or unresponsive for a long period of time. But I would like to see an effort to make this kind of transition before updating Quicklisp. So this kind of email is third best:
Hello, I tried to contact the original maintainer of the fooble project but haven't heard anything back in months. I would like to be the new maintainer and the new repo, with fixes, is at ...Thanks!
(defclass master-catalog () ;; subsystems and products (PC's) in this repository ((products :initform nil :version-technique :composite-set :accessor master-catalog/products) (subsystems :initform nil :version-technique :composite-set :accessor master-catalog/subsystems) ;; All satellite repositories known to this master. We don't allow ;; satellite repository names to change, though the projects they ;; contain may be renamed. **WARNING** BE CAREFUL IF YOU OPERATE ;; in non-latest metaversion views of this list or you might try to ;; create a satellite which already exists. Only update this list ;; using the latest metaversion. (satellite-repositories :initform nil :version-technique :composite-set) ;; Projects (a.k.a. ChangeSafe "classes") contained in satellite ;; repositories. The descriptors contain the key mapping from a ;; project name to a satellite-repository-name. We could almost ;; make this just a (project-name . satellite-name) mapping, but we ;; need to version project-name, and we also want to cache in the ;; master some information in the satellites so that we don't ;; always have to examine the satellites for often accessed ;; information. (classes :accessor master-catalog/classes :initform nil :version-technique :composite-set) ;; Cset-relationship-tuples is conceptually a list of sublists, ;; where each sublist is a tuple. For every master cid which ;; results in the creation of satellite cids, a tuple is added ;; which enumerates the master cid and the satellite cids which it ;; caused to be created. e.g. '((master.cid.1 satellite-1.cid.1 ;; satellite-2.cid.1)) Because we want portable references, blah ;; blah blah, we actually reference DIDS of CHANGE-SET objects ;; rather than the cids. We may instead wish to store CID-OBJECT ;; references. TBD. ;; Right now, this information is maintained only for change ;; transactions which arise from WITH-CM-MASTER-TXN and ;; WITH-CM-SATELLITE-TXN. This is ok, since those are the ;; interesting txns which manipulate satellite databases. ;; Note that because of the high volume of csets we expect to ;; track, we actually represent this information as a vector of ;; vectors to achieve space compaction. (cset-relationship-tuples :initform (make-instance 'persistent-vector :initial-element nil :size 1) :version-technique :nonversioned) (cset-rel-tuples-index :initform (make-instance 'persistent-vector :initial-element -1 :size 1) :version-technique :nonversioned) ;; BOTH these slots are updated ONLY by vm-txn-note-change-set, ;; except for schema upgrading. ;; The cset-rel-tuples-index slot is a conceptual hash table into the ;; cset-relationship-tuples slot. This is used by ;; master-catalog-lookup-cset-relationship ;; to avoid an extremely costly linear search of cset-relationship-tuples. ;; This is very important for cset_add, cset_remove, and csets_from_file. ;; The idea is that the did-string of the master-cid's did is hashed. ;; Reducing that hash modulo the number of entries in cset-rel-tuples-index, ;; finds a "home" index of cset-rel-tuples-index. Using the sb32 value ;; in that element, we either have a -1 (so the entry is not in the ;; hash table) or we get an index into cset_relationship_tuples. ;; If there is no hash collision, that element of cset_relationship_tuples ;; will contain the desired master-cid did we are looking for. If it ;; isn't the one we want, we have had a hash collision, and we resolve it ;; by linear probing in the next-door (circularly) element of ;; cset-rel-tuples-index. ;; The number of elements of cset-rel-tuples-index is always a prime number, ;; and is also maintained to be more than twice as large as the number of ;; entries in cset-relationship-tuples. That is important, to prevent ;; clustering and slow searching. So when it grows, cset-rel-tuples-index ;; grows by a reasonable factor (about 2) so that it always contains ;; at least half "holes", that is, -1. Further, we want to avoid frequent ;; growth, because growing requires computing every entry in the hash table ;; again. That makes for a big transaction, as every element of the ;; cid-relationship-tuple vector has to be mapped in, and rehashed with ;; the new size of cset-rel-tuples-index. ;; Space considerations: In Jack's db, there are roughly 40,000 elements ;; currently in the cset-relationship-tuples. Suppose we had 100,000 ;; elements. In Jack's db, it appears that the tuples are about 2 elements ;; each, average. Suppose it were 9. Then the tuples would take 4*(1+9)=40 ;; bytes each, so 40*100,000 = 4Mb total (plus another 400,000 for the ;; cset-relationship-tuples vector itself). This is large, but not likely ;; to be a cause of breakage anytime soon. ;; The cset-name-hashtable maps cset names to csets. While the HP ;; model of ChangeSafe doesn't allow changing the name of a cset, ;; we allow this in general. So this hash table is keyed by cset ;; name, and valued by all csets which EVER bore that name in their ;; versioned name component. The hash value is therefore a list. ;; In the case of system augmented names (by ;; change_create/master_change), there shouldn't be any collisions. ;; We also use this slot to hash unaugmented user names to csets, ;; and those are far more likely to have collisions (one key -> ;; multiple csets). In the case of un-augmented names, this is ;; expected. In the case of augmented names, this is an error. (cset-name-hashtable :version-technique nil :initform (make-instance 'persistent-hash-table :size 1023) :reader master-catalog/cset-name-hashtable) ) (:documentation "Catalog/hierarchy-root of versioned information maintained in the master repository.") (:metaclass versioned-standard-class) (:schema-version 0))Pretty straightforward, no? No? Let's list the products in the master catalog:
(defun cmctl/list-products (conman-request) "cheesy hack to list the products" (let ((master-repository-name (conman-request/repository-dbpath conman-request)) (reason "list products") (userid (conman-request/user-name conman-request))) (call-with-master-catalog-transaction master-repository-name userid :master-metaversion :latest-metaversion :version :latest-version :reason reason :transaction-type :read-only :receiver (lambda (master-repository master-transaction master-catalog) (declare (ignore master-repository master-transaction)) (collect 'list (map-fn 't (lambda (product) (list (distributed-object-identifier product) (named-object/name product) (described-object/description product))) (master-catalog/scan-products master-catalog)))))))That isn't very edifying.
(master-catalog/scan-products master-catalog)defined as
(defun master-catalog/scan-products (master-catalog) (declare (optimizable-series-function)) (versioned-object/scan-composite-versioned-slot master-catalog 'products))The
optimizable-series-functiondeclaration indicates that we are using Richard Waters's series package. This allows us to write functions that can be assembled into an efficient pipeline for iterating over a collection of objects. This code:
(collect 'list (map-fn 't (lambda (product) (list (distributed-object-identifier product) (named-object/name product) (described-object/description product))) (master-catalog/scan-products master-catalog)))takes each product in turn, creates a three element list of the identifier, the project name, and the product description, and finally collects the three-tuples in a list to be returned to the caller. Here is what it looks like macroexpanded:
(COMMON-LISP:LET* ((#:OUT-917 MASTER-CATALOG)) (COMMON-LISP:LET (#:OUT-914) (SETQ #:OUT-914 'PRODUCTS) (COMMON-LISP:LET (#:OUT-913 #:OUT-912) (SETQ #:OUT-913 (SLOT-VALUE-UNVERSIONED #:OUT-917 #:OUT-914)) (SETQ #:OUT-912 (IF *VERSIONED-VALUE-CID-SET-OVERRIDE* (PROGN (DEBUG-MESSAGE 4 "Using override cid-set to scan slot ~s" #:OUT-914) *VERSIONED-VALUE-CID-SET-OVERRIDE*) (TRANSACTION/CID-SET *TRANSACTION*))) (COMMON-LISP:LET (#:OUT-911 #:OUT-910 #:OUT-909) (MULTIPLE-VALUE-SETQ (#:OUT-911 #:OUT-910 #:OUT-909) (CVI-GET-ION-VECTOR-AND-INDEX #:OUT-913 #:OUT-912)) (IF #:OUT-911 NIL (PROGN (IF (COMMON-LISP:LET ((#:G717-902 #:OUT-910)) (IF #:G717-902 #:G717-902 (THE T (CVI/DEFAULT-ALLOWED #:OUT-913)))) NIL (PROGN (SLOT-UNBOUND (CLASS-OF #:OUT-917) #:OUT-917 #:OUT-914))))) (DEBUG-MESSAGE 5 "Active ion vector for retrieval: ~s" #:OUT-911) (COMMON-LISP:LET (#:OUT-908) (SETQ #:OUT-908 (IF #:OUT-911 #:OUT-911 (THE T #()))) (COMMON-LISP:LET (#:ELEMENTS-907 (#:LIMIT-905 (ARRAY-TOTAL-SIZE #:OUT-908)) (#:INDEX-904 -1) (#:INDEX-903 (- -1 1)) #:ITEMS-915 #:ITEMS-900 (#:LASTCONS-897 (LIST NIL)) #:LST-898) (DECLARE (TYPE SERIES::VECTOR-INDEX+ #:LIMIT-905) (TYPE SERIES::-VECTOR-INDEX+ #:INDEX-904) (TYPE INTEGER #:INDEX-903) (TYPE CONS #:LASTCONS-897) (TYPE LIST #:LST-898)) (SETQ #:LST-898 #:LASTCONS-897) (TAGBODY #:LL-918 (INCF #:INDEX-904) (LOCALLY (DECLARE (TYPE SERIES::VECTOR-INDEX+ #:INDEX-904)) (IF (= #:INDEX-904 #:LIMIT-905) (GO SERIES::END)) (SETQ #:ELEMENTS-907 (ROW-MAJOR-AREF #:OUT-908 (THE SERIES::VECTOR-INDEX #:INDEX-904)))) (INCF #:INDEX-903) (IF (MINUSP #:INDEX-903) (GO #:LL-918)) (SETQ #:ITEMS-915 ((LAMBDA (ION-SOUGHT) (CVI-INSERTION-RECORD/GET-VALUE-FOR-ION (SVREF #:OUT-909 ION-SOUGHT) ION-SOUGHT)) #:ELEMENTS-907)) (SETQ #:ITEMS-900 ((LAMBDA (PRODUCT) (LIST (DISTRIBUTED-OBJECT-IDENTIFIER PRODUCT) (NAMED-OBJECT/NAME PRODUCT) (DESCRIBED-OBJECT/DESCRIPTION PRODUCT))) #:ITEMS-915)) (SETQ #:LASTCONS-897 (SETF (CDR #:LASTCONS-897) (CONS #:ITEMS-900 NIL))) (GO #:LL-918) SERIES::END) (CDR #:LST-898)))))))To be continued...
We're looking for a talented algorithmic developer with solid Lisp skills and an interest in linguistics and natural language processing.
At Grammarly, we use Common Lisp, but if you've worked with some other Lisp flavour, that's fine, as long as you're willing to learn and master Common Lisp. It goes without saying that you should be well versed in both object-oriented and functional paradigms. You also have to be comfortable with the idea of coding some Java and, preferably, have some hands-on experience with it. We'll give you bonus points if you have a broad technical background and notable achievements beyond Lisp, contribute to open-source, write a blog or are otherwise active in the tech community.
You will get to work with amazing engineers, linguists, and business minds from all over the world and experience the magic of direct access within a small team that pays attention to your ideas and contributions. In turn, we expect you to continuously learn, strive for perfection and optimum performance, as well as derive joy from sharing with and helping your peers.
We love people who are open, honest, kind, cheerful and have a decent sense of humor.
If you are interested, drop us a line at email@example.com.
D-Wave is seeking an experienced Software Developer with extensive Common Lisp (or equivalent) programming and UNIX-based system administration experience to join the Processor Development group. The successful candidate will be responsible for architecting, designing, programming, testing and maintaining the entire suite of software necessary to support the testing and operation of D-Wave’s quantum computing hardware. The software is predominantly Common Lisp-based and is an integral part of the quantum computing system. It is used for a variety of purposes including calibration, operation, testing and benchmarking.
For more details please see http://www.dwavesys.com/en/files/13PD09_Software_Developer.pdf
Reasons here: http://article.gmane.org/gmane.lisp.ecl.general/10264
Juanjo sent en email yesterday about about the status of ECL:
* First of all, ECL no longer relates to my own work. On the contrary, other open source projects that I carry on (https://github.com/juanjosegarciaripoll?tab=repositories) are more directly related to my research and are demanded by my group. This is detracting development time from the project, but there is little I can do, as that numerical software is what feeds our bellies right now.
* Not only does my work consume most of my open-software development time, but the job overall does significantly constraint the time I can spare for the project. As group leader in a research environment with scarce resources, I spend more time writing grant applications and bureaucracy than I do in front of Emacs. Quite frustrating as it is, I only see it worsening in the near future.
* The consequence is that the time I can devote to ECL has serious ups and downs. In an environment of rapidly developing tools and libraries, this is quite unfortunate, as the project may lag behind and become obsolete. This is indeed what has happened with several of the ports out there.
* On top of this, there are a lot of frustrating things that I did not want to care about but which are bugging me right now and also stealing time. The first one is the license issue. I put out a suggestion to migrate to MPIR because I knew that MPIR had an effort to stay with LGPL2. Regrettably, I did not know that this effort was abandoned so that if ECL wishes to upgrade to any more recent version of GMP/MPIR it has to migrate to LGPL3.
* Another nagging issue is testing. You have suffered this in the past and it still is a problem: my testing environment is broken and I do not have time to fix it. Despite Anton's wonderful library, the fact is that it is a heck of a problem to maintain several virtual machines and computers in an uncooperative computing environment with frequent blackouts.
* Finally, on the one hand, there are many new upcoming implementations out there, some with promising results and features that I do not have the time to incorporate -- but which would be simple with resources -- and certain forks are consolidating. On the other hand, despite ten years of development, I have failed to aggregate any number of contributing developers around this project. This may be blamed on the community or on myself, and it does not match the supportive and helpful user base that ECL has always had, but the fact is that it is a problem and a time has come to accept it [but please, I do not need your pity on the IRC channels, ok?]
Though I did not have time to develop, I had time to think, even if on the bus trips and planes, and I came to the following conclusions:
* I am resigning and opening the position of ECL maintainer for anyone to take. I will grant him or her with full administrative rights and full responsibility over the project's future. No need to fork the project: if you really feel you can make it better, step ahead and take it. I will remain as a support developer and help you as much as I can.
* If no one takes over maintenance, I will continue working as I can, when I can. This may be unsatisfactory for many of you -- if this is the case, I am sorry, but that's all there is.
asdf-package-system 2K -- No license specified? No description provided. git: git://common-lisp.net/projects/asdf/asdf-package-system.git ayah-captcha 4K -- MIT A simple interface to the API of the play-thru captcha of areYouAHuman.com author: Andy Peterson git: https://github.com/aarvid/ayah-captcha.git more: https://github.com/aarvid/ayah-captcha#readme cl-binaural 4K -- GPL Utilities to generate binaural sound from mono author: Alexander Popolitov git: https://github.com/mabragor/cl-binaural.git more: https://github.com/mabragor/cl-binaural#readme fgraph 6K -- EUPL V1.1 No description provided. author: Thomas Bartscher mercurial: https://bitbucket.org/thomas_bartscher/cl-fgraph more: https://bitbucket.org/thomas_bartscher/cl-fgraph cl-larval 20K -- GPL Lisp syntax for assembler for AVR microcontrollers author: Alexander Popolitov git: https://github.com/mabragor/cl-larval.git more: https://github.com/mabragor/cl-larval#readme cl-ply 10K -- LLGPL A library to handle PLY file format which is known as the Polygon File Format or the Stanford Triangle Format in Common Lisp. author: Masayuki Takagi git: https://github.com/takagi/cl-ply.git more: https://github.com/takagi/cl-ply#readme cl-server-manager 5K -- MIT Manage port-based servers (e.g., Swank and Hunchentoot) through a unified interface. author: Wei Peng git: https://github.com/pw4ever/cl-server-manager.git more: https://github.com/pw4ever/cl-server-manager#readme cl-spark 10K -- MIT License Generates sparkline string for a list of the numbers. author: Takaya OCHIAI git: https://github.com/tkych/cl-spark.git more: https://github.com/tkych/cl-spark#readme curry-compose-reader-macros 2K -- GPL V3 reader macros for concise function partial application and composition author: Eric Schulte git: https://github.com/eschulte/curry-compose-reader-macros.git more: https://github.com/eschulte/curry-compose-reader-macros#readme drakma-async 26K -- MIT An asynchronous port of the Drakma HTTP client. author: Andrew Danger Lyon git: https://github.com/orthecreedence/drakma-async.git more: https://github.com/orthecreedence/drakma-async#readme draw-cons-tree 2K -- Public Domain Makes and ascii picture of a cons tree author: Ported by:CBaggers - Original Author:Nils M Holm git: https://github.com/cbaggers/draw-cons-tree.git more: https://github.com/cbaggers/draw-cons-tree#readme filtered-functions 5K An extension of generic function invocation that add a preprocessing step before the usual dispatch. No description provided. author: Pascal Costanza darcs: http://common-lisp.net/project/closer/repos/filtered-functions/ more: http://common-lisp.net/project/closer/filtered.html graph 37K -- GPL V3 Simple library for building and manipulating graphs. author: Eric Schulte, Thomas Dye git: https://github.com/eschulte/graph.git more: https://github.com/eschulte/graph#readme lisphys 19K -- Specify license here Describe lisphys here author: Guillaume git: https://github.com/kayhman/lisphys.git more: https://github.com/kayhman/lisphys#readme mailbox 2K -- MIT Simple multithreading mailboxes. author: Lucien Pullen git: https://github.com/drurowin/mailbox.git more: https://github.com/drurowin/mailbox#readme map-set 2K -- BSD 3-clause (See LICENSE) Set-like data structure. author: Robert Smith mercurial: https://bitbucket.org/tarballs_are_good/map-set more: https://bitbucket.org/tarballs_are_good/map-set cl-oneliner 3K -- wtfpl Given a piece of text, summarize it with a one-liner author: mck- git: https://github.com/mck-/oneliner.git more: https://github.com/mck-/oneliner#readme pooler 4K -- MIT A generic pooler library. author: Abhijit Rao git: https://github.com/quasi/pooler.git more: https://github.com/quasi/pooler#readme readable 443K -- MIT 'Readable' extensions to Lisp s-expresions: curly-infix, neoteric, and sweet expressions author: David A. Wheeler git: git://git.code.sf.net/p/readable/code more: http://readable.sourceforge.net/ simple-currency 13K -- BSD, 2 clause. Currency conversions using data published daily by the European Central Bank. author: Peter Wood git: https://github.com/a0-prw/simple-currency.git more: https://github.com/a0-prw/simple-currency#readme smackjack 17K -- MIT A small Ajax framework for hunchentoot using parenscript author: Andy Peterson git: https://github.com/aarvid/SmackJack more: https://github.com/aarvid/SmackJack#readme snappy 7K -- New BSD license. See the copyright messages in individual files. An implementation of Google's Snappy compression algorithm. author: Robert Brown git: https://github.com/brown/snappy.git more: https://github.com/brown/snappy#readme spellcheck 2,376K -- MIT Peter Norvig's spell corrector. author: Mikael Jansson git: https://github.com/RobBlackwell/spellcheck.git more: https://github.com/RobBlackwell/spellcheck#readme tagger 1,107K -- No license specified? No description provided. git: https://github.com/g000001/tagger.git more: https://github.com/g000001/tagger#readme
As usual many older packages were revised.
For older items, see the Planet Lisp Archives.
Last updated: 2013-11-30 00:00