Lisplog

Blogging in Lisp

Search

Feed Aggregator

Rendered on Mon, 24 Jul 2017 04:02:18 GMT  newer latest older 
Next udpate: Mon, 24 Jul 2017 04:30:00 GMT feeds

Ember Best Practices: Reducing CRUD complexity with components

via DockYard blog by Nico Mihalich on Tue, 18 Jul 2017 00:00:00 GMT

Reduce your Ember CRUD code with form components

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

via Planet Lisp by on Sat, 15 Jul 2017 01:00:00 GMT

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

 

 

 

From Java to Kotlin:

via The Oozou Blog - Medium by Boonya Kitpitak on Fri, 14 Jul 2017 09:12:38 GMT

Make things easier with “let” and “apply” (Android)

“let” and “apply” are very useful functions in Kotlin. It could change the way you write your code from what you did in Java. In this article, I would like to share how to make your code easier with “let” and “apply”. I will assume that your have some basic knowledge about Kotlin.

What can “let” do ?

I would like to point out two main usages of “let”

  1. Scoping Function: “let” could be used to make your code self-contain in “let” block and keep the logic separate. The variable in front of “let” could be referred to as it. Look at the code below as an example.

As you can see that the File(“dummy.txt”) will only be visible in the “let” block

2. Check against null: In Java, to prevent our lovely NullPointerException we have to repeatedly check for null in our code. Fortunately, we could make things easier with “let”. We can make the “let” block execute only when variable is not null. Let’s see an example.

Suppose we have object like this

user -(hold)-> info -(hold)-> email

Both user and info could be null. This is how we would do this in Java.

And in Kotlin :)

As you can see that it’s much shorter and cleaner in Kotlin

How to use “apply” ?

“apply” may help you write the code in slightly different way

“apply” can be used as extension on all type of variables. It will return the object with the thing in “apply” block apply to the object (it works according to its name). Let’s see things in action to get clearer picture.

Here are a couple of examples:

  1. In Java, when we try to set up RecyclerView. We might do something like this.

With “apply” in Kotlin, we could make it this way.

2. Creating object through setter in Java might require something like

With “apply” we could make things slightly better

Inside “apply” block we can refer to “properties” or “methods” of the variable that used “apply” with out having to refer to that variable again.

Conclusion

In my opinion “let” does make the code shorter and cleaner, especially the ability to check against null. Since as an Android developer we all might have to write many lines of code to check for null values in Java to prevent NullPointerException and “let” does solve that pain. For “apply”, I think it helps avoiding repeatedly referencing to the same variable and makes the code a bit easier to read.

Thank you for reading. This is my very first article. Therefore, if there are any mistakes or the things I can improve about my article please leave comments. :)

Reference

Otaku, Cedric's blog


From Java to Kotlin: was originally published in The Oozou Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Safari, iOS, and Progressive Web Apps: What You Should Know

via DockYard blog by Jessica Krywosa on Thu, 13 Jul 2017 00:00:00 GMT

Interested in a Progressive Web App but unsure about implementing one without Safari/iOS support? Here’s what you should know before making a decision.

Code Refactoring with Parameterization

via The Oozou Blog - Medium by Tino Thamjarat on Mon, 10 Jul 2017 09:01:01 GMT

Photo from Unsplash by Glenn Carstens-Peters

There are multiple occasion that I came across an ‘almost similar’ chunk of codes all over the code base. The problem with this kind of code smell is, once you want to change just a tiny bit of that particular function, you need to find all the implementation you did and change all of them which is not a good idea.

Duplicate code is a major cause of unmaintainable scripts.
— Brian Marick @ Everyday Scripting with Ruby

The technique that I often use and find it’s super easy to do is parameterization. Today I’ll explain how that works by a nice little example.

Finding weight average

There are reports that I need to find a weight average of a gross profit field and they are going to be weighted by sale revenue. Here is what I came up with. (in Ruby)

Simple stuff right? Now we need another method that does this exact same thing but for another field called cogs. The easiest thing here is to just duplicate the method and change what’s need to be changed.

Make it work, then make it right ❤

We got what we want right? Cool but what if we need weight average of other stuff? What if we need to change the weight from sale_revenue to something else? Creating new method that shares this logic would lead us to the problem I was talking about earlier., the duplication problem.

Parameterization in action

