path: root/TUTORIAL.md

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
```

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!


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: 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 2: 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 3: Generic functions – the identity
--------------------------------------------

Write the identity function for any type.

This should make you familiar with typing function
definitions that contain generics.


Exercise 4: Map left / right (integers)
---------------------------------------

Write functions `map-left` and `map-right` that take a
coproduct and a function and map the corresponding side of
the given coproduct using the given function.

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.