## Lambda Calculus in ML

This is a technical post (programming,offtopic) and there’s nothing about England whatsoever, but if you are still interested you can read on of course 🙂

Currently, I’m reading TAPL. When reading about lambda calculus, I wanted to see how near ML is from lambda calculus and if the basic blocks of LC can easily be “implemented” in ML (of course the answer is yes but the similarity was interesting). On the left the functions are defined in LC, on the right side in ML:

tru = λt. λf. t; → let tru = fun t -> fun f -> t

fls = λt. λf. f; → let fls = fun t -> fun f -> f

test = λl. λm. λn. l m n; → let test = fun l -> fun m -> fun n -> l m n

pair = λf. λs. λb. b f s; → let pair = fun f -> fun s -> fun b -> b f s

fst = λp. p tru; → let fst = fun p -> p tru

snd = λp. p fls; → let snd = fun p -> p fls

Having defined these basic functions we can make some calculations in the ML toplevel:

# test tru 1 2;;

– : int = 1

# test fls 1 2;;

– : int = 2

# pair “A” “B”;;

– : (string -> string -> ‘_a) -> ‘_a = <fun> (* curried function, expecting a boolean as third argument *)

# fst (pair “A” “B”);;

– : string = “A”

# fst(snd(pair 1 (pair 2 3)));;

– : int = 2

Conclusion? To implement Lambda Calculus in an exisiting programming language you will need high-order functions and function currying support by the language. ML has both. Maybe because it IS based on Lambda Calculus? 😉

Happy New Year.

Such satanic practices…

Perhaps FP would reach true mainstream adoption (read: demand throughout the entire software industry) if it were dumbed down a bit. I mean, end users don’t give a rat’s ass about what their software is built, but developers do care.

So the “FP revolution” might start with giving people UIs with boxes and connectors and other such things to build up stuff in a clickety-click fashion. There should be buttons to verify/whatever-domain-specific-action the stuff. The point is to dumb the whole development process down for the majority of the people who haven’t a clue of FP (I’m thinking about myself).

Perhaps at the same time we’d be able to step out of the clumsy software development ways and user interfaces which still mimic the ways how mechanical typewriters were used to type up sheets of paper in the year 1900. We’ve got these wonderful electronic computers with big screens and powerful visualization capabilities and technologies for unforeseen possibilities of human-computer interaction, and how do we use such systems to develop new systems…? Not very efficiently, I say.

We’re still stuck with the analogy “a program is like a novel mechanically typed to sheets of paper and therefore it should also be visualized as such forever and ever”. Hmm, maybe I should write some more about this!

SlinkyJanuary 16, 2007 at 10:25 pm