A Lisp in Clojure? How useless! But fun non the less.

Having found a nice post on how to built a simple lisp like (scheme like) language (How to Write a (Lisp) Interpreter (in Python)) I was wondering what would this look like in Clojure. Writing a lisp in Clojure sounded very useless and fun so here we go the result in on Github.

A couple interesting observations:

Since Clojure lends itself to using immutable datastructures the inital implementation of the evaluation seemed a little complex as it needs to receive the environment along with the next token. But as soon as I was implementing function calls this suddenly made the stacking of environments trivial. No complex chain maps etc. needed, nice!

clojure.core.match is a very nice little lib, I wish it was part of core Clojure by default. I had first implemented a giant cond statement, match made it much more concise and robust, as it not only asserts the matching symbol but also the parameters to it.

(defn lclj-eval
  "Eval a expression X in the context of environment ENV, defaults to
  base-env."
  ([x] (lclj-eval x lclj-base-env))
  ([x env]
   (match [x]
          [(_ :guard symbol?)] {:result ((keyword x) env) :env env}
          [(_ :guard number?)] {:result x :env env}
          [['if _ _ _]] (lclj-eval (if-branch x env) env)
          [['define _ _]] {:env (define-in-env x env)}
          [['quote _]] {:env env :result (-> x rest first)}
          [['lambda _ _]] {:env env :result (lclj-fn x env)}
          :else (lclj-fn-call x env))))

Obviously this can all be done better but it was a fun (I guess in total) afternoon for sure, having never written a lisp interpreter before.

Reversing collection vs Java Array in Clojure

How big is the overhead of using Clojure datastructures vs native Java Arrays? I was rather suprised to find it is lower than I expected, and the implementation looks much better using Clojure native vectors and lists than Java Arrays.

First an essentail when doing something like this

(set! *warn-on-reflection* true)

Without that it is easy to accidentally create arrays very inefficient calls via the array accessor and setter methods by having to rely on reflection. Now for the code

(defn hn-reverse
  [coll]
  (reduce #(conj %1 %2) '() coll))

Simple basic clojure implementation walking the incoming collection and prepending to a list.

Using criterium for a quick benchmark on my machine gives me

(let [v (vec (range 1000))]
  (bench (hn-reverse v)))

On my little XPS 13 gives me

Evaluation count : 2370120 in 60 samples of 39502 calls.
             Execution time mean : 26.090496 microsecond
    Execution time std-deviation : 832.330358 ns
   Execution time lower quantile : 25.220196 microsecond ( 2.5%)
   Execution time upper quantile : 28.154777 microsecond (97.5%)
                   Overhead used : 11.468971 ns

Found 5 outliers in 60 samples (8.3333 %)
  low-severe     5 (8.3333 %)
 Variance from outliers : 18.9765 % Variance is moderately inflated by outliers

Now how would an array perform here? (and yes I assumed it would be faster hence the name)

(defn fast-reverse
  [^ints array]
  ;; ^ints type annotation is essential here, otherwise this will be very slow
  ;; due to reflection on aget and aset
  (let [l (alength array)]
    (loop [i (dec l)
           j 0
           a (int-array l)]
      (if (= j l) a
          (do
            (aset a i (aget array j))
            (recur (dec i) (inc j) a))))))

Again quick criterium test

(let [a (int-array (range 1000))]
  (bench (fast-reverse a)))

This time

Evaluation count : 5851680 in 60 samples of 97528 calls.
             Execution time mean : 10.561515 microsecond
    Execution time std-deviation : 336.219142 ns
   Execution time lower quantile : 10.240088 microsecond ( 2.5%)
   Execution time upper quantile : 11.385153 microsecond (97.5%)
                   Overhead used : 11.468971 ns

Found 3 outliers in 60 samples (5.0000 %)
  low-severe     3 (5.0000 %)
 Variance from outliers : 18.9721 % Variance is moderately inflated by outliers

Using native Java Arrays is about 2.5x faster than clojure vector and list implentation in this case.

I somehow expected a bigger difference given the jump from immutable to mutable datastructures and the less allocations needed but it seems like this kind of optimization only really makes sense in the edge cases.

Counting vowels, in a more declerative manner

Playing with some clojure code while solving some of karan/Projects I discovered my solutions differ a lot when thinking in a functional way doing programming in Clojure than doing the same in Ruby some time ago. almost arriving at a declerative style in this case

(defn count-vowels
  "Take string S count vowels return map of vowel to count."
  [s]
  (let [up-inc (fnil inc 0)
        counts (reduce #(update %1 (string/lower-case %2) up-inc) {} s)
        vowels #{"a" "e" "i" "o" "u"}]
    (select-keys counts vowels)))

(count-vowels
 (generators/string generators/printable-ascii-char 1000))

Not sure why the concept of building a dataset and selecting what is relevant felt more natural than imperativly building up the data here, but it did for me somehow and the code reads quite nicely.

Playing with lazy-seq

Played a little with lazy-seq vs loop recur today, and got a suprise that lazy-seq is not as slow as I would have thought. Most likely the usecases are very different so by no means is this interchangably for most applications, but I assumed that a lazy-seq carries a lot of overhead. Don’t know why I thought that so, but playing around with it and timing the output I realized it seems to be a wrong assumption. By no means this is a real benchmark but it makes me read up more for sure.

(defn fib
  "Return the Nth fibonacci number."
  [n]
  (loop [i n
         p 0
         pp 1]
    (if (zero? i)
      p
      (recur (dec i) (+ pp p) p))))

(defn lazy-fib
  "Return the fibonacci sequence as a lazy sequence."
  ([] (lazy-fib 0 1))
  ([p pp] (lazy-seq (cons p (lazy-fib pp (+ p pp))))))


(let [n 60]
  (println "Nth number:")
  (time (fib n))
  (println "Non lazy:")
  (time (last (take n (map fib (range)))))
  (println "Lazy:")
  (time (last (take n (lazy-fib)))))

;; Nth number:
;; "Elapsed time: 0.022058 msecs"
;; Non lazy:
;; "Elapsed time: 0.133195 msecs"
;; Lazy:
;; "Elapsed time: 0.026575 msecs"

Seems like lazy-seq is at least same order of magnitude to just calculating N for fibonacci here, and creating a non lazy seq seems much slower. No optimization what so ever here, and also being pretty brute force about the recursion in the lazy-fib.

Emacs, echo mike alpha charlie sierra

Having moved to a different country spelling words over the phone is a real pain as its not easy for people to understand a foreign name, and because I don’t know the military alphabet in english. So even when I decide spell things out I get stuck on letters as I don’t know what the common word would be. After not remembering how to spell out my last name over the phone again today I decide to create a quick little helper, after all I almost always take notes on my laptop anyway when calling.

Here we go quick emacs string-to-military, with configurable alphabet.

(defun string-to-military (s)
  (interactive "sEnter string to transfor to military: ")
  (flet ((string-blank-p (s) (string-match-p "^\\s-*$" s))
         (military-get-string (s)
                              (if (string-blank-p s) " "
                                  (alist-get s military-alphabet "" nil #'equal))))
    (let* ((chars (mapcar 'string s))
           (normalized-chars (mapcar 'downcase chars)))
      (string-join (mapcar 'military-get-string normalized-chars) " "))))


(defun string-to-military-region (start end)
  (interactive "r")
  (let ((content (buffer-substring-no-properties start end)))
    (delete-region start end)
    (insert (string-to-military content))))

and for the curious

(defvar military-alphabet '(("a" . "alpha")
                            ("b" . "bravo")
                            ("c" . "charlie")
                            ("d" . "delta")
                            ("e" . "echo")
                            ("f" . "foxtrot")
                            ("g" . "golf")
                            ("h" . "hotel")
                            ("i" . "india")
                            ("j" . "juliet")
                            ("k" . "kilo")
                            ("l" . "lima")
                            ("m" . "mike")
                            ("n" . "november")
                            ("o" . "oscar")
                            ("p" . "papa")
                            ("q" . "quebec")
                            ("r" . "romeo")
                            ("s" . "sierra")
                            ("t" . "tango")
                            ("u" . "uniform")
                            ("v" . "victor")
                            ("w" . "whiskey")
                            ("x" . "x-Ray")
                            ("y" . "yankee")
                            ("z" . "zulu"))
  "Military alphabet alist (CHARACTER . WORD), all characters are
lowercase for lookup.")

now part of my coders-little-helper.el in my local emacs.

Setup use-package

I like my emacs configuration to be managable in git installing everything on first start, as I migrated away from my home grown install and package manage to use-package I wanted to keep this nicety, so I need to make sure use-package gets installed if it isn’t already present.

;; setup use-package, if we don't have it, install it
(require 'use-package nil t)

(unless (featurep 'use-package)
  (package-refresh-contents)
  (package-install 'use-package)
  (require 'use-package))

Setting up Emacs on Windows 10

Emacs runs quite well on Windows 10, but to get it to work correctly it needs to be setup with a couple of other requirements

  1. Setup HOME environment variable, find it via “environment” in cortana search
  2. Download Emacs and Emacs Deps
  3. Combine both into a folder under C:\Program Files\emacs

With this in place the runemacs.exe will start an emacs session, and with the dependencies in place TLS will work as well for getting packages from melpa, elpa, etc.

I also use org-mode for my notes and todo list, to allow it to sync with mobile it requires sha1sum.exe, available as a binary download. With the binary copied in place of the emacs binary org-mobile-push org-mobile-pull will work.

Clojure + Ring + API Gateway + Lambda

Serverless is all the rage right now, so I’ve been playing with AWS Lambda, and just by the name itself what could possibly be a better fit for lambda than using Clojure on it? Since I’m mostly interested in webapps I decied to give API Gateway a spin with lambda, sadly it does not immedialty work with the awesome Ring library for building web applications in clojure. Luckily it is reasonably easy to map between the two, and inspired by ring-aws-lambda-adapter some time later I now have a working version of Ring + API Gateway. Together with AWS SAM and AWS SAM CLI this makes for quite a nice, local or cloud, development and hacking experience. And all it took is about 90 lines of Clojure

(ns playground.core
  (:require [clojure.data.json :as json]
            [clojure.java.io :as io]
            [clojure.string :as s]
            [ring.util.codec :as codec]
            [ring.util.response :as r])
  (:gen-class
   :name playground.core.Handler
   :implements [com.amazonaws.services.lambda.runtime.RequestStreamHandler])
  (:import [com.amazonaws.services.lambda.runtime RequestStreamHandler]
           [java.io InputStream File]
           [clojure.lang ISeq]))

(defn sample-handler
  [event]
  (r/response "Hello Lambda, from ring!"))

(defn stream->event
  [in]
  (json/read (io/reader in) :key-fn keyword))

(defn str->int
  [s]
  (try
    (Integer/parseInt s)
    (catch NumberFormatException _)))

(defn maybe-remote-address
  "Take a guess at the remote client ip based on the X-FORWARDED-FOR header.
  This is not perfect as the X-FORWARDED-FOR can easily be spoofed. "
  [x-forwarded-for]
  (some-> x-forwarded-for
          (s/split #"," 2)
          first
          s/trim))

(defn maybe-http-version
  "Take http version frim VIA header if present"
  [via]
  (some-> via
          (s/split #" " 2)
          first
          s/trim))

(defn api-gw-event->ring-request
  ([ev] (api-gw-event->ring-request ev nil))
  ([ev ctx]
   (let [headers (get ev :headers {})]
     {:server-port (str->int (:X-Forwarded-Port headers))
      :body (:body ev)
      :server-name (:Host headers)
      :remote-addr (maybe-remote-address (:X-Forwarded-For headers))
      :uri (:path ev)
      :query-string (codec/form-encode (get ev :queryStringParameters {}))
      :scheme (maybe-http-version (:Via headers))
      :request-method (:httpMethod ev)
      :protocol (:X-Forwarded-Proto headers)
      :headers headers
      :event ev
      :context ctx})))

(defmulti wrap-body class)
(defmethod wrap-body String [body] body)
(defmethod wrap-body ISeq [body] (s/join body))
(defmethod wrap-body File [body] (slurp body))
(defmethod wrap-body InputStream [body] (slurp body))

(defn ring-response->api-gw-response
  [response]
  {:statuCode (:status response)
   :headers (:headers response)
   :body (wrap-body (:body response))})

(defn handle-request
  "Handle an api-gateway request from IN via a RING-HANDLER writing
  response to OUT."
  [ring-handler in out ctx]
  (let [event (stream->event in)
        request (api-gw-event->ring-request event ctx)
        response (ring-handler request)
        event-response (ring-response->api-gw-response response)]
    (with-open [w (io/writer out)]
      (json/write event-response w))))

(defn -handleRequest
  "Implementation for RequestStreamHandler handleRequest using IN
  instream OUT outstream and CTX context object, delegating to
  handle-request to handle request using ring"
  [_ in out ctx]
(handle-request sample-handler in out ctx))

All I want for XMas … is a Brainfuck interpreter in Clojure?

Over the holidays I felt it was time to play with a little Clojure, and since I recently became interested in compilers and interpreters I felt like it was a good idea to start extremly simple, it is the holidays after all. So I built the simplest possible interpreter, a Brainfuck interpreter. It is quite a need excercise and most certainly made me more interesting in building more complex ones.

So here it goes clojure-brainfuck for anyone interested.

Projectile and TRAMP

Projectile requires a lot of file system interaction to stay up to date, this does not work well when accessing remote files and causes massive slowdowns when used over a less than ideal SSH connection. My solution based on a comment regarding this issue has been to deactivate projectile on remote files, sadly its not just files but also dired buffers which suffer so a small addition is needed to the solution in the comment adding dired buffers to the list of things dired should not be enabled for.

(defadvice projectile-on (around exlude-tramp activate)
  "This should disable projectile when visiting a remote file"
  (unless  (--any? (and it (file-remote-p it))
                   (list
                    (buffer-file-name)
                    list-buffers-directory
                    default-directory
                    dired-directory))
    ad-do-it))

furthermore to avoid unneeded calculation of the current project the projectile modeline needs to be set static.

(setq projectile-mode-line "Projectile")

with this in place projectile works nicely locally and remote file interactions are as quick as they can be.