Denver-Augusta-Harrisburg

From Esolang
Jump to navigation Jump to search

Denver-Augusta-Harrisburg is a concurrent-message-passing programming language.

Execution of a Denver-Augusta-Harrisburg program starts with the main thread and the system thread. The main thread executes the main routine with the system thread as its first argument and can spawn more threads. A thread can send messages to and receive messages from other threads, including itself. A message consists of a thread. When receiving a message, the sender thread is also received. Execution of the program ends when the main thread exits.

Grammar

 program = routine-definition*
 
 routine-definition = routine-identifier variable-identifier* body
 body = '{' statement* '}'
 
 statement = guard* (assignment-statement | break-statement |
                     continue-statement | loop-statement | message-statement)
 assignment-statement = variable-identifier '<' (expression | spawn)
 break-statement = loop-identifier? 'break'
 continue-statement = loop-identifier? 'continue'
 loop-statement = loop-identifier? body
 message-statement = '[' message-statement-arm* ']'
 
 expression = variable-identifier | 'null' | 'self'
 guard = expression? ('=' | '!') expression
 spawn = '[' routine-identifier expression* ']'
 
 message-statement-arm = guard* (receive | send) body
 receive = variable-identifier variable-identifier '<' expression*
 send = expression '<' expression
 
 loop-identifier = identifier
 routine-identifier = identifier
 variable-identifier = identifier

Comments begin with == and extend to the end of the line.

Identifiers are uninterrupted sequences of non-space characters, excluding =, !, [, ], {, }, <, and may not be break, continue, null, or self. Space characters serve to separate tokens and are otherwise ignored.

Routines

A routine is declared with its routine identifier, a list of parameters, and a body. The routine identifier is also the loop identifier of the body. The parameters must be distinct from each other.

Routine identifiers must be unique within a program.

When a thread is spawned, it executes the routine it was spawned with by executing the statements in its body in a loop. The thread exits when the routine body is exited.

Statements

Every statement may have a guard list, where the statement is executed only if each item in the guard list is satisfied. A guard list may be empty.

If a guard is expression = expression, then the rest of the statement is only executed if the two expressions evaluate to the same thread.

If a guard is expression ! expression, then the rest of the statement is only executed if the two expression evaluate to different threads.

If a guard is = expression, then the rest of the statement is only executed if the expression evaluates to a thread that has not exited. It is not guaranteed that that thread has not exited when the rest of the statement executes. The null thread is always considered to have exited.

If a guard is ! expression, then the rest of the statement is only executed if the expression evaluates to a thread that has exited.

Assignment statement

An assignment statement sets the variable to the value of the expression. If the expression is a spawn expression, it spawns a new thread and set the variable to the new thread. The new thread executes the routine specified in the spawn expression, with its parameters set to the arguments in the spawn expression.

Other than spawn expressions, expressions are a variable, null, or self. A variable evaluates to the value the variable was last assigned, either by an assignment statement or a receive arm of a message statement, or the null thread if not previously assigned. null evaluates to the null thread. self evaluates to the currently executing thread.

Break statement

A break statement exits the specified, or, if not specified, innermost enclosing loop statement or message statement or routine body.

Continue statement

A continue statement continues executing at the beginning of the specified, or, if not specified, innermost enclosing loop statement or message statement or routine body.

Loop statement

A loop statement specifies a list of statements that are executed in a loop until exited. A loop can be exited by a break statement for the loop or by a break or continue statement for an enclosing loop statement, message statement or routine body.

Message statement

A message statement specifies a list of arms. An arm may have a guard list, for which each item must be satisfied for the arm to be active. An active arm attempts to send to a thread, receive from any in a list of threads, or receive from any thread. If there are no active arms, execution continues to the next statement. If there are multiple active arms, execution is blocked until one or more active arms can succeed. One of the arms that can succeed will succeed, and its body will be executed, then, unless the body of the successful arm exits the message statement, the message statement is executed again. If execution is blocked because every active arm is attempting to send to an exited thread or the null thread, or is attempting to receive only from exited threads or the null thread, execution continues to the next statement.

A send arm sends its right argument to its left argument.

A receive arm assigns the message received to the first variable on the left and the sender to the second variable on the left. The first variable and the second variable must not be the same variable. The arguments on the right is a list of sender threads. If the list is not empty, it can only receive from a thread in the list. If the list is empty, it can receive from any thread.

If an arm has an = expression guard and another arm has a ! expression guard, and the expressions evaluate to the same thread, at most one of the two arms will be active, depending on other guards. If there are no other guards, exactly one of the two arms will be active. If the arm with the = expression guard executes, it is not guaranteed that the thread has not exited since the guard was passed.

