Wednesday, September 29, 2010

Eff: Like Haskell, but simpler than Monads

I may someday learn yet another interesting language, Eff. It is like Python + Ocaml/Haskell in syntax, but it really has nothing to do with Python. Interestingly, it's written in Ocaml. It's not ready for primetime, but could be preferable to Haskell someday, though I do not yet see the value.

The main difference with Haskell is the Effect, rather than the Monad.

Linux Multi-Threaded "Swap Insanity"

Here is a helpful description of a problem that can be encountered on Linux using the NUMA (Non-Uniform Memory Architecture), often seen with MySQL.

In a nutshell, the machine may bog down with memory-swapping when total memory use is far below what is available, because the default policy is for a processor to prefer the memory in its own node even when swapping occurs.

The simplest solution is to use numactl --interleave.

Thursday, September 23, 2010

Eigen: Wrapper for SIMD instructions

From @Rikrd at http://blog.wolfire.com/2010/09/SIMD-optimization:
If you make extensive use of linear algebra (matrices, vectors, etc.) you may consider using Eigen. It is a header only library and it implements quite a few linear algebra operations in a very intuitive API and it uses whatever backend is available (simple loop unrolling, vectorizing with SSE/SSE2/SSE3..., Altivec, etc...). It may save you a lot of vectorization work... and it is just really fun to write stuff using Eigen.

Parsers and grammars

A friend expressed an interest in an improved version of yacc. I think this fits the bill:
    http://en.wikipedia.org/wiki/Lemon_Parser
    http://hwaci.com/sw/lemon/lemon.html

It's always re-entrant and thread-safe, with some other advantages and all the best lessons of
yacc (e.g. error-handling).

Anyway, I'm nearly sold on PEG (Parsing Expression Grammars).
    http://en.wikipedia.org/wiki/Parsing_expression_grammar
    http://piumarta.com/software/peg/peg.1.html

Unlike LR parsers, a PEG parser does not require a separate tokenizer.  It's very elegant, much like BNF.  I want to do some runtime comparisons, but I expect it to be comparable.  I will try to attach a pegleg grammar that I wrote to solve this (with the added constraint of left-associativity):
    https://www.spoj.pl/problems/ONP/
Just install peg/leg, run 'leg' on the attached file (if I ever manage to post it to this blog), and compile.

Here is an interesting table:
    http://en.wikipedia.org/wiki/Comparison_of_parser_generators

To learn a ton about PEG:
    http://pdos.csail.mit.edu/~baford/packrat/

In a nutshell, a Context-Free Grammar parser like
yacc is meant for natural language, based on Chomsky's work, not for an unambiguous computer language.  PEG simplifies the parser by eliminating ambiguity in the grammar.

Functional data-structures (F#, ML, Haskell)

A good way to learn Standard ML (which is very similar to F#) is to read Chris Okasaki's book, Purely Functional Structures, which uses ML for examples in the main text.

Okasaki has many interesting ideas on functional programming. For example, among other interesting articles here, I enjoyed "Alternatives to Two Classic Data Structures".

There is also source code next to the PDF, in both Java and Ada. However, the deletion routine for red-black trees is missing from the source code. I mention that because, as Randall Helzerman points out in an Amazon comment on Okasaki's book,
Although he presents an EXTREMELY lucid description of how to implement Red-Black trees in a functional language, he only presented algorithms for insertion and querying. Of course, deletion from a red-black tree is the hardest part, left here, I suppose, as an exercise to the student. If you want to supply this missing piece yourself, check out a paper by Stefan Kars, "Red-black trees with types", J. Functional Programming 11(4):425-432, July, 2001. It presents deletion routines, but you'll still want to read Okasaki's book first, for unless you're very much smarter than me you won't be able to understand Kars' paper until you read Okasaki's exposition of red black trees.
Unfortunately, I do not have access to that Journal. I'm hoping to get a PDF from a friend.... Here it is. Warning: The code it shows, including for deletion, uses existential types.

Functional data-structures are interesting for many reasons, not the least of which is their value in persistent data storage, such as in a system that was used when I was at AMD. Here is an overview of current knowledge of such data-structures.

Saturday, September 4, 2010

UNIX: stangeness with signals.

Slava Pestov, an author of the language Factor, calls this blogspot post, "2 Things Every Unix Developer Should Know."  I have to admit that I do not fully understand how to handle these problems, so I accept with alacrity his advice to use a high-level language instead of diving into UNIX.

JavaScript: The Good and the Bad

Here are some thoughts on JavaScript.  I agree.  Aside from a few blemishes, JavaScript is a beautiful, powerful language.  It's always a joy to code.