4 ms·

It requires a different mindset. You might not need leap year calculation often, but many things you do have a short, simple, efficient J/K/APL implementation e

It requires a different mindset. You might not need leap year calculation often, but many things you do have a short, simple, efficient J/K/APL implementation entirely different from how you’d do it in other languages. E.g. to check if a text string s has balanced parantheses in C/Java/Python, you would have a loop to increase/decrease depth based on character, error if negative at any point, and balanced if zero at end. In k, you would compute the running balance at each point b:+\(s=“(“)-(s=“)”) And then check the minimum of it &/b to see if it is negative, and the last element *|b To see if it is zero. This is a text parsing problem, but has an elegant vector solution. Most things do, whether it is graphics, database, whatever - but it’s rarely intuitive if you are not used to thinking in vectors. Also, the expression for b above can be half as long, but you would really need to be versed in k to understand it.

chongli 7y ago
That’s a very trivial example though. For a more real-world example, consider multiple different delimiters for matching. The C/Java/Python version is still trivial if you use a stack instead of a numeric counter, returning an error if you try to pop an empty stack or one whose top element does not correspond to the delimiter you’re matching. How would you do this in K?
- beagle3 7y ago
  The stack makes it much less trivial than a counter in Python, and even less so in e.g. C which lacks a built in data type useful as a stack (leading many to allocate a fixed size stack and either reject valid strings going too deep or have buffer overflows) Indeed, a multi delimiter version is harder in K as well. I am writing this on a phone without K (as I did the prev post) so will not attempt a runnable example; but, I would implement it as a state machine, taking Stack and one char as input; and returning new stack as output; then reducing it on s; if final stack is empty, it is valid. It would still be one line. K loves state machines. When tokenizing/parsing in K, you’ll often see people write DFA tables by hand because it turns out to be simpler than writing a lex spec; also shift/reduce tables because it is simpler than yacc grammars. I would not recommend these if you want to write a C++ compiler, or you need yacc’s error reporting and recovery. But 95% of the time, yacc/lex are for simple calc or DSL expressions that ARE easier to code by hand in K. And that’s another place K/APL mindset differs significantly from common practice: Avoid solving the general form of your problem if you can solve the particular one in one line (which you often can, and is often enough)
  - chongli 7y ago
    It’s not very hard to code up a dynamically allocated stack in C. I think it’s of fundamental importance for a programming language to let you easily implement lots of different data structures efficiently. Are you saying K has a stack built-in (or another structure that can easily implement a stack)? Okay then how about a problem for which K lacks a built in data structure? I would google it myself but I can’t seem to get any results on K.
    - beagle3 7y ago
      K has lists somewhat comparable to Python’s, which is what i’d use to implement a stack in either (append to push, shorten/pop to pop) You are moving the goalposts. You can construct problems where eventually K cannot be shorter/simpler - this is a consequence of Turing equivalence and kolmogorov complexity. The claim I made was that, for problems that people actually need to solve, K And APL often have a short, simple, elegant and usually performant solution. I stress that I am talking about the actual problems - that is, creating a mapping from an input set to a respective output set - I am NOT claiming that the solutions people reach for in language $x can be expressed more elegantly in K/APL. Another example is “flatten” - expressed as ,// in K, and which could be read “join over until-converged”. This is not how you would implement it in Lisp or Python likely - and it is likely less efficient at runtime than how you WOULD implement it in Lisp. But it is arguably short, simple, elegant and (depending on implementation and input structures) likely acceptably efficient. Added p.s: it is not hard to code a dynamically allocated stack in list, but it is about as complicated as checking the balance, which makes the balanced parentheses problem twice as complicated in C compared to even Python; which is why so many C buffer overflows exist - the buffer Management was accidental Complexity and therefore gets less attention than the security implications of a buffer overflow would warrant.
      - chongli 7y ago
        The reason I'm asking about further problems is not because I want to "move the goalposts" but because I (and likely other people) are skeptical about the ability of K (and other APL family languages) scale beyond simple problems or specific niches (such as finance). It's fine if it can't though. Different languages have different niches. You wouldn't write an operating system in python. I'd just like to know if there is a use case for K outside of finance (or other sorts of math on large data sets). Has anyone written a video game in K?
