I was just reading Ben Hutchison's blog post on functional programming:
study-functional-programming-or-be-ignorant/
and I've come to a very similar realisation, with one notable additional point
lisp.
After watching some of the
Structure and Interpretation of Computer Programs lectures,
my ideas about software, programming, data and computation have all been significantly changed.
The lectures focus on the theory of computer science using lisp.
In lisp, everything is (can be) represented as a list. This includes the source code, the interpreter, the environment, as well as data structures. The biggest change to my thinking occurred when they showed that something as fundamental as the list can be defined using closures and no other data structure. Something that I thought was an atom, built in, written in assembler; was actually definable in the language using other constructs.
This actually blew my mind.
It meant that all you needed was closures, and function application.
In the scheme example they showed in the lecture, it looked something like this:
(define (cons a b) (lambda (x) (x a b)))
(define (car x) (x (lambda (a b) a)))
(define (cdr x) (x (lambda (a b) b)))
The key is returning
a when you call
car(head), and
b when calling
cdr(tail).
I was so excited by this, I decided to implement it in a language I actually understood. ie NOT lisp.
I've been playing a bit with
clojure and
elisp, as well as
haskell and I've been reading about
F# and
OCaml; But I keep coming back to
scala, so I implemented it in that:
type consT[H, T] = ((H,T) => Any) => Any
def cons[H,T](a:H, b:T) : consT[H,T] = x => x(a,b)
def car[H,T](x:consT[H,T]) : H = x((a:H,b:T) => a).asInstanceOf[H]
def cdr[H,T](x:consT[H,T]) : T = x((a:H, b:T) => b).asInstanceOf[T]
Most of which is actually type annotations, which ensure that the methods are completely generic. This is in contrast to lisps dynamic typing.
Some simplification is possible, but it's still not really the scala way:
type consT[H, T] = ((H, T) => Any) => Any
def cons[H, T](a: H, b: T): consT[H, T] = _(a, b)
def car[H, T](x: consT[H, T]) = x((a, _) => a).asInstanceOf[H]
def cdr[H, T](x: consT[H, T]) = x((_, b) => b).asInstanceOf[T]
If scala were to have some more advanced type inference or dynamic typing, it might look something like:
def cons(a, b) = _(a,b)
def car(x) = x((a,_) => a)
def cdr(x) = x((_,b) => b)
But it's pretty clear that that's not likely.
The beauty of it is, the lisp and scala uses of the above code is pretty similar.
something like this in clojure/lisp:
(def a (cons 1 (cons 2 3)))
(car a)
(car (cdr a))
(cdr (cdr a))
in scala:
val a = cons(1, cons(2, 3))
car(a)
car(cdr(a))
cdr(cdr(a))
So while the library side of things may be more complicated in scala, (also type safe), the actually usage is no more complicated at all.
