about summary refs log tree commit diff stats
path: root/999spaces.cc
blob: 219e695dffcadc6b997d1721356122cf9ab1902c (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
//: Since different layers all carve out different parts of various namespaces
//: (recipes, memory, etc.) for their own use, there's no previous place where
//: we can lay out the big picture of what uses what. So we'll do that here
//: and just have to manually remember to update it when we move boundaries
//: around.
//:
//:: Memory
//:
//: Location 0 - unused (since it can help uncover bugs)
//: Locations 1-899 - reserved for tests
//: Locations 900-999 - reserved for predefined globals in Mu scenarios, like keyboard, screen, etc.
:(before "End Reset")
assert(Max_variables_in_scenarios == 900);
//: Locations 1000 ('Reserved_for_tests') onward - available to the allocator in chunks of size Initial_memory_per_routine.
assert(Reserved_for_tests == 1000);

//:: Recipes
//:
//: 0 - unused (IDLE; do nothing)
//: 1-199 - primitives
assert(MAX_PRIMITIVE_RECIPES < 200);
//: 200-999 - defined in .mu files as sequences of primitives
assert(Next_recipe_ordinal == 1000);
//: 1000 onwards - reserved for tests, cleared between tests

//:: Depths for tracing
//:
//: 0 - unused
//: 1-100 - app-level trace statements in Mu
//: 101-9989 - call-stack statements (mostly label run)
assert(Initial_callstack_depth == 101);
assert(Max_callstack_depth == 9989);
//: 9990-9999 - intra-instruction lines (mostly label mem)

//:: Summary of transforms and their dependencies
//: begin transforms
//:   begin instruction inserting transforms
//:     52 insert fragments
//:      ↳ 52.2 check fragments
//:   ---
//:     53 rewrite 'stash' instructions
//:   end instruction inserting transforms
//:
//:   begin instruction modifying transforms
//:     56.2 check header ingredients
//:      ↳ 56.4 fill in return ingredients
//:     48 check or set types by name
//:
//:     begin type modifying transforms
//:       56.3 deduce types from header
//:     ---
//:       30 check or set invalid containers
//:     end type modifying transforms
//:         ↱ 46 collect surrounding spaces
//:      ↳ 42 transform names
//:         ↳ 57 static dispatch
//:   ---
//:     13 update instruction operation
//:     40 transform braces
//:     41 transform labels
//:   end instruction modifying transforms
//:    ↳ 60 check immutable ingredients
//:
//:   begin checks
//:   ---
//:     21 check instruction
//:     ↳ 61 check indirect calls against header
//:     ↳ 56 check calls against header
//:     ↳ 43 transform 'new' to 'allocate'
//:     30 check merge calls
//:     36 check types of return instructions
//:     43 check default space
//:     56 check return instructions against header
//:   end checks
//: end transforms

//:: Summary of type-checking in different phases
//: when dispatching instructions we accept first recipe that:
//:   strictly matches all types
//:   maps literal 0 or literal 1 to boolean for some ingredients
//:   performs some other acceptable type conversion
//:     literal 0 -> address
//:     literal -> character
//: when checking instructions we ensure that types match, and that literals map to some scalar
//:   (address can only map to literal 0)
//:   (boolean can only map to literal 0 or literal 1)
//:     (but conditionals can take any scalar)
//: at runtime we perform no checks
f='#n445'>445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583
## experimental compiler to translate programs written in a generic
## expression-oriented language called 'lambda' into mu

scenario convert-lambda [
  run [
    local-scope
    1:address:array:character/raw <- lambda-to-mu [(add a (multiply b c))]
    2:array:character/raw <- copy *1:address:array:character/raw
  ]
  memory-should-contain [
    2:array:character <- [t1 <- multiply b c
result <- add a t1]
  ]
]

def lambda-to-mu in:address:array:character -> out:address:array:character [
  local-scope
  load-ingredients
  out <- copy 0
  cells:address:cell <- parse in
  out <- to-mu cells
]

# 'parse' will turn lambda expressions into trees made of cells
exclusive-container cell [
  atom:address:array:character
  pair:pair
]

# printed below as < first | rest >
container pair [
  first:address:cell
  rest:address:cell
]

def new-atom name:address:array:character -> result:address:cell [
  local-scope
  load-ingredients
  result <- new cell:type
  *result <- merge 0/tag:atom, name
]

def new-pair a:address:cell, b:address:cell -> result:address:cell [
  local-scope
  load-ingredients
  result <- new cell:type
  *result <- merge 1/tag:pair, a/first, b/rest
]

def is-atom? x:address:cell -> result:boolean [
  local-scope
  load-ingredients
  reply-unless x, 0/false
  _, result <- maybe-convert *x, atom:variant
]

def is-pair? x:address:cell -> result:boolean [
  local-scope
  load-ingredients
  reply-unless x, 0/false
  _, result <- maybe-convert *x, pair:variant
]

scenario atom-is-not-pair [
  local-scope
  s:address:array:character <- new [a]
  x:address:cell <- new-atom s
  10:boolean/raw <- is-atom? x
  11:boolean/raw <- is-pair? x
  memory-should-contain [
    10 <- 1
    11 <- 0
  ]
]

scenario pair-is-not-atom [
  local-scope
  # construct (a . nil)
  s:address:array:character <- new [a]
  x:address:cell <- new-atom s
  y:address:cell <- new-pair x, 0/nil
  10:boolean/raw <- is-atom? y
  11:boolean/raw <- is-pair? y
  memory-should-contain [
    10 <- 0
    11 <- 1
  ]
]

def atom-match? x:address:cell, pat:address:array:character -> result:boolean [
  local-scope
  load-ingredients
  s:address:array:character, is-atom?:boolean <- maybe-convert *x, atom:variant
  reply-unless is-atom?, 0/false
  result <- equal pat, s
]

scenario atom-match [
  local-scope
  x:address:cell <- new-atom [abc]
  10:boolean/raw <- atom-match? x, [abc]
  memory-should-contain [
    10 <- 1
  ]
]

def first x:address:cell -> result:address:cell [
  local-scope
  load-ingredients
  pair:pair, pair?:boolean <- maybe-convert *x, pair:variant
  reply-unless pair?, 0/nil
  result <- get pair, first:offset
]

def rest x:address:cell -> result:address:cell [
  local-scope
  load-ingredients
  pair:pair, pair?:boolean <- maybe-convert *x, pair:variant
  reply-unless pair?, 0/nil
  result <- get pair, rest:offset
]

def set-first base:address:cell, new-first:address:cell -> base:address:cell [
  local-scope
  load-ingredients
  pair:pair, is-pair?:boolean <- maybe-convert *base, pair:variant
  reply-unless is-pair?
  pair <- put pair, first:offset, new-first
  *base <- merge 1/pair, pair
]

def set-rest base:address:cell, new-rest:address:cell -> base:address:cell [
  local-scope
  load-ingredients
  pair:pair, is-pair?:boolean <- maybe-convert *base, pair:variant
  reply-unless is-pair?
  pair <- put pair, rest:offset, new-rest
  *base <- merge 1/pair, pair
]

scenario cell-operations-on-atom [
  local-scope
  s:address:array:character <- new [a]
  x:address:cell <- new-atom s
  10:address:cell/raw <- first x
  11:address:cell/raw <- rest x
  memory-should-contain [
    10 <- 0  # first is nil
    11 <- 0  # rest is nil
  ]
]

scenario cell-operations-on-pair [
  local-scope
  # construct (a . nil)
  s:address:array:character <- new [a]
  x:address:cell <- new-atom s
  y:address:cell <- new-pair x, 0/nil
  x2:address:cell <- first y
  10:boolean/raw <- equal x, x2
  11:address:cell/raw <- rest y
  memory-should-contain [
    10 <- 1  # first is correct
    11 <- 0  # rest is nil
  ]
]

## convert lambda text to a tree of cells

def parse in:address:array:character -> out:address:cell [
  local-scope
  load-ingredients
  s:address:stream:character <- new-stream in
  out, s <- parse s
  trace 2, [app/parse], out
]

def parse in:address:stream:character -> out:address:cell, in:address:stream:character [
  local-scope
  load-ingredients
  # skip whitespace
  in <- skip-whitespace in
  c:character, eof?:boolean <- peek in
  reply-if eof?, 0/nil
  pair?:boolean <- equal c, 40/open-paren
  {
    break-if pair?
    # atom
    b:address:buffer <- new-buffer 30
    {
      done?:boolean <- end-of-stream? in
      break-if done?
      # stop before close paren or space
      c:character <- peek in
      done? <- equal c, 41/close-paren
      break-if done?
      done? <- space? c
      break-if done?
      c <- read in
      b <- append b, c
      loop
    }
    s:address:array:character <- buffer-to-array b
    out <- new-atom s
  }
  {
    break-unless pair?
    # pair
    read in  # skip the open-paren
    out <- new cell:type  # start out with nil
    # read in first element of pair
    {
      end?:boolean <- end-of-stream? in
      not-end?:boolean <- not end?
      assert not-end?, [unbalanced '(' in expression]
      c <- peek in
      close-paren?:boolean <- equal c, 41/close-paren
      break-if close-paren?
      first:address:cell, in <- parse in
      *out <- merge 1/pair, first, 0/nil
    }
    # read in any remaining elements
    curr:address:cell <- copy out
    {
      in <- skip-whitespace in
      end?:boolean <- end-of-stream? in
      not-end?:boolean <- not end?
      assert not-end?, [unbalanced '(' in expression]
      # termination check: ')'
      c <- peek in
      {
        close-paren?:boolean <- equal c, 41/close-paren
        break-unless close-paren?
        read in  # skip ')'
        break +end-pair:label
      }
      # still here? read next element of pair
      next:address:cell, in <- parse in
      is-dot?:boolean <- atom-match? next, [.]
      {
        break-if is-dot?
        next-curr:address:cell <- new-pair next, 0/nil
        curr <- set-rest curr, next-curr
        curr <- rest curr
      }
      {
        break-unless is-dot?
        # deal with dotted pair
        in <- skip-whitespace in
        c <- peek in
        not-close-paren?:boolean <- not-equal c, 41/close-paren
        assert not-close-paren?, [')' cannot immediately follow '.']
        final:address:cell <- parse in
        curr <- set-rest curr, final
        # we're not gonna update curr, so better make sure the next iteration
        # is going to end the pair
        in <- skip-whitespace in
        c <- peek in
        close-paren?:boolean <- equal c, 41/close-paren
        assert close-paren?, ['.' must be followed by exactly one expression before ')']
      }
      loop
    }
    +end-pair
  }
]

def skip-whitespace in:address:stream:character -> in:address:stream:character [
  local-scope
  load-ingredients
  {
    done?:boolean <- end-of-stream? in
    reply-if done?, 0/null
    c:character <- peek in
    space?:boolean <- space? c
    break-unless space?
    read in  # skip
    loop
  }
]

def to-text x:address:cell -> out:address:array:character [
  local-scope
  load-ingredients
  buf:address:buffer <- new-buffer 30
  buf <- to-buffer x, buf
  out <- buffer-to-array buf
]

def to-buffer x:address:cell, buf:address:buffer -> buf:address:buffer [
  local-scope
  load-ingredients
  # base case: empty cell
  {
    break-if x
    buf <- append buf, [<>]
    reply
  }
  # base case: atom
  {
    s:address:array:character, atom?:boolean <- maybe-convert *x, atom:variant
    break-unless atom?
    buf <- append buf, s
    reply
  }
  # recursive case: pair
  buf <- append buf, [< ]
  first:address:cell <- first x
  buf <- to-buffer first, buf
  buf <- append buf, [ | ]
  rest:address:cell <- rest x
  buf <- to-buffer rest, buf
  buf <- append buf, [ >]
]

scenario parse-single-letter-atom [
  local-scope
  s:address:array:character <- new [a]
  x:address:cell <- parse s
  s2:address:array:character, 10:boolean/raw <- maybe-convert *x, atom:variant
  11:array:character/raw <- copy *s2
  memory-should-contain [
    10 <- 1  # parse result is an atom
    11:array:character <- [a]
  ]
]

scenario parse-atom [
  local-scope
  s:address:array:character <- new [abc]
  x:address:cell <- parse s
  s2:address:array:character, 10:boolean/raw <- maybe-convert *x, atom:variant
  11:array:character/raw <- copy *s2
  memory-should-contain [
    10 <- 1  # parse result is an atom
    11:array:character <- [abc]
  ]
]

scenario parse-list-of-two-atoms [
  local-scope
  s:address:array:character <- new [(abc def)]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | <> > >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  x2:address:cell <- rest x
  s1:address:array:character, 11:boolean/raw <- maybe-convert *x1, atom:variant
  12:boolean/raw <- is-pair? x2
  x3:address:cell <- first x2
  s2:address:array:character, 13:boolean/raw <- maybe-convert *x3, atom:variant
  14:address:cell/raw <- rest x2
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is an atom
    12 <- 1  # result.rest is a pair
    13 <- 1  # result.rest.first is an atom
    14 <- 0  # result.rest.rest is nil
    20:array:character <- [abc]  # result.first
    30:array:character <- [def]  # result.rest.first
  ]
]

