Updates

• Feb 14 - The Project 1 deadline is extended to Friday, Feb 17. Please contact me if this new due date poses any issues for you.
• Feb 10 - p1 tests updated to keep the units specified in the expression, rather than implicitly converting to SI units after computation. Feb 10 - The public tests have been updated slightly to fix a buggy test.
• Feb 9 - Fixed main.ml to use <> on lines 41 and 45 instead of !=.
• Feb 8 - Some public tests are now available.
• Feb 8 - Changed grammar to remove * and / from units, as discussed in class.

Introduction

In this project, you will develop a unit calculator that implements functionality similar to the unit conversions available in Google's calculator. For example, if your calculator is asked to compute 1 pound in grams it should return 453.59237 grams. As another example, if your calculator you is asked to compute 60 miles hour^-1 in m s^-1, it should return 26.8224 m s^{-1}.

To get you started, we've provided a code skeleton for your unit calculator. After unpacking this directory, make should build an executable calc intended to be used as follows:

• calc -config config-file input-file loads the unit configuration (see below) specified by config-file and then reads each expression from input-file, evaluating it and printing the result to standard out.
• calc -config config-file -parse-config-only loads the unit configuration file and prints it to standard out
• calc -parse-only input-file reads each expression from input-file, printing it (but not evaluating it) to standard out.

Input language

The input to your calculator will be a list of expressions es given by the following grammar:

es	::=	ε	Empty list
	|	e ;; es	List of expressions
e	::=	fp	Dimensionless quantity
	|	fp u	Dimensional quantity
	|	e + e	Addition
	|	e - e	Subtraction
	|	e * e	Multiplication
	|	e / e	Division
	|	e in u	Unit conversion
	|	( e )	Grouping
u	::=	ft | lbs | m | s | ...	Base units
	|	u ^ n	Unit Exponentiation
	|	u u	Unit multiplication
	|	( u )	Grouping

Here fp is a floating point number (whose syntax follows the OCaml convention, except the decimal point should not be required) and n is an integer (which may be negative, and may contain leading zeroes). The expression language is straightforward: the base quantities that can be calculated with may either be dimensionless or have dimensions. Standard arithmetic operations are permitted, along with a special form e in u, which converts the expression e from its current units into the units specified by u. Note that this conversion must be sensible; for example, 3 miles in lbs is an error.

Units u can either be base units such as ft, lbs, etc, or can be hybrid units composed from base units, e.g., s, m^2 s^-1, ft lbs, etc. Base units are sequences of upper or lower-case letters. Notice that multiplication of units is indicated by juxtaposition, and division by negative exponentiation; this avoids some annoying parsing conflicts.

Note that the input file is a list of expressions, each of which must be terminated by ;;.

Part 1: Parsing

The first step in building your calculator is to develop a parser for the input language. Your parser will accept strings produced from e in the grammar above, and from them should produce an abstract syntax tree (AST) in the form of an instance of the expr type, defined as:

type unit_t = (string * int) list

type value = float * unit_t

type expr =
  | Val of value
  | Plus of expr * expr
  | Minus of expr * expr
  | Mult of expr * expr
  | Div of expr * expr
  | In of expr * unit_t

Here units are represented by unit_t, which is a (possibly empty) list of dimensions and their exponents (either positive or negative). For example, s is represented by ["s",1], m^2 s^-1 is represented by ["m",2; "s",-1], and ft lbs is represented by ["ft",1; "lbs",1]. Quantities are paired with a unit. For example, 42 is represented as Val (42, []), and 3 ft s^-2 is represented as Val (3, ["ft", 1; "s", -2]).

Your parser should obey the following conventions:

• Your parser should allow the dot to be left out of a flating point numbers. E.g., 2 is a valid floating point number for this project.
• +, -, * and / are left associative.
• ^ binds most tightly, then* and /, which have equal precedence, and then + and -, which have equal precedence. in has the lowest precedence.
• Units bind more tightly than any arithmetic operations. Thus, for example, 4 + 3 s means "add the dimensionless number 4 to 3 seconds" (which will be an error under our semantics).
• Your parser should allow arbitrary unit strings, e.g., 3 smoots is valid, even if we don't have conversions for unit smoots.
• Your parser should not check for any semantic errors. For example, it should produce an AST for 4 + 3 s, even though attempting to evaluate that expression will yield an error.
• Your parser should group together unit factors with exactly the same base unit string, but it should not do any further processing on units. For example, s s should become ["s"; 2], and m s m^{-1} should become ["s"; 1]. (Note here we needed to remove m from the list entirely, rather than leave it in with exponent 0.) The order of base units in unit_t is arbitrary. In this stage, non-sensical units such as m ft and g kg are allowed, and should yield ASTs.
• The input file consists of multiple expressions, each one of which should be terminated with ;;

You must implement your parser using ocamllex and ocamlyacc. Below, we've provided you with skeleton code to add your parser to; you should modify the files lexer.mll and parser.mly for this part of the project.

Part 2: Unit configuration files

In order to perform unit conversions, your calculator will need to know some basic ratios among units. Rather than hard-code this into your calculator, we'll use a configuration file instead. For example, the following configuration file gives conversions for feet, pounts, and kilgrams in terms of meters, grams, and kilgrams, respectively:

{
 "ft": [0.3048, "m"],
 "lb": [453.59237, "g"],
 "kg": [1000, "g"],
 "acres": [4046.85642, "m^2"],
 "newton": [1000, "m g s^-2"]
}

The first line says that 1 ft is equal to 0.3048 m, the second and third lines give conversions for pounds and kilgrams, the fourth line gives a conversion for acres in terms of square meters, and the last line converts newtons (force) in terms of base units. We will refer to units defined in this way as derived units.

Configuration files are in JSON format; you can use Yojson to parse these files. The Makefile supplied with the project includes a commented-out line to load the Yojson package; you can uncomment that when you're ready to start on this part of the project. A valid configuration file consists of a single object representing a mapping from unit abbreviations to an array of [ratio, target-unit], where target-unit is produced by u from the grammar from part 1.

To keep things a bit simpler, target units for this project will always be the SI units for meters, grams, or seconds.

For this part of the project, you should write a function parse_config : string -> config -> unit where config is defined as

type config = (string, float * unit_t) Hashtbl.t

This function takes the name of a configuration file, a configuration hash table, and parses the file, adding the configuration definitions to the hash table. You may assume the hash table is empty when your parsing function is called. Your configuration file parser should raise an exception (any exception) if any of the following hold:

• The input string is ill-formed, ie., it does not have the format described above.
• A unit_t instance contains any units except "m", "g", and "s".
• The same derived unit string is defined multiple times in the file (even if the definition is the same).
• Any ratio is negative.

Part 3: Semantics

Finally, write a function eval : config -> expr -> value that calculates the value of an expession under the given configuration. Your evaluation function should work as follows:

• Any quantities that are added or subtracted must match unit types exactly.
• When multiplying or dividing quantities, derived units with the same base units must match exactly, but derived units with different base units may be combined. For example,

  1 ft * 1 lb	allowed
  1 ft * 1 m	not allowed
  (2 ft^2)/(1 ft)	allowed
  (2 ft^2)/(2 acres)	not allowed
  (2 m^2)/(2 acres)	not allowed
  (2 acres)/(4 acres)	allowed
  (1 ft)*(2 acres)	not allowed
  (2 acres)/(1 m)	not allowed

  To put it another way, when combining two expressions with multiplication or division, the mass units must match (or be absent in one or the other), and similarly for the length and time units.
• Unit conversions with in must make sense, i.e., they must map into and out of the same base units. For example, 1 ft in m is valid, but 1 ft in s is not.
• Any units referred to in the expression must be defined in the configuration file, except the base units g, m, and s, which always exist.
• Your function should raise an exception (any exception) if the expression cannot be evaluated because it violates any of the above assumptions.

What to turn in

Put all your code in the code skeleton we have supplied, and upload your solution to the submit server. Here are some public tests for you to try out. Note that almost all testing will be with secret tests.

Important note: You should implement your project in ocaml-3.12.1. To access this version of ocaml on the linuxlab, you need to add /usr/local/ocaml-3.12.1/bin to the front of your path. To check that you have the right version, just run ocaml from the command line and it will print the version number.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.