25 Jul 2017

feedPlanet Lisp

Quicklisp news: June 2017 Quicklisp download stats

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

25 Jul 2017 7:13pm GMT

Quicklisp news: July 2017 Quicklisp dist update now available

New projects:

Updated projects: 3d-vectors, assoc-utils, cepl, cl+ssl, cl-ana, cl-autowrap, cl-dbi, cl-emoji, cl-fluent-logger, cl-fond, cl-hash-util, cl-kanren, cl-mixed, cl-opengl, cl-pdf, cl-rail, cl-random-forest, cl-ssdb, cl-str, cl-typesetting, cl-webdav, clavier, closer-mop, clsql-fluid, coleslaw, croatoan, deeds, dexador, doubly-linked-list, femlisp, flac-parser, fs-utils, gamebox-dgen, gamebox-ecs, gamebox-frame-manager, gamebox-grids, gamebox-math, genie, glkit, harmony, hu.dwim.web-server, hu.dwim.zlib, hunchentoot, infix-math, inquisitor, jsonrpc, kenzo, lack, lake, lichat-protocol, lichat-serverlib, lichat-tcp-server, lichat-ws-server, local-time, maiden, mcclim, mito, mito-auth, ningle, parseq, pgloader, physical-quantities, plump, py-configparser, qlot, ratify, roan, rtg-math, rutils, sanitized-params, serapeum, simple-logger, sketch, spinneret, staple, stumpwm, trivia, websocket-driver, woo.

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!


25 Jul 2017 4:26pm GMT

15 Jul 2017

feedPlanet Lisp

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

(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:

README-PREPARE.txt

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 \
        --gradle \
        --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!

15 Jul 2017 1:00am GMT

01 Jul 2017

feedPlanet Lisp

Quicklisp news: June 2017 Quicklisp dist update now available

New projects:

Updated projects: 3d-matrices, 3d-vectors, architecture.builder-protocol, architecture.service-provider, ayah-captcha, caveman, caveman2-widgets-bootstrap, cepl, cepl.camera, cepl.devil, cepl.sdl2, cepl.sdl2-image, cepl.sdl2-ttf, cepl.skitter, cffi, cl+ssl, cl-ana, cl-ansi-term, cl-bloom, cl-dbi, cl-emoji, cl-fond, cl-gamepad, cl-gists, cl-glfw3, cl-graph, cl-haml, cl-hash-util, cl-jpeg, cl-monitors, cl-mssql, cl-ntp-client, cl-ohm, cl-opengl, cl-out123, cl-plplot, cl-readline, cl-scsu, cl-soil, cl-str, cl-twitter, clack, clim-widgets, closer-mop, clsql-fluid, clss, clx, croatoan, curry-compose-reader-macros, deeds, dendrite, dirt, documentation-utils, doubly-linked-list, drakma, easing, erudite, esrap, f2cl, fare-scripts, fast-http, fast-io, femlisp, fs-utils, fxml, gamebox-dgen, gamebox-ecs, gamebox-frame-manager, gamebox-grids, gamebox-math, gettext, glaw, glkit, glop, glsl-spec, glsl-toolkit, horner, http-get-cache, hu.dwim.asdf, hu.dwim.util, hu.dwim.web-server, inquisitor, iolib, jsonrpc, jwacs, l-system, lichat-protocol, livesupport, log4cl, macrodynamics, maiden, mcclim, media-types, metatilities, mito, mk-string-metrics, opticl, parachute, png-read, prbs, qlot, qmynd, qtools, rtg-math, rutils, scalpl, scriptl, sdl2kit, serapeum, simple-logger, sketch, skitter, smackjack, spinneret, staple, structy-defclass, stumpwm, the-cost-of-nothing, tm, translate-client, trivial-main-thread, trivial-mmap, trivial-shell, trivial-update, uffi, umlisp, unix-opts, varjo, weblocks, websocket-driver, whofields, with-cached-reader-conditionals, woo, yaclml.

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

01 Jul 2017 6:54pm GMT

17 Jun 2017

feedPlanet Lisp

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

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.

17 Jun 2017 7:24pm GMT

12 Jun 2017

feedPlanet Lisp

McCLIM: Progress report #8

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:

Bezier Curves

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

Bounties solved this iteration:

Fixed by Gabriel Laddel. Waiting for a pull request and a bounty claim.

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

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

Active bounties:

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

12 Jun 2017 1:00am GMT

11 Jun 2017

feedPlanet Lisp

ABCL Dev: ABCL 1.5.0

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.

Binaries for this release may either be downloaded directly from http://abcl.org/releases/1.5.0, retrieved from the distributed Maven POM graph, or run from Docker via

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.

11 Jun 2017 10:41am GMT

10 Jun 2017

feedPlanet Lisp

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

header
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!

10 Jun 2017 9:10am GMT

09 Jun 2017

feedPlanet Lisp

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

(See also: https://jobs.dou.ua/companies/surftown/vacancies/42175/)

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


09 Jun 2017 1:24pm GMT

07 Jun 2017

feedPlanet Lisp

ABCL Dev: ABCL 1.5.0-rc-0 draft of upcoming User Manual

An unsigned ABCL 1.5.0-rc-0 release now available to test the distributions mechanisms for the upcoming ABCL-1.5.0 release.

http://abcl.org/trac/milestone/1.5.0

http://abcl.org/releases/1.5.0/

Draft of upcoming User Manual to which corrections are solicited.

http://abcl.org/releases/1.5.0/abcl-1.5.0-rc-0.pdf


07 Jun 2017 12:11pm GMT