Tutorial ======== This tutorial consists of a language tour and a set of exercises, in the order of mentioning. Tour ==== Arithmetic operations --------------------- Addition, multiplication, subtraction and division are supported with +, *, - and / respectively. ```console > (+ 1 1) 2 : Int > (* 2 3) 6 : Int > (- 5 4) 1 : Int > (/ 4 2) 2 : Int ``` As addition and multiplication are associative, multiple arguments can be used (even just one, even though that doesn't really make sense): ```console > (+ 1 2 3) 6 : Int > (* 2 3 4 5) 120 : Int ``` Decimals are truncated in division: ```console > (/ 5 2) 2 : Int ``` Increment and decrement operators are supplied by the standard library: ```console > (-- 1) 0 : Int > (++ 1) 2 : Int ``` Booleans -------- Myslip supports booleans and `and`, `or`, `xor` and `not` for their comparisons. ```console > true true : Bool > false false : Bool > (and true true) true : Bool > (or true false) true : Bool > (xor true true) false : Bool > (not true) false : Bool ``` If-expressions are provided by the standard library in the form `(if [condition] [iftrue] [iffalse])`: ```console > (if true 1 0) 1 : Int > (if false 1 0) 0 : Int ``` Integer comparisons ------------------- To generate booleans from integers, some basic and quite self-explanatory operators are supplied. ```console > (> 2 1) true : Bool > (< 1 2) true : Bool > (>= 1 1) true : Bool > (<= 1 1) true : Bool > (= 1 1) true : Bool > (!= 1 1) false : Bool ``` Variables --------- Values can be bound to variables using the let expression. ```console > (let x 1) x saved > x 1 : Int ``` The REPL interprets this as `((let x 1) x)`, which you could also type but would make a more cumbersome REPLing experience (and would make loading definitions from files nigh impossible). Shadowing works as expected: ```console > ((let x 1) (+ x ((let x 2) x) x)) 4 : Int ``` Here, before the definition inside the addition, `x = 1`, and after it it is too, while in the middle term where `x = 2` is defined, `x = 2`. Types ----- Types are written as seen in the return types in the REPL. The base types of myslip are * `Int` for integer * `Bool` for boolean * `Nil` for `()` * `Type` for type literals * `Let` (what'd be the sensible type if not a special one?) * `Quote`, `Vector` and `Sum` for use in data structures. The types used in data structures will be covered later. These can be combined using the arrow type, list type and vector type. `(A -> B)` denotes a function with arguments of type `A` and a return value of type `B`. `(A B C D)` denotes a 4-length list with the respective types at respective positions. Though if it is an actual list not to be interpreted, in most cases a `Quote` will be present in the type: `(Quote (A B C D))`. Note that the length of a list can be any nonnegative integer (within memory constraints), but it needs to be fixed. `(A ...)` denotes a list the length of which is not known and whose each element is of type `A`. If this is in a vector structure, `Vector` is prepended as such: `(Vector (A ...))`. `(Sum A B)` denotes the type of a coproduct, the left type of which is `A` and right type `B`. Generics have limited support in myslip. They are written in uppercase. Functions --------- Functions are written in the form of `(fn [argument list] [argument type list] [return type] [function body])`. They don't have names of themselves, but they can be bound using `let`. The following example features a simple increment function and a function for checking if a integer is between two others. ```console > (let ++ (fn a Int Int (+ a 1))) ++ saved > (++ 1) 2 : Int > (let between (fn (a b c) (Int Int Int) Bool (and (< b c) (> b a)))) between saved > (between 1 2 3) true : Bool > (between 1 0 3) false : Bool ``` Lists ----- Lists in myslip correspond to what is known as tuples in many other programming languages. This difference exists because myslip is a list processor, and not using this underlying construct of the language would be odd. In principle, ```myslip (1 2 3 4 5) ``` is a valid list, but it is evaluated by the interpreter, which assumes that the first term, `1`, is an operator. That's why constructing a list requires the operator `quote`: ```console > quote quote : (T -> (Quote T)) > (quote 1 2 3 4 5) (quote 1 2 3 4 5) : (Quote (Int Int Int Int Int)) ``` In contrast from many other lisp-variants, in myslip sub-expressions are simplified. ```console > (quote (+ 1 1) (+ 2 2)) (quote 2 4) : (Quote (Int Int)) ``` The elements of a list can of course be of different types: ```console > (quote - 0 (quote 1 2)) (quote - 0 (quote 1 2)) : (Quote ((Int Int) -> Int) Int (Quote (Int Int))) ``` Vectors ------- Vectors behave roughly the same as lists, except their length is not specified on type-level, and their elements can be only of one type. ```console > vector vector : ((T ...) -> (Vector (T ...))) > (vector 1 2 3 4) (vector 1 2 3 4) : (Vector (Int ...)) ``` An empty vector is created by passing its type to nil: ```console > (() Int) vector : (Int ...) ``` Two vectors can be concatenated using the `<>`-operator: ```console > (<> (vector 1 2) (vector 3 4)) (vector 1 2 3 4) : (Vector (Int ...)) ``` The standard library provides the function `sum` to calculate the sum of a vector of integers. Through type conversions, this works for lists too. Coproducts ---------- Coproducts ("either-or -type") are instantiated with the `coprod` operator: ```console > (coprod (+ 1 2) Bool) (coprod 3 Bool) : (Sum Int Bool) > (coprod Int +) (coprod Int +) : (Sum Int ((Int ...) -> Int)) ``` They can be destructured with pattern matching as covered in the next section. Pattern matching ---------------- Values can be inspected using pattern matching. For basic lists, the `case`-operator can be used. It's syntax is: ```myslip (case [condition] ([pattern 1] [value 1]) ([pattern 2] [value 2]) ...) ``` Just note that every case expression needs to have one wildcard pattern, to ensure exhaustiveness. Here's a very basic example: ```console > (let x 1) x saved > (case (> x 5) (true (- x 1)) (_ x)) 1 : Int > (case (quote 1 2 3 4 5) ((5 4 3 2 1) 0) ((a b c 4 e) 1) (_ 2)) 1 : Int ``` The list can be destructured into parts. If there is a `..[variable name]` at the end of a pattern, it matches the rest of the list. ```console > (case (quote 1 2 3 4 5) ((h1 h2 ..tail) (+ h1 h2)) ((h ..t) h) (_ 0)) 3 : Int ``` Nesting in pattern matching works fine too. ```console > (case (quote 1 2 (quote 3 4) 5) ((1 2 (quote 3 4) 5) true) (_ false)) true : Bool ``` Pattern matching can be done on vectors too. Just remember that the rest pattern `..r` needs to be at the end of the whole pattern. ```console > (let myvec (vector 1 2 3 4 5)) myvec saved > (case myvec ((head ..tail) head) (_ 0)) 1 : Int ``` Coproducts are destructured with `inl` and `inr`: ```console > (case myprod ((inl x) x) ((inr b) (if b 1 0)) (_ -1)) 2 : Int > (case myprod ((inl 2) true) (_ false)) true : Bool ``` Even if when both an `inl` and `inr` arm are supplied, a wildcard pattern is required as myslip doesn't feature an exhaustiveness checker. That is the tradeoff for having nesting: ```console > (case (quote myprod 1) (((inl 2) _) true) (_ false)) true : Bool ``` (though with a careful rewrite of type checking for pattern matching, at least exhaustiveness for inl/inr arms would be fairly trivial, but that won't happen this summer) General recursion ----------------- General recursion in myslip is achieved through the fixed point operator `fix`. It works the same as in the course materials: it takes a function of type `(T -> T) -> (T -> T)` as an argument and uses that for recursive calls. The factorial function could be implemented as such: ```myslip (let fact (fix (fn fact' (Int -> Int) (Int -> Int) (fn n Int Int (case n (1 1) (_ (* n (fact' (- n 1)))) ) ) ) )) ``` Printing -------- This is quite a useless feature as the repl already echoes all results. But if you fancy, you can print anything using the `print` operator, which is behaviorally equivalent to Nil as long as its argument is valid myslip. For example, with the standard library enabled: ```console > (let x 1) x saved > (print 1) () : Nil > (print sum) (fn vec (Vector (Int ...)) Int (case vec ((h ..t) + h ((fix (fn sum' ((Vector (Int ...)) -> Int) ((Vector (Int ...)) -> Int) (fn vec (Vector (Int ...)) Int (case vec ((h ..t) + h (sum' t)) (_ 0))))) t)) (_ 0))) () : Nil ``` Exercises ========= These exercises are meant to make you familiar with the language. The solutions can be found in the `solutions` folder under the project root. Exercise 1: Fibonacci sequence ------------------------------ Write a function that calculates the n:th fibonacci number, when n is given as the sole argument. This should make you familiar with function definitions and fixed point recursion. Example of desired behaviour: ```console > (fibonacci 1) 0 : Int > (let n 10) n saved > (fibonacci n) 34 : Int ```