clarry 7y ago
Will the vector solution thing still be elegant if parentheses that are escaped with a backslash don't count? Oh, and backslashes can also be escaped, so the paren in "\\(" still counts. Oh and you can have a quoted segment in the string where parens don't count. As expected, quotes can be escaped.. I bet there are elegant solutions, and perhaps they are obvious to those who are well versed in array programming. What I think the world needs is a book/tutorial/whatever that demonstrates elegant solutions to things that seem ugly and not amenable to vector processing (at least in the obvious and naive way). I think we have enough (too many) tutorials showing how to calculate means and such :(
- beagle3 7y ago
  Elegance is in the eye of the beholder, of course - a state machine is easier to code in K than in almost any other language, and is likely the most elegant overall solution. A common kludgy solution you’d see would probably be to delete or zero out characters that shouldn’t be counted, and then do the original thing; some would consider that elegant and others won’t. There are many examples if you look for them, many well explained, e.g. https://nsl.com https://nsl.com ; the problem is APL/K is almost as different from C/Java as Japanese is from English ; there’s no amount of chewing anyone will do for you that will save you from going deep, and if you’ve decided to go deep, the material is already available.
  - clarry 7y ago
    Sounds good, I love state machines and I often write them in C where other people would just go with ad-hoc loops and branches and temporaries. I'll keep an eye out for examples..
    - avmich 7y ago
      Recently there was a link on simdjson, a C++ parser for JSON which aims to be record fast. It uses vector instructions of modern processes, but if you'll watch the video presentation, Daniel Lemire will also explain how they handle finding string boundaries - with all those escapes needed - without branching, purely logical operations. Could be a good example for how APL approaches things.
mamcx 7y ago
I'm interested in this are (building a toy relational lang with array capabilities) and one are I have not find example is CRUD apps. How exactly a simple todo or invoice work here?
- beagle3 7y ago
  I don't have a crud example off hand, but https://nsl.com/ https://nsl.com/ has a lot of examples - chat server/client, instant messenger, spreadsheet, class tracker, 15-puzzle, calculator, raytracer, pivot tables, and more. You may like http://nsl.com/k/t.k http://nsl.com/k/t.k - a 14 line in-memory, quite efficient, relational-style database (no parser, just the ops). Note most of nsl is k2/k3 ; the differences aren't huge, but if you dig deep it helps to know which version you're reading.

chongli 7y ago

That’s a very trivial example though. For a more real-world example, consider multiple different delimiters for matching. The C/Java/Python version is still trivial if you use a stack instead of a numeric counter, returning an error if you try to pop an empty stack or one whose top element does not correspond to the delimiter you’re matching. How would you do this in K?

beagle3 7y ago
The stack makes it much less trivial than a counter in Python, and even less so in e.g. C which lacks a built in data type useful as a stack (leading many to allocate a fixed size stack and either reject valid strings going too deep or have buffer overflows) Indeed, a multi delimiter version is harder in K as well. I am writing this on a phone without K (as I did the prev post) so will not attempt a runnable example; but, I would implement it as a state machine, taking Stack and one char as input; and returning new stack as output; then reducing it on s; if final stack is empty, it is valid. It would still be one line. K loves state machines. When tokenizing/parsing in K, you’ll often see people write DFA tables by hand because it turns out to be simpler than writing a lex spec; also shift/reduce tables because it is simpler than yacc grammars. I would not recommend these if you want to write a C++ compiler, or you need yacc’s error reporting and recovery. But 95% of the time, yacc/lex are for simple calc or DSL expressions that ARE easier to code by hand in K. And that’s another place K/APL mindset differs significantly from common practice: Avoid solving the general form of your problem if you can solve the particular one in one line (which you often can, and is often enough)
- chongli 7y ago
  It’s not very hard to code up a dynamically allocated stack in C. I think it’s of fundamental importance for a programming language to let you easily implement lots of different data structures efficiently. Are you saying K has a stack built-in (or another structure that can easily implement a stack)? Okay then how about a problem for which K lacks a built in data structure? I would google it myself but I can’t seem to get any results on K.
  - beagle3 7y ago
    K has lists somewhat comparable to Python’s, which is what i’d use to implement a stack in either (append to push, shorten/pop to pop) You are moving the goalposts. You can construct problems where eventually K cannot be shorter/simpler - this is a consequence of Turing equivalence and kolmogorov complexity. The claim I made was that, for problems that people actually need to solve, K And APL often have a short, simple, elegant and usually performant solution. I stress that I am talking about the actual problems - that is, creating a mapping from an input set to a respective output set - I am NOT claiming that the solutions people reach for in language $x can be expressed more elegantly in K/APL. Another example is “flatten” - expressed as ,// in K, and which could be read “join over until-converged”. This is not how you would implement it in Lisp or Python likely - and it is likely less efficient at runtime than how you WOULD implement it in Lisp. But it is arguably short, simple, elegant and (depending on implementation and input structures) likely acceptably efficient. Added p.s: it is not hard to code a dynamically allocated stack in list, but it is about as complicated as checking the balance, which makes the balanced parentheses problem twice as complicated in C compared to even Python; which is why so many C buffer overflows exist - the buffer Management was accidental Complexity and therefore gets less attention than the security implications of a buffer overflow would warrant.
    - chongli 7y ago
      The reason I'm asking about further problems is not because I want to "move the goalposts" but because I (and likely other people) are skeptical about the ability of K (and other APL family languages) scale beyond simple problems or specific niches (such as finance). It's fine if it can't though. Different languages have different niches. You wouldn't write an operating system in python. I'd just like to know if there is a use case for K outside of finance (or other sorts of math on large data sets). Has anyone written a video game in K?

clarry 7y ago

Will the vector solution thing still be elegant if parentheses that are escaped with a backslash don't count? Oh, and backslashes can also be escaped, so the paren in "\\(" still counts. Oh and you can have a quoted segment in the string where parens don't count. As expected, quotes can be escaped.. I bet there are elegant solutions, and perhaps they are obvious to those who are well versed in array programming. What I think the world needs is a book/tutorial/whatever that demonstrates elegant solutions to things that seem ugly and not amenable to vector processing (at least in the obvious and naive way). I think we have enough (too many) tutorials showing how to calculate means and such :(

beagle3 7y ago
Elegance is in the eye of the beholder, of course - a state machine is easier to code in K than in almost any other language, and is likely the most elegant overall solution. A common kludgy solution you’d see would probably be to delete or zero out characters that shouldn’t be counted, and then do the original thing; some would consider that elegant and others won’t. There are many examples if you look for them, many well explained, e.g. https://nsl.com https://nsl.com ; the problem is APL/K is almost as different from C/Java as Japanese is from English ; there’s no amount of chewing anyone will do for you that will save you from going deep, and if you’ve decided to go deep, the material is already available.
- clarry 7y ago
  Sounds good, I love state machines and I often write them in C where other people would just go with ad-hoc loops and branches and temporaries. I'll keep an eye out for examples..
  - avmich 7y ago
    Recently there was a link on simdjson, a C++ parser for JSON which aims to be record fast. It uses vector instructions of modern processes, but if you'll watch the video presentation, Daniel Lemire will also explain how they handle finding string boundaries - with all those escapes needed - without branching, purely logical operations. Could be a good example for how APL approaches things.

mamcx 7y ago

I'm interested in this are (building a toy relational lang with array capabilities) and one are I have not find example is CRUD apps. How exactly a simple todo or invoice work here?

beagle3 7y ago
I don't have a crud example off hand, but https://nsl.com/ https://nsl.com/ has a lot of examples - chat server/client, instant messenger, spreadsheet, class tracker, 15-puzzle, calculator, raytracer, pivot tables, and more. You may like http://nsl.com/k/t.k http://nsl.com/k/t.k - a 14 line in-memory, quite efficient, relational-style database (no parser, just the ops). Note most of nsl is k2/k3 ; the differences aren't huge, but if you dig deep it helps to know which version you're reading.