NYCJUG/2009-08-11

From J Wiki
Jump to: navigation, search

NYCJUG meeting, trees, walk directory tree, advantage of terseness, brevity, BAPLA'09, supercollider, Computer Science education, mathematics


Meeting Agenda for NYC JUG 20090811

1. Beginner's regatta: a simple recursive adverb to walk a directory tree,
applying an arbitrary verb at each node - see "Walk Directory Tree.doc".


2. Show-and-tell: some comments on the BAPLA'09 conference and an excerpt
from my talk there - see "Terser is Better.doc".  Also, a counterpoint to
this - see "Terse Confusion.doc".


3. Advanced topics: amending boxed arrays (Thomas) - see "Item Amend_Amend
and Merge.doc" and "Mapped Boxed Arrays.doc".


4. Learning, teaching and promoting J: continuing difficulties in Computer
Science education - see "US Computer Science Heading in Wrong Direction.doc",
"WhyCSDoesn'tMatter.doc" and "Are We Losing Our Ability to Think Critically.doc".

A look at another language - SuperCollider - and some ideas about extending it
with concepts from J - see "J Concepts in SC.doc" et al.

Proceedings

We talked a lot about trees, both in the context of walking a directory tree and more generally in the context of generalized updating of a deeply-nested boxed array. We also discussed the arguments both for and against terse notation. We discussed briefly the spotty relation between skills and education in programming versus mathematics. Finally, we looked at a sound-synthesis language that has been explicitly influenced by J.

Beginner's Regatta: Walk Directory Tree

from	 Devon McCormick <devonmcc@gmail.com>
date	 Fri, Jul 17, 2009 at 6:27 PM
subject Climbing a tree

Members of the Forum -

I've recently been playing with a useful utility I'm calling "climb" because it climbs a directory tree, doing something at each node. This "doing something" is user-specifiable, so this naturally lends itself to an adverbial construction, to whit:

