Back in the saddle

So I have been working on Wall Street for the last year+ and last week decided to quit my job. And non-too-soon, as my job will most likely no longer exist in a few months if you have been following the news over the past few weeks.

I am going back to school, moving out of NYC and off to Maryland so over this summer I should have a lot of free time and I am working on possibly being involved in sort of a freelance project in order to make money (details are still pending). Anyways, the current design of the project has a typical web-app interface, then a manager layer that encapsulates the database. The manager layer handles caching data and moving it back to the database when needed, and event dispatching, blah blah blah.

Immediately I think this is the perfect use case for Erlang. We want it to be fault tolerant of course (the downside of a web-app is when things go wrong it affects everyone) and be able to handle a lot of data moving back and forth (although I'm unsure of the specifics since this is so early). Basically this sounds like a standard Erlang app with mnesia as the cache most likely, spanning a few nodes and moving data back to a DB in a write-behind method.

Some people have a bit of a concern about Erlang, how will we find developers and so on, which are perfectly valid. My response to that is:
Erlang is such a simple language it does not take much time to learn, and while OTP is not as simple, it does not take much time to learn either. In the end, one needs to be less of an expert in Erlang to get an equal or better application (in terms of Erlang's strengths) than they would have to be in another language such as Java.

One possible alternative language being considered is Java because of JBoss. I haven't looked into JBoss in-depth yet, but at a quick glance it looks like it has some really nice and really mature features. The JMS implementation sounds pretty solid and the clustering. Everyone knows Java, or at least puts it on their CV, but this sounds misleading. How good does one need to be in Java in order to not make a mess of an application written using JBoss compared to Erlang? My opinion is that the way one learns Erlang is fairly similar to how they would write production software with Erlang, but perhaps not the same for Java. The features we use in our 'Hello World' are the same that we use in a production environment, this is not true of Java in my experience.

We are still looking into things but I'm currently hoping for Erlang.

Erlang Job Advert

Well, it's been over a year, sorry. Today I received an email with an Erlang job offer for a company based in Boston. I don't know anything about the company at all, perhaps it is junk, but the project seems like something Erlang is good at. It's a telecommuting job, so that might raise a red flag with some people. If you are interested I'll put you in touch with the recruiter or whatever he is, email me at orbitz AT ortdotlove.net (that is really ortdotlove.net, not fancy spelling for ort.love.net).

Here are the job details:

Job Description:

Our client, who is based in Boston, is seeking an adept Erlang developer to help build a next generation metrics and monitoring system on the GNU/Linux platform. This system will watch and report on hundreds and thousands of systems, ranging from network devices to servers to software applications.



Required Skills:

· Must have experience with the Erlang programming language

· Must have expert level network programming experience, preferably in Erlang, C++ and/or C

· Strong background in developing on GNU/Linux for mission-critical production deployments

· Strong understanding of MySQL 4.1-5.x, including database design patterns

· Strong experience programming network servers/clients, including knowledge of fundamental protocols such as TCP, UDP, IPV4/6, and SSL/TLS

Cryptogram solver

Newspaper puzzles beware. I have been working on soving newspaper cryptograms for the past few days in my free time. It is a bit more interesting of a problem to solve than sudoku I think. The algorithm I've implementing is nothing alltogether impressive and it relies on a good dictionary file to get solutions.

The algorithm works like so:
First you need an index which is a map of abstract words to lists of words.
An abstract word is taking a word and turning it into a pattern, for instance, 'cat' has the pattern '123', as does 'hat', and 'fat'. 'mom' has the pattern '121'.

Then it takes the sentence you have given it, splits it on spaces.
Popping the first word off the list, finds the list in the index of possible words it could be, iterates over it generating a map of letters to letters and recurses on the rest of the sentence, once it has reached the end of the sentence it puts the map it has generated into a list of possible solutions. If a generated map for a word conflicts with teh current map it is not a valid solution and moves onto the next possible solution.
The solve function returns a list of solution maps that can eb applied to any sentence to get the result.

Little things that make it helpful include being able to give an intial map, if you are sure some letters map to other letters you can give that as a hint. It can also remove any words whos pattern does not appear in the map.

Todo:
Solve only those subsets of words that, if solved, will result in the entire alphabet being solved. It should do this for all possible combinations of words in teh sentence that will result in this. This is not an optimizations, it should probably make it take longer to solve actually, however it allows it to solve sentences with words that might not exist in the dictionary but could come about as a result of solving the other words. I have a few ideas of how to do this but havn't had time to implement it yet.

The current code can be downloaded here.

Sudoku

I've got sudoku fever! Actually, no, I don't, I don't really like sudoku at all but I decided to write a solver in erlang. It was pretty trivial. The basic algorithm is as follows:
1) Create a list of every blank square and the possible values that can go into that square
2) Find the square with the least number of possible values
3) Iterate over the list of possible numbers that can be in that square, create a new board with that value in it and recurse on the new board
4) Continue until there are no more possible values (in which case it failed) or the puzzle is solved.

The code is not the prettiest stuff in the world but it appears to solve the problem (specifically the remove_* functions).

