csp

func S31_COPY ¶

func S31_COPY(west, east chan rune)

S31_COPY implements Section 3.1 COPY problem: "Write a process X to copy characters output by process west to process, east."

Solution:

X :: *[c:character; west?c -> east!c]

func S32_SQUASH ¶

func S32_SQUASH(west, east chan rune)

S32_SQUASH implements Section 3.2 SQUASH problem: "Adapt the previous program to replace every pair of consecutive asterisks "**" by an upward arrow "↑". Assume that the final character input is not an asterisk."

Solution:

X :: *[c:character; west?c ->
  [ c != asterisk -> east!c
   □ c = asterisk -> west?c;
         [ c != asterisk -> east!asterisk; east!c
          □ c = asterisk -> east!upward arrow
  ] ]    ]

func S32_SQUASH_EX ¶

func S32_SQUASH_EX(west, east chan rune)

S32_SQUASH_EX implements Section 3.2 SQUASH exercise: "(2) As an exercise, adapt this process to deal sensibly with input which ends with an odd number of asterisks."

Solution:

X :: *[c:character; west?c ->
  [ c != asterisk -> east!c
   □ c = asterisk -> west?c;
         [ c != asterisk -> east!asterisk; east!c
          □ c = asterisk -> east!upward arrow
         ] □ east!asterisk
  ]   ]

func S33_DISASSEMBLE ¶

func S33_DISASSEMBLE(cardfile chan []rune, X chan rune)

S33_DISASSEMBLE implements Section 3.3 DISASSEMBLE problem: "to read cards from a cardfile and output to process X the stream of characters they contain. An extra space should be inserted at the end of each card."

Solution:

*[cardimage:(1..80)characters; cardfile?cardimage ->
    i:integer; i := 1;
    *[i <= 80 -> X!cardimage(i); i := i+1 ]
    X!space
]

func S34_ASSEMBLE ¶

func S34_ASSEMBLE(X chan rune, lineprinter chan string)

S34_ASSEMBLE implements Section 3.4 ASSEMBLE problem: "To read a stream of characters from process X and print them in lines of 125 characters on a lineprinter. The last line should be completed with spaces if necessary."

Solution:

lineimage:(1..125)character;
i:integer, i:=1;
*[c:character; X?c ->
    lineimage(i) := c;
    [i <= 124 -> i := i+1
    □ i = 125 -> lineprinter!lineimage; i:=1
]   ];
[ i = 1 -> skip
□ i > 1 -> *[i <= 125 -> lineimage(i) := space; i := i+1];
  lineprinter!lineimage
]

func S35_Reformat ¶

func S35_Reformat(cardfile chan []rune, lineprinter chan string)

S35_Reformat implements Section 3.5 Reformat problem: "Read a sequence of cards of 80 characters each, and print the characters on a lineprinter at 125 characters per line. Every card should be followed by an extra space, and the last line should be complete with spaces if necessary."

Solution:

[west::DISASSEMBLE||X:COPY||east::ASSEMBLE]

func S36_ConwayProblem ¶

func S36_ConwayProblem(cardfile chan []rune, lineprinter chan string)

S36_ConwayProblem implements Section 3.6 Conway's Problem: "Adapt the above program to replace every pair of consecutive asterisk by an upward arrow."

Solution:

[west::DISASSEMBLE||X::SQUASH||east::ASSEMBLE]

func S41_DivisionWithRemainder ¶

func S41_DivisionWithRemainder(in chan S41_In, out chan S41_Out)

S41_DivisionWithRemainder implements Section 4.1 Division With Remainer. "Construct a process to represent a function type subroutine, which accepts a positive dividend and divisor, and returns their integer quotient and remainder. Efficiency is of no concern."

Solution:

[DIV::*[x,y:integer; X?(x,y)->
      quot,rem:integer; quot := 0; rem := x;
      *[rem >= y -> rem := rem - y; quot := quot + 1;]
      X!(quot,rem)
      ]
||X::USER]

func S42_Factorial ¶

func S42_Factorial(fac []chan int, limit int)

S42_Factorial implements Section 4.2 Factorial "Compute a factorial by the recursive method, to a given limit."

Solution:

[fac(i:1..limit)::
*[n:integer;fac(i-1)?n ->
  [n=0 -> fac(i-1)!1
  □ n>0 -> fac(i+1)!n-1;
    r:integer; fac(i+1)?r; fac(i-1)!(n*r)
]] || fac(0)::USER ]

Note that the solution above from original paper is wrong. Check the code below for some fixes.

func S45_S46_NewRecursiveSmallSetOfIntegers ¶

func S45_S46_NewRecursiveSmallSetOfIntegers() (chan S45_Has, chan int, chan chan S46_Least)

