Victor Allombert
email: victor.allombert@univ-orleans.fr

Mathias Bourgoin
email: mathias.bourgoin@univ-orleans.fr

Frédéric Loulergue
email: frederic.loulergue@nau.edu

Parallel Programming with OCaml: A Tutorial

Keywords: Parallel programming, functional programming, bulk synchronous parallelism, Multi-BSP, GPGPU f 1.0 2.0

OCaml is a multi-paradigm (functional, imperative, object-oriented) high level sequential language. Types are statically inferred by the compiler and the type system is expressive and strong. These features make OCaml a very productive language for developing efficient and safe programs. In this tutorial we present three frameworks for using OCaml to program scalable parallel architectures: BSML, Multi-ML and Spoc.

As parallel architectures are now the norm, it is necessary to consider programming languages and libraries that offer a trade-off between execution efficiency and programming productivity. While languages and libraries for high performance computing, such as MPI [START_REF] Snir | MPI the Complete Reference[END_REF], favor efficiency over productivity, a lot of application domains require that mainstream programmers develop parallel applications without huge knowledge about parallel programming.

Big Data is an area where productivity is also considered as important. MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] is a well-known programming model where it is only possible to express a parallel algorithm in a very structured and specific way. The creators of MapReduce indicate functional programming as an inspiration for their framework. Moreover, there is a recent trend to include functional features in mainstream languages, such as Java or C++. This tutorial is an introduction to parallel programming using a modern functional programming language: OCaml, a statically and strongly typed language, with a type inference system. This allows detecting errors very early in the development of applications. OCaml offers high-level features yet it is efficient. While the style of an OCaml application is mainly functional, OCaml is a multi paradigm language: it provides imperative and object-oriented features that can be used for efficiency or modularity reasons.

The three presented frameworks leverage OCaml for scalable parallel programming of homogeneous clusters (Section II), hierarchical architectures (Section III), and GPUs (Section IV). We use, as a running example, a parallel map and reduce implementations on distributed lists or distributed arrays. We begin with a short presentation of OCaml in Section I and discuss further reading in Section V.

I. AN OVERVIEW OF OCAML

In this section we describe the OCaml language and the features of the OCaml library that are necessary for a good understanding of this tutorial.

A. What is OCaml?

OCaml [START_REF] Leroy | The OCaml System release 4.00.0[END_REF] is a functional programming language [START_REF] Cousineau | The Functional Approach to Programming[END_REF] from the ML (Meta Language) family. It is the main implementation of Caml, a general-purposes language developed at Inria.

OCaml relies on a powerful static type system allowing type inference, as well as parametric and generalized algebraic data types polymorphism. It also proposes a system of modules and an object oriented approach. The code generated by the compiler is thus safe, thanks to the type checker.

The OCaml language offers a bytecode compiler to allow code portability on various architectures. The quality of the native compilation allows performances close to the highest standards of modern compilers. OCaml also provides automatic memory management thanks to its embedded garbage collector. A toplevel that permits interactive use of OCaml through and interactive loop is also available.

OCaml is supported by a widespread community and has a rich set of libraries and development tools [START_REF] Chailloux | Développement d'applications avec Objective Caml[END_REF], [START_REF] Minsky | OCaml for the masses[END_REF]

B. Introduction to the OCaml Syntax

As OCaml provides type inference, it is not necessary to specify the type of a variable. Variables are defined using let-bindings. For example, let x = 1 declares that x is a variable of type int with the value of 1. Although unnecessary, it is possible to annotate an expression with a type, so let x : int = 1 is valid too. We use type annotations in the next sections as types provide valuable information to the reader.

To declare a function in OCaml it is also possible to use a let-binding as following: let prod x y = x * . y. Here, we define the function prod which takes two arguments (x and y) and returns the product of them. Notice the usage of the * . operator which stands for floating point addition. The usage of this operators forces the types of x and y to be float. The prod function is typed prod:float → float → float as it takes as argument two floats and returns a float. The application of the function prod can be written as follows:

When there is no type constraints on values, the type system generates forall types. For example, let f x = x is a function taking an argument x and returning the exact same value. Here, the f can be applied on any value of x. Thus, it is typed f : α → α where α stands for any types.

Because of its functional capabilities, high-order functions are common in OCaml programs. For example, we can write a square function as following: let square x = prod x x. Anonymous function are also often used and are identified by the fun keyword. Thus, the following code allows the definition of the square function using anonymous function instead of using the prod function:

let square x = (fun x y → x * . y) x x.
Lists are one of the most common data structure used in the context of functional programming. In Ocaml, a list is implemented as an immutable singly linked list. A list of integers in OCaml can be defined as following: let l1 = [1;2;3]. The type of the l1 is int list. The brackets delimits the list and elements are separated with the semicolon. The empty list is written [] and the concatenation of two lists is written l1 @ [4;5;6]. The infix operator :: adds an elements at the beginning of a list. Therefore l1 can also be written 1::2::3::[]. Actually [] and :: are the two list constructors, i.e. any list value can be described in terms of this constant and this operation.

The definition of recursive functions using the let-binding must be annotated by the rec keyword. For example, we can write a (non tail-)recursive function that builds a list containing the values from n1 to n2 as follows:

let rec from_to n1 n2 = if n1>n2 then [] else n1::(from_to (n1+1) n2)
This function returns [] if the lower bound is greater than the upper bound. Otherwise, it returns the value of n1 concatenated with the recursive call of from_to on n1+1 and n2 using the operator ::. Pattern matching is a powerfully control structure used to match values or expressions (patterns) to computations. Clauses are matched, in order, and the first expression corresponding to the matching clause is evaluated. To describe how pattern matching works, we implement a (non tail-recursive) map operator in the following example. We recall that map on lists applies a function on each elements of a given list.

let rec map f l = match l with | [] → [] | hd::tl → (f hd)::(map f tl)
As expected, map takes as argument a function f and a list of elements l. The pattern matching is expressed using the match with keywords. Here, we match the value of l with, respectively:

• [] is the empty list. We return an empty list if the input list is empty. Indeed, if the previous matching fails, it means that the list is not composed of at least two elements, thus it is an empty list.

• hd::tl a list composed of the head element hd and the tail tl (the rest of the list). In this case, we return the result of the application of f on h concatenated with the result of the recursive call on the tail.

It is also possible to define arrays in OCaml as follows: let a = [|1;2;3|]. Thus, a is typed int array. Unlike lists, arrays are mutable data structures. Updating the cell at index i of an array a with a value v is written a.(i)←v.

In OCaml, it is simple to define its own types using records. A record is a data structure holding multiple values. For example, the definition of a point of a Cartesian coordinate system can be written: type point = { name : string; x : float; y : float; } Here, the record point is made of three fields: the name of the point and the x and y coordinates. An instance of a point is written: let a = {name="A";x=3.0;y=5.0}. Records can have mutable fields that can be set using the ← operator. For example, annotating the field x as follows mutable x : float allows one to write a.x←4.0.

C. Some Features of OCaml Libraries

To manipulate common data structures such as lists or arrays it is possible to use the List and Array modules from the standard library.

Regarding lists, the map function is very useful to apply a function on each element of a list. List.map is typed map : (α→β)→α list→β list. The code List.map f l applies function f on each elements of the list l. Thus, List.map (fun x → x * x) [0;1;2;3] produces list [0;1;4;9].

Folding on lists is a common operation that can be done using Many other functions are available to get the size (List.length), access the n th element (List.nth), reverse (List.rev), and so on.

A similar set of functions is available for arrays.

II. BULK SYNCHRONOUS PARALLELISM WITH OCAML

Bulk Synchronous Parallel ML or BSML [START_REF] Loulergue | Bulk Synchronous Parallel ML: Modular Implementation and Performance Prediction[END_REF] is based on the Bulk Synchronous Parallel model [START_REF] Valiant | A bridging model for parallel computation[END_REF], [START_REF] Mccoll | Scalability, portability and predictability: The BSP approach to parallel programming[END_REF], [START_REF] Bisseling | Parallel Scientific Computation[END_REF] or BSP. The aim of this model is to be a bridge between the world of parallel architectures and the world of parallel applications.

