Comment by jpcooper | Hacker News Reader

Comment by jpcooper | Hacker News Reader

Parent Full thread

Thanks for the explanation.

This makes sense. In Haskell, strict ByteStrings are a pointer, plus an offset, plus a length. You can call the unpack function on them, which provides a lazy list (it reads from the pointer in blocks) of the characters pointed to. There is also a library that provides lazy ByteStrings from mmapped files.

The Prolog stuff sounds quite interesting. I suppose you haven't published anything about the cross-border stuff? Quite a while ago I was using linear programming to build a home energy optimisation system, modelling the workings of a battery, solar panel, energy usage and energy tariffs. The whole thing was a big min-cost flow network. The output was a series of commands to hopefully optimise energy usage.

I defined the programme with glpk-hs (a Haskell library which can output in the CPLEX format) and then ran the programmes with cbc. It was very complex, and I later realised that what I really needed was a more general system which combined linear and logic.

Someone on HN mentioned ECLiPSe, but I see that you mention SWI quite a bit on your website. What can you recommend for the sort of thing I was doing? I am not an expert in linear programming, and I also found all the options of CBC a bit overwhelming.

The key attraction of the representation I mentioned is that on the level of Prolog programs, the compactly represented lists appear like any other lists, no matter how they are internally represented. So, internally, it is a sequence of raw bytes, and to Prolog programmers, it appears as a Prolog list of characters.

In Haskell, as long as we are forced to use ByteString or similar data types to get this efficient representation, the situation is not as convenient: ByteString is not the same type as String, and we have to convert manually between them, i.e., within Haskell programs. So, this causes overhead for programmers: We have to learn a new type with new interfaces, call an unpack function etc. A conceptually simpler solution would be to reduce the number of different types in Haskell programs, and instead implement String (i.e., [Char]) more efficiently internally so that it can be directly used instead.

For comparison, in Trealla Prolog, when we write the string "hello", then it is automatically internally represented in the efficient way as raw bytes. And on the Prolog level, it appears as a list of characters, corresponding to a String in Haskell:

    ?- "hello" = [h,e,l,l,o].
    true.

To read from files, there is a single predicate phrase_from_file/2 that internally performs the mmap call. On the Prolog level, we again only see a list of characters, and we can use DCGs as usual to process them.

So, the key attraction is that this efficient representation is transparent to the programmer in the sense that lists that are represented in this way are semantically completely indistinguishable from lists that are represented in the naive way internally. To Prolog programs, they have the exact same type, shape, length etc., they are only represented differently internally in the virtual machine. This idea can be used in Erlang and Haskell too to represent strings.

Currently, SICStus Prolog is the only Prolog system that can be reliably used for linear programming with constraints and is fast enough, see its library(clpq). I hope that a free Prolog system with a similar feature set will eventually become available. Currently, Scryer Prolog is looking very promising, especially due to the mentioned efficient internal representation of characters and its strong commitment to the Prolog ISO standard. There is ongoing work on a simplex library for Scryer Prolog, please see this issue and the linked file:

https://github.com/mthom/scryer-prolog/issues/463

The library contains functionality for solving transportation and assignment problems via network flow algorithms. This sounds similar to your use case, and I hope it works for you.

I think it is nice in Haskell to retain the ability to control the underlying representation of a string. The laziness allows the native linked list representation without the user having to know about the underlying representation. Your memory mapping function can simply return a lazy linked list of chars in Haskell as well. If the underlying representation turns out to be inefficient on the current system, then that can always be tuned by the user. Maybe in Prolog it is sufficient to leave all of that to the runtime system.

Thanks for the Prolog tips. I had a look at clpqr, and could not find any reference to boolean variables and operators. Maybe clpqr intersects with another system whose docs do refer to boolean variables. I could not see how to combine clpqr with clpb. Basically what I would like is for certain linear constraints to be active only if other chosen boolean expressions are true.

Example: Choose energy price based on maximum power usage over past month. There are some Japanese electricity tariffs which do this. There would be a partition of maximum power usage ranges, and each range is associated with a price. Associate a binary variable to each range. Ensure exactly one of the variables is true (sum = 1). Create a range constraint over the maximum power usage for each partition, and multiply the bounds of that constraint with the associated binary variable. When a binary variable is set to zero, you have a trivial constraint.

It is indeed possible to represent boolean constraints as linear constraints over binary variables and develop a DSL to translate in this direction. I am wondering whether a system exists which allows easy expression of linear and boolean combined, and which provides tools for solving them efficiently.

Reply on news.ycombinator.com