teliva/lisp.tlv

# .tlv file generated by https://github.com/akkartik/teliva
# You may edit it if you are careful; however, you may see cryptic errors if you
# violate Teliva's assumptions.
#
# .tlv files are representations of Teliva programs. Teliva programs consist of
# sequences of definitions. Each definition is a table of key/value pairs. Keys
# and values are both strings.
#
# Lines in .tlv files always follow exactly one of the following forms:
# - comment lines at the top of the file starting with '#' at column 0
# - beginnings of definitions starting with '- ' at column 0, followed by a
#   key/value pair
# - key/value pairs consisting of '  ' at column 0, containing either a
#   spaceless value on the same line, or a multi-line value
# - multiline values indented by more than 2 spaces, starting with a '>'
#
# If these constraints are violated, Teliva may unceremoniously crash. Please
# report bugs at http://akkartik.name/contact
- __teliva_timestamp: original
  str_helpers:
    >-- some string helpers from http://lua-users.org/wiki/StringIndexing
    >
    >-- index characters using []
    >getmetatable('').__index = function(str,i)
    >  if type(i) == 'number' then
    >    return str:sub(i,i)
    >  else
    >    return string[i]
    >  end
    >end
    >
    >-- ranges using (), selected bytes using {}
    >getmetatable('').__call = function(str,i,j)
    >  if type(i)~='table' then
    >    return str:sub(i,j)
    >  else
    >    local t={}
    >    for k,v in ipairs(i) do
    >      t[k]=str:sub(v,v)
    >    end
    >    return table.concat(t)
    >  end
    >end
    >
    >-- iterate over an ordered sequence
    >function q(x)
    >  if type(x) == 'string' then
    >    return x:gmatch('.')
    >  else
    >    return ipairs(x)
    >  end
    >end
    >
    >-- insert within string
    >function string.insert(str1, str2, pos)
    >  return str1:sub(1,pos)..str2..str1:sub(pos+1)
    >end
    >
    >function string.remove(s, pos)
    >  return s:sub(1,pos-1)..s:sub(pos+1)
    >end
    >
    >function string.pos(s, sub)
    >  return string.find(s, sub, 1, true)  -- plain=true to disable regular expressions
    >end
    >
    >-- TODO: backport utf-8 support from Lua 5.3
- __teliva_timestamp: original
  check:
    >function check(x, msg)
    >  if x then
    >    Window:addch('.')
    >  else
    >    print('F - '..msg)
    >    print('  '..str(x)..' is false/nil')
    >    teliva_num_test_failures = teliva_num_test_failures + 1
    >    -- overlay first test failure on editors
    >    if teliva_first_failure == nil then
    >      teliva_first_failure = msg
    >    end
    >  end
    >end
- __teliva_timestamp: original
  check_eq:
    >function check_eq(x, expected, msg)
    >  if eq(x, expected) then
    >    Window:addch('.')
    >  else
    >    print('F - '..msg)
    >    print('  expected '..str(expected)..' but got '..str(x))
    >    teliva_num_test_failures = teliva_num_test_failures + 1
    >    -- overlay first test failure on editors
    >    if teliva_first_failure == nil then
    >      teliva_first_failure = msg
    >    end
    >  end
    >end
- __teliva_timestamp: original
  eq:
    >function eq(a, b)
    >  if type(a) ~= type(b) then return false end
    >  if type(a) == 'table' then
    >    if #a ~= #b then return false end
    >    for k, v in pairs(a) do
    >      if b[k] ~= v then
    >        return false
    >      end
    >    end
    >    for k, v in pairs(b) do
    >      if a[k] ~= v then
    >        return false
    >      end
    >    end
    >    return true
    >  end
    >  return a == b
    >end
- __teliva_timestamp: original
  str:
    >-- smarter tostring
    >-- slow; used only for debugging
    >function str(x)
    >  if type(x) == 'table' then
    >    local result = ''
    >    result = result..#x..'{'
    >    for k, v in pairs(x) do
    >      result = result..str(k)..'='..str(v)..', '
    >    end
    >    result = result..'}'
    >    return result
    >  elseif type(x) == 'string' then
    >    return '"'..x..'"'
    >  end
    >  return tostring(x)
    >end
- __teliva_timestamp: original
  menu:
    >-- To show app-specific hotkeys in the menu bar, add hotkey/command
    >-- arrays of strings to the menu array.
    >menu = {}
- __teliva_timestamp: original
  Window:
    >Window = curses.stdscr()
