hyPiRion

Swearjure - Clojure without alphanumerics

posted

Clojure is feature-rich: Some data structures are functions themselves, and we have function literals so that we can write #(assoc % foo quux) instead of (fn [m] (assoc m foo quux)). In addition—since Clojure is a lisp—we have macros with both unquoting and splice unquoting: `(foo ~@[:a :b :c]) will return the list (foo :a :b :c). It turns out that these features may possibly be enough to write Clojure without using a single alphanumeric character.

A precise definition on Swearjure hasn’t been developed yet, though the main idea behind it is to avoid using alphanumerics altogether. Generally one wouldn’t allow def and the function names of the functions one develop to be written out with alphanumerics, but for the sake of clarity, I will do so here. In addition, I have taken the liberty to append some values to the argument list to not make it more confusing that it already is.

gfredericks/gfrlog and TimMc were the first to question and discuss how expressive Clojure would be without alphanumerics, in the #clojure channel on Freenode. The name Swearjure was coined in IRC as well, and became a way of referring to using Clojure without alphanumerics around November 2012.

Numbers

Clojure comes bundled with a couple of functions which makes it easy to write integers without using the numerics themselves. + and *, which gives us all the natural numbers that we want: As (+) returns 0, and (*) returns 1, a combination like (+ (*) (*)) return 2, and so forth. By prepending a -, we get negative numbers: (- (*)) equals -1. Division also works if you want to get ratios, (/ (*) (+ (*) (*))) would return 1/2 for instance. As of now, there doesn’t seem to be a way of getting floating points (ratios should suffice).

Functions

