MIFFS Is Fun For Sums

by rich

Using Functions

The power of functional languages lies in their treatment of functions. MIFFS should work as a basic calculator without using any of that, but what would be the fun of that?

The "fun" Declaration

To declare a new function that is accessible at the top level (i.e. in future input) you write fun, followed by an argument list, then = and finally an expression that may contain the arguments you listed or the name of the function (recursion). MIFFS replies with the new val that it recognises, meaning that it worked. (Although you may not have a valid function as MIFFS has no parse-time type checking!)

fun times(a,b) = a*b
val times = fn : α -> α
times(6,7)
val ans = 42 : int

Functions are Values

Every function is an object that can be the result of an expression, can be stored in a val label etc. This leads to the idea of "Currying" - because you can return a function from a function call, you only need a single argument, and can re-use functions more easily.

fun ncr n r = if r=0 orelse r=n then 1 
                else ncr(n-1)(r-1) 
                   + ncr(n-1)(r)
val ncr = fn : α -> α
val choosethree = ncr 3
val choosethree = fn : α => α
(choosethree 0, choosethree 1, 
 choosethree 2, choosethree 3)
val ans = (1, 3, 3, 1) : int * int * int * int

Anonymous Functions - The "fn" Constructor

As functions are values, we need some way of having an expression that evaluates to give a function. The fn [args] => [expr] construction does just that.

fn x => x+1
ans = fn : α -> α
(fn x => x+1) 4
ans = 5 : int

Local Declarations - "let"

Sometimes you need to re-use a value or access elements of a tuple individually. Write let then a list of definitions (val or fun), then in followed by an expression that may use the values or functions declared, terminated by end. Look at the function next below: this function needs to use the second element of the tuple that is its argument.

fun countfrom n = 
     (n, fn () => (countfrom (n+1)))
val countfrom = fn : α -> α
fun next x = let val (a,b) = x in b() end
val next = fn : α -> α
countfrom 1
val ans = (1, fn) : int * (() -> α)
next(ans)
val ans = (2, fn) : int * (() -> α)
next(ans)
val ans = (3, fn) : int * (() -> α)

To finish this section a bigger example: Erathostenes' sieve

fun sieve p (n, f) = if (n%p)=0 
     then sieve p (f()) 
     else (n, fn()=>sieve p (f()))
val sieve = fn : α -> α
sieve 2 (countfrom 1)
val ans = (1, fn) : int * (α -> α)
next(ans)
val ans = (3, fn) : int * (α -> α)
next(ans)
val ans = (5, fn) : int * (α -> α)
val primes = let 
   fun pr(p,f) = 
     (p,fn()=>pr(sieve p (f()))) 
 in 
   pr (countfrom 2) 
 end
val primes = (2, fn) 
     : int * (α -> α)
fun get 0 _ = [] 
 |  get n (m, f) = m :: (get (n-1) (f()))
val get = fn : a -> a
get 25 primes
val ans = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
   31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
   73, 79, 83, 89, 97] : int list

I hope this has piqued your interest. I shall be adding more functionality to the language as soon as I get the time. (Although, interestingly, the lack of a type-checker helped with the last example as the type of f in sieve is ambiguous because it refers to itself - to get this to work in ML you need to set up a recursive datatype.)