A. The Bulk Synchronous Parallel Model

The BSP model assumes a BSP architecture: a parallel machine consisting of a set of homogeneous processor-memory pairs, a network delivering point-to-point communications, and a global synchronization unit. This BSP architecture can be mapped on any general purpose parallel architecture. For example, a cluster can be seen as a BSP machine even if in this case the global synchronization unit is usually implemented using software rather than hardware. In a shared memory machine, each core can work on a dedicated region of the shared memory and can communicate with other cores using another region of the shared memory.

The execution of a BSP program proceeds as a sequence of super-steps. A super-step starts with a pure computation phase where each processor computes using the data it holds in its private memory, and requests data from other processors. A communication phase then occurs: data is exchanged between processors. Finally the super-step ends with a synchronization barrier. The remote data requested by processors is only guaranteed to be delivered after the synchronization barrier ends. The computation can then continue with the next superstep.

This constrained form of parallel execution made the design of a simple BSP performance model possible. A BSP architecture is characterized by four parameters: p is the number of processor-memory pairs (P denotes the set of processor identifiers from 0 to p-1), r is a processors' computing power usually expressed in floating point operations per second, L is the time required to perform a global synchronization barrier, and g (expressed in seconds per word) is the time required for performing a communication phase where each processor sends or receives at most 1 word of data. When the communication phase consists of the exchange of at most h words of data for each processor, the execution requires h × g. Such a communication phase is said to realize a communication pattern named a h-relation. In the presentation of BSP algorithms, L and g are usually normalized with respect to r and are therefore respectively expressed in flops and flops per word.

If w i is the time (or flops) required by processor i to execute the computation phase of the super-step, and the communication pattern of the super-step is a h-relation then the overall cost of the super-step is:

max i∈P w i + h × g + L
The cost of the execution of a BSP program is the sum of the costs of its super-steps.

B. BSML Primitives

Currently BSML is implemented as a library for the OCaml language rather than a new language. The only difference is that a full language would provide a dedicated type system [START_REF] Gava | A Static Analysis for Bulk Synchronous Parallel ML to Avoid Parallel Nesting[END_REF].

BSML implementation provides: an interactive loop to ease the development of BSML programs, a sequential implemen-tation (used in the interactive loop), and a parallel implementation on top of MPI [START_REF] Loulergue | Bulk Synchronous Parallel ML: Modular Implementation and Performance Prediction[END_REF]. There also exists an implementation as an interactive web site 1 .

BSML provides four constants corresponding to the four BSP parameters: bsp_p, bsp_r, bsp_g and bsp_l. This allows one to write performance portable programs: depending on the BSP parameters, it is possible to choose the best algorithm for the specific underlying architecture running the program.

BSML relies on a dedicated data structure, called parallel vector. This is a polymorphic data structure and its type is α par. The size of a parallel vector is always bsp_p, and each processor holds a value of type α. There is a limitation to polymorphism: α cannot be instantiate to a type that contains a parallel vector type. The type system [START_REF] Gava | A Static Analysis for Bulk Synchronous Parallel ML to Avoid Parallel Nesting[END_REF] can statically reject such forbidden nesting. However, the current implementation does not provide this type system, it is therefore the responsibility of the programmer to avoid such nesting.

BSML has a pure functional semantics [START_REF] Loulergue | A Calculus of Functional BSP Programs[END_REF]. Therefore the sequential implementation and the parallel implementation give the same results, provided no imperative features of OCaml are used. If imperative features are incorrectly used, the results may differ. The type system can also statically detect such incorrect programs. One important advantage of such a semantics, is that it is possible to use a proof assistant to verify the correctness of BSML programs.

BSML is more concise than the standard BSPlib [START_REF] Hill | BSPlib: The BSP Programming Library[END_REF]. In addition to the four constants, it only provides four parallel functions to manipulate parallel vectors.

In the remainder of this section, ⟨v 0 , . . . , v p-1 ⟩ denotes a parallel vector such that value v i is in the local memory of processor i. In BSML, parallel vectors are manipulated globally: there is no index notation for accessing a specific element in a parallel vector.

The primitive mkpar is devoted to create parallel vectors. Its type is (int→α)→α par. From a function f it creates a parallel vector: each processor applies this function to its identifier to obtain a value. Therefore mkpar f = ⟨f 0, . . . , f (p -1)⟩.

A parallel vector can contain any type of element but a parallel vector. In particular it can contain functions. However, a parallel vector of functions is not a function. The primitive apply is used to apply a parallel vector of functions to a parallel vector of values. Its type is (α→β)par→α par→β par. We have apply ⟨f 0 , . . . , f p-1 ⟩ ⟨v 0 , . . . , v p-1 ⟩ = ⟨f 0 v 0 , . . . , f p-1 v p-1 ⟩. Both mkpar and apply are executed during the local computation phase of a BSP super-step.

An almost inverse of mkpar is proj. From a parallel vector it creates a function such that if it is applied to a processor identifier it will return the value held by this processor. proj has type α par→(int→α). proj is not completely an inverse of mkpar because even if a function f given as argument to mkpar is defined for integers that are not valid processor identifiers, proj(mkpar f) will only be defined for valid processor identifiers. proj requires a full super-step for its execution: each processor sends the value it holds to all the other processors, and a synchronization barrier is called.

Finally put can realize any h-relation of a communication phase. Its type is put:(int→α)par→(int→α)par. Therefore its input and output are parallel vectors of functions. In the input, each function in the parallel vector encodes the messages to be sent to other processors. For example, a function f i at processor i encodes the messages to be sent by i to other processor. More precisely the message to be sent to processor j is f i j. In the output, each function encodes the messages received by the processor that holds the function. For example, at processor j, function g j is such that g j i is the message received by processor j from processor i. As described above, put seems to perform a total exchange. It is however not the case. Some values are considered to represent the empty message. This is for example the case for the empty list [] and the None value of the option type. A call to put needs a full super-step for its execution.

C. Map and Reduce with BSML

In this section, we consider that a distributed list is implemented as a parallel vector of lists. Intuitively, the user of the library we implement here can think of this data structure as a sequential list obtained by the concatenation of the lists held locally by p processors.

Implementing a parallel map is then very easy:

let map (f:α→β) (dl:(α list)par): (β list)par= apply (replicate (List.map f)) dl

First we replicate function f, meaning each processor will contain a copy of f, then we use apply to apply f to the local list on each processor. Replication can be defined as:

let replicate (x:α) : α par = mkpar(fun pid→x)
This is very common to apply a replicated sequential function, and we define a function to do that:

let parfun (f:α→β)(v: α par) : β par = apply(replicate f) v
Parallel reduction can be implemented in many ways. We present here two different implementations both using only one super-step of execution. reduce takes three arguments: a binary operation op, a neutral e for this binary operation, and a distribution list dl, and it reduces the distributed list using this binary operation. using to_list this parallel vector is converted into a sequential list that is finally reduced. to_list can be implemented using proj: let to_list (dl: α par) : α list = let f = proj dl in List.map f (from_to 0 (bsp_p-1))

If we prefer to obtain a parallel vector that contains the reduction result everywhere, reduce can be implemented using put as shown in Figure 1.

An alternative syntax avoids the use of mkpar and apply. It is based on this defined as mkpar(fun pid→pid), and a more compact syntax for manipulating parallel vectors [START_REF] Bousdira | Functional Parallel Programming with Revised Bulk Synchronous Parallel ML[END_REF].

Instead of writing replicate x it is possible to write ≪ x ≫. If a value v has type α par then inside ≪ and ≫ is is possible to use the notation $v$ that has type α but has a different value on each processor: the value held by this processor in parallel vector v. For example the following expression: ≪(fun x → x+1) $this$≫ evaluates to vector ⟨1, . . . , p⟩.

The example of Figure 1 can be rewritten using the alternative syntax as shown in Figure 2.

III. HIERARCHICAL PARALLELISM WITH OCAML

Multi-ML [START_REF] Allombert | Functional Abstraction for Programming Multi-Level Architectures: Formalisation and Implementation[END_REF], [START_REF] Allombert | Multi-ML: Programming Multi-BSP Algorithms in ML[END_REF] is a parallel programming language based on the Multi-BSP model [START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF]. It aims to bridge hierarchical architectures with several levels of distinct memories to parallel programming abstractions.