Loop identifiers

A loop identifier is associated with a routine, a loop statement, or a message statement. break and continue statements may specify a loop identifier to specify which loop statement or message statement they apply to, or if they apply to the body of the routine.

The scope of the loop identifier is the body of its loop statement or the bodies of every arm of its message statement.

The routine identifier is the loop identifier of the routine body and its scope is the routine body.

A loop identifier must not duplicate any other loop identifier that is in scope.

Variables

All variables are scoped to the routine in which it is used and, except for the routine parameters, are initially set to null. The routine parameters, listed after the routine identifier in the routine declaration, are initially set to values specified as arguments in the spawn expression. If there are fewer arguments provided in the spawn expression than the number of routine parameters, the remaining parameters are set to null.

Threads

A new thread is spawned when an assignment statement is executed with a spawn expression. The variable on the left-hand side of the assignment statement is assigned the new thread. The new thread executes the routine specified by the routine identifier in the spawn expression, and its parameters are set to the arguments specified in the spawn expression. If there are more parameters than arguments, the remaining parameters are set to null. If there are more arguments than parameters, the remaining arguments are ignored.

There are also some special threads.

Main thread

The main thread is spawned when the program starts and executes the main routine. If it has parameters, the first parameter is set to the system thread. Any additional parameters are set to the null thread.

Null thread

Uninitialized variables are set to the null thread, which never sends messages and ignores any message it receives.

System thread

The system thread is passed as the first parameter to the main routine in the main thread.

The system thread has a list of threads that provide various services. Sending any item in the list to the system thread causes the system thread to send the next item in the list to the sender. The first item in the list is the system thread itself. Sending the last element in the list or a thread not in the list to the system thread causes the system thread to send the null thread to the sender.

The list of threads contains the system thread, the input thread, and the output thread.

Input thread

When anything is sent to the input thread, if the next bit of input is 1, the input thread sends the input thread to the sender. If the next bit of input is 0, the input thread sends null to the sender. If there is no more input, the input thread exits.

There is no guaranteed ordering if multiple threads send to the input thread.

Output thread

The output thread never sends any messages. If it receives null, a 0 bit is output. If it receives anything else, a 1 bit is output.

There is no guaranteed ordering if multiple threads send to the output thread.

Examples

cat

 main system {
   [in=null  system < system {[in  _ < system {break}]}]
   [out=null system < in     {[out _ < system {break}]}]
 
   [state=null in < self {state < in}
    state=in   b _ < in  {state < out}
    state=out  out < b   {state < null}
   ]
   break
 }

lock

 lock locker {
   == send self to lock to acquire lock
   == send null to lock to release lock
   == send anything else to lock to query lock
   == lock always responds with lock holder or null if not held
   [msg sender < {
     [
      == acquire
      msg=sender locker=null sender < sender {locker < sender break}
      msg=sender locker!null sender < locker {break}
 
      == release
      msg=null locker=sender sender < null   {locker < null break}
      msg=null locker!sender sender < locker {break}
 
      == query
      msg!sender msg!null sender < locker {break}
     ]
    }
   ]
 }

list

 cons car cdr {
   == send null to get car
   == send anything else to get cdr
   [sender=null op sender < {}
    sender!null op=null sender < car {break}
    sender!null op!null sender < cdr {break}
   ]
   sender < null
 }

stack

 stack nil {
   == send nil to stack to pop, empty stack returns nil
   == send anything else to push
   serve [
     msg sender < {
       msg=nil [
         list=null sender < nil {serve continue}
         list!null list < nil {
           [car _ < list {
               sent-car < null
               got-cdr < null
               [sent-car=null sender < car  {sent-car < self}
                got-cdr=null  list _ < list {got-cdr < self}
               ]
               serve continue
             }
           ]
         }
       ]
       msg!nil list < [cons msg list]
     }
   ]
 }

tape

 exited{break}
 
 tape ? + - {
   == send ? to read
   == send + to advance one element
   == send - to rewind one element
   == send anything else to write
   == unwritten elements default to null
   head < null
   nil < [exited] == use exited thread as a private constant
   fwd < [stack nil]
   bwd < [stack nil]
   serve [
     msg sender < {
       msg=? {[sender < head {serve continue}]}
       msg=+ {[bwd < head {[fwd < nil {[head _ < fwd {head=nil head < null serve continue}]}]}]}
       msg=- {[fwd < head {[bwd < nil {[head _ < bwd {head=nil head < null serve continue}]}]}]}
       msg!? msg!+ msg!- {head < msg}
     }
   ]
 }

References