Showing posts with label lisp. Show all posts
Showing posts with label lisp. Show all posts

Wednesday, 7 January 2015

Maya- A DSL for math and numerical work


I feel awkward writing mathematical functions as s-exps

(defn quadratic-1 [a b c]
  (let [d (* 4 a c),
        D (Math/sqrt (- (* b b) d)),
        t (* 2 a), -b (- b)]
    [(/ (+ -b D) t) 
     (/ (- -b D) t)]))


Clojure's thread-first macro eases the pain a bit..


(defn quadratic-2 [a b c]
  (let [d (* 4 a c),
        D (-> (* b b) (- d) Math/sqrt),
        t (* 2 a), -b (- b)]
    [(-> -b (+ D) (/ t)) 
     (-> -b (- D) (/ t))]))


..but it's still pretty loaded with parens, and not very clear.

We need a math DSL that looks infixy and uses fewer parens.
Luckily, we can hack one for ourselves in no time.

~*~

Step 1- Thread mathematical expressions

(defmacro math->
  "(math-> 1 + 5 * 2 / 3) ;=> (-> 1 (+ 5) (* 2) (/ 3)) ;=> 4" 
  [exp & f-x-pairs]
  (if (even? (count f-x-pairs))
    `(-> ~exp 
       ~@(for [[f x] (partition 2 f-x-pairs)]
           (list f x)))
    (throw (Exception. "f-x-pairs should be even."))))

Step 2- Allow temporary bindings

(defmacro maya
  "(maya 1 + 5 :as six, six * 2 :as twelve, twelve / 3 * 2) ;=> 8"
  [& exprs]
  (let [[exp [_ ?as & next-exprs :as E]] (split-with #(not= :as %) exprs)]
    (if (empty? E)
      (cons `math-> exp)
      `(let [~?as (math-> ~@exp)]
         (maya ~@next-exprs)))))

Step 3- Profit?

(defn quadratic [a b c]
  (maya 4 * a * c :as d,
        b * b - d -> Math/sqrt :as D,
        2 * a :as t, (- b) :as -b,
        -b + D / t :as x1,
        -b - D / t :as x2,
    [x1 x2]))


~*~

Edit: Here's the original gist.

Wednesday, 31 December 2014

CljOS - Objectifying Clojure

The venerable master Qc Na was walking with his student, Anton. 
Hoping to prompt the master into a discussion, Anton said 
"Master, I have heard that objects are a very good thing - is this true?" 
Qc Na looked pityingly at his student and replied, 
"Foolish pupil - objects are merely a poor man's closures."

Chastised, Anton took his leave from his master and returned to his cell, 
intent on studying closures. He carefully read the entire 
"Lambda: The Ultimate..." series of papers and its cousins, 
and implemented a small Scheme interpreter with a closure-based object system. 
He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying 
"Master, I have diligently studied the matter, and now understand that 
objects are truly a poor man's closures." 
Qc Na responded by hitting Anton with his stick, saying 
"When will you learn? Closures are a poor man's object."

At that moment, Anton became enlightened.

~ * ~
When I first started learning Clojure (and Lisp in general), I was extremely skeptical, and the primary source of skepticism was what I had been reading about functions. 

Functions in Lisp were described as beings of great power and flexibility, especially if they could "close over" their environment. Having been exposed only to what are called functions in C and static-methods in Java, I could not even begin to imagine how they could possibly be as powerful as objects.

The first step to realizing the awesomeness of Lisp functions was using higher-order functions. The whole concept of Java Interfaces that I had loved so much flew right out the window. This approach was simpler, more intuitive, and actually easier to write/read/modify. Just compare examples of sort-by to how you would do something similar in Java.

Now, I had written a game engine in Java (Kilvish), and was thinking of porting it to Clojure. I had originally intended to write idiomatic Clojure, but that would require a complete redesign of my Java code. This is when I had a scary idea.
~*~
"Lisp has jokingly been called "the most intelligent way to misuse a computer". I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts."

(Edsger Dijkstra, CACM, 15:10)
~*~
I realized that I could add an Object System to Clojure, and reuse the same structure as my Java code. And though this sounds like a big project in itself, I was able to achieve this in less than a hundred lines of idiomatic, documented code! The result was CljOS.

After this, it was business as usual, and I ended up with a small game engine that I call Bakait.

CljOS is NOT a re-implementation of the Java OOP system, by the way. Much like the rest of Clojure, it is closer to what Python provides. CljOS does not 'hide' any data, for example. Being written in Clojure, it is also thread-safe.

Another *BIG* difference from traditional OO is the inheriting of class-variables as well as methods.  This is not a problem because just entering a class name at the REPL shows the entire structure of the class- every property, method, and the entire class hierarchy that it is a part of.

Anyways, Rich Hickey (the creator and BDFL of Clojure) hates objects and has good reasons for it. I don't use CljOS myself when writing Clojure, and generally wouldn't recommend anyone else to use it. But its existence reminds me of the power I wield being a Lisp programmer. Although Rich has (good) opinions on how Clojure should be used, the language itself is extremely malleable.

In short- Clojure doesn't tell me how to write my code, I tell it how to execute it.

Thursday, 12 June 2014

Clojure:Lisp :: LSD:Meditation

When I got back to my room last night, I found my roommate watching Scorsese's documentary on George Harrison, and immediately joined in.

The film suggests that the main motivation behind Harrison's foray into eastern mysticism and spirituality came out of a desire to tap into the mind-altering effects of LSD while steering free of chemical dependency. Today, the impact that the counterculture revolution has had on western society is very apparent, and much of it rose out of these same reasons. Many of the things that they now take for granted were born out of the same wants and needs, with Yoga being an obvious example.

Timothy Leary, in his version of the Tibetan Bardo Thodol, the 'Tibetan Book of the Dead' compares the phases that the soul passes through after death to good and bad trips, corresponding to Nirvana and rebirth respectively.

I have heard of the effects of Sudarshan Kriya from some of my college friends who had signed up for a summer course with the Art of Living and their experiences were very much like what we have come to know about the effects of external mind altering substances.

Anyway, my point is that experimenting with psychedelics led many to rediscover many spiritual aspects that were previously unknown to the vast majority, and brought them into the mainstream. Hoffman called his invention 'medicine for the soul', and wanted it to be regarded with awe rather than distrust, though it never really came to be. Acid led to the understanding of the the structure of DNA, a major revolution in thought, a dislike and deglamorization of war and things that lead to it, and to a whole lot of absolutely brilliant music.

Coding in Lisp seems to have infused many brilliant hackers (Alan Kay, Dijkstra, Stallman, etc.) with similar revelatory experiences.

It's been a long time since Common Lisp was standardized, and it has proven its worth time and again, and due to the largely orthogonal nature of the language, there have been little to no changes to its core, which some people see as a sign of 'death', and which couldn't be farther from the truth. Lisp embodies ideas that are timeless, and CL stuck to them and flourished, but didn't 'grow' in the sense other languages grow, because entirely new paradigms could be introduced in it without even touching the core. There was not a need to grow, only to embrace apparently new ideas.

But the language was dead to people who had not grown up with it, and lived in entirely foreign environments. Lispers tried time and again to reintroduce the power of their language through new implementations, but failed to grasp their attention. It was only with the addition of Lispy features to the now-mainstream languages, and the complexity that it exposed in them, that their followers regained that dying interest.

I would like to highlight this with some examples.
List comprehensions, for example, are an awesome feature, and Python supports them with the following syntax:
squares = [i*i for i in range(100)]

Clojure has a for macro to achieve the same thing, and it looks like this:
(def squares
  (for [i (range 100)])
    (* i i))

The Python example looks simple at first, but becomes increasingly complex when you try to do something useful.
Take this function (from Conway's Game of Life) for example, that returns a list of neighboring cells.
;Clojure
(defn neighbors [[x y]]
  (for [dx [-1 0 1]
        dy [-1 0 1]
        :when (not= 0 dx dy)]
    [(+ x dx) (+ y dy)]))

#Python
def neighbors(cell):
  [x, y] = cell
  ds = (-1, 0, 1)
  return [((x+dx, y+dy) for dy in ds if (dx!=0 and dy!=0)) for dx in ds]

Clojure's for scales gracefully to address the problem, whereas Python's list comprehension starts getting ugly. GvR wouldn't even let me break it into separate lines (which also results in a broken lambda, but I digress).

Then there's the issue of metaprogramming. One of the best Python frameworks I've ever come across is Django. And one of its best features is the Model-based database creation and interaction. Turns out it's written using metaclasses, which are (in Python) largely undocumented, really complex and nothing short of black magic. The best documentation on the subject is this answer on stackoverflow. Metaclass programming is easier in Ruby, and Ruby is more like Lisp, but as Paul Graham says - "If [Python hackers] don't want to wait for Python to evolve the rest of the way into Lisp, they could always just..."

In fact, this is exactly what prompted me to start learning Lisp.
I turned to Clojure because of these reasons:
1. It embraces the JVM, which I'm very comfortable with,
2. It has more novel ideas (STM, immutability-as-default, laziness, etc.) built-in than CL,
3. Rich Hickey is an awesome person, and his talks have made me a big fan (especially this one)

Yes, the current Clojure environment is not nearly as good as CL's, and ugly stack-traces litter the scene. Yes, there is no TCO happening automagically. Yes, there are no custom reader-macros.

But then, the community is working on a pure Clojure compiler, which will bring with itself a better environment, the recur keyword makes it absolutely clear that my code runs in constant space, and lesser diversity of reader-syntax makes the code easier to read.

This survey showed that 29% of Clojurians would switch to CL if Clojure disappeared, when only 5% of them were coming from it.

Clojure is re-introducing Lisp to a lot of people, much like Acid re-introduced spirituality, and for some reason, some Lispers (*cough* Pascal *cough* Costanza), instead of being happy about it, are bitching in public. There might be some truth to the myth of the SmugLispWeenie after all.

Thursday, 1 May 2014

(and Infinity Beyond)

So I came across this paradox called Thomson's Lamp, and immediately thought- "Well, isn't this what quantum theory is all about?"

Niels Bohr had once said-
"If quantum mechanics hasn't profoundly shocked you, you haven't understood it yet."

Let's try and simulate the phenomenon that creates this paradox.

(defn thomsons-lamp []
  (iterate (fn [[onoff dur]]
             [(not onoff) (/ dur 2)])
           [true 1]))

This Clojure function returns an infinite list of (on/off, duration)pairs where every successive on/off value is toggled (between true/false) and duration is halved.

NOTE: You can follow along on an awesome live REPL here.

So now when I call:
(take 10 (thomsons-lamp))

I get:
([true 1] 
 [false 0.5] 
 [true 0.25] 
 [false 0.125] 
 [true 0.0625] 
 [false 0.03125] 
 [true 0.015625] 
 [false 0.0078125] 
 [true 0.00390625] 
 [false 0.001953125])

...which is precisely what I wanted. Time to have some fun.

(nth (thomsons-lamp) 100) ;=> [true 7.888609052210118e-31]
(nth (thomsons-lamp) 1000) ;=> [true 9.332636185032189e-302]
(nth (thomsons-lamp) 10000) ;=>  [true 0]

Wait, what?

(nth (thomsons-lamp) 10001) ;=>  [false 0]
(nth (thomsons-lamp) 10002) ;=>  [true 0]

So it is on for 0 seconds, then turns off for the next 0 seconds, and keeps toggling every 0 seconds?

Basically, after some point, we don't know whether the lamp is on or off. In fact, it can be thought to be in both the states at the same time. We can know only if we observe or measure its state at a particular moment.

The problem is: we know that every even position (starting from 0) will return true, and every odd position will return false.

Measuring the state changes the outcome.

This has deep parallels with quantum theory, where electrons travelling at high velocities can either be observed as physical matter, or as waves of energy, depending on how we observe them (more).

Coming back to Thomson's problem, I define:

(defn state [t]
  (let [t-vals (map second (thomsons-lamp))]
    (loop [i 1]
      (if (<= t (apply + (take i t-vals)))
        ((comp first last) (take i (thomsons-lamp)))
        (recur (inc i))))))

which returns the state of the lamp at time = t seconds.

(state 1)    ;=> true
(state 1.5)  ;=> false
(state 1.51) ;=> true
(state 2)    ;=> false
(state 2.1)  ;=> ...(stuck)

Just as the paradox says, we will never know what the status of the lamp is after around 2 seconds.

PS: I got the idea after reading this list. You might like it too.

Sunday, 2 February 2014

On The Art of Programming

Foreword

This article is meant to guide the reader through the process of writing a program.
More importantly, it is intended to introduce the non-initiated hackers to the powerful world of functional programming and Lisp.


Introduction to Clojure

. Clojure is a dialect of Lisp, which is a family of programming languages.
. Lisp stands for list processing, and that is the core of the idea - everything is a list.
. Unless specified otherwise, lists are (eventually) evaluated, and are called forms.
. Clojure is built around the idea of immutability of state, which is pretty new and exciting.
. Many things in Clojure are lazy, ie, they are evaluated when and only if they are absolutely needed.

In Lisp, a form looks like this: (form-name x y z ...)
form-name can be one of 3 things: function-name, special-form-name, or macro-name.
The form (+ 1 2) evaluates to 3. + is a function, 1 and 2 are its arguments.


Aim

Our aim is to create a function infer-seq that takes a sequence as input and returns an infinite list created by extrapolating the input sequence using the Method of Differences.

Basically, we are implementing Babbage's Difference Engine in code. Awesome.

Use cases:

    (infer-seq [1 2])    ;=> (1 2 3 4 ...)    
    (infer-seq [10 8])   ;=> (10 8 6 4 ...)   
    (infer-seq [1 4 9])  ;=> (1 4 9 16 25 ...)

Code

Step 1
We first define a function diffs to get the list of differences for a pattern.

Use Case:
    (diffs [1 4 9]) ;=> (3 5)

Implementation:

    (defn diffs [pattern]
         (map - (rest pattern) pattern))

Working:
    (diffs [1 4 9])

  => (map - 
          (rest [1 4 9])
          [1 4 9])

  => (map - 
          [4 9]
          [1 4 9])

  => [(- 4 1) (- 9 4)]

  => [3 5]

Note:
    . As map iterates till the end of the smaller list, the 9 in the second list is simply ignored.

Step 2
We then define get-triangle as per the method of differences.

Use Case:
    (get-triangle [1 4 9]) ;=> ((1 4 9) (3 5) (2))

Implementation:

    (defn get-triangle [pattern]
         (take (count pattern) (iterate diffs pattern)))

Working:
    (get-triangle [1 4 9])

  => (take (count [1 4 9])
           (iterate diffs [1 4 9]))

  => (take 3
           [[1 4 9] [3 5] [2] [] [] [] ...])

  => [[1 4 9] [3 5] [2]]

Note:
     . As Clojure is lazy, the empty lists after [2] would never even exist.

Step 3
Finally, we define infer-seq.

Use Case:
    (infer-seq [1 4 9]) ;=>  (1 4 9 16 25 ...)

Implementation:

    (defn infer-seq [pattern]
         (->> (get-triangle pattern)
              (map last)
              reverse
              (iterate #(reductions + %))
              (map last)
              rest
              (concat pattern)))

Working:
    (infer-seq [1 4 9])

    => (->> (get-triangle [1 4 9])
          ...)
    
    => (->> [[1 4 9] [3 5] [2]]
          ...)

      => (map last [[1 4 9] [3 5] [2]])
      => [9 5 2]

      => (reverse [9 5 2])
      => [2 5 9]

      => (iterate #(reductions + %) [2 5 9])
      => [[2 5 9] [2 7 16] [2 9 25] ...]

      => (map last [[2 5 9] [2 7 16] [2 9 25] ...])
      => [9 16 25 ...]

      => (rest [9 16 25 ...])
      => [16 25 ...]

      => (concat [1 4 9] [16 25 ...])
      => [1 4 9 16 25 ...]

Note:
     . This example will help you understand how the ->> macro works.
     . #( ... ) is a reader-macro for writing anonymous functions in Clojure.
       Its arguments are: % %2 %3 ...
       Example: (map #(+ % 5) [1 2 3]) ;=> (6 7 8)
     . (reductions + [...]) returns the cumulative sums of a sequence.
       Example: (reductions + [1 2 3 4 5]) ;=> (1 3 6 10 15)


Complete Code

(defn diffs [pattern]
     (map - (rest pattern) pattern))

(defn get-triangle [pattern]
     (take (count pattern) (iterate diffs pattern)))

(defn infer-seq [pattern]
     (->> (get-triangle pattern)
          (map last)
          reverse
          (iterate #(reductions + %))
          (map last)
          rest
          (concat pattern)))

Conclusion

I had an awesome time writing this post.
Hope it encourages more people to check Lisp out.

Note

My original implementation was pretty memory intensive.
This version was suggested to me on StackOverflow.

Edit 1: Here's an equivalent in Python.