Friday, December 19, 2008

The Y-Combinator

I finally found the time to grok the Y-combinator. There are already multiple examples available but I am to thick to get them and, therefore, wanted to derive it myself.

The Y-combinator is a wonderful piece of software that allows you to create self-referential programs without built-in support. That is, it allows me to create anonymous recursive functions. This is best shown by an example.

```; The factorial function
(define fact
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))

```

In the recursive function above the fact refers to itself by name. This relies on the name being available before it is actually defined. To avoid this we can send the function as a parameter to itself. Like so:

```; Define a local variable g as the function.
; The function takes a function (itself) as an extra parameter.
; The function is called with itself as a parameter:  (g g 5)).
; This doesn't compile since the function h (that is g) requires
(let ((g (lambda (h n)
(if (< n 2) 1 (* n (h  (- n 1)))))))
(g g 5))

; The working version needs h to also call itself (h h (- n 1)).
(let ((g (lambda (h n)
(if (< n 2) 1 (* n (h h (- n 1)))))))
(g g 5))

```

We can now abstract over the h parameter with a technique reminiscent of currying.

```; A new lambda is abstracted over h.
; Note that the function calls to g and h need to change ((g g) 5))
; and ((h h) (- n 1)) to ensure that they agree with the definitions.
(let ((g (lambda (h)
(lambda (n)
(if (< n 2) 1 (* n ((h h) (- n 1))))))))
((g g) 5))

```

We can now abstract over n and (h h) creating a new lambda with the parameters q and m.

```; Function f is declared locally with the parameters q and m
; and then called directly (f (h h) n).
(let ((g (lambda (h)
(lambda (n)
(let ((f (lambda (q m)
(if (< m 2) 1 (* m (q (- m 1)))))))
(f (h h) n)))))
((g g) 5)))

```

Notice that f is independent of it’s context and can be moved to the top level.

```; f moved to the top level.
(let ((f (lambda (q m)
(if (< m 2) 1 (* m (q (- m 1)))))))
(let ((g (lambda (h)
(lambda (n)
(f (h h) n)))))
((g g) 5)))

```

I can now abstract over q to isolate the definition of fact.

```; Notice that the inner function of f is the original fact function.
(let ((f (lambda (q)
(lambda (m)
(if (< m 2) 1 (* m (q (- m 1))))))))
(let ((g (lambda (h)
(lambda (n)
((f (h h)) n)))))
((g g) 5)))

```

Now I abstract over the local variable f and declare a new variable Y. The call to ((g g) 5) is replaced (g g) and moved to the Y function instead.

```; A new variable Y is created for the abstraction over f.
; The function call is moved to the application of Y.
(let ((Y (lambda (f)
(let ((g (lambda (h)
(lambda (n)
((f (h h)) n)))))
(g g)))))
((Y (lambda (q)
(lambda (m)
(if (< m 2) 1 (* m (q (- m 1))))))) 5))

```

Finally we replace the local variable Y with a the function Y, the Y-combinator.

```(define Y
(lambda (f)
(let ((g (lambda (h)
(lambda (n)
((f (h h)) n)))))
(g g))))

```

Excellent!

Monday, December 15, 2008

Thoughts on Simplicity

A scientific theory should be as simple as possible, but no simpler. —Albert Einstein

Do the simplest thing that could possibly work. Keep it simple by refactoring. —Kent Beck

If you think something is clever and sophisticated, beware: it is probably self-indulgence. —Donald Norman

Simplicity does not precede complexity, but follows it. —Alan Perlis

To make something generic is to make the simple things complex. —Adam Keys

Simple things should be simple. Complex things should be possible. —Alan Kay

Don’t EVER make the mistake that you can design something better than what you get from ruthless massively parallel trial-and-error with a feedback cycle. That’s giving your intelligence much too much credit. —Linus Torvalds

Consistency is Simplicity: A consistent approach to style and solutions can make code easier to maintain. —Ken Pugh

If you think you’re designing something for idiots, the odds are that you’re not designing something good, even for idiots. —Paul Graham

It is better to be wrong than to be vague. —Fred Brooks

Simplicity is the ultimate sophistication. —Leonardo da Vinci

If you want to make something 10 times cheaper, remove 90 percent of the material—Amy Smith

Wednesday, December 10, 2008

What is "declarative" anyway?

Declarative programming often seems – to me – as the holy grail of programming. But what does it really mean?

According to Dictionary.com

Declarative – serving to declare, make known, or explain: a declarative statement.

or

Declarative – a mood (grammatically unmarked) that represents the act or state as an objective fact [syn: indicative mood]

or

Declarative – making declaration, proclamation, or publication; explanatory; assertive; declaratory.

So, the word means explanatory or stated as facts.

In the context of programming declarative is usually contrasted with imperative and procedural, where imperative programming means programming by changing state and procedural programming means that a detailed algorithm is used.

Wikipedia states

Declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow.

or

Declarative programming attempts to minimize or eliminate side effects by describing what the program should accomplish, rather than describing how to go about accomplishing it.

So, in this context, declarative means without describing the control flow and without side effects.

Does this mean that I am programming declaratively when I am writing immutable object oriented code (without side effects) with fluent interfaces (explanatory)?

Or does it mean I am programming declaratively when I set up a large table, or even a database, of stated facts that I use to drive my application?

Or, who cares?