Cascade in Rebol

Question

In Logo Language, cascade is a procedure to to compose a function with itself several times (it is almost like fold in functional language).
Example:

   add 4 add 4 add 4 5  -->  cascade 3 [add 4 ?1] 5 ==  17
   2^8 -->  cascade 8 [?1 * 2] 1
   fibonacci 5 --> (cascade 5 [?1 + ?2] 1 [?1] 0)
   factorial 5 --> (cascade 5 [?1 * ?2] 1 [?2 + 1] 1)

General notation for multi-input cascade, in Logo:
(cascade how many function1 start1 function2 start2 ...) with:

function1 -> ?1 ,  
function2 -> ?2 ... 

Cascade returns the final value of ?1.

In Rebol:

cascade1: func [howmany function1 start1] [....]      
cascade2: func [howmany function1 start1 function2 start2] [....]

How to write cascade1 and cascade2 in Rebol ?

Answer 1

With bind, that Binds words to a specified context (in this case local context of function), and compose function, I get:

cascade: func [  
    times
    template
    start 
] [
    use [?1] [
        ?1: start  
        template: compose [?1: (template)]  
        loop times bind template '?1  
        ?1
    ]  
]

cascade 8 [?1 * 2] 1
== 256
cascade 3 [add 4 ?1] 5
== 17  
val: 4
cascade 3 [add val ?1] 5
== 17



cascade2: func [
    times
    template1 start1
    template2 start2
    /local **temp**
] [
    use [?1 ?2] [ ; to bind only ?1 and ?2 and to avoid variable capture
        ?1: start1
        ?2: start2
        loop 
            times 
            bind 
                compose [**temp**: (template1) ?2: (template2) ?1: **temp**] 
                '?1
        ?1
    ]
]


 cascade2 5 [?1 * ?2] 1 [?2 + 1] 1
 == 120
 cascade2 5 [?1 + ?2] 1 [?1] 0
 == 8

Answer 2

My answer uses REBOL 3, but could be backported to 2 without too much trouble. (I'd have done it in REBOL 2, but I don't have REBOL 2 on my system and haven't used it in a long time.) This implements cascade fully (i.e., with any number of "functions") and does it in an idiomatically REBOL kind of way: It uses a simple DSL.

cascade: funct [
  count [integer!]
  template [block!]
  /only "Don't reduce TEMPLATE"
  /local arg fun-block
][
  param-list: copy []
  param-number: 1
  arg-list: copy []
  fun-list: copy []
  template-rules: [
    some [
      copy fun-block block! (
        append param-list to word! rejoin ["?" ++ param-number]
        append fun-list fun-block
      )
      copy arg any-type! (
        append arg-list :arg
      )
    ]
    end
  ]
  unless only [template: reduce template]
  unless parse template template-rules [
    do make error! rejoin ["The template " mold/flat template " contained invalid syntax."]
  ]
  while [! tail? fun-list] [
    fun-list: change fun-list func param-list first fun-list
  ]
  fun-list: head fun-list
  loop count [
    temp-args: copy []
    for f 1 length? fun-list 1 [
      append/only temp-args apply pick fun-list f arg-list
    ]
    arg-list: copy temp-args
  ]
  first arg-list
]

Using it is simple:

print cascade 23 [[?1 + ?2] 1 [?1] 0]

This correctly gives the value 46368 from one of the cascade examples given in the Logo cascade documentation linked by the questioner. The syntax of the DSL should be brutally obvious. It's a series of blocks followed by starting arguments. The outer block is reduced unless the /only refinement is used. A block itself will work just fine as an argument, e.g.,

cascade 5 [[?1] [1 2 3]]

This is because the first block is interpreted as a "function", the second as a starting argument, the third as a "function" and so on until the template block is exhausted.

As far as I can tell, this is a complete (and rather elegant) implementation of cascade. Man, I love REBOL. What a shame this language didn't take off.

Answer 3

Here is a somewhat working cascade in Rebol. It won't work with op! datatype--i.e. +, *--but it will work with add and multiply. You may want to check out the higher order functions script to see some other examples. I haven't had time to write cascade2 yet

cascade: func [
    times [integer!]
    f [any-function!]
    partial-args [series!]
    last-arg
][
    expression: copy reduce [last-arg]
    repeat n times [
        insert head expression partial-args
        insert head expression get 'f
    ]
    expression
]

With your examples:

probe cascade 3 :add [4] 5
print cascade 3 :add [4] 5

will result in:

[make action! [[
        "Returns the addition of two values."
        value1 [scalar! date!]
        value2
    ]] 4 make action! [[
        "Returns the addition of two values."
        value1 [scalar! date!]
        value2
    ]] 4 make action! [[
        "Returns the addition of two values."
        value1 [scalar! date!]
        value2
    ]] 4 5]

17

and

probe cascade 8 :multiply [2] 1
print cascade 8 :multiply [2] 1

Will result in:

[make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 make action! [[
        "Returns the first value multiplied by the second."
        value1 [scalar!]
        value2 [scalar!]
    ]] 2 1]

256