# Function Valence

## Problem

Given a string representation of a function f (usually 5:f),
compute the valence of f.

## Solution

The function 'val', defined here. E.g.,

val`val
1

## Analysis

There are several cases.

- monadic composition: f g h@
- monadic composition: *|:
- dyadic composition: &/<
- lambda, explicit argument list: {[a;b;c]..}
- lambda, no argument list:{..}

The valence of a function is the count of the variables used
by the function minus the variables replaced by the function.

Start by removing everything between quotations, everything
between (and including) "{" and "}", and all
blanks and tabs.

Next, chop the string using a finite state machine. here's the
idea:

We're looking for* variable replacement*s. A
replacement is a variable name followed immediately by a single
":", or a variable name followed immediately by
"::[". e.g.

a:10
a::[x;y;z]

We're also looking for *variables used*.

We'll need five token classes:

A alpha + "._"
N digits
C ":"
B "["
X everything else

The state machine is:

start in state 0.

0: if A -> 1 else -> 0

1,2: if A,N -> 2 else C -> 3 else -> 0

3: if A -> 1 else C -> 4 else -> 0

4: if A -> 1 else B -> 5 else -> 0

5: if A -> 1 else -> 0

Intuitively, we're trying to find:

abc
abc:
abc::
abc::[

We remove these from the list of used variables, then search
for occurrences of x, y, and z. (If there's no argument list,
these must determine the valence.)

The analysis is complicated by the fact that you can't know
you're dealing with a replacement until you've looked ahead,
possibly twice.

Once the string is chopped into replacements (type 1), uses (type
2), and everything else (type 0), we throw away all the symbols,
and find the difference between the set of used variables and the
set of replacements.

We must remember to disqualify variables which begin with a
".".

Source: K
listbox.