Usage looks like:

Eshell V5.5.1  (abort with ^G)
1> {solved, Res} = sudoku:solve([
1> [9, 5, b, b, b, 6, 4, 7, b],
1> [4, b, 8, 7, b, 2, b, b, b],
1> [6, 2, b, 4, b, b, b, 5, b],
1> [5, b, 2, b, 6, b, 3, b, b],
1> [b, b, b, 2, b, 7, b, b, b],
1> [b, b, 4, b, 1, b, 2, b, 8],
1> [b, 7, b, b, b, 9, b, 3, 4],
1> [b, b, b, 1, b, 3, 7, b, 5],
1> [b, 4, 3, 5, b, b, b, 2, 9]]).
...
2> sudoku:print(Res).
9 5 1 8 3 6 4 7 2 
4 3 8 7 5 2 9 6 1 
6 2 7 4 9 1 8 5 3 
5 8 2 9 6 4 3 1 7 
3 1 9 2 8 7 5 4 6 
7 6 4 3 1 5 2 9 8 
8 7 5 6 2 9 1 3 4 
2 9 6 1 4 3 7 8 5 
1 4 3 5 7 8 6 2 9 
ok

Code (can be downloaded here):

-module(sudoku).

-export([solve/1, print/1]).

solve(Puzzle) when is_list(Puzzle) ->
    solve_puzzle(dict_from_list(Puzzle)).

print(Puzzle) ->
    lists:foreach(fun(X) ->
                          lists:foreach(fun(Y) ->
                                                io:format("~w ", [dict:fetch({X, Y}, Puzzle)])
                                        end, lists:seq(0, 8)),
                          io:format("~n", [])
                  end, lists:seq(0, 8)).
                          
dict_from_list(List) ->
    element(2, lists:foldl(fun(Elm, {X, Dict}) ->
                                   {_, DDict} = lists:foldl(fun(Elem, {Y, NDict}) ->
                                                                    {Y + 1, dict:store({X, Y}, Elem, NDict)}
                                                            end, {0, Dict}, Elm),
                                   {X + 1, DDict}
                           end, {0, dict:new()}, List)).

solve_puzzle(Puzzle) ->
    case generate_open_spots(Puzzle) of
        [{{X, Y}, Set} | _] ->
            try_value({X, Y}, Set, Puzzle);
        [] ->
            {solved, Puzzle}
    end.

try_value(_, [], Puzzle) ->
    print(Puzzle),
    io:format("~n", []),
    failed;
try_value({X, Y}, [H | R], Puzzle) ->
    case solve_puzzle(dict:store({X, Y}, H, Puzzle)) of
        {solved, RPuzzle} ->
            {solved, RPuzzle};
        failed ->
            try_value({X, Y}, R, Puzzle)
    end.
                      
generate_open_spots(Puzzle) ->
    OpenSquareList = dict:fold(fun(Key, b, Acc) ->
                                       [Key | Acc];
                                  (_Key, _Value, Acc) ->
                                       Acc
                               end, [], Puzzle),
    lists:sort(fun({{_X1, _Y1}, E1}, {{_X2, _Y2}, E2}) when length(E1) < length(E2) ->
                       true;
                  (_E1, _E2) ->
                       false
               end, generate_open_values(OpenSquareList, Puzzle)).

generate_open_values(List, Puzzle) ->
    generate_open_values(List, [], Puzzle).

generate_open_values([], Acc, _Puzzle) ->
    Acc;
generate_open_values([{X, Y} | R], Acc, Puzzle) ->
    generate_open_values(R, [{{X, Y}, remove_region_vals({X, Y},
                                                         remove_x_vals(Y,
                                                                       remove_y_vals(X, lists:seq(1, 9),
                                                                                     Puzzle),
                                                                       Puzzle),
                                                         Puzzle)} | Acc],
                         Puzzle).

remove_x_vals(Y, List, Puzzle) ->
    lists:foldl(fun(Idx, Acc) ->
                        case dict:fetch({Idx, Y}, Puzzle) of
                            b ->
                                Acc;
                            E ->
                                lists:delete(E, Acc)
                        end
                        end,
                        List, lists:seq(0, 8)).

remove_y_vals(X, List, Puzzle) ->
    lists:foldl(fun(Idx, Acc) ->
                        case dict:fetch({X, Idx}, Puzzle) of
                            b ->
                                Acc;
                            E ->
                                lists:delete(E, Acc)
                        end
                        end,
                        List, lists:seq(0, 8)).

remove_region_vals({X, Y}, List, Puzzle) ->
    {RX, RY} = find_region(X, Y),
    lists:foldl(fun(IX, AccX) ->
                        lists:foldl(fun(IY, AccY) ->
                                            case dict:fetch({IX, IY}, Puzzle) of
                                                b ->
                                                    AccY;
                                                E ->
                                                    lists:delete(E, AccY)
                                            end
                                    end, AccX, lists:seq(RY, RY + 2))
                        end, List, lists:seq(RX, RX + 2)).

