bug-apl
[Top][All Lists]

## Re: Lambda recursions on the example of generating permutations

 From: Dr . Jürgen Sauermann Subject: Re: Lambda recursions on the example of generating permutations Date: Tue, 4 Apr 2023 16:58:30 +0200 User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.9.0

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.