Function composition — Part 2

(Go to part 1 here).

I’m trying to learn functional programming (actually, it’s more like “to think the functional way”). I’m using Racket for it and this is my second post about creating something for function composition in the style of the Factor language. (See part 1 for some background).

My first attempt can compose only functions with a single argument, this version can do it using more than one, but also have some drawbacks.

Function composition, concatenative style

Now I can do something like that:

(~> (open “some.csv”) (open “another.csv”) combine filter-something)

It’s like I have a pipe of executions, and anything not used in a function is passed to the following function. Something like this:

   (open “some.csv”)-
                     -(combine)-> -(filter-something)-> 
(open “another.csv”)-

Understanding this as a pipe is really useful to build things, however, the easiest way to implement it is not using pipes, but with a simple stack. Each function gets what it needs from the stack and puts the results back in it.

Here I’m using “>>” to invoke the composition (I discovered “->” is already taken for contracts in Racket).

The way it works is pretty simple, follow me:

; Define ">>" that simply calls "apply-to-stack"
; using an empty list as first argument and a list
; of procedures as the second one.
(define (>> . procs) 
  (apply-to-stack ‘() procs))

(functions are called “procedures” in Racket jargon)

This is only for convenience, no real work is being done, but it’s a nice interface. Talking about interface that’s exactly what “provide” in the beginning of the file means: “expose just this function”, all other functions are private in the this file.

(define (apply-to-stack stack procs)
  (match procs
    ; No more procs (empty list), we are done!
    ; Just return the stack.
    [‘() stack]
    ; The first element is a procedure, apply it
    ; using the values in the stack
    [(list a b …) #:when (procedure? a) (apply-proc stack a b)]
    ; We have something else, just add it to the stack
    ; and proceed to next procedure in the list
    [(list a b …) (apply-to-stack (cons a stack) b)]))

Pattern matching in Racket is really powerful! This is just the tip of the iceberg. I must write about it later!

In summary, the first part inside “[“ and “]” is the pattern to be matched and the second part is the return.

The function above does basic stuff: “Are we done?”, “ Do we have a procedure?”. If the list of functions contains things that are not functions (“procedures” in Racket talk, right?), we assume they are arguments so we just add them to the pipe, I mean, the stack.

Last part is where the heavy work happens, but it’s deceptively simple, 9 lines of code:

(define (apply-proc stack proc remaining-procs)
  ; Pattern matching to rescue (again)
  (match (procedure-arity proc)
    ; Function accepts variable arguments =(
    ; Can't handle it yet
    [(arity-at-least _) (error “multiple arguments”)]
    ; Optional arguments
    ; Can't handle them also (yet)
    [(list a …) (error “optional arguments”)]
    
    ; Fixed number of arguments, now we are talking!
    ; Take the arguments from the stack to use
    ; (and reduce stack accordingly)
    [ary (let* ([params (take stack ary)]
                [remaining-stack (drop stack ary)]
                ; Stack now is the remaining stack
                ; plus the function return
                [new-stack (cons (apply proc params) 
                                 remaining-stack)])
           ; Finally, continue to the next function,
           ; but now using the new stack
           (apply-to-stack new-stack remaining-procs))]))

Looks complicated? It’s not. We have two cases we can’t handle (yet) and for the one we handle we just take the top arguments from the stack, apply the function using them and go to the next function.

Conclusion

Overall, this version barely have 16 lines of code. Not bad for simulating a concatenative language!

So, did I learn about function composition? I guess so, at least a little bit. It’s a powerful technique I think I can use even in object oriented languages. I can remember several situations that passing something through a pipeline of instructions would make the code simpler.

A side note for Racket

The language has incredible constructs: easy macros, powerful pattern matching and several other amazing things I barely touched. The more I use it, more the statement “a programmable programming language” seems to make sense.

I should write about it too :)