Cost of "auxiliary" functions

[duke]

In a SML tutorial that I'm reading, the comment is made:

[quote]
An "auxiliary" function (....) is used to do most of the work. This is not at all unusual in a functional language. Because we do not normally use "variables", we can only have values in parameters, which sometimes requires the use of more than one function in order to perform a single computation.[/quote]

Is the absence of "global" variables in SML (FP in general) "expensive", in having to use use extra functions as a work-around?

[Paul Rubin]

Post by duke
An "auxiliary" function (....) is used to do most of the
work... Because we do not normally use "variables",...
Is the absence of "global" variables in SML (FP in general)
"expensive", in having to use use extra functions as a work-around?

1. The issue is not absence of global variables, but absence (or at
least deprecation) of any variables at all. That means no loops in the
traditional sense (because of no index variable). So you have to use
recursion where in imperative languages you would use a loop. To avoid
stack buildup, you want to put the recursion in the tail position, and
sometimes that requires writing an auxiliary function. Classic example
of tail-recursive factorial (in Haskell, so ignore lazy evaluation
issues for this example):

fac n = fac-aux 1 n

` fac_aux a 0 = a
fac_aux a n = fac_aux (a*n) (n-1)

2. Generally, good FPL compilers know how to compile tail recursion
efficiently since it's such an important technique.

[duke]

Post by Paul Rubin

Post by duke
An "auxiliary" function (....) is used to do most of the
work... Because we do not normally use "variables",...
Is the absence of "global" variables in SML (FP in general)
"expensive", in having to use use extra functions as a work-around?

1. The issue is not absence of global variables, but absence (or at
least deprecation) of any variables at all. That means no loops in the
traditional sense (because of no index variable). So you have to use
recursion where in imperative languages you would use a loop. To avoid
stack buildup, you want to put the recursion in the tail position, and
sometimes that requires writing an auxiliary function. Classic example
of tail-recursive factorial (in Haskell, so ignore lazy evaluation
fac n = fac-aux 1 n
` fac_aux a 0 = a
fac_aux a n = fac_aux (a*n) (n-1)
2. Generally, good FPL compilers know how to compile tail recursion
efficiently since it's such an important technique.

I found this:

http://stackoverflow.com/questions/33923/what-is-tail-recursion

explaining tail recursion. The examples given all seem to use a variable to keep track of the intermediate values. I'm trying to grok how tail-recursion works in SML where there are zero variables available - unless _it_ is used as such?

Anyway, I'm still curious as to whether or not is tail recursion more expensive than traditional loops? :) Thanks for your input!!

[Paul Rubin]

Post by duke
http://stackoverflow.com/questions/33923/what-is-tail-recursion
explaining tail recursion. The examples given all seem to use a
variable to keep track of the intermediate values. I'm trying to grok
how tail-recursion works in SML where there are zero variables
available - unless _it_ is used as such?

I don't see any variables in the tail recursion example, so maybe you're
confused by the term "variable" in this context. In an imperative
language, you can say:

i = 5; // assign the value 5 to i
i += 1; // now change the value from 5 to 6

What is the value of i in the above? It's 5 in one place and 6 in
another, i.e. it *varies*. That's why it's a *variable*. Functional
programming doesn't have variables. You can say

i = 5

which is called an "equation" rather than an assignment. It means i is
equal to 5, and anywhere you see "i" in that lexical scope, you can
substitute 5 instead ("referential transparency"). You can't change the
value of i once you have declared it to be 5. So you can't have a loop
like "for i = 1 to 5 do ..." since the value of i would change as you
went through the loop. Therefore, you use recursion like in the
stackoverflow thread, binding i to new values by creating new scopes
through the recursive calls. To print the numbers from 1 to 5 in
Haskell, you could say (untested):

f n = if n > 5
then return ()
else do { print n; f (n+1) }

main = f 1

You see there is a parameter called n, which doesn't vary, but instead,
we reach the next iteration by a new recursive call with the newly
computed parameter n+1. In practice in Haskell, you don't have to write
the recursions explicitly very often, since library functions (like map,
foldr, etc.) manage to hide most of it behind the scenes.

Post by duke
Anyway, I'm still curious as to whether or not is tail recursion more
expensive than traditional loops? :) Thanks for your input!!

