Module Specifications.Assign1

This assignment is due on Thursday 1/30 by 8:00PM. You should put all of your solutions in a file called assign1/lib/assign1.ml. See the file test/test_assign1.ml for example behavior of each function.

Programming

Practice Problems (Ungraded)

These problems come from a list of Exercises on OCaml's webpage. We won't grade these (the solutions are given with the problem statements) but we'll typically include a couple with each assignment for additional practice.

Perfect Numbers

val is_perfect : int -> bool

A positive integer is perfect if it's equal to the sum of its proper divisors. For example, the integer 6 is perfect since 6 = 1 + 2 + 3. Implement the function is_perfect so that is_perfect n is true if n is perfect and false otherwise. The behavior of the function is undefined if n is not positive.

Sum of Squares

val min_sos : int -> int

Implement the function min_sos so that min_sos n is the minimum number of perfect squares required to sum up to n. For example, 8 = 2^2 + 2^2 and 8 is not a perfect square so min_sos 8 = 2. The behavior of the function is undefined if n is negative.

Number of Substring Occurrences

val num_occurs : sub:string -> string -> int

Implement the function num_occurs so that num_occurs ~sub:s t is the number of occurrences of possibly overlapping instances of s in t. For example, the string "AA" appears in the string "AAA" twice as a substring so num_occurs ~sub:"AA" "AAA" = 2. The behavior of the function is undefined if s is the empty string. Hint. You should use the function String.sub. See the Stdlib320 documentation for more details.

Note the use of labeled arguments. Please reread this subsection of OCP. This is not a core feature of OCaml but you should become comfortable with it.

Written

Typing Judgments to English

    \def\code#1{\textcolor{purple}{\texttt{#1}}}
    \def\fun#1#2{#1 \ \code{->} \ #2}
    \def\comp{\ \code{>>} \ }
    \{ \
    \code{f} : \fun{\tau_1}{\tau_2}
    \ , \
    \code{g} : \fun{\tau_2}{\tau_3}
    \ \}
    \vdash
    \code{f} \comp \code{g} :
    \fun{\tau_1}{\tau_3}

Write down an English sentence which expresses the same thing as the above typing judgment. (Note: This operators is not in the OCaml standard library)

Typing Rules to English

    \def\code#1{\textcolor{purple}{\texttt{#1}}}
    \def\xor{\ \code{xor} \ }
    \frac
    {
    \Gamma \vdash e_1 : \code{bool}
    \qquad
    \Gamma \vdash e_2 : \code{bool}
    }
    {\Gamma \vdash e_1 \xor e_2 : \code{bool}
    }
    \
    (\mathsf{xor})

Write down an English sentence which expresses the same thing as the above typing rule. (Note: This operators is not in the OCaml standard library)

Semantic Rules to English

    \def\code#1{\textcolor{purple}{\texttt{#1}}}
    \def\xor{\ \code{xor} \ }
    \frac
    {
    e_1 \Downarrow \top
    \qquad
    e_2 \Downarrow v_2
    }
    {e_1 \xor e_2 \Downarrow \neg v_2}
    \
    (\mathsf{xorTrueEval})

Write down an English sentences which express the same things as the above semantic rules. The symbol '\neg' is Boolean negation (i.e., not in OCaml).

English to Semantic Rules

Write down the semantic rule which expresses the same thing as the following English sentence:

If the expression e_1 evaluates to the Boolean value \bot and the expression e_2 evaluates to the Boolean value v_2, then the expression e_1 \ \textcolor{purple}{\texttt{xor}} \ e_2 evaluates to v_2.