NYCJUG/2024-07-09
Beginner's regatta
Here we take a look at a proposed introduction to the talk "Using the J Language to Streamline Hacking" to be presented at the HOPE XV conference later this month.
Introduction to the J Programming Language for General Hacking
The J programming language is free, easy to use and very suitable for solving ad-hoc computer problems. It runs on Windows, Mac, Linux, Android, and Pi. I will start by providing some context about the importance of this language, followed by a basic introduction to some of its features. I will show a few simple examples of how useful it can be for a variety of tasks with an emphasis on using it to explore systems and work with code. We will look at steganography, as well as simple direct modification of an executable and other potentially useful topics.
Those Who Ignore the Past…
The roots of J extend back to the 1960s because it is directly descended from a language called APL which debuted in 1966. So why should we care about old stuff like this?
I will start by pointing out the news group “Forum on Risks to the Public in Computers and Related Systems”, also known as the “RISKS Digest” (see http://catless.ncl.ac.uk/Risks/ ) which has been publishing since 1985.
If you have followed this venerable news group, one of the recurring themes is how many well-known risks are commonly ignored in software projects over and over again. For instance, Microsoft had a leap-year bug as recently as a few years ago. It’s as if the computing profession deliberately ignores the lessons of the past, or it learns the wrong ones, but each new generation of programmers continues to make many of the same mistakes that previous generations have.
As blogger Scott Locklin puts it:
One of the problems with modern computer technology: programmers don’t learn from the great masters. There is such a thing as a Beethoven or Mozart of software design. Modern programmers seem more familiar with Lady Gaga. It’s not just a matter of taste and an appreciation for genius. It’s a matter of forgetting important things.
Tools of Thought
We will not address this larger issue directly but will instead focus on the particular issue of tools. The most concrete artifacts we have for software development are the tools we use. These are things like our editors, our IDEs, our programming languages. Narrowing our focus to a language we might use, I will introduce the J programming language, which, like its predecessor APL, is promoted as a tool of thought. This is one of those "old" concepts which seems be forgotten and re-discovered from time to time.
But why do we need tools and why do they matter?
Taking a bit of an esoteric detour here, let's look at this brief summary of the works of early nineteenth-century psychologist Lev Vygotsky talking about “tools of the mind”:
According to Vygotsky, until children learn to use mental tools, their learning is largely controlled by the environment; they attend only to the things that are brightest or loudest, and they can remember something only if has been repeated many times.
So, until we have mental tools for thinking about things - tools like abstraction, categorization, hierarchies, object relationships - we cannot reason.
Vigotsky goes on to say that after “…children master mental tools, they become in charge of their own learning, by attending and remembering in an intentional and purposeful way.”
We need mental tools because they help us think about problems. I hope to demonstrate how J is a useful tool by demonstrating how we might use it to play around with some interesting ideas. Specifically, we will see how we might implement steganography – which is hiding information in plain sight as it were – and how we can use J to explore and modify compiled code.
Basic J Features
J is an interpreted language so it is naturally used interactively: we enter a line of code and get an immediate result; often this result is an error. This is very useful for rapidly developing correct code because we partially debug each line as we get it to work correctly.
Two features of J that are most unlike most other languages is that J is symbolic and is evaluated right-to-left. J's symbols consist of one to four ASCII characters. This makes it very daunting to read at first until one becomes familiar with the symbol set. However, it also allows us to compress simple operations into very small expressions, allowing us to grasp more of the code at a single glance.
The right-to-left evaluation avoids needing to understand some hidden hierarchy of evaluation. Most people are familiar with this hierarchy for simple math operations, aka PEMDAS: we do exponentiation before multiplication and division which we do before addition and subtraction. However, this way of prioritizing evaluation quickly becomes unwieldy as we add more operations and has no obvious path toward generalization. It also complicates parsing.
The other top-level thing we need to understand is that most J symbols have both monadic and dyadic forms: they take either a right argument or both left and right arguments. Often the monadic case implies a default left argument. For instance, subtraction (-) used monadically is negation.
-2 3 4 _2 _3 _4 0-2 3 4 _2 _3 _4
We see that the monadic form of minus returns the same result as zero minus the right argument. Note J's use of the underscore character to denote the negative sign which distinguishes this from the minus sign's operation of negation.
We will note more specifics about the language as we work through our examples.
Show-and-tell
Here we look at an example of using J for computer science and some more of the HOPE XV J talk where we give some examples of using the language.
Teaching J/Computer Science: AP Computer Science
Slashdot reported on the AP Computer Science 2024 free response question 4:
High School AP CS A Exam Takers Struggled Again With Java Array Question
[Full text of the test question may be found in the last section.]
The problem stem has been posted by the College Board here:
https://apcentral.collegeboard.org/media/pdf/ap24-frq-comp-sci-a.pdf
The following was posted as a proposed solution done by an AP Computer Science Tutoring service, the link was provided in the Slashdot article:
apcomputersciencetutoring.com gridpath soulution
The author is Brandon Horn from the appearance of the website one of the instructors at apcomputersciencetutoring.com. He has a Bio at the page. The code from that site is reproduced here for educational purposes.
Mr. Horn's solution
To handle grid position, a class given in the set up of the question for which you had to write getNextLoc function
public Location getNextLoc(int row, int col)
{
Location belowLoc = new Location(row + 1, col);
Location rightLoc = new Location(row, col + 1);
if(row == grid.length - 1)
return rightLoc;
if(col == grid[0].length - 1)
return belowLoc;
if(grid[row + 1][col] < grid[row][col + 1])
return belowLoc;
else
return rightLoc;
}
The sumPath routine
public int sumPath(int row, int col)
{
int sum = grid[row][col];
Location loc = getNextLoc(row, col);
while(loc != null)
{
sum += grid[loc.getRow()][loc.getCol()];
if(loc.getRow() < grid.length - 1 ||
loc.getCol() < grid[0].length - 1)
loc = getNextLoc(loc.getRow(), loc.getCol());
else
loc = null;
}
return sum;
}
Now 2 replies to this solution posited recursive solutions to this problem. This is the first thing I thought of when I reviewed the problem before seeing any other solutions.
One solution was succinct by using object oriented dereferencing in place and not using temporary variables. The one chosen here is used because it's wrong just like the other solution, but it's easier to fix.
They're wrong because they fail to meet the preconditions of the problem (I admit on my attempt I too fell prey to the preconditions):
* Preconditions: row is a valid row index and col is a valid column index in grid. * row and col do not specify the element in the last row and last column of grid."
public int sumPathRec(int row, int col) {
if (row == grid.length-1 && col == grid[0].length-1) {
return grid[row][col];
}
else {
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
You should be able to see that this relies on providing the last cell coordinates as the base case. The college board seems to be forcing you away from this fairly elegant solution. I believe the correct recursive solution would be:
public int sumPathRec(int row, int col)
Location loc = getNextLoc(row, col);
int nextRow = loc.getRow();
int nextCol = loc.getCol();
if (nextRow == grid.length-1 && nextCol == grid[0].length-1) {
return grid[row][col] + grid[nextRow][nextCol];
}
else {
return grid[row][col] + sumPath(nextRow, nextCol);
}
}
I thought this would be a good example to implement in J as a way of teaching J and to further a more general discussion of teaching computer science.
NB. AP CS 2024 free response question 4
NB. redone in J without object oriented programming
NB. in the AP problem the grid is presumed to be given to you with parameters for size initialized in the object that defines it.
NB. in J it's a nice way to show how to use shuffle (dyadic ?) and shape ($) it into the grid we will need
makegrid =: 3 : 0
'm n'=. y
(m,n) $ (m*n) ? m*n
)
NB. so things won't run until I want them to I have an init routine
NB. it takes the grid row and column maximums you want and initializes grid, M = max rows, N = max columns
initproblem =: 3 : 0
'M N' =: y
grid =: makegrid M,N
)
NB. create a possible set of next locations
NB. in the case of this problem it will be the cell underneath
NB. and the cell to the right.
nxtlocs =: 1 0&+ ; 0 1&+
NB. must be a valid index and not go off the grid
NB. I assume there will be no negative numbers
NB. just make sure rows and columns are less than M,N
NB. constrain =: 3 : 'N&>@>./ y'
NB. my first cut at constrain I just used square grids
constrain =: 3 : '(M,N)&> each y'
NB. nxtloc - will return the location of the either the bottom or right neihbor
NB. depending on which location contains the smallest number
nxtloc =: 3 : 0
NB. get proposed set of possible grid locations
locs =. nxtlocs y
NB. keep only those locations that meet the constraints (ie. don't run off grid
locs =. (; *./each constrain locs) # locs
NB. for the grid locations that are left find the one with the smallest
NB. value in grid
((<./ locs { grid) = locs { grid)#locs
)
NB. return the full path through the grid
NB. precondition: y has valid row and column values. y can not be the coordinates of the last cell
path =: 3 : 0
NB. base case the next location coordinates are for the highest row and highest col
loc =. ;nxtloc y. NB. I return boxed coordinates when I didn't need to
if. *./ ((M-1),N-1) = loc do.
y;loc
return.
end.
(<y),path loc
)
sumPath =: {{ +/ x {~ path y }}
NB. sumPath =: {{ +/ (path y){grid }}
NB. run initproblem 12 9 for example to set up grid
NB. then the sum of the path is now easily obtained:
NB. +/ (path 3 4){grid
NB. will return the sum of the path starting at location 3 4
Here's the above code sans comments:
NB. AP CS 2024 free response question 4
NB. redone in J without object oriented programming
NB. no comment version except for this
makegrid =: 3 : 0
'm n'=. y
(m,n) $ (m*n) ? m*n
)
initproblem =: 3 : 0
'M N' =: y
grid =: makegrid M,N
)
nxtlocs =: 1 0&+ ; 0 1&+
constrain =: 3 : '(M,N)&> each y'
nxtloc =: 3 : 0
locs =. nxtlocs y
locs =. (; *./each constrain locs) # locs
((<./ locs { grid) = locs { grid)#locs
)
path =: 3 : 0
loc =. ;nxtloc y
if. *./ ((M-1),N-1) = loc do.
y;loc
return.
end.
(<y),path loc
)
sumPath =: {{ +/ x {~ path y }}
Handwriting a lost art
I hate to show my age but my Freshman year at college was the last year we had to use punch cards to write program. Sophomore year there were enough 3270 terminals to retire those monstrous dinosaurs. Getting on a punch card machine was tough. So when you finally got one you had to make sure the lion's share of your work was done. To do that you had to write your program out on paper by hand. You proofread the code a couple of times to make sure syntax was good and that the program seemed like it would do what it was supposed to. Then you sat at the machine typing in a line of code per card. Heaven help you if you ever dropped the cards on the ground on your way to the card reader.
Fast forward to the 21st century and my kids just jam in code to the IDE and run it. Then yell for me when it doesn't work.
When I ask, "what it is supposed to do?"
They pull up a PDF and say "this".
I ask if they printed the PDF out?
They give me a horrified look like no one prints stuff out. They get another horrified look because they know Dad's going to go into teaching mode.
They get up from the table just as I sit down and I ask "Where are they going?"
"I'm going to get a drink this seems like you are going to take a while"
When we finally get settled in for me to give them some help I find they have no hand written notes. There isn't single diagram they have put together. So I kind of have to start from scratch to show them how to design by hand so to speak. I have had 2 kids at 2 different schools and neither seem to require any handwritten documentation ever be done.
Even the teachers use slideware to teach the course so students don't even get to see someone else design on paper or a white board.
I have to wonder if this neglected form of designing software is partly why some students have trouble with programming. They aren't internalizing what the computer does, so every program is a mystery as to why it works.
This is also a place that J excels I can jot down a few lines of J and use it for a specification in any language I may be programming in. Its terseness takes away much of the drudgery of hand writing out code.
Recursion
Maybe it's me but I believe this is one of the single most important concepts you can teach to a new programmer. It not only exposes them to a powerful technique in programming it exposes them to the process of mathematical induction. Inductive reasoning is a useful tool for any student to have. AP CS Free Response Question 4 represents the antithesis of that process by seeming to deliberately steer students away from an elegant recursive solution, in favor of a brute force looping solution. The precondition for getNextLoc in the problem makes sense as there are no elements beyond the last cell and therefore no way to complete the logic needed without producing a memory leak. In the case of sumPath the precondition is arbitrary. Why can't I call sumPath with M-1,N-1 as the location. It should just return the value of the last cell. It also provides a more elegant solution in Java and a simpler recursive routine in J.
path =: 3 : 0 if. *./ ((M-1),N-1) = y do. <y return. end. (<y),path ;nxtlcoc y )
While this solution doesn't meet the preconditions. I believe it's a better solution. It has a cleaner look to it. There are no temporary variables used. Array languages have always had recursion and the language encourages recursive thinking. J even provides a self-reference operator ($:) so you can place recursion into your tacit programming. Here is the late Roger Hui's tacit quicksort definition as an example:
quicksort=: (($:@(<#[) , (=#[) , $:@(>#[)) ({~ ?@#)) ^: (1<#)
For those who might say recursion is inefficient and teaching looping code is more performance oriented. I would say that outside of teaching that recursive forms have a looping equivalent. The recursive form is a great specification for a generative AI program. I won't share the Java translation but perplexity.ai did a fine job of turning the Java based recursive program into a while loop. You can cut and paste the Java recursive definition into your favorite chatbot and see. What I will share is the stems for the Java translation and the stem and translation of the J recursive code into looping code. This was done at the perplexity.ai site.
Java code translation request stem:
can you translate the Java code delimited by '===' from its recursive form to loop form: === <paste java code here> ===
Now for the J code translation request:
Here is a similar recursive function written in the J programming language by jsoftware. It is a language in the category of array programming. Can you translate the recursive function (called a verb in J) into its loop based form. The verb (ie. function) is delimited by '==='.
=== path =: 3 : 0 if. *./ ((M-1),N-1) = y do. <y return. end. (<y),path ;nxtloc y )===
The results are pretty good (see below). The comments were added by perplexity.ai. You can see above I gave it uncommented code. The Java code I gave was for a combined sumPath routine. I only said similar I could have given a more detailed stem telling it I was saving all the coordinates of the path in J boxes. But it seems to have figured it out for itself.
path =: 3 : 0
result =. 0$0 NB. Initialize an empty list to store the path
current =. y NB. Start with the initial position
while. 1 do.
result =. result, <current NB. Append current position to result
if. *./ ((M-1),N-1) = current do.
break. NB. If we've reached the bottom-right corner, exit the loop
end.
current =. nxtloc current NB. Move to the next position
end.
result NB. Return the complete path
)
The Ah Ha! moment
Seeing the recursion in the solution to this problem is an Ah Ha! moment. Your brain sees it and there is intense satisfaction with it. Ruining that moment with arbitrary preconditions is taking the fun out of programming and probably losing a few students forever. The computer as a device is nit-picking enough on its own. Many new students find that alone annoying. If teachers and test creators add their own level of nit-picking how many more students are we chasing away. J takes the complete opposite approach. Most verbs return something. If you are trying to find the index of a particular integer in an array and it's not there J returns the size of the array as a signal it's not there. It doesn't immediately stop you most of the time. It returns some sort of an answer. The answer is usually useful in some way. In the indexing example it is returning the index of the number should you choose concatenate it to the end of the list.
Introduction to Steganography
I will skip the start of this part because it was covered at last month's meeting where we tried out a few different methods of hiding text in an image.
Regard the following as the next part of that presentation.
Hiding Low-Order Bits in 3D
We have made some progress but we still distort the image too obviously because we are replace complete pixels. What if we go down to the bit level?
Let's start by reading in the image and converting it to its 3D representation with the last dimension being the three RGB planes.
load '~Code/imageProcessing.ijs' NB. Basic image processing routines $gwok=. read_image 'GreatlyReducedGWoK.png' 226 330 $gwok=. rgb3 gwok NB. "rgb3" converts to and from the 3-plane representation. 226 330 3
Now let's convert the text we want to insert into binary.
$a. i. text NB. Convert letters to numbers. 1511 #:a. i. text NB. Convert numbers to binary representation. 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 ... $#:a. i. text NB. What is the shape of the binary table? 1511 7
Here we see that the characters are represented as 7-bit Booleans. This is because the monadic behavior of anti-base (#:) uses as few bits as necessary to encode the largest value and pads all the others to the same length with leading zeros. Notice that we already used anti-base in the rgb3 function.
rgb3
256 256 256&#:`(256&#.) @. (3 = [: {: $) (*.) 3 = [: # $
In this case, at the start of the line, we specify 256 256 256 as the left argument to anti-base to produce three digit base-256 numbers as the result when we are converting to the 3-plane representation.
Similarly, if we want to force our Boolean character encoding to be eight bits instead of seven, we need to override the default monadic behavior by explicitly specifying the left argument as eight 2s:
$(8$2)#:a. i. text NB. Encode characters as 8-bit Booleans 1511 8
Let's compare the size of the 3-plane image to the size of the Boolean table of text to be sure that the image is large enough to contain the text.
$,(8$2)#:a. i. text NB. How many bits? 12088 $,gwok NB. How many RGB pixels? 223740
This tells us we have plenty of room to embed the text using one bit of each RGB byte.
Let's turn the image into bits as well.
$(8$2)#:gwok 226 330 3 8 $,/,/(8$2)#:gwok NB. Flatten into (# of pixels) by (8 bits) table 223740 8
This next expression is kind of a doozy: it inserts the bits of text into the low-order bits of the Boolean table of the image and assigns the result to the variable newgwok.
$newgwok=. (,(8$2)#:a. i. text) (<"1]7,.~i.12088) } ,/,/(8$2)#:gwok 223740 8
You can see a couple of explicit values in this expression. The "7" targets the 7th (last) column of the bit table of the image and "12088" is the length of the text as an 8-bits per byte Boolean. We could generalize these but have not bothered for this specific example.
We write this altered image to a new file, reshaping it back to the shape of the original image on the fly:
(#.226 330 3 8$,newgwok) write_image 'newgwok.png'
The resulting image has no obvious artifacts:
In fact, a simple comparison of the old and new versions of the image shows them as apparently identical. I do this simple comparison by opening both images in a photo editor and XORing them together. This gives us an apparently completely black image indicating no differences between the two that we can see visually.
Reading the Hidden Text
Of course one of the most necessary things to do with a new piece of code is to test it. We do this by reading in the new file, turning it into an 8-column table of bits, reading in the last column of the table for the first 12,088 entries, and turning those bits back into characters.
$newgwok=. rgb3 read_image 'newgwok.png' NB. Image as RGB
226 330 3
$tt=. (<"1]7,.~i.12088){,/,/(8$2)#:newgwok NB. Bits of embedded text
12088
a.{~#._8]\tt NB. Take bits 8 at a time, convert these into numbers, then into characters.
Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.
Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place f...
But, in a larger sense, we can not dedicate -- we can not consecrate -- we can not hallow -- this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor l...
Abraham Lincoln
November 19, 1863
Generalizing the Extraction
One problem with this technique in general is that we would like to know how many bits we need to extract to build our text. We could simply convert the entire last bit column of the image and observe where the text becomes gobbledygook but this is a little crude and slower than it needs to be.
$tt=. 7{"1 ,/,/(8$2)#:newgwok NB. All bits of possible text
223740
a.{~#._8]\tt NB. Convert to 8 bit characters
Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.
Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place f...
But, in a larger sense, we can not dedicate -- we can not consecrate -- we can not hallow -- this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor l...
Abraham Lincoln
November 19, 1863
Pf # ┐ E � 5 ) t٦W `
C┌ f� R rz └ tHt ݢ?F│ �A ,<�X� [ 顆 %c/H iH"R\< ? p§T M 4&X�. : � q? 7 , T ,l� 0( |┘ g┴ZF qf/ ┴#:
if !^j ,#02 NO] 4├n │tR d . ؒHP v x┴Z │
...
The length of the extraction and conversion expression, with rgb3 inlined to remove an external dependency, is 112 bytes long.
'a.{~#._8]\(<"1]7,.~i.12088){,/,/(8$2)#:(256 256 256&#:`(256&#.)@.((3=[:{:$)(*.)3=[:#$)) read_image ''newgwok.png''' fappend 'newgwok.png'
112
This is short enough that we could stick the whole phrase on the end of our image but this has the same problem that we do not know in advance how long this expression will be for the general case.
What we can do is to also append this length as the last four bytes of the image after we've appended our extraction code in plain text. The four-byte representation of 112 in base-256 is
(4$256)#:112 0 0 0 112
If we establish the convention of using the last four bytes for this purpose, we can read in those bytes, convert them to a number, then extract that many bytes - plus these four - to give us the extraction code.
nn=. 4+#.a. i. fread 'newgwok.png';(4-~fsize 'newgwok.png'),4
nn
116
_4}.fread 'newgwok.png';(nn-~fsize 'newgwok.png'),nn NB. Read the last nn bytes and drop the last 4.
a.{~#._8]\(<"1]7,.~i.12088){,/,/(8$2)#:(256 256 256&#:`(256&#.)@.((3=[:{:$)(*.)3=[:#$)) read_image 'newgwok.png'
"._4}.fread 'newgwok.png';(nn-~fsize 'newgwok.png'),nn NB. Run these last nn-4 bytes
Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal.
Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place f...
But, in a larger sense, we can not dedicate -- we can not consecrate -- we can not hallow -- this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor l...
Abraham Lincoln
November 19, 1863
This concludes our steganography exercise. The things to notice are how easily and quickly I was able to try numerous different ideas and how easy it was to deal with the multi-dimensional array which was one of our intermediate results. This ease of use allows us to start with a very simple implementation and proceed to better, more complex versions.
Modifying Executables
This is a work in progress where I show how handy it is to be able to directly manipulate compiled code even with very little understanding of the complexity of the underlying executable.
Simple "For" Loop
I started with a very simple C program using a for loop.
// TestNew01.cpp : single "for" loop
#include <iostream>
int main()
{
for (int ii = 0; ii < 4; ii++) { std::cout << ii << "\n"; }
}
I compiled this using Microsoft's Visual Studio 2019 to produce the executable TestNew01.exe which works as one might expect.
>TestNew01 0 1 2 3
Now we make a version of this which differs only by the loop counter:
// TestNew02.cpp : single "for" loop with limit of 5
#include <iostream>
int main()
{
for (int ii = 0; ii < 5; ii++) { std::cout << ii << "\n"; }
}
This also works as expected:
>TestNew02 0 1 2 3 4
Let's read each executable and assign it to a variable in J:
'fl1 fl2'=. fread&.>'TestNew01.exe';'TestNew02.exe' #&.>fl1;fl2 +-----+-----+ |49152|49152| +-----+-----+
We have the two variables, each the same length.
fl1-:fl2 NB. They have the same length but are not identical. 0 +/fl1~:fl2 NB. How many bytes differ? 22 ]ixs=. I. fl1~:fl2 NB. Where is each difference? 232 6330 36064 36092 37196 37197 37198 37199 37200 37201 37202 37203 37204 37205 37206 37207 37208 37209 37210 37211 37252 37268
Notice that the last bunch of differences have consecutive indexes. Let's look at that group in each file.
(<4}.ixs){&.>fl1;fl2
+------------------+------------------+
| 3` ┤��A ┘?B11| ��� F h ┌'Q9�22|
+------------------+------------------+
This character representation does not tell us much so let's look at the values as numbers.
(<a.)i.&>(<4}.ixs){&.>fl1;fl2 NB. Compare values
193 51 96 174 21 27 1 65 144 24 243 169 157 145 63 66 49 49
204 2 2 4 176 144 226 70 140 104 197 16 39 81 57 14 50 5
This is not terribly illuminating either so let's look at only the first four differences.
(<4{.ixs){&.>fl1;fl2 NB. Compare only the first 4 differences
+----+----+
|����|d�dd|
+----+----+
(<a.)i.&>(<4{.ixs){&.>fl1;fl2 NB. Values of the first 4 differences
12 4 12 12
100 5 100 100
The interesting thing to note here is that the first file, with a loop limit of four, shows a "4" as the 2nd difference whereas the one with a loop counter of five shows a "5" in the same position. What happens if we change this single byte to a different value?
1{ixs NB. The position we want to modify
6330
fl3=. (9{a.) 6330 } fl1 NB. Replace with byte representing the number "9"
fl3 fwrite 'TestNew03.exe' NB. Write new file with this modification.
49152
What happens when we run this?
>TestNew03 0 1 2 3 4 5 6 7 8
It looks like we have modified the loop without recompiling the code.
Further Experiments with "For" Loops
Now that we know the purpose of a single byte in these executables, can we figure out which bytes denote the other parts of a "for" loop?
Let's look at the bytes next to the one we know about and see if anything jumps out.
]nbrs=. 6330+i:5 NB. Look at surrounding 5 bytes in each direction
6325 6326 6327 6328 6329 6330 6331 6332 6333 6334 6335
(<a.)i.&>(<nbrs){&.>fl1;fl2 NB. Values around the loop limit
69 248 131 125 248 4 125 41 104 48 155
69 248 131 125 248 5 125 41 104 48 155
How are these numbers around the known byte significant? Do they signal that we are in a "for" loop? Let's look at some different code to help us resolve this.
// TestMultiLoops1.cpp : multiple "for" loops
#include <iostream>
int main()
{
for (int ii = 0; ii < 2; ii++) { std::cout << ii << "\n"; }
for (int ii = 0; ii < 3; ii++) { std::cout << ii << "\n"; }
for (int ii = 0; ii < 4; ii++) { std::cout << ii << "\n"; }
for (int ii = 0; ii < 5; ii++) { std::cout << ii << "\n"; }
for (int ii = 0; ii < 6; ii++) { std::cout << ii << "\n"; }
}
Compiling this and reading in the resulting executable as a J variable, we see an immediate problem for comparing this with our other code: it has a different length.
#flm=. fread 'TestMultiLoops.exe'
49664
(<a.)i.&>(<nbrs){&.>fl1;fl2;flm NB. Values around the loop limit
69 248 131 125 248 4 125 41 104 48 155
69 248 131 125 248 5 125 41 104 48 155
69 248 131 125 248 2 125 41 104 48 155
<pre>
At least it looks like the first loop is in the same place since we see the value "2" of the first loop limit aligned with the loop limits from earlier.
Unfortunately, this new file differs in considerably more locations compared to the first two.
<pre>
+/fl1~:49152{.flm NB. How many bytes differ?
23477
I. fl1~:49152{.flm NB. How many bytes differ?
232 233 253 388 392 393 424 520 521 529 560 573 613 653 693 733 773 800 813 1030 1031 1035 1036 1040 1041 1045 1046 1050 1051 1055 1056 1060 1061 1065 1066 1070 1071 1075 1076 1080 1081 1085 1086 1090 1091 1105 1106 1110 1111 1115 1116 1120 1121 1125 1126 ...
ixs
232 6330 36064 36092 37196 37197 37198 37199 37200 37201 37202 37203 37204 37205 37206 37207 37208 37209 37210 37211 37252 37268
Comparing the new difference locations with the previous ones, we see some similarity at first but they quickly diverge.
What if we search for the byte patterns around the known loop limit location?
+/(131 125 248{a.) E. flm
3
+/(131 125{a.) E. flm
33
+/(248 131 125 248{a.) E. flm
3
Having three hits is not as exciting as it would be to have five hits because the new code has five loops. Another sequence is not much better.
+/(125 41 104 48{a.) E. flm
4
Advanced topics
Taking a brief look at a couple of papers: one makes the case that programming is over 90% thinking while the second one re-enforces the results of the study we looked at last week casting doubt on the links between language use and programming
Programming is Mostly Thinking
This blog posits that programming is mostly thinking, something most programmers will find unsurprising. Of course this will not stop management from trying to monitor programming productivity based on things like the number of keystrokes and the lines of code a programmer produces.
However, the more interesting part of this is the author's quantification of programming as 11/12ths thinking.
The essay starts with a hypothetical scenario where yesterday was a very productive day where you were able to spend the entire day programming without interruptions of any kind. However, in this scenario, today you discover that all your work from yesterday has been lost. The question is, how long should it take you to re-create the work you spent the better part of a day doing? As the author states it: "If I give you the diff, how long will it take you to type the changes back into the code base and recover your six-hours' work?" Here "diff" means a listing of all the changes made, perhaps captured in some sort of change log from yesterday that was not lost.
The author answers the question based on interviews with programmers.
I have asked this question at conventions, client companies, to my peers, to colleagues, and to strangers I have met for the first time when I find out they are programmers.
The answer I receive most often is "about half an hour."
I could use the 8-hour day, ignoring meetings and interruptions and status reports, but that feels like padding the answer. I stick to the six hours doing things that programmers identify as programming work.
There are twelve half-hours in six hours. One half-hour to retype all the changes made in six hours of hard programming work.
What in the world can that mean? How can it be so little?
What Do Programmers Do All Day?
Elaborating on the reasons for this discrepancy, the author notes
- Those 30 minutes are to recreate the net result of all the work they wrote, un-wrote, edited, and reworked through the day. It is not all the effort they put in, it is only the residue of the effort.
- Programmers are avoiding defects as best they can...[by] continuously evaluating the code as they write it, hypothesizing the kinds of defects or security vulnerabilities they might be introducing.
- Most of the work is not in making the change, but in deciding how to make the change. Deciding requires us to understand the code that already exists.
- There are social aspects of coding which require communications between team members but does not show up as finished code.
The author concludes "Six hours of intellectual work (reading, researching, deciding, confirming, validating, verifying) translates to about 30 minutes worth of net lines-of-code change to a code base." This is where the 11/12ths number comes from (1/2 hour versus 6 hours).
This leads to a conclusion about where we should place our priorities.
If programming is 1/12th motion and 11/12ths thinking, then we shouldn't push people to be typing 11/12ths of the time. We should instead provide the materials, environment, and processes necessary to ensure that the thinking we do is of high quality.
Doing otherwise is optimizing the system for the wrong effect.
So, if programming is mostly thinking, maybe what we really need are tools to help us think.
Language Primarily a Tool for Communication, not Thought
Tangentially related to this is the conclusion of this paper titled "Language is primarily a tool for communication rather than thought".
Among the interesting points of this paper is a summary of the major claims about the relation between language and thought. They authors point out that some of the stronger claims, like "all forms of thought require linguistic representations", are the easiest to disprove.
In a side-bar on claims about language and thought, the authors affirm this:
It seems clear that we can use language to compress analogue signals into symbolic representations (for example, reducing a visual array of nine objects to ‘nine’183; see ref. 173 for a recent proposal on the role of information compression in human thinking). However, these representations need not be specifically linguistic: they could be symbolic but non-linguistic (for example, ‘9’), and the use of symbolic non-linguistic representations does not engage linguistic resources (for example, mathematical reasoning elicits no response in the language brain areas and is preserved in individuals with severe aphasia).
The references given here provide further information about these issues which may be relevant to the notion of a notation being a "tool of thought".
The paper also provides an illustration of which areas of the brain have been shown to correspond to different language-related mental faculties.
This article covers a lot of ground and provides a good summary of where current thinking is about language and thought.
Materials
The AP Computer Science question referred to is the following:
4. This question involves a path through a two-dimensional (2D) array of integers, where the path is based on the values of elements in the array. When an element of the 2D array is accessed, the first index is used to specify the row and the second index is used to specify the column. The following Location class represents a row and column position in the 2D array.
public class Location { private int theRow; private int theCol; public Location(int r, int c) { theRow = r; theCol = c; } public int getRow() { return theRow; } public int getCol() { return theCol; } }The following GridPath class contains the 2D array and methods to use to determine a path through the array. You will write two methods of the GridPath class.
public class GridPath { /** Initialized in the constructor with distinct values that never change */ private int[][] grid; /** * Returns the Location representing a neighbor of the grid element at row and col, * as described in part (a) * Preconditions: row is a valid row index and col is a valid column index in grid. * row and col do not specify the element in the last row and last column of grid. */ public Location getNextLoc(int row, int col) { /* to be implemented in part (a) */ } /** * Computes and returns the sum of all values on a path through grid, as described in * part (b) * Preconditions: row is a valid row index and col is a valid column index in grid. * row and col do not specify the element in the last row and last column of grid. */ public int sumPath(int row, int col) { /* to be implemented in part (b) */ } // There may be instance variables, constructors, and methods that are not shown. }(a) Write the getNextLoc method, which returns a Location object that represents the smaller of two neighbors of the grid element at row and col, according to the following rules.
- The two neighbors that are considered are the element below the given element and the element to the right of the given element, if they exist.
- If both neighbors exist, the Location of the neighbor with the smaller value is returned. Two neighbors will always have different values.
- If only one neighbor exists, the Location of the existing neighbor is returned. For example, assume that grid contains the following values.
The following table shows some sample calls to getNextLoc.
Method Call Explanation getNextLoc(0, 0) Returns the neighbor to the right (the Location representing the element at row 0 and column 1), since 3 < 11 getNextLoc(1, 3) Returns the neighbor below (the Location representing the element at row 2 and column 3), since 15 < 16 getNextLoc(2, 4) Returns the neighbor below (the Location representing the element at row 3 and column 4), since the given element has no neighbor to the right getNextLoc(4, 3) Returns the neighbor to the right (the Location representing the element at row 4 and column 4), since the given element has no neighbor below In the example, the getNextLoc method will never be called with row 4 and column 4, as those values would violate the precondition of the method.
Complete the getNextLoc method.
/**
* Returns the Location representing a neighbor of the grid element at row and col,
* as described in part (a)
* Preconditions: row is a valid row index and col is a valid column index in grid.
* row and col do not specify the element in the last row and last column of grid.
*/
public Location getNextLoc(int row, int col)
Begin your response at the top of a new page in the separate Free Response booklet and fill in the appropriate circle at the top of each page to indicate the question number. If there are multiple parts to this question, write the part letter with your response.
Class information for this question
public class Location private int theRow private int theCol public Location(int r, int c) public int getRow() public int getCol() public class GridPath private int[][] grid public Location getNextLoc(int row, int col) public int sumPath(int row, int col)(b) Write the sumPath method, which returns the sum of all values on a path in grid. The path begins with the element at row and col and is determined by successive calls to getNextLoc. The path ends when the element in the last row and the last column of grid is reached. For example, consider the following contents of grid. The shaded elements of grid represent the values on the path that results from the method call sumPath(1, 1). The method call returns 19 because 3 + 1 + 2 + 1 + 9 + 1 + 4 + 1 + 0 + 1 + 1 + 5 = 19.
Write the sumPath method. Assume getNextLoc works as intended, regardless of what you wrote in part (a). You must use getNextLoc appropriately in order to receive full credit.
/** * Computes and returns the sum of all values on a path through grid, as described in * part (b) * Preconditions: row is a valid row index and col is a valid column index in grid. * row and col do not specify the element in the last row and last column of grid. */ public int sumPath(int row, int col)Begin your response at the top of a new page in the separate Free Response booklet and fill in the appropriate circle at the top of each page to indicate the question number. If there are multiple parts to this question, write the part letter with your response.
Class information for this question
public class Location private int theRow private int theCol public Location(int r, int c) public int getRow() public int getCol() public class GridPath private int[][] grid public Location getNextLoc(int row, int col) public int sumPath(int row, int col)