scenario parse-list-with-extra-spaces [
  local-scope
  s:address:array:character <- new [ ( abc  def ) ]  # extra spaces
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | <> > >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  x2:address:cell <- rest x
  s1:address:array:character, 11:boolean/raw <- maybe-convert *x1, atom:variant
  12:boolean/raw <- is-pair? x2
  x3:address:cell <- first x2
  s2:address:array:character, 13:boolean/raw <- maybe-convert *x3, atom:variant
  14:address:cell/raw <- rest x2
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is an atom
    12 <- 1  # result.rest is a pair
    13 <- 1  # result.rest.first is an atom
    14 <- 0  # result.rest.rest is nil
    20:array:character <- [abc]  # result.first
    30:array:character <- [def]  # result.rest.first
  ]
]

scenario parse-list-of-more-than-two-atoms [
  local-scope
  s:address:array:character <- new [(abc def ghi)]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | < ghi | <> > > >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  x2:address:cell <- rest x
  s1:address:array:character, 11:boolean/raw <- maybe-convert *x1, atom:variant
  12:boolean/raw <- is-pair? x2
  x3:address:cell <- first x2
  s2:address:array:character, 13:boolean/raw <- maybe-convert *x3, atom:variant
  x4:address:cell <- rest x2
  14:boolean/raw <- is-pair? x4
  x5:address:cell <- first x4
  s3:address:array:character, 15:boolean/raw <- maybe-convert *x5, atom:variant
  16:address:cell/raw <- rest x4
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  40:array:character/raw <- copy *s3
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is an atom
    12 <- 1  # result.rest is a pair
    13 <- 1  # result.rest.first is an atom
    14 <- 1  # result.rest.rest is a pair
    15 <- 1  # result.rest.rest.first is an atom
    16 <- 0  # result.rest.rest.rest is nil
    20:array:character <- [abc]  # result.first
    30:array:character <- [def]  # result.rest.first
    40:array:character <- [ghi]  # result.rest.rest
  ]
]

