Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Turing as a Functional Programming Language
Author Message
MysticVegeta

Posted: Fri May 26, 2006 2:40 pm   Post subject: (No subject)

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

Posted: Fri May 26, 2006 3:37 pm   Post subject: (No subject)

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

Posted: Fri May 26, 2006 9:15 pm   Post subject: (No subject)

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.

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

Posted: Sat May 27, 2006 5:41 pm   Post subject: (No subject)

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

Posted: Mon May 29, 2006 1:25 pm   Post subject: (No subject)

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

Posted: Mon May 29, 2006 1:32 pm   Post subject: (No subject)

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

Posted: Mon May 29, 2006 2:10 pm   Post subject: (No subject)

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))

 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

Posted: Mon May 29, 2006 4:42 pm   Post subject: (No subject)

Bah, polyglot...

Cervantes

Posted: Mon May 29, 2006 5:22 pm   Post subject: (No subject)

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

Posted: Tue Jan 13, 2009 5:38 pm   Post subject: RE:Turing as a Functional Programming Language

this was really helpful to me
syntax_error

Posted: Tue Jan 13, 2009 5:50 pm   Post subject: Re: RE:Turing as a Functional Programming Language

kishan25 @ Tue Jan 13, 2009 5:38 pm wrote:
this was really helpful to me

redsp0t

Posted: Sun Nov 14, 2010 10:16 pm   Post subject: RE:Turing as a Functional Programming Language

Amazing guide, really helpful like all of your other guides.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 2  [ 27 Posts ]
Goto page Previous  1, 2
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: