about summary refs log blame commit diff stats
path: root/091socket.cc
blob: 111b8d8aa76b02fa4cf0a7db5f5d394a8f131938 (plain) (tree)
1
2
3
4
5
6
7
8



                     
              

              
                   



                               
                                             






























































                                                                                                                                                                                                                      
                    
                                        
                                                                
                                       
                           
                                    
                                                                                                                                                                                             


                                              
                                                                                                                                                                            


                                 
                                                                                                                                                     


                                           
                                                                                                                                                                                    




                                                
                           
                                     
                                         
                     
                       

                                

          
                                                                 
                                                        

        
       
                                   

                                               

                                                          
                  
   


                                                                          
                                                                                                                                            
                                      
                                                                                                


                                          

                      
                                                                                                                    
   

                
 

























                                                                                                                                                                        
                     



                                                                                            
                                               





                                                                    

        
       
                                            


                                         
                                                                                      
                
 






                                                            

                                                                                                                                                      


                                              
                                                                                                                                                                                   

          


                                                                                                                                            

          

                                                                                                                                                                       

          









                                                                                                                                                                                       

          



                                                
                     

                                                                        





                                                                                   




                                                                             
                        



                                

                                                                       





                                               
                               
                             
                                                                                       



                                               

            
                          
   
                
                     
                                                                        
                                         




                                                           
                              

                                                   
                                       

















                                                                                                                                                     
                                                    
                                                     

                                                                        
                                      


                                                                                    
                     
                                                    
        







                                                    
                                    


                                                                                                                                                  
                                              
                                                                                                                                                                      

          







                                                                                                                                                                                                                        



                                                


                                                                        
                

                                                                      

        

                        
                       

                  

                       
:(before "End Types")
struct socket_t {
  int fd;
  sockaddr_in addr;
  bool polled;
  socket_t() {
    fd = 0;
    polled = false;
    bzero(&addr, sizeof(addr));
  }
};

:(before "End Primitive Recipe Declarations")
_OPEN_CLIENT_SOCKET,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$open-client-socket", _OPEN_CLIENT_SOCKET);
:(before "End Primitive Recipe Checks")
case _OPEN_CLIENT_SOCKET: {
  if (SIZE(inst.ingredients) != 2) {
    raise << maybe(get(Recipe, r).name) << "'$open-client-socket' requires exactly two ingredients, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_text(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first ingredient of '$open-client-socket' should be text (the hostname), but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.ingredients.at(1))) {
    raise << maybe(get(Recipe, r).name) << "second ingredient of '$open-client-socket' should be a number (the port of the hostname to connect to), but got '" << to_string(inst.ingredients.at(1)) << "'\n" << end();
    break;
  }
  if (SIZE(inst.products) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$open-client-socket' requires exactly one product, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.products.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first product of '$open-client-socket' should be a number (socket handle), but got '" << to_string(inst.products.at(0)) << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _OPEN_CLIENT_SOCKET: {
  string host = read_mu_text(ingredients.at(0).at(0));
  int port = ingredients.at(1).at(0);
  socket_t* client = client_socket(host, port);
  products.resize(1);
  if (client->fd < 0) {  // error
    delete client;
    products.at(0).push_back(0);
    break;
  }
  long long int result = reinterpret_cast<long long int>(client);
  products.at(0).push_back(static_cast<double>(result));
  break;
}
:(code)
socket_t* client_socket(const string& host, int port) {
  socket_t* result = new socket_t;
  result->fd = socket(AF_INET, SOCK_STREAM, 0);
  if (result->fd < 0) {
    raise << "Failed to create socket.\n" << end();
    return result;
  }
  result->addr.sin_family = AF_INET;
  hostent* tmp = gethostbyname(host.c_str());
  bcopy(tmp->h_addr, reinterpret_cast<char*>(&result->addr.sin_addr.s_addr), tmp->h_length);
  result->addr.sin_port = htons(port);
  if (connect(result->fd, reinterpret_cast<sockaddr*>(&result->addr), sizeof(result->addr)) < 0) {
    close(result->fd);
    result->fd = -1;
    raise << "Failed to connect to " << host << ':' << port << '\n' << end();
  }
  return result;
}

:(before "End Primitive Recipe Declarations")
_OPEN_SERVER_SOCKET,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$open-server-socket", _OPEN_SERVER_SOCKET);
:(before "End Primitive Recipe Checks")
case _OPEN_SERVER_SOCKET: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$open-server-socket' requires exactly one ingredient (the port to listen for requests on), but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first ingredient of '$open-server-socket' should be a number, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
    break;
  }
  if (SIZE(inst.products) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$open-server-socket' requires exactly one product, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.products.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first product of '$open-server-socket' should be a number (file handle), but got '" << to_string(inst.products.at(0)) << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _OPEN_SERVER_SOCKET: {
  int port = ingredients.at(0).at(0);
  socket_t* server = server_socket(port);
  products.resize(1);
  if (server->fd < 0) {
    delete server;
    products.at(0).push_back(0);
    break;
  }
  long long int result = reinterpret_cast<long long int>(server);
  products.at(0).push_back(static_cast<double>(result));
  break;
}
:(code)
socket_t* server_socket(int port) {
  socket_t* result = new socket_t;
  result->fd = socket(AF_INET, SOCK_STREAM, 0);
  if (result->fd < 0) {
    raise << "Failed to create server socket.\n" << end();
    return result;
  }
  int dummy = 0;
  setsockopt(result->fd, SOL_SOCKET, SO_REUSEADDR, &dummy, sizeof(dummy));
  result->addr.sin_family = AF_INET;
  result->addr.sin_addr.s_addr = Current_scenario ? htonl(INADDR_LOOPBACK) : INADDR_ANY;  // run tests without running afoul of any firewall
  result->addr.sin_port = htons(port);
  if (bind(result->fd, reinterpret_cast<sockaddr*>(&result->addr), sizeof(result->addr)) >= 0) {
    listen(result->fd, /*queue length*/5);
  }
  else {
    close(result->fd);
    result->fd = -1;
    raise << "Failed to bind result socket to port " << port << ". Something's already using that port.\n" << end();
  }
  return result;
}

