2009-02-16

Knitting is an acceptable Lisp

So, I'm a knitter. And I pretend to be a designer some days, when I'm not knitting endless swathes of k2, p2 rib. But first and foremost, I'm an unabashed geek.

As such, I took a look at KnitML. And it's neat. Well, in theory, it's neat. In practice, I haven't got the java dependencies set up on my computer yet to play with it. I do intend to do that, and am downloading them, but while I wait for them, I want to ponder through an idea that's been percolating in my brain.

Namely, I think of knitting patterns in two ways. One is the chart. This is how I write patterns, really. And given the choice between a chart and a list of stitches, I'll pick the chart every time.

It's a question of information density. The chart presents all the information that I need, in the least amount of space while still being human-readable.

So, let's look at a chart.

It's a fairly simple pattern, embedded moss stitch rib. And can be easily transformed into a written pattern:

  1. p2, k2, p1, k1, repeat to end of round
  2. p2, k2, p1, k1, repeat to end of round
  3. p2, k1, p1, k2, repeat to end of round
  4. p2, k1, p1, k2, repeat to end of round

This is where my brain starts making clicky noises. See, my immediate reaction to that is that it's a simple program. One that generates a handsome little ribbing.

However, my second line of thought runs straight for a programming principle: Don't Repeat Yourself. My process for generating a pattern is to draw charts in Inkscape, test those charts by knitting them, then translate the chart into written instructions. In future, I may also want to make my charts available in KnitML.

What this immediately says to me as a programmer is that I should have a single piece of data from which I can generate:

  • PNG graphics
    This is the format I use to show charts. It's a useful format in that it does a good job of reducing low-colour line drawings (like knitting charts) to a fairly small file size with no loss of detail or crispness.
    This is an even worse format to use as a data source, though. Rather than just interpreting the XML that SVG gives, I'd have to start into OCR territory.
  • SVG graphics
    This is the format that I actually use to make charts. Unfortunately, it would be a considerable effort to use it as a starting point: Anything more complicated than a knit or purl stitch are relatively complex "groups", rather than simple objects.
    However, they work admirably as a way to draw charts, and from my perusal of the spec, should be able to be drawn programmatically fairly easily.
  • HTML lists
    This actually isn't a bad starting point. Not good enough that I'd want to use it as a data source, but not bad enough, either, to discard it out of hand.
    Specifically, if I look at the HTML describing the pattern:
    <ol>
      <li> p2, k2, p1, k1, repeat to end of round
      <li> p2, k2, p1, k1, repeat to end of round
      <li> p2, k1, p1, k2, repeat to end of round
      <li> p2, k1, p1, k2, repeat to end of round
    </ol>
    Other than the <ol> and <li> tags, this actually isn't a bad representation of the data at all.
  • Plaintext
    What if I were to use the plaintext representation of the aforementioned list:
    p2, k2, p1, k1, repeat to end of round
    p2, k2, p1, k1, repeat to end of round
    p2, k1, p1, k2, repeat to end of round
    p2, k1, p1, k2, repeat to end of round
    That's actually, as I alluded before, a programmatic representation of knitting. And, were it not for that pesky "repeat to end of round", would be nearly perfect.
    In fact, this is relatively close to what KnitML uses as a human-readable format, according to my reading of the spec.
  • S-Expressions
    These little gems are the core of Lisp, and are easily transformable to and from XML if the need arises.
    The core elements to them are lists and atoms. A list is multiple atoms surrounded by parentheses and separated by spaces. An atom is some text representing something.
    Thus, the pattern described above becomes:
    (repeat 2
      (repeat-to-end (p2 k2 p1 k1)))
    (repeat 2
      (repeat-to-end (p2 k1 p1 k2)))
    And any Lisp programmer reading this just started twitching. As that's not properly-formed Lisp. On the other hand, it does represent a very interesting way to mix data and instructions.
    Patterns become lists of stitches and transformative operations performed on those stitches. It's knitting as a pseudo-mathematical notation.

So, taking s-expressions as a base, what does it all mean?

Well, in that list of representations, the further along I went, the more the representation changed from being a depiction of the data to a representation. By the time we reach the plaintext version of the pattern, it is recognisable as a rudimentary program.

The s-expression version isn't even a rudimentary one; if it were fed into an interpreter that recognised the words and symbols used, it is a program to generate a knitting pattern.

Now that offers some interesting prospects, because the output of the interpreter by no means has to be fixed. For instance, I could have one interpreter that reads the pattern as a way to generate a plain text file, another interpreter that generates an SVG graphic and a third that reads the pattern as a way to generate the equivalent KnitML file.

Why does all this matter? Well, I've become interested, in the past weeks, in the idea of an editor where I type in a row of stitches and it appears on the screen as a graphical pattern. Thinking about how to represent stitches is a first step on the road to knitting pattern zen.

7 comments:

  1. I feel like a bad lisper, as it looks like fine Lisp to me. ;)

    (I mean, a lot of my programs start out as a data picture, then I write the program which understands it...)

    ReplyDelete
  2. It's the stitch lists that are off. Were this a Lisp program, it would usually read (repeat 2 '(p2 k2 p1 k2)) as repeat is a function, while the stitches are a list of atoms.

    Now, if repeat were a macro, that's all moot.

    I played around for 30 minutes over coffee and I'm ashamed to admit that my macro-writing is not what it was 6 months ago: I can get it to not evaluate the list of stitches no problem, but am at a loss to make it treat k2, p2, etc. as atoms rather than trying to evaluate them as variables when the macro evaluation is complete.

    ReplyDelete
  3. Rather than asking for well-formedness, I went for a much simpler idea in designing a parser for knitting stitches as a lisp.

    At the moment, my implementation has three data types, total:

    There are lists. They can be nested infinitely and are the basic building block of the system.

    There are functions. They are reserved symbols stored in a lookup table (a hashmap).

    There are atoms. Everything that isn't a list or a function is an atom. They're grouped by lists and are operated on by functions.

    That means that, in my implementation, (repeat 2 (p2 k2 p1 k1) does indeed evaluate to ((p2 k2 p1 k1) (p2 k2 p1 k1)), without knowing what the pX and kX mean.

    That'll change, though, as stitch names become keywords that are understood by the parser.

    For the moment, all I wanted was to create a parse tree (easy to do with a s-expression based format, as the representation is the parse tree).

    The next step is assigning meaning to the symbols in the tree.

    ReplyDelete
  4. Anonymous18/2/09 13:26

    Your knitting chart is also reversed from the standard chart, which reads right to left on odd rows, then left to right on even rows, mimicking the order in which the stitches occur in a serpentine pattern which has as set points the original "right side" first and last stitches as first = tip of left needle, last= end of left needle.
    -D

    ReplyDelete
  5. Ah, yes. That's because I grabbed it from a post where I was charting various circular patterns.

    ReplyDelete
  6. It sounds like you want to do projectional editing. This is a brave new world that Martin Fowler brought up today in his talk. Here's his review of MPS. From what he told me, it's going open source soon.

    Are you trying to create a domain specific language for rows? That's basically what Knitting EL (from the KnitML Project) is. If you go with the plaintext option, perhaps Knitting EL is a step above? Your stitch pattern would look like this in Knitting EL:

    Row [1,2]: Repeat to end {p2, k2, p1, k1}
    Row [3,4]: Repeat to end {p2, k1, p1, k2}

    and it can be converted to 100% valid KnitML (in XML format) with a tool that exists today. Once that happens, you can create a chart from it with relative ease (what I am working on now).

    It sounds like we should definitely talk. Even if you don't geek Java, I bet we could have some good design chats.

    ReplyDelete
  7. Projectional editing: I've bookmarked the page, but I think I'm doing something far simpler, as there's fewer valid inputs and outputs.

    Yep, I'm playing with making a DSL for rows. More realistically, I'm using a Lisp-based DSL as a starting point because it's easy to parse.

    Deliberately, I'm trying to work in a way that approaches the KnitML specificaton and with an input format that resembles KEL.

    My long-term goal is full compatibility with that document spec. as it's there, it's got a level of completeness that I'm striving toward, and I've no great issue with how it presents or records data.

    My short-term goal is generating a chart, on the fly, from user input. So this means taking the input, converting it to a parse tree, walking the tree and asking each node for its graphical representation, then displaying the graphical representation.

    So, the reason to stick close to KnitML is that I very much want there to be another operation where walking the tree instead generates XML.

    ReplyDelete