[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Lambda recursions on the example of generating permutations

From: Robin Haberkorn
Subject: Re: Lambda recursions on the example of generating permutations
Date: Wed, 5 Apr 2023 02:24:55 +0300
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.7.1

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


      foo ← {⎕ ← ⍵}
      (foo "FOO") ⊢[1] 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 

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

Doing nothing. And

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

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

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,

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]