Lab 8: Moses

Overview

In this week’s assignment, you will implement a type-checker for a Haskell-like language.

The language is called Moses, and the purpose of this lab is to become familiar with Moses as a programming language: its features, its type system, and how to write and run programs. Taking about an hour to become familiar with Moses as a programmer will help you implement part of the language itself!

Materials

Use the assignment workflow and the link provided on Piazza to get access to this week’s files.

Do this lab on knuth, which has a working version of Moses installed.

Part 1: Simple data types and operations

In this part of the lab, we will look at some of the basic data types in Moses. You can experiment with Moses by running the following command on knuth:

        /cs/cs131/bin/Moses -i

You can quit the interactive interpreter at any time by typing quit.

This command will give you an interactive Moses prompt, where you can type in some example expressions.

Numeric types

Moses has ints and reals, and operations on those types. Here are some example expressions. Try typing these (and all the subsequent expressions) into the interactive prompt, to view the output. Note anything interesting about the types of these values and operations.

    42
    42.0
    2 + 2
    2.0 + 2.0
    2 + 2.0

Strings

Moses also has strings and string concatenation (++).

    "hello world"
    "hello" ++ " world"

Booleans

Moses has boolean values (True and False) and operations.

    True
    False
    2 == 2
    "a" == "b"
    3 > 4
    2 == 2.0

Lists

Moses has lists, list-concatenation (@), and list-append (:).

    [1, 2, 3]
    1 : [2,3]
    [1, 2, 3] @ [4, 5, 6]
    [1, 2.0, 3]
    []
    [1, 2.0, "three"]

Tuples

Moses has tuples. Just like in Haskell, the type of a tuple depends on the types and number of elements in the tuple.

    (1,2,3)
    (1, 2.0, "three")

Lambda expressions and function calls

Moses has lambda expressions with one variable. We must declare the type of the variable.

    (\x :: INT -> x + 1)
    (\x :: INT -> x + 1) 0

let expressions

Moses has simple let expressions:

    let x = 1 in x + x
    let f = (\x :: INT -> x + 1) in f 1

Other expressions and features

Moses has lots of other expressions, include if, case, and pattern-matching. We will explore those later in the lab.

Type errors

Try these expressions that generate type errors:

    1 + []
    [1,2,3] @ 4
    5 ++ 6
    False < True
    [] == []
    error "Error message"

Laziness

    let x = error "Oops" in "Blah blah blah"
    let x = 1 + error "Oops" in "Blah blah blah"
    let f = error "Oops" in let x = f 10 in "Blah blah blah"

Now quit the interactive mode by typing quit.

Part 2: Larger Programs

The provided code contains the following programs, which use more features of Moses.

  • fact.mose — a factorial function
  • fact2.mose — a factorial function again
  • length.mose — calculates the length of a list
  • sum.mose — sums up a list
  • posneg.mose — partition a list

For each program, look at the code (including reading the comments under the code about how Moses is different from Haskell) and run the code (/cs/cs131/bin/Moses fact.mose, etc.).

Part 3: Subtyping

As you’ve already seen, Moses supports subtyping. You can confirm this by using an if statement such as

    if True then 1 else 1.3

or by making a list, like:

    [1, 2.0]

Moses has two special types in its subtype system: ANY and NONE. Every type can be turned into an ANY (a bit like Object in Java). Unlike Java, there is no cast operation to turn an ANY back into any other type, so once something has become an ANY, we know nothing about what it is. Once something is as general as an ANY it is kind-of useless. The NONE type is a subtype of all types; whatever you need, you can always use a NONE. If you think of types as sets of allowed values, NONE has no values at all!. Thus all its amazingness is because everything is vacuously true for a member of the empty set. NONEs are thus amazing, magical, and entirely mythical. If you ever actually expect to see one, you won’t. A list of NONEs, for example will turn out to be the empty list. The error function has type STRING -> NONE because it crashes the program, never needing to deliver on its promise of returning a NONE value.

In your text editor, open each of the example files subtype1.mose to subtype13.mose in turn. In each case, write a comment in the file before you run it, saying what you think the type of the expression will be. Then run it with Moses and see if you’re correct. Add additional comments to indicate that you are correct, or if you’re wrong, say the correct answer why. (You can do experiments with /cs/cs131/bin/Moses -i to help figure things out if the results weren’t what you expected.) If you’re not sure, ask us!

Part 4: Writing a New Program

Write a new simple program in Moses in sample.mose. Suggestions are provided (basically don’t write something utterly trivial nor too ambitious). It should be about five to ten lines of code and do something that ought to be easy to understand and quick to write.

Important: Moses has incredibly limited pattern matching facilities. It can break apart a tuple in a let expression (and only there, and no nesting) and it has a case expression, which only works on lists, and only allows you to specify two cases, empty list and non-empty list (breaking up into head and tail), in that order. You cannot do any kind of more-sophisticated pattern matching. Although it might seem limiting when you are writing code, you will be happier about it when writing the type checker.