Creating stand-alone executables

The muSE interpreter binary can now create extensible stand-alone command line executables. For details, check out the wiki page StandAloneExecutables.

Simple run-time type checking in muSE

The guarded patterns facility can be used to implement a simple type checking facility that can be turned on and off with a global setting. Some functions useful in this situation are defined in examples/rtts1.scm.

muSE has some built-in functions to check types - int?, float?, cons?, vector?, hashtable?, text? and symbol?. The common characteristic of these predicates is to evaluate to their argument if it satisfies the predicate and to () if it doesn't.

If you take a type to be defined by a predicate - the class of objects being all objects that satisfy the predicate - the above predicates together with the combinators ?or, ?and, ?not and ?list-of defined in examples/rtts1.scm can express a broad set of types.

Note: The type checks are all performed at function invocation time. This can be quite a drag on performance. So the definition of decltype in the rtts1.scm file is such that the checks can be turned off by setting the *enable-rtts* to () at the start of the file.

Here's an example (note the use of braces {} around the decltype expressions) -

(define number? (?or int? float?)) ; From rtts1.scm

(define max
  (fn ({decltype n1 number?}
       {decltype n2 number?})
      (if (> n1 n2) n2 n1)))

(define multi-max
  (fn ({decltype n1 number?} . {decltype ns (?list-of number?)})
      (reduce max n1 ns)))

With type checking enabled, multi-max will only be usable with numeric arguments and you have to give it at least one argument.

If you disable type checking, then the above definitions become as though you'd typed -

(define max
  (fn (n1 n2)
      (if (> n1 n2) n2 n1)))

(define multi-max
  (fn (n1 . ns)
      (reduce max n1 ns)))

Google code adds Wiki ...

I've been blogging about aspects of muSE on this site, but am feeling uncomfortable with the organization that's turning out. When I visited the google code pages a few moments ago, I saw that a new Wiki tab has been added. That's the right tool to put in the kind of documentation I've been placing online using the blog and I'll be exploring moving the documentation that needs to be organized over to the wiki and leaving all the "latest scoop", "how to" and "things to do" kind of posts to the blog.

I could've created a separate web site ... ok just call me a lazy one.

Continuations and processes

The call/cc implementation has been revamped to make continuations work only within the processes in which they were captured. This is because none of the alternatives to supporting inter-process continuation invocation seemed clean enough or necessary.

What should happen when a process invokes a continuation that was captured by another process? Should it terminate the current process and join with the process to which the continuation belongs? If that's the case, what about the continuations that were captured in the invoking process? Should they be rendered invalid? Would this whole spaghetti be useful or meaningful?

An alternative is to have the continuation invocation finish evaluation in the invoking process and return with a value like nil or T. Doing that, however, means different behaviour when invoking a continuation in the same process it was captured in versus invoking a continuation captured in a different process. In the former case the invocation never completes evaluation whereas in the latter case it does.

Due of all of that, I've disabled invocation of continuations across process boundaries. Any possible use for that can be satisfied by the message passing mechanism (I think), which is simpler and more comprehensible anyway.

Erlang style processes in muSE

muSE now has an implementation of co-operative message passing processes in the same spirit as Erlang. The source code canbe obtained from the processes branch.

muSE processes provide an abstraction that let you think of your program as concurrently acting entities without worrying about the actual order in which the operations are actually being performed by the processor. Evaluation of muSE expressions may be pre-empted at graph reduction boundaries to pay some attention to other processes. Switching between processes is fairly efficient (close to setjmp + longjmp in C) and it is even possible to run 10000 processes without bringing down your machine to its knees, granted that each process will run pretty slowly on the average in that case though.

Spawning processes

(spawn thunk [attention])

Spawns off the given thunk (a function that takes no parameters) into a separate process. The thunk is evaluated in a loop, until it returns a non-nil value. Once the thunk returns with a non-nil value, the process dies. This is thunk's way of saying "I'm done." The (optional) second argument to spawn is an attention value that tells the muSE scheduler how much attention it should give to the created process before switching to another. The default value is 10. Play around until you find something that suits you. The processes are all scheduled in a simple round-robin manner for now.

The spawn expression itself evaluates to the process-id of the created process. The process id is not a number as is usual in most systems, but is actually a native-closure. The only two uses for the pid are to compare two pids for equality and to pass messages to the process it identifies.

To pass a message, simply use the process ID like a normal function. Its entire argument list will be placed as a single message in the process's message queue.

Pausing a process

(run [timeout-microseconds])

Pauses a process for the given timeout period, yielding time to other processes. If the timeout is omitted, the process is suspended for ever.

Receiving messages in a process

(receive ...)

Retrieves the next message in the process's mailbox. The message has the format

(pid . values)

where pid is the id of the process that sent the message and values is the list of arguments that it supplied to the message sending operation.

