newbie, questions, searching, directory tree walk, depth-first versus breadth-first

Contents

  1. Summary of Meeting
  2. Meeting Agenda for NYC JUG 20090908
  3. Proceedings
    1. Beginner's regatta
      1. A Simple Question Leads to a Useful Discussion
      2. Finding Things in J and in General
    2. Show-and-tell
      1. General Walk Tree
    3. Advanced Topics
    4. Learning and Teaching J
  4. Scan of Meeting Notes

Summary of Meeting

We talked about an interesting online problem and a puzzle, then covered the topics from how to improve the J learning experience for the inexperienced and help people find answers, to various discussions that kept coming back to topics on the virtues of terseness. Finally, we looked at some things an outsider likes about J.

Meeting Agenda for NYC JUG 20090908

1. Beginner's regatta: what are common newbie questions?  Updating the J
language FAQ: see "NewbieQuestionsWhatAreThey.odt" (3).

Recommendations for finding things in J and in general - see
"Finding Things in J and in General.odt" (2).


2. Show-and-tell: Generalization of directory tree walker: not only apply
an arbitrary verb at each node but allow specification of depth or breadth
first traversal as well as flat or nested results: see "General Walk Tree
explanation.odt" (3).


3. Advanced topics: Array habits considered harmful: see
"HowArrayHabitsCanBeHarmful.odt" (1).

How to promote J on "Rosetta Code" - see "PromotingJonRC.odt" (3) - and
balancing terseness with clarity - see "RCDiscussionAboutTerseness.odt" (3).


4. Learning, teaching and promoting J: what's so good about J? See
"The World's Most Mind-Bending Language.doc" (4).

Proceedings

Beginner's regatta

A Simple Question Leads to a Useful Discussion

We considered the following question posted on the forum: 

  asd =: 3 : 0
 t =. 2*(1+y)
 1+t*(t-1)+i.4
)

  asd 1 2 3

  (asd 1), (asd 2), asd 3

This elicited several responses, each with a different way to apply a function to rank-zero elements. The discussion that followed changed into a more general one about the difficulty of finding things about J:

There were a few helpful suggestions based on this:

Another reply reminded us that even the person who wrote a piece does not necessarily know where it is:

This last request reminds us how useful is the perspective of a newbie and how quickly we lose sight of it once we've acquired some level of expertise.

With this in mind, we took a look at some of the J FAQs and found them wanting. Here are the entries in them now:

[J Language FAQ] Contents

  1. Why does +/@*: 1 2 3 give me 1 4 9 instead of 14?

  2. 1 2 3 makes a list of numbers, why doesn't a b c do that when they are all numeric?

  3. Why do I get spelling errors when I write x. and y.?

  4. Is there a BNF description of J?

  5. Why do/don't these match?

  6. Why doesn't A * B matrix multiply the two matrices A and B?

  7. How do I get the row sum of a table?

  8. Why +/ *: a works, but when I say foo =: +/ *:, foo a doesn't work?

  9. Why does +/ % # 1 2 3 give me 0.333333 instead of the mean, 2?

  10. Why does ''trace'' produce an error?

[General FAQ] Contents

  1. How to add aFAQ?

  2. How do I define the rank of a user-defined verb?

  3. How do I launch a browser page from J?

  4. How do I run code in the clipboard?

  5. How does J manage memory?

  6. What should I know about J licenses?

  7. How to do lexical closure in J?

  8. How to convert between numbers and character representations of numbers

  9. How to convert negative numbers between J and other applications

  10. How do I save my workspace in J?

These look more like an initial attempt to seed the FAQs than actual "Frequently Asked Questions". Since these are all on the Wiki, the J community needs to make a better effort to update these with actual questions. I'm particularly discouraged by the presence of my long-time nemesis lexical closure at position #8 on the "General FAQ" - what newbie would think to ask a question like this?

A major difficulty for beginners to J is that they don't share our vocabulary: it's hard to frame a question well if you don't have the word to describe what you're looking for.

Asking how to ask questions led us directly into our second beginner's topic:

Finding Things in J and in General

     verb 123
   One Hundred and Three

     verb 1642
   One Thousand Six Hundred and Forty Two

...

This led us to question why people sometimes seem reluctant to search and a further discussion about how we need to re-orient how we think about searching. We need to envision what a result might look like rather than framing our search in terms of a question. It's this latter notion that seems to drive the research of some search-engine companies but perhaps this is the wrong direction.

Show-and-tell

The following is code and examples of a general directory tree walker. John mentioned that this is what is known as a "Visitor Pattern" in OO-speak: we visit each node and do something there. This lends itself naturally to an adverb.

This generalizes an earlier tree walker - also shown below - in two respects: we can specify whether to walk the tree depth-first or breadth-first and we can specify whether we want a nested or a "flat" result. This latter generalization is the result of my using the original tree walking code and noticing that, very often, the first thing I'd do with the nested result would be to flatten it.

General Walk Tree