Unfortunately using fn, defn, and defmacro isn’t allowed, so using those are currently out of the question. The only thing we are allowed to use which can generate functions is to use the function literal (#()). As a fresh reminder of how it works, here are some examples:

(#(+ 4 %) 5)
#_=> 9

(#(conj %2 %1) 3 [1 2])
#_=> [1 2 3]

(#(identity %&) 1 2 3)
#_=> (1 2 3)

(#(conj (vec %&) %1) 5 6 7 8)
#_=> [6 7 8 5]

Now, an important thing to keep in mind is that we’re not allowed to use digits, so using %2, %3, etc. in our code isn’t allowed. %1 is no good either, but since it is just an alias for %, we can just use that one instead. %& is also okay to use because it doesn’t contain any alphanumerics.

As such, some functions are rather easy to implement in Swearjure. Take inc and dec for instance, which is just

(def my-inc
 #(+ % (*)))

(def my-dec
 #(- % (*)))

(def my-identity
 #({} % %))

identity works because a hash map is also a function taking either one or two arguments. The second argument is returned if the first argument is not a key in the hash map.

This is fine, but for functions with more than one parameter, we have to do some more magic.

Unquote splicing to the rescue

The solution is to combine %&, unquote splicing and the fact that vectors themselves are functions. Since we’re guaranteed that %& is a list, we can unquote splice (~@) it without any issue. But, since lists in Clojure aren’t functions themselves, we have to invent our own tricks: We use unquote splicing within a backquoted vector, and we can from there on invoke the vector with different numerical arguments to get any kind of value:

(#(identity `[~@%&]) 1 2 3 4)
#_=> [1 2 3 4]

(#(`[~@%&] 1) 1 2 3 4) ; Get 2nd argument
#_=> 2

With these ideas, we can implement several functions:

(def my-list
  #([%&] (+)))

(def my-vector
  #(`[[~@%&]] (+)))

(def my-nth
  #(`[~@%] (`[~@%&] (+))))
;; nb, does not work on infinite lists.

(def my-hash-map
  #(`[{~% ~@%&}] (+)))

If you get how unquote splicing and unquoting works, this shouldn’t be hard to follow. The only one with a peculiar look is the hash-map implementation: The Clojure reader enforces all hash maps to contain an even element of arguments—even if the element is going to be unquote spliced. I’m not sure if this is a bug in Clojure or me pushing the limits of what the Clojure reader is supposed to support, though I wouldn’t be surprised if it is the latter.

Recursion

Recursion inside an anonymous function isn’t possible with the set of tools we’ve got, so we need to invent some way to add recursion. The general idea is to have multiple functions and make them call each other depending on conditions. However, we cannot create anonymous functions inside anonymous functions. As such, we give ourselves (for now) the possibility to let the first parameter be a Swearjure argument (i.e. without alphanumerics) which we implicitly assume is sent every time the function is called. The argument may be a map or a vector, in which we can lookup values from. This is nice because those values can be anonymous functions and can take themselves as an input value, essentially making them recursive.

To implement something large in Swearjure, it’s best to start off with an expanded version. Let numbers be numbers, anonymous functions be normal functions (though not nested) and the vector of functions a map of functions instead. This makes it easier to implement control flow.

Factorial

Let us as a proof of concept implement factorial in Swearjure. This factorial is not identical to TimMc’s Swearjure factorial but uses similar techniques.

We start off with a standard version:

((fn [factorial n]
   (factorial factorial n)) ; Call factorial with itself and n

 (fn [factorial n] ; First argument
     (if (= 0 n)
         1
         (* n (factorial factorial (- n 1)))))

 6) ; The actual argument

This works neatly in Clojure, and more or less everything here can be covered by the tricks we’re discovered earlier. However, there’s a catch: the if cannot be converted into Swearjure (neither can or and and, for that matter). As a result, everything we write within Swearjure will be evaluated.

That doesn’t mean we can’t simulate control flow. A standard solution for replacing an if is by having two functions, both taking same arguments but calculate something different. We then have a hash map which contains some value we compare our result with, and an optional argument which acts like an else function. We can do this by making the first argument a map and adding a :is-zero and :recurse clause:

((fn [hm n]
   ((hm :fact) hm n)) ; Call factorial with all fns and n

 {:fact (fn [hm n]
          (let [f-to-call ({0 :is-zero} n :recurse)]
            ((hm f-to-call) hm n)))
  :is-zero (fn [hm n] 1) ; return 1
  :recurse (fn [hm n]    ; recurse by calling :fact
             (* n ((hm :fact) hm (- n 1))))}

 6)

We’re now ready to Swearjure it: The let in :fact is inlined, and n is found by doing (`[~@%&] (+)). Currently we’ll replace :fact with :!, :is-zero with :+ and :recurse with :-.

(#((:! %) % (`[~@%&] (+))) ; Call factorial with all fns and n

 {:! #((% ({(+) :+} (`[~@%&] (+)) :-))
       % (`[~@%&] (+)))
  :+ #({} %& (*))               ; return 1 regardless of input
  :- #(* (`[~@%&] (+))          ; recurse by calling :!
         ((% :!) %  (- (`[~@%&] (+)) (*))))}

 6)

This is legal Swearjure, but it would be cool if we could remove the colons too. It turns out this is not a problem, but it will make the code a bit more unreadable. Recall that a vector is also callable, so we can place every function on a specified index instead of doing a mapping as the hash map does. In the code below, :! is 0, :+ is 1, and :- is 2.

(#((% (+)) % (`[~@%&] (+))); Call factorial with all fns and n

 [#((% ({(+) (*)} (`[~@%&] (+)) (+ (*) (*))))
    % (`[~@%&] (+)))
  #({} %& (*))
  #(* (`[~@%&] (+))
      ((% (+)) %  (- (`[~@%&] (+)) (*))))]

 6)

And there we go, factorial in Swearjure. With recursion, we can also implement other fancy stuff like rest. See TimMc’s solution for an example of how wrong this may turn out.

Swearjure without the additional parameter?

Now, it would be nice to remove the additional parameter and call functions with just the real arguments. Would that be possible?

… perhaps. We’re currently lacking a way to get into the namespace. If we’re able to find a way to get the clojure.core namespace and ns-map, Swearjure would be functionally equivalent to Clojure itself. Certain tricks have been attempted, and I believe the most promising one is the one trying to fetch metadata from a var: (For the sake of our sanities, I’ll print numbers in their numeric representation here.)

((`[~@(ns-map ((`[~@(meta #'+)] 0) 1))] 689) 1)
#_=> #'clojure.core/eval
;; 689 may differ from version and setup.

And with this comes a bunch of other functions we can utilize. We can fetch source-fn from clojure.repl and use it in conjunction with read-string to fetch special forms like let, if and recur from functions and macros using them. Through source-fn, read-string, and eval, we can generate code and evaluate it based on the source of Clojure itself1.

… however, that requires ns-map and meta available. Without those, this is nothing but a dream.

Other Curiosities

Backquoting backquotes gives interesting results which may at first look usable. We all know that `() gives (), but it’s not obvious what ``() may give us. Perhaps surprisingly, this gives us (clojure.core/list), which may at first look like a way picking up the list function. And it would be if the result itself was the function and not the symbol.

Looking up the symbol could be done in many different ways: Through eval, resolve or somehow through var-quoting. (`[#'~@``()] (+)) will for instance return (var clojure.core/list). If you’re able to evaluate this without calling eval, you’ve got a lot of nifty tools available—for instance, apply, vector and hash-map:

``[]
#_=> (clojure.core/apply clojure.core/vector
       (clojure.core/seq (clojure.core/concat)))

``{}
#_=> (clojure.core/apply clojure.core/hash-map
       (clojure.core/seq (clojure.core/concat)))

But again, we still have the problem with resolving these variables. Until we find a way of resolving variables or “hacking” ourselves into the namespace, we’re stuck with the n+1 arity versions for now.

  1. This is easily done by picking apart the source code of Clojure itself. Through source-fn, we can get a string of the source code. With read-string, we now have the source as data, and with (`[~@form] n) we can read out different values. If we compose it correctly, we can form fns and defns and use eval to define them.