Show HN: I designed a language for code golf, compiling to Common Lisp
rhoscript.com
rhoscript.com
As far as being purpose-built for code golf goes, there are already even more compact concatenative languages, like F[1] and XY[2], that might give this a run for its money due to K's obvious influence. Then again, it wouldn't be hard to have a rewrite layer to turn mnemonic operations into their expanded rhoScript words :)
[1]: http://nsl.com/k/f/f.htm [2]: http://nsl.com/k/xy/xy.htm
- The lazyness of lists. "1 naturals (add) map" will produce an infinite list of integers from 1. This introduces some interesting difficulties. For example, what would you expect "1 naturals (add) map 2 swap 5 take" to produce? It will clearly either be (1 2 3 4 5) or (2 3 4 5 6). I pick the first because it produces less surprising results. So, when map is called, it saves the state of the stack, so it doesn't end up seeing the 2 pushed on the stack.
- I added lexically-scoped "arguments" to functions because I found them useful. The commands "arg-[a-d]" will "remember" the top four values on the stack, even if the lazyness of the language changes the top four values on the stack by the time it reaches these commands.
I guess one other difference is that functions here are typed, but that's not really a fundamental difference with other concatenative languages.
As for F and XY, I haven't looked in to them much. A cursory glance, however, leads me to believe that when pushed to their limits, I'd expect the arithmetic-encoded programs to be significantly shorter. The 22 different tokens in the 8 queens program condense in to 17 bytes. (And, this assumes that all functions of a valid type are equally likely to be called -- I'd expect most programs to get shorter once I spend some time figuring out reasonable weights for the encoder). That said, I definitely see some things I'm going to steal from those languages.
Imagine you write the program "(add print) call". Clearly that function takes two integer arguments. Right?
Well, that's only because you're looking at the high-level version. Compile it down and you get AE 1D B0 88. If you run it on two integers, you get the sum, as expected.
But what happens if you run it with a list on the stack? Then it happens to run the program "(arg-min arg-a) call". Why? The arithmetic-decoder just sees some bytes, and it decodes them to match the correct types.
Representing the actual type of functions would require more bits, make programs longer, and so I haven't implemented that. I'm still pondering things to do here.
Beautiful!
Also, static types don’t necessarily preclude dynamic stack effects, as long as those effects can be characterised somehow by the type system. In my statically typed concatenative language, Kitten, I originally considered a notion of “regular” types that would let you do something like this:
{ :: r -> r End
} :: r End a* -> r [a]
{ 1 2 3 } :: [Int]
See: http://docs.factorcode.org/content/article-inference.html
In practice, all of the unbalanced stack-effects will become trivially balanced at word boundaries & dynamic stack-effects only occur when metaprogramming.
2. I was unable to get programs to run via http://www.rhoscript.com/try.html. For example:
>>> "hello" print run
Sending to server.
Received response in 237ms.
>>>
3. There is a small error in the text of your tutorial, at rhoscript.com/tutorial.html:
s/split-by-newlines results in a string with four elements/split-by-spaces results in a string with four elements/ "hello" printAnother issue: I wanted to see the output of just range. So I typed in `8 range` and got no output. Then I looked through the examples for something simple that might output a list. I tried the primes example, `100 range-from-1 rest (gcd 1 neq) uniq-by` but got blank output. Thoughts?
Have you ever considered anything like this?
If anyone has feedback let me know!
I'm hesitant to mention this since it doesn't really take away from your project, but "concatinatitive" should be spelled "concatenative".
Well that's embarrassing! (fixed)
I was thinking about building my own physical calculator (i don't like to use smart phones for that, there is not nearly enough space for keys, and the keys give not appropriate feedback). I was looking for languages to use and I didn't find anything suitable. Forth was too raw. I didn't like factor, it seem unsuitable for a calculator. OpenRPL was, i don't know why, odd. This language, once it add other number types, and allow to omit the map, APL style, looks very promising.
But writing a whole calculator software, with the menus and integrating the programming language, ability to plot functions, inspect variables and so on, was not a weekend project as first thought because the language has to be integrated deeply.
The best compilation of code-golfing problems I've seen is Anarchy Golf [1]. Pick almost any problem you want, implement it in rhoScript naively, and you'll get a much shorter solution. (Except those problems which use things not currently present, anything like, say, floating point numbers.)
If you look at some of the examples I have compared to the programs others have written, you'll get a brief sense. My eight-queens is 17 bytes, the shortest on Anarchy Golf [2] is 42. A solution to the 196 algorithm problem [3] in rhoScript takes 16 bytes compared to 24. But that's just cherrypicking problems I found interesting. I haven't yet done a real random sample to see how well it does.
Note, however, that the programs you write in rhoScript don't yet format the output to conform correctly, so they may require a few more bytes for that.
[1] http://golf.shinh.org/
[2] http://golf.shinh.org/p.rb?N+Queens
[3] http://golf.shinh.org/p.rb?196+algorithmqn:{[n],/{:[n=#x;,x;,/_f'f x,\:/:(!n)_dvl,/x]}'(f:0 -1 1+/:)@!n} bd:{[p]`0:".Q"p=\:!#p}
(see http://nsl.com/papers/qn.htm)
I suspect that a binary length-optimized encoding of K will be comparably short.
And take into account that K was not designed for code golf - it's just a side effect of optimizing for orthogonality.
One of the reasons golf never interested me is because people kept making these totally inscrutable concoctions that you couldn't even take a "squinty eyed look" at. Contrast this with the rhoscript solution:
8 range permutations (with-index (sum) map uniq arg-a with-index (*exploding subtract) map uniq concatenate length) keep-maxes-by
By contrast that piece of K code seems actively hostile to understanding it.
I'm also going to point out that whilst it looks pretty cool (and it runs very fast) it's a frikkin nightmare trying to debug someone else's K-code in production. Which is why I don't recommend that anyone learn it.
I'be found I can easily read Arthur's and Stevan's code. K takes a little more discipline (or talent) to be readable than other languages.
How was your experience with coding in CL?
The macros were the big win for me with this. I have only a few macros, but without them, the code would be significantly uglier. The entire builtin-generator is a big giant macro, and it was very nice to define my own little DSL to build commands. (fun story: I originally started developing this as a Python interpreter, and abandoned it because (a) it was far too slow, and (b) it was difficult to build a clean, abstract, method of writing builtins)
Other than the macros, the other big win was how easy it is to generate lisp code. There's no string munging, just (cons 'add cmds) and you're done.
There are some things I don't like about it. I think Scheme has it right with functions and variables sharing one namespace. I find the common lisp
(defun something (a)
(map #'square (funcall a)))
(define (something fn)
(map square (fn)))
1. Pure dynamic typing is a headache. I use type hints quite frequently, tend to use defstruct rather than cons, etc. SBCL has a pretty good type inference system and gives very useful compile-time feedback about types.
2. Macros can help improve organization and code re-use when used properly. Macros can also turn code into an unreadable mess when used improperly. The only way to learn what is "proper" is experience / practice; books like On Lisp and Let over Lambda help but you really do need to get your hands dirty.
3. Debugging across an FFI is really painful. The debugging tools for Lisp are fantastic, the debugging tools for C are fantastic, but those tools compose poorly.
4. I wish the standard allowed map, reduce, and similar constructs to be defined for arbitrary sequence types. There is more to life than lists and arrays.
5. I wish the standard came with more useful data structures. Associative lists in CL are great if you never have more than a tiny number of items in them; an associative tree type would be a great addition. It would also be nice to have a standard priority queue type, a standard random-access list type, etc.
6. Performance is easy to underestimate. SBCL does a bang-up job of optimizing code, with a few exceptions. The optimizer in SBCL could use some work, of course, but it is nowhere near as bad as people seem to expect for a high-level language.
Overall, I think what CL is desperately in need of is an updated standard. The world has changed a lot since CLtL2; we need a CLtL3. There are a lot of non-standard libraries that are widely used and that should just be standardized -- MOP, generic sequences, an FFI, etc.
What is your setup for debugging CL?