NB.* generalWalkTree: general directory tree walk: perform "u y" at each node:
NB. 0{x: (0) depth first or (1) breadth first;
NB. 1{x: (0) flattened or (1) nested result matching input tree structure.
generalWalkTree=: 1 : 0
   (1 0) u generalWalkTree y
:
   ct=. 0 [ rr=. '' [ stack=. ,boxopen y [ x=. 2{.x
   ctr=. (0{x){_1 0           NB. First we build the stack.
   while. ct<#stack do.                           NB. Get subdir names:
       subds=. ((('d'e.&>4{"1])#0{"1])@:(1!:0@<)) (>ctr{stack),'\*'
       subds=. subds (],&.>'\',&.>[) ctr{stack    NB. -> full path names
       if. 0{x do. stack=. stack,subds            NB. Breadth or
       else.       stack=. subds,stack  end.      NB.  depth first
       ctr=. ctr+(0{x){_1 1 [ ct=. >:ct           NB. Go forward or backward
   end.
   dpth=. (]-<./)'\'+/ . =&>stack
   if. 1{x do. ;&.>(<:~.dpth) depthEnc dpth </. u&.>stack  NB. Preserve tree
   else.       u&.>stack              end.                 NB.  or flatten it.
)

depthEnc=: 4 : '<^:(>:x)]y'"0

One of the things I found most interesting about this is that the difference between the two search orders is simply the order in which we assemble the stack: putting new items on the end gives us breadth-first whereas putting new items on the front gives us depth-first. J's terseness allows us to highlight the simplicity that underlies the difference between the two basic approaches.

Compare this with the original, simpler tree walker: 

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
)

Here’s a picture of a sample directory tree on which to test the general tree walker.

Note that the nodes are labeled to reflect the tree structure.

That is, the top node is “tree0” and the nodes below this are “tree00”, “tree01”, and “tree02”: each child node name is the parent node name suffixed by a sequence number. treeStruc0.png

Sample Results 

   dd=: 'C:\amisc\J\NYCJUG\200909\tree0\tree00'  NB. Our sample directory tree
   $&.>aa00=. (0 0) ] generalWalkTree_fldir_ dd  NB. Depth first, flat result
+--+--+--+--+--+--+
|54|54|54|45|45|37|
+--+--+--+--+--+--+
   >aa00
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000\tree0000
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000\tree0001
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree001\tree0010
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree001
C:\amisc\J\NYCJUG\200909\tree0\tree00

Here the display of our result lays out the depth-first order of tree traversal.

Notice how we use the verb "dex" here to help us test our result. Someone unfamiliar with functional programming might think that a function like ], which "does nothing", is a useless thing. However, here we see how useful it can be as it allows us to test the adverb without complication from the verb being applied.

Examples of the other three combinations of Depth/Breadth and Nested/Flat follow. 

   $&.>aa01=. (0 1) ] generalWalkTree_fldir_ dd  NB. Depth First, boxed result
+-+-+--+
|1|2|37|
+-+-+--+
   {::aa01
+---------------------------+-------------+---+
|+-------------------------+|+-----+-----+|+-+|
||+-------+-------+-------+|||+-+-+|+-+-+|||2||
|||+-+-+-+|+-+-+-+|+-+-+-+|||||1|0|||1|1|||+-+|
||||0|0|0|||0|0|1|||0|0|2|||||+-+-+|+-+-+||   |
|||+-+-+-+|+-+-+-+|+-+-+-+|||+-----+-----+|   |
||+-------+-------+-------+||             |   |
|+-------------------------+|             |   |
+---------------------------+-------------+---+
   (0;0;0){::aa01
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000\tree0000
   (1;0){::aa01
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000
   (2){::aa01
C:\amisc\J\NYCJUG\200909\tree0\tree00

   $&.>aa10=. (1 0) ] generalWalkTree_fldir_ dd  NB. Breadth first, flat result
+--+--+--+--+--+--+
|37|45|45|54|54|54|
+--+--+--+--+--+--+
   >aa10
C:\amisc\J\NYCJUG\200909\tree0\tree00
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree001
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000\tree0000
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000\tree0001
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree001\tree0010

   $&.>aa11=. (1 1) ] generalWalkTree_fldir_ dd  NB. Breadth first, boxed result
+--+-+-+
|37|2|1|
+--+-+-+
   {::aa11
+---+-------------+---------------------------+
|+-+|+-----+-----+|+-------------------------+|
||0|||+-+-+|+-+-+|||+-------+-------+-------+||
|+-+|||1|0|||1|1|||||+-+-+-+|+-+-+-+|+-+-+-+|||
|   ||+-+-+|+-+-+|||||2|0|0|||2|0|1|||2|0|2||||
|   |+-----+-----+|||+-+-+-+|+-+-+-+|+-+-+-+|||
|   |             ||+-------+-------+-------+||
|   |             |+-------------------------+|
+---+-------------+---------------------------+
   (0){::aa11
C:\amisc\J\NYCJUG\200909\tree0\tree00
   (1;0){::aa11
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree000
   (2;0;2){::aa11
C:\amisc\J\NYCJUG\200909\tree0\tree00\tree001\tree0010

Advanced Topics

We considered the trade-off between array-based versus streaming approaches to handling arrays as exemplified in this lesson from Joey Tuttle.

We then applauded Dan Bron's recent efforts to market J by getting the community involved in the Rosetta Code effort.

Learning and Teaching J

See this essay on what an outsider to the J community finds attractive about the language. He's very enthusiastic about some things that we take for granted or even disparage among ourselves.

Scan of Meeting Notes

NYCJUG090908Meeting40pct1.jpg NYCJUG090908Meeting40pct2.jpg NYCJUG090908Meeting40pct3.jpg NYCJUG090908Meeting40pct4.jpg NYCJUG090908Meeting40pct5.jpg NYCJUG090908Meeting40pct6.jpg NYCJUG090908Meeting40pct7.jpg NYCJUG090908Meeting40pct8.jpg NYCJUG090908Meeting40pct9.jpg

CategoryWorkInProgress CategoryWorkInProgress

NYCJUG/2009-09-08 (last edited 2009-10-17 20:53:45 by DevonMcCormick)