- __teliva_timestamp: original
  render:
    >function render(window)
    >  window:clear()
    >  -- draw stuff to screen here
    >  window:attron(curses.A_BOLD)
    >  window:mvaddstr(1, 5, "example app")
    >  window:attrset(curses.A_NORMAL)
    >  for i=0,15 do
    >    window:attrset(curses.color_pair(i))
    >    window:mvaddstr(3+i, 5, "========================")
    >  end
    >  window:refresh()
    >end
- __teliva_timestamp: original
  menu:
    >-- To show app-specific hotkeys in the menu bar, add hotkey/command
    >-- arrays of strings to the menu array.
    >menu = {}
- __teliva_timestamp: original
  update:
    >function update(window)
    >  local key = window:getch()
    >  -- process key here
    >end
- __teliva_timestamp: original
  init_colors:
    >function init_colors()
    >  for i=0,7 do
    >    curses.init_pair(i, i, -1)
    >  end
    >  curses.init_pair(8, 7, 0)
    >  curses.init_pair(9, 7, 1)
    >  curses.init_pair(10, 7, 2)
    >  curses.init_pair(11, 7, 3)
    >  curses.init_pair(12, 7, 4)
    >  curses.init_pair(13, 7, 5)
    >  curses.init_pair(14, 7, 6)
    >  curses.init_pair(15, -1, 15)
    >end
- __teliva_timestamp: original
  main:
    >function main()
    >  init_colors()
    >
    >  while true do
    >    render(Window)
    >    update(Window)
    >  end
    >end
- __teliva_timestamp: original
  eval:
    >function eval(x, env)
    >  function symeq(x, s)
    >    return x and x.sym == s
    >  end
    >  if x.sym then
    >    return lookup(env, x.sym)
    >  elseif atom(x) then
    >    return x
    >  -- otherwise x is a pair
    >  elseif symeq(x.car, 'quote') then
    >    return x.cdr
    >  elseif unary_functions[x.car.sym] then
    >    return eval_unary(x, env)
    >  elseif binary_functions[x.car.sym] then
    >    return eval_binary(x, env)
    >  -- special forms that don't always eval all their args
    >  elseif symeq(x.car, 'if') then
    >    return eval_if(x, env)
    >  elseif symeq(x.car.car, 'fn') then
    >    return eval_fn(x, env)
    >  elseif symeq(x.car.car, 'label') then
    >    return eval_label(x, env)
    >  end
    >end
- __teliva_timestamp: original
  eval_unary:
    >function eval_unary(x, env)
    >  return unary_functions[x.car.sym](eval(x.cdr.car, env))
    >end
- __teliva_timestamp: original
  eval_binary:
    >function eval_binary(x, env)
    >  return binary_functions[x.car.sym](eval(x.cdr.car, env))
    >end
- __teliva_timestamp: original
  unary_functions:
    >-- format: lisp name = lua function that implements it
    >unary_functions = {
    >  atom=atom,
    >  car=car,
    >  cdr=cdr,
    >}
- __teliva_timestamp: original
  binary_functions:
    >-- format: lisp name = lua function that implements it
    >binary_functions = {
    >  cons=cons,
    >  iso=iso,
    >}
- __teliva_timestamp: original
  lookup:
    >function lookup(env, s)
    >  if env[s] then return env[s] end
    >  if env.next then return lookup(env.next, s) end
    >end
- __teliva_timestamp: original
  eval_if:
    >function eval_if(x, env)
    >  -- syntax: (if check b1 b2)
    >  local check = x.cdr.car
    >  local b1    = x.cdr.cdr.car
    >  local b2    = x.cdr.cdr.cdr.car
    >  if eval(check, env) then
    >    return eval(b1, env)
    >  else
    >    return eval(b2, env)
    >  end
    >end
- __teliva_timestamp: original
  eval_fn:
    >function eval_fn(x, env)
    >  -- syntax: ((fn params body*) args*)
    >  local callee = x.car
    >  local args = x.cdr
    >  local params = callee.cdr.car
    >  local body = callee.cdr.cdr
    >  return eval_exprs(body,
    >                    bind_env(params, args, env))
    >end
- __teliva_timestamp: original
  bind_env:
    >function bind_env(params, args, env)
    >  if params == nil then return env end
    >  local result = {next=env}
    >  while true do
    >    result[params.car.sym] = eval(args.car, env)
    >    params = params.cdr
    >    args = args.cdr
    >    if params == nil then break end
    >  end
    >  return result
    >end
