Question

From the bibliography of chapter 1 of the 1962 A Programming Language, I found this intriguingly concise description of a forward-Polish (Lukasiewicz) Logic Machine. And I think I'm with it up to this part on the Logic Function F: Burks/

What does (2a) mean? How is this a function?

Here's my implementation (in PostScript) of everything up to that part (completed Postscript, C version):

%http://www.ams.org/journals/mcom/1954-08-046/

/L{length}def % length of string
/T{ % i D  tail(i) of string
    2 copy L le{ % i<=L(D)
        dup length 2 index sub % i D L(D)-i
        3 2 roll getinterval % D[L-i.*i]
    }{ % i>L(D)
        exch pop % D
    }ifelse
}def
/H{ % i D  head(i) of string
    2 copy L le{ % i<=L(D)
        0 % i D 0
        3 2 roll getinterval % D[0.*i]
    }{
        exch pop % D
    }ifelse
}def

/Wtab 1 dict def
 1 0 1 255{Wtab exch 2 index put}for    pop
 0 (N)    {Wtab exch 2 index put}forall pop
-1 (KA)   {Wtab exch 2 index put}forall pop

/W{ % weight of string or char
    dup type /integertype eq {
        Wtab exch get
    }{
        0 exch { W add } forall
    }ifelse
}def

%Wtab{exch =only( )=only =}forall
%(KAxyz)W =

/D{ % D(d) = 1 - W(d)
    1 exch W sub
}def

/Wmax{ % Wmax(D) = Max(W[T_i(D)]) for i > 0
    [ exch
    0 1 2 index L { % [ ... D i
        1 index T   % [ ... D T(i,D)
        W
        exch        % [ ... W(T(i,D)) D
    } for
    pop % [ ... W(T(i,D))
    counttomark 0 eq { pop 0 }{
        {
            counttomark 1 eq { exch pop exit } if
            2 copy lt { exch } if pop
        }loop
    }ifelse
}def

/Wmin{ % Wmin(D) = Min(W[T_i(D)]) for i > 0
    [ exch
    0 1 2 index L { % [ ... D i
        1 index T   % [ ... D T(i,D)
        W
        exch        % [ ... W(T(i,D)) D
    } for
    pop % [ ... W(T(i,D))
    counttomark 0 eq { pop 0 }{
        {
            counttomark 1 eq { exch pop exit } if
            2 copy gt { exch } if pop
        } loop
    }ifelse
}def

%(KAxyz) Wmax =
%(KAxyz) Wmin =

/PF{ % D is positive formula
    Wmin 0 gt
}def

/WFF{ % D is well-formed formula
    dup PF exch W 1 eq and
}def

/P(01)def
P{
    W 1 ne {ERROR:W_p!=1} if
}forall
/Ptab <<
    P {
        dup
    } forall
>>def

/F{
    dup D 0 gt {
    }{
    }ifelse
}def
Was it helpful?

Solution

Hm. Ok. I think I'm starting to get it. P is the data alphabet, just 0 and 1. And ignoring the bizarre way they defined it, the Degree function D of "K" yields 2. So this (2a) is just notating the variable-capture from the input string, little-delta. In other words, the input string little-delta is implicitly partitioned into a new little-delta (in the example, this is the character K) and its 2 (degree=2, right?) arguments, πD(δ) .. π1, which is defined as this list so it can extend to any arity. The εP part just means that F must yield 0 or 1, or more generally, an element of P

F itself is a parameter to the whole thing. It was right at the top. I forgot.

Burks Language Parameters

So here's the implementation of the functions K, A, and N. F controls when to call them, but they have to crack their own arguments from the string.

/P(01)def
P{
    W 1 ne {ERROR:W_p!=1} if
}forall
/Ptab <<
    P { 
        dup
    } forall
>>def

/iP{ % i <- P
    P exch search pop length exch pop exch pop 
}def

/Pi{ % P <- i
    P exch 1 getinterval
}def

/F{
    dup 0 get 
    D 0 gt { % ie. an operator
        dup 0 get % (...) K|A|N 
        exch % K|A|N (...)
        1 1 index length 1 sub getinterval % kan (..)
        exch Ftab exch get exec % F(d,..)
    }{ % leave it alone. F(p)=p
    }ifelse
}def
/Ftab <<
(K)0 get { % crack 2 args from string and convert to indices
    dup 0 1 getinterval iP
    exch 1 1 getinterval iP
    and 
    Pi % convert result back to alphabet P
}
(A)0 get {
    dup 0 1 getinterval iP
    exch 1 1 getinterval iP
    xor 
    Pi  
}
(N)0 get {
    0 1 getinterval iP
    1 add 2 mod 
    Pi  
}
>>def

(K00) F = 
(K01) F =
(K10) F =
(K11) F =

ghostscript output:

0
0
0
1

Aw. Sheesh. They totally say the same thing on the next page.

What I just said.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top