docs/exercises.md

   1 # Exercises to learn MAL
   2
   3 The process introduces LISP by describing the internals of selected
   4 low-level constructs. As a complementary and more traditional
   5 approach, you may want to solve the following exercises in the MAL
   6 language itself, using any of the existing implementations.
   7
   8 You are encouraged to use the shortcuts defined in the step files
   9 (`not`...) and `the `lib/` subdirectory (`reduce`...) whenever you
  10 find that they increase the readability.
  11
  12 The difficulty is progressive in each section, but they focus on
  13 related topics and it is recommended to start them in parallel.
  14
  15 Some solutions are given in the `examples` directory. Feel free to
  16 submit new solutions, or new exercises.
  17
  18 ## Replace parts of the process with native constructs
  19
  20 Once you have a working implementation, you may want to implement
  21 parts of the process inside the MAL language itself. This has no other
  22 purpose than learning the MAL language. Once it exists, a built-in
  23 implementation will always be more efficient than a native
  24 implementation. Also, the functions described in MAL process are
  25 selected for educative purposes, so portability accross
  26 implementations does not matter much.
  27
  28 You may easily check your answers by passing them directly to the
  29 interpreter. They will hide the built-in functions carrying the same
  30 names, and the usual tests will check them.
  31 ```
  32 make REGRESS=1 TEST_OPTS='--hard --pre-eval=\(load-file\ \"../answer.mal\"\)' test^IMPL^stepA
  33 ```
  34
  35 - Implement `nil?`, `true?`, `false?`, `empty?` and `sequential` with
  36   another built-in function.
  37
  38 - Implement `>`, `<=` and `>=` with `<`.
  39
  40 - Implement `list`, `vec`, `prn`, `hash-map` and `swap!` as non-recursive
  41   functions.
  42
  43 - Implement `count`, `nth`, `map`, `concat` and `conj` with the empty
  44   constructor `()`, `empty?`, `cons`, `first` and `rest`.
  45
  46   You may use `or` to make the definition of `nth` a bit less ugly,
  47   but avoid `cond` because its definition refers to `nth`.
  48
  49   Let `count` and `nth` benefit from tail call optimization.
  50
  51   Try to replace explicit recursions with calls to `reduce` and `foldr`.
  52
  53   Once you have tested your solution, you should comment at least
  54   `nth`.  Many implementations, for example `foldr` in `core.mal`,
  55   rely on an efficient `nth` built-in function.
  56
  57 - Implement the `do` special as a non-recursive function. The special
  58   form will hide your implementation, so in order to test it, you will
  59   need to give it another name and adapt the test accordingly.
  60
  61 - Implement quoting with macros.
  62   The same remark applies.
  63
  64 - Implement most of `let*` as a macro that uses `fn*` and recursion.
  65   The same remark applies.
  66   A macro is necessary because a function would attempt to evaluate
  67   the first argument.
  68
  69   Once your answer passes most tests and you understand which part is
  70   tricky, you should search for black magic recipes on the web. Few of
  71   us mortals are known to have invented a full solution on their own.
  72
  73 - Implement `apply`.
  74
  75 - Implement maps using lists.
  76   - Recall how maps must be evaluated.
  77   - In the tests, you may want to replace `{...}` with `(hash-map ...)`.
  78   - An easy solution relies on lists alterning keys and values, so
  79     that the `hash-map` is only a list in reverse order so that the
  80     last definition takes precedence during searches.
  81   - As a more performant solution will use lists to construct trees,
  82     and ideally keep them balanced. You will find examples in most
  83     teaching material about functional languages.
  84   - Recall that `dissoc` is an optional feature. One you can implement
  85     dissoc is by assoc'ing a replacement value that is a magic delete
  86     keyword (e.g.: `__..DELETED..__`) which allows you to shadow
  87     values in the lower levels of the structure. The hash map
  88     functions have to detect that and do the right thing. e.g. `(keys
  89     ...)` might have to keep track of deleted values as it is scanning
  90     the tree and not add those keys when it finds them further down
  91     the tree.
  92
  93 - Implement macros within MAL.
  94
  95 ## More folds
  96
  97 - Compute the sum of a sequence of numbers.
  98 - Compute the product of a sequence of numbers.
  99
 100 - Compute the logical conjunction ("and") and disjunction ("or") of a
 101   sequence of MAL values interpreted as boolean values.  For example,
 102   `(conjunction [true 1 0 "" "a" nil true {}])`
 103   should evaluate to `false` or `nil` because of the `nil` element.
 104
 105   Why are folds not the best solution here, in terms of average
 106   performances?
 107
 108 - Does "-2-3-4" translate to `(reduce - 0 [2 3 4])`?
 109
 110 - Suggest better solutions for
 111   `(reduce str "" xs)` and
 112   `(reduce concat [] xs)`.
 113
 114 - What does `(reduce (fn* [acc _] acc) xs)` nil answer?
 115
 116 - The answer is `(fn* [xs] (reduce (fn* [_ x] x) nil xs))`.
 117   What was the question?
 118
 119 - What is the intent of
 120  `(reduce (fn* [acc x] (if (< acc x) x acc)) 0 xs)`?
 121
 122   Why is it the wrong answer?
 123
 124 - Though `(sum (map count xs))` or `(count (apply concat xs))` can be
 125   considered more readable, implement the same effect with a single loop.
 126 - Compute the maximal length in a list of lists.
 127
 128 - How would you name
 129   `(fn* [& fs] (foldr (fn* [f acc] (fn* [x] (f (acc x)))) identity fs))`?