Knitting Computer Style

In my usual blog travels (which, maybe surprisingly, usually have nothing to do with yarn craft), I came across a link to an article on how the process of knitting can be described using computational concepts.  Which, while rather technical, is pretty brilliant.  Or maybe it's brilliant because it's technical. Anyway, there's a couple of concepts here that I'm just in love with, and that, now I've read them, are completely obvious to me.  My favorite one is idea of the working stitches acting like a stack or a dequeue.  I think it's a good way of looking at the knitting process rather differently, and they do work pretty well as a metaphor.

On the other hand, she brings memory and storage concepts into it to explain the yarn and completed fabric parts to go with the stack/dequeue metaphor, which is completely valid and it does complete the metaphor [1].  However, the more I  think about it, the more I think that there's another way to extend the metaphor.  We can just treat all the stitches in the knitted piece, on the needles and in the fabric, as a linked stack and linked queue.

What's a linked stack, you say?[2] Well, a linked stack is a stack that is implemented with a linked list.  Ditto with linked queue. A linked list is a data structure that involves nodes (treat this as black box objects for now, I'll get to it later) that contain pointers pointing to the next node.  The Wikipedia link for linked list has the normal representation of such an object, but for the sake of not breaking out a drawing program, I'm going to write them like this: {1} -> {2} -> {3}, where the -> symbol represents the pointer.

The thing with a linked list is that you can easily traverse the list; each node will lead to the next one.  They are connected objects.  Also, unlike what you see above, the object in the list doesn't just have to be a number.  It can be any data object...such as a custom structure.  I'll get to this a little later, but for now the class looks like this:

struct myObject
{
      int Value;
      myObject *next; (this is the pointer to the next object)
}

Or, in my drawings, like this: {1} ->

Now, a stack is an data structure that is built to only allow two main operations on each object in the stack: you may push an object onto the stack or you may pop the item off the stack.  This causes the stack to implement what they call Last-In, First-Out (LIFO) data processing.  For example, think of coasters in a holder. The holder acts like the stack storage object, and the coasters themselves are the objects.  If all the coasters are outside the holder (say you had a party and they're now in places you'd never think to look, like behind the toilet), the stack is empty. You don't think coasters should be behind the toilet, and you need to sit down somewhere, so you push three of the coasters back in their holder. 

Then you decide that you need a cup of coffee, and you should use a coaster because while your place is trashed already, someone definitely spilled beer on your coffee table, and you don't want your coffee cup to stick to it.  So you 'pop' the only coaster you can grab in the holder: the one you last put in.

(Then you say screw it; I'm too hung over for this shit and go back to bed.  But you come back, like you always do. Anyway...)

Now, how does this fit in with a linked list?  Well, we use a linked list to represent the actual stack.  First, though, we need an object that points to the top object in the stack.  Let's call it topItem, and it'll be represented like this: {topItem}

That's the coaster holder.  Now, I push three items to the stack by creating the first node ({1}), and assigning topItem the pointer to that node:

{topItem} -> {1}

{1}'s pointer is null, since there's no object before it.  I then create the second node ({2}), assign the value of topItem as {2}'s pointer so it's linked to {1}, and then point topItem to {2}:

{topItem} -> {2} -> {1}

 Repeat for {3} and:

{topItem} -> {3} -> {2} -> {1}

If I want to pop the last one, I just access the topItem pointer, which is pointing to {3}, take that object, and then re-assign topItem to the same value as the pointer in {3}:

{topItem} -> {2} -> {1}

That's the basic idea of a linked stack.

A queue, on the other hand, works via a First-In, First-Out (FIFO) methodology instead.  The first object you push in (enqueue the object) is 'popped' on the other end of the list (dequeue the object).  This is implemented using a linked list by creating another object to point to the last object in the list. We'll call it lastItem ({lastItem}).

Now I enqueue an object:

{topItem} -> {1} <- {lastItem}

Since there's only one object, both top and last item have the same pointer value.  Now I enqueue another one:

{topItem} -> {2} -> {1} <- {lastItem}

You get the point.

So how does this fit with knitting?  Well, let's create another structure called Stitch:

struct Stitch
{
      int stitchID;
      int baseStitchID;
      Stitch *next;
}

This, as you could guess, represents one 'knit' stitch.  Now, it would have more properties in the real world, but we're going to stick with this for now.  We'll now represent this structure like so: {id, base} ->

Now it's time to knit.  We get our resource pool (the yarn) and our needles.  The needles will represent the stack/queue, and the point of our needles will be the top and last items, depending on how we knit.  However, since right now there's no stitches, we have to start with the right needle representing the stack only, and the left will be pointing to the top. So, let's cast on 5 stitches:

{topStitch} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0}

