No Stinking Loops | Hacker News Reader

No Stinking Loops

nsl.com

70 pointssurprisetalk38 comments

Hoping the nsl site maintainer happens upon this discussion...

> A Lazy K (No, not that one)

That link is broken since I had to give up my homepage at CWI. It's now located at https://tromp.github.io/cl/lazy-k.html

> A Ray-Tracer in 7 Lines of K

And here's a number greater than Graham's in 7*7 bits of binary lambda calculus [1]:

    ┬─┬ ┬─┬──────────
    └─┤ │ │ ──┬──────
      │ │ │ ┬─┼──────
      │ │ │ └─┤ ┬─┬──
      │ │ │   │ ┼─┼─┬
      │ │ │   │ │ ├─┘
      │ │ │   │ ├─┘  
      │ │ │   ├─┘    
      │ │ ├───┘      
      │ ├─┘          
      └─┘

[1] https://codegolf.stackexchange.com/questions/6430/shortest-t...

Is there any context that could help understand wtf I’m looking at?

Is this a collection of resources that promote using things other than loops while programming?

Are we advocating for a world without physical loops, eg. Rollercoasters without loops?

array-based programming languages. APL, J, K, etc.

Supposing I'm "Joe HN User". I've worked with both Lisp and Numpy. How do array-based programming languages relate? Are they just syntactic sugar for things I could already do in Lisp/Numpy, or is there something more?

I suppose if you took numpy and got rid of the python (so ... "num"?) and built a language around that it would be the same idea.

Thank you!

As a slight tangent to your question- kdb/Q works beautifully with numpy, it’s very useful being able to work with numpy from the q prompt and pass objects between the environments.

Work with numpy from q or q from python? I'm not sure why you'd use numpy when you have access to k/q, they're much nicer.

It looks K-centric. The K language provides constructs like each, over, and scan to perform what would be looping behavior in other languages.

Having written Scala myself at one point, the thought of a loop-less language crossed my mind. It's amazing what you can accomplish with foldLeft and recursion schemes.

Elm doesn't have loops, just fold/map.

Elm can do iterative recursion, which is a thinly disguised loop without side effects.

I googled "iterative recursion " and couldn't find a definition. So is it judt iteration? And then, what languages don't have iteration?

Aren’t those things just convenience wrappers around loops? I don’t understand the fundamental difference.

They're loops with stronger semantics (in other words, they're more restrictive (in other words, they're easier to reason about)), in the same way that loops themselves are `goto` with stronger semantics.

> they're more restrictive (in other words, they're easier to reason about))

That's a great point. Often in my programming career, I've used the rule of least power[1]. In the looping/flow control ladder, I'd list descending

* JMP/GOTO

* for/while

* map/filter/reduce

If a problem only needs a map, using a for introduces needless complexity(ie: state). Personally, I think we have a pedagogical problem in that we teach people loops first and people confuse what they've been taught first with what is a reasonable choice[2].

For completeness, recursion has it's own ladder

* PUSH,POP,JMP

* function call

* recursion schemes[3]

Side note: recursion schemes have an enormous hurdle to adoption in that mathematicians got there first and the naming are so off putting that no one will take you serious if you bring up even simple schemes like anamorphism and catamorphism. Folks would rather accept a FactoryFactoryFactory over a futumorphism.

1. https://en.wikipedia.org/wiki/Rule_of_least_power

2. The other side of this coin is, "Why would they teach me a bad way of doing something?"

3. https://github.com/passy/awesome-recursion-schemes

Viewing loops as a stronger GOTO is a really interesting perspective which makes sense to me, thanks for the insight.

I see them as a restricted (so, less powerful than a goto). That’s why they are better. Perhaps that’s what you meant when you said “stronger”

When loopless constructs are a design principle of a language, they become much more than just a convenience wrapper.

Aren’t loops just wrappers around goto and if statements?

The claim is that by expressing programs in terms of these array primitives, you (a) can have those primitives be super optimised and (b) better see what the program is actually about without worrying too much about eg what names to give all the loop counters, all the other intermediate state associated with iteration, etc.

Most platforms make some kind of loop into a primitive, but in Common Lisp

  (dotimes (i 10)
    (print i))

