Commit | Line | Data |
---|---|---|
9678065e NB |
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 ``core.mal`` (`reduce`...) whenever you find that they | |
10 | 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 | ||
0544b52f NB |
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 (with REGRESS=1) will check them. The | |
31 | `runtest.py` script provide a convenient command-line parameter to | |
32 | pass a command like 'load-file' before running the testsuite. | |
9678065e NB |
33 | ``` |
34 | make REGRESS=1 TEST_OPTS='--hard --pre-eval=\(load-file\ \"../answer.mal\"\)' test^IMPL^stepA | |
35 | ``` | |
0544b52f | 36 | |
9678065e NB |
37 | - Implement `nil?`, `true?`, `false?`, `empty?` and `sequential` with |
38 | another built-in function. | |
0544b52f NB |
39 | |
40 | - Implement `>`, `<=` and `>=` with `<`. | |
41 | ||
1ca3ee3d NB |
42 | - Implement `hash-map`, `list`, `prn` and `swap!` as non-recursive |
43 | functions. | |
44 | ||
45 | - Implement `count`, `nth`, `map`, `concat` and `conj` with the empty | |
46 | constructor `()`, `empty?`, `cons`, `first` and `rest`. | |
47 | ||
9678065e NB |
48 | You may use `or` to make the definition of `nth` a bit less ugly, |
49 | but avoid `cond` because its definition refers to `nth`. | |
50 | ||
1ca3ee3d | 51 | Let `count` and `nth` benefit from tail call optimization. |
0544b52f | 52 | |
1ca3ee3d | 53 | Try to replace explicit recursions with calls to `reduce` and `foldr`. |
0544b52f NB |
54 | |
55 | - Implement the `do` special as a non-recursive function. The special | |
56 | form will hide your implementation, so in order to test it, you will | |
57 | need to give it another name and adapt the test accordingly. | |
58 | ||
304930e7 NB |
59 | - Implement `let*` as a macro that uses `fn*` and recursion. |
60 | The same remark applies. | |
9678065e NB |
61 | A macro is necessary because a function would attempt to evaluate |
62 | the first argument. | |
0544b52f | 63 | |
1ca3ee3d | 64 | - Implement `apply`. |
0544b52f NB |
65 | |
66 | - Implement maps using lists. | |
304930e7 NB |
67 | - Recall how maps must be evaluated. |
68 | - In the tests, you may want to replace `{...}` with `(hash-map ...)`. | |
69 | - An easy solution relies on lists alterning keys and values, so | |
70 | that the `hash-map` is only a list in reverse order so that the | |
71 | last definition takes precedence during searches. | |
72 | - As a more performant solution will use lists to construct trees, | |
73 | and ideally keep them balanced. You will find examples in most | |
74 | teaching material about functional languages. | |
75 | - Recall that `dissoc` is an optional feature. One you can implement | |
76 | dissoc is by assoc'ing a replacement value that is a magic delete | |
77 | keyword (e.g.: `__..DELETED..__`) which allows you to shadow | |
78 | values in the lower levels of the structure. The hash map | |
79 | functions have to detect that and do the right thing. e.g. `(keys | |
80 | ...)` might have to keep track of deleted values as it is scanning | |
81 | the tree and not add those keys when it finds them further down | |
82 | the tree. | |
0544b52f NB |
83 | |
84 | - Implement quoting within MAL. | |
85 | ||
86 | - Implement macros within MAL. | |
9678065e NB |
87 | |
88 | ## More folds | |
89 | ||
90 | - Compute the sum of a sequence of numbers. | |
91 | - Compute the product of a sequence of numbers. | |
92 | ||
93 | - Compute the logical conjunction ("and") and disjunction ("or") of a | |
94 | sequence of MAL values interpreted as boolean values. For example, | |
95 | `(conjunction [true 1 0 "" "a" nil true {}])` | |
96 | should evaluate to `false` or `nil` because of the `nil` element. | |
97 | ||
98 | Why are folds not the best solution here, in terms of average | |
99 | performances? | |
100 | ||
101 | - Does "-2-3-4" translate to `(reduce - 0 [2 3 4])`? | |
102 | ||
103 | - Suggest better solutions for | |
104 | `(reduce str "" xs)` and | |
105 | `(reduce concat [] xs)`. | |
106 | ||
107 | - What does `(reduce (fn* [acc _] acc) xs)` nil answer? | |
108 | ||
109 | - The answer is `(fn* [xs] (reduce (fn* [_ x] x) nil xs))`. | |
110 | What was the question? | |
111 | ||
112 | - What is the intent of | |
113 | `(reduce (fn* [acc x] (if (< acc x) x acc)) 0 xs)`? | |
114 | ||
115 | Why is it the wrong answer? | |
116 | ||
117 | - Though `(sum (map count xs))` or `(count (apply concat xs))` can be | |
118 | considered more readable, implement the same effect with a single loop. | |
119 | - Compute the maximal length in a list of lists. | |
120 | ||
121 | - How would you name | |
122 | `(fn* [& fs] (foldr (fn* [f acc] (fn* [x] (f (acc x)))) identity fs))`? |