How to resolve the algorithm Y combinator step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Y combinator step by step in the J programming language

Table of Contents

Problem Statement

In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function. The   Y combinator   is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function. The Y combinator is the simplest of the class of such functions, called fixed-point combinators.

Define the stateless   Y combinator   and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Y combinator step by step in the J programming language

Source code in the j programming language

Y=. '('':''<@;(1;~":0)<@;<@((":0)&;))'(2 : 0 '')
  (1 : (m,'u'))(1 : (m,'''u u`:6('',(5!:5<''u''),'')`:6 y'''))(1 :'u u`:6')
)


   'if. * y do. y * u <: y else. 1 end.' Y 10 NB. Factorial
3628800   
          '(u@:<:@:<: + u@:<:)^:(1 < ])' Y 10 NB. Fibonacci
55


   arb=. ':'<@;(1;~":0)<@;<@((":0)&;)                     NB. AR of an explicit adverb from its body 
   
   ara=. 1 :'arb u'                                       NB. The verb arb as an adverb
   srt=. 1 :'arb ''u u`:6('' , (5!:5<''u'') , '')`:6 y''' NB. AR of the self-replication and transformation adverb
   gab=. 1 :'u u`:6'                                      NB. The AR of the adverb and the adverb itself as a train
   
   Y=. ara srt gab                                        NB. Train of adverbs


XY=. (1 :'('':''<@;(1;~":0)<@;<@((":0)&;))u')(1 :'('':''<@;(1;~":0)<@;<@((":0)&;))((''u u`:6('',(5!:5<''u''),'')`:6 y''),(10{a.),'':'',(10{a.),''x(u u`:6('',(5!:5<''u''),'')`:6)y'')')(1 :'u u`:6')


   1 2 3 '([:`(>:@:])`(<:@:[ u 1:)`(<:@[ u [ u <:@:])@.(#.@,&*))'XY"0/  1 2 3 4 5 NB. Ackermann function...
 3  4  5   6   7
 5  7  9  11  13
13 29 61 125 253
                               '1:`(<: u <:)@.* : (+ + 2 * u@:])'XY"0/~ i.7       NB. Ambivalent recursion...
2  5 14 35 80 173 362
3  6 15 36 81 174 363
4  7 16 37 82 175 364
5  8 17 38 83 176 365
6  9 18 39 84 177 366
7 10 19 40 85 178 367
8 11 20 41 86 179 368
   NB. OEIS A097813 - main diagonal   
   NB. OEIS A050488 = A097813 - 1 - adyacent upper off-diagonal


YX=. (1 :'('':''<@;(1;~":0)<@;<@((":0)&;))u')($:`)(`:6)


Y=. ((((&>)/)((((^:_1)b.)(`(<'0';_1)))(`:6)))(&([ 128!:2 ,&<)))


   u=. [ NB. Function (left)
   n=. ] NB. Argument (right)
   sr=. [ apply f. ,&< NB. Self referring
    
   fac=. (1:`(n * u sr n - 1:)) @. (0 < n)
   fac f. Y 10
3628800
       
   Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1 < n)
   Fib f. Y 10
55


   fac f. Y NB. Factorial...
'1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])&>/'&([ 128!:2 ,&<)

   fac f.   NB. Factorial step...
1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])

   
   Fib f. Y NB. Fibonacci...
'(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])&>/'&([ 128!:2 ,&<)

   Fib f.   NB. Fibonacci step...
(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])


   sr=. [ apply f.,&<                 NB. Self referring
   lv=. (((^:_1)b.)(`(<'0';_1)))(`:6) NB. Linear representation of a verb argument
   Y=. (&>)/lv(&sr)                   NB. Y with embedded states
   Y=. 'Y'f.                          NB. Fixing it...
   Y                                  NB. ... To make it stateless (i.e., a combinator)
((((&>)/)((((^:_1)b.)(`_1))(`:6)))(&([ 128!:2 ,&<)))


Y=:1 :0
  f=. u Defer
  (5!:1<'f') f y
)

Defer=: 1 :0
:
  g=. x&(x`:6)
  (5!:1<'g') u y
)

almost_factorial=: 4 :0
  if. 0 >: y do. 1
  else. y * x`:6 y-1 end.
)

almost_fibonacci=: 4 :0
  if. 2 > y do. y
  else. (x`:6 y-1) + x`:6 y-2 end.
)


   almost_factorial Y 9
362880
   almost_fibonacci Y 9
34
   almost_fibonacci Y"0 i. 10
0 1 1 2 3 5 8 13 21 34


Y=:2 :0(0 :0)
NB. this block will be n in the second part
:
  g=. x&(x`:6)
  (5!:1<'g') u y
)
  f=. u (1 :n)
  (5!:1<'f') f y
)


   almost_factorial f. Y 10
3628800

You may also check:How to resolve the algorithm Copy a string step by step in the Elena programming language
You may also check:How to resolve the algorithm Keyboard macros step by step in the Raku programming language
You may also check:How to resolve the algorithm Rosetta Code/Find unimplemented tasks step by step in the Lua programming language
You may also check:How to resolve the algorithm Pernicious numbers step by step in the 11l programming language
You may also check:How to resolve the algorithm Base64 decode data step by step in the Go programming language