A. The Multi-BSP Model

Multi-BSP [START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF] is a structured parallel programming model which extends the BSP model [START_REF] Valiant | A bridging model for parallel computation[END_REF]. It takes into account hierarchical architectures with an arbitrary number of levels. In accordance to the BSP model, it reflects the physical characteristics of the architecture. The structure and abstraction brought by Multi-BSP allows having portable programs with scalable performance predictions, without dealing with lowlevel details of the architectures. Note that the definition of the Multi-BSP model handles balanced and homogeneous architecture only.

Multi-BSP brings a tree-based view of nested components where the lowest stages (leaves) are processors and every other stage (nodes) contains memory. The architecture depth is denoted by d and a Multi-BSP instance is defined by 4d parameters : (p i , g i , L i , m i ). Where p i is the number of subcomponents inside the i-1 stage; g i is the bandwidth between stages i and i -1; L i is the synchronisation cost of all subcomponents of a component of i-1 stage; m i is the amount of memory available at stage i for each component of this stage.

Every component of the architecture can execute independent codes. However, they have to synchronise in favour of data exchange. Thus, the Multi-BSP model does not allow subgroup synchronisation of any group of processors. The execution scheme of Multi-BSP algorithms is similar to the BSP one. Here, supersteps are hierarchically organised in order to manage sub-synchronisations. At a stage i, a superstep is composed by the following steps: the sub-components of stage i -1 execute some code independently (until they reach a barrier); there are exchanges of information with the m i memory; synchronisation of the sub-components (stage i -1).

Thanks to the structure of Multi-BSP and a dedicated cost model, performance prediction is also possible. Considering the communication cost C i j of a superstep j at stage i as follows:

C i j =h j ×g i +L i where h j is the maximum size of the exchanged messages at superstep (as it is in the BSP cost model). We can express the cost T of a Multi-BSP algorithms as follows:

T = d-1 i=0 ( Ni-1 j=0 w i j + C i j )
where d is the depth of the Multi-BSP architecture, N i is the number of supersteps at stage i, w i j is the maximum computational cost of the superstep j within stage i.

B. The Multi-ML Language

Multi-ML [START_REF] Allombert | Functional Abstraction for Programming Multi-Level Architectures: Formalisation and Implementation[END_REF], [START_REF] Allombert | Multi-ML: Programming Multi-BSP Algorithms in ML[END_REF] is based on the idea of executing BSML-like codes on every stage of a Multi-BSP architecture. This approach eases incremental development from BSML codes to Multi-ML ones. As expected, the synchronous communication primitives of BSML are also available to communicate values from/to parallel vectors. Multi-ML follows the Multi-BSP approach where the hierarchical architecture is composed by nodes and leaves. On nodes, it is possible to build parallel vectors, like in BSML. A parallel vector aims to manage values that are stored on the sub-nodes: at stage i, the code let v=≪ e ≫ evaluates the expression e on all i -1 stages.

Multi-ML also introduces the concept of multi-function to recursively go through a Multi-BSP architecture. A multifunction is a particular recursive function, defined by the keyword let multi, which is composed by two codes: the node and the leaf codes. The recursion is initiated by calling the multi-function (recursively) inside the scope of a parallel vector, that is to say, on the sub-nodes. The evaluation of a multi-function starts on the root node and is propagated down to the leaves. Then, the recursion goes back to the root node. The execution of a multi-function can be seen as a divide and conquer pattern. Another parallel data structure called tree is available in Multi-ML. A tree denotes a value which is distributed over all components of the Multi-BSP architecture. It is possible, for each component, to access its own value using at t, where t is a tree. The keyword let multi tree is used to define a multi-tree-function allowing tree construction. A multi-tree-function behaves similarly to a multi-function, but the keyword finally must be used to specify the values used to build the tree. Thus, at each node, we specify the local root and the branches used to build the sub-tree of the current stage; and so on, toward the root node.

C. Map and Reduce with Multi-ML

As the Multi-ML language uses a hierarchical tree based recursion to execute code, the map and reduce phases are almost embedded in the syntax of the language. Indeed, the map phase consists in mapping a function to the leaves (the map phase); and then, we combine the results to the root node (the reduce phase).

Similarly to BSML, we consider that a distributed list is implemented as a tree where only the leaves contain values (and nodes contain empty lists). The m_map function (standing for multi-map) can be written as following: First, the map multi-function is enclosed into the m_map function in order to define the function f globally and avoid its communications through each recursive call. As expected, the let multi tree keyword is used to declare map as its executions results in a tree. Then, we define the node code by the recursive call of map on its sub-nodes. The result of the recursion is stored in rc and will contains the sub-trees (or branches) generated on the sub-nodes. Thus, the node sections ends by constructing a new sub-tree with lower branches and an empty list. Finally, the leaf code consists of the sequential mapping of f on the values contained on leaves, accessed using at on tdl.

During the reduce phase, we must take into account the potential different number of children of a node when converting a parallel vector to a list (to_list function). To do so, we use the nb_children primitive which computes the number of children when executed on a node. The function to_list is thus defined:

let to_list vec = let p = proj vec in List.map p (my_children())
The reduce phase can be written easily: Using the reduce operator op and a neutral element e, the node code of the reduce multi-function consists in calling reduce recursively. The resulting parallel vector is then converted into a list using to_list. The resulting value of a node is thus the local reduction of the sub-reductions. The leaf code is the local reduction of the values distributed through the tdl tree. As reduce is a multi-function, it returns a sequential value (typed β) which is then available to all the components of the architecture.

It is also possible to write a single multi-function combining both the map and reduce phase. Such a multi-function will benefit in terms of line of code and efficiency, as the recursion through the components is done once. The m_map_reduce function can be written as follows: Intuitively, the node code combines the recursion call of map_reduce and the local reduction. The leaf performs both the mapping phase and the local reduction.

IV. GPGPU PROGRAMMING WITH OCAML A. GPGPU Programming

General purpose programming with graphics processing unit (GPGPU) is a common way to achieve high performance. It consists in the use of highly parallel GPU architectures as co-processors to handle intensive computations. GPGPU programming demands to write specific subprograms (called kernels) to be actually executed on the GPUs. As GPUs are co-processors, kernels are handled via the CPU host. The CPU is also responsible for the memory management (Direct Memory Access (DMA) copy between the host memory and the GPU memory). GPUs are parallel architectures (several hundreds of "cores") and thus kernels are written with a specific programming style.

B. The SPOC Library and the Sarek Domain Specific Language SPOC (Stream Processing with OCaml) [START_REF] Bourgoin | Spoc: Gpgpu programming through stream processing with ocaml[END_REF], [START_REF]Efficient abstractions for GPGPU programming[END_REF] is a highlevel library for GPGPU programming with OCaml. SPOC is a library based on programming via the OpenCL and CUDA frameworks. It offers several abstractions over memory transfers as well as device management. SPOC only focuses on the host program. It can interoperate with native GPGPU kernels (using the OpenCL and CUDA C subsets) as well as with kernels described with the Sarek DSL. To provide portability, SPOC unifies both CUDA and OpenCL APIs. SPOC automatically detects, at run-time, all devices compatible with it. As SPOC exposes a common API, it can be used to indifferently and conjointly handle multiple co-processors (from any framework). This eases the expression of complex programs dedicated to very heterogeneous architectures. SPOC introduces a specific data set to OCaml that is called vector. Vectors keep information about their current location in the system on host or co-processor memory. Thus, SPOC can automatically trigger transfers when needed. In particular, SPOC checks that every vector used by a GPGPU kernel is present in the co-processor memory (and triggers transfers if required) before launching the computation. Similarly, when the host reads or writes in a vector, SPOC checks its location and transfers it if needed.

SPOC can be used with native kernels as well as with kernels described in the Sarek DSL. In this section, we will only focus on Sarek to program kernels. Sarek is built into OCaml. As such, it provides some consistency over the host language. It is an expression oriented language with an MLlike imperative core. Sarek is based on the C subsets of CUDA and OpenCL but offers type inference, with static type checking as well as an OCaml-like syntax.

