Page 1 of 1

Currying and Combinators Learn basic combinators in Scheme

#1 Jaakuuta  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 163
  • Joined: 02-July 09

Post icon  Posted 26 September 2009 - 09:52 AM

Hello!
This tutorial is designed to teach you about the basics of currying and combinators using a language that's designed to be almost pure lambda calculus, so it's very fitting for the task.

First, let's start by explaining what currying is. This technique was named after the logician Haskell Curry who rediscovered it at around the same time as the Lambda Calculus was being developed. Basically the idea is that you can start with a problem like what would be written in normal algebra as f(x, y) = x + y and rewrite it so that it appears as f(x) => y... g(y)... or g(f(x)) This isn't as easy to show with just algebraic functional notation. So let's give a concrete example. Suppose we have f(x, y) = x + y . Then we can take this and make a new function g(y) = "+ y" and f(x) = x, then putting them together, we have g(f(x)) = x + y . This is where combinators come in. The function g(y) acts as a simple combinator. Let's see how this looks in lambda notation...
^xy.x + y => (^x. (^y. x + y))
This is saying basically "take some number x, whatever it may be, then add y to it before evaluating x. This means, if you apply this function once to a number, then you'll be left with the first function g(y) = "+ y" . Then when you apply it to a second number, it will become x + y.
Let's see this in Scheme to see this process in action:
(define f
  (lambda (x)
	(lambda (y) (+ x y))))

;value: f

(define g
  (f 3))

;value: g

(g 4)

;value: 7


This means you can also define a generic increment function using this function.
(define succ
  (f 1))

;value: succ


I named it succ because that's the name used in a lot of functional languages to refer to this specific function.
Now you can use this function to generate numbers by incrementing them one at a time. Or you can make increment functions by using multiple applications of the succ function.
(succ (succ 0))

;value: 2

(succ (succ (succ (succ (succ 0)))))

;value: 5

(define add2
  (lambda (x)
	(succ (succ x))))

;value: add2

(add2 0)

;value: 2

(add2 (add2 0))

;value: 4

(add2 (succ 0))

;value: 3

(add2 (add2 (succ 0)))

;value: 5


Now let's go on to something a little bit more interesting. This next function we will be defining is a function that applies some other function to a variable. This is a generally useful function because you can use it for a lot of different things. This is what's known as a partial application. Let's call this function parap.
(define parap
  (lambda (f x)
	(lambda (y) (f x y))))

;value: parap

(define dbl;that is "double"
  (parap * 2))

;value: dbl

(dbl 2)

;value: 4

(dbl 6)

;value: 12

(define succ;redefining succ with parap
  (parap + 1))

;value: succ

(succ 0)

;value: 1


You can even define a function without naming it and use it to apply it to something all in one statement.
((parap * 2) 2)

;value: 4


This may seem a bit pointless for a function this small, but for chained functions it can be useful. One thing to point out at this point is so far all the functions I've shown you use functions that are commutative. That is, it doesn't matter what order the arguments come in. However, with this method, we have it that whatever function we define with parap has the argument passed to parap as the first argument of the whole function. Therefore, something like (dbl 3) would be defined as (* 2 3) and not (* 3 2)... Suppose we wanted to make it so that we do have the argument in the second section? Then we will have to make a new combinator that will change positions between the two arguments. This is usually known as swap in functional languages.
(define swap
  (lambda (f)
	(lambda (x y) (f y x))))

;value: swap

((parap (swap /) 2) 1)

;value: 1/2


What this is basically saying is the swap function takes the operator or function that will be acting upon the arguments that follows it, then waits for the next two arguments and simply swaps their position and returns it to be used with the calling function. Now that we have this, we can make a list of functions that will use the four basic arithmetic operations.
(define succ
  (parap + 1))

;value: succ

(define dec
  (parap (swap -) 1))

;value: dec

(define dbl
  (parap (* 2)))

;value: dbl

(define half
  (parap (swap /) 2))

;value: half


Now we can start doing some more neat things like function composition and the like. I will teach you how to take an algebraic expression of one variable and express it in terms of a single function that can be applied to that variable without using the name of the variable at all within the function. This is what's known as a tacit definition. First, let's start out with a combinator for composition.
(define cmp
  (lambda (f g)
	(lambda (x) (f (g x)))))

;value: cmp

;let's try composing some of the opposite functions we made last time to see
;that they cancel one another out

((cmp half dbl) 2)

;value: 2

((cmp dec succ) 3)

;value: 3


Also, we can come up with a composition combinator that will take two functions, apply them to an argument, then apply another function to the results of those two functions. This is known as a fork.
(define fork
  (lambda (f g h)
	(lambda (x)
	  (f (g x) (h x)))))

;value: fork

((fork - dbl succ) 3)

;value: 2

;that is (- (dbl 3) (succ 3)) or 6 - 4


Now we can make some simple polynomial expressions in tacit form.
;f(x) = 2x^2 + 1

(define f
  (cmp succ (cmp dbl square)))

;value: f

(f 3)

;value: 19

;g(x) = 4x^2 +6x - 3

(define g
  (cmp (parap (swap -) 3) (fork + (parap * 6) (cmp (parap * 4) square))))

;value: g

(g 0)

;value: -3
[/swap]
See, we got to use both our composition and our fork on that last one.  Not once did we actually use the variable 'x' the whole time in that definition.  That's tacit programming in action with the use of combinators.
One last neat little combinator I wanted to teach you about before I finish off this tutorial.  That's the combinator that will take one argument and double it.  This can be used together with other such combinators to make an arbitrarily long list of arguments out of one.
[code]
(define dbler
  (lambda (f)
	(lambda (x) (f x x))))

;value: dbler

((dbler *) 9)

;value: 81

((dbler *) 1.414)

;value: 1.9993959999999997

;see how the above value is almost 2?  we've just made our own version of
;the square function


This type of programming is not limited to just the Scheme language. Actually, it's used efficiently in a lot of functional languages. I plan on making some tutorials to show how this can be done in other languages, but I figured that Scheme would be the easiest to start with as it's one of the closest languages to pure lambda calculus.
Hopefully you found this tutorial useful.
Have a nice day!

Is This A Good Question/Topic? 0
  • +

Page 1 of 1