Now what do we see, these two methods is almost identical right? The only different is the block I passed into the map function.

The differences are highlighted in blue.

Extract the similar codes out and put them in the new method. I’ll call it weighted_avg then parameterized the differences.

Keep the grey part and parameterized the blue part.
Notes: Ruby can dynamically calls a function by passing string or symbol to the method send

I’ve remove the duplicate method now and our program look like this.

Now the logic of these two methods are in the same place. I can easily extend it to compute a weight_avg of any value from the report with a one-lined function.

Going further

Parameterization is a nice little trick but it is not a silver bullet. Sometimes it is wiser to have small amount of duplications than one over abstracted method than cannot be extended or modify. As Sandi Metz stated in RailsConference 2014

Duplication is far cheaper than the wrong abstraction.

Final Note

I believe we should focus not only on making things work but also on creating a clean code base that can be easily maintained by any developer carry on the project.

If you have any questions or suggestions, feel free to comment them down below and please hit that little green heart to give me a pat on my back.

Shy me.

Thank you for reading

My name is Tino Thamjarat. Technical Lead at BASE and Software Engineer at Oozou . I love discussing everything. Business ideas, philosophy, physics, religion, tech, gaming, you name it. I also play League of Legend and a little bit of music once in a while. If you need a website, want to give some advice/comments or just need some guy to talk to, feel free to contact me on my Twitter or Instagram.


Code Refactoring with Parameterization was originally published in The Oozou Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Quicklisp news: June 2017 Quicklisp dist update now available

via Planet Lisp by on Sat, 01 Jul 2017 18:54:00 GMT

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
  • cl-threadpool — Implementation of a thread pool — 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
Updated projects3d-matrices3d-vectorsarchitecture.builder-protocolarchitecture.service-providerayah-captchacavemancaveman2-widgets-bootstrapceplcepl.cameracepl.devilcepl.sdl2cepl.sdl2-imagecepl.sdl2-ttfcepl.skittercfficl+sslcl-anacl-ansi-termcl-bloomcl-dbicl-emojicl-fondcl-gamepadcl-gistscl-glfw3cl-graphcl-hamlcl-hash-utilcl-jpegcl-monitorscl-mssqlcl-ntp-clientcl-ohmcl-openglcl-out123cl-plplotcl-readlinecl-scsucl-soilcl-strcl-twitterclackclim-widgetscloser-mopclsql-fluidclssclxcroatoancurry-compose-reader-macrosdeedsdendritedirtdocumentation-utilsdoubly-linked-listdrakmaeasingeruditeesrapf2clfare-scriptsfast-httpfast-iofemlispfs-utilsfxmlgamebox-dgengamebox-ecsgamebox-frame-managergamebox-gridsgamebox-mathgettextglawglkitglopglsl-specglsl-toolkithornerhttp-get-cachehu.dwim.asdfhu.dwim.utilhu.dwim.web-serverinquisitoriolibjsonrpcjwacsl-systemlichat-protocollivesupportlog4clmacrodynamicsmaidenmcclimmedia-typesmetatilitiesmitomk-string-metricsopticlparachutepng-readprbsqlotqmyndqtoolsrtg-mathrutilsscalplscriptlsdl2kitserapeumsimple-loggersketchskittersmackjackspinneretstaplestructy-defclassstumpwmthe-cost-of-nothingtmtranslate-clienttrivial-main-threadtrivial-mmaptrivial-shelltrivial-updateuffiumlispunix-optsvarjoweblockswebsocket-driverwhofieldswith-cached-reader-conditionalswooyaclml.

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

Accelerated Mobile Pages (AMP): What are you willing to sacrifice for speed?

via DockYard blog by Jessica Krywosa on Thu, 22 Jun 2017 00:00:00 GMT

A simple, Google backed, solution to slow loading mobile content is very enticing. But what will you have to give up to make this happen?

Erlang/OTP 20.0 is released

via Erlang.org News RSS by on Wed, 21 Jun 2017 00:00:00 GMT

img src=http://www.erlang.org/upload/news/

Erlang/OTP 20.0 is a new major release with new features, quite a few (characteristics) improvements, as well as a few incompatibilities.

