Some background: Burks, Warren and Wright published a description of simple interpreter for a Logic Machine for unparenthesized Lukasiewicz notation (paper, SO question, c implementation, postscript implementation) which was heavily cited in Kenneth Iverson's 1962 classic A Programming Language.

Within there is an elegant system of typing by associating integer weight to variables, literals, and functions, which allows a simple max_weight/length test for well-formedness (ready for reduction), as well as a simple formula to convert the weight into the degree or arity of the function. Specifically, variables and literals are given weight=1, and unary functions are given weight=0, and binary functions are given weight=-1. For a function (w<1), its degree d is 1-w.

What I'd like to do, and I'm not sure how to go about it, is to add APL's operator type to the mix. But it would seem that I need a very weird kind of number, that can by simple arithmetic yield the function arity and yield the correct positive (minimum, ie. 1) weight for a complete well-formed formula.

For the extended language, I'm adding integers 0-9 as well as variables a-z, binary + and -, and unary < "box" and > "unbox", and the monadic operator / "reduce". Also, we'll use infix syntax with right-to-left evaluation, like APL.

So for the very simple formula "0+4", we encounter

0  literal, w=1
0+  function, w=-1, sum of weights=0,  function degree=1-w=2
0+4  literal, w=1, sum of weights=1 <--complete wff

Now the problem happens when I try to add an operator, it needs to counterbalance the weight of its associated functions, thus it should be positive, but it shouldn't ever create a condition of "false positive", so it also needs to be further from positive. Perhaps another dimension, or a second field of the type descriptor?

For "+/ab", the sequence of discovery is

+  function, w=-1, function degree=1-w=2
+/  operator w=1??  sum of weights=0
+/a  variable, w=1, sum of weights=1 <-- false positive.
+/ab  variable w=1, sum of weights=2, yet I want this to sum to 1.

Is there a better way that I'm not seeing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.