Concrete Syntax

1. variable::=lower_case_letter.
2. action::= basic | iteration | selection | sequence.
3. basic::="0" variable | "+" variable | "-" variable.
4. iteration::= "*" variable "(" action ")".
5. selection::= "?" variable "(" action ":" action ")".
6. sequence::= # action, -- any number of actions including none.

   Example

   While a>0, subtract one from a and add one to b.

    	*a(-a+b)

   Here is a rough translation into C/C++/Java:

    	while(a>0){--a; ++b}

Abstract Syntax

1. V::=a|b|c|...|z, -- 26 variables.
2. A::= empty | 0 V | + V | - V | * V ( A ) | ? V ( A : A ) | A A, -- actions.

Semantic Domains

I = 0,1,2,.. , values of variables: integers greater than or equal to zero. S = V -> I, state: each variable has a value.

For s:S, v:V, s(v) = the value of v in s.

For s:S, v:V, i:I, s[ i / v ] = the state with the value of v set to i,
Net

1. (s1): s[i/v](v) = i,
2. (s2): For v1 != v2, s[i/v1](v2) = s(v2).

(End of Net)


Semantic Function Declaration

m<<a>>: S->S, the meaning of a.

m<<a>>s is the effect of a on state s.

Semantic Function Equations

For s: S, a,a1,a2:A, v:V.
(a): m<<empty>>s = s.
(b): m<<0 v>>s = s[0/v].
(c): m<<+ v>>s = s[s(v) +1 / v].
(d): m<<- v>>s = s[ max(0, s(v) -1) / v].
(e): m<<* v(a)>>s = if s(v)=0 then s else m<<*v(a)>> ( m<<a>> s).
(f): m<<?v(a1:a2)>>s = if s(v) =0 then m<<a2>>s else m<<a1>> s.
(g): m<<a1 a2>> s = m<<a2>> (m<<a1>>s).

Using the Equations

For example, if a=1 and b=0 in s0 and s2 = m<<-a+b>>s0, the values of a and b in s2 can be shown to be 0 and 1 respectively as follows.

Initially:

1. s0(a) =1.
2. s0(b) =0.

3. s2 = m<<-a+b>>s0,
4. s2 =m<<+b>>(m<<-a>>s0), by (g) above.

   Let s1=m<<-a>>s then

5. s2=m<<+b>>s1 where
6. s1 = m<<-a>>s0
7. =s0[max(0, s0(a) - 1)/a ] by (d) above,
8. =s0[max(0, 1 - 1)/a ] , by (s1) above
9. =s0[max(0, 0)/a ] ,
10. = s0[0/a ].

    Notice, s1(b)=s0[0/a](b) =s0(b) =0, by (s2) above.

    So,

11. s2=m<<+b>>s1
12. = s1 [s1(b)+1/b], by (c)
13. = s1 [0+1/b]
14. = s1 [1/b]
15. = s0[0/a] [1/b].

    So, in s2, a=0 and b=1.

Examples of Minsky code

1. Set b equal to 2

       0b+b+b

2. Dump a into b (and clear a)

       0b*a(+b-a)

3. Dump 2a into b

       0b*a(+b+b-a)

4. Use c to copy a to b

       0b0c*a(-a+b+c)*c(-c+a)

5. Dump half of a into b (rounded up)

       0b*a(+b-a-a)

6. If a!=0 then set b to 1 else set b to 0

       ?a( 0b+b : 0b)

7. Clear a and if a was odd set c to 1 else set c to 0

       0c*a(-a ?a(:+c)-a)

8. Calculate quotient q and remainder r of a divided by 2 using b (buggy!):

       0r0q0b *a(+q+b-a ?a(:+r) -a+b) *b(-b+a)

9. Calculate quotient q and remainder r of a divided by 2 using b:

       0r0q0b *a(+q+b-a ?a(:+r) -a+b) *b(-b+a) ?r(-q-a)

   (Improved, but may still have a bug or two).

. . . . . . . . . ( end of section The Programming Language Minsk) <<Contents | Index>>

Glossary