ocaml代写

  git add .
  git commit -m "solution"
  git push

You can replace “solution” by a more meaningful commit message. Refresh your browser window pointing at

  https://github.com/nyu-pl-fa18/hw07-<YOUR-GITHUB-USERNAME>/

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.

Problem 1: Parametric Polymorphism (5 Points)

Write OCaml functions that satisfy the following polymorphic type signatures: ^. afunction f:(‘a->’b)->(‘b->’c)->’a->’c
_. afunction g:(‘a*’b->’c)->’a->’b->’c
`. afunction h:(‘a->’b->’c)->’a*’b->’c

For the next two subproblems, assume we are additionally given the following algebraic data type:

  type ('a,'b) sum =
    | L of 'a
    | R of 'b

a. afunction i:(‘a,’b)sum*(‘a->’c)*(‘b->’c)->’c

b. a function j: (‘a, ‘b * ‘c) sum -> (‘a, ‘b) sum * (‘a, ‘c) sum

It does not matter what your implementations of these functions do as long as they satisfy the above type signatures. In all cases, there is an obvious implementation that follows from the type signature. Note that you are not allowed to use any explicit type annotations in your solution.

Hint: Here is how to approach this problem. Consider the type of the function f : f: (‘a -> ‘b) -> (‘b -> ‘c) -> ‘a -> ‘c

This type tells you that f is a curried function that takes three parameters, say x y and z , and then returns some result. So the basic shape of the definition of f must look like this

let f x y z = e

for some appropriate expression e that you need to find. To figure out what e is, inspect the type of f and what it tells you about its parameters and return value. E.g. it tells you that x must be a function of type ‘a -> ‘b , y must be a function of type ‘b -> ‘c and z must be a value of type ‘a . Moreover, the return value has type ‘c , which hence is the type of the expression e that you need to find. So think about how to construct a value of type ‘c using x , y , and z .

Put your solution into the file src/problem1.ml .

Problem 2: MiniML

In this exercise we will practice the use of algebraic data types and use it in an application domain that functional programming languages are particularly well-suited for: symbolic computation.

The goal is to implement an interpreter for a dynamically typed subset of OCaml, called MiniML. We will implement the interpreter in OCaml itself. Most of the code will be given to you. Your task will be to implement three functions that are missing in the given code. These functions are relatively small but critical for the interpreter to work correctly.

Syntax

We consider a core language built around the untyped lambda calculus. For convenience, we extend the basic lambda calculus with primitive operations on Booleans and integers. We also introduce a fixpoint operator to ease the implementation of recursive functions. The concrete syntax of the language is described by the following grammar:

(Variables)
x: var

(Integer constants)
i: int  ::=

   ... | -1 | 0 | 1 | ...

(Boolean constants)
b: bool ::= true | false

(inbuilt functions)
f: inbuilt_fun ::=

not | fix

(Binary infix operators)
bop: binop ::=

* | / | mod

• |  +|-|
• |  &&|||
• |  =|<>
• |  <|>|<=|>=

  (Terms)
  t: term ::=
  

  f | i | b | x

(logical negation)
(fixpoint operator)

(multiplicative operators)
(additive operators)
(logical operators)
((dis)equality operators)
(comparison operators)

(inbuilt functions)
(integer constants)
(Boolean constants)
(variables)
(function application)
(binary infix operators)

| t1 t2
| t1 bop t2
| if t1 then t2 else t3 (conditionals)
| funx->t1 (lambda abstraction)

The rules for operator precedence and associativity are the same as in OCaml.
For notational convenience, we also allow OCaml’s basic let bindings, which we introduce as syntactic sugar. That is, the

OCaml expression

let x = t1 in t2
is syntactic sugar for the following term in our core calculus:

(fun x -> t2) t1
Similarly, the OCaml expression

let rec x = t1 in t2
is syntactic sugar for the term

(fun x -> t2) (fix (fun x -> t1))
We represent the core calculus of MiniML using algebraic data types as follows:

  (** source code position, line:column *)

  type pos = { pos_line: int; pos_col: int }
  (** variables *)

  type var = string

  (** inbuilt functions *)

  type inbuilt_fun =
    | Fix (* fix (fixpoint operator) *)
    | Not (* not *)

  (** binary infix operators *)

type binop =

|Mult
|Div
| Mod
|Plus
| Minus (* – *) |And (*&&*) |Or (*||*) |Eq (*=*) |Lt (*<*) |Gt (*>*) |Le (*<=*) |Ge (*>=*)

(** terms *)

type term =
| FunConst of inbuilt_fun * pos
| IntConst ofint*pos
| BoolConst of bool * pos
| Var of var * pos
| App of term * term * pos
| BinOp of binop * term * term * pos (* t1 bop t2 (binary infix operator) *)
| Ite of term * term * term * pos (* if t1 then t2 else t3 (conditional) *) | Lambda of var * term * pos (* fun x -> t1 (lambda abstraction) *)

Note that the mapping between the various syntactic constructs and the variants of the type term is fairly direct. The only additional complexity in our implementation is that we tag every term with a value of type pos , which indicates the source code position where that term starts in the textual input given to our interpreter. We will use this information to provide more meaningful error reporting to the programmer.

(***) (*/*) (* mod *) (*+*)

(* f (inbuilt function) *)
(* i (int constant) *)
(* b (bool constant) *)
(* x (variable) *)

(* t1 t2 (function application) *)

Code Structure, Compiling and Editing the Code, Running the Interpreter

The code template contains various OCaml modules that already implement most of the functionality needed for our interpreter:

src/util.ml: some useful utility functions and modules (the type pos is defined here)

src/ast.ml: definition of abstract syntax of MiniML (see above) and related utility functions

src/grammar.mly: grammar definition for a parser that parses a MiniML term and converts it into an abstract syntax tree

src/lexer.mll: associated grammar definitions for lexer phase of parser

src/parser.ml: interface to MiniML parser generated from grammar

src/eval.ml: the actual MiniML interpreter

src/miniml.ml: the main entry point of our interpreter application (parses command line parameters and the input file, runs the input program and outputs the result, error reporting)

src/tests.ml: module with unit tests for your code using the OUnit framework.

The interpreter is almost completely functional. However, it misses three functions that are only implemented as stubs (see below). These functions are found in the module Ast . The file ast.ml is the only file that you need to edit to complete this part of the homework. Though, we also encourage you to add additional unit tests to tests.ml for testing your code.

The root directory of the repository contains a shell script build.sh that you can use to compile your code. Simply execute ./build.sh

and this will compile everything. You will have to install ocamlbuild and ounit for this to work. Follow the instructions in the class notes for Class 7 to do this. Assuming there are no compilation errors, this script will produce two executable files in the root directory:

miniml.native : the executable of the MiniML interpreter.

tests.native : the executable for running the unit tests.
You can find some test inputs for the interpreter in the directory tests . In order to run the interpreter, execute e.g.

./miniml.native tests/test01.ml
Note that the interpreter will initially fail with an error message “Not yet implement” when you run it on some of the tests

because you first need to implement the missing functions described below.

The interpreter supports the option -v which you can use to get some additional debug output. In particular, once you have implemented the pretty printer for MiniML, using the interpreter with this option will print the input program on standard output after it has been parsed.

To run the unit tests, simply execute

  ./tests.native

The root directory of the repository also contains a file .merlin , which is used by the Merlin toolkit to provide editing support for OCaml code in various editors and IDEs. Assuming you have set up an editor or IDE with Merlin, you should be able to just open the source code files and start editing. Merlin should automatically highlight syntax and type errors in your code and provide other useful functionality. You may need to run build.sh once so that Merlin is able to resolve the dependencies between the different source code files.

Part 1: MiniML Pretty Printer (6 Points)

Your first task is to implement a pretty printer for MiniML. That is, you need to implement the two functions

  string_of_term: term -> string
  print_term: out_channel -> term -> unit

in ast.ml . The function string_of_term takes the AST of a MiniML term as input and is supposed to convert it into its textual representation. E.g. the code

  let t =
    Lambda ("x", BinOp (Mult, IntConst (2, dummy_pos),

in

  string_of_term t

should yield the string

BinOp (Add, Var ("x", dummy_pos), IntConst (3, dummy_pos), dummy_pos),
dummy_pos), dummy_pos)

fun x -> 2 * (x + 3)
Here, we use dummy_pos as a place-holder value for the source code position of each subterm.

You are allowed to have additional redundant parenthesis in the output string as in

(fun x -> (2 * (x + 3)))
In general, your implementation of the function string_of_term should satisfy the following specification: for all terms t

  equal t (Parser.parse_from_string (string_of_term t)) = true

Here, the predefined function Parser.parse_from_string parses the string representation of a MiniML term and produces its AST representation as a value of type term . The function equal is defined in ast.ml and checks whether two MiniML terms are structurally equal when one ignores the source code position tags. Thus, the above requirement expresses that pretty printing a term represented as an AST and parsing it back to an AST, yields the same AST (modulo source code positions). The file tests.ml contains several unit tests that uses this condition to test your implementation. We encourage you to add more test cases there.

The second function print_term , which you also need to implement, should print the string representation of the given term to the given output channel. E.g. calling

print_term stdout t
will print the term t to standard output.

A straightforward implementation of these two functions is to implement string_of_term by building the string representation of the term recursively from its parts using string concatenation ( ^ ), and then implement print_term using string_of_term and one of the functions provided by the module Printf in the OCaml standard library. However, this is both inefficient and nonidiomatic, and therefore strongly discouraged.

Instead, use OCaml’s Format module to implement the pretty printer by implementing a function: