Another General Update

Tue Nov 25, 2014

Fuck its been a while.

I think.

I'm not actually sure because I've been under enough stress on enough different fronts lately that I'm not sure I can reckon time accurately, other than to sequence it. This isn't going to contain any kind of big insight; I'm thinking about various macro-expansion and edge-detection-related things, but I'm saving the interesting details for their own articles once the relevant work is "done" rather than merely "in progress". The following is just a quick brain-dump of stuff that's been on my mind lately.

Dead Bitmaps 2: Rise of the Ellipses

I'm starting to think about ellipse finding. And, at the urging of some members of the Toronto Haskell User Group, shape finding in general. The pre-beta cut of the code which will find an ellipse in a region is up at github. Essentially, we take a region, find its center, plot an ellipse based on that|1|, and check perimeter coordinates at ~10 degree intervals. If we get three consecutive misses, or 10 total missesGarbage Collection

Having studied a few tracers|3|, it's at once obvious why they emerged in Lisp systems, why Lisp had the reputation of being slow to begin with, and why the "everything is a list" myth continues despite its factual incorrectness. It turns out that if you commit to a one-size-fits-all data structure|4|, decide that you don't care at all about data locality|5|, and don't optimize anything, you can write a working tracer in just over 300 lines of C. I can't see a generational or copying approach pushing this past about 500 or 600 lines. You wouldn't want to try doing any kind of high-performance computing this way, but if your primary concern is security|6| this starts looking like a pretty good idea.

The problem is, contiguous memory vectors are really good for performance, and if you go far enough with this mad scheme, there are lots of things at the lowest levels that end up taking ridiculous amounts of memory which you could theoretically save by hand-tuning it. Theoretically. In practice, I tend to think that even small systems by the day's standards have enough moving parts to give an un-aided human plenty of trouble.

The point being: the naive way of building tracers plays exactly to Lisp's conceptual tropes, and gives you "slow" code. "Duh", when you think about it.

Composability and Cost Models

Conflicts I've observed between the Haskell and ML communities are about

I haven't informed myself about the first well enough to comment yet, though I am trying.

The second one comes down to the trade-off between having |7| for pieces of your program if you're not. There seem to be two real solutions and two non-solutions to this problem. The non-solutions are picking either strict or lazy and pretending that's good enough. As I understand it, Rob Harper has picked one of these. Specifically, he's taken the simple cost model (see the first comment) and made peace with the fact that he gets to write some amount of manual glue code. Personally, if I were forced to pick between the non-solutions I'd pick the other one. I don't give a rat's ass about performance except in very specific situations, so getting very cheap composition sounds like a good deal to meHal Abelson chats with the CompSci Cabal

This was fucking awesome. |9|, also known as "Abelson and Sussman", and Dann managed to get Hal Abelson to talk to us about what went into the book, what he thinks about CompSci teaching evolution over the past few decades, how building language interpreters helps you think about problems, and some of the things that surprised him about the industry. It was interesting enough that I don't think I could do it justice in a mere writeup, so I won'tFootnotes

1 - |back| - Later cuts will plot multiple ellipses with some tolerance and look for any complete ones, or alternately check a particular radius around each point.

2 - |back| - Actual thresholds subject to change.

3 - |back| - And implemented most of one that I'll never be able to show you.

4 - |back| - The Cons cell.

5 - |back| - By using exclusively Cons cells rather than occasionally resorting to contiguous memory vectors or naked primitive data.

6 - |back| - As in, preventing buffer overflows and segfaults at all costs.

7 - |back| - And I'd probably be writing those in C rather than either of the higher level languages up for discussion.

8 - |back| - To be fair, I also know quite a few languages, and that club would be missing a non-strict member without Haskell. So for me personally, making that choice expands the convex hull of my perspective, and so is virtuous regardless of the specific trade between evaluation schemes.

9 - |back| - Though this does unfortunately mean that you'll never see it; we weren't in an "On Air" hangout, so none of this was recorded as far as I know.


Creative Commons License

all articles at langnostic are licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License

Reprint, rehost and distribute freely (even for profit), but attribute the work and allow your readers the same freedoms. Here's a license widget you can use.

The menu background image is Jewel Wash, taken from Dan Zen's flickr stream and released under a CC-BY license