Using SPOC and Sarek, the common example of the vector addition can be written as following: The first function, vec_add, is the GPGPU kernel. As Sarek is built as an OCaml syntax extension, the kernel is written with Sarek directly into the OCaml code. As with CUDA or OpenCL, a kernel is an elementary computation that will be instantiated into GPGPU-threads. These threads will then be mapped over the numerous hardware computation units of the GPU to execute the computation in parallel. Here, our kernel first opens the Std module that gives access to GPGPU-specific global functions, in particular those necessary to identify each thread running the kernel. Here we use thread_idx_x + block_dim_x * block_idx_x to compute the global identifier of the each thread running an instance of our kernel. Then our kernel naively computes an elementary addition. The mapping of this kernel on numerous computation units will provide the overall vector addition.

Following the kernel comes the host part of the program, that is run by the CPU and will handle communications and computations scheduling with the GPU. It starts by initializing the SPOC system with Devices.init(). This function scans the system for co-processors compatible with either CUDA or OpenCL and returns an array of devices that can be used in the rest of the program. We then declare some variables. In particular, v1, v2 and v3 that are SPOC vectors, that can be shared between host and GPU automatically. The block and grid variables are used to describe a 3D layout of threads corresponding to a virtual GPU appropriately sized for our computation. With GPGPU frameworks, kernels are executed in a 3D grid of 3D blocks of threads. Threads will be mapped to the actual computation units of the GPU. Threads inside a block can be synchronized and can communicate through a shared memory. There is no global synchronization mechanism (between threads of different blocks). Here we describe a linear layout with one thread for each element in our vectors. Then, we have the main function, it first fills the vectors with random values. Then we use the gen function from the Kirc module to compile our kernel to actual CUDA or OpenCL code. Here we use the default compilation scheme that generates both versions of the kernel. Then we run the kernel with the correct parameters on the first device detected during initialization (dev.(0)). Finally the program prints the content of the result vector that was computed on the GPU. As described earlier, the host program does not need to explicitly handle memory transfers between the host and the GPU as they are automatically managed by the SPOC library. Besides, remember that this simple example is very portable as compiled program using SPOC and Sarek are usable with CUDA or OpenCL devices (or a combination of both) specifying their behaviour at run-time.

C. Map and Reduce with SPOC and Sarek

To make GPGPU programming simpler, both CUDA and OpenCL frameworks impose specific constraints. SPOC and Sarek inherited some of them which makes writing general Map and Reduce functions trickier than with BSML and Multi-ML. In particular, kernel functions are sequential (it is their mapping on numerous computations units that produces the parallelism). Besides, higher order functions are not available in the Sarek DSL, which makes it impossible to write parallel map/reduce-like functions with Sarek only. On the other hand, OCaml (and the SPOC library) and Sarek look very similar but, in practice, Sarek code is very different from OCaml functions. Sarek kernels are pre-compiled into a data-structure containing an internal representation (IR) of the kernel that is directly embedded into the OCaml host code at compiletime. Then the Kirc.gen function we've seen earlier will translate this IR into actual CUDA/OpenCL code. This make difficult (but not impossible) to write a generalized map/reduce operation from OCaml with SPOC that manipulated Sarek kernels. Last but not least, Sarek kernels cannot currently be polymorphic. Keeping all these constraints in mind, we will, in the rest of this section, look at how to write map/reduce-like computations with Sarek, SPOC and OCaml.

1) Map: The main objective here is to use a Sarek kernel producing an output vector of type β from an input vector of type α. A naive Sarek kernel would thus look like the following:

let map_f = kern a b → let open Std in let idx = thread_idx_x + block_dim_x * block_idx_x in if idx < Vector.length a then b.[<idx>] ← f a.[<idx>]
Here f is an external function or an inlined computation of type α → β.

From the host side, it is necessary to pre-create a vector for the output of the map computation before running the kernel. The code would then look like the following : Fig. 3. A tree based reduction using the addition operator.

Using this kind of program, the application of the f function (used in the Sarek kernel) to each elements of the input vector into the output vector will take place in parallel using a GPU. The version proposed here is naive as it does not take into account the arithmetic complexity of the f function which could be too small to dedicate one GPU thread to each element of the vector. In the same vein, it cannot be used directly with vectors larger than the maximum number of threads usable on an actual GPU.

2) Reduce: Map is an easy target for parallelism. Reduction is more complex. The common/simple way to handle reduction with GPUs is a tree based approach. A tree based GPU computation of a reduction using the addition operator on the vector would be similar to Figure . 3.

Here, each level of the tree corresponds to a parallel computation. Between each computation, a synchronization is needed. However, GPUs cannot do global synchronizations inside kernels. The only synchronization mechanism available synchronizes threads within a block. There is no similar mechanism between blocks. Blocks are limited in size (number of threads), besides actual hardware demands to use multiple blocks in order to increase parallelism. Thus, for large enough vectors, global synchronization (between blocks) will be needed. The simpler solution to provide "global synchronization" consists in decomposing the overall reduction into multiple kernels (one for each step of the reduction), using kernel launches as global synchronization points. We will not detail here the code for a GPGPU reduction, CUDA/OpenCL reductions have been widely discussed [START_REF] Harris | Optimizing CUDA[END_REF], [START_REF] Catanzaro | OpenCL Optimization Case Study: Simple Reductions[END_REF] and is similar with Sarek and OCaml.

3) High-level Map/Reduce with SPOC and Sarek: As we said earlier, Map and Reduce with SPOC and Sarek are difficult to generalize. In the end, the two solutions proposed here are very low-level and similar to those available with CUDA and OpenCL. However, without going into detail, Sarek offers a solution to improve the situation. Sarek kernels internal representation is embedded into the OCaml host code at compile-time. This IR is mostly an Abstract Data Tree (ADT) compose of OCaml values. This makes this tree parsable from the host code. For instance, the Kirc.gen function is an OCaml function parsing the IR ADT and generating CUDA/OpenCL native code. It is thus possible to design OCaml functions taking Sarek kernels as parameters and producing new computations. These computations (that we call transformations) can be used to provide map/reducelike operations. For instance, for map, it consists mainly in an OCaml function taking a kernel computing on scalars (corresponding to the function f in the map_f kernel) as a parameter. The function transforms it into a new kernel similar to map_f. It also generates the output vector and runs the kernel with the correct input/output before returning the computed output vector.

For instance, raising each element of a vector to the power of two could be written as follow : The f function is still constrained by the limitations of GPGPU frameworks (no polymorphism etc.). However, the map transformation is polymorphic and can transform any kernel of type α → β.

V. FURTHER READING a) BSML: While being more concise than BSPlib, BSML is however equally expressive [START_REF] Loulergue | A BSPlib-style API for Bulk Synchronous Parallel ML[END_REF]. In addition to the primitives presented in this paper, BSML has been extended by parallel compositions [START_REF]Parallel Superposition for Bulk Synchronous Parallel ML[END_REF], [START_REF]Parallel Juxtaposition for Bulk Synchronous Parallel ML[END_REF], [START_REF] Gava | Implementation of the parallel superposition in bulksynchronous parallel ML[END_REF], [START_REF] Garnier | CPS implementation of a BSP composition primitive with application to the implementation of algorithmic skeletons[END_REF], parallel exceptions handling [START_REF] Gesbert | Bulk Synchronous Parallel ML with Exceptions[END_REF], and IO. These features are not available in the public release yet.

The pure semantics of BSML makes the verification of BSML program possible using a proof assistant [START_REF] Tesson | A Verified Bulk Synchronous Parallel ML Heat Diffusion Simulation[END_REF]. This is the foundation of a framework for the Coq proof assistant to support the systematic development of correct parallel programs [START_REF] Gesbert | Systematic Development of Correct Bulk Synchronous Parallel Programs[END_REF], [START_REF] Loulergue | Formal Derivation and Extraction of a Parallel Program for the All Nearest Smaller Values Problem[END_REF], [START_REF] Emoto | A Verified Generate-Test-Aggregate Coq Library for Parallel Programs Extraction[END_REF], [START_REF] Loulergue | A verified accumulate algorithmic skeleton[END_REF], [START_REF] Loulergue | Calculating Parallel Programs in Coq using List Homomorphisms[END_REF].

