2

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
3

1 Answer 1

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.