scenario parse-nested-list [
  local-scope
  s:address:array:character <- new [((abc))]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < < abc | <> > | <> >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  11:boolean/raw <- is-pair? x
  x2:address:cell <- first x1
  s1:address:array:character, 12:boolean/raw <- maybe-convert *x2, atom:variant
  13:address:cell/raw <- rest x1
  14:address:cell/raw <- rest x
  20:array:character/raw <- copy *s1
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is a pair
    12 <- 1  # result.first.first is an atom
    13 <- 0  # result.first.rest is nil
    14 <- 0  # result.rest is nil
    20:array:character <- [abc]  # result.first.first
  ]
]

scenario parse-nested-list-2 [
  local-scope
  s:address:array:character <- new [((abc) def)]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < < abc | <> > | < def | <> > >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  11:boolean/raw <- is-pair? x
  x2:address:cell <- first x1
  s1:address:array:character, 12:boolean/raw <- maybe-convert *x2, atom:variant
  13:address:cell/raw <- rest x1
  x3:address:cell <- rest x
  x4:address:cell <- first x3
  s2:address:array:character, 14:boolean/raw <- maybe-convert *x4, atom:variant
  15:address:cell/raw <- rest x3
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is a pair
    12 <- 1  # result.first.first is an atom
    13 <- 0  # result.first.rest is nil
    14 <- 1  # result.rest.first is an atom
    15 <- 0  # result.rest.rest is nil
    20:array:character <- [abc]  # result.first.first
    30:array:character <- [def]  # result.rest.first
  ]
]

