Select this to skip to main content [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

Contents


    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.
  4. HTML_page::syntax= "<HTML>" head body.
  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.


Formulae and Definitions in Alphabetical Order