Re: Lambda recursions on the example of generating permutations

[Dr . Jürgen Sauermann]

Hi Robert,

I have quite a few thoughts when in comes to lambdas, in particular named lambdas and multi-line lambdas. The limitations that you see are primarily caused by concerns that otherwise APL would develop into a non-APL direction. A language does not necessarily get better as the number of its features grows (see PL/I or Ada).

∘ lambdas are only elegant if they are short and obvious. Beast like Perm below are IMHO neither elegant nor readable. Brevity alone does not imply elegance, in particular not if overdone.

∘ named lambdas are contradictions in themselves. Also. recursion and nameless functions do not play well together because the recursion has to refer to itself in some way.

 ∘ The semantics of lambdas (as defined by Dyalog, chapter 8 of the Dyalog book) is not consistent with the rest of APL. For example (I will use ◊ to indicate end of line to kept things short):

Z←1 ◊ Z←2 ◊ Z←3     ⍝ sets Z to 3.

In Dyalog multi-line lambdas (using λ← to indicate the result):

    λ←1 ◊ λ←2 ◊ λ←3     ⍝
        sets λ to 1 and returns (!).

Also, local variables are handled differently than proper ∇-defined functions.

In contrast, GNU APL lambdas declare local variables in the same fashion as in proper ∇-functions:

      ⊣{ E←(D+1),⍪D←1 2 3;D }
      )VARS
E

All in all I would argue that having the same execution semantics for lambdas and for their proper ∇-function companions is far better than not. Implementation-wise  it is not too difficult to provide multi-line lambdas, but the implementation options to choose from are then: to adopt a bad solution as to maintain compatibility with Dyalog, or else to do it properly but become incompatible with Dyalog. Due to these complications I decided to drop multi-line lambdas entirely.

∘ What exactly is the advantage of a multi-line lambda compared to a proper ∇-function? Is A←{...} that much better than ∇A ... ∇ ? I rather doubt so.

∘ Gnu actually has a built-in If/Else constructor (i.e. ⊢ with axis):

     'foo' ⊢[0] 'bar'
foo
      'foo' ⊢[1] 'bar'
bar

    The if/else condition X
    is the axis and the alternatives are the left and right arguments of A ⊢[X] B.
    
    If I compare the alternatives:
    
    { 'foo' ⊢[⍵] 'bar' }
        { :If ⍵ ◊ 'foo' ◊ :Else ◊ 'bar' ◊ :Endif }   ⍝ ◊ shall mean
        CR/LF
     
    thenn the first one convinces me more. Also, the second seems to
    work only in proper ∇-functions but not in Dyalog lambdas (at least
    I could not figure how in tryapl.org).
    
    ∘ lexical scoping: If I understand this term correctly then it means
    that local variables of a function are not visible in sub-functions
    called by it. From an APL point of view I consider that a limitation
    rather than an advantage. In APL it is the called function that
    decides which variables are local (and thus hide the non-local ones)
    while in lexical scoping it is the calling function that hides them.
    One can argue which one is better, but having both is IMHO the worst
    solution. As a C/C++ programmer I am used to lexical scoping by
    default, but I never missed it in APL.
    
    There is another GNU APL feature, dyadic → (aka. relative jumps
    similar to monadic  →N+↑⎕LC), that need no labels and
    therefore not only works in defined functions but also in immediate
    execution mode. I am not advertising it much because I believe that
    all APL extensions will sooner or later fire back (lambdas being one
    example). In A → B is B the
    branch condition and A the offset from the current line (negative to
    branch backwards.
    
    
    Best Regards,
    Jürgen

On 4/3/23 20:12, Robin Haberkorn wrote:

> Hello
>       everybody, 
>       
>       I stumbled across an interesting little problem. I would like to
>       generate all possible combinations of taking ⍺ things from a total
>       of ⍵. The number of possible combinations is consequently ⍺!⍵. 
>       
>       Here's a straight-forward "brute force" solution: 
>       
>       Perm ← {(X/⍨⍺=+/¨X←(⊂2⍴⍨⍵)⊤¨⍳2*⍵) /¨ ⊂⍳⍵; X} 
>       
>             2 Perm 4 
>        3 4  2 4  2 3  1 4  1 3  1 2 
>             3 Perm 4 
>        2 3 4  1 3 4  1 2 4  1 2 3 
>       
>       Unfortunately the algorithm has O(2^⍵) time and space complexity.
>       Which is okay for what I am using it, but I was still curious of
>       how this could be solved recursively in a lambda. I feel that
>       simple things like this should have elegant solutions in GNU APL.
>       Unfortunately this is the best I could come up with: 
>       
>       Perm ← {⍎∊('↑,/X,¨¨X+(⍺-1) Perm¨⍵-X' 'X')[1+⍺≤1] ⊣ X←⍳1+⍵-⍺; X} 
>       
>       At this point I was really feeling the limitations of lambdas in
>       GNU APL. There apparently aren't enough means of control flow. At
>       least I couldn't find a way to utilize one of APL's operators
>       elegantly for this purpose, so I fell back to a computed ⍎, which
>       feels really clumsy and is probably quite slow as well. 
>       
>       Or you write a traditional ∇ function with →... I mean you could
>       also write your own ⍶IfElse⍹ operator, but due to the lack of
>       lexical scoping this would be pretty useless for recursion, unless
>       you pass in your context as ⍺ or ⍵ which is again very clumsy. 
>       
>       I would therefore claim that we are either lacking lexical scoping
>       and/or built-in structured If-Else constructs. Or lambdas should
>       simply be allowed to contain ⋄, new lines and →. Or I am missing
>       something obvious. I am not sure. But IMHO something fundamental
>       is missing in the language. 
>       
>       I am interested in hearing your thoughts. 
>       
>       Yours sincerely, 
>       Robin 
>       
>       PS: I am not saying "I want it like in Dyalog!!!11". GNU APL is
>       great for what it is and I am not ready to switch over to Dyalog
>       yet. I particularly like two things about GNU APL: 1) It's FREE
>       software. 2.) It's more conservatively designed than Dyalog. 
>       
>       
>