experimental mapping syntax with ellipsis

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

experimental mapping syntax with ellipsis

Per Bothner
I checked in a new *experimental* syntax for iterating/mapping over
generalized sequences.  It's based on the '...' (ellipsis) syntax
used in syntax-rules patterns and templates.

Remember the new pattern-based definition syntax:

   (! PATTERN VALUE)

In the simple case:

   (! var value)

is (roughly) the same as:

   (define var value)

The syntax of PATTERN is quite limited (for now) but you can do:

   (! [x y z] value)

which succeeds if value evaluates to a sequence of length 3,
in which case the items are bound to respective x, y, and z.

Where it gets interesting is we allow the '...' (ellipsis)
notation from syntax-rules:

   (! [x r ...] value)

This succeeds if value is a sequence with at least 1 element,
in which case x gets bound to the first element, and r gets
bound to the "rest of the elements".  But the variable r is not
a regular variable, and is only valid in an expression that is
*also* followed by '...', just like in syntax-rules.  For example,
if value is [11 12 13 14] then:

   [(+ 100 r) ... (2 * x)]

evaluates to:

   [112 113 114 22]

Fr want of a better name, I use the name "scan variable"
for a variable defined in an ellipsis pattern (such as r).
A "scan context" expression is an expression followed by '...'
(such as (+ 100 r)).  A scan variable can only be used
in a scan context expression.  A "scan sequence" is the
sequence matched by a scan variable (such as [12 13 14]).

In general:

   (OP A B SEXP ... Y Z)

is syntactic sugar for:

   (OP A B @(map (lambda (r1 r2) SEXP) q1 q2) Y Z)

assuming r1 and r2 are scan variables referenced in SEXP,
and q1 and q2 are the scan sequences matched by r1 and r2.

Another example: The inner product of two vectors is the
sum of pairwise multiplying their elements.

(define (inner-product vec1 vec2)
   (let (([v1 ...] vec1) ([v2 ...] vec2))
     (+ (* v1 v2) ...)))

(inner-product [5 4 3] [10 15 20]) ==> 170

Later the plan is to allow patterns in parameters:

;; Note yet working:
(define (inner-product [v1 ...] [v2 ...])
   (+ (* v1 v2) ...))

(This depends on the pattern/apply-rewrite I'm working on.)

Instead of using an ellipsis pattern, you can use the 'scan' macro:

(define (inner-product vec1 vec2)
   (+ (* (scan vec1) (scan vec2)) ...))

(scan VEC) creates an anonymous scan variable that ranges
over the scan sequence VEC.  'scan' is the inverse operation
of '...', which is a "collect" operation".

This is all very experimental.  For example nested patterns
(such as [[A B] ...]) don't work.  Things are poorly optimized.
Think don't work with sequences that aren't java.util.List.
And no doubt more problems.

I have some idea for extensions to make this a general
iteration framework, including the functionality of
Java 8 streams features flat-map, and filter, as well
as short-circuiting (like a 'while' statement).

I also want to support lazy and recursively-defined sequences.

The plan of course is for the compiler to (unlike Java 8
steams) expand this to efficient code similar to hand-written
loops, like we already do for map and for-each.  I'm not
sure what to do for parallelism: Possibly translate into using
Java 8 streams, where possible.
--
        --Per Bothner
[hidden email]   http://per.bothner.com/