A Tutorial on Programming Features in ATS:
PrevNext

Chapter 9. Recursion

The notion of recursion is ubiquitous in ATS. For instance, there are recursively defined sorts (datasorts) and types (datatypes) in the statics, and there are also recursively defined functions in the dynamics. Literally, the word recurse means "go back". When an entity is defined recursively, it means that the entity being defined can appear in its own definition. In the following presentation, I will show several ways to define (or implement) recursive functions and non-recursive functions, where the latter is just a special case of the former.

The keyword fun can be used to initiate the definition of a recursive function. For instance, following is the definition of a recursive function: 

fun
fact(x: int): int =
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

A non-recursive function is a special kind of recursive function that does not make use of itself in its own definition. So one can certainly use fun to initiate the definition of a non-recursive function. However, if there is a need to indicate explicitly that a non-recursive is being defined, then one can use the keyword fn to do so. For instance, the definiton of a non-recursive function is given as follows: 

fn square(x: int): int = x * x

which is directly translated by the compiler into the following binding between a name and a lambda-expression: 

val square = lam (x: int): int => x * x

As another example, please note that the two occurrences of the symbol fact in the following code refer to two distinct functions: 

fn
fact(x: int): int =
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

While the first fact (to the left of the equality symbol) refers to the (non-recursive) function being defined, the second one is supposed to have been declared previously.

A recursive function can also be defined as a recursive value. For instance, the recursive function fact defined above can be defined as follows: 

val
rec
fact : int -> int =
lam (x) =>
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

where the keyword rec indicates that fact is defined recursively, that is, it is allowed to appear in its own definition. In fact, the former definition of fact is directly translated into the latter one by the compiler. Of course, one may also use a reference to implement recursion: 

val
fact = ref<int->int>($UNSAFE.cast(0))
val () =
!fact :=
(
  lam (x:int):int => if x > 0 then x * !fact(x-1) else 1
) (* end of [val] *)

But this is definitely not a style I would like to advocate. For the sake of completion, I present yet another way to define fact as a fixed-point expression: 

val
fact =
fix f(x: int): int =>
  if x > 0 then x * f(x-1) else 1
(* end of [fact] *)

Of course, if one wants to, then one can always replace a lambda-expression with a fixed-point expression (or simply fix-expression for short). For instance, lambda(x:int):int => x+x can be written as fix _(x:int):int => x+x.

For defining mutually recursive functions, one can simply use the keyword and to concatenate function definitions. For instance, the following code defines two functions isevn and isodd mutually recursively: 

fun
isevn(x: int): bool =
  if x > 0 then isodd(x-1) else true
and
isodd(x: int): bool =
  if x > 0 then isevn(x-1) else false

The code, as one may have guessed, is translated by the compiler into the following form (for defining two mutually recursive values): 

val
rec
isevn : int -> bool =
  lam (x) => if x > 0 then isodd(x-1) else true
and
isodd : int -> bool =
  lam (x) => if x > 0 then isevn(x-1) else false

One can certainly use the keyword and to concatenate definitions of non-recursive functions, but doing so is probably just a curiosity (instead of a meaningful practice).

Even at this point, I have not presented all of the possible ways to define functions in ATS. For instance, one can also define stack-allocated closure-functions in ATS, which may be either recursive or non-recursive. I plan to introduce such functions elsewhere in this tutorial.

Often, the interface (that is, type) for a function is declared at one place and its definition (or implementation) is given at another place. For instance, one may first introduce the following declaration: 

extern fun fact (x: int): int

Later, one can implement fact according to the above declaration: 

implement
fact (x) =
  if x > 0 then x * fact(x-1) else 1
// end of [fact]

When implement is used to initiate the definition of a function, any previously declared symbols (including the one that is being defined) can appear in the definition. If it is desirable, one may replace implement with implmnt.

Please find on-line the entirety of the code used in this chapter.

PrevHomeNext
Dot-Symbol OverloadingUpDatatypes