Balancing Scheme expressions containing parentheses, brackets and braces.
A practical application of callbacks from Scheme to Applescript - as implemented in Scheme-OSA application
Callbacks
A Scheme callback, as defined for our purposes, is a means by which a Scheme interpreter asks the Scheme-OSA bridge to evaluate some piece of foreign code on its behalf. The mechanism involves marking the Scheme response as a 'callback, attaching a foreign code (directly or indirectly) to be evaluated by Applescript or indirectly by Cocoa, and putting itself in a wait mode in order to read possibly useful results from the foreign calculations.
The normal mode of the bridge operation is simple: user types some Scheme expression into the input text view of Scheme-OSA application, the expression is sent via input pipe to Scheme interpreter, the interpreter computes the results and sends them back via its output pipe to the bridge, and the bridge displays the results in the output text view.
The callback mode is more complicated, since there are extra round trips to complete the transaction, and some data marshalling - simple as it is - from Scheme to Applescript and back. For example, this Scheme expression:
(*
(ask-for-number "enter odd number" 3)
(ask-for-number "enter even number" 20))
uses a wrapper of an applescript code from our tiny GUI library to prompt a user for some numeric data. As usually, this code is initiated by a user on the bridge side, but once it gets to the Scheme interpreter it causes the latter to issue two callbacks. Both callbacks invoke GUI dialogs, a user enters requested numbers into text fields of dialog boxes (defaults: 3 and 20 are for lazy users, :-)), and both numbers are returned to Scheme. From then on everything looks like in the normal mode of operation: Scheme mutiplies the received numbers and returns the final result (default: 60) to the bridge - which then displays it in output text view.
[A side note: Practical implementation of the above mechanism is more complicated than that, due the fact that the Scheme-OSA interaction is asynchronous: it is sequential, but not synchronous. In other words, bridge does not wait for Scheme interpreter to complete its computations, but goes away letting other appplescript applications to do their jobs. The GUI thread of Scheme-OSA but will be notified by a special event when Scheme response is to be read from a buffer. In meantime a background thread collects all characters that Scheme sends through its output pipe -- until it senses that it is time to send a "time-to-consume" notification to the main thread.]
This script provides some Scheme utilities to be used by Scheme-OSA bridge to perform paren/bracket/brace balancing of Scheme code, which is either typed into, dragged to, or copied to the input text view from other editors.
Description of procedures
Below are two procedures:
1. (balance-stream port)
2. (balance-range k)
The first one is a pure Scheme procedure, which you can test in any environment and any input port, including Scheme-OSA.
Examples:
(define p (current-input-port))
(balance-stream p)()rubbish@ ==> 1
(balance-stream p)(string-append "abc" "efg")rubbish@ ==> 26
(balance-stream p)(string-append "ab[c" "efg")rubbish@ ==> 27
(balance-stream p)((string-append "ab[c" "efg")rubbish@ ==> -1
The second one, the wrapper around the first one, is designed for consumption by Scheme-OSA bridge, to set a new text selection that visualizes the user-activated paren/bracket/brace balancing, or lack of such.
It is used as follows:
1. User moves the insertion point just in front of any "open" character in input text view; that is, one of '(open-paren open-bracket open-brace) and then presses the option-command-B keys, or selects the "Balance" commmand from the Text menu in the menu bar.
2. Scheme-OSA bridge passes the command "(balance-range k1)" and a stream of characters following the insertion point k1 to Scheme interpreter.
3. Scheme interpreter computes a list '(k1 k2) indicating a range of characters that are balanced by a "close" character; that is, one of '(close-paren close-bracket close-brace) characters, which match the opening character. After marking it as a callback and attaching to it an Applescript code the range is sent back to bridge for evaluation.
4. The bridge recognizes it as callback, and passes it to AppleScript runtime for compilation and evaluation. The runtime colorizes the computed range as a new selection and the computed range is returned back to Scheme.
5. Scheme, having no further use for this result, just echoes it back to the bridge.
6. Bridge displays it - as any other Scheme response destined for the direct consumption (i.e., not a callback) - in the output text view.
Why calling Scheme for balance computation?
It would seem that the problem of paren/bracket/brace balancing could be easily solved via regular expressions mechanism. And since we have access to one such regex library for Applescript, "Satimage Osax"[1], we could handle the balancing at the Applescript level with the help of Satimage -- without a need for calling back to Scheme. After all, we use Satimage's regular expressions for text coloring.
Unfortunately, Satimage - as most other regex libraries - does not support recursive patterns in regular expressions.
Let us see what others have to say on a subject of a code balancing. The following is a quote from the TextWrangler[3] editor manual:
Without the use of recursion, the best that can be done is to use a pattern that matches up to some fixed depth of nesting. It is not possible to handle an arbitrary nesting depth. Perl 5.6 has provided an experimental facility that allows regular expressions to recurse (among other things). It does this by interpolating Perl code in the expression at run time, and the code can refer to the expression itself.
Obviously, Scheme-OSA cannot support direct interpolation of Perl code at the Applescript level. There are two choices however: one can escape to shell via "do shell script" and then call the Perl engine, or one can call Scheme to perform the recursive balancing via a proper tail-recursive procedure, such as the 'balance-range. Since Scheme is the integral part of Scheme-OSA, we have chosen the latter approach for obvious resons...
Perceived efficiency
No noticeable delays are felt when running this code on G4 laptop, even when the input stream (a Scheme source code following the insertion point in input text view) becomes huge.
Why combination of keys: option-command-B for "Balance" command?
Two of the best ASCII editors for Mac OS X, the commercial BBEdit[4] and its free cousin TextWrangler[3] use command-B as the key sequence for the invocation of the "Balance" command. However, since one of our goals is to provide IDE working in a rich text environment, not just the ASCII one, we need to preserve the command-B for invocation of the "Bold" action, typical in any rich-text editing environment. Consequently, we choose option-command-B for the "Balance" command. If you do not like this, you can easily remap some of the keys of the main menu of the Scheme-OSA application, including option-command-B.
Limitations
There are several limitation to the algorithms presented here.
1. The algorithms work only in the "forward" mode, which means that the insertion point must be positioned just before an "open" character. A good balancer should also work "backwards" - from the last "close" character to the first matching "open" character, and "from the middle", where insertion point is placed somewhere between an "open" and a "close" characters.
I'll work on it later.
2. Current implementation correctly ignores any open/close characters that appear within strings or within line comments. However, it does not ignore balancing within the Scheme block comments. Working on it...
3. A temporary End-Of-Data hack, described below
A temporary End-Of-Data hack
In a rush to get a prototype working, I have introduced #\@ character as a End-Of-Data marker. Some sort of a marker is needed since the pipe between Applescript and Scheme is always open. In normal circumstances the marker is not actually needed since we can use Scheme prompts to decide whether or not the data is complete. In the postfix i/o cases, such as this one, the data marker is needed, because we have no other means to signal End-Of-Data; the open pipe will never send End-Of-File marker.
But we have to keep the input pipe to Scheme open, otherwise a Scheme interpreter would exit prematurely, if we were to send "close-pipe" command after writing data to Scheme. Consequently, no EOF object is ever to be expected on the pipe. But using character #\@ as a EOD marker is not a good choice: after all #\@ is as legal as any other ASCII character: it can be used in strings, symbols or identifiers.
Possible other solutions are:
1. Marking EOD by a sequence of ASCII characters, rather than by a single one. Such algorithms are known, but efficiency would somewhat suffer due to look ahead and backtracking.
2. Using a higher order character with a code point x, such that 127 < x < 256. Not every Scheme implementation supports this. Petite Chez Scheme for example, although happy with Unicode and UTF8 when reading strings or symbols, will crash when individual characters are read or examined.
3. Redesigning read-char, so
(read-char (current-input-port))#\bel
would indeed recognize #\bel (or other such control character) as a single character, and not as # followed by \bel.
4. Making exception to this and other i/o procedures and using temporary files or named fifo pipes, rather than the one standard input pipe. I'd rather not to introduce any exceptions to this simple model.
5. Redesigning the signature of the "balance-range" function to accept explicit strings, rather than implicit streams. This means that we would have to prepare a string like this: "(balance-string \"quoted-text-of-input-text-view\" k1)".
This works, but onus is on Applescript to double-quote every string that might appear in the text of the input text view. It follows that the text
a. must be surrounded by "\"" substrings
b. must have every double-quote character preceded by \\.
It is the point b. that makes such algorithm very inefficient, since such quoted string must be assembled on character-by-character basis. Although acceptable for short pieces of code, the performance is not acceptable when balancing even the smallest pieces of code in typically-sized Scheme modules.
References:
[1] "Satimage Osax" by Satimage-software, www.satimage-software.com
[2] osax - (Open Scripting Architecture eXtension) is the nickname for the Scripting Additions', the plug-ins for AppleScript.
[3] TextWrangler - free Mac OS X editor, by Bare Bones Software, http://www.barebones.com
[4] BBEdit - commercial Mac OS X editor, by Bare Bones Software, http://www.barebones.com
No comments:
Post a Comment