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 | 54 | |
42d31a20 NB |
55 | Once you have tested your solution, you should comment at least |
56 | `nth`. Many implementations, for example `foldr` in `core.mal`, | |
57 | rely on an efficient `nth` built-in function. | |
58 | ||
0544b52f NB |
59 | - Implement the `do` special as a non-recursive function. The special |
60 | form will hide your implementation, so in order to test it, you will | |
61 | need to give it another name and adapt the test accordingly. | |
62 | ||
304930e7 NB |
63 | - Implement `let*` as a macro that uses `fn*` and recursion. |
64 | The same remark applies. | |
9678065e NB |
65 | A macro is necessary because a function would attempt to evaluate |
66 | the first argument. | |
0544b52f | 67 | |
1ca3ee3d | 68 | - Implement `apply`. |
0544b52f NB |
69 | |
70 | - Implement maps using lists. | |
304930e7 NB |
71 | - Recall how maps must be evaluated. |
72 | - In the tests, you may want to replace `{...}` with `(hash-map ...)`. | |
73 | - An easy solution relies on lists alterning keys and values, so | |
74 | that the `hash-map` is only a list in reverse order so that the | |
75 | last definition takes precedence during searches. | |
76 | - As a more performant solution will use lists to construct trees, | |
77 | and ideally keep them balanced. You will find examples in most | |
78 | teaching material about functional languages. | |
79 | - Recall that `dissoc` is an optional feature. One you can implement | |
80 | dissoc is by assoc'ing a replacement value that is a magic delete | |
81 | keyword (e.g.: `__..DELETED..__`) which allows you to shadow | |
82 | values in the lower levels of the structure. The hash map | |
83 | functions have to detect that and do the right thing. e.g. `(keys | |
84 | ...)` might have to keep track of deleted values as it is scanning | |
85 | the tree and not add those keys when it finds them further down | |
86 | the tree. | |
0544b52f NB |
87 | |
88 | - Implement quoting within MAL. | |
89 | ||
90 | - Implement macros within MAL. | |
9678065e NB |
91 | |
92 | ## More folds | |
93 | ||
94 | - Compute the sum of a sequence of numbers. | |
95 | - Compute the product of a sequence of numbers. | |
96 | ||
97 | - Compute the logical conjunction ("and") and disjunction ("or") of a | |
98 | sequence of MAL values interpreted as boolean values. For example, | |
99 | `(conjunction [true 1 0 "" "a" nil true {}])` | |
100 | should evaluate to `false` or `nil` because of the `nil` element. | |
101 | ||
102 | Why are folds not the best solution here, in terms of average | |
103 | performances? | |
104 | ||
105 | - Does "-2-3-4" translate to `(reduce - 0 [2 3 4])`? | |
106 | ||
107 | - Suggest better solutions for | |
108 | `(reduce str "" xs)` and | |
109 | `(reduce concat [] xs)`. | |
110 | ||
111 | - What does `(reduce (fn* [acc _] acc) xs)` nil answer? | |
112 | ||
113 | - The answer is `(fn* [xs] (reduce (fn* [_ x] x) nil xs))`. | |
114 | What was the question? | |
115 | ||
116 | - What is the intent of | |
117 | `(reduce (fn* [acc x] (if (< acc x) x acc)) 0 xs)`? | |
118 | ||
119 | Why is it the wrong answer? | |
120 | ||
121 | - Though `(sum (map count xs))` or `(count (apply concat xs))` can be | |
122 | considered more readable, implement the same effect with a single loop. | |
123 | - Compute the maximal length in a list of lists. | |
124 | ||
125 | - How would you name | |
126 | `(fn* [& fs] (foldr (fn* [f acc] (fn* [x] (f (acc x)))) identity fs))`? |