This assignment uses Prolog and the biductive computing paradigm to allow a user to translate simple knitting patterns into diagrams and vice versa. Prolog naturally supports parsing context-free and context-sensitive grammars using definite clause grammars (DCGs).
This assignment only handles simple knitting patterns. Here is an example pattern:
k4, p6.
k1, p1, * k2, p2; rep from * 2 times.
k7, p3.
k9, p1.
Each line is a row of stitching. “kN” means “knit N times,” while “pN” means purl N times. An asterisk indicates the start of a repeated knit/purl sequence, and the phrase “rep from * N times” repeats that phrase N times. The resulting diagram would be the following:
[[k,k,k,k,p,p,p,p,p,p],
[p,p,k,k,p,p,k,k,p,k],
[k,k,k,k,k,k,k,p,p,p],
[p,k,k,k,k,k,k,k,k,k]]
This Prolog notation (a list of lists) could be trivially translated into a grid image with white cells indicating knits and gray cells indicating purls. Note that every other row, starting from the second, must be reversed from the pattern described in the text since the knitted piece must be turned around after each row is completed and the yarn is at the other side from which it began the prior row.
Your implementation must prevent patterns like, “k1, k1, k1”, which should be written “k3” instead, perhaps by forcing alternation among “k” and “p” segments. You may restrict the length of the number of stitches (knits or purls) on a single row to 20 to ensure patterns are not arbitrarily long.
In a deductive use case, we can generate the diagram from a pattern string:
diagramPattern(Diagram, "k3, p13.\np4, * k2, p2; rep from * 3 times.\n").
The result is a list of lists representing a diagram:
[[k,k,k,p,p,p,p,p,p,p,p,p,p,p,p,p],
[p,p,k,k,p,p,k,k,p,p,k,k,p,p,p,p]]
We may also use the parser abductively, i.e., generating a pattern string from a diagram.
diagramPattern([[k,k,k,p,p,p,p,p,p,p,p,p,p,p,p,p],
[p,p,k,k,p,p,k,k,p,p,k,k,p,p,p,p]], Pattern).
There are multiple pattern strings that translate to this diagram. Here are a few that should be generated by your implementation:
k3, p13.
p4, k2, p2, k2, p2, k2, p2.
p4, * k2, p2; rep from * 3 times.
We may use Prolog to its full biductive potential and ask the parser to fill in the rest of both the pattern and corresponding diagram. For example, we can constrain the pattern string to start “k3, p” on the first row and end “k2, p2.” on the second row. We will also constrain the diagram so the first row starts [k,k,...] and the second row has a gap in the middle: [p,p,k,k,p,p,...,p,p,p,p].
Row1 = [k,k|RestRow1],
append([p,p,k,k,p,p|MiddleRow2], [p,p,p,p], Row2),
append(["k3, p",MiddlePattern,"k2, p2.\n"], Pattern),
diagramPattern([Row1,Row2], Pattern).
One result finishes the first row of the diagram with k followed by p, the gap of the second row is empty (no gap), and the resulting string is “k3, p1” for row 1 and “p6, k2, p2” for row 2. The biductive use case enables a knitter to generate various alternatives for completing a piece while maintaining specific constraints such as the knit pattern at the edges of the piece. The diagram and pattern string are generated together so the constraints may be specified in the string or diagram or both.
Take note that biductive parsing can easily lead to deep recursive search and stack overflows. It is important to constrain the grammar in a manner shown in our background notes. Also consider using a "tabling" library for Prolog to cache results during the search.
A series of test cases are given in knit_tests.pl. Run the test cases with this command:
swipl --traditional -q -s knit_tests.pl -t run_tests
If the tests pass, you should see only some dots (1 dot per test) and no error or warning messages.
Submit your knit.pl file. Include the file knit_tests.pl as well, even though you do not need to modify it.
Real knitting patterns are significantly more complex than those handled in this assignment. A natural extension is to support more pattern features, such as colors and other kinds of stitches like slip stitches and cast on / bind off.