about summary refs log tree commit diff stats
path: root/lisp.tlv
blob: 1165cc6c0dbb130429d5f7f66009ba205a3c897e (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
# .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
    >
    >-- TODO: backport utf-8 support from Lua 5.3
- __teliva_timestamp: original
  debugy:
    >debugy = 5
- __teliva_timestamp: original
  dbg:
    >-- helper for debug by print; overlay debug information towards the right
    >-- reset debugy every time you refresh screen
    >function dbg(window, s)
    >  local oldy = 0
    >  local oldx = 0
    >  oldy, oldx = window:getyx()
    >  window:mvaddstr(debugy, 60, s)
    >  debugy = debugy+1
    >  window:mvaddstr(oldy, oldx, '')
    >end
- __teliva_timestamp: original
  check_eq:
    >function check_eq(x, expected, msg)
    >  if x == expected then
    >    Window:addch('.')
    >  else
    >    print('F - '..msg)
    >    print('  expected '..tostring(expected)..' but got '..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
  map:
    >-- only for arrays
    >function map(l, f)
    >  result = {}
    >  for _, x in ipairs(l) do
    >    table.insert(result, f(x))
    >  end
    >  return result
    >end
- __teliva_timestamp: original
  reduce:
    >-- only for arrays
    >function reduce(l, f, init)
    >  result = init
    >  for _, x in ipairs(l) do
    >    result = f(result, x)
    >  end
    >  return result
    >end
- __teliva_timestamp: original
  filter:
    >-- only for arrays
    >function filter(l, f)
    >  result = {}
    >  for _, x in ipairs(l) do
    >    if f(x) then
    >      table.insert(result, x)
    >    end
    >  end
    >  return result
    >end
- __teliva_timestamp: original
  find_index:
    >function find_index(arr, x)
    >  for n, y in ipairs(arr) do
    >    if x == y then
    >      return n
    >    end
    >  end
    >end
- __teliva_timestamp: original
  trim:
    >function trim(s)
    >  return s:gsub('^%s*', ''):gsub('%s*$', '')
    >end
- __teliva_timestamp: original
  split:
    >function split(s, d)
    >  result = {}
    >  for match in (s..d):gmatch("(.-)"..d) do
    >    table.insert(result, match);
    >  end
    >  return result
    >end
- __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