R6 is underway, according to schemers.org. I've been looking through
SISC to get a feel for how it works, and I thought the authors might
want to comment on both the direction of SISC, and the direction of
Scheme itself, with respect to vector processing.
Arthur Whitney's K language (http://www.kx.com) is a commercial
product/language designed, mostly, for the financial industry. It's
from the APL family; as such, you find very terse source code, where
every punctuation mark means a great deal. While I find the syntax of K
powerful but tough, I find the verb/adverb sytem within it to be very
powerful. I keep thinking that Scheme's power is greatly multiplied if
the language can take on some of the vector processing capabilities of
the APL family.
A quick example: When we add two numbers (+ 2 4) we get a result, 6. We
can form a vector like this: '#(1 2 3), but we can't do this (+ 2 '#(1 2
3)). If Scheme had vector processing capability, the answer would be
#3(3 4 5). Similarly, if we do (+ '#(1 2 3) '#(4 5 6)) the answer would
be #3(5 7 9).
Switching to K for a second, we can do this: (1;2;3)+(4;5;6), which
results in 5 7 9. K has _adverbs_, which modify what the base verbs (in
our case +), do. So in K we can also write (1;2;3) +\: (4;5;6), which
modifies + with "each-left", and results in:
(5 6 7
6 7 8
7 8 9)
The \: following the + symbol is the EACHLEFT adverb; it tells K to call
the + function with each member of the left operand and the entire right
operand.
K has an exceedingly well designed set of interacting verbs (functions)
and adverbs (such as EACHLEFT). Here's a quick list of verbs (from the
K interpreter):
\+
Dyad Monad
+ plus flip
- minus negate
* times first
% divide reciprocal
& min/and where
| max/or reverse
< less upgrade
> more downgrade
= equal group
^ power shape
! mod/rotate enumerate
~ match not
, join enlist
# take/reshape count
_ drop/cut floor
$ form/format format
? find/invert unique invert-guess
@ at atom m-amend d-amend
. dot value m-amend d-amend
f[x] is f .,x is f@x is f x
f[x;y] is f .(x;y)
And here is the list of adverbs (from the K interpreter):
f' EACH
d\: EACHLEFT
d/: EACHRIGHT
d': EACHPRIOR
d/ OVER f/[init;...] RECUR
d\ SCAN f\[init;...] TRACE
m/ CONVERGE n m/ DO b m/ WHILE
m\ CONVERGE n m\ DO b m\ WHILE
f(function) d(dyadic) m(monadic) b(boolean)
scatter selection matrix'
transitive closure vector/ vector\
state transition matrix/ matrix\ matrix':
compose 2+ 8$ ~= ~< ~> *|:(first reverse)
project pv:{[c;t;d]+/c*d^t} pv[c:.1 .1 1.1;t:1 2 3]d:%1.1
invert pv[c;t]?.97 pv[c;;d]?.98 pv[;t;d]?.99
modify @[0 0 0;1 1 0 2 2 0 1 2;+;!8]
iterate 9{+':0,x,0}\1 9(|+\)\1 1.0
converge (1+%:)\1.0 {x\'!#x}parent:0 0 1 1 0
integrate +\2 3 4 *\2 3 4
differentiate -':0 2 5 9 %':1 2 6 24
verbs default to dyad. use(:) for monad, e.g. (<;<:)
The STL derives a good deal of its power from providing a similar set of
well design functions that can interact to produce more complex
behaviors. Scheme R5 provides functions like "map" that understand how
to operate on lists, but nothing like the powerful set of primitives
that K has.
Bending a LISP-family language to do this kind of vector processing is a
bit tricky, but it can be done. Creation of vectors of primitive types
is not difficult (SRFI 4 takes a small step in this direction). Within
SISC, vectors of primitive types would be easy to implement. Next comes
modification of primitives, such as +, to be able to handle vectors
correctly. Again, this is relatively trivial, when working at the
primitive level.
It become more difficult when we want to give a programmer the ability
to write vector-capable functions. We can clearly write functions that
check types at runtime with is-vector-XXX?. This is what the primitives
do on the inside; they check the types of their arguments and select an
appropriate method of calculation. There's clearly some crossover with
generic procedures, though. If we wanted to code our own + procedure,
we might want a syntax that would allow us to declare various forms of
it (+ int double) (+ float float), and have the "right" one called.
If is-a tests can be made very efficiently, generic procedures might not
be necessary. The K system gains its speed by handling as atomic vector
operations many computations that would require extensive iteration in
other languages.
The adverb construct that K uses isn't too problematic. I can define
each-left like this:
(define (each-left func left right)
(if (null? left)
left
(cons (func (car left) right)
(each-left func (cdr left) right)))
)
then do: (each-left + '(1 2 3) 5) to get (6 7 8). If the primitive +
knew how to deal with vectors and lists this would work directly on
statements like (each-left + '#(1 2 3) '#(5 6 7)). This isn't totally
desirable, though, because at the interpreter level we want to be able
to detect the combination of each-left and + (for example), and execute
a potentially optimized version.
In particular, in an interpreter like SISC, we want to avoid continously
transforming values into and out of Value objects. We want to be able
to operate on the primitives directly. Looking at the SISC code, I
wonder about the practice of having primitives return new Value objects
as their result. SISC does this:
Value result = mult(Value a, Value b)
Would it not be more efficient to do (at least for numerics):
mult(Value result, Value a, Value b)
SISC's use of subclasses for various Value types makes this difficult,
as a single Value can't hold all possible types. Still, in tight loops,
a great deal of heap allocation can be avoided by using this style to
hold intermediate results.
Blending vector capability into Scheme together with a well-chosen set
of functions (such as those in K) brings yet another style of
programming into Scheme's domain, and substantially increases its
usefulness for many kinds of development. Finding a way to combine such
a capability with existing work on collections is a challenge; ideally,
I should be able to use an each-left adverb on lists, collections and
vectors. I note that SISC author Scott Miller has written SRFI 44 on
collections.
Are the authors of SISC interested in this kind of experiment? Is this
kind of discussion suited to the SRFI process? Has vector handling been
covered in the past?
Ross Judson
-------------------------------------------------------
This SF.Net email is sponsored by: IBM Linux Tutorials
Free Linux tutorial presented by Daniel Robbins, President and CEO of
GenToo technologies. Learn everything from fundamentals to system
administration.http://ads.osdn.com/?ad_id70&alloc_id638&op=click
|
