Utterly confused

So, I have been spending time pondering about code, data and various programming paradigms. And I came to conclusion that the whole thing is huge, convoluted baklava, where layer upon layer has been piled on top of each other.

If you have been reading my blog before, you fairly surely have found me talking how code and data are just different sides of the same thing in lisps. Code has hardwired instructions how to operate on the data that is fed to it. But sometimes that data is actually code and not data. And instead of outputting regular results (for lack of better term), sometimes code is generated and fed back to the program.

And then there’s really thought-provoking example in SICP that I replicated below to my best ability:

(defn my-cons [a b]
  (fn [x]
    (if (= x 1) a
        (= x 2) b
        (assert False "incorrect selector"))))

(defn my-car [a]
  (a 1))

(defn my-cdr [a]
  (a 2))

=> (setv data (my-cons 1 (my-cons 2 (my-cons 3 None))))
=> (my-car data)

=> (my-car (my-cdr data))

my-cons can be used to build single-linked lists of arbitrary length. my-car and my-cdr are then used to access the list, pulling stored values from inside it. What makes the example interesting is that both my-car and my-cdr are just function calls to a function that my-cons returned. Think that a bit. my-cons creates a function. Calling that function with correct parameter will then return either the head or tail of the linked list. And from those three basic structures one can go and start building more complex structures, like hashtables, which in turn can be used to create object oriented system with objects, methods, inheritance and all that jazz.

Below is a quick example how to map over our little “function collection” and produce a new one with calculated values. It’s recursive, so expect errors with sufficiently long lists.

(defn my-map [func coll]
  (if (is coll None) None
      (my-cons (func (my-car coll))
               (my-map func (my-cdr coll)))))
(defn double [x]
  (* 2 x))
=> (setv data (my-cons 1 (my-cons 2 (my-cons 3 (my-cons 4 None)))))
=> (setv data2 (my-map double data))
=> (my-car (my-cdr data))
=> (my-car (my-cdr data2))

Back to code that produces code. Here’s an extremely simple example that simplifies writing if not statements

(defmacro if-not [pred false-stmt true-stmt]
 `(if (not ~pred)
=> (if-not (= 1 1)
...  "1 is not equal to 1, oh woes!"
...  "1 is equal to 1, everything is fine.")
"1 is equal to 1, everything is fine."

In one sense, if-not is some special construct that has ability to write pieces of programs (inverted if-statement in this case). On the other hand, it just creates a list with predefined structure and inserts values of given variables into it. So nothing special at all. This ability of treating same piece as code or as data is rather powerful concept and mind-boggling strange when you start thinking it too deeply. And as hinted previously, resulting code could itself contain more macros that output more code that contains more macros and so on. It’s possible to even write a recursive macro that keeps expanding and expanding until some condition finally stops the recursion (or the computer runs out of memory).

What about objects and such? How special are they in the end? Turns out, not that special. But on the other hand, quite special indeed. Another quick example (this time lifted from Hy documenation and extended a bit) shows how to package data into a container and define an overridden method for each of them.

(require [hy.contrib.multi [defmulti defmethod default-method]])

(defmulti area [shape]
  "calculate area of a shape"
  (:type shape))

(defmethod area "rectangle" [rectangle]
  (* (:width rectangle)
     (:height rectangle)))
(defmethod area "circle" [circle]
  (* (** (:radius circle) 2)
(defn rectangle [width height]
  "create rectangle"
  {:type "rectangle"
   :width width
   :height height})

(defn square [width]
  "create square"
  (rectangle width width))
(defn circle [radius]
  "create circle"
  {:type "circle"
   :radius radius})

=> (setv item-1 (circle 10))
=> (setv item-2 (rectangle 5 10))
=> (setv item-3 (square 5))
=> (area item-1)
=> (area item-2)
=> (area item-3)

So now one can create objects representing geometrical shape with a constructor and call area to calculate area of a specific type of an object. Granted, this system is limited as it doesn’t allow proper inheritance of methods. But that’s shouldn’t be too tricky to implement. Big question is then, if I write a program using such a system, is my program object oriented or not? Does that even matter at that point?

Another particularly interesting (at least to me) example is how F# and Reactive Extensions (Rx) make state management very explicit by removing it from hands of programmer. Below is a snippet of code that defines starsUpdater function that when given a list of Mobs and current gametime produces a new list of mobs with updated locations (this draws a nice parallax starfield). Later on that function is hooked to time streams that are running while start menu is displayed or game is running:

let starsUpdater (state:Mob list) (time:GameTime) =
    state |> List.map (fun star ->
        let newLocation = star.location + star.speed * timeCoeff time
        let newLocation' = if newLocation.y > 768.0f
                              then { newLocation with y = 0.0f }
                              else newLocation
        { star with location = newLocation' })

let starStream = menuTimeStream
                 |> Observable.merge gameRunningTimeStream
                 |> Observable.scanInit (initialStarField renderResources rng time) starsUpdater
                 |> Observable.publish

The really cool this is that programmer is writing very functional code: old state and game time in, new state out. Rx takes care of state management with scanInit function. Every time a new state is produced, it overwrites the old state stored by scanInit. When next element in time stream floats by, previous state is fed back into starsUpdater, which produces a new state and so on. There definitely is state in the program and it keeps changing as time goes by, but it has mostly been abstracted away from the programmer.

And if you want to ponder even deeper mysteries, you start wondering the difference between functional, procedural, declarative and imperative paradigms. For example, Haskell’s do block sometimes looks very much like imperative program as it computes values, stores them into intermediate variables and computes more values and maybe output some data on-screen. But that do block gets expanded into chained lambdas, so in the end it’s functional after all. But then the code is executed and goes changing state of the computer system nilly-willy, messing with registers and outputting stuff on screen. I would hazard a guess that if one were to observe what a processor is doing during program execution, it would be hard to tell functional and imperative programs apart.

So, where am I getting with all this (am I getting somewhere)? I guess it’s just fun to pondering things from slightly different perspectives what you’re used to. Sometimes it yields insightful information, sometimes it’s just fun amusement.

The more interesting point is that it sort of highlights the fact that programming is all about building mental models. Not only about the problem you’re trying to solve or about the software you’re writing to solve it. It’s also about building mental models about the language or paradigm you’re using to write that particular piece of software. Some models might yield vastly different answers when applied to same problem. Being aware of them will help programmer to choose a suitable model for their task.


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