(archive 'newLISPer)

June 27, 2008

Functions That Use and the Functions That Get Used…

Filed under: newLISP — newlisper @ 17:31
Tags:

While writing a function to tell me what functions a function functions with (by this I mean, what functions a function uses to do its thing), it occurred to me that this could be accomplished using newLISP’s ability to look within (no wonder newLISP is so enlightened ;-) We could, of course, hand-code one for each function:

> (define (f a b) (+ a  b (- b a)))
(lambda (a b) (+ a  b (- b a)))
> (define (f-uses) '(+ -))
(lambda () '(+ -))
> (f-uses)
(+ -)
> _

But that would add a lot of needless functions to our namespace — and make competent programmers laugh at us :-)

Better to look at the function itself (the S-expression) and extract all of the function names automatically. But how?

Let’s pretend we have no idea how to do this yet and just feel our way along. Of course, I already know how to do this (he says in a voice that betrays his ignorance), so don’t you worry about a thing. Everything will be fine (*gulp*).

The best place to start may be by looking at a function’s S-expression. A naive attempt might be to just look at the value of a function’s name. But first, we need to define a function to look at:

> (define (f a b) (+ a b (- b a)))
(lambda (a b) (+ a b (- b a)))
> f
(lambda (a b) (+ a b (- b a)))
> _

Look, newLISP rewards our naiveté with exactly what we want, matching our mental model of the world! Two things to notice here. The result of define and the value of f are identical, and this result is a lambda (a function without a name).

Now let’s begin our dissection of this S-expression to see if we can get at those function names.

> (0 f)
((a b) (+ a b (- b a)))
> (1 f)
((+ a b (- b a)))
> ;; almost there!
> ((1 f) 1)
(+ a b (- b a))
> ;; here we go.
> _

Now we just need to look at the first symbol in each expression (with exceptions) to know which functions this function is using. Before we continue, we’d better get a better grip on our subject.

> (set 'subj ((1 f) 1))
(+ a b (- b a))
> _

To get the first one is easy. Just use first!

> (first subj)
+
> _

If all we were interested in was the first function our function calls, we’d be done. Actually, we want all of the functions, so we must keep going. Iteration seems to be in order. Warning: The next few snippets contain examples of code-groping. Don’t try this at work ;-)

(map (fn (ea) (and (list? ea) (first ea))) subj)
(nil nil nil -)
> _

That’s almost it. We don’t need all those nils, though. Next try.

>(filter (fn (ea) (and (list? ea) (first ea))) subj)
((- b a))
> _

That’s not exactly right, either. Maybe we should break this up into finer steps.

> (filter list? subj)
((- b a))
> _

Now we’re on to it. If this were a complete example, we would have more than just one expression in our resultant list. Now for the next part:

> (map first (filter list? subj))
(-)
> _

You know what? We’re missing something here. A test to see if the first element of the list is a lambda or a primitive. How do we do that? lambda? and primitive?, of course.

> [cmd]
(filter
    (fn (ea)
        (let (ea (eval ea))
        (or (lambda? ea) (primitive? ea))))
    (map
        first
        (filter list? subj)))
[/cmd]

There we are. We’re all done except for the first function in the expression, which we got by applying first. Here we need it consed to the front of our list:

> [cmd]
(cons
    (first subj)
    (filter
    (fn (ea)
            (let (ea (eval ea))
            (or (lambda? ea) (primitive? ea))))
        (map
            first
            (filter list? subj))))
[/cmd]
(+ -)
> _

Wow. There it is! The functions our subject function calls. But are we really done yet? Done is something that programming never seems to be ;-) Is the first element being tested to see if it’s a function? And will it work with deeply nested functions? This is the part where I expect the author to say, “I’ll leave that as an excerise for you,” probably because he or she is tired of writing ;-) Not me!

First, let’s define this as a function.

> [cmd]
(define (uses fname)
    (let (subj ((1 fname) 1))
    (cons
        (first subj)
        (filter
            (fn (ea)
                (let (ea (eval ea))
                (or (lambda? ea) (primitive? ea))))
            (map
                first
                (filter list? subj))))))
[/cmd]
(lambda (fname)
    (let (subj ((1 fname) 1))
    (cons (first subj) (filter (lambda (ea)
        (let (ea (eval ea))
            (or (lambda? ea) (primitive? ea))))
        (map first (filter list? subj))))))
> (uses f)
(+ -)
> _

That seems to be working. Let’s try this with a deeper function.

> (define (deep-f a b) (+ a (- (* b a) a)))
(lambda (a b) (+ a (- (* b a) a)))
> (uses deep-f)
(+ -)
>

Just as I suspected. Anything deeper than one level, and it’s ignored. Where do we go from here? I’ll leave that as an exercis . . . just kidding ;-) Maybe we should conclude for today and then we can look forward to Part II of “Functions That Use and the Functions That Get Used by Other Functions”! If you would like to post solutions to the comments section, by all means do. I’ll just check them against my already-conceived code (you don’t really believe this, do you?), and we can pick the best one. I’m pretty sure mine won’t win, though ;-)

m i c h a e l

P.S. If you detect a slight shallowing of the code in these posts, the effect is entirely acknowledged to be true. I’m looking with nostalgia at the days when I could spend an hour or more coding something up in newLISP, and that’s a bad sign, indeed.

Comment from don Lucio

Here is a solution using the function ‘flat’ which makes it easy to acess a deep nested list:

(define (uses fname)
(unique (filter
  (fn (s) (primitive? (eval s)))
 (flat fname))))

Comment from cormullion

Excellent post! I’ve always wondered about this area of newLISP!

(The modest note at the end of your post is entirely unjustified!)

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: