Saturday, June 22, 2013

Elm In Practice

So I've gotten some time in with it. Not quite enough to finalize the new interface, though I do have an unstyled 95% version running on my local with an apropos choice of music. Firstly, here's the code.

The Code

module Mote where

import JavaScript.Experimental (toRecord)
import Json (fromString, toJSObject)
import Graphics.Input (button, buttons, customButtons)
import Window (middle)
import Http (sendGet, send, post)
import Maybe (maybe)

----- Signal Declarations
uriDir str = "/show-directory?dir=" ++ str
reqPlay str = post ("/play?target=" ++ (maybe "" id str)) ""
reqCmd str = post ("/command?command=" ++ (maybe "" id str)) ""

command = buttons Nothing
playing = buttons Nothing
files = buttons "root"

dir = sendGet $ lift uriDir files.events
cmd = send $ lift reqCmd command.events
ply = send $ lift reqPlay playing.events

----- Utility
jstrToRec jStr = let conv = toRecord . toJSObject
                 in maybe [] conv $ fromString jStr

----- Application
box n = container 350 n midTop

cmdButton name = height 42 $ width 80 $ command.button (Just name) name

controls = flow down [ box 48 $ flow right $ map cmdButton ["backward", "stop", "pause", "forward"]
                     , box 50 $ flow right $ map cmdButton ["volume-down", "volume-off", "volume-up"]]
           
entry { name, path, entryType } = let btn = if | entryType == "return" -> files.button path
                                               | entryType == "directory" -> files.button path
                                               | otherwise -> playing.button (Just path)
                                           in width 350 $ btn name

showEntries res = case res of
  Success str -> flow down . map entry $ jstrToRec str
  _ -> plainText "Waiting..."

showMe entries = flow down [ box 100 $ controls
                           , showEntries entries ] 

main = showMe <~ dir

And that's all. Seriously. This replaces all of the ~200 lines of JS/HTML/CSS that comprised the Angular.js edition, and the ~300 lines of its jQuery/Backbone predecessor.

So, if nothing else, Elm is very terse.

module Mote where

import JavaScript.Experimental (toRecord)
import Json (fromString, toJSObject)
import Graphics.Input (button, buttons, customButtons)
import Window (middle)
import Http (sendGet, send, post)
import Maybe (maybe)

That first part is the module declaration and imports, hopefully self-explanatory.

----- Signal Declarations
uriDir str = "/show-directory?dir=" ++ str
reqPlay str = post ("/play?target=" ++ (maybe "" id str)) ""
reqCmd str = post ("/command?command=" ++ (maybe "" id str)) ""

command = buttons Nothing
playing = buttons Nothing
files = buttons "root"

dir = sendGet $ lift uriDir files.events
cmd = send $ lift reqCmd command.events
ply = send $ lift reqPlay playing.events

This declares the main signals of the interaction, and some uri/request helper functions they'll need. command is the group of buttons that issues playback commands, playing is the group of buttons sending play instructions specifically, and files is the group of buttons sending show-directory commands. These were all handled by the same callback mechanism in earlier versions of the interface, but it makes sense to separate them if we're dealing with their signal streams. dir, cmd and ply just take event signals from those button groups, make appropriate Ajax requests when necessary, and return signals of responses.

----- Utility
jstrToRec jStr = let conv = toRecord . toJSObject
                 in maybe [] conv $ fromString jStr

That is a short utility function that converts a JSON string to a (potentially empty) list of records. The empty list situation happens in two cases

  • if the server sends back an empty list
  • if the server sends back a malformed JSON string
----- Application
box n = container 350 n midTop

cmdButton name = height 42 $ width 80 $ command.button (Just name) name

controls = flow down [ box 48 $ flow right $ map cmdButton ["backward", "stop", "pause", "forward"]
                     , box 50 $ flow right $ map cmdButton ["volume-down", "volume-off", "volume-up"]]
           
entry { name, path, entryType } = let btn = if | entryType == "return" -> files.button path
                                               | entryType == "directory" -> files.button path
                                               | otherwise -> playing.button (Just path)
                                           in width 350 $ btn name

showEntries res = case res of
  Success str -> flow down . map entry $ jstrToRec str
  _ -> plainText "Waiting..."

showMe entries = flow down [ box 100 $ controls
                           , showEntries entries ] 

main = showMe <~ dir

This is the meat of the front-end. box is just a positioning helper function. cmdButton is a helper function to define a playback command element. Note that these are missing a piece of functionality from the old interface: clicking and holding the rewind/forward/volume-up/volume-down buttons doesn't do anything. It used to make serial requests to the server for the appropriate command, but Elm doesn't have very good support for HTML events. I'll talk more about that in a bit.

controls defines the two-row, centered placement of those command elements. entry defines a button for the main show/play buttons which comprise the principal interaction with Web Mote. These are missing the play/shuffle sub-buttons for directories and they subtle styling, but that's just because I didn't do it yet. There's no obviously missing feature that would prevent me from implementing all of it; I'd just need to define the appropriate customButton and slot it in. I'd call it five lines at the outside. Thing is, I want to get to writing this article first, so it'll probably happen in an addendum.

Now that we've got that out of the way, here's what I think.

What I Think

To summarize, very good, but obviously not finished yet. Which makes sense, since it's only at 0.8. I'm going to go through the headaches first, then note the things I particularly like about working with it.

Headaches

Signal Hell

Or, alternately, "Type Hell". I'm putting this one front-and-center, because Elm's author is fiercely anti-callback, but seems to be just fine with introducing a similar situation with the type system.

The argument against callbacks goes like this in a nutshell: if you write one, you're separating pieces of a procedure that should really be unified. You want to express "do this stuff", but part of it has to happen after an asynchronous request, so you have to break your procedure up into pre-async and post-async stuff, then have the request call the function that completes post-async stuff after the request returns. It gets even worse if you need to do multiple async requests as part of your tasks; you might need to split the work up arbitrarily among a large number of functions, all of which should actually be unified conceptually.

Now, I'm not disagreeing with this argument, but take a look at the bottom of that code from Mote.elm.

showMe entries = flow down [ box 100 $ controls
                           , showEntries entries ] 

main = showMe <~ dir

What I want to express here is "Stack the controls on top of the file entries (figuring out entries based on the signal dir)". But you can't display an Element in the same list as a Signal Element because that would make some type theorist somewhere cry apparently. So instead of doing something like

main = flow down [ box 100 $ controls, showEntries $ id <~ dir]

I have to write a separate callback-like function to accept the sanitized signal value and display that instead.

This is the same situation as callback hell. The only difference is that callbacks separate your code at boundaries determined by asynchronous calls, while these signal display functions do it at boundaries determined by the type system. I guess one of those might be better than the other if you squint hard enough, but I'm not seeing it from here.

Very Few Event Options

A button or customButton send signals when they're clicked. input of type="text", passwords, checkboxes, and dropDowns send signals when their value changes. textarea and radio buttons don't exist. And that's all.

What do you do if you want a given form to submit when you hit Ret in a relevant input? What do you do if you want to define a button that can be held down (requiring a mouse-down event)? How do you implement draggables, or droppables, or datepickers, or any of the interactive pieces that jQuery has trivially provided since something like 2006? You either do it with global signals, or you make liberal use of the JavaScript FFI. Which isn't exactly fun. Since Elm is trying to do all of styling/content/behavior specification, I understand that you need to have elements like image that don't actually have behaviors. That is, they're of type Element rather than of type (Element, Signal a). But the ones that do send signals should have a menu of signals to provide. I mean, you already have this cool record syntax, what you could do is provide an interface for the user where,

button : String -> SignalOptions -> (Element, Signal a)

and SignalOptions is something like { click : a, mouseEnter: a, mouseLeave: a, mouseDown: a, mouseUp: a, keyDown: a }. Granted, maybe that shouldn't be a button, but rather a different multi-signal element, but it would give quite a bit more flexibility to front-end developers. If you had an element like that, you could easily implement any of the interactions I mention above.

No Encoding/Decoding Out-of-the-box

I'll probably implement something here when I get around to poking at the language again, but there's no built-in way to call encodeURI or encodeURIComponent from Elm. Which means that as written, this front-end will fail to play files with & in their name. That's less than ideal. I get the feeling it wouldn't be too hard to implement using the JS FFI, but I'm not diving into that right now.

Gimped Case

The Elm case statement doesn't pattern-match on strings. There's no mention of that behavior in the docs, so I'm not sure whether this is a bug or an unimplemented feature or what, but I missed it once in a ~50 line program. Specifically, in entries

entry { name, path, entryType } = let btn = if | entryType == "return" -> files.button path
                                               | entryType == "directory" -> files.button path
                                               | otherwise -> playing.button (Just path)
                                           in width 350 $ btn name

where I had to resort to using the new, otherwise unnecessary multi-branch if. Unfortunately ...

Gimped if Indentation

Because there's no elm-mode yet, you're stuck using haskell-mode for editing .elms. haskell-mode craps out on indentation of that multi-branch if statement I just mentioned. If you try to indent the following line, it'll yell at you about parse errors rather than inserting the appropriate amount of white-space, which makes working with an already unnecessary-feeling operator just that little bit more annoying. This is similar to that [markdown| |] tag indentation issue I mentioned last time, it's just that the Web Mote front-end port didn't happen to need any markdown.

Gratuitous Differences

Type annotation (::) and cons (:) from Haskell have been switched for no obvious reason, and if seems to have a similar treatment. Unlike most of the other things I bumped into, this and the case "bug" have no hope in hell of being solved by a mere user of the language, so hopefully the designer does something about them.

Nitpicks

These aren't big things, and they're not really related to the language itself, but I noticed them and they were annoying.

No Single-File Option

This is just a nice to have. It would have made this front-end marginally easier to deploy, but I'm not sure how it would work if you needed more than one file served for your program. Elm targets JavaScript as a platform, which means that the base language is deployed as a js file that you have to host manually if you're not using the elm-server. When you compile an Elm project, you have an option that looks like this

  -r --runtime=FILE           Specify a custom location for Elm's runtime
                              system.

It's slightly misleading, because what it actually does is specify where to load elm-runtime.js from in the compiled file. Literally, it determines the src property of the appropriate script tag. For that Mote front-end, I had to elm --make -r "/static/js/elm-runtime.js" --minify Mote.elm, and then make sure to serve elm-runtime.js from that static url (by default, you can find this file in ~/.cabal/share/Elm-0.8.0.3/elm-runtime.js, in case you were wondering).

Anyhow, it would be nice if there was a compiler option you could activate to just have this runtime inlined in your compiled result, rather than served separately.

Unstable Website

elm-lang.org is down pretty frequently. It seems to be up at the moment, but I'm not sure how long that's going to be the case. It happens often enough that I just went ahead and did a checkout from its github. Then I found out that the "Documentation" pages happen to be missing from that repo...

Highlights

Anything I didn't mention above is good, which is to say "most of it", but there are two things I like about the language enough to call out.

Records

This is brilliant. Take a bow, you've nailed record interaction. The approach probably wouldn't fit trivially into GHC, but it would solve some of the problems their records have. It's also something the Erlang devs should probably keep an eye on, because it's much much better than what I remember having access to in Erl-land. Probably the biggest win is that Elm records get first-class treatment in terms of the languages' pattern matching facilities, which lets you do things like

entry { name, path, entryType } = let btn = if | entryType == "return" -> files.button path
...

That's something I miss in almost every single language that has both pattern matching and k/v constructs. As usual, Common Lisp has a 95% solution as part of the Optima pattern matching library.

This dynamic record syntax also lets you trivially handle JSON input from a server. In case you didn't notice, the stuff I was passing into entry originates in ajax responses from the server.

Haskell-grade Terseness

Just a reminder. Despite all those flaws I pointed out above, the Elm version of this particular program weighs in at about 1/4 the code of the reactive Angular.js version, let alone the traditional plain DOM/jQuery approach. It's also more pleasant to work with than JS, but that's an entirely subjective point. Improvements can still be made here; implementing haskell-style sections and multi-line definitions would save a bit of typing, though, to be fair, not as much as I thought it would.

Conclusions

I've already mentioned that I'm going to take a swing at putting together some SSE support, encodeURI(component)? calls and a more appropriate Emacs mode for Elm, but it probably won't be very soon. Thanks to a tip-off from Dann, I managed to squeak into the registration for the Lisp In Summer Projects event, which looks very much like a multi-month NaNoWriMo with parentheses instead of character development and sleep.

I'm going to make a serious attempt at getting a little pet project of mine up-and-running in either Common Lisp or Clojure by September 30, which means I'll have very little time to hack on someone else's up-and-coming language regardless of how interesting it looks.

Tuesday, June 18, 2013

Dragging in an FRP Context

I made an off-the-cuff remark earlier to the effect that Elm doesn't let you easily define drag/drop functionality, or element-originating clicks. Really, the situation is that you can't easily work with any of the basic HTML events, which also include hovering, element-originating keypresses, various window events, and various form events. When you think about how you'd implement any of them individually, it starts to become obvious why that is.

The first reflex is to reach for callbacks. Which, as was already discussed, is the exact opposite of what Elm is trying to do. The real trouble begins when you consider how you'd do the same thing without callbacks in order to preserve that purity of purpose.

First Pass

The obvious solution is to use a bunch of signals everywhere. One for each of the element-based events. Let the user specify signal values on elements, and dispatch on their results at the other end.

Except thats quite complex.

At first glance, you're looking at twenty or so global signals, each of which are going to have the kind of isolated, complicated dispatch we saw in that Tic Tac Toe example. That sounds worse in every way than callback hell; all your dispatch needs to be centralized, which means that behavior under various circumstances will by definition be separated from the element it pertains to, and you suddenly can't understand any component of your program without understanding the central signal dispatch code.

Second Pass

Another approach might be not to let the user specify signal values. Make them hooks to the relevant element. Expose some kind of interface to the user so that they can pipe other signal values into various properties of that element, and call it a day.

Also, we don't really need to have a signal per HTML event. For the situations I'm currently thinking about, we could get away with exactly two. Keyboard.focus and Mouse.focus will give me most of what I'd want in a pretty simple way. Basically, have mouseover, mouseout, mousedown, mouseup and mouseclick send this over the Mouse.focus signal, and let mouseclick, esc and tab send the same over the Keyboard.focus signal.

You'd then have some idea of what needs to be moved as a result.

User Side

Of course, that's all base implementation stuff. On the client side, you don't want to have to do things like maintain your own table of draggables to dispatch a signal to when relevant. You'd want to be able to do something like

draggable dragDefs $ plainText "This text is draggable"

and have that tap the right signals so that when you mousedown or touch on "This text is draggable", it starts moving along with the cursor. In basic terms what needs to happen is

  • when the mouse down signal is being sent
  • and the Mouse.focus signal is referring to a draggable
  • start piping cursor position, modified by initial deltas, into the x and y coordinates of that element

and I have no idea what the appropriate way to express that is in the framework of the existing Elm language.

It sounds like it might just be easier to avoid those interactions while I'm starting out. SSEs sound like they'd be a much easier first feature, actually.

SSEs

The reason being that, when you think about it, this fits perfectly into the FRP paradigm. A source is a signal whose value is the latest matching message body and/or id. That's it. You'd want the declaration to look something like

src = eventSource "/my/source/uri" ["message type 1", "message type 2" ...]

at which point src should be a signal you can pass around, whose current value will be the latest message coming out of "/my/source/uri" that has one of the message types specified. It might also be useful to handle unlabeled messages, at which point our message needs to look something like

data SSE = SSE { id : Maybe Int, label : Maybe String, body : String }

Manageable, if slightly annoying due to the optional fields.

You'd implement a rolling message by piping src through plainText . .body, and you could put together a very simple chat program with some judicious use of foldp.

These were all just some random thoughts I wanted a good look at, for the time being. Like I said, I'll be throwing my next few spare hours at putting together an Elm-based WebMote front-end. Fortunately, this task doesn't involve any in-depth interaction, and the SSEs aren't central to the exercise.

Monday, June 17, 2013

Elm First Impressions

For the past little while, I've been poking around a new language named Elm. A Haskell-like web front-end language with a heavy focus on FRP. Actually, no, it's not like Haskell, its syntax is Haskell except for a few omissions[1], a couple justifiable small changes, and a couple pointlessly gratuitous differences[2]. To the point that the actual, official recommendation is to just use Haskell mode to edit Elm files.

This works pretty well, except for one thing: Elm has a built-in reader macro for Markdown input. Using this feature in Haskell mode plays all kinds of hell with your indentation and highlighting. Enough that I thought it worth-it to hack a workaround in using two-mode-mode. This is far from ideal, but bear with me. You need to get two-mode-mode from that previous link, do a search/replace for mode-name into major-mode, and delete the line that reads (make-local-hook 'post-command-hook). Then, you have to add the following to your .emacs somewhere:

(require 'two-mode-mode)
(setq default-mode (list "Haskell" 'haskell-mode)
      second-modes (list (list "Markdown" "\[markdown|" "|\]" 'markdown-mode)))

and then run two-mode-mode whenever you're editing .elm files. The end result is that, whenever you enter a markdown block with your cursor, your major mode will automatically change to markdown-mode, and change back to haskell-mode when you leave. There has to be a better solution than this, probably involving one of the other Multiple Modes modules, and I'll put some thought into it when I get a bit of time.

Installation/Basics

Installing is ridiculously easy. If you've ever installed a module for Haskell, you won't have trouble. It's just cabal update; cabal install elm elm-server. Do the update first, like it says there; the language hasn't reached 1.0 status as of this writing, which means that it's quite likely there will be significant changes by the time you get around to following these instructions.

You write code into .elm files, which you can either preview dynamically or compile. You do the dynamic preview thing by running elm-server in your working directory. That starts up a server listening on http://localhost:8000 that automatically compiles or re-compiles any .elm file you request. That server runs on Happstack, and does a good enough job that the official elm-lang site seems to serve directly from it.

If you're like me though, you prefer to use static files for your actual front-end. You can use elm --make --minify [filename] to generate a working .html file[3] that you can serve up along with the elm-runtime from whatever application server you want to use.

Enough with the minutia though. Really, I'm here to give you a paragraph or two on what I think about the language.

What I think about the Language

The usual disclaimers apply.

  • you'll easily find more people who are familiar with JS/HTML than those who are familiar with Elm
  • if you use it, there's an extra[4] abstraction layer between you and the final front-end
  • using it forces your users to enable JavaScript. Ostensibly, you can use the compiler to generate noscript tags, but all these seem to do is statically document what the page would do if JS was on.

That second one in particular means that once again, you really should learn JavaScript before trying to use Elm to save yourself from it.

Once you get past that, it's quite beautiful and elegant. Much better than plain JS for some front-end work. Not that that's a very high bar.

There's some stuff conspicuously missing, like my beloved SSEs, and some basic DOM interactions including draggable and an arbitrary, element-triggered click event. The approaches available out-of-the-box are respectively, Drag Only One Element That You Can't Drop and Detect Mouse Location On A Click, Then Dispatch Based On It. Neither of those seem very satisfying. In fact, the proposed workarounds look strictly worse to me than the "callback hell" this language is trying to save me from.

Those shortcomings are just getting me more interested, to be honest. The reason being that it looks like it's possible to implement additional native functionality fairly easily, so all it'll do is cause me to spend some time writing up the appropriate, signal-based libraries to do these things.

Overall first impressions so far are good, though I'm seriously questioning how useful this language is going to be for more complicated interfaces. In the short term, I'll test out its shallow limits by writing a new WebMote front-end.

I'll let you know how it goes.


Footnotes

1 - [back] - Which I'm pretty sure will eventually be addressed. I particularly miss full sections and where, though you'd think the multi-line function declarations would be the biggest gap.

2 - [back] - For no reason I could see, : is Elm's type annotation operator, while :: is Elm's cons. It's precisely the opposite in Haskell, and buys little enough that I hereby formally question the decision. Similar reasoning seems to apply to the operator <|, which seems to do exactly the same thing as Haskells' $, except that it's twice as long.

3 - [back] - Or separate .html and .js files, if you also passed the -s flag.

4 - [back] - Not particularly stable, yet.

Sunday, June 9, 2013

Short Ramble and Almost Literate Cooking

Just as a heads up, this piece is brief reflection followed by dinner. No programming information, except perhaps metaphorically.

Short Ramble

I'm sitting at home alone, sipping tea and listening to the almost-silence of the city with light cello overtones. My wife went to the cottage for a couple of weeks and took our kid with her, so the apartment is relatively peaceful for the first time in, oh, about a year. Now that I think about it, this is the first time in about seven or eight years that I'm spending any serious alone-time.

There's a story in that too. It's really bizarre, but everyone I tell the situation to has a reaction resembling "Wow. You must be feeling pretty lonely". And to set that straight, no I don't. I enjoy solitude. It's not a dirty word to me. Oddly, everyone who has this reaction really ought to know better given what I am, but it's still pretty consistent. Enough that I'm beginning to wonder if there isn't some social undertow I hadn't noticed before. Anyway, not important right now.

Man, life has been crazy as fuck lately; I've been rolling with the punches long enough that "rolling" began to feel like the natural state. And that's probably not a good thing. From huge deployment pushes at work, to the disruptive experience of looking for a new place, to the massively disruptive experience of having a child, there hasn't really been anywhere near enough time for me to sit down and reflect on much. So I'm taking the opportunity, while I've got my tea in hand and the clock and cello to keep me company.

Or rather, I started, then discovered that it was too hard to take myself seriously. Boo hoo, Inaimathi, the professional Canadian Lisper, with a happy son and wife, diminishing mortgage and steadily improving physical fitness is feeling sorry for himself. Why is that? Could it be because the software he's writing at his tiny-but-profitable company is getting enough clients attention that maintenance is non-trivial? Because he's only got time to devote about an hour a day to artistic endeavors and hobby blog?

And having run smack into my own snarky sense of self-doubt, it became clear that it would be more fun to be doing something other than sitting here. I was going to head over to the local Pho place for food, but lets put these hands to good use.

Almost Literate Cooking

I've got a tag on this blog called almost-literate-programming. It's not what I write most because it takes quite a bit of effort to slice a program thinly and accurately enough to label its insides for others' consumption, but it's up in the top five[1]. I'm going to try something similar here.

Before I begin, a note on general strategies. The North American approach almost universally seems to be recipe-driven. That is

  1. decide what you're going to make
  2. consult a recipe
  3. collect the ingredients you need to make it
  4. portion those out in precise quantities through a learned ritual
  5. construct food

This contrasts pretty severely to the traditional eastern European way of doing things, which from what I've observed is usually ingredient driven.

  1. see what you've got around
  2. construct food
  3. if the result is good, record recipe

No real judgment call here by the way; both are valid ways of constructing a meal, the former gets more consistent results while the latter is a lot more fun assuming you have the habit of keeping a stocked kitchen. I'm going to mix and match today; consulting my inventory, I've found that my potatoes are coming up on their best-before date, so I'll make those. I also kind of want some fried chicken, so I'll make that too.

I probably should have defrosted the chicken first, but did the potato peeling instead. Most people, including everyone who's ever cooked for me, throws the skins away, but I'm trying to use the whole buffalo today, so.

This is one of the problems you run into with the ingredient-driven approach; it doesn't lend itself to long-term planning. This'll have to go in the microwave for defrosting, rather than doing it the natural way. If I was having people over, I'd have second thoughts at this point, but I'm not fussy when it comes to chicken.

Right, I want the potatoes sliced into even chunklets. They don't have to be a particular size, they just need to be similar enough to each other that they'll boil at about the same time.

The chicken's still not defrosted, and I just put the pot on, so I prepare the breading stages for that chicken. We've got breadcrumbs[2], flour and eggs. My wife always skips the flour for some reason, but it never makes the chicken taste any worse, so whatever works for you. The two mandatory parts here are eggs and breadcrumbs. I've always found it mildly odd that making a fried chicken meal involves marinating the flesh of an animal in the juices of its unborn offspring. Not really sure who came up with that one, or how, but it lends credence to some theories I've heard.

Anyway, the chicken's out. And the water's warming up sufficiently to accept my offering of potato, so I put those chunks in along with some salt.

This is where the fillet knife comes out. Yes, we own Chef Tony knives. They were on sale when we were moving in together, and the fillet knife and stake knives aren't half bad. Flouring the chicken is just step one.

Checking on the potatoes. If you can do this to one, it's not ready yet. A boiled potato would have just fallen apart right there.

This is my usual fried chicken routine. Flour, egg, flour, egg, breadcrumbs. Like I said, the flour is entirely optional, you can do this part with just eg, then breadcrumbs. As a note, it's much harder doing this with one hand. Especially if your other hand is holding a phone.

In the meantime, the potatoes are boiled, so I drain them and put them back on low heat to dry out. You can't tell from those pictures, but they're already falling apart by the first one. I probably should have kept them boiling for a little bit longer than I did.

You can see the consequences in that mashing picture. If they were really ready, they wouldn't be crumbling like that, they'd be mashing entirely. There's two things wrong with the creme. First, I didn't have time to heat it, so it's going in almost straight out of the fridge. And second...

...it's not creme. I'm lactose intolerant, so I can't have the real stuff, and I couldn't find lactose free creme anywhere. I'm reasonably sure it exists, just haven't seen any in real life.

Oil goes in the pan on medium/high heat. It's at 7 on my stove, yours might be different. This is Canola oil. I'm pretty sure you can use vegetable oil too if you like, but don't use olive for frying. You want enough in there that it'll 1/2 to 3/4 submerge your fillets, not just enough to cover the bottom of the pan.

Every part of the fucking buffalo. The leftover breadcrumbs, eggs and flour come together to make a little bread/cake thing. My grandmother called it a "tortica" in Croatian, which literally means something like "cakette" or "small cake", but it's really just the leftovers after the breading process. I always found it mildly entertaining that this is a "bread" made by adding egg and flour to ground up bread. Maybe I should start calling it zombie bread.

The potatoes are coming along nicely. I'm still keeping them on low heat so that they reduce a bit more.

That's the first wave of chicken on the pan. The oil's been heating for a few minutes at this point. If you did it right, it should start sizzling as soon as you put the first piece of chicken in there. The flip happens pretty soon thereafter; only about three minutes or so. You should be looking to get that darker brown color on each side, rather than counting time.

The potatoes are just about ready at this point, and the chicken is ready not long after that. I like to split a thicker piece just to make sure there's no red inside. The rest of the chicken goes on the same way. Once that's done...

The potato skins go in. This takes a bit longer than the chicken, just because I'm basically trying for a chip-like consistency. They need to be salty and crunchy when they come out, which is why I salt and dry them over the pan. Uh, just to clarify, since I realized after the fact that I only have a "before" and "after", but not a "during" pic, I did actually put the skins into the oil. I just took them out and dried them off on the mesh afterwards.

And that's that. I packed some of it away for tomorrow, and truthfully didn't end up finishing what I put on the plate either.

This won't do at all.

Cleanup is just as much a part of the task as setup is

(defmacro with-kitchen (&body body)
  `(progn (get :cutlery :dishes :ingredients)
          ,@body
          (clean :cutlery :oven)
          (wash :dishes)))

(let ((m (with-kitchen (make-instance 'meal))))
  (eat m))

so I need to get this out of the way. It'll also give me the time to get some water boiling for an accompanying tea.

There. Admittedly, another round of dishes is waiting after these finish their soak, but it's better than nothing. Now then

Fuck.

Yes.

See you next time.


Footnotes

1 - [back] - If you don't count the language-specific tags, anyways.

2 - [back] - Store-bought, as it happens, but nothing's stopping you from making your own[3].

3 - [back] - If you do, add some garlic and oregano[4].

4 - [back] - Unless you don't like garlic, I guess.

Sunday, June 2, 2013

Sudoku ReRedux

Ok, this is why I'm less than proud of that actually, factually working solution.

import List
 
main = putStr . unlines . map disp . solve . return . input =<< getContents
 
solve s = foldr (\p l -> [mark (p,n) s | s <- l, n <- s p]) s idx
 
mark (p@(i,j),n) s q@(x,y)
    | p == q                             = [n]
    | x == i || y == j || e x i && e y j = delete n (s q)
    | otherwise                          = s q
    where e a b = div (a-1) 3 == div (b-1) 3
 
disp s = unlines [unwords [show $ head $ s (i,j) | j <- [1..9]] | i <- [1..9]]
 
input s = foldr mark (const [1..9]) $
  [(p,n) | (p,n) <- zip idx $ map read $ lines s >>= words, n>0]
 
idx = [(i,j) | i <- [1..9], j <- [1..9]]

Except, as I mentioned, that one cheats by omitting the type signatures[1], so here's the original on which it was based:

import Data.List

type T = (Int,Int) -> [Int]

main = do
  s <- getContents
  putStr $ unlines $ map disp $ solve [input s]

solve :: [T] -> [T]
solve s = foldr search s idx where
    search p l = [mark (p,n) s | s <- l, n <- s p]

mark :: ((Int,Int),Int) -> T -> T
mark (p@(i,j),n) s q@(x,y) =
  if p==q then [n] else
  if x==i || y==j || e x i && e y j then delete n $ s q else s q
  where e a b = div (a-1) 3==div (b-1) 3

disp :: T -> String
disp s  = unlines [unwords [show $ head $ s (i,j) | j <- [1..9]] | i <- [1..9]]

input :: String -> T
input s = foldr mark (const [1..9]) $
  [(p,n) | (p,n) <- zip idx $ map read $ lines s >>= words, n>0]

idx :: [(Int,Int)]
idx = [(i,j) | i <- [1..9], j <- [1..9]]

This is not the most readable code ever; its goal is supreme elegance[2], not instant clarity. It took me a couple of days thinking on-and-off, as well as a read-through of this almost equivalent Python transliteration[3] to finally understand what the hell is going on here.

Lets get the obvious out of the way.

disp :: T -> String
disp s  = unlines [unwords [show $ head $ s (i,j) | j <- [1..9]] | i <- [1..9]]

This takes a board (whose type is named T for some reason), and returns its string representation.

input :: String -> T
input s = foldr mark (const [1..9]) $
  [(p,n) | (p,n) <- zip idx $ map read $ lines s >>= words, n>0]

This takes a string representation and returns a board.

idx :: [(Int,Int)]
idx = [(i,j) | i <- [1..9], j <- [1..9]]

This returns all the (y, x) coordinates in a 9x9 board.

main = do
  s <- getContents
  putStr $ unlines $ map disp $ solve [input s]

This takes from standard in, tries to interpret the result as a board, solve it and print it.

type T = (Int,Int) -> [Int]

And finally, this is how a board is represented; it's a function of one argument, an Int, Int tuple, and returns a list of possible values, a [Int].

Before we go any further, there are a lot of naming conventions here that are aimed at terseness rather than comprehensibility of the resulting code. So lets just do a naive renaming for now.

import Data.List

type Board = (Int,Int) -> [Int]

main = do
  boardString <- getContents
  putStr . unlines . map disp $ solve [input boardString]

solve :: [Board] -> [Board]
solve boards = foldr search boards idx where
    search (x, y) boards = [mark ((x, y),val) brd | brd <- boards, val <- brd (x, y)]

mark :: ((Int,Int),Int) -> Board -> Board
mark (p@(x,y),val) board p'@(x',y') = 
  if p==p' then [val] else 
    if x==x' || y==y' || blockBound x x' && blockBound y y' then delete val $ board p' else board p'
  where blockBound a b = div (a-1) 3==div (b-1) 3

disp :: Board -> String
disp board = unlines [unwords [show . head $ board (x,y) | y <- [1..9]] | x <- [1..9]]

input :: String -> Board
input boardString = foldr mark (const [1..9]) $
  [((x, y),val) | ((x, y),val) <- zip idx . map read $ lines boardString >>= words, val>0]

idx :: [(Int,Int)]
idx = [(x,y) | y <- [1..9], x <- [1..9]]

Granted, we can no longer claim "707 bytes", but even this minor renaming makes the end result a bit more understandable. On to the difficult parts.

mark :: ((Int,Int),Int) -> Board -> Board
mark (p@(x,y),val) board p'@(x',y') = 
  if p==p' then [val] else 
    if x==x' || y==y' || blockBound x x' && blockBound y y' then delete val $ board p' else board p'
  where blockBound a b = div (a-1) 3==div (b-1) 3

input :: String -> Board
input boardString = foldr mark (const [1..9]) $
  [((x, y),val) | ((x, y),val) <- zip idx . map read $ lines boardString >>= words, val>0]

solve :: [Board] -> [Board]
solve boards = foldr search boards idx where
  search (x, y) boards = [mark ((x, y),val) brd | brd <- boards, val <- brd (x, y)]

The high level of what's going on here is that you're representing a board as a function of (Int, Int) -> [Int], and marking spaces by wrapping that function up in a dispatch/delete which returns pruned results in some circumstances.

mark :: ((Int,Int),Int) -> Board -> Board
mark (p@(x,y),val) board p'@(x',y') = 
  if p==p' then [val] else 
    if x==x' || y==y' || blockBound x x' && blockBound y y' then delete val $ board p' else board p'
  where blockBound a b = div (a-1) 3==div (b-1) 3

This function uses some uncommon notation, and isn't really structured the way you'd expect in a Haskell program. That initial 12-line solution actually does a marginally better job of it. Here's a slightly revised, but equivalent version[7]

mark :: ((Int,Int),Int) -> Board -> Board
mark (p@(x,y),val) board p'@(x',y') 
  | p == p' = 
    [val]
  | x==x' || y==y' || blockBound x x' && blockBound y y' = 
    delete val $ board p'
  | otherwise =
    board p'
  where blockBound a b = div (a-1) 3==div (b-1) 3

That uses the more common guard statements rather than a cascaded if/then/else. The input line and type signature on this one is what threw me for the longest time, so I'm going to linger there for a moment.

mark :: ((Int,Int),Int) -> Board -> Board
mark (p@(x,y),val) board p'@(x',y') 

Remember, our Board is defined as ((Int, Int) -> [Int]), so that type signature could also be written

mark :: ((Int,Int),Int) -> (Int, Int) -> [Int] -> (Int, Int) -> [Int]

which should ironically clarify things. The actual arguments aren't doing anyone any favors either. The @s there are applying labels to some destructured constructs. The end result is that you can use the name p instead of (x, y) and p' instead of (x', y'). The following code is equivalent, but very slightly longer[8]:

mark ((x,y),val) board (x',y') 
  | (x, y) == (x', y') = 
    [val]
  | x==x' || y==y' || blockBound x x' && blockBound y y' = 
    delete val $ board (x', y')
  | otherwise =
    board (x', y')
  where blockBound a b = div (a-1) 3==div (b-1) 3

Right, so that's how you mark a value. Except it doesn't really make sense in isolation. Not until we take a look at, at minimum, input

input :: String -> Board
input boardString = foldr mark (const [1..9]) $
  [((x, y),val) | ((x, y),val) <- zip idx . map read $ lines boardString >>= words, val>0]

This is the function that takes a board string and returns an actual board constructed from it. The main operation there is foldr, and I'm going to assume you understand how a fold works for this exercise. If you don't, read this and this, then do some googling. (const [1..9]) is a function that always returns the list of integers from 1 to 9, inclusive. It's equivalent to (\_ -> [1,2,3,4,5,6,7,8,9])[9]. What it produces... is a bit trickier. It has to do with an inherent property of Haskell, and that type signature for mark I showed earlier.

mark :: ((Int,Int),Int) -> (Int, Int) -> [Int] -> (Int, Int) -> [Int]

First off, Haskell partially applies everything by default. Meaning that if you pass fewer than 4 arguments to mark, what you actually get back is a function that takes the next argument, and returns either the next partial or the final result. If you take a look at foldr, its type is

foldr :: (a -> b -> b) -> b -> [a] -> b

which means that it'll be treating mark as a function of two arguments. Note that the second argument is itself a function. Specifically, a (Int, Int) -> [Int], which means that mark will be getting three of its arguments filled. It might be easier to think about it like this

mark :: ((Int,Int),Int) -> ((Int, Int) -> [Int]) -> (Int, Int) -> [Int]

but since every function in Haskell can be applied partially, those are equivalent types. The end result of that fold operation is another function of (Int, Int) -> [Int]. Lets take a real close look at what's going on there.

This is the empty board

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Because it only contains zeros, it'll be represented as (const [1..9]). Of course, it also has to be encoded as

"0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0"

but that first one is easier to read.

GHCi, version 7.4.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load "/home/inaimathi/projects/code-retreat/sudoku/sudoku-elegant.hs"
[1 of 1] Compiling Main             ( /home/inaimathi/projects/code-retreat/sudoku/sudoku-elegant.hs, interpreted )
Ok, modules loaded: Main.
*Main> let b = input "0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0"
*Main> b (1, 2)
[1,2,3,4,5,6,7,8,9]
*Main> b (1, 3)
[1,2,3,4,5,6,7,8,9]
*Main> b (6, 3)
[1,2,3,4,5,6,7,8,9]
*Main> 

Now, adding a value makes sure it recurs once.

*Main> let b2 = input "4 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0"
*Main> b2 (1, 1)
[4]
*Main> b2 (1, 2)
[1,2,3,5,6,7,8,9]
*Main> b2 (2, 1)
[1,2,3,5,6,7,8,9]
*Main> b2 (2, 3)
[1,2,3,5,6,7,8,9]
*Main> b2 (5, 5)
[1,2,3,4,5,6,7,8,9]
*Main> 

That's the key to understanding this. Lets do the Little Schemer thing, and break input down. Not necessarily the way GHC does it, but so that we can conceptually understand what's happening here.

00}} input "4 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0 0"

01}} foldr mark (const [1..9]) $ 
                [((x, y),val) | 
                 ((x, y),val) <- zip idx . 
                                 map read $ 
                                     lines boardString 
                                     >>= words, 
                                     val>0]

02}} foldr mark (const [1..9]) $ 
                [((x, y),val) | 
                 ((x, y),val) <- zip idx . 
                                 map read $ 
                                     ["4 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0",
                                      "0 0 0 0 0 0 0 0 0"]
                                     >>= words, 
                                     val>0]

03}} foldr mark (const [1..9]) $ [((1, 1), 4)]

04}} foldr (\((x,y),val) board (x',y') 
             | (x, y) == (x', y') = 
               [val]
             | x==x' || y==y' || blockBound x x' && blockBound y y' = 
               delete val $ board (x', y')
             | otherwise =
               board (x', y')
             where blockBound a b = div (a-1) 3==div (b-1) 3)
           (const [1..9]) $
           [((1, 1), 4)]

05}} (\board (x',y') 
        | (1, 1) == (x', y') = 
          [4]
        | 1==x' || 1==y' || blockBound 1 x' && blockBound 1 y' = 
          delete 4 $ board (x', y')
        | otherwise =
          board (x', y')
        where blockBound a b = div (a-1) 3==div (b-1) 3) (const [1..9])

06}} (\(x',y') 
        | (1, 1) == (x', y') = 
          [4]
        | 1==x' || 1==y' || blockBound 1 x' && blockBound 1 y' = 
          delete 4 $ (const [1..9]) (x', y')
        | otherwise =
          (const [1..9]) (x', y')
        where blockBound a b = div (a-1) 3==div (b-1) 3)

And there. If we added another space, it would unfold another level, with the entire step 06}} there being slotted in instead of (const [1..9]). Ok, last bit.

solve :: [Board] -> [Board]
solve boards = foldr search boards idx where
  search (x, y) boards = [mark ((x, y),val) brd | brd <- boards, val <- brd (x, y)]

Hopefully, now that I've unfoldrd the definition of input, this is intuitively obvious. search is an internal function that takes a list of boards and a space (x, y), and attempts to solve for them. It does this by taking each possibility for that space on each board and marking them, collecting all the results. If you look carefully, and have read those foldr links from earlier, this also explains why the Haskell version starts returning answers very quickly. The way iteration unfolds here, the first board is going to be solved quite a while before the complete sequence is solved, which means it'll be returned and printed quickly and thereafter not take further resources from the program.

The page "explaining" this code claims that it's "neither fast nor clever", and the Python version states that it's "Not the ideal way to solve Sudoku", but I'm honestly having a hard time imagining one that would give you any kind of gain, either in terms of performance or elegance[10].

Possibly the most interesting thing about this solution for me is that, since it generates a list of all possible boards given a solution, you write a generator fairly simply[11] using something along the lines of choice $ solve [input . take 161 $ cycle "0 "], then redacting the results to a desired difficulty level. That might be another thing for me to throw some time at.


Footnotes

1 - [back] -Which, judging by the responses I get whenever I ask for comments on my Haskell code, is somewhere between grossly impolite and crime-against-humanatee.

2 - [back] -Which it hits, in my opinion.

3 - [back] -Python doesn't have the same approach to partial functions that Haskell does, so the transliteration is both slightly easier to understand and slightly clunkier.[4] It also uses foldl instead of foldr, because Python only comes with an implementation of foldl. Something tells me this kneecaps the .py versions' performance. Testing it out on the sample data listed at the bottom of this page, after manually sanitizing for spaces, seems to confirm that suspicion. On my machine, it spun up to 100% usage on one core until it occupied all of my memory, then sat there paging until I killed it. The Haskell solution, by contrast, starts producing results very close to instantly, puts all 4 cores to good use, and utterly fails to mem-rape my laptop before computing all possible solutions, which it does well before the Python version produces any solutions[5].

4 - [back] -That's Python for you far as I can tell, in case you were wondering. It could almost be their slogan. "Python: Easier to understand and fatter than Haskell.".

5 - [back] -So I guess that slogan should really be "Python: Easier to understand, fatter and much slower than Haskell."[6].

6 - [back] -Ok, that isn't entirely fair; this example wasn't optimized in any sense of the word. It uses list comprehensions instead of generators, and could probably implement a lazy foldr equivalent to start returning results right away. I'll put a bit of time into that later.

7 - [back] -As an aside here, it's mildly frustrating that every single gain in clarity in this exercise adds lines to the final count. I wish there was a way of being clearer while being more succinct.

8 - [back] -which I get the feeling is why the author chose to use the @s.

9 - [back] -though in this particular case, it'll be treated as (\(_, _) -> [1,2,3,4,5,6,7,8,9]) :: ((Int, Int) -> [Int]) because of how Board is defined.

10 - [back] -Though, obviously, I think clarity could be somewhat improved.

11 - [back] -I was going to say "Trivially", and then promptly lost 40 minutes to trying to figure out why exactly it is that an RVar [Int] can't be shown by default, or have its contents putStrd no matter how much liftM was applied. "Easier to understand, but fatter and slower than Haskell", also happens to be why I've been using Python at work. Haskell makes certain, very well understood things supremely easy, but as soon as I sit down to do something like output or randomness that's trivial in other languages, I find myself suffering a few hours of headaches before figuring it out. I also happen to agree with Sussman about the core point; implementing things that are very well understood is not the primary goal of programming.