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

Impending kOS

archive.vector.org.uk

Post reply on HN
Print view View original

231–240 of 242 posts

Re: Impending kOS

#231

Post by robryk »

beagle3 wrote: post #228
robryk wrote: post #221

Earlier quoted context omitted.

How would you represent a graph and implement DFS in K?

If you are really interested, http://nsl.com/ is a treasure trove - quite a few of the examples are extremely well documented, some or not, but there's a wealth of information there. Specifically about graphs, you can look at: http://nsl.com/papers/order.htm - topological sorting http://nsl.com/k/tarjan.q - strongly connected components http://nsl.com/k/loop.q - find loops in graphs I think in all of these the graph…

Thanks, I've missed the SCC one. I will try to understand it. (The reason I've asked about DFS in particular is that it is inherently sequential. This SCC algorithm probably encapsulates some kind of DFS.)

Re: Impending kOS

#232

Post by geocar »

dragonwriter wrote: post #216
geocar wrote: post #209

Earlier quoted context omitted.

The view automatically gets updated whenever a gets updated. Every time you change a (directly or indirectly), then c will automatically get updated. Doing this generally in Ruby I think is impossible, but you might be able to get close if all your objects are based on ActiveModel::Dirty

> Doing this generally in Ruby I think is impossible Not so much. At least with views over most Enumerables, its quite possible in Ruby -- that's the whole reason that Enumerable::Lazy exists. The existing File class doesn't quite support it because of the way its iterators are implemented (particularly, they are one way) but the class is easily extended to allow it, e.g.: class RewindFile Then you can create a synce…

If I go `a=whatever` or `a[42]=whatever`, then `c` will not get updated if I have already consumed those values; I still need to "reset" c every time I update a.

Re: Impending kOS

#233

Post by avmich »

tubular wrote: post #226
avmich wrote: post #166

Earlier quoted context omitted.

In J there are two special ways to combine functions which are written using special syntax. Namely, 1) when you want to calculate f(y, g(y)) , you write (f g) y - this is "hook" of one argument (monadic, in J terms) 2) when you want to calculate f(x, g(y)) , you write x (f g) y - this is "hook" of two arguments (dyadic) 3) when you want to calculate f(g(y), h(y)) , you write (g f h) y - this is monadic "fork" 4) whe…

A mite of pedantry: the J train (a b c d) is a hook with a fork on the right, and so dyadically acts like a(x, c(b(y), d(y))) Roger himself has dismissed [0] hooks as an unfortunate result of J4's myriad train rules, made in the name of tacitable everything, which I lament because for some reason, tacit programming is just so much more satisfying than normally solving the problem. [0]: http://www.jsoftware.com/jwiki/…

Yes, my mistake regarding 4-element dyadic train.

Re: Impending kOS

#234

Post by icsa »

svan99 wrote: post #193

I love K/Q and is using it in my startup. Thanks a lot for Kx's recent freeing up the 32bit version. To use APL-like languages I have to really shift the way of designing/modeling things. Most importantly K may not be best for lots of developers working on the same thing. Object oriented languages will fit better in that case. K projects often only involve one or two developers who model things in vector thinking (co…

What kind of computation is done at your startup? I've used k/q for trading, graph analytics and computer vision (scene reconstruction).

Re: Impending kOS

#235

Post by beagle3 »

robryk wrote: post #231
beagle3 wrote: post #228

Earlier quoted context omitted.

If you are really interested, http://nsl.com/ is a treasure trove - quite a few of the examples are extremely well documented, some or not, but there's a wealth of information there. Specifically about graphs, you can look at: http://nsl.com/papers/order.htm - topological sorting http://nsl.com/k/tarjan.q - strongly connected components http://nsl.com/k/loop.q - find loops in graphs I think in all of these the graph…

Thanks, I've missed the SCC one. I will try to understand it. (The reason I've asked about DFS in particular is that it is inherently sequential. This SCC algorithm probably encapsulates some kind of DFS.)

K has interesting sequential goodies as well: over ("fold" in Lisp/Haskell, "reduce" in python), and scan (same, with all intermediate results returned as well). But it also has the unary ("monadic" in APL terminology) counterparts to these essentially binary operators, which I don't remember from Lisp or Haskell (but I'm neither a Lisper or a Haskellite, they probably are there somewhere..)

Unary over is the "fixed point"/"converge" adverb, which does

    x
until x stabilizes (to within floating point tolerance if it is a float), returns to its first value, or goes through a requested number of iterations.

The best example of this that I can think off is the K "flatten" idiom:

   ,//
read: "concat over, converge". That is, given a general list, it concatenates all its items promoting atoms to one-element lists - thus, flattening one level of the list; And then applies it again and again until there is no further change, thus flattening successive levels of the list.

Is this the most efficient way to do this? No! in fact, for an unbalanced one sided list it will do O(n^2) where n is the number of items, with a best (and idiomatic Lisp/Haskell) solution being O(n), although it's usually 100 chars rather than 3.

But the actual code orchestrated by these 3 chars behind the scenes is all tight C loops, so for small n it will beat complex solutions. And it is all of 3 self-describing, easily remembered, easily recognized, easily optimized (if Arthur ever cared ...) characters. If you care about worst case, you can easily code the standard Lisp/Haskell solution just as you would in those languages. See [0] for more.

