[jackhill/mal.git] / docs / exercise.md

Once you have a working implementation, you may want to implement
parts of the process inside the MAL language itself. This has no other
purpose than learning the MAL language. Once it exists, a built-in
implementation will always be more efficient than a native
implementation. Also, the functions described in MAL process are
selected for educative purposes, so portability accross
implementations does not matter much.

You may easily check your answers by passing them directly to the
interpreter. They will hide the built-in functions carrying the same
names, and the usual tests (with REGRESS=1) will check them. The
`runtest.py` script provide a convenient command-line parameter to
pass a command like 'load-file' before running the testsuite.

Some solutions are given in the `examples` directory. Feel free to
submit new solutions, or new exercises.


- Implement the following functions with other built-in functions.
  - `nil?`, `true?` and `false?`
  - `empty?`
  - `sequential?`

- Implement `>`, `<=` and `>=` with `<`.

- Implement the following non-recursive functions.
  - `hash-map`
  - `list`
  - `prn`
  - `swap!`

- Implement `map` with a recursion.

- Implement the `do` special as a non-recursive function. The special
  form will hide your implementation, so in order to test it, you will
  need to give it another name and adapt the test accordingly.

- Implement `let*` as a macro that uses `fn*` and recursion.
  The same remark applies.

- Implement `apply` as a macro.

- Implement maps using lists.
  - Recall how maps must be evaluated.
  - In the tests, you may want to replace `{...}` with `(hash-map ...)`.
  - An easy solution relies on lists alterning keys and values, so
    that the `hash-map` is only a list in reverse order so that the
    last definition takes precedence during searches.
  - As a more performant solution will use lists to construct trees,
    and ideally keep them balanced. You will find examples in most
    teaching material about functional languages.
  - Recall that `dissoc` is an optional feature. One you can implement
    dissoc is by assoc'ing a replacement value that is a magic delete
    keyword (e.g.: `__..DELETED..__`) which allows you to shadow
    values in the lower levels of the structure. The hash map
    functions have to detect that and do the right thing. e.g. `(keys
    ...)` might have to keep track of deleted values as it is scanning
    the tree and not add those keys when it finds them further down
    the tree.

- Implement quoting within MAL.

- Implement macros within MAL.
Commit	Line	Data
0544b52f NB	1	Once you have a working implementation, you may want to implement
	2	parts of the process inside the MAL language itself. This has no other
	3	purpose than learning the MAL language. Once it exists, a built-in
	4	implementation will always be more efficient than a native
	5	implementation. Also, the functions described in MAL process are
	6	selected for educative purposes, so portability accross
	7	implementations does not matter much.
	8
	9	You may easily check your answers by passing them directly to the
	10	interpreter. They will hide the built-in functions carrying the same
	11	names, and the usual tests (with REGRESS=1) will check them. The
	12	`runtest.py` script provide a convenient command-line parameter to
	13	pass a command like 'load-file' before running the testsuite.
	14
	15	Some solutions are given in the `examples` directory. Feel free to
	16	submit new solutions, or new exercises.
	17
	18
	19	- Implement the following functions with other built-in functions.
	20	- `nil?`, `true?` and `false?`
	21	- `empty?`
	22	- `sequential?`
	23
	24	- Implement `>`, `<=` and `>=` with `<`.
	25
	26	- Implement the following non-recursive functions.
	27	- `hash-map`
	28	- `list`
	29	- `prn`
	30	- `swap!`
	31
	32	- Implement `map` with a recursion.
	33
	34	- Implement the `do` special as a non-recursive function. The special
	35	form will hide your implementation, so in order to test it, you will
	36	need to give it another name and adapt the test accordingly.
	37
304930e7 NB	38	- Implement `let` as a macro that uses `fn` and recursion.
304930e7 NB	39	The same remark applies.
0544b52f NB	40
	41	- Implement `apply` as a macro.
	42
	43	- Implement maps using lists.
304930e7 NB	44	- Recall how maps must be evaluated.
	45	- In the tests, you may want to replace `{...}` with `(hash-map ...)`.
	46	- An easy solution relies on lists alterning keys and values, so
	47	that the `hash-map` is only a list in reverse order so that the
	48	last definition takes precedence during searches.
	49	- As a more performant solution will use lists to construct trees,
	50	and ideally keep them balanced. You will find examples in most
	51	teaching material about functional languages.
	52	- Recall that `dissoc` is an optional feature. One you can implement
	53	dissoc is by assoc'ing a replacement value that is a magic delete
	54	keyword (e.g.: `__..DELETED..__`) which allows you to shadow
	55	values in the lower levels of the structure. The hash map
	56	functions have to detect that and do the right thing. e.g. `(keys
	57	...)` might have to keep track of deleted values as it is scanning
	58	the tree and not add those keys when it finds them further down
	59	the tree.
0544b52f NB	60
	61	- Implement quoting within MAL.
	62
	63	- Implement macros within MAL.