is just a predefined macro that might expand into primitives like

  (BLOCK NIL
    (LET ((I 0))
      (TAGBODY
        #:LOOP-2867
        (IF (>= I 10)
          (GO #:END-2868))
        (PRINT I)
        (PSETQ I (1+ I))
        (GO #:LOOP-2867)
        #:END-2868
        (RETURN-FROM NIL (PROGN NIL)))))

Sure, and C is a convenience wrapper around assembly and assembly is a convenience wrapper around toggling octal codes on your front panel and punching in octal code is a convenience wrapper around rewiring vacuum tubes and relays and that's a convenience wrapper around mechanical cogs and that's a convenience wrapper around an abacus.

But it's a different paradigm than procedural programming and embracing it might lead to a different mind set.

Lol. IMO the difference between an C and Assembly (as between vacuum tubes and the abacus) is really a difference in power, since it allows the same program to be implemented on different architechtures. It's only fair to start calling things convenience wrappers once you get past C. And often enough, an abstraction aimed at convenience leads to a reduction in expressive power.

Loops (Eg: in C) are a much “wilder” construct — something special could happen for i=17 or successive iterations might overwrite values, etc. more restrictive “tamer” versions help programmers & computers reason about the code.

Loops themselves can be considered just convenient wrappers around goto. The point is to restrict the variety (structured programming) and make spaghetti unreadable code less likely.

Using higher-order functions instead of loops is similar e.g. loops:

    # input_ =  "1,2,3"
    numbers = (int(d) for d in input_.split(","))
    product = 1
    for n in numbers:
        product *= n

can be replaced:

    numbers = map(int, input_.split(","))
    product  = reduce(mul, numbers, 1)

each is a necessary evil of K. It can often be avoided by more thoughtful use of vectors.

I would claim that SQL is the ubiquitous loop-less language.

Once you get into it, you start realizing what manipulating data is all about. And most of what you need can be expressed without for loops. And then the step from SQL to Scala is not long.

For me imperative languages are like Lego. SQL is like origami. You fold yourself to the solution.

That said, K is obviously one step further in that analogy.

Primarily K focuses on applying functions to vectors. If using “each” can be avoided, it is.

It’s a wonderful language to work with.

It promotes array languages, where operator symbols indicate actions on an n-dimension array (0 = scalar, 1 = vector, 2 = array, etc.)

As a trivial example, A + B means the element-wise addition two arrays, rather than use looping to compute the terms yourself.

The original array language is APL, which is also known for using its own non-ASCII notation. https://en.wikipedia.org/wiki/APL_(programming_language) . To give you a sense of what I mean, the implementation of the Game of Life is:

  life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

Compare that to how you might implement GoL as a couple of for-loops, with a hard-coded count of the 3x3 neighbor grid. But why use stinking for-loops when you express what the result you want directly, tersely, so you can able see the whole program at once?

(OTOH, as I recall, that implementation uses a fixed-width array, which highlights a limitation to using that approch. For GoL you really want to use Hashlife, which isn't so amenable to an array approach.)

Many of the links here reference K, a descendant of APL which uses ASCII.

> life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

Must be fun to type that...

I copied it from the Wikipedia page, which also shows a layout for an APL keyboard and has a picture with the mechanisms to get your typewriter/printer to handle it.

Is there an implementation of an APL-like language which transpiles to SIMD operations at the instruction set level?

A DDG search for "apl simd" finds https://aplwiki.com/wiki/Performance as the first match:

"APL's array operations are also ideal for implementation with SIMD, or "single instruction, multiple data", operations, that perform a single action on several different values. In some cases, such as scalar functions, the primitives are SIMD operations; in others such as Reverse, they are easily implemented using SIMD—for Reverse, SIMD selection or "shuffle". While experimental SIMD machines (such as the APL-influenced CDC Star-100) were created as early as the 1960s, SIMD computing first entered the personal computing mainstream in the 1990s and has steadily grown in prominence for high-performance computing since then. In APL, CPU vector instruction sets such as Intel's SSE are the most often way to access SIMD optimization, although Co-dfns instead runs on a GPU to attain much higher throughput at the cost of increased overhead and restriction of available algorithms."

Thank you.

Yes, k

Weird name for a site whose first content is a looping gif

But the wolf isn’t farting. Key word is stinking. Checks out.

Dogs are famous for being tail-recursive

Also stumbled across an old column with that name looking at another front page topic https://news.ycombinator.com/item?id=38666287 which links to

> a new occasional column “No Stinking Loops” by the legendary Stevan Apter

here: http://archive.vector.org.uk/art10500340

Reply on news.ycombinator.com