- __teliva_timestamp: original
  eval_exprs:
    >function eval_exprs(xs, env)
    >  local result = nil
    >  while xs do
    >    result = eval(xs.car, env)
    >    xs = xs.cdr
    >  end
    >  return result
    >end
- __teliva_timestamp: original
  eval_label:
    >function eval_label(x, env)
    >  -- syntax: ((label f (fn params body*)) args*)
    >  local callee = x.car
    >  local args = x.cdr
    >  local f = callee.cdr.car
    >  local fn = callee.cdr.cdr.car
    >  return eval({car=fn, cdr=args},
    >              bind_env({f}, {callee}, env))
    >end
- __teliva_timestamp: original
  atom:
    >function atom(x)
    >  return x == nil or x.num or x.char or x.str or x.sym
    >end
- __teliva_timestamp: original
  car:
    >function car(x) return x.car end
- __teliva_timestamp: original
  cdr:
    >function cdr(x) return x.cdr end
- __teliva_timestamp: original
  cons:
    >function cons(x, y) return {car=x, cdr=y} end
- __teliva_timestamp: original
  doc:main:
    >John McCarthy's Lisp -- without the metacircularity
    >If you know Lua, this version might be easier to understand.
    >
    >Words highlighted like [[this]] are suggestions for places to jump to using ctrl-g (see the menu below).
    >You can always jump back here using ctrl-b (for 'big picture').
    >
    >Lisp is a programming language that manipulates objects of a few different types.
    >There are a few _atomic_ types, and one type that can combine them.
    >The atomic types are what you would expect: numbers, characters, strings, symbols (variables). You can add others.
    >
    >The way to combine them is the [[cons]] table which has just two keys: a [[car]] and a [[cdr]]. Both can hold objects, either atoms or other cons tables.
    >
    >We'll now build an interpreter that can run programs constructed out of cons tables.
    >
    >One thing we'll need for an interpreter is a symbol table (env) that maps symbols to values (objects).
    >We'll just use a Lua table for this purpose, but with one tweak: a _next_ pointer that allows us to combine tables together.
    >See [[lookup]] now to get a sense for how we'll use envs.
    >
    >Lisp programs are just cons tables and atoms nested to arbitrary depths, constructing trees. A Lisp interpreter walks the tree of code,
    >performing computations. Since cons tables can point to other cons tables, the tree-walker interpreter [[eval]] is recursive.
    >As the interpreter gets complex, we'll extract parts of it into their own helper functions: [[eval_unary]], [[eval_binary]], [[eval_if]], and so on.
    >The helper functions contain recursive calls to [[eval]], so that [[eval]] becomes indirectly recursive, and [[eval]] together with its helpers
    >is mutually recursive. I sometimes find it helpful to think of them all as just one big function.
    >
    >All these mutually recursive functions take the same arguments: a current expression 'x' and the symbol table 'env'.
    >But really, most of the interpreter is just walking the tree of expressions. Only two functions care about the internals of 'env':
    >  - [[lookup]] which reads within env as we saw before
    >  - [[bind_env]] which creates a new _scope_ of symbols for each new function call.
    >More complex Lisps add even more arguments to every. single. helper. Each arg will still only really matter to a couple of functions.
    >But we still have to pass them around all over the place.
    >
    >Hopefully this quick overview will help you get a sense for this codebase.
    >
    >Here's a reference list of eval helpers: [[eval_unary]], [[eval_binary]], [[eval_if]], [[eval_fn]], [[eval_exprs]], [[eval_label]]
    >More complex Lisps with more features will likely add helpers for lumpy bits of the language.
    >Here's a list of primitives implemented in Lua: [[atom]], [[car]], [[cdr]], [[cons]], [[iso]] (for 'isomorphic'; comparing trees all the way down to the leaves)
    >Here's a list of _constructors_ for creating objects of different types: [[num]], [[char]], [[str]], [[sym]] (and of course [[cons]])
    >I should probably add more primitives for operating on numbers, characters and strings..
- __teliva_timestamp: original
  iso:
    >function iso(x, y)
    >  if x == nil then return y == nil end
    >  local done={}
    >  -- watch out for the rare cyclical expression
    >  if done[x] then return done[x] == y end
    >  done[x] = y
    >  if atom(x) then
    >    if not atom(y) then return nil end
    >    for k, v in pairs(x) do
    >      if y[k] ~= v then return nil end
    >    end
    >    return true
    >  end
    >  for k, v in pairs(x) do
    >    if not iso(y[k], v) then return nil end
    >  end
    >  for k, v in pairs(y) do
    >    if not iso(x[k], v) then return nil end
    >  end
    >  return true
    >end