A raytracer in 7 lines of 'K' | Hacker News Reader

A raytracer in 7 lines of 'K'

nsl.com

16 pointsjacquesm40 comments

Will one of you geniuses hurry up and write an open source K interpreter? It's not that complex of a language to parse..

The source to Mr Whitney's prior language, A+, is available.

Unfortunately the source is rather poorly coded - it's Arthur's "K in every language" style of C - and A+ has a lot of assumptions that I'm not comfortable with. I'd love a modernized K interpreter suitable for use by stylish gentlemen. Which perhaps could be the name..

I wrote a rather basic J-ish interpreter, but it was understand the mindset of the language, rather than to have a practical implementation. (I don't think I have it anymore, but it was only about two pages of Lua.) To do it well, real experience with J/K/APL would probably be necessary. It wouldn't need to be absolutely compatible with K, just a similar language.

FWIW, there's A+ (http://www.aplusdev.org/), but I would far rather stick to the ASCII character set.

* http://www.jsoftware.com/jwiki/Essays/Incunabulum

I know a guy who wrote an open mostly Q interpreter. KX Systems did not appreciate it very much.

If anyone is interested in learning more about K and Q, the best tutorial I found came from a third party - http://gbkr.com/subjects/q/index.html

OK, this is a mess. Lets try to get some new coolness metrics here.

A. Number of lines of assembler it compiles to

B. Time it took you to write it (no cheating)

C. Number of symbols used (with names being one symbol)

K is an interpreted language.

Then it's JIT interpreted to object code.

You know, 7 lines or not, name your goddamned variables. I'd fire someone who presented me with code like this.

I'd fire someone who presented me code from the IOCCC (http://www.ioccc.org/) as well. That's entirely beside the point. The point of code like this is that it is short - other things can and will be sacrificed.

Edit: It's like complaining that the Mona Lisa is a crappy painting, because you are insistent on looking at it as if you were a cubist. It's completely missing the point.

I worked at a K shop last summer, and when I was learning the language, I tried using sensible variable names. I was told in no uncertain terms that, when you write K, local variables should be one letter, globals should be two, and functions should be three.

It sounds like a total disaster, but after about two weeks (which is a long-ass time to learn a language), everything made perfect sense, and I really enjoyed using it for the rest of the time. It's very powerful and fast to execute, and after you get the hang of it, it's fast to write, too.

I haven't spent enough time with K to get to that point of naturalness. I do think a k like language that used slightly more natural nemonics could have much broader appeal with minimal impact on code length. IMHO what makes k (and j for that matter) concise is the primitives, how they combine naturally, and how iteration is subsumed to avoid any form "item at a time" code. That last bit is what separates it from the common map/fold idioms in other languages.

Example: http://www.nsl.com/papers/kisntlisp.htm

Do tell us more about your experience. I'm fascinated with this stuff from afar.

Also, I'm curious how their database stacks up: what's it better/worse at? It seems like magic for a program so small to do so much so well. I'd like to know what the tradeoffs are. (Either that or move to their universe.)

Sorta forgot about this thread, but hopefully ou see this.

K is super-great at vector operations; element-wise addition between two lists of equal length, for example; more powerfully, mapping lists to functions.

The DB stuff we were doing were columnar databases, so it was incredibly fast at doing data analysis and correlations. Not so fast at adding single rows, but if you wanted to take a list of transactions and compare things day-over-day, or do sophisticated statistical operations, you simply had to write a line or two, and watch it take multiple million-element lists and give you an answer in milliseconds. I'm still pretty convinced it was voodoo magic.

When I used it, there was a pretty hefty license fee, but there's a trial version which limits the amount of memory it will use, but can still do quite a bit to give you a sense of the speed (as long as you're doing it right). Remember, no stinkin' loops!

I'm still pretty convinced it was voodoo magic.

I was kind of afraid you would say that. I wish they'd open-source it.

It's such a pity that Peter Seibel didn't include Arthur Whitney in Coders at Work. I suggested him, IIRC, but he didn't get in. As far as I'm concerned he belongs in the top echelon. Here is what Roger Hui, the J guy and no slouch, said (I love this story):

