Turing as a Functional Programming Language

[MysticVegeta]

For the area under a curve one we could use some integral calculus, simple 1 line function with no recursion.

code:

function area (power : int, low, high : int) : real     result ((high ** (power + 1)) / (power + 1)) - ((low ** (power + 1)) / (power + 1)) end area put area (2, 0, 5)

[zylum]

your code will only work for functions of the form f(x) = x^power... the point is that you can pass any function to cervantes code and it will calculate the area. i'd imagine it would be quite difficult to implement code that finds the integral to any function (like here: http://integrals.wolfram.com/index.jsp)

[Cervantes]

Propogation of Functions: functions that return functions
(with imaginary Turing syntax)

What is a function? This is a question of a time long ago, when you were first learning the fundamentals of a function. You learned it is a block of code that takes some values as parameters and returns another value, or something like that.

Take this definition, but recall what I said in the opening of this tutorial.

Cervantes wrote:

functions in a functional language are first-class values, just like integers or strings


If a function is a first-class value, and if a function is just something that takes parameters and returns a value, then that value that it returns could itself be a function. In fewer words: A function that returns a function.

Function Composition

Here's an example. Say we have two functions, f(x) = x^2 and g(x) = x + 1. What is the value of f(g(x)) (also written as f̥̥̥̥⃝g, read as f composed with g)? Going through the math, it would be f(x + 1) = (x + 1)^2. Let's code this.
First, we'll define our functions


code:

function f (x : real) : real     result x ** 2 end f function g (x : real) : real     result x + 1 end g


Nothing new here. This is valid Turing syntax. However, this section is going to require us to pretend Turing can create anonymous functions, so we'll use the same syntax I introduced in part one. Let's redefine those functions, using this syntax:


code:

var f : (function (x : real) : real) := lambda {[x : real] x ** 2} var g : (function (x : real) : real) := lambda {[x : real] x + 1}


That's a pretty hefty data type, though. It's a lot to "type". Let's factor that out into a type (oh, oh, pun!):


code:

type real2real : (function (x : real) : real) var f : real2real := lambda {[x : real] x ** 2} var g : real2real := lambda {[x : real] x + 1}


Now we must write a compose function:


code:

function compose (f, g : real2real) : real2real     var c : real2real := lambda {[x : real] f (g (x))}     result c    % I defined the variable, 'c', just to specify the type of the function returned. end compose


And put it to action:


code:

var h : real2real := compose (f, g) put h (5)       % outputs (5 + 1)^2 = 36


Function composition allows us to "compose" new functions from previously existing ones. This is a powerful concept, allowing us to code only the most basic functions, building the more advanced functions from them.

Partial Function Application

Once more, let's go back to our previous knowledge of functions. If I have a function f(a, b) = a + b, then calling f(5, 7) is acceptable, but calling f(5) is not. Why does calling f with only one parameter necessitate an error?

That's obvious, for sure. We can't return an integer if we are missing values to plug a + b. Fair enough: we can't return an integer. What can we return?

We can return a function. Since f(a, b) = a + b, f(5) = 5 + b. 5 + b is just another function. This is quite intuitive: if my function takes two parameters, then fixing one of them to a certain value returns another function that now only relies on one parameter.

Implementing PFA method one


Now, to implement this in Turing, we're not only going to have to use our "lambda" syntax for anonymous functions, we're going to have to use function overloading. In case you're not familiar with this concept, we'll take a very brief detour to explain it.

Detour: Function Overloading


Languages that support function overloading (languages such as my imaginary version of Turing) allow multiple copies of a function by the same name to exist, so long as they all take different parameters. When that function is called, the version of that function that is run is determined by the parameters passed in the function call. For example, if I have a function f(a, b) = a + b and another version of that function, f(a) = a + 5, then I can call f with either one or two parameters.



Using function overloading, here is an implementation of Partial Function Application on the function f in iTuring.


code:

function f (a, b : int) : int     result a + b end f function f (a : int) : (function (b : int) : int)     result lambda {[b : int] a + b} end f


Now we can call this function f like this:


code:

put f (5, 7)      % => 12 put (f (5)) (7)   % => 12


The second represents f (5) creating a new function that takes 7 as a parameter and returns 5 + 7 = 12.

There's another way we can implement PFA, however; one that does not require function overloading.



Implementing PFA method two


This approach involves our function f returning a function that returns a function...


code:

