Re: Lambda recursions on the example of generating permutations

[Robin Haberkorn]

Hello Jürgen,

04.04.23 17:58, Dr. Jürgen Sauermann пишет:
> ... A language does not necessarily get better as the number of its features grows 
> (see PL/I or Ada).
Totally agree. I am a language minimalist myself. Many languages suffer from 
what I call "feautureitis", ie. trying to stuff as many as possible features, 
esp. programming paradigms, into the language. As a result, many programmers do 
not fully comprehend their languages and code tends to become idiosyncratic.

> ∘ 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.
Well, I think that the non-recursive version of Perm is still acceptable, 
although I would usually avoid these assignments in the middle of the 
expression. Let's see whether I can still understand it in a month. It's only 
the second time I am using APL semi-seriously, so I am still trying to find the 
right balance.

> ∘ 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.
Their attraction, I think, comes from their brevity compared with traditional ∇ 
functions.

> ∘ 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.
I also had this thought. And yes, it's probably pointless to introduce multiline 
lambdas, as long as they have the exact same semantics as ∇ functions. Also, it 
would just propagate the Computed-Goto style of control flow. So let's discard 
this idea.
(On a side note, it in general wouldn't hurt to have a way to break lines - 
escape line breaks - in APL statements. I don't know what other dialects did in 
this regard.)

> ∘ Gnu actually has a built-in If/Else constructor (i.e. ⊢ with axis):
> ...
That's very nice to know. I overlooked that possibility. It certainly lends to a 
nicer idiom than (A B)[1+C].
It also seems that calls in APL expressions are lazily evaluated and ⊢[] 
therefore has some "short-circuit" semantics:

      foo ← {⎕ ← "FOO"}
      foo ⊢[1] 23
23

However:

      foo ← {⎕ ← ⍵}
      (foo "FOO") ⊢[1] 23
FOO
23

So what's going on here? If ⊢ would really lazily evaluate both of its sides, 
that would be a viable control flow construct, not only for lambdas.
I don't know if any rules of standard APL prohibit general lazy evaluation, but 
at least in combination with the extended ⊢, there would be little to loose.

> 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).

I also cannot get the second syntax to work in Dyalog (using the Linux CLI 
version). But they in general do not allow multiline lambdas in immediate 
execution mode (the REPL). ⋄ is allowed in lambdas, but I cannot get the :If to 
work either. Perhaps they only support lambda guards?
> ∘ 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.
> ...

It actually means something different. A symbol should only be visible in the 
scope it was declared. But that's irrelevant here. I didn't express myself 
precisely enough. What I actually meant is that lambdas should be closures 
(enclose the references to local variables from the enclosing scope) in order to 
be of use for flow control in any way. And it seems they are in GNU APL! What 
makes them hard to use for flow control is the lack of appropriate operators.
Let's say, you would like to use power ⍣ as a "structured" If-Statement.
The left operand ⍶ needs to be at least monadic, so you end up with a very 
clumsy

  ⊣{⎕ ← "FOO" ⊣⍵}⍣0 ⍬

Doing nothing. And

  ⊣{⎕ ← "FOO" ⊣⍵}⍣1 ⍬
FOO

But it does work. We can even abuse it as an If-Else (similar to C's ?: 
operator) if we are fine with the right side always being evaluated as it is 
returned if you apply ⍶ 0 times:
({T⊣⍵}⍣C) F
This lazily evaluates to T if C=1 and F otherwise.

Now we can rephrase our little "beast" Perm:

Perm ← {{↑,/⍵,¨¨⍵+(K-1) Perm¨N-⍵}⍣(K>1) ⍳1+(N←⍵)-K←⍺; K; N}

Nice. I like that. It can even coincidentally make use of the array being passed 
into the inner lambda.
Of course, for a more general short-circuit IfElse, we could easily define an 
operator:

∇R ← (IfBranch IfElse ElseBranch) Cond
  →Cond/3
  R ← ElseBranch ⋄ →0
  R ← IfBranch
∇

Which can now be happily used everywhere, including in lambdas:

Perm ← {{↑,/X,¨¨X+(K-1) Perm¨N-X} IfElse {X} K>1 ⊣ X←⍳1+(N←⍵)-K←⍺; X; K; N}

Except, that it does not work. And I am quite clueless why...

Best regards,
Robin

> 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.