sencjw

Here’s my website. Some common things are on the navbar. I’ve also worked to preserve any locations that people would have linked to from elsewhere. If I’ve broken a link of yours that used to point to sencjw.com somewhere, let me know and I’ll put it back, cool URIs don’t change.

Recent Blog Posts

Lists out of lambdas and boxes out of functions

2013-04-06

There’s a cool article by Steve Losh called List out of Lambda that reminded me, in a really good way, of a section in SICP. If you want to read the boiled-down scheme version that’s in SICP, here it is (my paraphrasing from SICP section 2.1.3)

“cons” makes a list by putting an element onto the front of an existing list.

(cons 1 '()) ; '(1)

that’s empty list ‘() and a list with just “1” in it above’(1). There’s two other functions that deconstruct a list: ‘car’ and ‘cdr’, or head and tail (name’s not really important):

(car '(1 2 3)) ; 1
(cdr '(1 2 3)) ; '(2 3)

Car returns the head of the list and cdr returns the rest of the list (without the head). You’d think that ‘car’, ‘cdr’, and ‘cons’ would pretty much have to be built in functions, but actually they don’t!

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

This is the trickiest thing to grok, but then you’re in the clear. Calling ‘cons’ returns a function (called “dispatch”) which “closes” over its two arguments. That means that the function is implicitly storing x and y off where function arguments are stored. Dispatch takes a single argument, m, which acts like a kind of selector. If m == 0, then dispatch returns the first argument to cons, if m == 1, then dispatch returns the second argument to cons.

((cons 1 '(2 3)) 0) ; 1
((cons 1 '(2 3)) 1) ; '(2 3)

Now we just define car and cdr to do exactly this:

(define (car lst)
  (lst 0))

(define (cdr lst)
  (lst 1))

Remember that the way that this works is that the list is being stored as a function so the only thing we can do is to call it!

(car (cons 1 '(2 3))) ; 1
(cdr (cons 1 '(2 3))) ; '(2 3)

Cool! We just built lists out of “nothing”. If you want to be even more mind-bending. You can make the “dispatch” function anonymous:

(define (cons x y)
  (lambda (m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m)))))

It works the same.

If you view functions as little boxes that basically just contain their return values this makes sense. A function is like a box that, when given its argument barfs up the result. In fact, don’t think of a function as doing something, think of it as being something. If it is first class then you should be able to treat it this way in all respects. You can pass around these little boxes that have some value “in” them and the only way to get it out is to “call” it (or force, or… whatever). But, and we’re starting to tread into heavy functional land here, what if you weren’t so hung up on the idea of getting the value “out” of the box?

(define (box-it-up x) (lambda () x))

This puts a value, x, in a box. You can do whatever you want with the box. You can store it, you can pass it around etc. And, of course, you can open it up by doing this:

((box-it-up 10)) ; 10

If that’s a bit hard to read, just remember that whatever is the first thing in a lisp list is called. Javascript would be:

box_it_up(10)(); // 10

But let’s say that we don’t really care to open the box (we labeled our boxes really well). We just want to make sure that, whenever it is opened, that we obey special handling instructions. Let’s write “double this” on the box.

(define (double-this box)
  (lambda () (* (box) 2)))

Maybe I bent the rules a bit. I used a magic pen that when I wrote “double-this” on the box, it performed an old mover’s optimization trick. Instead of just having our original box I magically duplicated the old box with the twist that the new box now contains double whatever was in the old one ;) Got that? (Hey, metaphors are hard).

Maybe you can see where I’m going here. I don’t want to have to make a new kind of “double-this” function every time I want to do something. How about I just give you the magic pen?

(define (magic-pen box func)
  (lambda () (func (box))))

That means you can write “double-this” like so:

(define (double-this box)
  (magic-pen box (lambda (x) (* 2 x))))

Here’s how this all looks now:

(define twenty-box (double-this (box-it-up 10)))

(twenty-box) ; 20

cool! So this is how I’ve been thinking about Promises in javascript. We have a kind of box that unlike functions we really can’t open up for the simple reason that the value may not have happened yet. But it is no biggie because we can do whatever we like to the values inside inside the box!

If you’ve got all that, then I’m happy because I’ve also kinda sorted tricked you into understanding monads. Did you notice how I was just able to handwave at the end and say, “yeah, but instead of functions the ‘box’ is some as-yet-unreceived network packet”? Monads are just the idea that you can compute all day long with these sorts of “unopened boxes”. Well not just, but the devil is in the details and that means that I’ll probably write another blog post about it.

the dipert problem

2012-09-03

Recently, Alan Dipert dropped a bomb on the twittersphere with his posing of this question (warning there are spoilers in the replies):

“pop quiz: solve http://www.4clojure.com/problem/107 point-free. answer must be a function value! #clojure”

In case your office has banned 4clojure for being a huge distraction, I’ll post the problem here:

(= 256 ((__ 2) 16),
       ((__ 8) 2))

(= [1 8 27 64] (map (__ 3) [1 2 3 4]))

(= [1 2 4 8 16] (map #((__ %) 2) [0 1 2 3 4]))

In problem 107, your challenge is to write a function that satisfies all of these (it could be dropped in place of the __s above). I will let you go take a crack at solving it. Because up next is some serious spoiler action.

Got your solution? I came up with this:

(fn [x] (fn [y] (reduce * (repeat x y))))

or (what I was really doing) in Haskell:

f :: Int -> Int -> Int
f x y = foldl1 (*) (replicate x y)

We are doing manual exponentiation: “make a list of ys that is x in length (e.g. replicate 8 2 == [2, 2, 2, 2, 2, 2, 2, 2]). Then you just run multiplication through the list:

foldl1 (*) [2,2,2,2,2,2,2,2] == 2 * 2 * 2 * ... 2 == 256

Now comes the “Dipert Problem.” He has told us that we have to rewrite the solution (or any solution) using so-called point-free style. I’m sure that there’s more to it, but essentially that means that we are not allowed to mention any variables! When I first heard about this style, it sounded impossible! The cool thing is that it isn’t and it leads to some massively simple code. Let’s try it out.

I’m going to start with my solution above called f and then write some successive versions of it, each time, I’ll remove a variable and call it the “next” version: f1, f2, okay? Cool.

f, f1, f2 :: Int -> Int -> Int
f x y = foldl1 (*) (replicate x y)

For the first transformation, we need to get rid of the y that’s hanging off the end of both sides of our equation. We’ll need to juggle the innards a bit because here is what the types look like so far:

foldl1 (*) :: [Int] -> Int
replicate x y :: Int -> a -> [a]

replicate takes two arguments and then produces a list that the foldl1 (*) wants to consume. The trouble is, and what tripped me up a bunch, is that I can’t just do this:

foldl1 (*) . replicate

Wah, wah (sad trombone). GHCI tells me:

Expected type: Int -> [c0]
  Actual type: Int -> a0 -> [a0]

Okay, that makes sense, for the fold and replicate to “line up” for composition, replicate has to take one argument then produce a list. The crux is that composition (the “dot” or period in the code) only works for single-argument-functons:

(.) :: (b -> c) -> (a -> b) -> a -> c

This is a little pipeline, but reversed because that’s how mathematics does it. It says “the right-side function takes an a and gives a b, and the left-side function expects a b and gives a c; now you can stitch them together and have a function that skips the b and takes you right from a to c.” But we have a function that looks like:

(a -> b -> c)

on the right-hand side; it won’t work. how do we convert a (a -> b -> c) to a (a -> (b -> c))? This way:

{-
f x y =  foldl1 (*) ((replicate x) y)
f x y = (foldl1 (*) . (replicate x)) y
-}
f1 x  =  foldl1 (*) . (replicate x)

Note: the first two lines are commented in case you are cut-n-pasting along. The first line just puts parenthesis in where they really are in haskell. Each time you see a function of two arguments, it is really a function which takes one argument and returns a function that expects the second argument! This weird but remarkable fact of haskell is called currying.

Now, on to the second line, we see that we have the right types! (I am cheating a bit on types, if you like, you can define rep which just uses Ints)

replicate x :: Int -> [Int]  -- cheating: where 'x' is a specific int
foldl1 (*)  :: [Int] -> Int

foldl1 (*) . replicate x :: Int -> Int

And that brings us to f1! We used grouping and composition to move the y outside the computation and then we dropped it from both sides.

Next we’ll tackle the x:

{-
f x =  (foldl1 (*) .) (replicate x)
f x = ((foldl1 (*) .) . replicate) x
-}
f2 =   (foldl1 (*) .) . replicate

It may look different, but the same thing is going on. We can group the composition with the fold without changing anything. This is just like doing:

3 + 4 == (3 +) 4

Next we do that same trick again where we can now compose the inner functions because the types line up (again, I’m simplifying types a bit):

((foldl1 (*) .) .) :: (a -> b -> [c]) -> a -> b -> c

it looks a bit hairy, but in our case, it is just what we want! If I fill in the actual types we’ll be using, it becomes clearer:

((foldl1 (*) .) .) :: (Int -> Int -> [Int]) -> Int -> Int -> Int

Booyah! This contraption takes a function of two Ints that produces a list of ints, [Int]. Well, that’s just what replicate is! So if we then feed in replicate:

(foldl1 (*) .) . replicate :: Int -> Int -> Int

And that’s it, we have a point-free function that takes two Ints and returns an Int. And so that’s our last, and final function:

f2 = (foldl1 (*) .) . replicate

In general, and I don’t know a term for this, but the operation of successive function composition lets us compose higher and higher arity functions together. Here’s a dumb example using my little point-free succ function:

g :: Int -> Int
g = (+1)
(g .)       :: (a -> Int) -> a -> Int
(g .) .)    :: (a -> b -> Int) -> a -> b -> Int
(g .) .) .) :: (a -> b -> c -> Int) -> a -> b -> c -> Int

Clear pattern. I kinda think of this as saying something like “please give me a function which eventually promises to give me what I want.” The eventually part is essentially “after you’ve collected all the stuff you need.” It would be trivially satisfied by some function that ignores its args and returns a constant:

(((g .) .) .) (\x y z -> 1) 4 5 6 == 2

Remembering that g just increments, the x y z are totally ignored. The function supplied to the multiply-composed g is like some kind of integer “pre-processor”; the x, y and z can be whatever you need to do to figure out how to give g an integer. Or at least that’s how I’m thinking of it.

I had a lot of fun trying to figure this out!

my “transparent web” talk

2012-08-22

Without much ado at all, here’s my talk. I’m covering the real basics of using both Ur/Web and Opa. I create a basic “Hello world” page in each and then I go on to write a little “comments” system.

my gpl talk

2012-05-05

note to the reader, my speaker notes are reproduced below and all run together. Also, the editing isn’t top-notch.

notes

First a warning, if you thought I was going to talk about software licenses, I’m not. Not really. I’m going to talk mostly about people. Ideas are one thing, they are the compiled results of processes that people go through. I want to decompile some ideas. I want to talk about that.

To that end, let me tell you a story. Let’s go back to 1980, Richard Stallman is employed as a staff hacker at the MIT AI lab. This is the stuff of legend.

The lab had recently been given a new prototype printer from XEROX PARC. This was ten times faster than the previous printer, finishing a 20 minute job in 2 minutes and with more precise shapes to boot. This was the same sort of tech that a decade hence would touch off the desktop publishing revolution. But back at the AI lab, the printer was becoming the source of more headache than anything else. Stallman and others would send jobs to the printer only to show up later to find that the job had jammed four pages in. This was a minor annoyance, but it was multiplied by everyone at the lab. Stallman thought, “why should I have to babysit this machine when I can code?”

Stallman knew a way to attack this sort of problem. On a previous printer he had modified the source to insert some monitoring code in the printer driver. Periodically, Stallman’s code would check to see that the printer was proceeding in its assigned job, if it had stalled, the program would alert whoever’s print job was affected. You’d get a message like: “The printer is jammed. Please fix it.” It wasn’t perfect, but it informed those most interested in the problem.

The solution this time around would be similar. Stallman could grab his old code, tweak it for the new printer and voila: jam notifications. So Stallman rolled up his sleeves, grabbed a coffee, and opened up the Xerox source code.

If you see where I’m going here, you’ll probably see what’s coming next. There was no source code. Stallman even spoke with the programmer that had worked on it and that programmer wasn’t allowed reveal the code to Stallman.

This is the moment where something happens. This is where an insight strikes, the apple falls on your head, the disparate pieces line up and you need to jump out of the tub and tell the world. Stallman decided, at that moment, that some fundamental wrong had been done: the wrong of not being allowed to help your neighbor by telling him how code works., This brings me to the main point of this talk. This is the thing that, even if everything else you hear is mangled or forgotten, I want to come through unchanged: RMS believes that software has moral implications, the choice of what kind of SOFTWARE you want is a choice about what kind of WORLD you want.

Note all the things that I didn’t say. It isn’t about what is technically superior. It isn’t about what is good for being able to sell. It isn’t about what the legal department says. It has no bearing on what various companies will tell you to be worried about. It isn’t about being good for playing games, or having flash support. It is nothing more and nothing less than a philosophical stance. You can agree with it, or disagree with it in exactly the same way as you would argue about Plato’s Forms.

I feel like this is the key misunderstanding in discussions surrounding the GPL and Free software. I’m taking a philosophical, an ethical, and maybe a moral stance. I haven’t brought anything else into it. Often, when I see discussions about software licenses, I feel like people are talking past one another from the very first sentence.

It is profoundly nonsensical to compare something like “justice” to something like a wrench., Philosophers begin by defining words, because if they don’t, we’ll get so mired in the muck of argument that no points are made, no progress is made.

The word “free” is a good place to start. Free can be taken to mean “no cost” but it can also be taken to mean “freedom”. This is sort of a fine point to make, but I think it could lead to lots of confusion.

Free software has to do with the “freedom” part. There are lots of really good objections at this point. The one that I have anticipated is “freedom for whom?” And that’s the core of the so-called permissive divide in the broader category of “open” software. The permissive people would respond to the “freedom for whom” question with something like “certainly not for me, you say I must share changes, that’s pretty restrictive.” And the answer to “freedom for whom?” that I want to present here is…

Well, that’s the rest of my talk., The GPL is a really a more general case of the Emacs license.

Now Emacs has a pretty storied history, wikipedia dates it back to the mid seventies, well before GNU or Emacs-as-GNU-project. But by the time of the release of Emacs 15, there was a sort of proto-GPL license attached. It served to give “users the right to make and distribute copies” and “the right to make modified versions, but not the right to claim sole ownership of those modified versions”. It was moving in a similar direction, but it was not as legalistically formal as the eventual GNU project would need it to be.

Stallman’s intellectual property attorney at the time viewed the GNU Emacs License pretty much as a simple contract, although one that stipulated a rather odd price. Rather than money, the license cost access to any changes. Users would have to share modified versions of the software. The attorney remarked: “I think asking other people to accept the price was, if not unique, highly unusual at that time”

In 1989 a 1.0 version of the GPL had emerged. The preamble read:

The General Public License is designed to make sure that you have the freedom to give away or sell copies of free software, that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.

To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.

one notable change was that users were no longer required to share changes. You could make private in-house tweaks to the software without being forced to share these changes back to the community. , License agreements are not usually characterized by what they give you, rather, as we scan ever longer End User License Agreements, or plow through revision 271 of Facebook’s new much-better-we-assure-you privacy policy, we are looking for things that they are taking from us.

The GPL, in essence, tries to codify a very idealistic hacker ethic. It is for tinkering, changing, breaking, reassembling, and passing it on to your friend. It is software as mix-tape.

The main things that the GPL gives you are broken down into four parts, aka the “four freedoms”, Zero: You’re allowed to do what you want with the software. An author can’t proscribe the software’s use for something that they don’t approve of. This is pretty profound, I think.

one: if you are going to be able to do this, you’ll need the source code. You’ll also need whatever is required to actually end up with a working program. This can be a point of contention. A corner case of this is in embedded systems such as set-top boxes where the code may be GPL, busybox is a common example, but you can’t actually change the code due to things like code signing., two: I think it is interesting that two emphasizes the goal of the redistribution. It isn’t just for fun or for copying’s sake, it is because we view software as something that can help people.

freedom three, the final freedom. You’ll also need access to the source code to realize this one. You are allowed to make public changes to the code. The difference with freedom one is that you’re allowed to do this out in the open, rather than just in private and for your own reasons. You can fork. You can contribute back.

lurking in freedom three is also the core of my argument, which I promise I’m getting to really soon., I’m going to try and dispel a common myth about the GPL, one I’ve heard a lot. The general gist is that “the GPL is to copyright as anarchy is to government.” Something that is opposed to the very notion of it. This is where people get the idea that any business built on such shifting sand of self-destruction must be flawed in some way.

Opposition to copyright is an interesting subject, there’s lots of good debate. But it doesn’t really have anything to do with the GPL. The GPL has staked its efficacy IN copyright.

Far from being some sort of anti-copyright construct, the GPL’s EXISTENCE depends on copyright, if you didn’t have copyright, you couldn’t have the GPL (or lots of other stuff). You wouldn’t get any say in what people do with your stuff… but that’s another discussion entirely!

So for the rest of the talk, consider copyright to be a constant underpinning, a foundational necessity for everything else we’re talking about. It’s just that we’re going to use it for something that it wasn’t intended: we’re hacking it., BAM: flip it

copyleft: pay it forward.

As Stallman said: “see [the GPL] as a form of intellectual jujitsu, using the legal system that software hoarders have set up against them”, he actually lifted this from a similar sticker from a sci-fi convention which read: “Copyleft (L), All Rights Reversed.”, And this brings me around to what my thinking on the GPL is. I guess I’m kinda surprised by all the emphasis on virulence these days. The metaphor is broken. Metaphors are broken–but that’s another talk.

Casting aside any metaphors, the GPL is an inductive license. This is a term that I made up but I think it describes the nature of the GPL much better than saying that it is viral.

An initial case is established. You have the four freedoms: the freedom to run, freedom to change, freedom to redistribute, and the freedom to share those changes.

But for it to really be Free software, the person receiving the software must have these freedoms. So it is not good enough for us to leave it here. We only have the base case for a software license. We have to prove the general case, not me or you, but person N+1., So the person who’s freedom we’re talking about is person N+1, the inductive person.

This idea is the essential difference between being permissive software and being free software. Free software describes the case of that person N+1, inductively. It raises the “freedom for whom?” question and answers it with “the inductive person”.

So I’ll leave where, approximately, I started with a definition:

The word “induction” is the practice of deriving general laws from specific cases, it arises from a root word meaning “leading to” or “hypothetical”. Free software asks us to consider this hypothetical person on the assumption that it could someday be anyone, indeed everyone.

secret santa

2011-12-27

While I was sitting around and eating a ton of Christmas food, I got to thinking about the Secret Santa problem. In its most basic form, this is the same as something called a derangement. I mention it just because I think the name is cool, the concept is super simple, a derangement is a permutation of the elements of a list such that no element stays in the same place:

[1, 2, 3] would have a derangement:
[2, 3, 1]

notice that each element has moved. So this pertains to secret santas because if you are just not allowed to chose yourself then a derangement (like this) is all that you’d need, it would be a valid secret santa!

> zip [1, 2, 3] (derangement [1, 2, 3])
[(1,2),(2,3),(3,1)]

cool! person 1 gives to person 2, person 2 gives to person 3, and person 3 gives to person 1.

As my family could tell you, I thought that I could do better (in keeping with my motto “if it ain’t broke, fix it until it is”). Wouldn’t it be cool if in additon to just forbidding the case where you pick your own name (reflexive), you also can provide two more lists. One is a list of pairings which are disallowed and the second is a list of pairings which are to be discouraged (less likely).

I’ve implemented almost what I just described. In the code below, I don’t actually make a selection from some distribution where discouraged selections are less likely. Instead, I’ve added a bestSantas function that allows you to limit yourself to selections that are under a certain amount of badness (a selection has 1 point of badness for each discouraged pairing that it includes). I hadn’t decided how I wanted to select from among differing levels of badness yet. But anyway, enjoy!

For a complete list of posts, see the blog page.