jonny goes to england

London & co

Lambda Calculus in ML

with one comment

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.


Written by jk

January 1, 2007 at 1:16 pm

Posted in offtopic

One Response

Subscribe to comments with RSS.

  1. 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!


    January 16, 2007 at 10:25 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: