Scheme - recursive lambda, collections

Author

recursive lambda, collections

RJudson

2004-07-02, 3:59 pm

I've been playing with a little collections API for Scheme, and
encountered a newbie sort of problem -- is there a straightforward way
for a procedure defined in a lambda to call itself recursively? I can
see how to do it with continuations, I think, but I'm wondering if
there's a simpler way; it's not jumping out at me from R5.

Thanks to Miller and Radestock's excellent SISC implementation, I've
been able to do some interesting experimentation. Finding the right
"style" for collections under Scheme is a bit tough -- without
type-based dispatching you get solutions that are less than desirable
(function naming strategies like tree-map-add, etc). Those require
you to know what kind of structure you're working on at all times.
Being a novice Schemer (last Scheme I did was in University 15 years
ago ;) I came up with a example, and thought I'd ask the experts about
its merits.

The essential idea here is that collections have generic operations, a
behavioral specification (map, set, list, bag, etc), and a
representation. We want to be able to adapt conventional Scheme
structures (like association lists) and use them as collections, and
we want to be able to define more sophisticated collections as well,
such as BTrees. We don't want different calls for different
structures. This sounds like a job for generic dispatch, but even
that feels a little too "object-oriented" and not quite Scheme enough.

Here's the idea. First, a little code from the user's perspective:

(define sample (list (list 'a 1)(list 'b 2)(list 'c 3)))

(get* map-alist sample 'b) => 2
((get* map-alist sample) 'b) => 2
(((get* map-alist) sample) 'b) => 2

(add* list-list sample (list d 4))
((add* list-list sample) (list d 4))
(((add* list-list) sample) (list d 4)))

(let ((sample-mv (map-values* map-alist sample))(total 0))
(sample-mv (lambda (value) (set! total (+ total value)))))

The desired procedure is an intersection of operation, behavior, and
representation. Using a little currying trick, we can capture
convenient intermediate states and get a more specialized procedure
that's simpler to use.

Here's an incomplete sketch implementation, for discussion. It uses a
simple assq dispatch technique, which nicely fits into regular Scheme
without relying on anything else. New, fully compatible
behavior-representation implementations can easily be defined and
plugged in. Operations can be added at will, as well. The API can
also be used to manipulate its own behavior-representation handlers.

(define (create-collection handler)
`(,handler)
)

(define collection-tag 'collection-tag)

(define set-list
`(,collection-tag
(add
,(lambda (lst value)
(if (not (pair? (member value lst)))
(set-cdr! lst (cons (car lst)(cdr lst)))
(set-car! lst value))))
(remove
,(lambda (lst value)
(let ((pos (member value lst)))
(if (pair? pos)
(car pos)
lst))))
(contains
,(lambda (lst value)
(pair? (member? value lst))))
(map
,(lambda (lst function)
(map function lst)))
))

(define map-alist
`(,collection-tag
(put
,(lambda (alist key value)
(let ((existing (assoc key alist)))
(if (pair? existing)
(let ((current (cadr existing)))
(set-cdr! existing (list value))
current)
(begin
(set-cdr! alist (cons (car alist)(cdr alist)))
(set-car! alist (list key value))
#f)))))
(remove
,(lambda (alist key)
(let ((existing (assoc key alist)))
(if (pair? existing)
(cadr existing)
#f))))
(contains
,(lambda (alist key)
(let ((existing (assoc key alist)))
(pair? existing))))
(get
,(lambda (alist key)
(let ((existing (assoc key alist)))
(if (pair? existing)
(cadr existing)
#f))))
(clear
,(lambda (alist)
(set-cdr! alist '())
(set-car! alist '())))
(map
,(lambda (alist function)
(map function alist)))

(mapkeys
,(lambda (alist function)
(map (lambda (pair) (function (car pair))) alist)))

(mapvalues
,(lambda (alist function)
(map (lambda (pair) (function (cadr pair))) alist)))

))

(define (is-handler obj)
(if (pair? obj)
(eq? (car obj) collection-tag)
#f))

; (add handler) => (add <struct> values)
; (add handler struct) => (add values)
; (add handler struct values)

; simple dispatch for collections with limited currying
(define (handler* operation)
(lambda args
(let
((len (length args))(op-handler (cadr (assq operation (cdar
args)))))
(if (equal? len 1)
(lambda struct-then-values
(apply op-handler struct-then-values))
(let
((struct (cadr args)))
(if (equal? len 2)
(lambda values
(apply op-handler (cons struct values)))
(apply op-handler (cons struct (cddr args))))))))
)

(define add* (handler* 'add))
(define put* (handler* 'put))
(define get* (handler* 'get))
(define remove* (handler* 'remove))
(define contains* (handler* 'contains))
(define clear* (handler* 'clear))
(define map* (handler* 'map))
(define mapkeys* (handler* 'mapkeys))
(define mapvalues* (handler* 'mapvalues))

Richard C. Cobbe

2004-07-02, 3:59 pm

google@soletta.com (RJudson) writes:

> I've been playing with a little collections API for Scheme, and
> encountered a newbie sort of problem -- is there a straightforward way
> for a procedure defined in a lambda to call itself recursively? I can
> see how to do it with continuations, I think, but I'm wondering if
> there's a simpler way; it's not jumping out at me from R5.

Sure. The following evaluates to a function, whose body is provided by the
(lambda ...) form, that is able to call itself.

(letrec ([foo (lambda (w x) ... (foo y z) ...)])
foo)

It's a common enough idiom that some implementations provide a convenient
macro wrapper. In PLT Scheme, for example, you can accomplish the same
thing as follows:

(require (lib "etc.ss"))
(recur foo (lambda (w x) ... (foo y z) ...))

You almost certainly want to do it this way rather than with continuations
-- it'll be much easier for other people to read and understand your code.

Richard

Ray Dillinger

2004-07-03, 4:09 am

If you develop a good collections API, and it's
written in such a way that someone implementing
a new collection type can use R5RS scheme to make
the new collection "accessible" to your API without
modifying any code outside his own collection code,
please consider writing a SRFI.

There is something that alleges to be a "collections"
SRFI now, but it fails the fundamental test of
usability since it isn't possible to develop portable
collections that can be accessed through it. It needs
to be obsoleted by something better, quickly.

Bear

Grzegorz Chrupała

2004-07-03, 8:56 am

RJudson wrote:

> I've been playing with a little collections API for Scheme, and

A generic collection API for Scheme is defined in SRFI-44
(srfi.schemers.org). Its reference implementation relies on Tiny CLOS for
dispatch.

> encountered a newbie sort of problem -- is there a straightforward way
> for a procedure defined in a lambda to call itself recursively? I can
> see how to do it with continuations, I think, but I'm wondering if
> there's a simpler way; it's not jumping out at me from R5.

This can be done with the REC macro defined in SRFI-31. Anonymous factorial
would look like this:

(rec (F N)
(if (zero? N)
1
(* N (F (- N 1)))))

Cheers,
--
Grzegorz Chrupała | http://pithekos.net | grzegorzc@jabber.org

Sponsored Links