:(before "End Primitive Recipe Declarations")
_ACCEPT,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$accept", _ACCEPT);
:(before "End Primitive Recipe Checks")
case _ACCEPT: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$accept' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first ingredient of '$accept' should be a number, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
    break;
  }
  if (SIZE(inst.products) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$accept' requires exactly one product, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.products.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first product of '$accept' should be a number (file handle), but got '" << to_string(inst.products.at(0)) << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _ACCEPT: {
  products.resize(2);
  products.at(1).push_back(ingredients.at(0).at(0));  // indicate it modifies its ingredient
  long long int x = static_cast<long long int>(ingredients.at(0).at(0));
  socket_t* server = reinterpret_cast<socket_t*>(x);
  if (server) {
    socket_t* session = accept_session(server);
    long long int result = reinterpret_cast<long long int>(session);
    products.at(0).push_back(static_cast<double>(result));
  }
  else {
    products.at(0).push_back(0);
  }
  break;
}
:(code)
socket_t* accept_session(socket_t* server) {
  if (server->fd == 0) return NULL;
  socket_t* result = new socket_t;
  socklen_t dummy = sizeof(result->addr);
  result->fd = accept(server->fd, reinterpret_cast<sockaddr*>(&result->addr), &dummy);
  return result;
}

:(before "End Primitive Recipe Declarations")
_READ_FROM_SOCKET,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$read-from-socket", _READ_FROM_SOCKET);
:(before "End Primitive Recipe Checks")
case _READ_FROM_SOCKET: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$read-from-socket' requires exactly one ingredient, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first ingredient of '$read-from-socket' should be a number (socket), but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
    break;
  }
  int nprod = SIZE(inst.products);
  if (nprod == 0 || nprod > 4) {
    raise << maybe(get(Recipe, r).name) << "'$read-from-socket' requires 1-4 products, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_character(inst.products.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first product of '$read-from-socket' should be a character, but got '" << to_string(inst.products.at(0)) << "'\n" << end();
    break;
  }
  if (nprod > 1 && !is_mu_boolean(inst.products.at(1))) {
    raise << maybe(get(Recipe, r).name) << "second product of '$read-from-socket' should be a boolean (data received?), but got '" << to_string(inst.products.at(1)) << "'\n" << end();
    break;
  }
  if (nprod > 2 && !is_mu_boolean(inst.products.at(2))) {
    raise << maybe(get(Recipe, r).name) << "third product of '$read-from-socket' should be a boolean (eof?), but got '" << to_string(inst.products.at(2)) << "'\n" << end();
    break;
  }
  if (nprod > 3 && !is_mu_number(inst.products.at(3))) {
    raise << maybe(get(Recipe, r).name) << "fourth product of '$read-from-socket' should be a number (error code), but got '" << to_string(inst.products.at(3)) << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _READ_FROM_SOCKET: {
  products.resize(4);
  long long int x = static_cast<long long int>(ingredients.at(0).at(0));
  socket_t* socket = reinterpret_cast<socket_t*>(x);
  // 1. we'd like to simply read() from the socket
  // however read() on a socket never returns EOF, so we wouldn't know when to stop
  // 2. recv() can signal EOF, but it also signals "no data yet" in the beginning
  // so use poll() in the beginning to wait for data before calling recv()
  // 3. but poll() will block on EOF, so only use poll() on the very first
  // $read-from-socket on a socket
  //
  // Also, there was an unresolved issue where attempts to read() a small
  // number of bytes (less than 447 on Linux and Mac) would cause browsers to
  // prematurely close the connection. See commit 3403. That seems to be gone
  // after moving to recv()+poll(). It was never observed on OpenBSD.
  if (!socket->polled) {
    pollfd p;
    bzero(&p, sizeof(p));
    p.fd = socket->fd;
    p.events = POLLIN | POLLHUP;
    int poll_result = poll(&p, /*num pollfds*/1, /*timeout*/100/*ms*/);
    if (poll_result == 0) {
      products.at(0).push_back(/*no data*/0);
      products.at(1).push_back(/*found*/false);
      products.at(2).push_back(/*eof*/false);
      products.at(3).push_back(/*error*/0);
      break;
    }
    else if (poll_result < 0) {
      int error_code = errno;
      raise << maybe(current_recipe_name()) << "error in $read-from-socket\n" << end();
      products.at(0).push_back(/*no data*/0);
      products.at(1).push_back(/*found*/false);
      products.at(2).push_back(/*eof*/false);
      products.at(3).push_back(error_code);
      break;
    }
    socket->polled = true;
  }
  char c = '\0';
  int error_code = 0;
  int bytes_read = recv(socket->fd, &c, /*single byte*/1, MSG_DONTWAIT);
  if (bytes_read < 0) error_code = errno;
//?   if (error_code) {
//?     ostringstream out;
//?     out << "error in $read-from-socket " << socket->fd;
//?     perror(out.str().c_str());
//?   }
  products.at(0).push_back(c);
  products.at(1).push_back(/*found*/true);
  products.at(2).push_back(/*eof*/bytes_read <= 0);
  products.at(3).push_back(error_code);
  break;
}

:(before "End Primitive Recipe Declarations")
_WRITE_TO_SOCKET,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$write-to-socket", _WRITE_TO_SOCKET);
:(before "End Primitive Recipe Checks")
case _WRITE_TO_SOCKET: {
  if (SIZE(inst.ingredients) != 2) {
    raise << maybe(get(Recipe, r).name) << "'$write-to-socket' requires exactly two ingredient, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _WRITE_TO_SOCKET: {
  long long int x = static_cast<long long int>(ingredients.at(0).at(0));
  socket_t* socket = reinterpret_cast<socket_t*>(x);
  // write just one character at a time to the socket
  long long int y = static_cast<long long int>(ingredients.at(1).at(0));
  char c = static_cast<char>(y);
  if (write(socket->fd, &c, 1) != 1) {
    raise << maybe(current_recipe_name()) << "failed to write to socket\n" << end();
    exit(0);
  }
  products.resize(1);
  products.at(0).push_back(ingredients.at(0).at(0));
  break;
}

:(before "End Primitive Recipe Declarations")
_CLOSE_SOCKET,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "$close-socket", _CLOSE_SOCKET);
:(before "End Primitive Recipe Checks")
case _CLOSE_SOCKET: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$close-socket' requires exactly two ingredient, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_number(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "first ingredient of '$close-socket' should be a number, but got '" << to_string(inst.ingredients.at(0)) << "'\n" << end();
    break;
  }
  if (SIZE(inst.products) != 1) {
    raise << maybe(get(Recipe, r).name) << "'$close-socket' requires exactly one product, but got '" << inst.original_string << "'\n" << end();
    break;
  }
  if (inst.products.at(0).name != inst.ingredients.at(0).name) {
    raise << maybe(get(Recipe, r).name) << "product of '$close-socket' must be first ingredient '" << inst.ingredients.at(0).original_string << "', but got '" << inst.products.at(0).original_string << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case _CLOSE_SOCKET: {
  long long int x = static_cast<long long int>(ingredients.at(0).at(0));
  socket_t* socket = reinterpret_cast<socket_t*>(x);
  close(socket->fd);
  delete socket;
  products.resize(1);
  products.at(0).push_back(0);  // make sure we can't reuse the socket
  break;
}

:(before "End Includes")
#include <netinet/in.h>
#include <netdb.h>
#include <poll.h>
#include <sys/socket.h>
#include <unistd.h>
e>
                                   
                

              

 
                                         

                  
                         
                                   

 
                                                  

                  
                         
                                              

 
                                      

                  
                          
                                             

 
                                      

                  
                          
                                             

 
                           
             
                   
                        

                           

                         






                           
                   

                               

                           


                         
   
 
 
                                                   

                  
                                                         
                                 




                        
                            
                                     




                         
                                     

                  
                                                         
                            


                                  
                                    

                  
                                                         
                            


                                 
                                                            

                  
                                                               
                        



                                           
                                                          

                  
                                                               
                        



                                         

                                  
                   


                          








                                  
                   


                               
                            
                         




                               
 

                                         
                                 

                  
                                  
                   
                           

 
                                                            

                  

                          
                              
                       
                                      
   

                  
                                      
     
                                     
                    
                                        
                       

                                      
                       
                    
                  
                          
          
     
                                 
                     




                                  


                                              

                                    
                                                     
                  
                                                  
                           
                                  


                                        
                           
     
                              

                                    
                                                     
                              
                  
       
                                                    

                                 
                       
       
                                             
                                 
                                           

                        
                                                







                                        
                                                            
                                                                    
                                
                                    

                                                                             

                                
                                                    
                                                                                        
       

          
             
   

 
                                                          


                  
                                   
                           
                     
                           





                       
                                  

                  
                                    



                            
                                                                





                           
          


                   
                                                        

                        
          


                         
                         

                             
                       



                            
                                   
             
                   
                     
                                                        
                           

                                      
                             

   


                     
                     
                     
                                                        
                           

                                      
                               

   
 
                                  
             
                           
                     


                                     
                           

                      

                                                         
                       
                                                         
                          

                           


                                      


                                           

                                                    




                                       
                                                
                     


                                     
                           

                      

                                                         
                       
                                                         
                          

                           





                                           

                                                    

   


                                            
                               
                     


                                               
                           

                      

                                                         
                       
                                                         
                      
                            
                       
                                                         
                          


                           
                         






                                                


                                                    

   
 

                            
                         
                     


                                    
                           
                      
                           
                       
                                                         

                          
                           





                                            
                                                     




                              
                             
                     


                                              
                           
                      
                           
                       
                                                         


                          
                                                         
                          

                           






                                            

                                                     


   



                                                                             
                      
                   
                        







                                          
                         
                   
                        




                                          


                                         
                             
                     


                            
                           

                      

                                                         

                           




                                      

                                               




                                                   
                                 
                     


                                      
                           

                      

                                                         
                       
                                                         
                      
                                                         


                           





                                           


                                                    

   
 
                                   
 
                                 

                  
                                    



                            
                                                                               




                                              
                       
 
## experimental compiler to translate programs written in a generic
## expression-oriented language called 'lambda' into Mu

# incomplete; code generator not done
# potential enhancements:
#   symbol table
#   poor man's macros
#     substitute one instruction with multiple, parameterized by ingredients and products

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

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

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

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

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

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

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

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

scenario atom-is-not-pair [
  local-scope
  s:text <- new [a]
  x:&:cell <- new-atom s
  10:bool/raw <- is-atom? x
  11:bool/raw <- is-pair? x
  memory-should-contain [
    10 <- 1
    11 <- 0
  ]
]

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

def atom-match? x:&:cell, pat:text -> result:bool [
  local-scope
  load-ingredients
  s:text, is-atom?:bool <- maybe-convert *x, atom:variant
  return-unless is-atom?, 0/false
  result <- equal pat, s
]

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

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

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

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

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

scenario cell-operations-on-atom [
  local-scope
  s:text <- new [a]
  x:&:cell <- new-atom s
  10:&:cell/raw <- first x
  11:&: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:text <- new [a]
  x:&:cell <- new-atom s
  y:&:cell <- new-pair x, 0/nil
  x2:&:cell <- first y
  10:bool/raw <- equal x, x2
  11:&: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:text -> out:&:cell [
  local-scope
  load-ingredients
  s:&:stream:char <- new-stream in
  out, s <- parse s
  trace 2, [app/parse], out
]

def parse in:&:stream:char -> out:&:cell, in:&:stream:char [
  local-scope
  load-ingredients
  # skip whitespace
  in <- skip-whitespace in
  c:char, eof?:bool <- peek in
  return-if eof?, 0/nil
  pair?:bool <- equal c, 40/open-paren
  {
    break-if pair?
    # atom
    buf:&:buffer:char <- new-buffer 30
    {
      done?:bool <- end-of-stream? in
      break-if done?
      # stop before close paren or space
      c:char <- peek in
      done? <- equal c, 41/close-paren
      break-if done?
      done? <- space? c
      break-if done?
      c <- read in
      buf <- append buf, c
      loop
    }
    s:text <- buffer-to-array buf
    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?:bool <- end-of-stream? in
      not-end?:bool <- not end?
      assert not-end?, [unbalanced '(' in expression]
      c <- peek in
      close-paren?:bool <- equal c, 41/close-paren
      break-if close-paren?
      first:&:cell, in <- parse in
      *out <- merge 1/pair, first, 0/nil
    }
    # read in any remaining elements
    curr:&:cell <- copy out
    {
      in <- skip-whitespace in
      end?:bool <- end-of-stream? in
      not-end?:bool <- not end?
      assert not-end?, [unbalanced '(' in expression]
      # termination check: ')'
      c <- peek in
      {
        close-paren?:bool <- equal c, 41/close-paren
        break-unless close-paren?
        read in  # skip ')'
        break +end-pair
      }
      # still here? read next element of pair
      next:&:cell, in <- parse in
      is-dot?:bool <- atom-match? next, [.]
      {
        break-if is-dot?
        next-curr:&: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?:bool <- not-equal c, 41/close-paren
        assert not-close-paren?, [')' cannot immediately follow '.']
        final:&: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?:bool <- equal c, 41/close-paren
        assert close-paren?, ['.' must be followed by exactly one expression before ')']
      }
      loop
    }
    +end-pair
  }
]

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

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

def to-buffer x:&:cell, buf:&:buffer:char -> buf:&:buffer:char [
  local-scope
  load-ingredients
  # base case: empty cell
  {
    break-if x
    buf <- append buf, [<>]
    return
  }
  # base case: atom
  {
    s:text, atom?:bool <- maybe-convert *x, atom:variant
    break-unless atom?
    buf <- append buf, s
    return
  }
  # recursive case: pair
  buf <- append buf, [< ]
  first:&:cell <- first x
  buf <- to-buffer first, buf
  buf <- append buf, [ | ]
  rest:&:cell <- rest x
  buf <- to-buffer rest, buf
  buf <- append buf, [ >]
]

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

scenario parse-atom [
  local-scope
  s:text <- new [abc]
  x:&:cell <- parse s
  s2:text, 10:bool/raw <- maybe-convert *x, atom:variant
  11:@:char/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:text <- new [(abc def)]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | <> > >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  x2:&:cell <- rest x
  s1:text, 11:bool/raw <- maybe-convert *x1, atom:variant
  12:bool/raw <- is-pair? x2
  x3:&:cell <- first x2
  s2:text, 13:bool/raw <- maybe-convert *x3, atom:variant
  14:&:cell/raw <- rest x2
  20:@:char/raw <- copy *s1
  30:@:char/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:text <- new [ ( abc  def ) ]  # extra spaces
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | <> > >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  x2:&:cell <- rest x
  s1:text, 11:bool/raw <- maybe-convert *x1, atom:variant
  12:bool/raw <- is-pair? x2
  x3:&:cell <- first x2
  s2:text, 13:bool/raw <- maybe-convert *x3, atom:variant
  14:&:cell/raw <- rest x2
  20:@:char/raw <- copy *s1
  30:@:char/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:text <- new [(abc def ghi)]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | < ghi | <> > > >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  x2:&:cell <- rest x
  s1:text, 11:bool/raw <- maybe-convert *x1, atom:variant
  12:bool/raw <- is-pair? x2
  x3:&:cell <- first x2
  s2:text, 13:bool/raw <- maybe-convert *x3, atom:variant
  x4:&:cell <- rest x2
  14:bool/raw <- is-pair? x4
  x5:&:cell <- first x4
  s3:text, 15:bool/raw <- maybe-convert *x5, atom:variant
  16:&:cell/raw <- rest x4
  20:@:char/raw <- copy *s1
  30:@:char/raw <- copy *s2
  40:@:char/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:text <- new [((abc))]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < < abc | <> > | <> >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  11:bool/raw <- is-pair? x
  x2:&:cell <- first x1
  s1:text, 12:bool/raw <- maybe-convert *x2, atom:variant
  13:&:cell/raw <- rest x1
  14:&:cell/raw <- rest x
  20:@:char/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:text <- new [((abc) def)]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < < abc | <> > | < def | <> > >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  11:bool/raw <- is-pair? x
  x2:&:cell <- first x1
  s1:text, 12:bool/raw <- maybe-convert *x2, atom:variant
  13:&:cell/raw <- rest x1
  x3:&:cell <- rest x
  x4:&:cell <- first x3
  s2:text, 14:bool/raw <- maybe-convert *x4, atom:variant
  15:&:cell/raw <- rest x3
  20:@:char/raw <- copy *s1
  30:@:char/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:text <- new [(]
#? #?   hide-errors
#?   x:&:cell <- parse s
#? #?   show-errors
#?   trace-should-contain [
#?     error: unbalanced '(' in expression
#?   ]
#? ]
#? 
#? scenario parse-error-after-element [
#?   local-scope
#?   s:text <- new [(abc]
#? #?   hide-errors
#?   x:&:cell <- parse s
#? #?   show-errors
#?   trace-should-contain [
#?     error: unbalanced '(' in expression
#?   ]
#? ]

scenario parse-dotted-list-of-two-atoms [
  local-scope
  s:text <- new [(abc . def)]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < abc | def >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  x2:&:cell <- rest x
  s1:text, 11:bool/raw <- maybe-convert *x1, atom:variant
  s2:text, 12:bool/raw <- maybe-convert *x2, atom:variant
  20:@:char/raw <- copy *s1
  30:@:char/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:text <- new [(abc def . ghi)]
  x:&:cell <- parse s
  trace-should-contain [
    app/parse: < abc | < def | ghi > >
  ]
  10:bool/raw <- is-pair? x
  x1:&:cell <- first x
  x2:&:cell <- rest x
  s1:text, 11:bool/raw <- maybe-convert *x1, atom:variant
  12:bool/raw <- is-pair? x2
  x3:&:cell <- first x2
  s2:text, 13:bool/raw <- maybe-convert *x3, atom:variant
  x4:&:cell <- rest x2
  s3:text, 14:bool/raw <- maybe-convert *x4, atom:variant
  20:@:char/raw <- copy *s1
  30:@:char/raw <- copy *s2
  40:@:char/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:&:cell -> out:text [
  local-scope
  load-ingredients
  buf:&:buffer:char <- new-buffer 30
  buf <- to-mu in, buf
  out <- buffer-to-array buf
]

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