Tail recursion and traditional loops should compile to the same code if
the compiler is careful.

You might read the book "Structure and Interpretation of Computer
Programs" (search for the title). The text is online if you don't
want a printed copy.

[duke]

Post by Paul Rubin
You might read the book "Structure and Interpretation of Computer
Programs" (search for the title). The text is online if you don't
want a printed copy.

Great book! I refer to it often ...

[Andreas Rossberg]

   i = 5;    // assign the value 5 to i
   i += 1;   // now change the value from 5 to 6
What is the value of i in the above?  It's 5 in one place and 6 in
another, i.e. it *varies*.  That's why it's a *variable*.  Functional
programming doesn't have variables.

Correction: FP *has* variables just fine. It just doesn't have
*mutable* variables (or at least, most variables aren't mutable). Five
decades of dominance of imperative programming have somehow mislead
too many people to equate the former with the latter. But that's not
what "variable" has meant for centuries, e.g. in math, where a
variable is simply a placeholder. Any identifier effectively is a
variable, especially if it does not have a constant definition.

Some people even argue that the mutable entities in programming
languages should never have been called "variables", since they are
something else entirely (references, cells, assignables are
alternative names used in CS circles). See e.g. Bob Harper's post on
the subject: http://existentialtype.wordpress.com/2012/02/01/words-matter/

/Andreas

[duke]

Post by Andreas Rossberg

   i = 5;    // assign the value 5 to i
   i += 1;   // now change the value from 5 to 6
What is the value of i in the above?  It's 5 in one place and 6 in
another, i.e. it *varies*.  That's why it's a *variable*.  Functional
programming doesn't have variables.

Correction: FP *has* variables just fine. It just doesn't have
*mutable* variables (or at least, most variables aren't mutable). Five
decades of dominance of imperative programming have somehow mislead
too many people to equate the former with the latter. But that's not
what "variable" has meant for centuries, e.g. in math, where a
variable is simply a placeholder. Any identifier effectively is a
variable, especially if it does not have a constant definition.
Some people even argue that the mutable entities in programming
languages should never have been called "variables", since they are
something else entirely (references, cells, assignables are
alternative names used in CS circles). See e.g. Bob Harper's post on
the subject:http://existentialtype.wordpress.com/2012/02/01/words-matter/

What a great article B. Harper wrote!! And IMHO, the term "assignable"
is
quite appropriate, and deserves wider, if not general, usage.

I now "get", that SML does not have assignables, but rather algebraic-
type
variables that behave more like "constants" in imperative languages.
However,
I also see that I'm going to have to get into an "algebraic" mind-set
"real soon now" if I'm ever going to grok FPLs. :)

[Andreas Rossberg]

Post by duke
I now "get", that SML does not have assignables, but rather algebraic-
type variables that behave more like "constants" in imperative languages.

SML, being an impure functional language, has "assignables" in the
form of the 'ref' type. But they are first-class and independent from
variables, i.e. they may or may not be bound to a variable.

let
val s = ref "Hello "
in
print (!s);
s := "world!";
print (!s)
end

/Andreas

[duke]

Post by Andreas Rossberg

Post by duke
I now "get", that SML does not have assignables, but rather algebraic-
type variables that behave more like "constants" in imperative languages.

SML, being an impure functional language, has "assignables" in the
form of the 'ref' type. But they are first-class and independent from
variables, i.e. they may or may not be bound to a variable.
let
  val s = ref "Hello "
in
  print (!s);
  s := "world!";
  print (!s)
end

That's just great!!! Now I have to choose between impure and pure
FPLs. :)
I knew that OCAML had the "ref" syntax, but I haven't yet found it in
the SML stuff that I'm reading. Thanks ...

[Paul Rubin]

Post by Andreas Rossberg
  print (!s);
  s := "world!";
  print (!s)

That's just great!!! Now I have to choose between impure and pure FPLs. :)

The impurity comes from any sort of side effect in the function, such as
the print statements. A pure language wouldn't allow printing from a
pure function. The reference cell update is just another such effect.
You can think of it as similar to an i/o operation, and in Haskell (with
IORef) it is treated as one. Another Harper blog post:

http://existentialtype.wordpress.com/2011/05/01/of-course-ml-has-monads/

[duke]

Post by Paul Rubin

Post by Andreas Rossberg
  print (!s);
  s := "world!";
  print (!s)

That's just great!!! Now I have to choose between impure and pure FPLs. :)

The impurity comes from any sort of side effect in the function, such as
the print statements.  A pure language wouldn't allow printing from a
pure function.  The reference cell update is just another such effect.
You can think of it as similar to an i/o operation, and in Haskell (with
http://existentialtype.wordpress.com/2011/05/01/of-course-ml-has-monads/

Way over my head at this point! But thanks anyway. I'd better take it
slow with FPLs, or I'll sour on them, and nuke the the compilers off
of my boxen. :)

I should look at a pure FPL, with minimum "ifs, ands, or buts" - if
such a language exists. I have Miranda installed on my Linux box, and
Amanda on Windoze7. I should give them a look.

[Paul Rubin]

Post by duke
I should look at a pure FPL, with minimum "ifs, ands, or buts" - if
such a language exists. I have Miranda installed on my Linux box, and
Amanda on Windoze7. I should give them a look.

Nobody uses Miranda any more, and I haven't even heard of Amanda.
Haskell is pretty much Miranda's successor so you might like to
give it a try. http://learnyouahaskell.com is a good introduction,
as already mentioned.

[duke]

Post by Paul Rubin

Post by duke
I should look at a pure FPL, with minimum "ifs, ands, or buts" - if
such a language exists. I have Miranda installed on my Linux box, and
Amanda on Windoze7. I should give them a look.

Nobody uses Miranda any more, and I haven't even heard of Amanda.
Haskell is pretty much Miranda's successor so you might like to
give it a try. http://learnyouahaskell.com is a good introduction,
as already mentioned.

OK! OK! You win!! LOL ....
I just installed Haskell and I'll give the above link another go.

As for Miranda http://miranda.org.uk/ , I see that David even supports MacOS X Lion - so it isn't dead yet, and could become useful given a gung-ho community. :)

Amanda - http://www.cs.ucl.ac.uk/teaching/3C11/amanda.html

[Paul Rubin]

Post by duke
As for Miranda http://miranda.org.uk/ , I see that David even supports
MacOS X Lion - so it isn't dead yet, and could become useful given a
gung-ho community. :)

