## A Computational Model of Knitting

This is the second blog post of the “Towards Computational Craft” series.

This part is all about the process of knitting as seen through the lens of a computer scientist.

While the first part was a maifesto for structural rather than procedural knitting instructions, we will now take a look at hand-knitting as computation.

### Storing Stitches

First off we can observe, that hand knitting needles both have a storage and a stitch processing function. For example when knitting socks, three or more needles may be used, only two of which are operated by the bi-manual human, while the other needles only serve to hold the stitches.

#### Abstract Knitting Datatypes

In terms of their storage function, knitting needles can be regarded as physical implementations of popular computer science concepts, namely the abstract data types referred to as stack and deque.

While straight needles with caps store and retrieve their stitches according to the principle of LIFO (last in – first out), double pointed and circular needles additionally implement the functions of a queue or FIFO (first in – first out), effectively forming a double ended queue, also known as deque.

#### Knitting Memory

While the needles constitute the main memory, there is an immense amount of external memory available. Free memory usually takes the form of the yarn ball, whereas allocated memory is constituted by the finished knitwork. Once a stitch is dropped off the needle it is automatically saved to the external memory. Every stitch can be modeled by a data structure with pointers to the subordinate stitches which it holds together.

#### Garbage Collection

There even is an automatic garbage collection accounting for dropped stitches: once the number of superordinate stitches referencing a stitch drops to zero, the whole stitch is dropped altogether, meaning that it is replaced by the null stitch, which only contains references to is neighbors but not to any subordinate stitch. This garbage collection mechanism gives rise to typical avalanche effects, generally known as runs or ladders.

### Stitch Processing

#### Flipping Stitches

To simulate loop formation and the slip-stitch-over operation, frequently encountered in hand knitting, the stack and dequeue functions are slightly extended by simple flip or “loop through” operator. This operator exchanges two stitches at the top of the stack or the end of the queue with the side effect, that the second stitch which takes over the prime position becomes subordinate to what was previously the first stitch.

#### Von Neumann Knitting

The process of knitting is strictly sequential in nature, in contrast to the process of weaving, that may be considered an essentially parallel technique of fabric construction. In this respect knitting is similar to the Von Neumann architecture, but there are substantial differences in terms of the processing units: in the kind of computation performed by hand knitting there is no single CPU. Instead each needle point constitutes a decentralized processing unit, and pairs of such units operate in intimate interaction.

#### Number of Thread Processing Units

The fact, that straight needles do not have access to their very own working memory, explains the need for at least two needles in straight-needle based computation. The only notable exception to this “one hand washes the other” approach are some casting-on techniques, where the human hand performs functions that may also be taken over by a needle.

Although knitting needles have otherwise random access to the main memory both free and allocated, knitting operations are in practice mostly restricted to stitches that may be retrieved via the interface of the abstract data types and can be immediately released into the external storage.

#### The Four Clock Cycles

The default stitch processing operation usually requires four clock cycles:

• First one stitch of the source needle S is copied to the destination needle D by pop and push operations.
• In the next cycle a null stitch is retrieved from the free external memory and is pushed onto D.
• In cycle 3 the flip operation is applied to D, which turns the null stitch into a real stitch, now serving as a superordinate stitch for the source stitch that has been copied over from S.
• finally the source stitch is dropped from the destination needle using pop. The last two cycles may be merged into a single one by concatenating flip and pop into a single slip-stitch-over operation.

#### Twisted Stitches

To allow for variants of the knit stitch, such as purl, twisted knit and twisted purl, the orientation or twisting of the stitch must be part of its data structure.

To construct such stitches, we might either introduce left- and right-handed versions for elementary stitch operations such as push, depending on the side from which the needle enters the stitch.

Alternatively an isolated twist operation can be used, that only changes the orientation of the first stitch on the needle. While the first approach provides a more realistic model of the hand knitting process, the second approach may be preferred from an information processing point of view. In any case this is a matter of taste, since both systems are computationally equivalent.

### From Stich-OPs to Programs

So far I have introduced a lot of crazy analogies. You may consider some of them adventurous and daring, or you might even wonder why one would go as far as to break down a knitting-stitch into even smaller actions.

The reason is that once we have identified the atoms of the knitting process, we can use them as building-blocks for all kinds of hand-knitting stitches and knitting instructions.

And this is exactly what we will do in the third part of this series.

## Discussion

, 2013/08/15 21:01
Hello everyone!
Bitcraft Blog has been featured on BoingBoing :)

Unfortunately the discussion plugin was broken, so no one could really submit any comments.
I'm really sorry about that. Thanks to Jared Warren for pointing this out to me. Comments should now be working again.

http://www.k2g2.org/feed:bit.craft

@bitcraftlab or @bitcraftblog

, 2013/08/21 23:41
Computer scientist who knows nothing about knitting here. I personally prefer denotational semantics, so I'm finding your operational semantics a bit hard to follow. Have I got this right:

A stitch is modeled as a set of pointers to the stitches it holds together ("subordinates"). I'm guessing twisted stitches can be modeled as an ordering on the subordinate set? A "null stitch" is defined as a stitch with a null set of subordinates. (What does "the null stitch, which only contains references to is neighbors" mean?)

I don't understand why the needles need to be modeled as separate processors with structured registers unless there are cases where they're doing things in temporally indeterminate order. Would it work to model the needles as data structures or objects and model the human or machine doing the stitching as the processor implementing instructions? The basic operations would then be:

- allocate some free memory as a null stitch on top of a needle

- move a stitch from the top of one needle to another

- flip the top two stitches on a needle, which adds a pointer from the first stitch to the second stitch (the pointer can be added to either the front or the back of the pointer list to implement twists)