BSML has been used for example to implement parallel data structures [START_REF] Gava | A modular implementation of data structures in bulksynchronous parallel ML[END_REF], algorithmic skeletons on distributed lists [START_REF] Loulergue | Implementing Algorithmic Skeletons with Bulk Synchronous Parallel ML[END_REF], and powerlists [START_REF] Loulergue | Implementing powerlists with Bulk Synchronous Parallel ML[END_REF].

b) Multi-ML: In the tradition of BSML, Multi-ML aims to propose formal properties. The semantics of the language is thus described in [START_REF] Allombert | A formal semantics of the Multi-ML language[END_REF] and a formalisation of the compilation scheme ensuring that the generated code follows the semantics is proposed in [START_REF] Allombert | An ML implementation of the MULTI-BSP model[END_REF]. As the language relies on a type system with locality annotations and effects, a formal definition the Multi-ML type system can be found in [START_REF] Allombert | Functional Abstraction for Programming Multi-Level Architectures: Formalisation and Implementation[END_REF]. c) SPOC: The SPOC library and the Sarek DSL have been first described in [START_REF] Bourgoin | Spoc: Gpgpu programming through stream processing with ocaml[END_REF] and [START_REF]Efficient abstractions for GPGPU programming[END_REF]. Several extensions have been developed on top of them. Parallel skeletons and compositions have been proposed in [START_REF] Bourgoin | Experiments with Spoc[END_REF], [START_REF] Bourgoin | GPGPU composition with OCaml[END_REF] to make the design of high performance GPGPU applications easier. High-level data structures that can automatically be transferred between host (CPU) and GPU memory have been introduced to Sarek in [START_REF] Bourgoin | High Level Data Structures for GPGPU Programming in a Statically Typed Language[END_REF]. A portable profiling solution has been developed as a Sarek extension in [START_REF] Bourgoin | Profiling High Level Heterogeneous Programs[END_REF]. They also have been used to develop a web-oriented version of SPOC described in [START_REF] Bourgoin | High-level accelerated array programming in the web browser[END_REF].

  List.fold_left : (α→β→α)→α→β list→α.Given a functionf, an element e and a list of n elements [x0;x1; ... ;xn], .. (f (f e x0) x1) ...) xn.To compute the sum of all the element of a list, we can write the following code:List.fold_left (fun x y → x + y) 0 [1;2;3;4;5].

Fig. 1 .Fig. 2 .

 12 Fig. 1. Parallel Reduction in BSML

  let m_map(f:α→β)(tdl:α list tree) = let multi tree map tdl = where node = let rc = ≪ map tdl ≫ in finally(rc,[]) where leaf = List.map f (at tdl) in map tdl

  let m_reduce(op:α→α→α)(e:α)(tdl:α list tree)= let multi reduce tdl = where node = let rc = ≪ reduce tdl ≫ in let sub_vals = to_list rc in List.fold_left op e sub_vals where leaf = List.fold_left op e (at tdl) in reduce tdl

  let m_map_reduce (op_map:α→β) (op_red:β→β→β) (e:β) (tdl:α list tree):β = let multi map_reduce tdl = where node = let rc = ≪ map_reduce tdl ≫ in let sub_vals = to_list rc in List.fold_left op_red e sub_vals where leaf = let res_map = List.map op_map (at tdl) in List.fold_left op_red e res_map in map_reduce tdl

open

  Spoc let vec_add = kern a b c n → let open Std in let idx = thread_idx_x + block_dim_x * block_idx_x in if idx < n then c.[<idx>] ← a.[<idx>] +. b.[<idx>] let dev = Devices.init () let n = 1_000_000 let v1 = Vector.create Vector.float64 n let v2 = Vector.create Vector.float64 n let v3 = Vector.create Vector.float64 n let block = {blockX = 1024; blockY = 1; blockZ = 1} let grid={gridX=(n+1024-1)/1024; gridY=1; gridZ=1} let () = random_fill v1; random_fill v2; Kirc.gen vec_add; Kirc.run vec_add (v1, v2, v3, n) (block,grid) dev.(0); for i = 0 to Vector.length v3 -1 do Printf.printf "res[%d] = %f; " i v3.[<i>] done;

  let f = kern a → a * a in ... let output = map f input dev.(0)

http://tesson.julien.free.fr/try-bsml


domain: math shs

text:
Irene M Duranczyk

Vilma Mesa
email: vmesa@umich.edu

Nidhi Kohli
email: nkohli@umn.edu

April Strom
email: april.strom@scottsdalecc.edu

Laura Watkins
email: laura.watkins@gccaz.edu

Measuring gains in knowledge within algebra instruction at community colleges: Assessing the efficacy of the Algebra Pre-Calculus Readiness

Keywords: Mathematics, postsecondary instruction, algebra, classroom-based research

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

The measurement of student learning for a federally funded project, EHR #831882, [START_REF] Watkins | Algebra instruction at community colleges: Exploration of its relationship with student success (EHR#831882)[END_REF] will be used to investigate the connection between instructional practices and student learning in algebra courses at six community colleges in three states of the United States. The poster focused on measurement issues faced in identifying students' learning gains in the pilot data.

Although we like to think that teaching causes learning, the truth is that such connection has not been established empirically [START_REF] Hiebert | The effects of classroom mathematics teaching on students' learning[END_REF]. As a first attempt to establish this connection, we investigate the extent to which there is a correlation between what occurs in the classroom and what students learn in a one semester course. Whereas there is some research documenting how individual and institutional characteristics (e.g., prior achievement, family support, financial aid, learning support and tutoring centers, and ratios of full-to part-time instructors) factor into failure rates and other performance measures [START_REF] Bradburn | Short-term enrollment in postsecondary education: Student background and institutional differences in reasons for early departure[END_REF][START_REF] Feldman | Factors associated with one-year retention in a community college[END_REF], there is little information about the fundamental work of teachers in the classroom, and the interaction that occur between instructors, students, and the mathematical content. The Quality of Mathematics Instruction (QMI), a video analysis tool used in P-12 settings (Learning Mathematics for Teaching Project, 2011), was adopted to measure faculty and student interaction at the community college. Research in K-12 and four-year colleges documents that the association between quality of instruction and student outcomes can be moderated by instructors' knowledge and attitudes towards innovative teaching practices, knowledge of algebra for teaching, and their beliefs about mathematics, its curriculum, and students' learning. The association is also moderated by students' attitudes, beliefs, and confidence about mathematics, their patterns of adaptive learning orientations, and the perceptions they have about their instructors' behaviors in the classroom and by the personal characteristics of instructors and students. The Algebra and Precalculus Concepts Readiness (APCR) test [START_REF] Madison | Conceptual precalculus: strengthening students' quantitative and covariational reasoning[END_REF] was used to measure student learning.

The first phase, presented here, is the pilot testing of the APCR instrument to measure learning gains. The algebra instruction captured for analysis focused on three key algebra topics: linear, rational, and exponential equations. The APCR tests these topics and was administered in the second week of the semester before the topics were introduced and then two weeks before the end of the semester after the three focal topics had been taught.

The analysis based on the APCR data from 6 community college faculty and 161 students in beginning, intermediate and college level algebra courses lead to questions about the suitability of the instrument for our work. Examining the descriptive statistics, item analysis, and reliability measures from classical test theory [START_REF] Thorndike | Measurement and evaluation in psychology and education[END_REF] revealed problematic point-biserial correlation and poor item discrimination. Ten item on the test fell well below acceptable levels (point-biserial correlations below 0.20).

Reliability measure gives information about the extent to which the scores produced by such measurement procedures are consistent and reproducible. The APCR had a Cronbach's alpha of 0.676 for the pretest data and 0.784 for the posttest data. The test-retest coefficient reliability coefficient [START_REF] Crocker | Introduction to classical and modern test theory[END_REF] for the APCR data was equal to 0.597, another low indicator.

Conversations were held with the authors of the APCR and the instrument is undergoing major revisions to be re-tested in April 2017. Working collaboratively with the APCR team on the newly revised version hopefully will generate an instrument that performs at a higher standard for greater reliability and discrimination. The poster presentation provided an excellent venue to review the testing results and confer with colleagues in possible next steps which were taken in March, 2017.

