Finesses - Spicery/Nutmeg GitHub Wiki

Overview

Finesses are Nutmeg's mechanism for writing function-like procedures that use side-effects safely. From the outside they look like functions but on the inside the programmer can use side-effecting updates freely, although I/O is not allowed. (A future expansion of Nutmeg will allow a limited form of I/O that is localised.)

A finesse is a procedure that obeys the following rules:

• A finesse is a procedure with const inputs and outputs.
• Internally it may use 'var' variables, side-effecting functions and functions that allocate mutable store.
• However any external constants that it references must be bound to const values. For clarity:
  • This forbids procedures that directly or indirectly reference pre-existing mutable store (aka impervious).
  • This allows procedures that allocate or mutate store.
• External constants may not directly or indirectly reference functions that perform I/O.

To understand why this definition makes a finesse safe, it is important to bear in mind the following key facts:

• In Nutmeg, var-variables can only be used in the exact scope they are declared in and not in any inner scope. Nor can they be used at top-level. This implies that a Nutmeg function cannot reference var-variables.
• Also, const in Nutmeg always means deep, recursive, full immutability (as opposed to shallow, single-level immutability). Perma-locked values may count as const for these purposes if they only reference const values.
• Therefore a procedure can only reference non-assignable variables (val) and a finesse can only reference constants (const) whose values are fully immutable.
• The only mutable store a finesse can access is therefore allocated during the invocation of the finesse.
• And because the return values are const, that store cannot escape as a return value.
• Nor can store escape by being stashed in externally modifiable store, as referencing pre-existing mutable store makes a procedure non-const.

The upshot of this is that all mutable store allocated during the invocation of a finesse is local to the invocation of that finesse. It also means that a finesse is automatically exception-safe. The latter is a very important property of finesses.

Simple Example showing use of 'var'

For example, we can write the classic iterative version of factorial as follows.

finesse factorial( n ) =>>
    var sofar = 1
    for n in [ 2 ... n ]:
        sofar <- sofar * n
    endfor
    return( sofar )
end

Example showing use of mutable store

finesse bubblesort( list ) =>>
    vector := MutableList( **list )    ### **x means all the values of x, syntax TBD.
    N := vector.length
  
    # Traverse through all array elements 
    for i in [ 0 ..< N-1 ] do
        ### Here: the elements from [ N-i ..< N ] are sorted.
        for j in [ 0 ..< N-1-i ] do
            ### Here: the biggest element in the range [ 0 ... j ] is at j.
            if vector[ j ] > vector[ j+1 ] then
                vector.swap( j, j+1 )
            endif
            ### Here: the biggest element in the range [ 0 ... j+1 ] is at j + 1.
        endfor
        ### Here: the elements from [ N-(i+1) ..< N ] are sorted.
    endfor

    return( snapshot( vector ) )
end

Quicksort As a Finesse

finesse quicksort( const list ):
    val A := Mutable( list )
    quicksortInPlace( A, 0, A.length )
    return( snapshot( A ) )
end    

def quicksortInPlace( A, lo, hi ):
    if lo < hi:
        p := partition( A, lo, hi )
        quicksort( A, lo, p - 1 )
        quicksort( A, p + 1, hi )
    end
end

def partition( A, lo, hi ):
    val pivot := A[hi]
    var i := lo
    for j := lo .. hi do
        if A[j] < pivot:
            A.swap( i, j )
            i <- i + 1
        end
    end
    A.swap( i, hi )
    return( i )
end