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 ``` Note though that they are not short-circuiting as their arguments are evaluated before passing to the operator as with all functions defined in myslip. Implementing a short-circuiting version would be possible if an 'unquoting' operator was added. If you wish short-circuiting behavior, use case directly instead. 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 ```myslip (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 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 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 of lists 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 > (let myprod (coprod 2 Bool)) myprod saved > (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 ``` Because you might want to use print several times in consequence, but putting them in a list makes the type checker look at you weird, the standard library offers the convenience function `discard`, which takes anything as arguments and returns nil. Here's an example that shows why you might want to use discard: ```console > ((print 1) (print 2)) Type error: invalid operator: '(print 1)' expected: '(_ -> _)' found: 'Nil' > (quote (print 1) (print 2)) 1 2 (quote () ()) : (Quote (Nil Nil)) ``` As you can see, the return type of the latter try at using print twice looks horrible. ```console > (discard (print 1) (print 2)) 1 2 () : Nil ``` That looks better! Loops ===== Loops are quite worthless in a functional language, but I might get points for them. The standard library provides the functions `repeat` and `map-i->i`. The former one has the syntax `(repeat [operation] [number of times])`, which quite intuitively repeats the given operation the given number of times. The operation should be a function that takes an integer as an argument and returns Nil, so this function is useless for anything but printing. ```console > (repeat (fn x Int Nil (print x)) 10) 1 2 3 4 5 6 7 8 9 10 () : Nil ``` The latter has the syntax `(map-i->i [vector] [operation])` where only vectors of integers and operations from integers to integers are supported. More general mapping functions would require more sophisticated generics. The standard library also provides a similar function for filtering on vectors of integers. 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: Collatz conjecture step ----------------------------------- Given an integer `x`, compute the next step of the sequence famous from the Collatz conjecture. In other words, if `x` is even, return half of `x`, and if `x` is odd, return `3x + 1`. This should make you familiar with arithmetic and conditional logic. Exercise 2: Running code ------------------------ Write a function `cond-add-inv` in a file called `a.slip`. It should take an integer and a boolean argument, and if the boolean argument is true, return the additive inverse of the given integer, otherwise return the given integer without modification. Then, in a file `b.slip`, use the function `cond-add-inv` to first print the inverse of 7 and then print 7 without taking its inverse. This should make you familiar with integers, conditional logic and using the `myslip` program to link together your program from files. As a bonus, you can use the if-statement provided by the standard library, so now you know it works too when linking together multiple files. As a superbonus"challenge", you may want to try out the `--babysteps` feature (see `myslip --help`). Exercise 3: 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 ``` Exercise 4: Generic functions – the identity -------------------------------------------- Write the identity function for any type. This should make you familiar with typing function definitions that contain generics. Exercise 5: Left / right or --------------------------- Write functions `left-or` and `right-or` that take a coproduct and a default value of the type of the corresponding hand of the coproduct, and if the coproduct is of the left type, returns its value, otherwise returns the default value. Note: the solution is not in the same directory as the rest, but you can find implementations for these in the standard library. This exercise will train your abilities to use generics more than the last one. You will get familiar with coproducts.