The baseStitch is 0 because this is the cast on edge.

We want to knit straight, so we need to use the linked stack structure. Now the right needle becomes the left, and the right point is pointing to our top stitch.  Now we knit by creating the next stitch object with the next ID number (6) and popping the last stich on the stack to first get the baseStitch:

Stitch newStitch = {6, 5}

{topStitch} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0}

Now, he pointer of stitch 6 must be assigned the pointer value of topStitch, and topStitch now should be assigned to the new stitch, since stitch 6 is connected via the yarn path to stitch 5.  We now push both 5 and 6 back onto the stack (though in the needle world, it's now split between two needles and the fabric).  It now looks like this:

 {topStitch} -> {6, 5} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0}

We knit the rest of the row.  Now all the live stitches are on the right needle, and there's a row of knitted fabric below.  However, the stack repersentation will look like this:

{topStitch} -> {10, 1} -> {9, 2} -> {8, 3} -> {7, 4} -> {6, 5} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0}

You can tell by the baseStitch value what loop we've drawn the active loop through, but as like real knitting, we can't just jump to that base stitch. The pointers here are representing the path of the yarn.  For example, say if we screwed up and needed 6 stitches in the fabric below, we would have to pop stitches 10 to 6 (and lose them in the process since we can only save one temporarily when we're working with it), and push the new object {6, 0} to point to the right stitch.

On the other hand, to work in the round, we need to be able to 'pop' off the first stitch as well so we can get the value of the baseStitch for the new stitch.  We can't 'pop' the first stitch, but if we use lastItem (now lastStitch), we can dequeue it.  So let's go back to our cast-on:

{topStitch} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0}

Since the needles are somehow connected, one active needle point is topStitch, and the other has been created as lastStitch:

{topStitch} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0} <- {lastStitch}

Now we knit the next stitch, which happens to be the first one in the queue.  So, we first create a new stitch by dequeuing the lastStitch to get the baseStitch, but using topStitch to get the next ID:

Stitch newStitch = {6, 1}

{topStitch} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0} <- {lastStitch}

We now do the same steps as the stack: assign the new stitch the pointer value of topStitch, and topStitch the pointer to the new one, and enqueue the new stitch:

 {topStitch} -> {6, 1} -> {5, 0} -> {4, 0} -> {3, 0} -> {2, 0} -> {1, 0} <- {lastStitch}

However, now the last stitch is the second to last one in the queue, so it needs to point to that one.  This is the one point where we hit a pitfall with this implementation.  To get the new lastStitch, we have to go through the whole queue to get the pointer value of stitch 3, since we can only follow the yarn:

{topStitch} ->	{6, 1} ->	{5, 0} ->	{4, 0} ->	{3, 0} ->	{2, 0} ->	{1, 0}
					^
					|
					{lastStitch}

This, of course, is why the author used an array-based dequeue instead.  It avoids this pitfall, and you could still implement a restriction for the knitting/tinking action to only use topStitch via a knitting class that implements a special case of the dequeue.

There are other pitfalls with this idea in terms of computational use that make this method a bad idea in the real world.  It's nowhere near the most efficient way, as you would eat a lot of memory storing a sweater's worth of stitch nodes like this.  Having the ability to more quickly call up the node doesn't offset this as knitters (usually, ha) don't tink most of their stitches, and so they most likely won't be accessed again (ripping it all out would be akin to deleting the stack/queue).  But while the author may be building towards modeling the act of knitting on a computer and is concerned about these things, I'm just using technical metaphors and this way allows more simplistic operations and an interesting parallel to how the yarn actually flows.  Metaphorical computers have infinite memory and processing power.

Well, mine does at least.

******************************************************************************
[1]:  I am nowhere near as smart or learned than the author of the article and maybe even you.  So this and most likely the rest of this post may be a bit presumptuous of me.  I'm just a high-level language using programmer who has an undergraduate degree in computer science and likes to build stupid, simple, shit.  Theory was never my forte. 

[2]: While I'm linking to Wikipedia, I actually got my old data structures textbook out for reference.  It's called ADT's, Data Structures, and Problem Solving with C++. by Larry Nyhoff.  I have the Second Edition, which is most likely old now in textbook years.  Stacks can be found staring on page 315 (Chapter 7) , linked stacks starting on page 353 (Chapter 7, Section 3), and linked queues starting on page 413 (Chapter 8, Section 3).