[CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> Minsky [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Tue Jun 8 11:46:31 PDT 2004

# The Programming Language Minsky

## 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

1. BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
2. EBNF::="Extended " BNF.
3. HTML::= "HyperText Markup Language", used on the WWW.
5. Java::="An " OO " Language from Sun".
6. LISP::= "LISt Processing Language".
7. LRM::="Language Reference Manual".
8. OO::="Object-Oriented".
9. Prolog::="Programming in Logic".
10. TBA::="To Be Announced".
11. UML::="Unified Modeling Language".
12. URL::=Universal_Resource_Locator,
13. Universal_Resource_Locator::syntax= protocol ":" location, where
Net
1. protocol::= "http" | "ftp" | "mailto" | ... ,
2. location::= O( "//" host) O(pathname).

(End of Net)
14. WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
15. XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of syntax, semantics, and other formal specifications.