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 replacements. 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.