# todo: uncomment these tests after we figure out how to continue tests after
# assertion failures
#? scenario parse-error [
#?   local-scope
#?   s:address:array:character <- new [(]
#? #?   hide-errors
#?   x:address:cell <- parse s
#? #?   show-errors
#?   trace-should-contain [
#?     error: unbalanced '(' in expression
#?   ]
#? ]
#? 
#? scenario parse-error-after-element [
#?   local-scope
#?   s:address:array:character <- new [(abc]
#? #?   hide-errors
#?   x:address:cell <- parse s
#? #?   show-errors
#?   trace-should-contain [
#?     error: unbalanced '(' in expression
#?   ]
#? ]

scenario parse-dotted-list-of-two-atoms [
  local-scope
  s:address:array:character <- new [(abc . def)]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < abc | def >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  x2:address:cell <- rest x
  s1:address:array:character, 11:boolean/raw <- maybe-convert *x1, atom:variant
  s2:address:array:character, 12:boolean/raw <- maybe-convert *x2, atom:variant
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  memory-should-contain [
    # parses to < abc | def >
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is an atom
    12 <- 1  # result.rest is an atom
    20:array:character <- [abc]  # result.first
    30:array:character <- [def]  # result.rest
  ]
]

scenario parse-dotted-list-of-more-than-two-atoms [
  local-scope
  s:address:array:character <- new [(abc def . ghi)]
  x:address:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | ghi > >
  ]
  10:boolean/raw <- is-pair? x
  x1:address:cell <- first x
  x2:address:cell <- rest x
  s1:address:array:character, 11:boolean/raw <- maybe-convert *x1, atom:variant
  12:boolean/raw <- is-pair? x2
  x3:address:cell <- first x2
  s2:address:array:character, 13:boolean/raw <- maybe-convert *x3, atom:variant
  x4:address:cell <- rest x2
  s3:address:array:character, 14:boolean/raw <- maybe-convert *x4, atom:variant
  20:array:character/raw <- copy *s1
  30:array:character/raw <- copy *s2
  40:array:character/raw <- copy *s3
  memory-should-contain [
    10 <- 1  # parse result is a pair
    11 <- 1  # result.first is an atom
    12 <- 1  # result.rest is a pair
    13 <- 1  # result.rest.first is an atom
    14 <- 1  # result.rest.rest is an atom
    20:array:character <- [abc]  # result.first
    30:array:character <- [def]  # result.rest.first
    40:array:character <- [ghi]  # result.rest.rest
  ]
]

## convert tree of cells to mu text

def to-mu in:address:cell -> out:address:array:character [
  local-scope
  load-ingredients
  buf:address:buffer <- new-buffer 30
  buf <- to-mu in, buf
  out <- buffer-to-array buf
]

def to-mu in:address:cell, buf:address:buffer -> buf:address:buffer, result-name:address:array:character [
  local-scope
  load-ingredients
  # null cell? no change.
  # pair with all atoms? gensym a new variable
  # pair containing other pairs? recurse
]