find_region(X, Y) ->
    {find_region(X), find_region(Y)}.

find_region(V) when V >= 0, V < 3 ->
    0;
find_region(V) when V >= 3, V < 6 ->
    3;
find_region(V) when V >= 6, V < 9 ->
    6.

Lack of activity

I have been busy looking for a job so I have had not had much time to do anything Erlang related. This, unfortunately, means I have not had much time to blog. I am hoping this will change by Sept. If anyone has any job offers and wants a resume, I am currently looking in the New York Ciy area for Financial Programming work or Bioinformatics work. Send an email to orbitz AT ortdotlove.net (that is really ortdotlove.net, not fancy spelling for ort.love.net). I'll gladly mail you back my resume.

I'm looking forward to getting back to programming for fun soon.

Shell

The other day, araujo suggested Erlang might make a good shell. Shell as in, bash. Hrm, I thought, maybe...
I don't think Erlang would be flexible enough to make a decent shell. Take something like this:

for i in *; do echo $i; done

What would the Erlang equivalent look like?

lists:map(fun(X) -> print([X]) end, ls())

I just don't see it? I should hope it doesn't look like that but I don't know. On the other hand, I seem to have it pretty set in my mind that Common Lisp would make an excellent shell language. A few people have told me that CL would probably be too verbose and not work out well but, I don't know, it just seems so succinct and powerful. You could make a lot of macros to make your life easier. I sent an email to the Lisp At Light Speed blog dude to get his opinion but I figured I'd post it here too to see if anyone has any thoughts.

What I have in mind is basically an interactive shell, using Common
Lisp as its programming language.  For instance something like:
 
for i in *; do echo $i; done
 
Might look like:
 
(loop for i in (ls) do (print i))
 
The second thing I would love to see is Monad/Powershell.  Rather
than using text to pass data around, uses lists/objects/etc.  (ls)
for instance gives a list of file objects to iterate over, and you
can extract things like the size and permissions and what not.
 
This raises a question though. In order to do this, just about every
standard program becomes obsolete. For instance, why use 'cut' when
you can simply split a string with a CL function.  However some
things would still be very useful, such as ls, or grep, but these
now need to communicate via objects rather than just text, so those
will have ot be rewritten.  In which cause it seems like they could
simply be packages and loaded into the shell, meaning you don't
have to deal with program startup times or what not.  Is this a lot
of work to rewrite all of these programs, and does it mean that we
cannot usefully use third party programs that people write?  You
can always drop down to using strings as communication I suppose.
 
That is the basic idea.  So far a few people have suggested that
sexprs really aren't any better for this sort of thing.  sexpr's
won't be any better than say...bash.  Someone suggested that Factor
might be a better language for this.  But it seems to me, with
Common Lisps powerful macro system, you can easily make most
operations incredibly simple?  The most useful aspect would be using
objects to communicate.  But even if this is a lot of work to
accomplish, it seems to me that simply using CL as a shell programming
language seems like it would be nice. Am I wrong here? Am I missing
something?

If CL would make a poor langauge, what would make a good language? Riastrach has suggested Factor. I don't know enough about factor to say that but I think I like CL better for this.

All I know is:

This is not the answer

Pastebin design - Mnesia tables

I have started to design the tables for this. The main goal is simple: make it easily extendable. That is to say I want to make it so I can easily develope it incrementally and add things to it that I didn't think of before. But that should be obvious to any developer. Given the spec of my previous post, here is the beginning of the database.

Table:
paste - This is the table that will hold the actual pastes.
pid | text | annotation | language | date

pid - unique id to identify a paste
text - the actual text
annotation - any annotation the paster wants to include
language - Plaintext/C++/Erlang, etc
date - when they pasted it


highlight - cache of pastes that have been put through the source highlighter
pid | text | last_viewed

pid - the same as paste.pid
text - result of being put through the highlighter
last_viewed - to keep track of when the entry should be removed

threads - paste threads
tid | [pid]

tid - the unique id for a thread
[pid] - list of pid's


I decided to have the thread table just contain an id and list so you don't have to do a bunch of queries to get every paste in a thread. This way a paste can be part of multiple threads (Although I don't see when this will ever happen). The paste table contains, I think, the minimalist amount of data in order to be useful. Using a highlight table means we can store, if we want, every single paste with a highlighted copy of the text, or just a few and use it as a cache style system. Later on we can also add the ability to associate a paste with an irc channel or a user if we wish to track that sort of information.

I'm not sure how to generate unique id's in mnesia. In a SQL database I would use a serial data type but I am unsure if mnesia supports this functionality. If not I suppose I could use newref maybe? I need to be able to convert it to a string to make url's, and also be valid between restarts.

As I think about it, I guess serials are just implemented as a table and store the integer in there, I can implement that in mnesia I suppose. It just needs to have some sort of get_and_increment functionality so two proceses don't get the same idea. If anyone has any ideas on how to implement this let me know. Bear in mind I have not looked at the mnesia documentation yet and am just brainstorming, so it is quite possible the solution is incredibly simple.

Next step - determine what pages pages will be needed.