var f : ((function (a : int) : (function (b : int) : int))) := lambda {[a : int] lambda {[b : int] a + b}}


Calling f now looks like this:


code:

put (f (5)) (7) % => 12





What's the point?


There is no point to Partial Function Application if we're just going to use it like (f (5)) (7). We might as well just write f (5, 7). So what's the point?

Partial Function Application, just like Function Composition, allows us to quickly and easily create new functions from a base of functions. Say we had a function to multiply two numbers,


code:

var mul := lambda {[a, b : int] a * b}


We could then, using PFA, create functions with names based on the English language:


code:

var double := mul (2) var triple := mul (3) % ...



We could also pass the function returned by our PFA technique into another function. Assuming we've got an already initialized IntArray object based on my IntArray class from the TURuby section of this tutorial, the following code doubles each element in our array.


code:

int_array -> map (mul (2))


No need to go through all the 'lambda' business. This one is actually readable, too: "map 'multiply by 2' onto int_array".

[wtd]

Good stuff. I would mention that this works much better in languages where it's actually meant to happen.

[MysticVegeta]

wait a sec, if this is all imaginary syntax, then what you are trying to do by writing this tut? Are you sending something to holtsoft to implement these features or is it jsut for beginners to functional programming like me understand this concept, but not be able to do this turing?

[Delos]

MysticVegeta wrote:

wait a sec, if this is all imaginary syntax, then what you are trying to do by writing this tut? Are you sending something to holtsoft to implement these features or is it jsut for beginners to functional programming like me understand this concept, but not be able to do this turing?

Essentially the latter. There's nothing wrong or outlandish about presenting a theoretical tutorial. If people are able to follow along with it, then it might just be time for them to embrace another language to implement such structures.
Personally, I find that having these conceptually challenging ideas thrown around quite conducive to my own coding. The more I read about functional programming, the more I use it (even if it still is in Turing). Getting into good habits, methinks...

[wtd]

A lot of it is fictional in Turing. But it's not imaginary elsewhere.

Cervantes' lambda syntax is imaginary. I know, I helped devise it.

But, there are lots of languages where this can be done.

Common Lisp:

code:

(let ((foo (lambda (bar) (+ (* bar 2) 1))))    (funcall foo 4))

Scheme:

code:

(let ((foo (lambda (bar) (+ (* bar 2) 1))))    (foo 4))

Haskell:

code:

let foo = \bar -> bar * 2 + 1 in foo 4

Or using composition:

code:

let foo = (+ 1) . (* 2) in foo 4

O'Caml:

code:

let foo = fun bar -> bar * 2 + 1 in    foo 4

SML:

code:

let    val foo = fn bar => bar * 2 + 1 in    foo 4 end

Python:

code:

foo = lambda bar: bar * 2 + 1 foo(4)

Ruby:

code:

foo = lambda { |bar| bar * 2 + 1 } foo.call(4)

Smalltalk:

code:

| foo |    foo := [ :bar | bar * 2 + 1 ].    foo value: 4

Io:

code:

foo := block(bar, bar * 2 + 1) foo(4)

Scala:

code:

val foo = bar: Int => bar * 2 + 1 foo(4)

C# 3.0:

code:

var foo = bar => bar * 2 + 1; foo(4);

Nice:

code:

let Any->Any foo = Any bar => bar * 2 + 1; foo(4);

I likely left out a huge number of languages.

[Delos]

Bah, polyglot...

[Cervantes]

Nice, wtd! As wtd's post clearly shows, the idea of anonymous functions is a big deal. It's a big deal because it relieves the heavy burden of declaring a function before using it for it's one time purpose, as illustrated by the TURuby section.

MysticVegeta wrote:

wait a sec, if this is all imaginary syntax, then what you are trying to do by writing this tut? Are you sending something to holtsoft to implement these features or is it jsut for beginners to functional programming like me understand this concept, but not be able to do this turing?

As Delos said, the latter. This tutorial serves as a segue to higher level languages. The concepts discussed in this tutorial (and in the full OOP tutorial) are very applicable to programming languages, though less so to Turing. Thus, these tutorials begin the journey into new programming paradigms from within the comfortable world of Turing, thereby making the transition to new languages easier.

[kishan25]

this was really helpful to me

[syntax_error]

kishan25 @ Tue Jan 13, 2009 5:38 pm wrote:

this was really helpful to me

necroposting is bad.

[redsp0t]

Amazing guide, really helpful like all of your other guides.