There are only minor changes compared to the second release candidate, some of them listed below:

  • ERTS:
    • erlang:term_to_binary/1 changed the encoding of all atoms from ATOM_EXT to ATOM_UTF8_EXT and SMALL_ATOM_UTF8_EXT. This is now changed so that only atoms actually containing unicode characters are encoded with the UTF8 tags while other atoms are encoded ATOM_EXT just as before.

Here are some of the most important news in OTP 20:

Potential Incompatibilities

  • ERTS:

    • The non SMP Erlang VM is deprecated and not built by default
    • Remove deprecated erlang:hash/2
    • erlang:statistics/1 with scheduler_wall_time now also includes info about dirty CPU schedulers.
    • The new purge strategy introduced in OTP 19.1 is mandatory and slightly incompatible for processes holding funs
      see erlang:check_process_code/3.
    • The NIF library reload is not supported anymore.
    • Atoms can now contain arbitrary unicode characters which means that the DFLAG_UTF8_ATOMS capability in the distribution protocol must be supported if an OTP 20 node should accept the connection with another node or library. Third party libraries which uses the distribution protocol need to be updated with this.
  • Asn1: Deprecated module and functions removed (asn1rt, asn1ct:encode/3 and decode/3)

  • Ssh: client only option in a call to start a daemon will now fail

Highlights

Erts:

  • Dirty schedulers enabled and supported on VM with SMP support.
  • support for “dirty” BIFs and “dirty” GC.
  • erlang:garbage_collect/2 for control of minor or major GC
  • Erlang literals are no longer copied when sending messages.
  • Improved performance for large ETS tables, >256 entries (except ordered_set)
  • erlang:system_info/1 atom_count and atom_limit
  • Reduced memory pressure by converting sub-binaries to heap-binaries during GC
  • enif_select, map an external event to message
  • Improvements of timers internally in the VM resulting in reduced memory consumption and more efficient administration for timers

Compiler:

  • Code generation for complicated guards is improved.
  • Warnings for repeated identical map keys. #{'a'=>1, 'b'=>2, 'a'=>3} will warn for the repeated key a.
  • By default there is now a warning when export_all is used. Can be disabled
  • Pattern matching for maps is optimized
  • New option deterministic to omit path to source + options info the BEAM file.
  • Atoms may now contain arbitrary unicode characters.
  • compile:file/2 has an option to include extra chunks in the BEAM file.

Misc other applications

  • Significantly updated string module with unicode support and many new functions
  • crypto now supports OpenSSL 1.1
  • Unnamed ets tables optimized
  • gen_fsm is deprecated and replaced by gen_statem
  • A new event manager to handle a subset of OS signals in Erlang
  • Optimized sets add_element, del_element and union
  • Added rand:jump/0-1
  • When a gen_server crashes, the stacktrace for the client will be printed to facilitate debugging.
  • take/2 has been added to dict, orddict, and gb_trees.
  • take_any/2 has been added to gb_trees
  • erl_tar support for long path names and new file formats
  • asn1: the new maps option changes the representation of SEQUENCE to be maps instead of records
  • A TLS client will by default call public_key:pkix_verify_hostname/2 to verify the hostname
  • ssl: DTLS documented in the API, experimental
  • ssh: improving security, removing and adding algorithms
  • New math:fmod/2

For more details see
http://erlang.org/download/otp_src_20.0.readme

The Erlang/OTP source can also be found at GitHub on the official Erlang repository,
https://github.com/erlang/otp with tag OTP-20.0

Pre built versions for Windows can be fetched here:
http://erlang.org/download/otp_win32_20.0.exe
http://erlang.org/download/otp_win64_20.0.exe

On line documentation can be browsed here:
www.erlang.org/doc/

Thanks to all contributors.

Who’s responsible for what happens after design?

via DockYard blog by Maria Matveeva on Tue, 20 Jun 2017 00:00:00 GMT

As a designer, I am responsible for the ethics of the products I help build. But ethics aren’t always convenient to discuss.

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

via Planet Lisp by on Sat, 17 Jun 2017 19:24:00 GMT

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.

Can you see your invisible problems?

via DockYard blog by Maria Matveeva on Tue, 13 Jun 2017 00:00:00 GMT

A UX audit can reveal big problems and simple fixes much faster than an insider ever could. Here it is, explained with paper towels.

McCLIM: Progress report #8

via Planet Lisp by on Mon, 12 Jun 2017 01:00:00 GMT

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).

Bezier Curves

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

 newer latest older