NYCJUG/2009-09-08

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

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:

from             Andrea Ambu < 3n1gm4@gmail.com >
to               Programming forum < programming@jsoftware.com >
date             Mon, Aug 31, 2009 at 7:20 AM
subject          [Newbie question] Apply a monad to each element of an array

. I wrote this simple monad (is it its correct name?):

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

It works very well if I call it with just a number as parameter. I'd like to call it with a list as parameter, for example:

  asd 1 2 3

and I'd like to have the same output that

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

would have. I thought I had to look for the map equivalent, in the vocabulary I found {:: but I wasn't able to make it work. Thank you for any help!

-- Andrea

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:

Reply: Alexander Mikhailov

.. I was searching in vain for many days how to specify rank to the verb, defined in multiline manner. I've searched both through JforC and LJ books; I was convinced that in-line setting of the rank is only possible for on-line definitions. I've never seen even a hint to this. Thank you very much, Matthew. Henry Rich, please, please, include this bit of information explicitly into the next revision of your great book. Yes, I'm newbie, and yes, I don't fully understand the logic of verb definitions, or I could've tried to guess that myself, but it's still a pity I was in the dark for so long regarding this matter. Alex

There were a few helpful suggestions based on this.

Reply: Devon McCormick

Alex - this is all too common a problem but that's why we have the J Wiki. Based on your question, I added the following FAQ: http://www.jsoftware.com/jwiki/Guides/General FAQ/How do I define the rank of a verb I create .

Reply: Matthew Brand

It would be good to mention it on the dictionary page as well in an example: http://www.jsoftware.com/help/dictionary/d310n.htm

Reply: Matthew Brand

Glad to be of help, but... "I was searching in vain for many days how to specify rank to the verb, defined in multiline manner." Don't search for days. If you can't find something after a couple of hours then just ask on the forum and get yourself a cup of tea until someone answers - that is what it is here for. Good luck.

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

Reply: Raul Miller

On Tue, Sep 1, 2009 at 5:44 PM, Alexander Mikhailov< avmich@yahoo.com > wrote: > Thank you very much, Matthew. Henry Rich, please, please, include this bit of information explicitly into the .. I did not find a multi-line example of this, but he does say: http://www.jsoftware.com/help/jforc/verb-definition_revisited.htm The point to note is that a verb-definition sequence is just an instance of a compound verb produced by a conjunction, and the resulting verb can appear anywhere a verb is allowed; when the resulting verb is executed, it operates by interpreting the text of the definition one line at a time. You may assign the verb to a name but that's not required. Here are some examples showing how a definition is just an ordinary part of a sentence:

        addrow =: monad : '+/y' "1

.. FYI, -- Raul

Reply: Henry Rich

Yes, thanks, Raul, I thought I had mentioned it somewhere. This is a place where the newbies can help me out. It is hard for me to know how much I have to say to make this clear. Can you, Alexander, or anyone else who has been puzzled by this, give some hints about what more I need to say? Henry Rich

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? 1. 1 2 3 makes a list of numbers, why doesn't a b c do that when they are all numeric? 1. Why do I get spelling errors when I write x. and y.? 1. Is there a BNF description of J? 1. Why do/don't these match? 1. Why doesn't A * B matrix multiply the two matrices A and B? 1. How do I get the row sum of a table? 1. Why +/ *: a works, but when I say foo =: +/ *:, foo a doesn't work? 1. Why does +/ % # 1 2 3 give me 0.333333 instead of the mean, 2? 1. Why does trace produce an error?

[General FAQ] Contents

1. How to add a FAQ ? 1. How do I define the rank of a user-defined verb? 1. How do I launch a browser page from J? 1. How do I run code in the clipboard? 1. How does J manage memory? 1. What should I know about J licenses? 1. How to do lexical closure in J? 1. How to convert between numbers and character representations of numbers 1. How to convert negative numbers between J and other applications 1. 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

from Ian Gorse <unigee@gmail.com>

to Programming forum <programming@jsoftware.com>

date Wed, Sep 2, 2009 at 3:04 PM

subject [Jprogramming] number to text . Sometime last year when I first looked at J, I found some J code that converts a number into a speech representation string for example

     verb 123
   One Hundred and Three

     verb 1642
   One Thousand Six Hundred and Forty Two

  I can't remember where I saw it, I literally found it within a day or two after hearing of J, and was testing what was possible in this strange yet intriguing language I had stumbled upon, so it could have been any of the normal locations J code exists (pdf, mailing list archives, wiki, labs) and sadly my search terms seem to be futile.

Does anybody know where I could find it?

Thanks

Reply: Roger Hui . http://www.jsoftware.com/jwiki/Essays/Number%20in%20Words

Reply: Ian Gorse . Thanks, that was exactly what I was looking for

Reply: Kip Murray . One more "Ask Roger": Roger, how do you search for references like this one?

Reply: Roger Hui . It seems likely that the description of a program of that nature would have "number" or "hundred" in its text. In the J wiki, searching for "number" in the text produces the "Number in Words" essay as the seventh hit; searching for "hundred" produces "Number in Words" as the top hit.

...

Reply: Ian Gorse . See,

Searching for "number" seemed too general, and I immediately dismissed it as an option.

Instead my search terms were more like "number to text" "number to speech" "convert number into words" "number to words"

Of which all of them returned zero results.

I really need to learn to broaden my search terms when my attempts such as "convert number into words" don't give me a link to the exact page I was looking for. Sometimes I really do under-estimate the power of search algorithms, such an elementary mistake.

Reply: Yuvaraj Athur Raghuvir . My experience has been that 'instance' of what I search (in this case the use of the word 'hundred') typically works better than 'representation of intent' (like 'number to text'). Most often I find that there are many ways to represent the intent but the 'forms of the instances' are specific enough to help the search engines generate better results. Many-a-times, combination of intent and instance (like 'number to text hundred') generates better quality results.

My 2c,

Yuva

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.

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.