The result of a (receive...) expression is designed to be used with muSE's pattern-matching case construct as follows -

(case (receive)
   ((pid ...msg-pattern-1...) action-1)
   ((pid ...msg-pattern-2...) action-2)
   ...)

The receive primitive has four forms -

(receive)

Pauses the process until a message is available in the process's mailbox and evaluates to the message. This will always evaluate to a valid message.

(receive timeout-microseconds)

Pauses the process for at most timeout-microseconds. If there is mo message in the process's mailbox for more than timeout-microseconds, it evaluates to () which is muSE's false value.

(receive pid)

Waits for and retrieves the next message from the process with the given pid.

(receive pid timeout-microseconds)

Similar to the previous one, but times out with a () value after timeout-microseconds.

Controlling concurrency

(atomic ...expressions...)

From the point of view of a single process, atomic works exactly like do - evaluating all the expression in turn and itself evaluating to the value of the last expression in the series. From the point of view of the cluster of running processes, it does not yield any time to any other process until all its expressions are evaluated.

atomic expressions may be nested to arbitrary depths. You can forcibly yield to other processes however, if you use any of the pausing functions receive and run.

Process identity

(this-process)

Evaluates to the pid of the process in which it is evaluated.

Embedding issues

For muSE, it is important to consider how these processes interact when embedded in a C/C++ based application. The application can make calls to the muSE API to evaluate expressions. These calls are always evaluated in the "main process" using the main application's C stack. Each muSE process has its own C stack and won't interfere with the main C stack. The entry and exit processes for this case will always be the main process. Other processes get a chance to execute only when within a muSE API call and therefore will not interfere with the application's execution when not running muSE code.

Exception mechanism

muSE had so far lacked the facility to raise exception conditions and handle them in code that's specified non-locally. One could conceivably use the call/cc construct to implement raising exceptions, but capturing a continuation to evaluate an expression that often won't invoke the continuation turns out to be expensive in terms of memory - capturing a continuation copies the stack in muSE.
As of version 73 in the processes branch, a simple exception raising and handling mechanism has been added to muSE. There are two new primitives involved -

(raise ...args...)

The raise primitive is used to flag an exceptional condition and results in all the established handlers being tried one by one until one of them can be found to handle the condition. A handler (which is a function) is taken to accept an exception for handling if its argument pattern matches the pattern of arguments to the raise expression that raised the exception.

(try expr handler1 handler2...)

The try block wraps the expr with handlers that get tried when any sub-expression of expr raises an exception.

Any muSE object can be used in the place of a handler. If the object is a function, then its arguments have to pattern match against the exception raised in order for its body to be evaluated as the result of its try block. If the object is not a function, its value is used as the result of the try expression as is. For example -

(try (if (< a b) 
         (- b a)
         (raise 'NotInOrder a b))
   0)

will evaluate too 0 if a >= b.

A function used as a handler needs to have its arguments in a special order -

1. The first argument to the handler is an exception object.


2. The remaining arguments are the same list of values passed to the raise expression that raised the exception.

For example -

(fn (ex 'NotInOrder x y) ...)

can be the signature of a handler that handles the 'NotInOrder exception raised by the previous example. The ex argument's sole purpose is to let you resume the computation from the raise expression with a new valid value as the result of the raise. The ex object is actually a (cheaper than call/cc) continuation that you can invoke with a single argument that will resume the computation in such a manner. To expand on the previous example,

(try 
  (do (write "Difference = "
             (if (< a b)
                 (- b a)
                 (raise 'NotInOrder a b)))
      (write "Product = " (* a b)))
      
  (fn (ex 'NotInOrder x y)
      (ex (- x y))))

In the above form, the exception condition is corrected by reversing the arguments of the subtraction operation. If the handler did not invoke the exception object to resume the computation, its result value is used as the result value of the try block. Trivial example, yes, but serves to illustrate the point.

Processes branch

The processes branch of muSE has now reached a fair degree of completeness. This post documents the facilities available as of version 82, whose snapshot is available in the tag v0.2cp. I intend to make the processes branch the main trunk when the functionality is a bit more tested.

The processes branch implements a few significant features over and above the standard muSE engine on the trunk -

Processes

A simple implementation of Erlang style message passing processes in order to express concurrent computations. Primitives added are spawn, receive, atomic and run.

Process-local continuations

Continuation support modified to work within a process. Continuation invocation across process boundaries is forbidden. No new primitives.

Process-aware networking

muSE had some simple s-expr based communication functions all along. This branch now has these functions process aware - i.e. reading from a network port will not stall processes. A polling mechanism (which is invisble at the scheme-level) is used to handle all connections.

Resumable exception mechanism

New primitives try and raise provide the means to raise, handle and resume exceptional conditions. This is something muSE had been lacking all along and was badly needed.

Static guarded patterns (minor)