Proceedings of CERME10


text:
Anthony Cronin
email: anthony.cronin@ucd.ie

Maria Meehan
email: maria.meehan@ucd.ie

In what ways do lecturers receive and use feedback from large first year mathematics classes?

Keywords: Feedback, large class instruction, mathematics support

We report on a study aimed at examining the ways in which lecturers of large mathematics classes receive and use feedback from their students, with a particular focus on how they use feedback received via the Maths Support Centre (MSC). Three separate interviews with each of thirteen lecturing staff over the course of one semester were conducted. We discuss the ways in which these lecturers receive and use ten modes of feedback from their students and examine where the feedback received by the MSC sits in the general context of this feedback. We conclude that MSC feedback is one of

Research questions

 How do lecturers receive and use feedback from large first year mathematics classes?  In what ways, if any, do lecturers find the feedback provided by the MSC on students' visits, useful? How do they use it?  Where does MSC feedback sit placed in the general context of formative feedback?

Methodology

Thirteen lecturers from a research-intensive university in Ireland volunteered to participate in this study. Lecturing experience varied from two to seventeen years and two lecturers were teaching their particular module for the first time. The modules' sizes ranged from 66 to 550 students in subjects including Calculus, Statistics, Linear Algebra, Computer Science and Applied Mathematics. Twelve of the 13 classes we examined were mathematics/statistics modules taught to non-mathematicians, in particular the cohorts consisted of agriculture, computer science, engineering, business, science and applied mathematics students.

Thirty-seven semi-structured interviews consisting of three interviews with each lecturer were conducted in semester one of 2014/15 (interview one was not conducted with one lecturer as there was no MSC feedback to discuss at that time and the final interview for one module was conducted with both co-lecturers of that module simultaneously). This feedback, on the content of each students' visit, is generated by the attending MSC tutor and electronically uploaded (anonymously) in real time via the MSC software system where it can be viewed at any time by the lecturer [START_REF] Cronin | The development and evolution of an advanced data management system in a mathematics support centre[END_REF]. Interview 1 was an exploratory interview conducted in week 4 of the teaching term where lecturers were asked to review the MSC feedback collected from their module to see if they could identify the topic and mathematical difficulty being reported. The mathematical content of this feedback is discussed in the PhD of Nuala Curley and more information is available in [START_REF] Curley | Most commonly occurring mathematical difficulties -eight weeks in the life of a Maths Support Centre[END_REF]. Interview 2 was conducted in week 8 where lecturers were asked to comment on the various ways in which they receive feedback from their students and to comment on the usefulness of each. The third interview, conducted three weeks after teaching had finished, invited lecturers to Thematic Working Group 14 Proceedings of CERME10

summarise their experiences with the MSC feedback mechanism throughout the term and discuss the value associated with each of the feedback forms they received from students throughout the module. Interviews were analysed using thematic analysis [START_REF] Braun | Using thematic analysis in psychology[END_REF].

Findings

Lecturers reported nine ways in which they receive feedback from large classes. These are: in-class questions, after-class questions, continuous assessment (e.g. quizzes), midterms and final exams, module tutors, online activity (Blackboard, Moodle, WebWork etc), the institution's Module Feedback system, staff-student fora and MSC feedback (Figure 1). Lecturers identify MSC feedback as one of the most valuable forms of feedback from a large mathematics class. In particular it is specific, detailed and lecturers reported that it aligns closest to in-class questions as it is content based, formative and in real time. It is mathematically accurate being the MSC tutor's interpretation of the student's difficulty. Lecturers stated that it is reassuring and confirms what is been asked at (and after) lectures. Many instructors stated that reviewing MSC feedback has had impact on their practice including; revising lecture content, writing midterms and revision classes, omitting material and delaying (or bringing forward) continuous assessment components.

Figure 1 :

 1 Figure 1: Usefulness of feedback forms to lecturers

Thematic Working Group 14 Proceedings of CERME10


text:
Megan Wawro
email: mwawro@vt.edu

Kevin Watson

Warren Christensen
email: warren.christensen@ndsu.edu

Meta-representational competence with linear algebra in quantum mechanics

Keywords: Linear algebra, meta-representational competence, physics

In this report we analyze one student's meta-representational competence as he engages in solving a quantum mechanics problem involving the linear algebra concepts of basis, eigenvectors, and eigenvalues. We provide detail on student A25, who serves as a paradigmatic example of a student's power and flexibility in thinking in and using different notation systems. This case study, which lays the groundwork for future analysis, provides evidence that meta-representational competence (MRC) is beneficial to a student's ability to make sense of and use concepts from linear algebra while solving quantum mechanics problems.

Introduction

The National Research Council's (2012) report, which charges the United States to improve its undergraduate Science, Technology, Engineering, and Mathematics (STEM) education, specifically recommends "interdisciplinary studies of cross-cutting concepts and cognitive processes" (p. 3) in undergraduate STEM courses. It further states that "gaps remain in the understanding of student learning in upper division courses" (p. 199), and that interdisciplinary studies "could help to increase the coherence of students' learning experience across disciplines … and could facilitate an understanding of how to promote the transfer of knowledge from one setting to another" (p. 202). Our work contributes towards this need by investigating student understanding of linear algebra in quantum mechanics. Two research questions that guide us in this paper are: what are the various ways in which students reason about and symbolize concepts related to eigentheory in quantum physics, and in what ways might meta-representational competence impact how they make sense of linear algebra concepts in quantum mechanics?

In this paper, we focus on one student's reflection on symbolizing choices he makes while solving a quantum mechanics problem that involves linear algebra. In particular, we analyze his reasons for how and why he chooses a specific symbol systemeither Dirac notation or matrix notationfor solving an expectation value problem. We align our analysis with the frameworks of metarepresentational competence [START_REF] Disessa | Inventing graphing: Metarepresentational expertise in children[END_REF] and of structural features of algebraic quantum notations [START_REF] Gire | Structural features of algebraic quantum notations[END_REF]. This case study, which lays the groundwork for future analysis, explores in what ways MRC might aid a student's ability to make sense of and use concepts from linear algebra while solving quantum mechanics problems.

Background and theoretical framework

In this section, we give an overview of research conducted on student understanding of symbols and representations in mathematics and physics, as well as our theoretical orientation. We conclude with a brief introduction to eigentheory in Quantum Mechanics and Dirac notation.

Student understanding of symbols and representations

The recognition of the importance of students' understanding of symbols used in mathematics and physics has grown over the past few decades. [START_REF] Arcavi | Symbol sense: Informal sense-making in formal mathematics[END_REF][START_REF] Arcavi | Developing and using symbol sense in mathematics[END_REF] coined this as "symbol sense," which includes aspects such as being "friendly" with symbols, engineering symbolic expressions, choosing which aspects of a mathematical situation to symbolize, using symbolic manipulations flexibly, and sensing the different roles symbols can play in various contexts. Other research along this vein include: an explication of how different perspectives, such as cognitivist, situationist, and social-psychological, provide vastly different ways to understand how students make sense of and use inscriptions and symbols [START_REF] Kaput | Representations inscriptions, descriptions and learning: A kaleidoscope of windows[END_REF]; a study of how students mathematize their language from a Vygotskian perspective [START_REF] Van Oers | The mathematiztion of young children's language[END_REF]; and an exploration of how notational systems can serve as a mediational tool which triggers and sustains mathematical activity [START_REF] Meira | Mathematical representations as systems of notations-in-use[END_REF].