climb=: 1 : 0
   svdir=. 1!:43 ''
   1!:44 svdir [ rr=. u y [ 1!:44 y
   subds=. ((('d'e.&>4{"1])#0{"1])@:(1!:0@<)) y,'\*.*' NB. Only subdir names
   if. 0~:#subds do. rr=. rr;(u climb)&.>(<y,'\'),&.>subds end.
)

The only very complicated line is the one assigning the subdirectory variable "subds". I had originally written this

   subds=. jd dir y,'\*.*' NB. Only subdir names

but have since substituted the definitions for "jd" (just directories) and "dir" since this makes the function self-contained.

I'm interested in comments on a couple of design choices. First of all, is the name good? The more normal terminology has one "walk" a directory tree. In fact, the Rosetta code page "Walk Directory Tree" (http://rosettacode.org/mw/index.php?title=Walk_Directory_Tree) presents an application of this code though the problem statement is poorly worded. It states that this algorithm will "[w]alk a given directory tree and print files matching a given pattern" when it apparently means not "print files" but "display file information", based on the submissions.

Of course, the J function here is more general as it allows one to do anything while climbing the tree.

Another design choice has us changing directories to run the supplied verb but it's not clear this is really necessary.

Yet another choice is to make this recursive in order to simplify the logic. However, if we were to handle the sub-directory navigation more explicitly, this opens up the possibility of being able to specify either "depth-first" or "breadth-first" processing of the tree rather than the implicit "depth-first" approach of recursion.

Finally, when I first attempted to use this to list files matching a certain pattern, I had an initial problem specifying my verb. My first attempt,

   aa=. (dir&'*Bis-B*.csv') climb 'C:\amisc'

failed. When I examined the behavior of my verb - which intentionally ignores the default argument inside "climb" of the current directory path - I found this:

   (dir&'*Bis-B*.csv') 'C:\amisc'
|length error: dir
|       (dir&'*Bis-B*.csv')''

Playing around with some variations led me to this

aa=. ((dir@:])&'*Bis-B*.csv') climb 'C:\amisc'

which worked fine but I'm not clear on why my initial attempt to bind the right argument of "dir" fails.

In any case, this is a useful utility that offers some room for improvement but I've already used it successfully in a couple of different ways.


from	Devon McCormick <devonmcc@gmail.com>
date	Sun, Jul 19, 2009 at 2:04 PM

On Sun, Jul 19, 2009 at 1:47 PM, Zsbán Ambrus <ambrus@math.bme.hu> wrote:

...
I think it's called _descending_ a directory tree because computer
scientists have their trees upside down.  Or just call it find.

> However, if we were to handle the sub-directory navigation more
> explicitly, this opens up the possibility of being able to specify either
> "depth-first" or "breadth-first" processing of the tree rather than the
> implicit "depth-first" approach of recursion.
The term "depth-first" also implies a tree growing downward.

Ambrus

These are good points. However, coming from the APL/J world, I've always felt little incentive to observe computer "science" tradition in the cases where it seems backwards, like upside-down trees. At the same time, I'd like to strike a balance as it's an ongoing problem with J that we use a different vocabulary than most everyone else and this presents a non-essential barrier to entry.

So, on the basis of spurning mistaken tradition, I would prefer "climb" to "descend". The word "find" is perhaps too broad though my "climb" is very much like the Unix "find", so that's maybe the way to go.


Bjorn chided me for incompleteness –


from	 Björn Helgason <gosinn@gmail.com>
date	 Fri, Jul 24, 2009 at 4:13 AM

When I a wanted to try out your interesting example here I discovered that it needed a bit more to run.

To begin with, the dir command is missing

require'dir'

Then a simple example

  aa=.dir climb 'C:\j601'

And something to display the results

  ,.aa

So like this to start with

require'dir'

climb=: 1 : 0
 svdir=. 1!:43 ''
 1!:44 svdir [ rr=. u y [ 1!:44 y
 subds=. ((('d'e.&>4{"1])#0{"1])@:(1!:0@<)) y,'\*.*' NB. Only subdir names
 if. 0~:#subds do. rr=. rr;(u climb)&.>(<y,'\'),&.>subds end.
)
  aa=.dir climb 'C:\j601'
  $aa
5
  $ &.> aa
+-----+-+-+-+-+
|25 54|5|6|2|6|
+-----+-+-+-+-+

  ,.aa

The results from the example is still a bit complicated for a beginner I guess but it sure looks interesting.


I re-worked the function based on experimenting with its use. The final version is more well-commented and has a line at the end with a usage example. Also, I changed the order to extract the sub-directory names before applying the verb so that those names are available to it.

NB.* walkDirTree: walk directory tree performing "u y" at each node where
NB. "y" is current directory name.
walkDirTree=: 1 : 0
   subds=. ((('d'e.&>4{"1])#0{"1])@:(1!:0@<)) y,'\*' NB. Only subdir names
   rr=. u y    NB. Do it in current, then look to subdirs
   if. 0~:#subds do. rr=. rr;(u walkDirTree)&.>(<y,'\'),&.>subds end.
NB.EG ] walkDirTree 'C:\Temp'
)

My experiments revealed some interesting behavior: apparently the operating system (Windows XP) caches the result of a directory sweep on a local drive, so subsequent sweeps run much more quickly. The following screenshots illustrate this.

Some Apparent OS Caching on Local Drives When Walking Directory Tree

Here we see how the initial run takes almost 563 seconds but incurs no obvious system load (as shown by the Process Explorer information on the right.)

WalkDirTiming00.png

However, a subsequent run, even in a separate J session, completes in about five seconds.

WalkDirTiming10.png

This behavior does not appear to extend to network drives: drive “E:” shown here.

This display shows an “.ijx” window on top and a jee session running under emacs below.

All timings take over 300 seconds when sweeping the network drive.

WalkDirTiming30.png

Final Version

In the meeting, Thomas pointed out how I could simplify the code by getting rid of the "if" statement and simply applying the recursion to any subdirectories found - if there are none, the function returns an empty result. This gives us what I now consider to be my final version:

NB.* walkDirTree: walk directory tree performing "u y" at each node where
NB. "y" is current directory name.
walkDirTree=: 1 : 0
   subds=. ((('d'e.&>4{"1])#0{"1])@:(1!:0@<)) y,'\*' NB. Only subdir names
   rr=. u y    NB. Do it in current, then look to subdirs
   rr=. (<rr),(u walkDirTree)&.>subds ([,~&.>[:<'\',~]) y
)

I obtain the subdirectories prior to invoking the user-supplied function with the idea of having that information available to the invocation.

Show-and-tell

When I put together my talk on J for the BAPLA'09 conference (videos here), I was initially daunted by the prospect of filling up forty minutes, so I pulled in a lot of material. However, once I was in the midst of the talk, I realized that I had far too much material and had to skip and minimize certain sections. It was like my one talk was two or three talks jammed together.

This is an attempt to extract one of those two or three talks into a stand-alone topic: the argument in favor of terseness. What follows are my slides with a little commentary sandwiched between each.

Terser is Better

Here’s a very simple problem with a very simple solution – why shouldn’t the code reflect this simplicity?

MusingOnJ TerserIsBetter001.jpg


The common view is that less code is less legible. Meanwhile, people typically emphasize parts of their solution that are irrelevant, like thread-safety and parallelizability: how are high-performance, heavy-duty concepts like these relevant to such a trivial problem?

Along the same lines, how is “only 44 lines of code” in any way commensurate with this simple problem? That is a lot of code for a very trivial algorithm.

MusingOnJ TerserIsBetter002.jpg


This equation of terseness to unreadability is common even where we should know better – in the APL community! We should turn this argument around: why is a page of baby-talk better than a few lines of concise, high-level, well-articulated expression?

MusingOnJ TerserIsBetter003.jpg


Even though the APL and J solutions are superficially different, they are actually very similar. We can even line up the single line solution from each language to see how they both do the same things in the same order. Here we see them lined up with the same part of each line doing essentially the same thing.

MusingOnJ TerserIsBetter004.jpg


Having a succinct solution allows us more flexibility to play with variants and discover potentially useful generalizations. This is something we see APL people do quite frequently: present a simple, succinct solution, then play with it to explore the boundaries of the solution and how it might be generalized. You don't have time for this once you've labored to put together many pages of code like you would in most conventional languages.

MusingOnJ TerserIsBetter005 WhyTerseness0MoreFlexible.jpg


To be fair, we must concede the danger of being too telegraphic. However, the ease of reaching a workable solution allows us the luxury of mitigating some of the difficulty of parsing dense code by using a small, domain-specific language as shown here.

MusingOnJ TerserIsBetter006 WhyTerseness1MoreUnderstandable.jpg


But to emphasize the folly of verbosity = readability, consider the following. Detail at too fine a level can obscure what’s important about an algorithm. There probably is some actual processing being done here that's relevant to the problem, it's just hard to find in the morass of irrelevant detail.

MusingOnJ TerserIsBetter007 WhyTerseness1MoreUnderstandable2.jpg


Another Illustration of the Virtue of Brevity

Here we show a fairly simple spec for calculating a check-digit.

The amount of code should reflect the complexity of the algorithm which, in this case, is not much.

MusingOnJ TerserIsBetter008 Example0.jpg


Since this was so easy to code in the first place, we have plenty of bandwidth to break down the steps into little pieces to demonstrate our intermediate results to verify that we’re doing what the spec requires.

MusingOnJ TerserIsBetter009 Example1.jpg


Here, we see the small, domain-specific language - or little language as Jon Bentley would have it - we’ve customized for this problem.

Since the implementation of the spec is so terse, it’s easy to compare differing implementations as shown by the last two lines of code here: the differences are obvious. Contrast this with the difficulty of comparing algorithms of even one or two pages.

MusingOnJ TerserIsBetter010 Example2.jpg


See also Jon Bentley, of Programming Pearls" fame, on "little languages":

A "Programming Pearls" column on "little languages" (subscription required)

examples of good "little languages"

gloss on Jon Bentley's "little languages" idea

Advanced topics

Thomas spoke to us about the problems with amending deeply nested arrays using map }:: . MeetingNotes200908110001 50.jpg

Learning and Teaching J

Some essays on the continuing difficulties in Computer Science education - see "US Computer Science Heading in Wrong Direction.doc", "WhyCSDoesn'tMatter.doc" and "Are We Losing Our Ability to Think Critically.doc"

J Concepts in SC

SuperCollider is a real-time audio synthesis programming language. It is maintained on SourceForge.

Some J concepts, like multiple assignment among others, have found their way into this community. Here is an essay on applying concepts from J to this (array-oriented) language.


The J programming language is a successor of APL; see http://www.jsoftware.com. These languages are made for processing arrays of data and are able to express complex notions of iteration implicitly.

The following are some concepts borrowed from or inspired by J. Thinking about multidimensional arrays can be both mind-bending and mind-expanding. It may take some effort to grasp what is happening in these examples.

// iota fills an array with a counter
z = Array.iota(2, 3, 3);
z.rank; // 3 dimensions
z.shape; // gives the sizes of the dimensions
z = z.reshape(3, 2, 3); // reshape changes the dimensions of an array
z.rank; // 3 dimensions
z.shape;

// fill a 2D array
Array.fill2D(3,3,{1.0.rand.round(0.01)});
Array.fill2D(2,3,{|i,j| i@j});

// fill a 3D array
Array.fill3D(2,2,2,{1.0.rand.round(0.01)});
Array.fill3D(2,2,2,{|i,j,k| `[i,j,k]});


// using dup to create arrays
(1..4) dup: 3;
100.rand dup: 10;
{100.rand} dup: 10;
{100.rand} dup: 3 dup: 4;
{{100.rand} dup: 3} dup: 4;
{|i| i.squared} dup: 10;
{|i| i.nthPrime} dup: 10;

// ! is an abbreviation of dup
(1..4) ! 3;
100.rand ! 10;
{100.rand} ! 10;
{100.rand} ! 3 ! 4;
{{100.rand} ! 3} ! 4;
{|i| i.squared} ! 10;
{|i| i.nthPrime} ! 10;

// other ways to do the same thing:
// partial application
_.squared ! 10;
_.nthPrime ! 10;

// operating on a list
(0..9).squared;
(0..9).nthPrime;

Operator Adverbs
Adverbs are a third argument passed to binary operators that modifies how they iterate over  SequenceableCollections or Streams.  See the Adverbs help file.

[10, 20, 30, 40, 50] + [1, 2, 3]; // normal
[10, 20, 30, 40, 50] +.f [1, 2, 3]; // folded
[10, 20, 30, 40, 50] +.s [1, 2, 3]; // shorter
[10, 20, 30, 40, 50] +.x [1, 2, 3]; // cross
[10, 20, 30, 40, 50] +.t [1, 2, 3]; // table

Operator Depth
J has a concept called verb rank, which is probably too complex to understand and implement in SC, but operator depth is similar and simpler.  A binary operator can be given a depth at which to operate negative depths iterate the opposite operand.

These are better understood by example.  It is not currently possible to combine adverb and depth.

z = Array.iota(3,3);
y = [100, 200, 300];
z + y;
z +.0 y; // same as the above. y added to each row of z
z +.1 y; // y added to each column of z
z +.2 y; // y added to each element of z
z +.-1 y; // z added to each element of y

// deepCollect operates a function at different dimensions or depths in
// an array.
z = Array.iota(3, 2, 3);
f = {|item| item.reverse };
z.deepCollect(0, f);
z.deepCollect(1, f);
z.deepCollect(2, f);
f = {|item| item.stutter };
z.deepCollect(0, f);
z.deepCollect(1, f);
z.deepCollect(2, f);

// slice can get sections of multidimensional arrays.
// nil gets all the indices of a dimension
z = Array.iota(4,5);
z.slice(nil, (1..3));
z.slice(2, (1..3));
z.slice((2..3), (0..2));
z.slice((1..3), 3);
z.slice(2, 3);
z = Array.iota(3,3,3);
z.slice([0,1],[1,2],[0,2]);
z.slice(nil,nil,[0,2]);
z.slice(1);
z.slice(nil,1);
z.slice(nil,nil,1);
z.slice(nil,2,1);
z.slice(nil,1,(1..2));
z.slice(1,[0,1]);
z.flop;

Sorting Order
z = {100.rand}.dup(10); // generate a random array;
// order returns an array of indices representing what would be the
// sorted order of the array.
o = z.order;
y = z[o]; // using the order as an index returns the sorted array

// calling order on the order returns an array of indices that returns
// the sorted array to the original scrambled order
p = o.order;
x = y[p];

// bubbling wraps an item in an array of one element. It takes the
// depth and levels as arguments.
z = Array.iota(4,4);
z.bubble;
z.bubble(1);
z.bubble(2);
z.bubble(0,2);
z.bubble(1,2);
z.bubble(2,2);

// similarly, unbubble unwraps an Array if it contains a single element.
5.unbubble;
[5].unbubble;
[[5]].unbubble;
[[5]].unbubble(0,2);
[4,5].unbubble;
[[4],[5]].unbubble;
[[4],[5]].unbubble(1);
z.bubble.unbubble;
z.bubble(1).unbubble(1);
z.bubble(2).unbubble(2);

Laminating with the +++ Operator
The +++ operator takes each item from the second list and appends it to the corresponding item  in the first list. If the second list is shorter, it wraps.

z = Array.iota(5,2);
z +++ [77,88,99];
z +++ [[77,88,99]];
z +++ [[[77,88,99]]];
z +++ [ [[77]],[[88]],[[99]] ];
// same as:
z +++ [77,88,99].bubble;
z +++ [77,88,99].bubble(0,2);
z +++ [77,88,99].bubble(1,2);
z +++ [11,22,33].pyramidg;
z +++ [11,22,33].pyramidg.bubble;
z +++ [[11,22,33].pyramidg];
z +++ [[[11,22,33].pyramidg]];

(
z = (1..4);
10.do {|i|
z.pyramid(i+1).postln;
z.pyramidg(i+1).postln;
"".postln;
};
)

// reshapeLike allows you to make one nested array be restructured in
// the same manner as another.
a = [[10,20],[30, 40, 50], 60, 70, [80, 90]];
b = [[1, 2, [3, 4], [[5], 6], 7], 8, [[9]]];
a.reshapeLike(b);
b.reshapeLike(a);

// If the lengths are different, the default behaviour is to wrap:
a = [[10,20],[30, 40, 50]];
b = [[1, 2, [3, 4], [[5], 6], 7], 8, [[9]]];
a.reshapeLike(b);

// but you can specify other index operators:
a.reshapeLike(b, \foldAt);
a.reshapeLike(b, \clipAt);
a.reshapeLike(b, \at);

// allTuples will generate all combinations of the sub arrays
[[1, 2, 3], [4, 5], 6].allTuples;
[[1, 2, 3], [4, 5, 6, 7], [8, 9]].allTuples;

Scan of Meeting Notes

MeetingNotes20090811 50.jpg