The underlying computational model fits sequential, parallel, SIMD, and almost every other paradigm much better than all the popular programming languages. Unfortunately, there's a learning curve that puts of most people (and is perhaps insurmountable to some people who have no problem with Python, Java, C or PHP) - it's much more Math-oriented.

[0] http://www.math.bas.bg/bantchev/place/k.html

edit: added [0] link and ref

Re: Impending kOS

#236

Post by icsa »

tsmith wrote: post #212

Sounds great! Where's the documentation on IPC / mutexes / threading? > todo > files, procs, tcp/ip, usb, .. Oh.

E.g. - (k4/q) http://code.kx.com/wiki/Reference/hopen shows how to open a file/proc.

The rest of the wiki is quite useful including a references and tutorials for q.

k5 uses operators instead of words like q.

Btw, being able map/reduce w/ 1000 procs on a 8GB Linux vm (using k5) is both useful and fun.

Re: Impending kOS

#237

Post by icsa »

jwatte wrote: post #133
geocar wrote: post #34

Earlier quoted context omitted.

If I am from another planet, and say I don't know why programs are so big and slow and buggy, and the most complicated program you see I've produced is a glorified calculator, it's too easy to be patronising and say well, that's because you haven't done anything complicated . However if I then show you a programming language, a database engine (similar in capability to SQL but around 1000x faster), a graphical deskto…

If the SQL is I/O bound, the kdb version cannot be 1000x faster. And if it's not I/O bound, you're not pushing it right. (Nite: compare columnar SQL here.) K can't make your I/O subsystem faster, and the new OS probably doesn't natively support 99.9% of existing high performance hardware.

The SQL was not I/O bound, per se - that is database/implementation-specific. The benchmarks were evaluated on "hot" data with plenty of RAM available (like any good production system).

Some databases don't manage that situation as well as they should. I.e. - they were developed in an era of small RAM & large disk.

> And if it's not I/O bound, you're not pushing it right. That's exactly the point. k is "pushing it right" while the others don't do nearly as well.

> the new OS probably doesn't natively support 99.9% of existing high performance hardware.

At <500 LOC of ANSI C there's not much to port to new hardware, given a decent C compiler.

Re: Impending kOS

#238

Post by icsa »

geocar wrote: post #37
dang wrote: post #31

Earlier quoted context omitted.

Yes, the research literature on software development has consistently found that code size is the best measurement of complexity and predictor of error rates. (Sorry I don't have citations handy but we've discussed this many times on HN, and there's a recent study in the book "Making Software" that adds to it.) What's interesting is how strongly this goes against what most people think they know about good programmin…

If someone produces smaller and faster code than me, then I should want to learn from it. I wonder why other people have the exact opposite reaction. Why do you think that is?

I think that "It's what I'm used to." is the main reason - intellectual comfort zone.

Having learned BASIC, FORTRAN and Pascal, C seemed like line noise - at first. As did PERL. And then k.

Btw, COBOL seemed "too verbose".

Once I actually started writing many k programs and then reading even more of them, I was able to recalibrate for the abstraction/density. I moved my intellectual comfort zone. Ironically, I was already there with mathematics. However, programming languages were different :).

Now, as a result, every time I have to read Java, I suffer from a kind of fatigue - having to read way too much code to glean the writer's intent. I just want them to get to the F'ing point.

N.B. - Mathematical literature/writing went through this same transition during the Renaissance. Equations were described in natural language (not unlike COBOL). A simple polynomial could require a paragraph of text to describe.

Re: Impending kOS

#239

Post by icsa »

ah- wrote: post #36

k/q really doesn't have to be this unreadable, that's just Arthurs style. Here's some code in C by him for comparison: http://kx.com/q/cs107/a.c

Here is a style for K (http://nsl.com/papers/style.pdf) 1995. Interestingly, most of the concepts still apply.

I believe the audience is developers using K in a commercial/production environment.

The biggest differences, compared to Arthur's style of writing, are: * Less code on each line * A separate comment column on each line * Nominal use of spaces for readability

Re: Impending kOS

#240

Post by icsa »

lafar6502 wrote: post #156

I don't buy this story. Maybe kdb is fast and great, but the article attempts to describe it as a work of a genius, better than anything else because it's 100 lines of code, doing its own memory management and running on bare metal. But in fact many other programs do their own memory management and can run on bare metal. JVM or .Net do their own mem management, all database servers too, and many, many others. So what…

What's left on the table is the efficient use of resources.

When I mentioned to a friend that the current version of K5 was a binary Access to more resources does not mean that one should be wasteful.

K benefits from a dedication to avoiding waste and duplication and efficient use of mathematical concepts. The Fundamental New Computing Technologies at VPRI has similar goals (an entire end-user system including "Office" apps in 40 KLOC or less).

Being able to prototype a multi-proc map/reduce algorithm in k with 1000 procs on a laptop with 8 GB RAM is quite nice.

> 500 lines of C code that's meant to change the world? I really doubt it (or, these guys arent using line breaks). There are line breaks, undoubtedly. That said, I'm sure the code is concise - much like k code.

K3 was 1200 lines of code and included the language, windows(GUI), database, IPC, REPL (w/ simple debugger), FFI and OS interaction. The Windows executable was 320 KB.

Post reply on HN