Thursday, September 12, 2013

Lisp Without Parentheses

Lisp is sometimes jokingly said to stand for "Lots of Irritating Superfluous Parentheses". Despite the joke, it turns out most of the parentheses in an average Lisp program are, in fact, superfluous. Let's examine the program for finding square roots by Newton's Method from SICP:

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      (sqrt-iter (improve guess x)

(define (improve guess x)
   (average guess (/ x guess)))
(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

This isn't as bad as some Lisp programs, but even so, three closing-parens in a row starts to get hard to keep track of without editor support. Admittedly, most programmers have editor support (if your text editor can't match parens for you in 2013, you need to get a new text editor); but if we don't need them we might as well get rid of them. Parentheses do 3 things in this program: they tell indicate where function/macro applications start and where the argument lists for those applications end, and they delimit lists. If we know the signature of each function or macro, then we don't need parentheses for that second purpose- telling us where argument lists end. We can restrict them to simply marking applications (as opposed to functions that are being used as values), and delimiting lists (in this case, the only lists we need to worry about are the argument lists in function definitions). That gives us a transformed program that looks like this:

(define) '(sqrt-iter guess x)
  (if) (good-enough?) guess x
      (sqrt-iter) (improve) guess x

(define) '(improve guess x)
   (average) guess (/) x guess
(define) '(average x y)
  (/) (+) x y 2

(define) '(good-enough? guess x)
  (<) (abs) (-) square guess x 0.001

(define) '(sqrt x)
  (sqrt-iter) 1.0 x

For clarity, I've explicitly quoted the lists to distinguish an application from a list of a single element. This is starting to look a lot like Polish Notation with all of the operators parenthesized. You might think "Polish Notation arithmetic doesn't need parentheses because arithmetic operators use distinct symbols from operands"; true, but that turns out not to matter. If we think of values as functions that take no arguments and return themselves, and variables as functions that take no arguments and apply their values, then we can assume that everything is always applied by default, and then we don't need those parentheses (or anything else) to mark applications, giving us this:

define '(sqrt-iter guess x)
  if good-enough? guess x
      sqrt-iter improve guess x

define '(improve guess x)
   average guess / x guess
define '(average x y)
  / + x y 2

define '(good-enough? guess x)
  < abs - square guess x 0.001

define '(sqrt x)
  sqrt-iter 1.0 x

This should look suspiciously like FORTH. If it doesn't, try capitalizing everything and reading it backwards (in Reverse Polish Notation, like old HP calculators use). I have a sneaking suspicion that FORTH variants have remained fairly niche languages largely because they put their arguments and function names backwards from everybody else (well, except for Assembly languages, but nobody really wants to program in assembly either). (Incidentally, this is very similar to how actual Lisps are compiled into concatenative languages like VM bytecode.)

As long as you have just enough static typing to keep track the arity of each function, all of the original parenthesization can be reconstructed automatically (which means that we can still implement things like lazy evaluation or automatic parallelization under the hood).

Now, we did lose something by eliminating parentheses are explicit delimiters of argument lists: you can't handle variadic functions anymore (well, unless you do crazy Haskell stuff). But, for the most part, you don't really need variadic functions. Lisps tend to map rest arguments to lists anyway, so just pass list. If you want, say, variadic add, just write a function to fold a list over binary add. Something like...

define '(\+ l) fold + 0 l, oops. Type error. That code will be automatically parenthesized as follows:

(define (\+ l) (fold (+ 0 l)))

+ needs two numbers, not a number and a list, and fold doesn't take a number as it's first argument (plus, it needs a couple more). What we need is some way to turn off the application of + and get its value instead. We only need this for passing first-class function values as arguments, and that happens far less often than function applications do in most programs, so we can bring back parentheses for that (the exact opposite of their original purpose) and still have a net gain in program concision (and reduced nesting):

define '(\+ l) fold (+) 0 l

We're using parentheses here rather than some other symbol (like, say, a prefixed # or something) to indicate non-application, because we can actually put more stuff in there- a whole list of stuff, in fact. Maybe something like

define '(list-double-plus l) map (+ 1 * 2) l

What's really going on here is not that parentheses are suppressing application- rather, parentheses delimit lists (just like they do when quoted), but now, instead of representing function applications, unquoted lists represent functions that return functions composed of the contents of the list. (+) isn't a binary operator that hasn't been applied, rather it's a new function that returns a function composed solely of that binary operator. It gets applied as normal (to zero arguments), but its return value is what fold needed as its first argument. (+ 1 * 2) returns a function that's the composition of +, 1, *, and 2, with automatic currying. With these semantics, we don't actually need a separate "lambda" construct in the language anymore, since lists produce anonymous functions- as long as you're willing to program in point-free style, anyway.
If we just imagine the whole program as wrapped in one big set of top-level, outside parentheses, we can see that all programs are still lists- just less deeply nested ones. The language is still homoiconic, so it's still pretty easy to do metaprogramming, and it still makes sense to call this a dialect of Lisp.

Addendum on String Formatting:

The canonical example of a variadic function is a string formatter (which is what that Haskell variadic craziness was developed for, too). Since it's horribly stupid to get format strings out of variables, though,  and you should always have them as literals in the program text, we can solve that problem by building string formatting/interpolation into the language as have the language implementation turn literal strings into functions that take a fixed number of arguments (for the interpolation slots) and return string values.

Thursday, August 8, 2013

My Journey Through Flow Arts

Time for something a little bit different. Flowtoys has asked people to put up their "flow stories" on Facebook, and, as I really like Flowtoys, I thought I'd do so, and did. And then I thought "I should edit this a bit and put it on my blog, because I have one, and I ought to use it more." So, here it is.

Prior to high school, I had very little interest in any physical activity; I pretty much figured that as long as my body was working well enough to keep my brain alive, that was good enough. My parents, on the other hand, were determined that I ought to still get some sort of regular exercise even after I hit junior year and no longer had to take mandatory PE. No, they did not introduce me to poi- they decided I should join the internationally-acclaimed high school rowing crew. Predictably, I absolutely hated it. But, in the meantime, I had some friends who did glowstringing, and I thought that was coolest thing ever and determined to figure it out. The basic butterfly in particular totally blew my mind. I was totally uncoordinated, and I accidentally re-invented some basic meteor spinning, having never heard of it before, just as an excuse to avoid having to use my cruddy left hand (ironically, I still suck at meteor spinning). From glowstringing, via YouTube tutorials, I got into poi, and made my own set by tying shoelaces to tennis balls (flat shoelaces are still my favorite tethers). After a couple of months, I quit rowing, and I'm pretty sure my interest in this weird poi thing that at least got me out of a chair was a significant factor in my parents letting me do it.

Then I graduated and went off to college. Prior to this point, I was certain that I hated dancing- I went to exactly two dances in high school (Junior and Senior Prom) and spun glowsticks. College gave me a lot more opportunity for dances (residence hall dances, student association dances, etc.), and, figuring that I ought to have some way of figuring out how to engage in socialization, I made myself go to them and got through it with glowsticks. Eventually, it clicked that poi is dance- just using your arms more than your feet. Prior to that moment, I had been almost entirely focused on technical spinning. Afterwards, I found myself opened up to exploring a whole new world of body movement, and started playing with freehand light tracing to try to force myself to develop some "danciness" independent of the motion of the poi.

Looking for good tutorials on YouTube had led me to Nick Woolsey's videos and Playpoi. During my second semester at college, Playpoi started putting out videos on double staff, and I decided I had to figure out staffs as well. So, the next summer, I got myself some dowel rods from Home Depot and started playing. From the start, I was fascinated by the connections between staff and poi patterns, analysing which patterns would transfer between the two forms, which couldn't, and why. I still frequently get a lot of my new performance ideas by learning a new trick with poi and then thinking "what's the closest I can come to replicating this with a staff?" or vice-versa.

Then I took two years off from life to serve on a mission for the LDS Church in Ukraine. In what little free time a missionary has, I practiced poi with shoelaces tied to tennis balls, and staffs with broom handles, spare PVC pipe, or whatever was at hand. During that time, my mom shipped me my first set of two flowlights- so much better than chemical glowsticks! Having no access to videos or other spinners for two years, I credit that period with helping me develop my own sense of style as a simple unavoidable necessity.

When I got back and started college again in 2010, I was totally hooked on flowlights. I got myself oggpoi, crystal cases (still using shoelace tethers!), and collapsable staffs and went to town out on the lawns in my apartment complex nearly every night. When I met new people around campus or new people moved in to my complex between semesters, it became not uncommon to be greeted with "hey! you're that guy with the lights!" Based on my glowsticking roots, I took to using double-ended crystal poi, mixing in techniques from handle spinning and meteor hammer; I've seen lots of people do tosses with poi, and even use weighted handles, but nobody outside of the glowstringing community play with two equally weight ends. One more thing to add to my personal style.

I heard rumors that there was another poi spinner in the campus juggling club, and I should go hang out with them, and I thought maybe that would give me the chance to finally try out some partner poi stuff- sadly, no luck. Poi is unloved in the juggling club. But, I did get a ready-made group of friends who like to do all kinds of other prop-manipulation arts, and started doing performances for libraries, school groups, the homecoming parade.... Then in the spring of 2011, I found myself sitting next to a chocolate fountain at a dance and simultaneously next to a girl who I was certain was merely waiting for her date to get back from the buffet table. Turns out, she was single, also drawn to chocolate fountains, and wondered if I could show her how to spin lights, 'cause those looked just so awesome! By this point, lots of people had asked to borrow my lights for a few minutes, or wondered if I could teach them, or told me how they wished they could do that, but no one ever followed through for more than 5 minutes. This particular girl, on the other hand, to my shock and amazement, asked me to dance, got my phone number, and set up regular weekly poi spinning lessons. Needless to say, we became friends, and I finally got my partner-poi-partner.

When summer break came, we talked on the phone just about every other day, but somehow I did not quite get the hint. During the next fall semester, though, she finally managed to convince me that I really wanted to marry her. Seven excruciatingly long months later, we got married just in time to shoot our first video for Circles of Light. In the meantime, I had tried introducing her to staffs, but it just didn't stick like poi spinning did. That is, until we both realized that, while I had always been into double staff (because two sticks are more fun than one), she loved single staff. Thus, I had to learn single staff. And of course, we had to figure out how to do it as partners. Sadly, my new mother-in-law was of the opinion that this whole poi spinning thing was extremely weird, and what is this crazy guy getting my baby girl into....
Until November, when we found out that, no, we did not win, but we did get on the 2012 COL DVD! External validation from an international competition went a long way towards improving my mother-in-law's opinions.

That fall, some new people had joined the juggling club- one wanting to learn contact juggling, and one wanting to sell some contact juggling balls. Thus we gained our third flow art. I'm still not very good at it yet (being distracted by the events of the following paragraph), but contact juggling adds a whole new dimension to the experience of flow arts- it's flow, but not as we know it, Jim.

Then it was time to start planning for the next year's video. I initially wanted to merge partner poi with passing patterns from toss juggling- but our toss-juggling-fu was not that good. Some day I'm sure it will make for some awesome performances, but after realizing we weren't going to make that work, we fell back to the idea of doing partner staff. Having no YouTube videos to look at for inspiration, we invented our own patterns for two staffs and two people- a mix of single and double staff techniques and interconnected patterns that are impossible with only two hands. In a fit of choreographic panic, we both somehow managed to go from sort of casually playing around to actually being competent with a single staff just in time to get a video in the mail.

A few weeks later (and just a few weeks ago, by now), we went to a big week-long family reunion in Island Park, Idaho. One of my brothers, who has three kids, lives just a couple miles away from me, and my wife & I have often ended up babysitting for him. Whenever we go, we've taken to taking our big bag of toys along. As a result, one of my nephews has taken an interest in contact juggling, both think staff spinning is pretty cool (one of them is in karate, and does a totally different kind of staff work), and my two year old niece has oodles of fun throwing juggling balls. Knowing there would be lots of kids, we of course took the big bag of toys to the family reunion as well. There we discovered that one of my other nieces seems to have a natural talent for contact juggling. One night, we did our video performance with glow staffs for the whole family, and afterwards took apart all of our equipment and let all of our (numerous!) nieces and nephews run around the yard with flowlights and oggs. They were a pretty big hit! In addition to the personal pleasure that comes from playing with flowtoys, it's enormously gratifying to see little kids get so much joy from play with some bright glowing lights and pretending they're lightsabers or fairy dust or whatever.

I have high hopes that we are inspiring another generation of flow artists.

Now, that's the end of my flow art journey (until I go and learn how to do more cool stuff), but I ought to add another little anecdote. Flowtoys has a really fantastic warranty policy, so when one of our spectrum lights started acting funky, I naturally wanted to get it replaced. However, it is nearly time for my wife's birthday, and I also wanted to buy her some new toys. It would be nice if I could the warranty items and the new order all packaged together so I could save a few bucks on shipping... but, oh darn, I waited too long to send stuff in, and there's no way the warranty items are gonna ship soon enough for everything to get to me on time....

Enter Flowtoys' exceptional customer service. Not only did they decide to process and ship out my order in 1 day rather than the expected "up to three" to make sure my wife got her birthday presents on time, they went out of their way to bundle in my warranty items even though my returns hadn't arrived yet. Not only do they make the best equipment you can get, they're really nice people.

Also, Home of Poi: they're based in New Zealand (the actual home of poi), so shipping can be a bit steep, but if Flowtoys doesn't sell it, HOP probably does. I haven't had any personal interaction with HOP employees to evaluate them on, but I do really like their stuff.

Saturday, May 11, 2013

Pointful Concatenative Programming

Well, I managed to spend the last year or so working on parallelism and vau expressions without actually writing any blog posts about it. Next week I'm giving a conference presentation, and maybe after that I'll come back here and review the last year's work. But for now, I am on to something a little different.

Reading Why Concatenative Programming Matters has inspired me to experiment with concatenative languages. Concatenative languages are often called "stack-based" languages, because they are incredibly easy to implement with stacks, but that article enlightened me to the fact that stacks are not actually necessary- other evaluation options are possible. In fact, type analysis can be used to identify substrings of concatenative programs that take no inputs which correspond to expressions in argument positions in functional languages and can all be executed in parallel. (In retrospect, this should have been obvious since functional languages compile to concatenative ones- this is just the reverse mapping.)

One of the reasons concatenative programming is cool because it's point-free; i.e., you never have to specify variable names, which makes things nice and concise. Unfortunately, that can backfire and end up making things horribly unreadable, which is why concatenative languages tend to suck at expressing basic math. Sometimes, you just want to use a variable to put the same value in multiple places; even in RPN syntax, "y x * y -", using variables to put values in the right place on the virtual stack, is way easier to read and understand than "DUP ROT * SWAP -", using stack effect operators. Not having variables also means that concatenative languages tend to lack the ability to do variable capture, which means no closures.

I have thus been pondering a concatenative language that adds variable-binding lambda expressions. Something like this:

{ a b | b a }

would take two values off the top of the virtual stack and bind them to variables "a" and "b" within the scope of the expression. Variables are just words that take no arguments are return their bound values. The effect of this expression would then be to swap the top two elements on the virtual stack. Lots of otherwise basic, built-in words can be created with these kinds of expressions. E.g., DUP looks like this:

{ x | x x }

These sorts of lambda expressions would be interpreted like words and applied immediately, causing them to function rather like let-bindings in functional languages. Combining lambdas with quotation, however, allows us to create closures:

{ x | [{ y | x y + }] }

This expression binds one argument and returns a closure that takes another argument and adds it to the closed-over value.

Well, that's all for now. Maybe, if I'm lucky, I'll have time this summer to start implementing this thing.