Example: Constructing a Statically Allocated List

In embedded programming, static memory allocation is often preferred due to dynamic memory allocation being less predictable. I present as follows an example in which a list is constructed with statically allocated memory. This example also strongly attests to ATS and C being intimately related.

In order to statically allocate memory for list-nodes, we need to first form a type for list-nodes so that we can inform the C compiler how much memory is needed for each list-node. In the following code, the type list_node in ATS is for boxed list-nodes, and this type is exported to C under the same name:

// vtypedef list_node = list_cons_pstruct(int,ptr) // [list_node] for boxed nodes // extern vtypedef "list_node" = list_node // exporting [list_node] to C //

Exporting list_node to C also introduces (implicitly) a typedef list_node_ in C for unboxed list-nodes. So the following type list_node_ in ATS is precisely what we want (for unboxed list-nodes):

// typedef list_node_ = $extype"list_node_" // [list_node_] for unboxed nodes //

The following code statically allocates an array of list-nodes and then initialize these nodes, turning the array into a list:

local #define N 10 (* ** static allocation *) var nodes = @[list_node_][N]() fun loop ( p: ptr, i: int ) : void = let in // if i < N then let val res = $UN.castvwtp0{list_node}(p) val+list_cons (x, xs) = res val ( ) = x := i*i val p = ptr_succ<list_node_> (p) val i = i + 1 val () = ( if i < N then xs := p else xs := the_null_ptr ) : void // end of [val] val _(*ptr*) = $UN.castvwtp0{ptr}((view@x, view@xs | res)) in loop (p, i) end else ((*void*)) // end of [if] // end // end of [loop] in (* in of [local] *) val () = loop (addr@nodes, 0) val xs_static = $UN.castvwtp0{list(int,N)}((view@nodes|addr@nodes)) val () = println! ("xs_static = ", xs_static) // 0, 1, 4, 9, 16, ... end // end of [local]

The implementation of loop makes extensive use of unsafe C-style programming in ATS. For someone familiar with C, it should be straightforward to visualize the C code that corresponds to this implementation directly.

Please find the entire code for this example on-line.