Research into students' competence with symbols and representations is not limited to primary and secondary school studies. For example, [START_REF] Hillel | Modes of description and the problem of representation in linear algebra[END_REF] described three modes of description (abstract, algebraic, and geometric) of the basic objects and operations in linear algebra and pointed out that "the ability to understand how vectors and transformation in one mode are differently represented, either within the same mode, or across modes is essential in coping with linear algebra" (p. 199). [START_REF] Thomas | Eigenvalues and eigenvectors: Embodied, symbolic and formal thinking[END_REF] found that students struggle to coordinate the two mathematical processes captured in 𝐴𝒙 = 𝜆𝒙, where 𝐴 is an n x n matrix, 𝒙 is a vector in ℝ 𝑛 , and 𝜆 is a scalar, to make sense of equality as "yielding the same result." This interpretation of the "equals" symbol is often novel and nontrivial for students [START_REF] Harel | Three principles of learning and teaching mathematics: Particular reference to linear algebra-old and new observations[END_REF]. Harel also posits that the interpretation of "solution" in this setting, the set of all vectors 𝒙 that make the equation true, entails a new level of complexity than does solving equations such as 𝑐𝑥 = 𝑑, with each taking values from the reals. [START_REF] Thomas | Eigenvalues and eigenvectors: Embodied, symbolic and formal thinking[END_REF] conjecture that this complexity may prevent students from progressing symbolically from 𝐴𝒙 = 𝜆𝒙 to (𝐴 -𝜆𝐼)𝒙 = 𝟎, which is particularly useful when solving for the eigenvalues and eigenvectors of a matrix 𝐴.

Research into students' understanding of quantum mechanics also investigates student use of symbols, such as how students make sense of and use a novel notation, called Dirac notation (explained in the subsequent section). Most closely related with this current study, [START_REF] Gire | Structural features of algebraic quantum notations[END_REF] looked at structural features of three different notation systems used in quantum mechanics (Dirac, matrix, and wave function) and how students' reasoning interacts with these features. The features identified by the authors are: (a) individuation, or "the degree to which important features are represented as separate and elemental" (p. 5); (b) externalization, or "the degree to which elements and features are externalized with markings included in the representation" (p. 7); (c) compactness; and (d) symbolic support for computation. Using problem-solving interviews with students as insight into these features, Gire and Price found that students readily used Dirac notation, and that the structural features vary across the different notations and among contexts. Relatedly, diSessa et al. (1991) importantly discovered that students have a great deal of knowledge about what good representations are and are able to critique and refine them, which the authors defined as Meta-Representational Competence (MRC). diSessa and Sherin (2000) explained that MRC includes inventing and designing new representations, judging and comparing the quality of representations, understanding the general and specific functions of representations, and quickly learning to use and understand new representations. Furthermore, diSessa (2002,2004) offered a variety of critical resources students possess as part of their MRC for judging the strength of representations, such as compactness, parsimony, and conventionality. Two particular resources encompassed by MRC that we focus on in our data are "critique and compare the adequacy of representations and judge their suitability for various tasks," and "understand the purposes of representations generally and in particular contexts and understand how representations do the work they do for us (diSessa, 2004, p. 94).

In this study, we align ourselves with the theory that representations are a sense-making tool, in that "the construction of representations on paper during problem solving mediates and organizes one's understanding of mathematical concepts" (Meira, 2002, p. 101). We couple this with a framing of MRC, specific to two particular notational systems, to investigate a student's reflection on his own notational preferences in quantum mechanics and what that may reveal about his understanding of change of basis and eigentheory in that context.

Brief introduction to eigentheory and Dirac notation in quantum mechanics

In quantum mechanics, certain physical systems are modeled and made sense of using eigentheory. To a physical system we associate a Hilbert space (such as ℂ 2 ), to every possible state of the physical system we associate a vector in the Hilbert space, and to every possible observable (i.e., measurable physical quantity) we associate a Hermitian operator (usually given in its matrix form). The only possible result of a measurement is an eigenvalue of the operator, and after the measurement the system will be found in the corresponding eigenstate.

Dirac notation, also known as bra-ket or just ket notation, is a commonly used notational system in quantum mechanics. A vector representing a possible state is symbolized with a ket, such as |𝜓⟩. are the two possible measurement results of the observable. When symbolized in terms of this eigenbasis, the matrix representation of 𝑆 𝑥 is

[ ℏ 2 ⁄ 0 0 -ℏ 2 ⁄ ].
One can also measure spin along other directions, such as 𝑧; similarly, the eigenvalue equations are 𝑆 𝑧 |±⟩ = ± ℏ 2 |±⟩ (it is common for no subscript to be used for the 𝑧-direction). Thus, "within its own basis," the matrix representation of 𝑆 𝑧 would be identical to the aforementioned diagonal one for 𝑆 𝑥 . It is often beneficial to change between bases; for example,

|+⟩ 𝑥 = 1 √2 |+⟩ + 1 √2 |-⟩ and |-⟩ 𝑥 = 1 √2 |+⟩ -1 √2 |-⟩, so 𝑆 𝑥 in the "𝑧-basis" is [ 0 ℏ 2 ⁄ ℏ 2 ⁄ 0
]. Finally, inner products are involved in computing the expectation value of observable 𝐴 for state psi, ⟨𝜓|𝐴|𝜓⟩. These calculations require the bra and ket expansion to be in the same eigenbasis as the matrix representation of 𝐴. As such, expectation value problems present a rich setting for investigating students' symbolizing of eigentheory and change of basis in a physics context.

Methods

Participants for this study were third year undergraduate physics majors at a large, public, researchintensive university in the Pacific Northwestern United States. They were drawn on a volunteer basis from a class of 35 students in a Spin and Quantum Measurements course; this course met for 7 classhours per week for three weeks and involved many student-centered activities and discussions. The data for this report come from individual, semi-structured interviews (Bernard, 1988) conducted with 8 students at the end of the course. The goals of the interview questions were to learn how students reasoned about linear algebra concepts (e.g., normalization, basis, and especially eigentheory), how they reasoned with these concepts as they discussed quantum mechanics concepts and solved quantum mechanics problems, and how they symbolized their work.

To begin our analysis, we viewed the video and observed how students navigated the interview problems, while we kept in mind the overarching research questions regarding students' reasoning about and symbolizing eigentheory in quantum physics. We noticed some students were particularly fluent in how they talked about and worked with both matrix and Dirac notations. This compelled us to investigate the literature about student use of symbols and notations, the most relevant of which were discussed above. Our analysis draws most heavily on the work of diSessa and colleagues regarding MRC, and that of [START_REF] Gire | Structural features of algebraic quantum notations[END_REF] regarding structural features of algebraic quantum notations. In particular, we coded for instances of students mentioning structural features of the mathematics or students making explicit meta-commentary on the representations they chose to use. This allowed us to integrate our analysis of students' MRC with Gire and Price's types of structural features in a way novel to the physics and mathematics education fields.

In this report, we focus on one student: A25, a double major in physics and nuclear engineering who had completed two 10-week courses in linear algebra. The reason we chose to focus on participant A25 was his demonstrated ability to articulate his thinking. During the interview, he exhibited flexibility in reasoning about the concepts we were probing, and through his explanation a great deal of MRC seemed visible and analyzable.

Results

In the beginning of the interview, student A25 volunteered that he sometimes explicitly chooses between doing calculations in matrix notation or in Dirac notation: I: So how do you feel like, using eigenvectors and eigenvalues, in spins has been similar to and different from how you've experienced those in other classes? A25: Uh, well, it's very similar because you're doing a lot of the same math …the difference especially in physics, you're looking at kets. In, in at first I was kind of jarring, like to-to try to do the math in kets. But now, it's kinda-it's kinda easier, there's problems, there certain problems…where there's two ways to do them, they're kind of parallel, you can do it and you can expand the-the state in-in like as a-and expand them as kets in a different basis, or you can write that state as aas a, as a vector, in that basis, and you can either do the matrix math for the like expectation values for example, you can do the matrix math or you can do the ket math, and sometimes it's, I'm finding that I, rather expand something in the ket.

From the transcript we see that A25 was aware multiple legitimate ways exist to solve the problem, seemingly understanding the various mathematical nuances and implications of his notational choices. His brief explanation highlights sentiments that are consistent with Arcavi's characteristics of symbol sense, such as being "friendly" with symbols and using them flexibly. Also, A25's selfreflection on his symbol usage adds a metacognitive aspect to the symbol sense characterization.

Because A25 volunteered expectation value problems as a situation in which he could use either notation, the interviewer had him work on such a problem right away, even though it was prepared to be at the end of the interview: "Consider the state |𝜓⟩ = -4 5

|+⟩ 𝑥 + 𝑖 3 5

