Thomas wrote:
> Yes. It turns out that O. seems to acts as a "recursion scope" as in the
> 103!:0 foreign documented in the link. That was unintentional but makes...
Regarding the recursion scope, for many years I thought that it would be
difficult to write an adverb, in the official version of the J interpreter,
to provide a recursion scope to tacit recursive verbs to be able to fix
them and embed them within other tacit fixed verbs; I also thought that the
adverb would produce quite inefficient verbs. Thus, the foreign (J
extension (Jx) recursion scope (103!:0) adverb was developed.
However, a couple of days ago I realized that it might not be difficult at
all. Indeed, a pair of adverbs (mRS and dRS) can easily provide the
required scope for monadic and dyadic recursive verbs respectively . (A
single adverb could also be easily written but I will pass until I see an
interesting ambivalent recursive verb).
Since this could be considered a puzzle (there is a caveat though) and a
challenge by someone (although this is unlikely) I am presenting them after
a count down nevertheless:
,. @ |. @ i. 47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
The definition of the (wicked!) adverbs and a performance comparison with
the default hybrid alternative follow:
NB. Recursion Scope...
JVERSION
Installer: j602a_win.exe
Engine: j701/2011-01-10/11:25
Library: 6.02.023
NB. Utilities...
o=. @:
an=. <@:((,'0') ,&< ])
Cloak=. (0:`)(,^:)
evoke=. (<'`:') Cloak NB. Cloaking `: as a verb
train=. evoke&6 NB. Cloaking `:6 as a verb
fix=. (<'f.') Cloak NB. Cloaking f. as a verb
af=. an o fix f. NB. Atomizing after fixing
( a0=. `'' ) ( a1=. (@:[) ((<'&')`) (`:6) ) ( a2=. (`(an _)) (`:6) )
((`'')(((@:[)(&`))(`:6)))((`_)(`:6))
( av=. ((af'a0')`) (`(af'a1')) (`(af'a2') ) (`:6) ) NB. Cloaking a verb
as an adverb
(((`''`)(`(((@:[)(&`))(`:6))))(`((`_)(`:6))))(`:6)
u av
((`'')(&(u@:[)))((`_)(`:6))
st=. (] , <@:(1&({::) * 2&({::)))@:(] ; 7!:2@:] ; 6!:2)
NB. Monadic and dyadic recursive scope adverbs...
mRS=.(`'') (an o < o train f.av) (`,)(`]) (`:6) (train f. o )
(&:(an f.))
dRS=.(`'') (an o < o train f.av) (`,) (`]) (,`) ([`) (`:6) (train f. o )
(&:(an f.))
NB. Monadic recursion scope...
fact=. 1:`(* $:@<:)@.*
( f0=. (1 + fact)f. ) ( f1=. 1 + fact f.mRS )
(1 + 3 : '1:`(* $:@<:)@.* y' :(4 : 'x 1:`(* $:@<:)@.* y')) (1 +
,^:(0:``:)&6@:((<1:`(* $:@<:)@.*) , ])&:(<@:((,'0') ,&< ])))
(f0 ; f1) 5
┌───┬───┐
│121│121│
└───┴───┘
1111 st &> 'f0 5 ' ; 'f1 5 '
┌────────┬────┬──────────┬─────────┐
│f0 5 │5440│3.48083e_5│0.189357 │
├────────┼────┼──────────┼─────────┤
│f1 5 │2944│2.55445e_5│0.0752031│
└────────┴────┴──────────┴─────────┘
11 st &> 'f0 1111x' ; 'f1 1111x'
┌────────┬──────┬──────────┬───────┐
│f0 1111x│986432│0.0109654 │10816.6│
├────────┼──────┼──────────┼───────┤
│f1 1111x│984192│0.00961377│9461.79│
└────────┴──────┴──────────┴───────┘
((1+!) -: f0) 1111x
1
(f0 -: f1) 1111x
1
NB. Dyadic recursion scope...
binomial=. 1:`(%~ * $:&:<:)@.(*@:[)
( g0=. (1 + binomial)f. ) ( g1=. 1 + binomial f.dRS )
(1 + 3 : '1:`(%~ * $:&:<:)@.(*@:[) y' :(4 : 'x 1:`(%~ * $:&:<:)@.(*@:[)
y')) (1 + ,^:(0:``:)&6@:([ , (<1:`(%~ * $:&:<:)@.(*@:[)) , ])&:(<@:((,'0')
,&< ])))
7 (g0 ; g1) 11
┌───┬───┐
│331│331│
└───┴───┘
1111 st &> '7 g0 11' ; '7 g1 11'
┌───────┬────┬──────────┬────────┐
│7 g0 11│7936│5.27918e_5│0.418956│
├───────┼────┼──────────┼────────┤
│7 g1 11│4544│5.03489e_5│0.228785│
└───────┴────┴──────────┴────────┘
11 st &> '777x g0 111x' ; '777x g1 1111x'
┌─────────────┬──────┬─────────┬───────┐
│777x g0 111x │900544│0.0150156│13522.2│
├─────────────┼──────┼─────────┼───────┤
│777x g1 1111x│897664│0.0149416│13412.5│
└─────────────┴──────┴─────────┴───────┘
777x ((1+!) -: g0) 1111x
1
777x (g0 -: g1) 1111x
1
There is still a case, although not as strong as before, for the Jx adverb
(103!:0); the following is the same session executed with a Jx interpreter:
NB. Recursion Scope...
JVERSION
Installer: j602a_win.exe
Engine: j701/2012-12-06/12:20/x
Library: 6.02.023
NB. Utilities...
o=. @:
an=. <@:((,'0') ,&< ])
Cloak=. (0:`)(,^:)
evoke=. (<'`:') Cloak NB. Cloaking `: as a verb
train=. evoke&6 NB. Cloaking `:6 as a verb
fix=. (<'f.') Cloak NB. Cloaking f. as a verb
af=. an o fix f. NB. Atomizing after fixing
( a0=. `'' ) ( a1=. (@:[) ((<'&')`) (`:6) ) ( a2=. (`(an _)) (`:6) )
((`'')(((@:[)(&`))(`:6)))((`_)(`:6))
( av=. ((af'a0')`) (`(af'a1')) (`(af'a2') ) (`:6) ) NB. Cloaking a verb
as an adverb
(((`''`)(`(((@:[)(&`))(`:6))))(`((`_)(`:6))))(`:6)
u av
((`'')(&(u@:[)))((`_)(`:6))
st=. (] , <@:(1&({::) * 2&({::)))@:(] ; 7!:2@:] ; 6!:2)
NB. Monadic and dyadic recursive scope adverbs...
mRS=.(`'') (an o < o train f.av) (`,)(`]) (`:6) (train f. o )
(&:(an f.))
dRS=.(`'') (an o < o train f.av) (`,) (`]) (,`) ([`) (`:6) (train f. o )
(&:(an f.))
NB. Monadic recursion scope...
fact=. 1:`(* $:@<:)@.*
( f0=. (1 + fact)f. ) ( f1=. 1 + fact f.mRS )
(1 + 1:`(* $:@<:)@.* (103!:0)) (1 + ,^:(0:``:)&6@:((<1:`(* $:@<:)@.*) ,
])&:(<@:((,'0') ,&< ])))
(f0 ; f1) 5
┌───┬───┐
│121│121│
└───┴───┘
1111 st &> 'f0 5 ' ; 'f1 5 '
┌────────┬────┬──────────┬─────────┐
│f0 5 │2176│1.42387e_5│0.0309835│
├────────┼────┼──────────┼─────────┤
│f1 5 │2944│2.57751e_5│0.0758819│
└────────┴────┴──────────┴─────────┘
11 st &> 'f0 1111x' ; 'f1 1111x'
┌────────┬──────┬─────────┬───────┐
│f0 1111x│983168│0.0132661│13042.8│
├────────┼──────┼─────────┼───────┤
│f1 1111x│984192│0.0118299│11642.9│
└────────┴──────┴─────────┴───────┘
((1+!) -: f0) 1111x
1
(f0 -: f1) 1111x
1
NB. Dyadic recursion scope...
binomial=. 1:`(%~ * $:&:<:)@.(*@:[)
( g0=. (1 + binomial)f. ) ( g1=. 1 + binomial f.dRS )
(1 + 1:`(%~ * $:&:<:)@.(*@:[) (103!:0)) (1 + ,^:(0:``:)&6@:([ , (<1:`(%~ *
$:&:<:)@.(*@:[)) , ])&:(<@:((,'0') ,&< ])))
7 (g0 ; g1) 11
┌───┬───┐
│331│331│
└───┴───┘
1111 st &> '7 g0 11' ; '7 g1 11'
┌───────┬────┬──────────┬────────┐
│7 g0 11│3648│3.27112e_5│0.11933 │
├───────┼────┼──────────┼────────┤
│7 g1 11│4544│5.05107e_5│0.229521│
└───────┴────┴──────────┴────────┘
11 st &> '777x g0 111x' ; '777x g1 1111x'
┌─────────────┬──────┬─────────┬───────┐
│777x g0 111x │896256│0.0154204│13820.7│
├─────────────┼──────┼─────────┼───────┤
│777x g1 1111x│897664│0.0147461│13237.1│
└─────────────┴──────┴─────────┴───────┘
777x ((1+!) -: g0) 1111x
1
777x (g0 -: g1) 1111x
1
On Wed, Aug 27, 2014 at 3:20 PM, Thomas Costigliola <[email protected]>
wrote:
> On Wed, Aug 27, 2014 at 2:35 PM, Raul Miller <[email protected]>
> wrote:
>
> > This pair of mechanisms ($: and O.) makes it easier to talk about
> > "tail call optimizations".
> >
> > The "tail call optimization on recursion" is only valid when the
> > result of $: is the result of its containing verb.
> >
>
> Yes. It turns out that O. seems to acts as a "recursion scope" as in the
> 103!:0 foreign documented in the link. That was unintentional but makes
> sense given the implementation. So something like (f O. g h O.) should work
> if you want f and h recursive independent of each other.
>
>
> >
> > So that should make detection of the invalid case simple - *any*
> > transformation of the result of $: within a verb controlled by O.
> > should be flagged as an error.
> >
>
> Yes. One way to do that is to inspect v in v O. and detect it structurally
> before doing anything. Another way is to either 1: define the continuation
> (the result of $:) in a way that would already trigger an error in the
> interpreter (which would require something clever) or 2: modify the other
> primitives to signal an error when passed a continuation; some already take
> care of that I think.
>
>
> >
> > Thanks,
> >
> > --
> > Raul
> >
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
