Currying in apocrita

While apocrita is very limited language, it’s already complete enough that I can experiment with ideas and see how they work in practice (or in this case, how to implement an old and well known idea). And that old idea is currying (technically partial application, but close enough).

In partial application the language will detect if a function is being called without enough parameters. Instead of throwing an error, a new function is created and returned. This new function captures all the parameters that were supplied to the original function and can be called either normally or partially applied again (if there are more than one parameter left).

As you probably remember, heart of apocrita is the apply-eval – loop, where these two functions are being called until only a value is left. Like the name suggest, partical application falls squarely in apply-function. Normally there’s choice between doing a primitive application (essentially jumping out of apocrita, back to the host language) or applying a function to given set of parameters. If there are not enough parameters, an error is raised and execution halted.

By adding a third case here, we can extend the language. If we aren’t doing primitive application and don’t have enough parameters, we should do a partial application. Checking amount of parameters is best to encapsulate as a separate function to keep things readable:

(defn needs-currying? [proc args]
  "does this application result to currying"
  (> (len (. proc params expr)) (len args)))

And calling it is simple as:

(defn apply- [proc args]
  "apply procedure to arguments"
  (cond [(primitive? proc) (apply-primop proc args)]
        [(needs-currying? proc args) (curry proc args)]
        [true (eval- (. proc body)
                     (bind (. proc params) args (. proc env)))]))

Curry function is supposed to create a new function that captures supplied parameters. One important thing to pay attention here is that the code keeps scope correct. Any symbols that original function’s scope captures should be available to the new function, in addition to the symbols passed in as parameters. And order has to be correct too: if there’s a symbol captured by the original scope and symbol with same name passed in as a parameter, the latter one should take precedence. Luckilly this is easily arranged by using the original scope of function and binding the parameters in it.

Curry in itself is another call to eval function. After finding out which parameters have been specified and which ones are lacking values still (if I ever implement optional or keyword parameters, this part of the code is going to change) we create a new expression for lambda and evaluate it. Body of the lambda is the body of the original function:

(defn curry [proc args]
  "curry a function"
  (let [[all-params (. proc params expr)]
        [arg-count (len args)]
        [unbound-params (slice all-params arg-count)]
        [bound-params (slice all-params 0 arg-count)]]
    (eval- (Expression [(Symbol "lambda")
                        (Expression unbound-params)
                        proc.body])
           (bind (Expression bound-params) args (. proc env)))))

I have to admit, that getting this right took me couple of tries. Originally I tried constructing closure object directly, but in the end found that it’s easiest if I just create an expression and evaluate that in correct environment. Based on the testing I have done so far it seems to work just fine:

=> (define (sum a b)
...  (+ a b))
<closure: a b>

=> (define (calculate op a b)
...  (op a b))
<closure: op a b>

=> (calculate sum 2 3)
5

=> (define calculate-sum (calculate-sum))
<closure: a b>

=> (calculate-sum 2 3)
5
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s