# Ocaml代写 | Homework 8

### Getting the code template

Before you perform the next steps, you first need to create your own private copy of this git repository. To do so, click on the link provided in the announcement of this homework assignment on Piazza. After clicking on the link, you will receive an email from GitHub, when your copy of the repository is ready. It will be available at https://github.com/hw08-<YOUR-GITHUB-USERNAME> . Note that this may take a few minutes.

Choose a place on your computer for your homework assignments to reside and open a terminal to that location.

### Preliminaries

We assume that you have installed a working OCaml distribution, including the packages ocamlfind , ocamlbuild , and

ounit . Follow the instructions in the notes for Class 7 if you haven’t done this yet.

### Submitting your solution

Once you have completed the assignment, you can submit your solution by pushing the modified code template to GitHub. This can be done by opening a terminal in the project’s root directory and executing the following commands:

git add .

git commit -m “solution”

You can replace “solution” by a more meaningful commit message. Refresh your browser window pointing and double-check that your solution has been uploaded correctly.

You can resubmit an updated solution anytime by reexecuting the above git commands. Though, please remember the rules for submitting solutions after the homework deadline has passed.

### Preliminaries

The goal of this homework is to implement a small library for arbitrary precision integer arithmetic in OCaml. The code template consists of two files.

### Problem 1: Big Natural Numbers (7 Points)

We start with an implementation of an OCaml module BigNat for manipulating arbitrarily large natural numbers. The file arithmetic.ml defines the signature BigNatType of this module, as well as an incomplete implementation of BigNat .

• Understand the partial implementation of big natural numbers in the module BigNat and complete the missing functions sub (subtraction with carry) and ( ** ) (exponentiation). When you implement sub , pay attention to the elimination of leading zeros to preserve the uniqueness of the representation of natural numbers. The predefined function zcons is useful for this.Your implementation of sub should raise the exception Invalid_argument “result is negative” if the result of the subtraction is negative. You can do this with
`raise (Invalid_argument "result is negative")`
• Write a function
`fac: BigNat.bignat -> BigNat.bignat`

redefines the infix operator + to work on the type bigint rather than int . Note that OCaml does not support operator overloading. That is, the above definition shadows the standard definition of + on the type int in the remainder of the module implementation. Subsequent expressions x + y within the module scope will refer to the new definition of + and, hence, x and y will be expected to be bigint values rather than int values. If you need to use + on int values x and y , you can do this by writing Pervasives.(x + y) . This will locally open the Pervasives module, which contains all standard inbuilt operators and functions of OCaml including + on int . The same restrictions apply to the other operators like (-) , ( * ) , (/) , etc.

### Problem 2: Big Integers (13 Points)

Next, we want to build a module BigInt that provides arbitrary precision integer arithmetic operations by building on top of our module BigNat . The resulting module should have the signature BigIntType . Rather than using BigNat directly, we parameterize our implementation of BigInt by a module of the signature BigNatType so that we can easily swap out one implementation of BigNat with another. That is, we implement a functor

`module MakeBigInt (BigNat : BigNatType) : BigIntType`

In our functor, we implement the type bigint of BigIntType as follows

`type bigint = bool * BigNat.bignat`

Complete the missing implementations of the functions in MakeBigInt using the functions provided by BigNat . The function to_string should use the symbol – as the sign for negative numbers. The exponentiation function ( ** ) should raise an exception Invalid_argument “negative exponent” if the given exponent is negative.

Hints: Be careful to ensure that the representation of big integers is unique so that the meaning of equality of two values is correct. That is, the number 0 must be represented uniquely. You may want to write a helper function

`val norm: bigint -> bigint`

E-mail: [email protected]  微信:dmxyzl003

E-mail: [email protected]  微信:itcsdx