Someone once asked Peggy Lee who she thought was the best jazz singer. Her answer was, You mean besides Ella? Likewise, the answer to the question Who's the best programmer? is Besides Arthur?

Edit: maybe if I'd included that in my suggestion to Seibel it would have helped :)

That's golfing though. Most real code gets a bit more wordy.

I could, for instance, cut about 80% of my line count in the two Q projects I've open sourced if I used naming and spacing conventions as shown.

http://github.com/DannoHung/qutil http://github.com/DannoHung/qspec

[/Tooting Own Horn]

Using single letters in a piece of code helps in outlining the structure, instead of the contents.

That is why mathematical formulas are written with x, y, and z instead of long names. The idea is that we are emphasizing the generic relations, not what might be fed to the function.

Similarly, when writing functional code it is good style to use single letters instead of long names.

Absolutely. These conventions are not arbitrary and the people working within them are not stupid. That they would lead to poor code in a completely different language is beside the point.

I went through something like this hacking in Lisp, actually. When I started out, I used long descriptive variable names; it's the CL style anyway (MULTIPLE-VALUE-BIND, anyone?) Over time, I found myself using shorter and shorter names, to the point where my code is now of the sort that some of the commenters here would apparently fire me for it. Yet it's not like I somehow became less passionate about readable, clear code. What gives?

It took me a while to figure out. As programs get shorter (because the level of abstraction gets higher), the shape of the code itself becomes increasingly meaningful. (I mean the physical shape of the code as it appears on the screen.) This is doubly true of languages with very regular syntax like Lisp and K, and is a huge advantage to such regularity. Partly this is just that, since the program is shorter, more of it fits on one screen. But I think it's a deeper and more mysterious effect than that. You begin to develop an intuition for different patterns that have different semantics, as it were. Grokking these patterns becomes a big part of what you do when you read this sort of code. This effect is weaker in mainstream languages, so it's not surprising that people aren't aware of it. (Edit: although I used to joke that I could tell how good C# code was by printing out reams of it, hanging it on a wall, and stepping back 15 feet. That's an example of the effect too. It's just that in more powerful languages you don't have to step back 15 feet to see it.)

When you're working in a verbose language, long variable names are indispensable. You've got a whole lot of lines of code to read through, and a name like "x" does nothing to orient you as you switch contexts. But exactly the opposite is true of dense, concise programs. Variable names as long as even, say, "customerID" will dominate such programs textually, obscuring their natural shape. To increase overall clarity, you have to shorten those names to a length consonant with their semantic role. In other words, this style evolved not because people don't care about readability but because they are trying to maximize it. A convention like "one letter for local vars, two for global, and three for functions" is exactly the sort of thing that would help achieve this in a language like K.

Ironically, I have given a verbose expansion of what you just said:

Using single letters in a piece of code helps in outlining the structure, instead of the contents.[...] The idea is that we are emphasizing the generic relations

My excuse is exploratory writing: I've been meaning to write about this for a while to clarify how it works in my head. And I don't have time to make it shorter :)

Yes, and if you spend some time working with J, you will find that they solve this by avoiding variables altogether. Functions in J can only be applied to one or two variables, and it is clear from the context what the number is. So, you can write a bunch of code without referring to the arguments.

As far as readability goes, this might have as well been written in machine language.

Except that a machine language program would be thousands if not millions of times as long.

Readability is relative. Java is unreadable to my grandmother. Turkish is unreadable to me. In other words, the opinion of someone who hasn't learned a language regarding its readability is irrelevant.

It is true that the way you read a language like this is different from the way you read Java. You don't expect to grok a line of code atomically, then move to the next line. It's more like reading math: you work with each line, understanding what makes it tick. No doubt that doesn't appeal to everyone. But the APL/K/J people do amazing things.

The ultimate answer as to whether or not this is just line noise? http://kx.com/Customers/end-user-customers.php

> Readability is relative. Java is unreadable to my grandmother. Turkish is unreadable to me. In other words, the opinion of someone who hasn't learned a language regarding its readability is irrelevant.

What a gem!

I should start a collection of those, every now and then you get these things you can just frame and look at three times a day here.

I'm just glad somebody got my point. It seems so obvious, yet it must not be, because the contrary is much more common. It especially bears repeating in the context of a largely undiscovered gem like K.

