docs/step_notes.txt

   1 Step Notes:
   2
   3 - step0_repl
   4     - prompt, input, READ, EVAL, PRINT, output
   5     - readline module
   6         - display prompt, read line of input
   7     - Details:
   8         - get your language compiler/interpreter running
   9         - create step0_repl.EXT
  10             - loop that reads input, calls rep, writes output, exits
  11               on EOF/Ctrl-D
  12             - rep calls PRINT(EVAL(READ(str)))
  13             - READ, EVAL, PRINT just return input parameter
  14         - modify toplevel Makefile
  15             - add language (directory name) to IMPLS
  16             - add <lang>_STEP_TO_PROG entry
  17             - add <lang>_RUNSTEP entry
  18         - for a compiled language, add <lang>/Makefile
  19             - targets: all, step*, stats, stats-lisp,
  20
  21 - use native eval in EVAL if available
  22
  23 - libedit/GNU readline:
  24     - use existing lib, wrap shell call or implement
  25     - load history file on first call
  26     - add non-blank lines to history
  27     - append to history file
  28
  29 - step1_read_print
  30     - types module:
  31         - add boxed types if no language equivalent:
  32             - nil, true, false, symbol, integer, string, list
  33         - error types if necessary
  34     - reader module:
  35         - stateful reader object
  36             - alternative: mutate token list
  37         - tokenize (if regex available)
  38             - standard regex pattern: "/[\s,]*(~@|[\[\]{}()'`~^@]|\"(?:\\.|[^\\\"])*\"|;.*|[^\s\[\]{}('\"`,;)]*)/"
  39         - read_str
  40             - read_form(new Reader(tokenize(str)))
  41         - read_form
  42             - detect errors
  43             - call read_list or read_atom
  44         - read_list
  45             - read_form until ')'
  46             - return array (boxed)
  47         - read_atom (not atom type)
  48             - return scalar boxed type:
  49                 - nil, true, false, symbol, integer, string
  50             - skip unquoting
  51     - printer module:
  52         - _pr_str:
  53             - stringify boxed types to their Mal representations
  54             - list/array is recursive
  55             - skip quoting
  56     - repl loop
  57         - catch errors, print them and continue
  58         - impls without exception handling will need to have a global
  59           variable with checks for it at the beginning of critical
  60           code sections
  61     - Details:
  62         - copy step0_repl.EXT to step1_read_print.EXT
  63             - modify Makefile if compiled
  64             - call reader.read_str from READ
  65             - pass through type returned from read_str through
  66               READ/EVAL/PRINT
  67         - create reader.EXT
  68             - if regex support (much easier) then tokenize with this:
  69                 /[\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"|;.*|[^\s\[\]{}('"`,;)]*)/g
  70             - add read_str:
  71                 - call tokenize
  72                 - handle blank line (exceptions, return code, global
  73                   depending on lang features)
  74             - read_str -> read_form -> {read_list, read_atom}
  75                 - mutable reader thing
  76         - create printer.EXT
  77             - _pr_str function which basically reverses read_str and
  78               returns a string representation
  79         - run `make test^EXT^step1`. Much of the basics should pass up
  80           to vectors
  81         - implement read_hash_map (can refactor read_list)
  82         - import read_vector
  83             - probably want to define types for List and Vector in
  84               types.EXT that extend or wrap native arrays
  85         - run `make test^EXT^step1`. All mandatory should pass
  86
  87 - comments
  88
  89 - vectors
  90     - Basically: two array types that retain their boxed types, can be
  91       challenging depending on the language (e.g. JS, PHP: no clean
  92       way to derive new array types).
  93     - types module:
  94         - add vector boxed type
  95             - derived from array if possible
  96         - pr_str:
  97             - vector is recursive
  98         - sequential?
  99     - reader module:
 100         - read_vector:
 101             - re-use read_list but with different constructor, delims
 102
 103 - hash-maps
 104     - reader module:
 105         - re-use read_list function and apply that using hash-map
 106           constructor
 107     - types module:
 108         - pr_str addition
 109         - hash-map, map?, assoc, dissoc, get, contains?, keys,
 110           vals (probably assoc! and dissoc! for internal)
 111     - eval_map: eval the keys and values of hash_maps
 112     - EVAL:
 113         - if hash_map, call eval_map on it
 114
 115 - step2_eval
 116     - types module:
 117         - symbol?, list? (if no simple idiomatic impl type check)
 118         - first, rest, nth on list
 119     - eval_ast:
 120         - if symbol, return value of looking up in env
 121         - if list, eval each item, return new list
 122         - otherwise, just return unchanged ast
 123     - EVAL/apply:
 124         - if not a list, call eval_ast
 125         - otherwise, apply first item to eval_ast of (rest ast)
 126     - repl_env as simple one level hash map (assoc. array)
 127         - store function as hash_map value
 128     - Details:
 129         - copy step1_read_print.EXT to step2_eval.EXT
 130         - create repl_env hash_map) with +, -, *, /
 131             - store anon func as values if possible
 132         - types.EXT
 133             - implement symbol? (symbol_Q) and list? (list_Q)
 134         - add env param to EVAL and add to rep EVAL call
 135         - EVAL
 136             - if not list call eval_ast
 137             - otherwise eval_ast, and call first arg with rest
 138         - eval_ast
 139             - if symbol?, lookup in env
 140             - if List, EVAL each and return eval's list
 141             - otherwise, return original
 142         - optional: handle vector and hash-map in eval_ast
 143
 144 - vectors
 145     - eval each item, return new vector
 146
 147 - hash-maps
 148     - eval each value, return new hash_map
 149
 150 - step3_env
 151     - types module:
 152         - may need function type if HashMap is strongly typed (e.g. Java)
 153     - env type:
 154         - find, set, get (no binds/exprs in constructor yet)
 155     - EVAL/apply:
 156         - def! - mutate current environment
 157         - let* - create new environment with bindings
 158     - Details:
 159         - cp step2_eval.EXT to step3_env.EXT
 160         - add env.EXT if lang support file dep cycles, otherwise, add
 161           to types.EXT
 162             - Env type
 163             - find, get, set methods/functions
 164         - use Env type instead of map/assoc. array
 165         - eval_ast: use method for lookup
 166         - EVAL:
 167             - switch on first symbol
 168                 - def!
 169                     - set env[a1] to EVAL(a2, env)
 170                 - let*
 171                     - loop through let building up let_env
 172                     - EVAL(a2, let_env)
 173                 - move apply to default
 174
 175 - step4_if_fn_do
 176     - types module:
 177         - function type if no closures in impl language
 178         - _equal_Q function (recursive)
 179     - reader module
 180         - string unescaping
 181     - printer module
 182         - print_readably option for pr_str
 183         - add function printing to pr_str
 184         - string escaping in pr_str
 185     - core module (export via core_ns):
 186         - export equal_Q from types as =
 187         - move arith operations here
 188         - add arith comparison functions
 189         - pr_str, str, prn, println
 190         - list, list?, count, empty?
 191     - env module:
 192         - add binds/exprs handling to Env constructor with variable arity
 193     - EVAL:
 194         - do:
 195         - if:
 196         - fn*:
 197             - simple if language supports closures
 198             - otherwise needs a way of representing functions that can
 199               have associated metadata
 200     - define "not" using REP/RE
 201     - Details:
 202         - cp step3_env.EXT to step4_env.EXT
 203             - modify Makefile if compiled
 204         - env.EXT
 205             - add binds and exprs args. Create new environments with
 206               exprs bound to binds. If & symbol, bind rest of exprs to
 207               next bind symbol
 208         - EVAL:
 209             - do:
 210                 - eval_ast [1:], then return last eval'd element
 211             - if
 212                 - EVAL(a1)
 213                     - if true EVAL(a2)
 214                     - else EVAL(a3), unless no a3 then return nil
 215             - fn*
 216                 - if available use function closures to return a new
 217                   native function that calls EVAL(a2, Env(env, a1, fargs))
 218                 - otherwise, store exp, params and env in a structure
 219         - core.EXT
 220             - create ns object to hold core namespace
 221             - move numeric operators here
 222             - add comparison operators
 223             - add list, list?, empty?, count
 224         - run make test^EXT^step4
 225         - implement equal?/equal_Q in types.EXT and refer in core.ns
 226         - implement not as rep("(def! not (fn* (a) (if a false true)))")
 227         - run make test^EXT^step4: should pass everything except
 228           string routines
 229         - implement: pr-str, str, prn, println in core.EXT and
 230           refer in core.ns
 231             - should leverage pr-str from printer.EXT
 232             - add reader/printer string quote/unquote
 233
 234 - step5_tco
 235     - types module:
 236         - mal function type:
 237             - stores: eval, exp, env, params
 238             - eval is EVAL in native mal case (needed for map function
 239               later), otherwise reference to platform function
 240             - if metadata support, then store exp, env, params as
 241               metadata
 242     - printer
 243         - add printing of mal function type
 244     - EVAL:
 245         - while loop around whole thing
 246         - cases where we directly return result of EVAL, instead set
 247           ast and env to what would be put in the EVAL, then loop.
 248             - do, if, "apply"
 249             - "apply"
 250                 - if mal function type
 251                     - set env to new Env based on properties on the function
 252                 - if native function, same as before
 253     - Details:
 254         - types.EXT
 255             - create Mal function type to store eval, exp, env, params
 256         - cp step4_if_fn_do.EXT to step5_tco.EXT
 257             - wrap EVAL in infinite while loop
 258             - in let*, do, and if:
 259                 - set ast and env and loop (no return)
 260             - in fn* create Mal function type
 261         - if compiled, update Makefile
 262         - in apply, test if Mal function type:
 263             - if so, generate new env from stored env, args and callee
 264               params
 265             - set ast to stored ast
 266
 267
 268 - step6_file
 269     - core module:
 270         - read-string, slurp functions
 271     - define eval and load-file functions
 272     - set *ARGV*
 273     - if files on command line, use load-file to run first argument
 274       using rest as arguments
 275     - Details:
 276         - cp step5_tco.EXT to step6_file.EXT
 277         - if compiled update Makefile
 278         - add eval to repl_env
 279             - if no (or limited closures) may have to add an "eval"
 280               case to EVAL and use function which gets root of
 281               environment to env.EXT (see rust).
 282         - add empty *ARGV* list to repl_env
 283         - in core.ns:
 284             - wrap printer.read-str as read-string
 285             - implement slurp
 286         - implement load-file using rep
 287         - test:
 288             (load-file "../tests/inc.mal")
 289             (inc3 10)
 290         - implement command line execution
 291         - test:
 292             ./step6_file ../tests/incA.mal
 293             =>9
 294         - implement comments in reader.EXT (ignore in tokenize)
 295
 296 - step7_quote
 297     - add is_pair and quasiquote functions
 298         - rewrite ast using cons/concat functions
 299         - if vectors, use sequential? instead of list? in is_pair
 300     - EVAL:
 301         - add 'quote', 'quasiquote' cases
 302     - core module:
 303         - add cons and concat functions
 304     - reader module:
 305         - add reader macros to read_form for quote, unquote,
 306           splice-unquote and quasiquote
 307     - Details:
 308         - cp step6_file.EXT to step6_quote.EXT
 309         - if compiled update Makefile
 310         - implement reader macros (', `, ~, ~@) in reader
 311         - retest make test^go^step1
 312         - add is_pair and quasiquote
 313         - add quote and quasiquote cases to EVAL
 314         - implement cons and concat in core.EXT
 315         - retest test^go^step7
 316
 317 - step8_macros
 318     - types
 319         - capability to store ismacro property in function
 320     - core module:
 321         - add first, rest, nth functions
 322     - add is_macro_call and macroexpand
 323         - recursively macroexpand lists
 324         - if applying a macro function, run it on the ast first before
 325           continuing
 326     - call macroexpand apply in EVAL before apply
 327     - EVAL:
 328         - add 'defmacro!' and 'macroexpand'
 329         - set ismacro property on function
 330     - Details:
 331         - cp step7_quote.EXT to step8_macros.EXT
 332         - if compiled update Makefile
 333         - add isMacro property to Mal Function type
 334             - may need to go back and adjust step5-7
 335         - implement is_macro_call and macroexpand
 336         - call macroexpand on ast before apply in EVAL
 337         - add defmacro! and macroexpand to EVAL switch
 338         - make test^go^step8 should pass some basic macros
 339         - add nth, first, and rest to core.ns
 340         - make test^go^step8 should now pass
 341
 342 - step9_try
 343     - core module:
 344         - throw function
 345         - apply, map functions: should not directly call EVAL, which
 346           requires the function object to be runnable
 347         - readline
 348         - nil?, true?, false?
 349     - EVAL:
 350         - try*/catch*: for normal exceptions, extracts string
 351           otherwise extracts full value
 352     - set and print *host-language*
 353     - define cond and or macros using REP/RE
 354     - Details:
 355         - cp step8_macros.EXT to stepA_try.EXT
 356         - if compiled update Makefile
 357         - core.ns implement nil?, true?, false?, symbol?, sequential?,
 358           vector, vector?
 359         - add mal error type which wraps normal mal type
 360             - in core.ns add throw which wraps type in mal error type
 361               and throws/raises/sets exception
 362         - add try*/catch* support to EVAL
 363             - if mal error type, bind to catch* bind symbol
 364             - otherwise, bind string of error to catch* bind symbol
 365         - implement apply, map in core.ns
 366         - make test^go^stepA
 367         - implement readline.EXT
 368             - provide option (e.g. commented out) to link with GNU
 369               readline (GPL) or libedit (BSD)
 370         - add hash-map functions: hash-map, map?, assoc, dissoc, get,
 371           contains?, keys, vals
 372         - add metadata support to List, Vector, HashMap, and Functions
 373             - add reader macro
 374             - may need to box HashMap and native functions
 375         - add atom type, reader macro and functions: with_meta, meta
 376         - get `make test^go^stepA` to fully pass
 377         - get `./stepA_try ../mal/step1_read_print` to pass
 378             - continue for each mal step until ../mal/stepA_try
 379             - Now self-hosting!
 380
 381
 382 - Extra defintions needed for self-hosting
 383     - core module:
 384         - symbol?, sequential? (if not already)
 385         - vector, vector?
 386
 387
 388 - atoms
 389     - reader module:
 390         - @a reader macro -> (deref a)
 391     - core module:
 392         - pr_str case
 393         - atom type, atom, atom?, deref, reset!, swap!
 394
 395 - metadata
 396     - reader module:
 397         - ^ reader macro reads ^meta obj -> (with-meta obj meta)
 398     - types module:
 399         - support meta property on collections: lists, vectors,
 400           hash-maps, functions, atoms
 401             - clone/copy of collections
 402     - core module:
 403         - add with-meta, meta functions
 404
 405 - Other misc:
 406     - conj function
 407
 408 - stepA_mal
 409     - convert returned data to mal data
 410         - recursive, similar to pr_str
 411     - Details:
 412