Description

Rate this product

1    Introduction

 

This assignment will practice  imperative  programming.

 

 

1.1     Getting The Homework Assignment

 

The starter files for the homework assignment have been distributed through our git repository,  as usual.

 

 

1.2     Submitting The Homework Assignment

 

Submissions will be handled through Autolab, at https://autolab.andrew.cmu.edu.

To submit  your solutions,  run make from the hw/11 directory  (that con- tains a code folder). This should produce a file hw11.tar, containing the files that  should be handed  in for this homework assignment.  Open the Autolab web site, find the  page for this  assignment,  and submit  your hw11.tar file via the “Handin  your work” link.

 

This  homework  will be partially  autograded.   When  you  submit  your code some very basic tests  are run.  These are the public tests,  and you will immediately  see your score on these.  After the final submission deadline, we will run a more comprehensive suite of private tests on your code. Your final score will be a function of your public score, private  score, and any manual grading we perform.  Non-compiling code will automatically receive a 0.

All the  code that  you want  to  have  graded  for this  assignment  should be contained  in imperative.sml, and must  compile cleanly.  If you have a

 

 

 

 

 

 

function  that  happens  to be named  the  same as one of the  required  func- tions but does not have the required type, your code will not compile in our environment.

 

 

 

 

1.4     Methodology

 

Since you  are  implementing  modules,  we give you  the  signatures  for the modules.  The specs are in the signatures,  so you don’t need to write specs. However you still need to write testcases.

For example, for the factorial function presented  in lecture:  Please write tests  in a separate  testing  structure(s).

For example:

 

signature FOO =

sig

val fact : int -> int end

 

structure Foo : FOO =

struct

(* fact : int -> int

* REQUIRES: n >= 0

* ENSURES: fact(n) ==> n! *)

fun fact (0 : int) : int = 1

| fact (n : int) : int = n * fact(n-1)

end

 

structure FooTests =

struct

val 1 = Foo.fact 0 val 6 = Foo.fact 3

end

 

 

 

 

 

 

2    The Only Constant  is Change

 

Arrays are a commonly used mutable  datastructure, especially in imperative languages.   While SML has its  own array  implementation in the  standard basis library,  we will task you to implement your own version of arrays.

 

 

Representation

 

We will represent arrays  as the type

 

datatype ’a array = A of int * (int -> ’a ref)

 

A value  A(n,f) of type  t array represents  an  array  of length  n using  a partial  function  f which maps any integer  0 to n-1 to an ’a ref reference cell containing  the element at that  index.

If we wish to change an element of A(n,f) at index i to the value x, we can use the following code: f i := x. Likewise, if we want the ith element of arr, we can use !(f i). If an index i is out of bounds, f i can do whatever it wants.   We provide an exception OutofBounds that  you can raise in this case.

Note:  Built-in  arrays  have constant-time access, but  because we are im- plementing  arrays with functions, we will allow accessing an element to take O(log n) time instead.

 

 

Implementation

 

 

Task 2.1 (10 pts).  Implement the function

 

init array: int -> ’a -> ’a array

 

init array n a is a new array defined over the indices 0 through n − 1, with all elements initialized to a. Beware of aliasing : different elements need to be in different reference cells. Random access must have O(log(n)) work at most.

 

 

 

Task 2.2 (1 pts).  Implement the function

 

get : ’a array -> int -> ’a ref option

 

 

 

 

 

 

get a i returns  SOME( the i’th element of a) or NONE if it is out of bounds.

Task 2.3 (3 pts).

 

Implement the function

 

double len: ’a array -> ’a -> ’a array

 

double len arr n a is an  array  of length  2n with  the  exact  same first n elements and ref-cells as arr (such that  modifying an element in one will be reflected in the other).  The last n elements should be initialized to a. This new larger array should also have logarithmic work random access if arr has logarithmic  work random  access.

 

Task 2.4 (3 pts).  Implement the function

 

foldl: (’a ref * ’b -> ’b) -> ’b -> (’a array) -> ’b

 

foldl f b a returns  the value produced  by using f to combine all the ref- erences  in the  array  from left-to-right (in the  same order  as List.foldl). This should not change the state  of the array  unless f does.

 

Task 2.5 (3 pts).  Implement the function

 

expand: ’a array -> int -> ’a -> ’a array

 

expand a n x expands  a to a size of exactly  n, filling in the new elements with x (hint:  You know how to make arrays longer, and making them shorter is easy.)

 

 

Memo

 

 

Task 2.6 (8 pts).  Storing previous results in an array can make code faster. Implement the function

 

memo fib: unit -> int -> IntInf.int

 

where memo fib () returns  a function (let’s call that  function f), where f i is the ith Fibonacci  number  (starting at  0, 1).  For all i:int, f should only compute  the  value  of f i once, storing  the  result  in a array.   After  that,

 

 

 

 

 

 

calling f i should result  in looking up the  appropriate value in the  array. You should test that  your function is not exponential  time by running a test that  would take  too  long if it  was exponential-time. Hint:   memo fib () should return  a new function that  uses some local state.

Note: This function returns  IntInf.int which is like int except it can represent  arbitrarily large numbers  (which is useful for testing  fib).  This type uses the exact same type as int and supports  the same operations  (you can write out numerals, write + and *, etc.)  To use IntInf.int you just need to add at least one type annotation somewhere, such as (0 : IntInf.int) so that  it doesn’t accidentally  use int instead.

 

 

Searching Arrays

 

Let’s practice  different ways of searching an array  by writing Finds

 

Task 2.7 (2 pts).  Implement

findr:  (’a ref -> bool) -> ’a Array.array -> ’a ref option findr p a returns  (SOME applied to) a reference r from the array a such that

p r == true if one exists, NONE otherwise.

 

Task 2.8 (1 pts).  Implement

findv: (’a -> bool) -> ’a Array.array -> ’a ref option findv p a returns  (SOME applied  to)  a reference r from the  array  a such

that  p x == true for the  value x currently  stored  in r, if one exists, NONE

otherwise.

 

Task 2.9 (2 pts).  Implement

findv imp(’a -> bool) -> ’a Array.array -> ’a ref ref -> bool findv imp p a out searches  for a reference r from the  array  a such that

p x == true for the value x currently  stored in r. If such an element exists, findv stores it in out.  findv_imp returns  true iff it modified out, false otherwise.

 

Task 2.10  (2 pts).  Implement

 

containsr : ’a ref > ’a Array.array -> bool

 

 

 

 

 

 

containsr a r evaluates  to true iff the reference r is in the array a, false

otherwise.

 

 

 

 

See you at the final! Good luck, have fun!