S45_RecursiveSmallSetOfIntegers implements Section 4.5 Recursive Data Representation: Small Set of Integers. "Same as above, but an array of processes is to be used to achieve a high degree of parallelism. Each process should contain at most one number. When it contains no number, it should answer 'false' to all inquiries about membership. On the first insertion, it changes to a second phase of behavior, in which it deals with instructions from its predecessor, passing some of them on to its successor. The calling process will be named S(0). For efficiency, the set should be sorted, i.e. the i-th process should contain the i-th largest number."

Solution:

S(i:1..100)::
*[n:integer; S(i-1)?has(n)->S(0)!false
□ n:integer; S(i-1)?insert(n)->
   *[m:integer; S(i-1)?has(m)->
      [m<=n->S(0)!(m=n)
      □m>n-->S(i+1)!has(m)
    ]
   □m:integer; S(i-1)?insert(m)->
    [m<n->S(i-1)!insert(m); n:=m
    □m=n->skip
    □m>n->S(i+1)!insert(m)
]]]

S46_RemoveTheLeastMember implements Section 4.6 Multiple Exits: Remove the Least Member. "Exercise: Extend the above solution to respond to a command to yield the least member of the set and to remove it from the set. The user program will invoke the facility by a pair of commands:

S(1)!least();[x:integer;S(1)?x-> ... deal with x ...
             □S(1)?nonleft()-> ... ]

or if he wishes to scan and empty the set, he may write:

S(1)!least();more:boolean;more:=true;
             *[more;xinteger;S(1)?x-> ...deal with x...; S(1)!least())
              □ more;S(1)?noneleft()->more:=false]

"

func S51_BoundedBuffer ¶

func S51_BoundedBuffer() (chan int, chan int)

S51_BoundedBuffer implements Section 5.1 Bounded Buffer "Construct a buffering process X to smooth variations in the speed of output of portions by a producer process and input by a consumer process. The consumer contains pairs of commands X!more();X?p, and the producer contains commands of the form X!p. The buffer should contain up to ten portions."

Solution:

X::
buffer:(0..9)portion;
in,out:integer; in:=0; out := 0;
comment 0 <= out <= in <= out+10;
  *[in < out + 10; producer?buffer(in mod 10) -> in := in + 1
  □ out < in; consumer?more() -> consumer!buffer(out mod 10);
     out := out + 1 ]

func S53_DiningPhilosophers ¶

func S53_DiningPhilosophers()

S53_DiningPhilosophers implements Section 5.3 Dining Philosophers "Five philosophers spend their lives thinking and eating. The philosophers share a common dining room where there is a curcular table surrounded by five chairs, each belonging to one philosopher. In the center of the table there is a large bowl of spaghetti, and the table is laid with five forks. On feeling hungry, a philosopher enters the dinning room, sits in his own chair, and picks up the fork on the left of his place. Unfortunately, the spaghetti is so tangled that he needs to pick up and use the fork on his right as well. When he has finished, the puts down both forks, and leaves the room. The room should keep a count of the number of philosophers in it."

Solution:

The behavior of the i-th philosopher may be described as follows:

PHIL = *[...during ith lifetime ... ->
         THINK;
         room!enter();
         fork(i)!pickup();fork((i+1)mod5)!pickup();
         EAT;
         fork(i)!putdown();fork((i+1)mod5)!putdown();
         room!next()]

The fate of i-th fork is to be picked up and put down by a philosopher sitting on either side of it

FORK = *[phil(i)?pickup()->phil(i)?putdown()
       □ phil((i-1)mod5)?pickup()->phil((i-1)mod5)?putdown()]

The story of the room may be simply told:

ROOM = occupancy:integer; occupancy := 0;
       *[(i:0..4)phil(i)?enter()->occupancy:=occupancy+1
       □ (i:0..4)phil(i)?exit()->occupancy:=occupancy-1]

All these components operate in parallel:

[room::ROOM||fork(i:0..4)::FORK||phil(i:0..4)::PHIL]

func S61_TheSieveOfEratosthenes ¶

func S61_TheSieveOfEratosthenes(np int)

S61_TheSieveOfEratosthenes implements Section 6.1 Prime Numbers: The Sieve of Eratosthenes. "To print in ascending order all primes less than 10000. Use an array of processes, SIEVE, in which each process inputs a prime from its predecessor and prints it. The process then inputs an ascending stream of numbers from its predecessor and passes them on to its successor, suppressing any that are multiples of the original prime."

Solution:

[SIEVE(i:1..100)::
 p,mp:integer;
 SIEVE(i-1)?p;
 print!p;
 mp:=p; comment mp is a multiple of p;
*[m:integer; SIEVE(i-1)?m->
   *[m>mp->mp:=mp+p];
    [m=mp->skip □ m<mp->SIEVE(i+1)!m ]
 ]
|| SIEVE(0)::print!2; n:integer; n:=3;
      *[n<10000->SIEVE(1)!n;n:=n+2]
|| SIEVE(101)::*[n:integer;SIEVE(100)?n->print!n]
|| print::*[(i:0..101)n:integer;SIEVE(i)?n->...]
]