Dan,
First, thanks for the pointers (given in the other thread), I found your
tool but I could not find Oleg's; anyway, I made Roger's map tacit (I cannot
help it):
tm 5!:5 < 'tm'
, ((2 (#.\"1) 0 ,. [ (] </~ [ i...@] [ -...@] >./)@] [ +/\...@] ([ =/\...@]
'''' ~: ]) * 1 _1 0 {~ '()' i. ]) { ' ' , 6 8 10 { [ 9!:6...@] ''"_)
└─────┘ └──────────────────────┘
└─────────────────┘
└─────────────────────────────────────────────────────────────────────────────────────────────┘
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
It has been already useful for analyzing parts of your code which I find
fascinating.
Second,I understand that you want to avoid recursion because it not fully
fixable and you are already following a non-recursive lead from, will all do
respect, "the Boss." However, there is a way to write fully fixable recursive
code in J; see http://rosettacode.org/wiki/Y_combinator#J . The method implies
heavy overhead and it is typically relatively slow; but adverbial programming,
as you pointed out before, is not about efficiency; besides it could be fun to
try.
Jose (a.k.a. Pepe)
________________________________
From: Dan Bron <[email protected]>
To: General forum <[email protected]>
Sent: Friday, August 21, 2009 4:11:43 PM
Subject: Re: [Jgeneral] Looks like a bug in ".
> vs NB. Verb structure
> ~.@:|.@:((3: = 4!:0) # ])@:(;:@:(5!:5@<)) ,. $:&.>@:(~.@:|.@:((3: = 4!:0) #
>])@:(;:@:(5!:5@<)))
Hey, neat! That's going in my bag of tricks. Have you seen Oleg's work in
this field?
http://www.jsoftware.com/pipermail/general/2008-July/032131.html
http://www.jsoftware.com/jwiki/OlegKobchenko/Map%20Display
I have a similar tool:
http://www.jsoftware.com/pipermail/general/2008-July/032126.html
Of course these tools help visualize code structure, whereas your tool
helps visual name structure (or relationships between names).
-Dan
----- Forwarded Message ----
________________________________
From: Dan Bron <[email protected]>
To: Programming forum <[email protected]>
Sent: Monday, August 24, 2009 3:32:43 PM
Subject: [Jprogramming] Recursive nesting, avoiding recursion
Hey guys,
I needed to represent a "nested list" like this:
NEST =. ;: '(345 * _2 + +/@:(+/%#) * ]) - ''hello''"_ , <.'
as analogously-nested set of boxes, like this:
] BOX =. (< (;:'345*_2+;+/@:') , (<;:'+/%#') , ;:'*]') ,
;:'-''hello''"_,<.'
+-----------------------------------+-+-------+-+-+-+--+
|+---+-+--+-+-+-+-+--+---------+-+-+|-|'hello'|"|_|,|<.|
||345|*|_2|+|;|+|/|@:|+-+-+-+-+|*|]|| | | | | | |
|| | | | | | | | ||+|/|%|#|| | || | | | | | |
|| | | | | | | | |+-+-+-+-+| | || | | | | | |
|+---+-+--+-+-+-+-+--+---------+-+-+| | | | | | |
+-----------------------------------+-+-------+-+-+-+--+
This is something I've had to do a number of times, with minor variations.
The most recent case was in the ae2 script [1], which is as above,
except instead of the actual J words I needed to nest their indices in the
original sentence. But I've encountered it in other guises over the
years: parsing XML, data representations from other languages, etc.
So, what I would like is a general dyad to transform a "parenthesized" list
into nested boxes:
A. The right argument (y) is the "parenthesized list"
(in the example above, it's a list of J words,
some of which are boxed parens, but it could be
anything, like a string with {}s, boxes containing
XML elements, etc).
B. The left argument (x) indicates or implies the "level"
or "depth" of each of the items of y . For example,
if y were NEST then the level of each word is:
(345 * _2 + +/@:(+/%#) * ]) - 'hello'"_ , <.
1 1 1 1 1 11 1222222 1 11 0 000 0 0
How to represent this is up to you. You could require
parens to be included or excluded from both x and y;
if included you could require their level to be be N
or N+1 or different for open and close parens; you
could use an integer for the level of each element,
like above, or just _1 0 1 to indicate "level
change", etc.
The key thing is how to represent x is up to you, but
how to calculate x from y is up to your user [2].
C. The output is the nested-box analog of y.
Here's how I do it in [1]:
nest2Box =. cleanNest@:cutNest@:,&<~
cleanNest =. bubble@:rmScaff
bubble =. >@:{.^:(1=#)L:1^:_
rmScaff =. >@:{.L:1
cutNest =. cutBot L:1^:maxDepth
cutBot =. ('';1) <@:,;.1 ] noParen;.2&>~ minMask
noParen =. <@:(}.@:}:^:(1<#))
minMask =. (=<./)&.>@:{:
maxDepth =. 1 + >./@:>@:{:
n2b =: nest2Box f.
x =. (;:'()') (+/\@:(-/))@:(=/) NEST NB. Depth of each element
y =. i.#NEST NB. Elements
x n2b y
+----------------------------------+--+--+--+--+--+--+
|+-+-+-+-+-+-+-+------------+--+--+|17|18|19|20|21|22|
||1|2|3|4|5|6|7|+-+--+--+--+|14|15|| | | | | | |
|| | | | | | | ||9|10|11|12|| | || | | | | | |
|| | | | | | | |+-+--+--+--+| | || | | | | | |
|+-+-+-+-+-+-+-+------------+--+--+| | | | | | |
+----------------------------------+--+--+--+--+--+--+
But I'm not too proud of it [3]. For one thing, it's not general; y must
be open (not boxed), because of the way I use L: :
x n2b NEST
|domain error: n2b
| x n2b NEST
Which raises the question of why I use L: . Isn't nesting a textbook
example of a recursive problem? Shouldn't I be recursing from the top
down, rather than cutting from the bottom up?
The reason is that I, like Jose, prefer fully fixable tacit verbs. There
are essentially two ways to recurse in J; having a named verb call its own
name, and anonymous recursion using $: . Neither method lends itself to
fully fixable tacit form.
Named recursion doesn't permit fixing, and requires a verb be named when
ideally all verbs work the same when anonymous. And verbs that use $:
cause problems when fixed in the definition of other verbs. Essentially,
when a verb ("f") is fixed, if one of the verbs it calls ("g") uses $: ,
then that $: stops referrring to f and starts referring to g , or
introduces an explicit context where it wasn't previously required (and
stops the verb from being fully tacit). On that note, I should mention
that I can picture approaches that generate and evoke code, but I consider
them ambiguously tacit at best.
So, while I'm interested in all approaches (because I can do the work to
adapt them to the form I prefer), I'm particularly interested in verbs
which are tacit, fully fixable, and could be replaced everywhere by their
definition in parentheses. I think this implies cutting from the bottom
up, as I have. But I'm happy to be proven wrong.
-Dan
[1]
http://www.jsoftware.com/svn/DanBron/trunk/environment/anonymous_evoke2.ijs
[2] Allowing the user to calculate x, rather than calculating
it for him, makes future extensions easier. For
convenience, we could also provide cover verbs of
nest2Box to calculate x for common cases (like J words,
strings with {}s, etc).
If we did, I think it would be useful to let the cover
verb's left argument be (potential) items from y that
represent "parentheses", in several forms:
(A) A single item that counts as both open and
close parens,
(B) A list of 2 items which count as open and
close-parens respectively,
(C) A table of (B); a N by 2 table of items
that count as open-parens and close-parens.
[3] If nothing else, improvements to nest2Box are welcome. For example,
bubble and rmScaff are essentially identical. (I know I implemented a
similar function in a different context, and IIRC it was a bit more
elegant. But I can't find that now.)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
