Can't say that I like any of their code or examples.
In J, In addition to boxscan there is also ^: and lexical closures
http://www.jsoftware.com/jwiki/PascalJasmin/nonads%20revisited
/ is very powerful though
|. >: i.10
10 9 8 7 6 5 4 3 2 1
applying */ to the above not only gives the factorial function, but applying it
partially to any part (from the right side) of it gives you a result you could
apply to more of it
( |. 11 + i.10) * reduce */ |. >: i.10
2432902008176640000
*/ |. >: i.20
2432902008176640000
*/ creates the accumulator as it goes, and is basically a repeated function of
the accumulator and the list tail.
If you wanted an operation that makes a dyadic function between the 2 tail
elements, and then a further operation with the accumulator. Say add the last
2 and multiply by accumulator
1 *&(+/) reduce~ _2 ]\ >: i.10
65835
or wordier general approach of accessing each side separately and then
combining them with a middle fork verb:
(_2 ]\ >: i.10) (] * +/@:[) reduce 1
65835
(] * +/@:[) boxscan (_2 <\ >: i.10)
(,<) 1
65835
Both the cells and the accumulator can be any shape including nested boxes, and
pretty much any recursive function is a fold to a shape compatible with the
function (accumulator cell).
Using these ideas with ^: is commonly done with simulations or search
algorithms where you have a data cell and control cell in 2 boxes, and the left
side of ^: will use {. and {: to qualify access to each side, and then return 2
updated boxes. Any static data should be in x variable. Writing the function
at least initially as an explicit verb can simplify it. Debugging with ^: is
very easy because you can ask it to do 1 2 3 searches and post intermediate
result steps.
the lexical closure approach can be neat. Although performance is not bad, its
not usually as good as boxscan.
lex =: 2 : 0
a =. n~ :: ] y
(n) =: u(a&)
a
)
* lex 'f'"0 ] 1 2 3
1 2 6
f
6&*
(* lex 'f') 1
6
f
6&*
(* lex 'f') is a verb. It is a verb that will update the verb named 'f' to
whatever the result of its last application as a bound x parameter. It will
create f if it doesn't yet exist too. The linked page has more advanced uses
including extracting the x data (accumulator result)
erase 'f'
(* lex 'f')"0 ] 1 2 3 4 5
1 2 6 24 120
f
120&*
(* lex 'f')"0 ] 6 7 8 9 10
720 5040 40320 362880 3628800
the lexical closure approach might be more flexible than boxscan, as the
function part can be updated:
([ lex 'f') 1 NB. locking to a constant function returning x.
3628800
f
3628800&[
f 123
NB. obviously can be applied without updating
3628800
(% lex 'f') 1x NB. reset again
3628800
f
3628800&%
(% lex 'f') 100
36288
(* lex 'f') 2 NB. note that this applies last % function, but will reset f
to 18144&*
18144
linked essay has more uses including the most useful variation of separating
the result and transformation functions.
The terrible blastoff trampoline example can be implemented with nonads
(transformative lexical closures)
erase 'f'
1
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 3 NB. lexT defined in essay
3
f NB. first call just binds x
3&('blast off!'"_^:(0 = [) ; <:@[)
f 5
┌─┬─┐
│5│2│
└─┴─┘
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 5
5
f
2&('blast off!'"_^:(0 = [) ; <:@[) NB. note bound var lowered by 1
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 11
11
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 11 NB. bound value is only 0
after call.
11
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 11
blast off!
timing is not terrible. timespacex causes 2 calls to function.
erase 'f'
1
('blast off!'"_^:(0 = [) ; <:@[) lexT 'f' 1000
0
1000
0
timex '(''blast off!''"_^:(0 = [) ; <:@[) lexT ''f''"0 ] 10000 $ 1'
0.0999663
over 100k calls per second.
----- Original Message -----
From: Jose Mario Quintana <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Monday, August 25, 2014 8:35:39 PM
Subject: Re: [Jprogramming] Adler-32
Pascal wrote:
"
use of terms like "recursion with tail call optimization" come from lisp
fold implementations where in order to avoid stack growth/exhaustion (/
avoids such stack abuse btw), you need to pass any accumulator (state
between function calls) as a parameter to the function. boxscan basically
allows the anything lisp can do, can be done with boxscan (and each/ at its
core) thinking.
"
This sounds very interesting. There is a technique, trampolining, that
supposedly allows for an implementation of tail call optimization; see for
example
http://weblambdazero.blogspot.com/2010/07/advanced-recursion-in-newlisp.html
for an implementation in NewLISP and
http://www.integralist.co.uk/posts/understanding-recursion-in-functional-javascript-programming/
for an implementation in JavaScript. As far as I can see, this trampoline
is a tool (function) written in a target language that allows for TCO
without the need to alter the interpreter. Glancing at these articles
references to accumulators and passing arguments pop up.
Can you really write an equivalent trampoline verb or adverb in J using
boxscan (or anything else)? Further, can you write a wrapper adverb to
modify a recursive verb to optimize it via the trampoline? I would love to
see such tools in a familiar language (explicit versions would be welcome).
Please be gentle with you answer; I am not a computer scientist; I know
next to nothing about LISP, NewLISP or JavaScript; I cannot not even claim
that I know J very well.
On Mon, Aug 25, 2014 at 2:40 PM, 'Pascal Jasmin' via Programming <
[email protected]> wrote:
> / and boxscan are indeed fold and reduce in other languages. The lisp
> implementations probably the easiest to understand.
>
> The big difference between / and boxscan is that / applied to a list
> implies a requirement that all items in the list are the same shape.
> boxscan can use any list of arguments as the x, and appends any shape as
> the y, as long x u y results in a shape "compatible with y" (more
> accurately compatible with future applications of x u result .
>
> use of terms like "recursion with tail call optimization" come from lisp
> fold implementations where in order to avoid stack growth/exhaustion (/
> avoids such stack abuse btw), you need to pass any accumulator (state
> between function calls) as a parameter to the function. boxscan basically
> allows the anything lisp can do, can be done with boxscan (and each/ at its
> core) thinking.
>
> A neat feature regarding tacit adverbs in general, is that I can type
> boxscan in source code, but the actual definition will be "compiled away"
> as if it were called with f. . using the term boxscan can help with
> readability if the intent of the function is to create a rightmost
> accumulator state.
>
>
>
>
> ----- Original Message -----
> From: Raul Miller <[email protected]>
> To: Programming forum <[email protected]>
> Cc:
> Sent: Monday, August 25, 2014 1:16:58 PM
> Subject: Re: [Jprogramming] Adler-32
>
> I have a nitpick with your phrasing here.
>
> Instead of saying "... use / recursively... (tail call optimization)"
> I think you should say something else.
>
> Mind you, I'm not quite sure what you should say.
>
> And, it's a nice clever bit of code. And here's another example of how
> I might use the concept of "use" - I am using the usual J convention
> where we indent the expression but not the result:
>
> (long sentence here) ((&.>)/)(>@:)
> >@:((long sentence here)&.>/)
>
> But I can't quite bring myself to say that this is "using / recursively".
>
> I think I recognize the thought process - the argument to boxscan is a
> binary operator or what we call a dyadic verb, and the underlying
> concept here (which might be called "reduce", "insert" or "fold") is
> often implemented recursively in other contexts.
>
> But / itself represents that same operation. So it's the
> implementation of / or the concept of / which would attach to the
> concept of "recursively", but that's something very different, in my
> mind, from "using / recursively".
>
> Using / recursively seems like it ought to repeatedly use / in the
> same context (instead of just once).
>
> Maybe the sentence should have been "make the use of / more closely
> match a tail call recursive list scan"?
>
> I'm not sure.
>
> (Should I take this kind of side thought to the chat forum?)
>
> Thanks,
>
> --
> Raul
>
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