- drop the top stitch on a needle into the memory heap

- move a specified stitch from the memory heap onto a needle

(And variations of all those for the bottom of double-ended needles.)

I’m really looking forward to the rest of this project because I’ve always found knitting to be very mysterious. If you’re looking to make your model into a domain specific language I’d recommend checking out Haskell.
, 2013/08/22 16:44
j4warren: Knitter who knows nothing about computer science here. Sounds like you need someone to knit in front of you. Would volunteer, but live in France.
Joseph Knecht: thank you for this article, I just about made sense of it and am thrilled to now think of myself as a "Von Neumann knitter"
, 2013/08/24 13:07
Hi j4warren + Hélèe Wilkinson

This is really just a first sketchy attempt towards a computational model of knitting, so I'm pretty sure it won't live up to the scientific rigor a theoretical computer scientist would expect ;)
I haven't found the time to implement it, but I think Haskell might be a great choice. I would also like to churn out a Processing sketch at some time, since I think a visual representation of the knit-work, will make things much more clear.
There's also a project on SourceForge, dedicated to hand knitting that looks like a good start. It's called Knitter: http://sourceforge.net/p/knitter

Regarding Stitches and Pointers:

When knitting with a single thread all stitches are just loops that are arranged on a thread, so a data structure would have to represent the order of stitches. If this is done via pointers, every stitch has pointers to its predecessor and successor stitch. That's why the null-stitch, which is essentially just a non-loop has just those two pointers.

Regarding the CPU / Stitch-Processing Unit:

You are right. As long as you are single human knitter with just two needles, you could model the whole process using the human as the CPU. However there are cases where several needles are involved (like sock-knitting), and sometimes even several humans knitting in parallel
(See: http://weeklyweaves.blogspot.de/2013/05/forro-casino-human-knitting.html)
If we get to machine knitting you have thousands of needles processing stitches with no human involved at all. (Of course you might model the knitting cams as CPUs)
It's really just a design choice, but I decided to take the human out of the loop, because I think humans are really hard to model ;)

In the next post I will deal with individual knitting stitches based the computational model outlined above. In the meantime feel free to check out all the other crafty stuff on the k2g2 craftopedia. It's an open wiki on all aspects of computational craft. Feel free to contribute, if you got knowledge to share!
, 2013/09/02 01:08
This is great - I've been percolating about this for a long time. (A CS/software engineer who has been playing with knitting & other textile crafty things since I was 7ish.) Knitting and crocheting have fascinated me both in this sense (it's computational form), and also that things so beautiful and interesting can be made out of very simple, atomic items (a knit & purl stitch, simple crochet stitches).

For those unfamiliar with knitting and who are really visually oriented, TechKnitter [http://techknitting.blogspot.com/] has great illustrations on different knitting techniques. This may help some understand the basics. I'd suggest looking at her Unified index [http://techknitter.blogspot.com/2010/04/revised-unified-index-for.html], and specifically at the basic continential knit stitch http://techknitting.blogspot.com/2006/12/continental-knit-stitch_20.html to start. (Then you can look at Enlish style, and also at purl stitches -- all having to do with stitch orientation and formation.)

j4warren: Those graphics may help you understand things better. In addition to information about itself (orientation, etc), a stitch has TWO groups of information that it maintains:
(1) pointers to it's neighbors (ex: neighbor(s) preceding it, neighbor(s) after it; maybe others...),
and
(2) pointers to stitches it holds together.

When (2) is empty -- when this stitch does not hold any other stitches together, then this stitch is 'NULL' (it is a 'dropped' stitch in knitting terms). It may still have neighbors -- in fact, it usually does still have a neighbor stitch the precedes it, and one that comes after it. But it doesn't link or loop in any way to hold other stitches in the entire object. In real life, it's usually just a section of the yarn that is no longer looped in any way.

There are times when stitches are done 'non-sequentially' There are times when a knitter works with stitches that have already been completed, many rows down (in 'allocated memory' in the model above). The most common time this is done is with "short rows." Here are some schematics from TechKnitter: http://techknitting.blogspot.com/2009/10/short-rows-method.html

Creating 'cables' and twisted stitches is essentially working one or more stitches out of sequence on the same row. Here's a bit about that: http://www.knitty.com/ISSUEwinter07/FEATwin07TT.html

It's also done to create specific stitch patterns and patterns (picking up a stitch from many rows down will create a fold in the fabric.

That's all probably TMKI (Too Much Knitting Information), but I'm excited to see this all develop. I've often thought lots about using Processing to both show knitting visually and also use it as a way to show how a pattern (in the small, as in a 'stitch pattern,' or the large as in a garment) would look. And I've done extremely rudimentary things on my own so that I could see how different colors and/or striping patterns would look (e.g. different colors & striping on Zimmerman's classic Baby Suprise Jacket: http://www.ravelry.com/patterns/library/baby-surprise-jacket)

Looking forward to more!
, 2013/09/17 19:11
Good stuff! I like analogies between knitting and other things - I wrote one myself on how a (knitted) scarf is like a scientific dataset (http://citingbytes.blogspot.co.uk/2013/02/how-is-scarf-like-dataset.html)

I think there's a lot of crafts out there that can be used as models for other complicated things. But knitting is my favourite :-)
, 2014/04/10 23:13
I'm a computer scientist who wants to start computing via knitting! Is there a followup to this post and if so, where can I find it?
, 2017/01/13 11:34
Is there some kind of conditional operation? Like depending on the stitch in the previous row, use this or that operation now.

That would probably make knitting Turing complete, because then the program and input is the first row.