> Except that a machine language program would be thousands if not millions of times as long.

Oi, I seriously doubt that. Seriously, millions? It's all math. Take a couple of assembler instructions per operation. I bet there's 256 byte assembler demo's out there...

You're probably right. I was thinking maybe millions of 0s and 1s (if those count as tokens at the lowest level) but that's getting silly.

Breaking into many lines and renaming variables would go a long way to make this code look more like C.

For a transformation in the opposite direction, here's a first draft interpreter for J (a related language) in J-ish C.

http://www.jsoftware.com/jwiki/Essays/Incunabulum

It segfaults, because it's written in rather non-portable C that assumes sizeof(function pointer) == sizeof(int), among other things. It's an interesting piece of code, though.

I don't completely understand it - I'm confused by the concept of rank in J, and haven't worked with the language enough to get over that hump. (IIRC, K avoids "rank" entirely, and just uses either an array or an array-of-arrays for multiple dimensions.) I've only been a tourist in the APL family of languages, but what I've seen has left me quite impressed.

Please take this not as an insult but as invitation to offer help.

Rank shouldn't be something to get confused about; if it is you're probably overthinking it.

What did you find confusing about it?

I found the way that the linked interpreter above implements dimensions rather confusing, mostly.

Thanks for the offer, but I didn't get that far because I decided I was better off focusing on Erlang for the time being. I'm very curious about that language family, I'm just trying to not spread myself too thin. When I get back to it, I'll try working through the J labs - it's probably a much better way to pick it up than untangling a semi-obfuscated interpreter.

Yeah I've not studied that interpreter so if that's your specific interest no luck sadly; rank is an easy idea but wouldn't surprise me if there's some trick to it in an implementation that short.

I think it'd be easier to untangle if you already had a working knowledge of the language but given the line-noisy look of J I can't blame you for trying the shortcut.

The interactive J labs are very good. You might also find the J for C programmers discussion of rank particularly helpful if you are looking at learning by understanding an implementation.

I figure the array languages will make a minor comeback soon what with gpus / larrabee / etc showing up on the horizon and what with more-versatile input devices showing up (making it easier to go back to funky symbols instead of line noise).

I figure the array languages will make a minor comeback soon what with gpus / larrabee / etc showing up on the horizon

What specifically do you see as the fit between GPUs and array languages?

The fit imho is that at least if you stick to numerics you'd have to try pretty hard not to be writing code in a way that could be easily translated into something that'd be runnable on a gpu (or larrabee).

This isn't really a new idea: http://portal.acm.org/citation.cfm?id=579.357248&coll=GU...

...(and gpus / larrabee etc. aren't solely vector processors, but the idea is apparent).

Most of the bulk numeric actions in an array language map pretty nicely to the data-parallel approach you need to use to take advantage of a gpu or larrabee (if it ever shows up); in particular take a look through this:

http://www.ncsa.illinois.edu/~gshi/LRBni_cheatsheet.pdf

...and see how much more straightforward it'd be to take advantage of (compared to SSE and so on). Your interpreter has to be a little more sophisticated (work has to be kept in units of 512 bytes) but seems much more tractable than previously.

Since this isn't a new idea there's history to learn from; it was previously the case that you'd get a speedup from offloading work to the vector units but not really a cost-proportionate one. But now if you look at the performance differential between cpus and gpus and their relative costs it starts making sense again.

You say that like it's a good thing.

Voted up in hope that someone can adequately explain that piece of code frighteningly close to line-noise.

Be happy it is not APL, where if you need two lines to express your problem you'll be scolded because you programmed it before you properly understood it ;)

frighteningly close to line-noise

That's everyone's initial reaction (it was mine too). But my experience has been that if you suspend initial disbelief and approach the language on its own terms, the result is jaw-dropping awe.

http://news.ycombinator.com/item?id=266167

It's more readable than Perl :-P

It's better once you realize that % is the division operator, and math always has right-to-left precedence (3*2+5 yields 21).

edit: there's also \:/: which is a cross-product, and ' (single-quote) is like mapcar. More explanations here: http://news.ycombinator.com/item?id=266101

The same source, slightly expanded - http://www.nsl.com/k/ray/ray.k

Reply on news.ycombinator.com