Heh, ok, but I suspect it's mostly for legacy users. You could also
look at Clean. Miranda, Haskell, and Clean may all be a bit confusing
at first because of their use of lazy evaluation, a somewhat separate
issue from purity. I had a lot of trouble with this, though I'm getting
better at it.

[duke]

Post by Paul Rubin

Post by duke
As for Miranda http://miranda.org.uk/ , I see that David even supports
MacOS X Lion - so it isn't dead yet, and could become useful given a
gung-ho community. :)

Heh, ok, but I suspect it's mostly for legacy users. You could also
look at Clean. Miranda, Haskell, and Clean may all be a bit confusing
at first because of their use of lazy evaluation, a somewhat separate
issue from purity. I had a lot of trouble with this, though I'm getting
better at it.

"Introduction to Functional Programming" http://www.st.cs.ru.nl/papers/cleanbook/CleanBookI.pdf from the Clean wiki appears to be a very well written intro to Clean.

[Paul Rubin]

Post by duke

Correction: FP *has* variables just fine... See e.g. Bob Harper's post on
the subject:http://existentialtype.wordpress.com/2012/02/01/words-matter/

Harper's terminology is not all that standard. Obviously "variable" is
a somewhat overloaded term and I used it in the sense of "assignable".
I agree that "assignable" is a better term.

Post by duke
I now "get", that SML does not have assignables, but rather algebraic-
type variables that behave more like "constants" in imperative
languages. However, I also see that I'm going to have to get into an
"algebraic" mind-set "real soon now" if I'm ever going to grok FPLs. :)

To make things worse, "algebraic datatype" means something else
entirely, the equivalent of a tagged union. SML does have mutable
reference cells but you shouldn't have to use them very often. Haskell
has something similar (STRef and IORef) that is more precisely managed
by Haskell's type system (the ST and IO monads).