|-⟩ 𝑥 in a spin-1/2 system.

Calculate the expectation value for the measurement of 𝑆 𝑥 ." A25 immediately worked on the problem using Dirac notation, saying, "basically to find the expectation value… it's like denoted that way [writes 〈𝐴〉] but really what you're doing is you're taking the, the bra of the state, and then you're putting the operator [writes = ⟨𝜓|𝐴|𝜓⟩] in the middle of the inner product." He continued to explain his work as he proceeded, with statements such as "you know that 𝑆 𝑥 is just going to um, like apply it's eigenvalues to these, so, so like the eigenvalue corresponding to plus 𝑥 is going to be + ℏ 2 ⁄ and the, the eigenvalue corresponding to -𝑥 is going to be -ℏ 2 ⁄ , so you end up with this equation that looks like this [points to the second half of line 2 in Figure 1a]. Note that his work in Figure 1a, which led him to the correct answer of 7ℏ 50 ⁄ , involved the state's expansion and use of eigenvector equations for 𝑆 𝑥 in ket notation. He did not need to physically write the expansion of |𝜓⟩ in the 𝑥 basis kets, nor did he write out the eigenvector equations; however, his verbal description of his process relied on his understanding of both basis and the eigenvector relationships at play. Furthermore, this notation was novel to the students during this course; as such, A25 was clearly quick to use and understand this representation (a quality of MRC, diSessa & Sherin, 2000).

After discussing his work and solution, the interviewer asked: "Before you were telling about bra-ket versus matrix notation, you brought up an expectation value as an example of like, either or both, so can you, now that you had this problem, kinda revisit that?" A25 immediately solved the problem completely within matrix notation. He began by saying "if we're strictly in the plus and minus 𝑥 basis" and wrote the column vector [ ] associated with the given ket |𝜓⟩. He then said, "and then the bra would be, um, minus 4 over 5 and then minus i 3 over 5," writing out the row vector [- as he spoke (see Line 1 in Figure 1b). He then said, "and so what you do is take this [copies the column vector]…and then you have the operator in the middle [writes an empty 2x2 matrix], and then you have the bra here [copies the row vector], and the operator in this case is 𝑆 𝑥 and we're in the 𝑥 basis so it's just ℏ 2 ⁄ and -ℏ 2 ⁄ , 0, 0" [fills in the 2x2 matrix values] (see line 2 in Figure 1b). Impressively, he was able to fluidly move from his original ket notation to matrix notation, flawlessly making translations from the bras, kets, and operators in ket notation to row vectors, column vectors, and matrices in the matrix notation, further evidence of his strong MRC. Next, he explained his process for computing the matrix times the column vector before he did the computation, noting that "you're gonna get a vector." Again in line 3 he explained "then I do it again, so, um, this time you're gonna get a number out," meaning he anticipated that a row vector times a column vector would be a number. This shows two aspects of A25's strong understanding: first, a fluency in the calculations and computations within matrix notation similar to his ease in working in ket notation, including the ability to anticipate results before actually carrying out a computation (as in anticipating the result of a matrix times a vector); and second, an ability to compare the two notations as well as an understanding that the two notations represent two ways to conceptualize the quantum physical calculation of expectation value. We see this as flexibly using symbolic manipulations (Arcavi, 1995) and an anticipation of results. The interviewer then asked A25 to reflect on any preference between the two notations: A25: Uh...To be honest, I don't really, I don't really know why I prefer this [Figure 1a], I think it's just because, um, I like this notation. This specific notation [Figure 1a line 1] like this to me is like a cleaner way of writing that [Figure 1b line 2] because that-I mean this and that [touches Figure 1a We see his use of "nice looking thing" and "big array of numbers" in comparison to one another are an example of compactness. He also compares Figure 1a line 1 and Figure 1b line 3 regarding the "amount" of information they convey, which involves reflection on the physical and mathematical content expressed in the compared notations. Finally, acting directly on the expansion in terms of the eigenstates of the operator allow him to forego the matrix calculation entirely, which speaks to A25's view of compactness, parsimony, and symbolic support for ket notation for this problem.

When asked about his notation preferences if the basis expansion of a given state vector and the operator "didn't match," A25 recalled a problem from his last homework that was "actually easier…to do the matrix multiplication," stating "you don't want to have to change these kets into different bases all over the place 'cause they're already all written in the same basis and you know what the operator is in that basis so you might as well just, do the matrix multiplication." Here we see how strong A25's understanding is of the important linear algebra concepts of bases and change of bases, and how they relate to the matrix multiplication within expectation value quantum mechanics problems.

Furthermore, we see another aspect of his MRC, namely his understanding that different notations have different strengths and weaknesses, and his ability to leverage these strengths and weaknesses depending upon the particular quantum mechanics situation. This speaks to his awareness of symbolic support as well as using symbols flexibly. Finally, when asked if the concepts of basis or eigenvectors/eigenvalues come up more in one notation than the other, A25 1a] you're thinking ok, this is the 𝑆 𝑥 operator, this is the 𝑥 plus ket, this is the 𝑥 minus bra…so I think that you're definitely more aware of what basis you're in when you're using this, because you have to be." This explanation is consistent with externalization [START_REF] Gire | Structural features of algebraic quantum notations[END_REF], in that the ket notation allows features of the problem, namely basis, to be externalized in a way that matrix notation did not provide for A25. This again attests to his understanding that notations have different strengths and weaknesses, an element of MRC that seems particularly important within quantum mechanics.

Conclusion

In this report we analyzed one student's MRC and his understanding of change of basis and eigentheory as he solved an expectation value problem in quantum mechanics. This case study lays the groundwork for future analysis by being a paradigmatic example of a student's power and flexibility for thinking in and using different notation systems. In addition, it provides evidence that MRC seemed to positively impact this student's ability to make sense of and use concepts from linear algebra while solving quantum mechanics problems. In addition to analyzing the other students from our data set, future research includes investigating how classroom interactions may have influenced students regarding their notational choices, what aspects of MRC seem most important to success in using linear algebra when solving quantum mechanics problems, and what that implies regarding students' understanding of the mathematics and physics content involved.

Figure 1 :

 1 Figure 1: A25's expectation value problem, in ket notation (a) and matrix notation (b)

  line 1 and Figure 1b line 2 simultaneously] I feel like are your starting points, so you, you start here with this nice, like, looking thing [traces one finger under ⟨𝜓|𝐴|𝜓⟩], or you start here with this big array of numbers [puts two open hands around Figure 1b line 2], and I prefer this [Figure 1a line 1], even though you have to expand this into basically the same amount of information [Figure 1a line 2]. And also, the nice thing about, about this [Figure 1a line 1], is it-actually this is really why it's better-is because you can, you can say ok 𝑆 𝑥 works-acts directly on these kets, you can just get rid of the matrix altogether...

  𝑆 𝑥 |±⟩ 𝑥 = ± ℏ 2 |±⟩ 𝑥 , where |+⟩ 𝑥 and |-⟩ 𝑥 form an orthonormal eigenbasis of 𝑆 𝑥 , and ±

	Mathematically, kets behave like column vectors, such as |𝜓⟩ ≐ [ 𝑎 2 𝑎 1	], 𝑎 1 , 𝑎

2 ∈ ℂ, and are usually normalized. The complex conjugate transpose of a ket is called a bra, which behaves mathematically like a row vector, such as ⟨𝜓| ≐ [𝑎 1 * 𝑎 2 * ]. In addition, the eigenvalue equations for observables are central to many calculations. For example, the eigenvalue equations for 𝑆 𝑥 (the operator measuring the 𝑥-component of intrinsic angular momentum) of a spin-½ particle are ℏ 2

  stated, "certainly…every time you write down a ket you're, you're very conscious of what basis you're in. In this one [points to Figure 1b] it's just kinda implied…all this [is] in the same basis, so you're just, you're just writing out numbers, an arrays of numbers, but here [in Figure

Proceedings of CERME10

Acknowledgment

This material is based upon work supported by the National Science Foundation under Grant DUE-1452889. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. The authors thank Andy diSessa, Jeff Rabin, Michael Wittmann, and Michelle Zandieh for their insights on the data.