Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Loopless Programming

code.jsoftware.com

Post reply on HN
Print view View original

101–110 of 129 posts

Re: Loopless Programming

#101

Post by kragen »

lgas wrote: post #96
kragen wrote: post #91

Earlier quoted context omitted.

While this code is awesomely mindbending, it does seem to be limited to a 20×20 grid, rather than being applicable to grids of any size. Also, and correct me if I'm wrong here, it looks like it would take more than 5 minutes to write. The more interesting aspect, though, is that it seems to be organized in an almost totally different way from the APL code. I suggest that this is largely because the two languages fost…

It doesn't have to be a finite grid. Here is another comonadic implementation of Life with an infinite board: https://github.com/BartoszMilewski/GameOfLife/blob/master/Li... Either version would definitely take me more than five minutes to write, but then again it would take me more than five minutes to write the APL version too. For someone like Penner or Milewski the comonadic Haskell versions might be achievable i…

Thank you very much for posting both of these awesome links!

Re: Loopless Programming

#102

Post by manmal »

Swift provides many of the required Collection operators to go loopless - map, reduce, flatMap, compactMap (eliminate nil values), filter, first, contains, prefix/suffix, ... there’s even an OSS library that gives a compile time guarantee that a Collection is non-empty.

There are only some instances where I ever need a loop:

- map cannot produce a Dictionary, so Dictionary manipulations usually require a loop

- Sometimes, a more complex qualifier or stopping condition is needed. Like striding through a Collection in a non-linear way.

Re: Loopless Programming

#103

Post by kbbr »

Unless you can leverage special instructions / hw to realize your array operations, loops will be the fundamental operations generated by the compiler executed by the CPU. For a lot of scenarios, loopless code is surely more expressive. However, I would not say that it is per se in any kind superior. Rather, it is a feature of each language, how much to abstract from the actual CPU instructions.

So to have fine granular control over your generated code, classic loops in C always relevant, while a simple array operation can be expressed in such high level way for other use cases.

Re: Loopless Programming

#104

Post by ridiculous_fish »

First I've heard of J! Say you want to compute the product of integers in a list. Should you encounter a zero, you can exit immediately since the product is known. In C this would be an `if (arr[i] == 0) break`. How would one express this in J's loopless style?

Re: Loopless Programming

#105

Post by Athas »

Last time I did APL programming I was a bit bothered by the performance implications of some of the standard loopless programming styles. In particular, it's hard to nest loops.

As an example of the implications, consider computing the Mandelbrot set. I'll be using Numpy here to ensure people can follow what I'm doing, but for the point I wish to make, it's similar to how you'd write it in APL. The Mandelbrot set is compute by applying a function like this to each of a bunch of complex numbers:

  def divergence(c, d):
    i = 0
    z = c
    while i
To apply this to many points simultaneously in a vectorised "loopless" style, we'd write it like this:

  def mandelbrot_numpy(c, d):
      output = np.zeros(c.shape)
      z = np.zeros(c.shape, np.complex32)
      for it in range(d):
          notdone =
            np.less(z.real*z.real + z.imag*z.imag,
                    4.0)
          output[notdone] = it
          z[notdone] = z[notdone]**2 + c[notdone]
      return output
There is just one `for` loop, which is pretty easy to do in APL. The `while` loop has been subsumed into control flow encoded in boolean arrays. This is not exactly how you'd do in APL, but it has a similar feel. It's also pretty slow, because we are manifesting the entire `z` array in memory for every iteration in the outer loop. In contrast, an old school loop over every point, with an inner while loop for every point, would involve only two memory accesses per point. On a GPU, I have measured the vectorised style to be about 30x slower than one with a conventional `while` loop.

Re: Loopless Programming

#106

Post by dorian-graph »

manmal wrote: post #102

Swift provides many of the required Collection operators to go loopless - map, reduce, flatMap, compactMap (eliminate nil values), filter, first, contains, prefix/suffix, ... there’s even an OSS library that gives a compile time guarantee that a Collection is non-empty. There are only some instances where I ever need a loop: - map cannot produce a Dictionary, so Dictionary manipulations usually require a loop - Somet…

> - map cannot produce a Dictionary, so Dictionary manipulations usually require a loop

Assuming you meaning mapping over a list, some sort of fold function could produce a dictionary, in some languages, such as Elm. [1]

[1] https://package.elm-lang.org/packages/elm/core/latest/List#f...

Re: Loopless Programming

#107

Post by regularfry »

Athas wrote: post #105

Last time I did APL programming I was a bit bothered by the performance implications of some of the standard loopless programming styles. In particular, it's hard to nest loops. As an example of the implications, consider computing the Mandelbrot set. I'll be using Numpy here to ensure people can follow what I'm doing, but for the point I wish to make, it's similar to how you'd write it in APL. The Mandelbrot set is…

In theory you could escape that by using generators rather than explicitly creating the intermediate list. No idea if J does that under the covers though.

Re: Loopless Programming

#108

Post by bouncycastle »

jameshart wrote: post #20

Most programmers have worked in a largely loopless programming language: SQL. IT lets you easily build the same sort of ‘Boolean state for every item’ as this discusses, but it requires you to be much more explicit about which items you want to line up next to one another if you’re joining two lists together. In modern languages we usually just use mapreduce like functional approaches to handle the same sort of thing…

I believe it's called Declarative Programming. Prolog comes to mind as well. https://en.wikipedia.org/wiki/Declarative_programming

Re: Loopless Programming

#109

Post by flexblue »

Quote:

"(x + y) is an expression rather than a statement. The J programmer can embed (x + y) in a larger expression, perhaps a matrix multiplication (w +/ . * (x + y)) which adds the equivalent of three more nested loops, but is still a single expression. Expressions can be combined; statements cannot."

What about an expression like (x * x + y * y)? This would still be a single loop in C. Is J smart enough to figure that out, or will it turn that into three loops?

Re: Loopless Programming

#110

Post by wffurr »

tom_mellior wrote: post #95
wffurr wrote: post #40

Earlier quoted context omitted.

You described the GPs point perfectly. This is also covered in the article; it exhaustively covers the use cases for loops and provides higher level functions and operators instead.

It covers the use cases for loops over arrays/lists, not over more general graph-like structures.

For which there exist a slew of higher order graph traversal algorithms.
Post reply on HN