DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
urmCutland.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.urmCutland
4 # URM (Unlimited Register Machine) de <span style="font-variant:small-caps">Cutland</span>
5 #
6 # Cf. \htmlonly <a href="http://www.opimedia.be/Bruno_Marchal/index.htm#Theo" target="_blank">
7 # <tt>http://www.opimedia.be/Bruno_Marchal/index.htm#Theo</tt></a>\endhtmlonly
8 
9 ##\file
10 # URM (Unlimited Register Machine) de <span style="font-variant:small-caps">Cutland</span>
11 #
12 # Cf. \htmlonly <a href="http://www.opimedia.be/Bruno_Marchal/index.htm#Theo" target="_blank">
13 # <tt>http://www.opimedia.be/Bruno_Marchal/index.htm#Theo</tt></a>\endhtmlonly
14 
15 # (c) Olivier Pirson --- DragonSoft
16 # http://www.opimedia.be/DS/
17 # Débuté le 6 janvier 2008
18 ####################################
19 from __future__ import print_function
20 
21 ## Date du dernier changement pour ce module
22 VERSION = 'urmCutland --- 2010 April 12'
23 
24 import DSPython
25 import DSPython.factors as factors
26 
27 
28 
29 # ######### ??? changer les exceptions pour chaque raise
30 # Classes #
31 ###########
32 ## Une instruction pour la machine virtuelle UrmCutland
33 class UrmCutlandInstruction:
34  """Une instruction pour la machine virtuelle UrmCutland"""
35 
36  ## self == value ?
37  def __eq__(self, value):
38  """Renvoie True si self représente la même instruction que value
39  (càd si même type d'instruction et mêmes arguments),
40  False sinon
41 
42  Result: bool
43 
44  O() = 1"""
45  return (isinstance(value, UrmCutlandInstruction)
46  and (self._inst == value._inst) and (self._a == value._a)
47  and ((self._inst != T) or (self._b == value._b))
48  and ((self._inst != J) or ((self._b == value._b) and (self._c == value._c))))
49 
50 
51  ## Initialise l'instruction.
52  def __init__(self, inst, a=1, b=1, c=1):
53  """Si inst == Z alors initialise l'instruction à Z(a),
54  si inst == S alors initialise l'instruction à S(a),
55  si inst == T alors initialise l'instruction à T(a,b),
56  si inst == J alors initialise l'instruction à J(a,b,c)
57 
58  Si inst est un string
59  alors tous les espaces ' ' et tabulations '\t' sont ignorés
60  et si inst est 'Z(a)' alors initialise l'instruction à Z(a),
61  si inst est 'S(a)' alors initialise l'instruction à S(a),
62  si inst est 'T(a,b)' alors initialise l'instruction à T(a,b),
63  si inst est 'J(a,b,c)' alors initialise l'instruction à J(a,b,c)
64  Si la syntaxe de inst est incorrecte alors une exception est levée
65 
66  Pre: inst: Z, S, T, J
67  ou string de la forme 'Z(a)', 'S(a)', 'T(a,b)'
68  ou 'J(a,b,c)'
69  avec éventuellement des ' ' et '\t',
70  a, b et c représentants des naturels >= 1
71  écrits en base 10
72  Pre: a: naturel >= 1
73  b: naturel >= 1
74  c: naturel >= 1
75 
76  O() = 1"""
77  if isinstance(inst, int): # instruction par son code
78  assert Z <= inst <= J, inst
79  assert DSPython.natural_is(a), (type(a), a)
80  assert a >= 1, a
81  assert DSPython.natural_is(b), (type(b), b)
82  assert b >= 1, b
83  assert DSPython.natural_is(c), (type(c), c)
84  assert c >= 1, c
85 
86  self._inst = inst # code de l'instruction
87  self._a = a # 1er argument
88  if inst >= T:
89  self._b = b # 2e argument
90  if inst == J:
91  self._c = c # 3e argument
92  else: # string
93  assert isinstance(inst, str), (type(inst), inst)
94 
95  s = inst.replace(' ', '')
96  s = s.replace('\t', '')
97  if (len(s) < 4) or (s[1] != '(') or (s[-1] != ')'):
98  raise "syntax error in instruction '{0}'".format(inst)
99 
100  args = s[2:-1].split(',')
101  try:
102  args = [int(t) for t in args]
103  except:
104  raise "bad argument in instruction '{0}'".format(inst)
105  if args[0] <= 0:
106  raise "bad 1st argument in instruction '{0}'".format(inst)
107  self._a = args[0]
108 
109  if s[0] == 'Z': # Z(a)
110  self._inst = Z
111  if len(args) != 1:
112  raise "Z take 1 argument ({0} given): '{1}'".format(len(args), inst)
113  elif s[0] == 'S': # S(a)
114  self._inst = S
115  if len(args) != 1:
116  raise "S take 1 argument ({0} given): '{1}'".format(len(args), inst)
117  elif s[0] == 'T': # T(a,b)
118  self._inst = T
119  if len(args) != 2:
120  raise "T take 2 arguments ({0} given): '{1}'".format(len(args), inst)
121  if args[1] <= 0:
122  raise "bad 2nd argument in instruction '{0}'".format(inst)
123  self._b = args[1]
124  elif s[0] == 'J': # J(a,b,c)
125  self._inst = J
126  if len(args) != 3:
127  raise "J take 3 arguments ({0} given): '{1}'".format(len(args), inst)
128  if args[1] <= 0:
129  raise "bad 2nd argument in instruction '{0}'".format(inst)
130  self._b = args[1]
131  if args[2] <= 0:
132  raise "bad 3rd argument in instruction '{0}'".format(inst)
133  self._c = args[2]
134  else: # erreur
135  raise "bad instruction '{0}'".format(inst)
136 
137 
138  ## self != value ?
139  def __ne__(self, value):
140  """Renvoie True si self représente une instruction différente de value
141  (càd si type d'instruction différent
142  ou au moins un argument différent),
143  False sinon
144 
145  Result: bool
146 
147  O() = 1"""
148  return not (self == value)
149 
150 
151  ## Renvoie l'instruction sous forme d'un string
152  def __str__(self):
153  """Renvoie l'instruction sous forme d'un string
154 
155  Result: string
156 
157  O() = 1"""
158  if self._inst == Z: # Z(a)
159  return 'Z({0})'.format(self._a)
160  elif self._inst == S: # S(a)
161  return 'S({0})'.format(self._a)
162  elif self._inst == T: # T(a, b)
163  return 'T({0},{1})'.format(self._a, self._b)
164  else: # J(a, b, c)
165  assert self._inst == J, self._inst
166 
167  return 'J({0},{1},{2})'.format(self._a, self._b, self._c)
168 
169 
170  ## Renvoie le 1er argument de l'instruction
171  def a(self):
172  """Renvoie le 1er argument de l'instruction
173 
174  Result: naturel
175 
176  O() = 1"""
177  return self._a
178 
179 
180  ## Renvoie le 2e argument de l'instruction (ou lève une exception s'il n'y en pas)
181  def b(self):
182  """Renvoie le 2e argument de l'instruction
183  (ou lève une exception s'il n'y en pas)
184 
185  Result: naturel
186 
187  O() = 1"""
188  if self._inst >= T:
189  return self._b
190  else:
191  raise 'Not 2nd argument'
192 
193 
194  ## Renvoie le 3e argument de l'instruction (ou lève une exception s'il n'y en pas)
195  def c(self):
196  """Renvoie le 3e argument de l'instruction
197  (ou lève une exception s'il n'y en pas)
198 
199  Result: naturel
200 
201  O() = 1"""
202  if self._inst == J:
203  return self._c
204  else:
205  raise 'Not 3rd argument'
206 
207 
208  ## Renvoie le "nombre de Gödel" associé à l'instruction
209  def godelnumber(self):
210  """Renvoie le "nombre de Gödel" associé à l'instruction,
211  càd 2**n * 3**(a - 1) * 5**(b - 1) * 7**(c - 1)
212  où n == 0, 1, 2 ou 3 pour instruction == Z, S, T ou J
213 
214  Result: naturel >= 1
215 
216  O() = ..."""
217  if (self.inst() == Z) or (self.inst() == S): # instruction Z(a) ou S(a)
218  return 2**self.inst() * 3**(self.a() - 1)
219  elif self.inst() == T: # instruction T(a,b)
220  return 2**self.inst() * 3**(self.a() - 1) * 5**(self.b() - 1)
221  elif self.inst() == J: # instruction J(a,b,c)
222  return 2**self.inst() * 3**(self.a() - 1) * 5**(self.b() - 1) * 7**(self.c() - 1)
223  assert False
224 
225 
226  ## Renvoie le code associé à l'instruction
227  def inst(self):
228  """Renvoie le code associé à l'instruction
229 
230  Result: naturel
231 
232  O() = 1"""
233  return self._inst
234 
235 
236 
237 ## Programme (suite de UrmCutlandInstruction) pour la machine virtuelle UrmCutland
238 class UrmCutlandProg:
239  """Programme (suite de UrmCutlandInstruction)
240  pour la machine virtuelle UrmCutland"""
241 
242  ## self == value ?
243  def __eq__(self, value):
244  """Renvoie True si self représente le même programme que value
245  (càd si exactement la même suite d'instructions),
246  False sinon
247 
248  Result: bool
249 
250  O() = ..."""
251  if (not isinstance(value, UrmCutlandProg)) or (len(self) != len(value)):
252  return False
253  for i in range(1, len(self) + 1):
254  assert isinstance(self[i], UrmCutlandInstruction), type(self[i])
255  assert isinstance(value[i], UrmCutlandInstruction), type(value[i])
256 
257  if self[i] != value[i]:
258  return False
259  return True
260 
261 
262  ## Renvoie l'instruction numéro n
263  def __getitem__(self, n):
264  """Renvoie l'instruction numéro n
265 
266  Pre: n: naturel >= 1
267 
268  Result: UrmCutlandInstruction
269 
270  O() = ..."""
271  assert DSPython.natural_is(n), (type(n), n)
272  assert n >= 1, n
273 
274  return self._insts[n - 1]
275 
276 
277  ## Initialise le programme pour la machine virtuelle UrmCutland
278  def __init__(self, insts):
279  """Initialise le programme pour la machine virtuelle UrmCutland
280  Si insts est une séquence de UrmCutlandInstruction
281  alors initialise simplement le programme
282  avec cette séquence d'instructions.
283 
284  Si insts est un string ou séquence de string :
285 
286  Si une instruction est incorrecte
287  alors une exception est levée.
288 
289  Alphabet stricte:
290  'Z', 'S', 'T', 'J',
291  '(', ')', ', ',
292  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
293 
294  De plus '#' désigne un commentaire
295  (dans lequel tous les caractères sont permis)
296  jusqu'à la fin du string ou une fin de ligne,
297  et est alors ignoré
298  Tous les espaces ' ', tabulations '\t'
299  et à la ligne '\n' sont ignorés
300 
301  Instructions permises : 'Z(a)'
302  'S(a)'
303  'T(a,b)'
304  'J(a,b,c)'
305  où a, b et c représentent des naturels >= 1
306  écrits en base 10
307 
308  Pseudo-instruction include : 'i(prog)'
309  où prog désigne une variable contenant
310  un programme qui sera inclus
311  (tous les numéros d'instructions de prog
312  sont décalés en conséquence)
313 
314  Un numéro de ligne
315  peut précéder une (pseudo-)instruction : 'n)'
316  où n représente un naturel >= 1 écrit en base 10
317  (dans ce cas il doit être plus grand
318  que les numéros de ligne déjà traités)
319  (si des numéros d'instructions sont passés
320  alors ajoute des instructions neutres 'T(1,1)'
321  pour complèter les trous)
322 
323  Pre: insts: séquence de UrmCutlandInstruction
324  ou string ou séquence de string
325 
326  O() = ..."""
327  assert isinstance(insts, str) or isinstance(insts, list) or isinstance(insts, tuple), \
328  type(insts)
329 
330  if ((isinstance(insts, list) or isinstance(insts, tuple))
331  and ((len(insts) == 0)
332  or isinstance(insts[0],
333  UrmCutlandInstruction))) : # séquence de UrmCutlandInstruction
334  if __debug__:
335  for inst in insts:
336  assert isinstance(inst, UrmCutlandInstruction), type(inst)
337 
338  self._insts = list(insts) # suite des UrmCutlandInstruction
339  else: # source texte
340  # Transforme insts en une liste de string (sans '\n')
341  if isinstance(insts, list) or isinstance(insts, tuple):
342  insts = '\n'.join(insts)
343  insts = insts.split('\n')
344 
345  l = [] # liste des instructions déjà traitées
346  t = '' # string du travail en cours
347  num = 1 # numéro de l'instruction courante
348  already_num = False # True ssi déjà un numéro spécifié explicitement
349  # pour l'instruction courante
350 
351  ## Pour chaque string (lignes numérotées à partir de 1)
352  for i in range(1, len(insts) + 1):
353  assert isinstance(insts[i - 1], str), (i, type(insts[i - 1]), insts[i - 1])
354 
355  comment = False # True ssi on est dans un commentaire
356 
357  ## Pour chaque caractère (colonnes numérotées à partir de 0)
358  for j in range(len(insts[i - 1])):
359  assert insts[i - 1][j] != '\n', (i, j, insts[i - 1][j])
360 
361  c = insts[i - 1][j] # caractère courant
362  if comment:
363  if c == '\n':
364  comment = False
365  continue
366 
367  if (c != ' ') and (c != '\t'): # évite les "espaces"
368  if c == '#': # début de commentaire
369  comment = True
370  elif c != ')': # accumule les caractères jusqu'à un ')')
371  if (t[:1] != 'i') and not (c in 'ZSTJi(,0123456789'):
372  raise ("bad character '{0}' in line {1} column {2}: '{3}'"
373  .format(c, i, j, t))
374  t += c
375  else: # ')', fin d'un numéro d'instruction
376  # ou d'une (pseudo)-instruction
377  if t == '':
378  raise "closed ')' with nothing in line {0} column {1}".format(i, j)
379  if t[0] in 'ZSTJ': # c'est une instruction
380  try:
381  inst = UrmCutlandInstruction(t + ')')
382  except:
383  raise ("bad instruction '{0})' in line {1} column {2}"
384  .format(t, i, j))
385  if len(l) + 1 < num: # si il faut complèter avec des NOTHING
386  l += [NOTHING]*(num - 1 - len(l))
387  l.append(inst)
388  num += 1
389  already_num = False
390  elif t[0] == 'i': # c'est la pseudo-instruction i
391  if (len(t) >= 2) and (t[1] != '('):
392  raise ("not opening '(' in line {0} column {1}: '{2})'"
393  .format(i, j, t))
394  if len(l) + 1 < num: # si il faut complèter avec des NOTHING
395  l += [NOTHING]*(num - 1- len(l))
396  try:
397  include = eval(t[2:])
398  except:
399  raise ("bad include program '{0})' in line {1} column {2}"
400  .format(t, i, j))
401  if not (isinstance(include, UrmCutlandProg)):
402  raise ("not valid include program '{0})' in line {1} column {2}"
403  .format(t, i, j))
404  for inst in include:
405  if not isinstance(inst, UrmCutlandInstruction):
406  raise ("not valid instruction in include program '{0})'"
407  + ' in line {1} column {2}'
408  .format(t, i, j))
409  l += include.shiftInstrNum(num - 1)
410  num += len(include)
411  already_num = False
412  else: # c'est un numéro d'instruction
413  if already_num:
414  raise ('already number {0} to this instruction:'
415  + " '{1})' in line {2} column {3}"
416  .format(num, t, i, j))
417  try:
418  num = int(t)
419  except:
420  raise ("bad number instruction '{0})'"
421  + " in line {1} column {2} : '{3}'"
422  .format(t, i, j, insts[i - 1]))
423  if len(l) > num:
424  raise ('already number instruction {0} (greater: {1})'
425  + " in line {2} column {3}: '{4}'"
426  .format(num, len(l) - 1, i, j, insts[i - 1]))
427  already_num = True
428  t = ''
429 
430  if t != '':
431  raise "piece of instruction '{0}'".format(t)
432  if already_num:
433  raise 'number instruction {0} without instruction'.format(num)
434  self._insts = l # suite des UrmCutlandInstruction
435 
436 
437  ## Itère sur les instructions du programme
438  def __iter__(self):
439  """Itère sur les instructions du programme
440 
441  O() = 1"""
442  for inst in self._insts:
443  yield inst
444 
445 
446  ## Nombre d'instructions du programme
447  def __len__(self):
448  """Renvoie le nombre d'instructions du programme
449 
450  Result: naturel
451 
452  O() = 1"""
453  return len(self._insts)
454 
455 
456  ## self != value ?
457  def __ne__(self, value):
458  """Renvoie True si self représente un programme différent de value
459  False sinon
460 
461  Result: bool
462 
463  O() = ..."""
464  return not (value == value)
465 
466 
467  ## Initialise la valeur de l'instruction numéro n à value
468  def __setitem__(self, n, value):
469  """Initialise la valeur de l'instruction numéro n à value
470 
471  Pre: n: naturel >= 1
472  value: UrmCutlandInstruction
473 
474  O() = ..."""
475  assert DSPython.natural_is(n), (type(n), n)
476  assert n >= 1, n
477  assert isinstance(value, UrmCutlandInstruction), type(value)
478 
479  self._insts[n - 1] = value
480 
481 
482  ## Renvoie dans un string la suite des instructions du programme
483  def __str__(self):
484  """Renvoie dans un string
485  la suite des instructions du programme
486  séparée par '\n'
487 
488  Result: string
489 
490  O() = ..."""
491  return '\n'.join([str(inst) for inst in self._insts])
492 
493 
494  ##\brief Renvoie une copie du programme dont tous les numéros d'instructions == c
495  # mentionnés dans les instructions J sont changés en new
496  def changeInstrNum(self, c, new):
497  """Renvoie une copie du programme
498  dont tous les numéros d'instructions == c
499  mentionnés dans les instructions J sont changés en new
500 
501  Pre: c: naturel >= 1
502  new: naturel >= 1
503 
504  Result: UrmCutlandProg
505 
506  O() = ..."""
507  assert DSPython.natural_is(c), (type(c), c)
508  assert c >= 1, c
509  assert DSPython.natural_is(new), (type(new), new)
510  assert new >= 1, new
511 
512  l = [] # liste des instructions déjà traitées
513 
514  ## Pour chaque instruction
515  for inst in self:
516  assert isinstance(inst, UrmCutlandInstruction), type(inst)
517 
518  l.append(UrmCutlandInstruction(inst.inst(), inst.a(), inst.b(), new)
519  if (inst.inst() == J) and (inst.c() == c)
520  else inst)
521 
522  return UrmCutlandProg(l)
523 
524 
525  ## Renvoie le code source correspondant au programme
526  def decompile(self, skip=True, num=') ', concat='\n'):
527  """Renvoie le code source correspondant au programme
528  Si skip == True
529  alors passe les instructions T(a,a) avec a naturel
530  (dans ce cas il faut num != None)
531  Si num != None
532  alors chaque instruction est précédée
533  de son numéro puis de num
534  Si concat == None
535  alors renvoie une liste de string,
536  chacune contenant une instruction
537  sinon concatène toutes les instructions
538  en un seul string séparées par concat
539 
540  Pre: skip: bool
541  num: None ou string composée de ' ', '\t' ou '\n'
542  concat: None ou string composée de ' ', '\t' ou '\n'
543 
544  Result: string ou liste de string
545 
546  O() = ..."""
547  assert ((num == None) and not skip) or isinstance(num, str), (type(num), num, skip)
548  assert (concat == None) or isinstance(concat, str), (type(concat), concat)
549 
550  n = 1 # numéro d'instruction
551  l = [] # liste de string des instructions
552 
553  ## Pour chaque instruction
554  for inst in self:
555  assert isinstance(inst, UrmCutlandInstruction), type(inst)
556 
557  if (not skip) or (inst.inst() != T) or (inst.a() != inst.b()):
558  l.append(str(inst) if num == None
559  else '{0}{1}{2}'.format(n, num, inst))
560  n += 1
561 
562  return (l if concat == None
563  else concat.join(l))
564 
565 
566  ## Renvoie le "nombre de Gödel" associé au programme
567  def godelnumber(self):
568  """Renvoie le "nombre de Gödel" associé au programme,
569  càd 2**g_1 * 3**g_2 * 5**g_3 * 7**g_4 * ... * P_k**g_k
570  où g_i est le "nombre de Gödel" de l'instruction numéro i
571 
572  Result: naturel >= 1
573 
574  O() = ..."""
575  l = []
576  for inst in self._insts:
577  l.append(inst.godelnumber())
578  return factors.godelnumber(l)
579 
580 
581  ##???
582  def read(f):# ou dans __init__ ???
583  """???
584 
585  Pre: f: fichier (texte) ouvert en lecture
586 
587  O() = ..."""
588  assert isinstance(f, file), f
589 
590  raise NotImplementedError
591 
592 
593  ##\brief Renvoie une copie du programme dont tous les numéros d'instructions
594  # mentionnés dans les instructions J sont décalés de offset
595  def shiftInstrNum(self, offset, underflow=1):
596  """Renvoie une copie du programme dont tous les numéros d'instructions
597  mentionnés dans les instructions J sont décalés de offset.
598  Si une des valeurs devient < 1
599  alors elle est remplacée par underflow
600 
601  Pre: offset: int
602  underflow: naturel >= 1
603 
604  Result: UrmCutlandProg
605 
606  O() = ..."""
607  assert isinstance(offset, int), (type(offset), offset)
608  assert DSPython.natural_is(underflow), (type(underflow), underflow)
609  assert underflow >= 1, underflow
610 
611  l = [] # liste des instructions déjà traitées
612 
613  ## Pour chaque instruction
614  for inst in self:
615  assert isinstance(inst, UrmCutlandInstruction), type(inst)
616 
617  l.append(UrmCutlandInstruction(inst.inst(), inst.a(), inst.b(),
618  (inst.c() + offset if inst.c() + offset > 0
619  else underflow)) if inst.inst() == J
620  else inst)
621 
622  return UrmCutlandProg(l)
623 
624 
625  ##???
626  def write(f):
627  """???
628 
629  Pre: f: fichier (texte) ouvert en lecture
630 
631  O() = ..."""
632  assert isinstance(f, file), f
633 
634  raise NotImplementedError
635 
636 
637 
638 ##\brief Machine virtuelle UrmCutland :
639 # Unlimited Register Machine de <span style="font-variant:small-caps">Cutland</span>
640 # (variante de la machine de
641 # <span style="font-variant:small-caps">Shepherdson</span>
642 # &ndash; <span style="font-variant:small-caps">Sturgis</span>)
643 
644 ##\details
645 # Machine virtuelle constituée d'une infinité (potentielle) de registres numérotées 1, 2, 3, ...\n
646 # Chaque registre contient un naturel (initialement 0).
647 #
648 # Un programme pour cette machine virtuelle
649 # est une suite finie d'instructions numérotées 1, 2, 3, ..., k
650 #
651 # Liste des instructions (a, b et c étant des naturels \htmlonly&ge;\endhtmlonly 1) :
652 # \verbatim
653 # Zero Z(a) : initialiser le registre numéro a avec la valeur 0
654 # Successor S(a) : incrémenter la valeur du registre numéro a
655 # Transfer T(a,b) : initialiser le registre numéro b avec la valeur du registre numéro a
656 # Jump J(a,b,c) : si la valeur du registre numéro a
657 # == la valeur du registre numéro b
658 # alors reprendre à partir de l'instruction numéro c
659 # (si elle existe, sinon arrêter le programme)
660 # sinon ne rien faire\endverbatim
661 #
662 # Cf. <i lang="en">Computability: A introduction to recursive function theory</i>
663 # (Nigel J. <span style="font-variant:small-caps">Cutland</span>,
664 # Cambridge University Press, 2000)
665 #
666 # Cf. \htmlonly <a href="http://www.opimedia.be/Bruno_Marchal/index.htm#Theo" target="_blank">
667 # <tt>http://www.opimedia.be/Bruno_Marchal/index.htm#Theo</tt></a>\endhtmlonly
668 #
669 # Pour une présentation imagée par un "coffee bar"
670 # cf.
671 # \htmlonly
672 # <a lang="en" href="http://www.mail-archive.com/everything-list@eskimo.com/msg14085.html"
673 # target="_blank"><i>Re: Key Post 1,
674 # toward <span style="font-variant:small-caps">Church</span> Thesis and Lobian machine</i></a>
675 # \endhtmlonly
676 # (Bruno <span style="font-variant:small-caps">Marchal</span>)
677 class UrmCutland:
678  """Machine virtuelle UrmCutland :
679  Unlimited Register Machine de Cutland
680  (variante de la machine de Shepherdson - Sturgis)"""
681 
682  ## Renvoie la valeur du registre numéro n
683  def __getitem__(self, n):
684  """Renvoie la valeur du registre numéro n
685 
686  Pre: n: naturel >= 1
687 
688  Result: naturel
689 
690  O() = ..."""
691  assert DSPython.natural_is(n), (type(n), n)
692  assert n >= 1, n
693 
694  self._extend(n)
695  return self._regs[n - 1]
696 
697 
698  ## Initialise la machine virtuelle UrmCutland
699  def __init__(self, init=(), nb=1):
700  """Initialise la machine virtuelle UrmCutland
701  en initialisant ses premiers registres.
702 
703  Si init est un naturel
704  alors initialise les nb premiers registres avec la valeur init.
705  Si init est une séquence
706  alors initialise les premiers registres
707  avec les valeurs de init prises nb fois
708 
709  Pre: init: naturel ou séquence de naturels
710  nb: naturel
711 
712  O() = nb"""
713  assert DSPython.natural_is(init) or isinstance(init, list) or isinstance(init, tuple), \
714  (type(init), init)
715  assert DSPython.natural_is(nb), (type(nb), inb)
716 
717  # self._regs: liste de valeur des registres
718  if DSPython.natural_is(init): # init est un naturel
719  self._regs = [init]*nb
720  else: # init est une séquence
721  if __debug__:
722  for n in init:
723  assert DSPython.natural_is(n), (n, init)
724 
725  self._regs = list(init)*nb
726 
727 
728  ## Itère sur les registres de la machine virtuelle
729  def __iter__(self):
730  """Itère sur les registres de la machine virtuelle
731 
732  O() = 1"""
733  for reg in self._regs:
734  yield reg
735 
736 
737  ## Nombre de registres utilisés
738  def __len__(self):
739  """Renvoie le nombre de registres utilisés
740  (en fait le plus grand numéro de registre
741  parmi les registres ayant été utilisés)
742 
743  Result: naturel
744 
745  O() = 1"""
746  return len(self._regs)
747 
748 
749  ## Initialise la valeur du registre numéro n à value
750  def __setitem__(self, n, value):
751  """Initialise la valeur du registre numéro n à value
752 
753  Pre: n: naturel >= 1
754  value: naturel
755 
756  O() = ..."""
757  assert DSPython.natural_is(n), (type(n), n)
758  assert n >= 1, n
759  assert DSPython.natural_is(value), (type(value), value)
760 
761  self._extend(n)
762  self._regs[n - 1] = value
763 
764 
765  ## Renvoie dans un string la suite des valeurs des registres numérotés de 1 à len()
766  def __str__(self):
767  """Renvoie dans un string la suite des valeurs
768  des registres numérotés de 1 à len()
769 
770  Result: string
771 
772  O() = ..."""
773  return '[' + ' '.join([str(n) for n in self._regs]) + ']'
774 
775 
776  ## Étend self._regs si nécessaire
777  def _extend(self, n):
778  """Si le registre numéro n n'est pas encore défini dans self._regs
779  alors étend self._regs avec des 0 et renvoie True
780  sinon renvoie False
781 
782  Pre: n: naturel >= 1
783 
784  Result: bool
785 
786  O() = ..."""
787  assert DSPython.natural_is(n), (type(n), n)
788  assert n >= 1, n
789 
790  if n > len(self._regs): # il faut étendre
791  self._regs += [0]*(n - len(self._regs))
792  return True
793  else:
794  return False
795 
796 
797  ## Renvoie le "nombre de Gödel" associé à la liste des registres
798  def godelnumber(self):
799  """Renvoie le "nombre de Gödel" associé à la liste des registres,
800  càd 2**r_1 * 3**r_2 * 5**r_3 * 7**r_4 * ...
801  où r_i est la valeur du registre numéro i
802 
803  Result: naturel >= 1
804 
805  O() = ..."""
806  return factors.godelnumber(self._regs)
807 
808 
809  ## Registre numéro a == registre numéro b ?
810  def J_test(self, a, b):
811  """Renvoie True
812  si les registres numéro a et numéro b contiennent la même valeur,
813  False sinon
814 
815  Pre: a: naturel >= 1
816  b: naturel >= 1
817 
818  Result: bool
819 
820  O() = ..."""
821  assert DSPython.natural_is(a), (type(a), a)
822  assert a >= 1, a
823  assert DSPython.natural_is(b), (type(b), b)
824  assert b >= 1, b
825 
826  self._extend(max(a, b))
827  return self._regs[a - 1] == self._regs[b - 1]
828 
829 
830  ##\brief Initialise avec les valeurs lues dans le fichier f
831  # les nb registres à partir du registre numéro n
832  # (si nb != None alors lit au plus nb valeurs)
833  def read(f, n=1, nb=None):# ou dans __init__ ???
834  """Initialise avec les valeurs lues dans le fichier f
835  les registres à partir du registre numéro n
836  (si nb != None alors lit au plus nb valeurs)
837 
838  Pre: f: fichier (texte) ouvert en lecture
839  composé uniquement des caractères '0'..'9', ' ', ',', ';', '\t', 'n'
840  ???
841  n: naturel >= 1
842  nb: None ou naturel
843 
844  O() = ..."""
845  assert isinstance(f, file), f
846  assert DSPython.natural_is(n), (type(n), n)
847  assert n >= 1, n
848  assert (nb == None) or _init__.natural_is(nb), (type(nb), nb)
849 
850  for line in f:
851  line = line.replace('\t', ' ')
852  line = line.replace('\n', ' ')
853  line = line.replace(';', ' ')
854  line = line.replace(',', ' ')
855  l = ' '.split(line.replace(' ', ' '))
856  for s in l:
857  if nb == 0:
858  return
859  number = int(s)
860  if number <= 0:
861  raise 'number readed dont >= 1'
862  self[n] = number
863  n += 1
864  if nb != None:
865  nb -= 1
866 
867 
868  ##\brief Exécute au plus nb instructions (ou toutes si nb == None) de prog
869  # à partir de l'instruction numéro i
870  # et renvoie (numéro de l'instruction finale, nombre d'instructions exécutées)
871  def run(self, prog, i=1, nb=None):
872  """Exécute au plus nb instructions (ou toutes si nb == None) de prog
873  à partir de l'instruction numéro i
874  et renvoie (numéro de l'instruction finale,
875  nombre d'instructions exécutées)
876  (le numéro de l'instruction finale est en fait
877  soit le numéro après la dernière instruction exécutée,
878  soit le numéro d'une instruction qui n'existe pas
879  mentionné par la dernière instruction J exécutée)
880 
881  Pre: prog: UrmCutlandProg
882  i: naturel >= 1
883  nb: None ou naturel
884 
885  Result: (naturel >= 1, naturel)
886 
887  O() = ..."""
888  assert isinstance(prog, UrmCutlandProg), type(prog)
889  assert DSPython.natural_is(i), (type(i), i)
890  assert i >= 1, i
891  assert (nb == None) or DSPython.natural_is(nb), (type(nb), nb)
892 
893  k = 0 # nombre d'instructions exécutées
894 
895  ## Tant qu'il reste des instructions à exécuter
896  while (i <= len(prog)) and ((nb == None) or (k < nb)):
897  assert isinstance(prog[i], UrmCutlandInstruction), (i, type(prog[i]), prog[i])
898 
899  k += 1
900  instruction = prog[i]
901  i += 1
902  if instruction.inst() == Z: # Z(a)
903  self.Z(instruction.a())
904  elif instruction.inst() == S: # S(a)
905  self.S(instruction.a())
906  elif instruction.inst() == T: # T(a,b)
907  self.T(instruction.a(), instruction.b())
908  elif self.J_test(instruction.a(), instruction.b()): # J(a,b,c) avec reg a == reg b
909  assert instruction.inst() == J, instruction.inst()
910 
911  i = instruction.c()
912 
913  return (i, k)
914 
915 
916  ## Instruction Successor : ajoute 1 dans le registre numéro a
917  def S(self, a):
918  """Instruction Successor : ajoute 1 dans le registre numéro a
919 
920  Pre: a: naturel >= 1
921 
922  O() = ..."""
923  assert DSPython.natural_is(a), (type(a), a)
924  assert a >= 1, a
925 
926  self._extend(a)
927  self._regs[a - 1] += 1
928 
929 
930  ##\brief Instruction Transfer :
931  # initialise le registre numéro b avec la valeur du registre numéro a
932  def T(self, a, b):
933  """Instruction Transfer :
934  initialise le registre numéro b
935  avec la valeur du registre numéro a
936 
937  Pre: a: naturel >= 1
938  b: naturel >= 1
939 
940  O() = ..."""
941  assert DSPython.natural_is(a), (type(a), a)
942  assert a >= 1, a
943  assert DSPython.natural_is(b), (type(b), b)
944  assert b >= 1, b
945 
946  self._extend(max(a, b))
947  self._regs[b - 1] = self._regs[a - 1]
948 
949 
950  ##???
951  def write(f):
952  """???
953 
954  Pre: f: fichier (texte) ouvert en lecture
955 
956  O() = ..."""
957  assert isinstance(f, file), f
958 
959  raise NotImplementedError
960 
961 
962  ## Instruction Zero : initialise le registre numéro a à 0
963  def Z(self, a):
964  """Instruction Zero : initialise le registre numéro a à 0
965 
966  Pre: a: naturel >= 1
967 
968  O() = ..."""
969  assert DSPython.natural_is(a), (type(a), a)
970  assert a >= 1, a
971 
972  self._extend(a)
973  self._regs[a - 1] = 0
974 
975 
976 
977 # ############
978 # Constantes #
979 ##############
980 ## Code associé à l'instruction Z
981 Z = 0
982 
983 ## Code associé à l'instruction S
984 S = 1
985 
986 ## Code associé à l'instruction T
987 T = 2
988 
989 ## Code associé à l'instruction J
990 J = 3
991 
992 
993 ## Instruction qui ne fait rien
994 NOTHING = UrmCutlandInstruction(T, 1, 1)
995 
996 
997 
998 ##\brief Programme négation booléenne de n (càd si n == 0 alors 1 sinon 0)\verbatim
999 # Pre: | n |
1000 # Post: | négation booléenne de n |
1001 # Bord: | | 0 |
1002 # O() = 1\endverbatim\hideinitializer
1003 NOT = UrmCutlandProg("""
1004 1) Z(2)
1005 2) J(1,2,5)
1006 3) Z(1)
1007 4) J(1,1,6)
1008 
1009 5) S(1)
1010 """)
1011 
1012 ##\brief Programme a <= b (càd si a <= b alors 1 sinon 0)\verbatim
1013 # Pre: | a | b |
1014 # Post: | a <= b |
1015 # Bord: | | b | min(a, b) |
1016 # O() = min(a, b)\endverbatim\hideinitializer
1017 LESSOREQ = UrmCutlandProg("""
1018  # INV: 0 <= a <= b ou 0 <= b <= a
1019 1) Z(3) # INV: _3 <= a <= b ou _3 <= b <= a
1020 
1021 # Boucle _3 de 0 à min(a, b) :
1022 2) J(1,3,6) # INV: _3 < a <= b ou _3 <= b <= a
1023 3) J(2,3,9) # INV: _3 < a <= b ou _3 < b <= a
1024 4) S(3)
1025 5) J(1,1,2)
1026 
1027 6) Z(1) # INV: _3 == a <= b
1028 7) S(1)
1029 8) J(1,1,10)
1030 
1031 9) Z(1) # INV: _3 == b < a
1032 """)
1033 
1034 ##\brief Programme a < b (càd si a < b alors 1 sinon 0)\verbatim
1035 # Pre: | a | b |
1036 # Post: | a < b |
1037 # Bord: | | b | | si a == b,
1038 # | | b | min(a, b) | sinon
1039 # O() = min(a, b)\endverbatim\hideinitializer
1040 LESS = UrmCutlandProg("""
1041  1) J(1,2,10) # INV: 0 <= a < b ou 0 <= b < a
1042  2) Z(3) # INV: _3 <= a < b ou _3 <= b < a
1043 
1044 # Boucle _3 de 0 à min(a, b) :
1045  3) J(1,3,7) # INV: _3 < a < b ou _3 <= b < a
1046  4) J(2,3,10) # INV: _3 < a < b ou _3 < b < a
1047  5) S(3)
1048  6) J(1,1,3)
1049 
1050  7) Z(1) # INV: _3 == a < b
1051  8) S(1)
1052  9) J(1,1,11)
1053 
1054 10) Z(1) # INV: _3 == b < a
1055 """)
1056 
1057 ##\brief Programme a >= b (càd si a >= b alors 1 sinon 0)\verbatim
1058 # Pre: | a | b |
1059 # Post: | a >= b |
1060 # Bord: | | b | min(a, b) |
1061 # O() = min(a, b)\endverbatim\hideinitializer
1062 GREATOREQ = UrmCutlandProg("""
1063  # INV: 0 <= a <= b ou 0 <= b <= a
1064 1) Z(3) # INV: _3 <= a <= b ou _3 <= b <= a
1065 
1066 # Boucle _3 de 0 à min(a, b) :
1067 2) J(2,3,6) # INV: _3 <= a <= b ou _3 < b <= a
1068 3) J(1,3,9) # INV: _3 < a <= b ou _3 < b <= a
1069 4) S(3)
1070 5) J(1,1,2)
1071 
1072 6) Z(1) # INV: _3 == b <= a
1073 7) S(1)
1074 8) J(1,1,10)
1075 
1076 9) Z(1) # INV: _3 == a < b
1077 """)
1078 
1079 ##\brief Programme a > b (càd si a > b alors 1 sinon 0)\verbatim
1080 # Pre: | a | b |
1081 # Post: | a > b |
1082 # Bord: | | b | | si a == b,
1083 # | | b | min(a, b) | sinon
1084 # O() = min(a, b)\endverbatim\hideinitializer
1085 GREAT = UrmCutlandProg("""
1086  1) J(1,2,10) # INV: 0 <= a < b ou 0 <= b < a
1087  2) Z(3) # INV: _3 <= a < b ou _3 <= b < a
1088 
1089 # Boucle _3 de 0 à min(a, b) :
1090  3) J(2,3,7) # INV: _3 <= a < b ou _3 < b < a
1091  4) J(1,3,10) # INV: _3 < a < b ou _3 < b < a
1092  5) S(3)
1093  6) J(1,1,3)
1094 
1095  7) Z(1) # INV: _3 == b < a
1096  8) S(1)
1097  9) J(1,1,11)
1098 
1099 10) Z(1) # INV: _3 == a < b
1100 """)
1101 
1102 
1103 
1104 ##\brief Programme minimum de a et b : min(a, b)\verbatim
1105 # Pre: | a | b |
1106 # Post: | min(a, b) |
1107 # Bord: | | b | min(a, b) |
1108 # O() = min(a, b)\endverbatim\hideinitializer
1109 MIN = UrmCutlandProg("""
1110  # INV: 0 <= a <= b ou 0 <= b <= a
1111 1) Z(3) # INV: _3 <= a <= b ou _3 <= b <= a
1112 
1113 # Boucle _3 de 0 à min(a, b) :
1114 2) J(1,3,6) # INV: _3 < a <= b ou _3 <= b <= a
1115 3) J(2,3,6) # INV: _3 < a <= b ou _3 < b <= a
1116 4) S(3)
1117 5) J(1,1,2)
1118 
1119 6) T(3,1) # INV: _3 == a <= b ou _3 == b < a
1120 """)
1121 
1122 ##\brief Programme maximum de a et b : max(a, b)\verbatim
1123 # Pre: | a | b |
1124 # Post: | max(a, b) |
1125 # Bord: | | b | min(a, b) |
1126 # O() = min(a, b)\endverbatim\hideinitializer
1127 MAX = UrmCutlandProg("""
1128  # INV: 0 <= a <= b ou 0 <= b <= a
1129 1) Z(3) # INV: _3 <= a <= b ou _3 <= b <= a
1130 
1131 # Boucle _3 de 0 à min(a, b) :
1132 2) J(1,3,6) # INV: _3 < a <= b ou _3 <= b <= a
1133 3) J(2,3,7) # INV: _3 < a <= b ou _3 < b <= a
1134 4) S(3)
1135 5) J(1,1,2)
1136 
1137 6) T(2,1) # INV: _3 == a <= b
1138 """)
1139 
1140 
1141 
1142 ##\brief Programme n + 1\verbatim
1143 # Pre: | n |
1144 # Post: | n |
1145 # O() = 1\endverbatim
1146 INC = UrmCutlandProg((UrmCutlandInstruction(S, 1), ))
1147 
1148 ##\brief Programme n - 1\verbatim
1149 # Pre: | n |
1150 # Post: | n - 1 | si n > 0, sinon ne s'arrête jamais
1151 # Bord: | | n | n |
1152 # O() = n\endverbatim\hideinitializer
1153 DEC = UrmCutlandProg("""
1154 1) T(1,3)
1155 2) Z(1)
1156 3) Z(2)
1157 4) S(2)
1158 
1159 # Boucle _2 de 1 à n :
1160 5) J(2,3,9)
1161 6) S(1)
1162 7) S(2)
1163 8) J(1,1,5)
1164 """)
1165 
1166 ##\brief Programme a + b\verbatim
1167 # Pre: | a | b |
1168 # Post: | a + b |
1169 # Bord: | | b | b |
1170 # O() = b\endverbatim\hideinitializer
1171 ADD = UrmCutlandProg("""
1172 1) Z(3)
1173 
1174 # Boucle _3 de 0 à b :
1175 2) J(2,3,6)
1176 3) S(1)
1177 4) S(3)
1178 5) J(1,1,2)
1179 """)
1180 
1181 ##\brief Programme a - b\verbatim
1182 # Pre: | a | b |
1183 # Post: | a - b | si a >= b, sinon ne s'arrête jamais
1184 # Bord: | | a | a |
1185 # O() = a - b\endverbatim\hideinitializer
1186 SUB = UrmCutlandProg("""
1187 1) T(1,3)
1188 2) Z(1)
1189 
1190 # Boucle _2 de b à a :
1191 3) J(2,3,7)
1192 4) S(1)
1193 5) S(2)
1194 6) J(1,1,3)
1195 """)
1196 
1197 ##\brief Programme a*b\verbatim
1198 # Pre: | a | b |
1199 # Post: | a*b |
1200 # Bord: | | a | | b | b | si b == 0,
1201 # | | a | a | b | b | sinon
1202 # O() = a*b\endverbatim\hideinitializer
1203 MUL = UrmCutlandProg("""
1204  1) T(2,4)
1205  2) T(1,2)
1206  3) Z(1)
1207  4) Z(5)
1208 
1209 # Boucle _5 de 0 à b :
1210  5) J(4,5,13)
1211  6) i(ADD)
1212 11) S(5)
1213 12) J(1,1,5)
1214 """)
1215 
1216 ##\brief Programme division euclidienne : quotient entier a//b et reste a%b\verbatim
1217 # Pre: | a | b |
1218 # Post: | a//b | a%b | si b != 0, sinon ne s'arrête jamais
1219 # Bord: | | | a | b | a |
1220 # O() = a\endverbatim\hideinitializer
1221 DIV = UrmCutlandProg("""
1222  1) T(1,3)
1223  2) T(2,4)
1224  3) Z(1)
1225  4) J(1,2,4) # si b == 0
1226  5) Z(2)
1227  6) Z(5)
1228 
1229 # Boucle _5 de 0 à a :
1230  7) J(3,5,15)
1231  8) S(2) # reste += 1
1232  9) S(5)
1233 10) J(2,4,12) # si reste == b
1234 11) J(1,1,7)
1235 
1236 12) S(1) # quotient += 1
1237 13) Z(2) # reste = 0
1238 14) J(1,1,7)
1239 """)
1240 
1241 ##\brief Programme a<sup>b</sup> == a**b\verbatim
1242 # Pre: | a | b |
1243 # Post: | a**b |
1244 # Bord: | | a | 0 | 0 | 0 | b | b | si b == 0,
1245 # | | a | | a | a | b | b | si b > 0 et a == 0,
1246 # | | a | a**(b - 1) | a | a | b | b | sinon
1247 # O() = a**b\endverbatim\hideinitializer
1248 POW = UrmCutlandProg("""
1249  1) T(2,6)
1250  2) T(1,2)
1251  3) Z(1)
1252  4) S(1)
1253  5) Z(7)
1254 
1255 # Boucle _7 de 0 à b :
1256  6) J(6,7,22)
1257  7) i(MUL)
1258 19) S(7)
1259 20) T(4,2)
1260 21) J(1,1,6)
1261 """)
1262 
1263 
1264 ##\brief Programme plus grand commun diviseur : gcd(a, b)\verbatim
1265 # Pre: | a | b |
1266 # Post: | gcd(a, b) | | si a != 0 ou a!= b, sinon ne s'arrête jamais
1267 # Bord: | | 0 | 0 | gcd(a, b) | 0 | si a == 0 ou b == 0,
1268 # | | 0 | k*gcd(a, b) | gcd(a, b) | 0 | sinon
1269 # (avec k naturel >= 1 et gcd(a, b) <= k*gcd(a, b) <= max(a, b))
1270 # O() = ...\endverbatim\hideinitializer
1271 GCD = UrmCutlandProg("""
1272 # Boucle tant que _2 > 0 : (algorithme d'Euclide)
1273  1) Z(5)
1274  2) J(2,5,19)
1275  3) i(DIV) # | a//b | a%b | a | b | a |
1276 17) T(4,1) # | b | a%b | a | b | a |
1277 18) J(1,1,1)
1278 19) J(1,5,19)
1279 """)
1280 
1281 ##\brief Programme n<sup>e</sup> et (n + 1)<sup>e</sup> nombres de Fibonacci :
1282 # F<sub>n</sub> et F<sub>n + 1</sub>\verbatim
1283 # Pre: | n |
1284 # Post: | F_n | F_(n+1) |
1285 # Bord: | | | | n | n | si n == 0,
1286 # | | | F_n | n | n | sinon
1287 # O() = F_(n+1)\endverbatim\hideinitializer
1288 FIBONACCI2 = UrmCutlandProg("""
1289  1) T(1,4)
1290  2) Z(1)
1291  3) Z(2)
1292  4) S(2)
1293  5) Z(5)
1294 
1295 # Boucle _5 de 0 à n :
1296  6) J(4,5,16)
1297  7) i(ADD)
1298 12) T(1,2)
1299 13) T(3,1)
1300 14) S(5)
1301 15) J(1,1,6)
1302 """)
1303 
1304 ##\brief Programme n!\verbatim
1305 # Pre: | n |
1306 # Post: | n! |
1307 # Bord: | | n | | | | n | si n == 0,
1308 # | | n | (n - 1)! | n | n | n | sinon
1309 # O() = n!\endverbatim\hideinitializer
1310 FACTORIAL = UrmCutlandProg("""
1311  1) T(1,6)
1312  2) Z(1)
1313  3) S(1)
1314  4) Z(2)
1315 
1316 # Boucle _2 de 0 à n :
1317  5) J(2,6,21)
1318  6) S(2)
1319  7) i(MUL)
1320 19) T(4,2)
1321 20) J(1,1,5)
1322 """)
1323 
1324 
1325 
1326 # ######\cond MAINTEST
1327 # Main #
1328 ########
1329 if __name__ == '__main__':
1330  def main_test():
1331  """Test du module"""
1332  import fractions, math, sys
1333 
1334  try:
1335  if not 'profile' in dir():
1336  import psyco
1337  psyco.full()
1338  except ImportError:
1339  pass
1340 
1341  import DSPython.debug as debug
1342  import DSPython.nat32 as nat32
1343 
1344  debug.test_begin(VERSION, __debug__)
1345 
1346  print('Z == {0}'.format(Z)); sys.stdout.flush()
1347  assert DSPython.natural_is(Z), (type(Z), Z)
1348  assert Z == 0, Z
1349 
1350  print('S == {0}'.format(S)); sys.stdout.flush()
1351  assert DSPython.natural_is(S), (type(S), S)
1352  assert S == 1, S
1353 
1354  print('T == {0}'.format(T)); sys.stdout.flush()
1355  assert DSPython.natural_is(T), (type(T), T)
1356  assert T == 2, T
1357 
1358  print('J == {0}'.format(J)); sys.stdout.flush()
1359  assert DSPython.natural_is(J), (type(J), J)
1360  assert J == 3, J
1361 
1362 
1363 
1364  print()
1365  print('UrmCutlandInstruction()...', end=''); sys.stdout.flush()
1366  print('???', end='')
1367  print('ok'); sys.stdout.flush()
1368 
1369 
1370  print('UrmCutlandInstruction.__eq__()...', end=''); sys.stdout.flush()
1371  print('???', end='')
1372  print('ok'); sys.stdout.flush()
1373 
1374 
1375  print('UrmCutlandInstruction.__ne__()...', end=''); sys.stdout.flush()
1376  print('???', end='')
1377  print('ok'); sys.stdout.flush()
1378 
1379 
1380  print('UrmCutlandInstruction.__str__()...', end=''); sys.stdout.flush()
1381  print('???', end='')
1382  print('ok'); sys.stdout.flush()
1383 
1384 
1385  print('UrmCutlandInstruction.a()...', end=''); sys.stdout.flush()
1386  print('???', end='')
1387  print('ok'); sys.stdout.flush()
1388 
1389 
1390  print('UrmCutlandInstruction.b()...', end=''); sys.stdout.flush()
1391  print('???', end='')
1392  print('ok'); sys.stdout.flush()
1393 
1394 
1395  print('UrmCutlandInstruction.c()...', end=''); sys.stdout.flush()
1396  print('???', end='')
1397  print('ok'); sys.stdout.flush()
1398 
1399 
1400  print('UrmCutlandInstruction.godelnumber()...', end=''); sys.stdout.flush()
1401  print('???', end='')
1402  print('ok'); sys.stdout.flush()
1403 
1404 
1405  print('UrmCutlandInstruction.inst()...', end=''); sys.stdout.flush()
1406  print('???', end='')
1407  print('ok'); sys.stdout.flush()
1408 
1409 
1410  print("NOTHING == '%s'" % NOTHING); sys.stdout.flush()
1411  assert isinstance(NOTHING, UrmCutlandInstruction), type(NOTHING)
1412  assert str(NOTHING) == 'T(1,1)', str(NOTHING)
1413 
1414 
1415 
1416  print()
1417  print('UrmCutlandProg()...', end=''); sys.stdout.flush()
1418  print('???', end='')
1419  prog = UrmCutlandProg((' \n \t ',
1420  """ \t
1421  \t """))
1422  assert prog == UrmCutlandProg([]), [str(i) for i in prog]
1423 
1424  prog = UrmCutlandProg('1) S(1)')
1425  assert prog == INC, [str(i) for i in prog]
1426 
1427  prog = UrmCutlandProg(('Z ( \t \n 3 )#####',
1428  ' J(2, 3, 000 # comment',
1429  ' 00 6 ) S(1) # comment \n S(3) J(1,1,\t2)'))
1430  assert prog == ADD, [str(i) for i in prog]
1431 
1432  prog = UrmCutlandProg("""
1433  T(2,4) # initialisation
1434  T(1,2)
1435  Z(1)
1436  Z(5)
1437  J(4,5,13)
1438  Z(3) # [ADD
1439  J(2,3,11)
1440  S(1)
1441  S(3)
1442  J(1,1,7) # ADD]
1443  S(5) # boucle sur ADD
1444  J(1,1,5)""")
1445  assert prog == MUL, [str(i) for i in prog]
1446  print('ok'); sys.stdout.flush()
1447 
1448 
1449  print('UrmCutlandProg.__eq__()...', end=''); sys.stdout.flush()
1450  print('???', end='')
1451  print('ok'); sys.stdout.flush()
1452 
1453 
1454  print('UrmCutlandProg.__getitem__()...', end=''); sys.stdout.flush()
1455  print('???', end='')
1456  print('ok'); sys.stdout.flush()
1457 
1458 
1459  print('UrmCutlandProg.__iter__()...', end=''); sys.stdout.flush()
1460  print('???', end='')
1461  print('ok'); sys.stdout.flush()
1462 
1463 
1464  print('UrmCutlandProg.__len__()...', end=''); sys.stdout.flush()
1465  print('???', end='')
1466  print('ok'); sys.stdout.flush()
1467 
1468 
1469  print('UrmCutlandProg.__ne__()...', end=''); sys.stdout.flush()
1470  print('???', end='')
1471  print('ok'); sys.stdout.flush()
1472 
1473 
1474  print('UrmCutlandProg.__setitem__()...', end=''); sys.stdout.flush()
1475  print('???', end='')
1476  print('ok'); sys.stdout.flush()
1477 
1478 
1479  print('UrmCutlandProg.__str__()...', end=''); sys.stdout.flush()
1480  print('???', end='')
1481  print('ok'); sys.stdout.flush()
1482 
1483 
1484  print('UrmCutlandProg.changeInstrNum()...', end=''); sys.stdout.flush()
1485  print('???', end='')
1486  print('ok'); sys.stdout.flush()
1487 
1488 
1489  print('UrmCutlandProg.decompile()...', end=''); sys.stdout.flush()
1490  print('???', end='')
1491  src = ADD.decompile(concat=' ')
1492  assert src == '1) Z(3) 2) J(2,3,6) 3) S(1) 4) S(3) 5) J(1,1,2)', src
1493 
1494  src = ADD.decompile(concat=None)
1495  assert src == ['1) Z(3)',
1496  '2) J(2,3,6)',
1497  '3) S(1)',
1498  '4) S(3)',
1499  '5) J(1,1,2)'], src
1500 
1501  src = MUL.decompile(num=') \t')
1502  assert src == """1) \tT(2,4)
1503 2) \tT(1,2)
1504 3) \tZ(1)
1505 4) \tZ(5)
1506 5) \tJ(4,5,13)
1507 6) \tZ(3)
1508 7) \tJ(2,3,11)
1509 8) \tS(1)
1510 9) \tS(3)
1511 10) \tJ(1,1,7)
1512 11) \tS(5)
1513 12) \tJ(1,1,5)""", src
1514  print('ok'); sys.stdout.flush()
1515 
1516 
1517  print('UrmCutlandProg.godelnumber()...', end=''); sys.stdout.flush()
1518  print('???', end='')
1519  print('ok'); sys.stdout.flush()
1520 
1521 
1522  print('UrmCutlandProg.read()...', end=''); sys.stdout.flush()
1523  print('???', end='')
1524  print('ok'); sys.stdout.flush()
1525 
1526 
1527  print('UrmCutlandProg.shiftInstrNum()...', end=''); sys.stdout.flush()
1528  print('???', end='')
1529  print('ok'); sys.stdout.flush()
1530 
1531 
1532  print('UrmCutlandProg.write()...', end=''); sys.stdout.flush()
1533  print('???', end='')
1534  print('ok'); sys.stdout.flush()
1535 
1536 
1537 
1538  print()
1539  print('UrmCutland()...', end=''); sys.stdout.flush()
1540  print('???', end='')
1541  print('ok'); sys.stdout.flush()
1542 
1543 
1544  print('UrmCutland.__getitem__()...', end=''); sys.stdout.flush()
1545  print('???', end='')
1546  print('ok'); sys.stdout.flush()
1547 
1548 
1549  print('UrmCutland.__iter__()...', end=''); sys.stdout.flush()
1550  print('???', end='')
1551  print('ok'); sys.stdout.flush()
1552 
1553 
1554  print('UrmCutland.__len__()...', end=''); sys.stdout.flush()
1555  print('???', end='')
1556  print('ok'); sys.stdout.flush()
1557 
1558 
1559  print('UrmCutland.__setitem__()...', end=''); sys.stdout.flush()
1560  print('???', end='')
1561  print('ok'); sys.stdout.flush()
1562 
1563 
1564  print('UrmCutland.__str__()...', end=''); sys.stdout.flush()
1565  print('???', end='')
1566  print('ok'); sys.stdout.flush()
1567 
1568 
1569  print('UrmCutland._extend()...', end=''); sys.stdout.flush()
1570  print('???', end='')
1571  print('ok'); sys.stdout.flush()
1572 
1573 
1574  print('UrmCutland.godelnumber()...', end=''); sys.stdout.flush()
1575  print('???', end='')
1576  print('ok'); sys.stdout.flush()
1577 
1578 
1579  print('UrmCutland.J_test()...', end=''); sys.stdout.flush()
1580  print('???', end='')
1581  print('ok'); sys.stdout.flush()
1582 
1583 
1584  print('UrmCutland.read()...', end=''); sys.stdout.flush()
1585  print('???', end='')
1586  print('ok'); sys.stdout.flush()
1587 
1588 
1589  print('UrmCutland.run()...', end=''); sys.stdout.flush()
1590  print('???', end='')
1591  print('ok'); sys.stdout.flush()
1592 
1593 
1594  print('UrmCutland.S()...', end=''); sys.stdout.flush()
1595  print('???', end='')
1596  print('ok'); sys.stdout.flush()
1597 
1598 
1599  print('UrmCutland.T()...', end=''); sys.stdout.flush()
1600  print('???', end='')
1601  print('ok'); sys.stdout.flush()
1602 
1603 
1604  print('UrmCutland.write()...', end=''); sys.stdout.flush()
1605  print('???', end='')
1606  print('ok'); sys.stdout.flush()
1607 
1608 
1609  print('UrmCutland.Z()...', end=''); sys.stdout.flush()
1610  print('???', end='')
1611  print('ok'); sys.stdout.flush()
1612 
1613 
1614 
1615  print()
1616  print('NOT...', end=''); sys.stdout.flush()
1617  assert isinstance(NOT, UrmCutlandProg), type(NOT)
1618  for inst in NOT:
1619  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1620 
1621  for n in range(100):
1622  m = UrmCutland(init=n)
1623  (i, nb) = m.run(NOT)
1624  assert i == len(NOT) + 1, (n, i, len(NOT), nb)
1625  assert nb == 3 + (n != 0), (n, i, nb)
1626  assert len(m) == 2, (n, len(m))
1627  assert m[1] == (not bool(n)), (n, m[1])
1628  assert m[2] == 0, (n, m[2])
1629  print('ok'); sys.stdout.flush()
1630 
1631 
1632  print('LESSOREQ...', end=''); sys.stdout.flush()
1633  assert isinstance(LESSOREQ, UrmCutlandProg), type(LESSOREQ)
1634  for inst in LESSOREQ:
1635  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1636 
1637  for a in range(50):
1638  for b in range(20):
1639  m = UrmCutland(init=(a, b))
1640  (i, nb) = m.run(LESSOREQ)
1641  assert i == len(LESSOREQ) + 1, (a, b, i, len(LESSOREQ), nb)
1642  assert nb <= len(LESSOREQ)*(min(a, b) + 1), (a, b, i, len(LESSOREQ), nb,
1643  len(LESSOREQ)*(min(a, b) + 1))
1644  assert len(m) == 3, (a, b, len(m))
1645  assert m[1] == (a <= b), (a, b, m[1], a <= b)
1646  assert m[2] == b, (a, b, m[2])
1647  assert m[3] == min(a, b), (a, b, m[3])
1648  print('ok'); sys.stdout.flush()
1649 
1650 
1651  print('LESS...', end=''); sys.stdout.flush()
1652  assert isinstance(LESS, UrmCutlandProg), type(LESS)
1653  for inst in LESS:
1654  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1655 
1656  for a in range(50):
1657  for b in range(20):
1658  m = UrmCutland(init=(a, b))
1659  (i, nb) = m.run(LESS)
1660  assert i == len(LESS) + 1, (a, b, i, len(LESS), nb)
1661  assert nb <= len(LESS)*(min(a, b) + 1), (a, b, i, len(LESS), nb,
1662  len(LESS)*(min(a, b) + 1))
1663  assert len(m) == (2 + (a != b)), (a, b, len(m))
1664  assert m[1] == (a < b), (a, b, m[1], a < b)
1665  assert m[2] == b, (a, b, m[2])
1666  if a != b:
1667  assert m[3] == min(a, b), (a, b, m[3])
1668  print('ok'); sys.stdout.flush()
1669 
1670 
1671  print('GREATOREQ...', end=''); sys.stdout.flush()
1672  assert isinstance(GREATOREQ, UrmCutlandProg), type(GREATOREQ)
1673  for inst in GREATOREQ:
1674  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1675 
1676  for a in range(50):
1677  for b in range(20):
1678  m = UrmCutland(init=(a, b))
1679  (i, nb) = m.run(GREATOREQ)
1680  assert i == len(GREATOREQ) + 1, (a, b, i, len(GREATOREQ), nb)
1681  assert nb <= len(GREATOREQ)*(min(a, b) + 1), (a, b, i, len(GREATOREQ), nb,
1682  len(GREATOREQ)*(min(a, b) + 1))
1683  assert len(m) == 3, (a, b, len(m))
1684  assert m[1] == (a >= b), (a, b, m[1], a >= b)
1685  assert m[2] == b, (a, b, m[2])
1686  assert m[3] == min(a, b), (a, b, m[3])
1687  print('ok'); sys.stdout.flush()
1688 
1689 
1690  print('GREAT...', end=''); sys.stdout.flush()
1691  assert isinstance(GREAT, UrmCutlandProg), type(GREAT)
1692  for inst in GREAT:
1693  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1694 
1695  for a in range(50):
1696  for b in range(20):
1697  m = UrmCutland(init=(a, b))
1698  (i, nb) = m.run(GREAT)
1699  assert i == len(GREAT) + 1, (a, b, i, len(GREAT), nb)
1700  assert nb <= len(GREAT)*(min(a, b) + 1), (a, b, i, len(GREAT), nb,
1701  len(GREAT)*(min(a, b) + 1))
1702  assert len(m) == (2 + (a != b)), (a, b, len(m))
1703  assert m[1] == (a > b), (a, b, m[1], a > b)
1704  assert m[2] == b, (a, b, m[2])
1705  if a != b:
1706  assert m[3] == min(a, b), (a, b, m[3])
1707  print('ok'); sys.stdout.flush()
1708 
1709 
1710  print('MIN...', end=''); sys.stdout.flush()
1711  assert isinstance(MIN, UrmCutlandProg), type(MIN)
1712  for inst in MIN:
1713  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1714 
1715  for a in range(50):
1716  for b in range(20):
1717  m = UrmCutland(init=(a, b))
1718  (i, nb) = m.run(MIN)
1719  assert i == len(MIN) + 1, (a, b, i, len(MIN), nb)
1720  assert nb <= len(MIN)*(min(a, b) + 1), (a, b, i, len(MIN), nb,
1721  len(MIN)*(min(a, b) + 1))
1722  assert len(m) == 3, (a, b, len(m))
1723  assert m[1] == min(a, b), (a, b, m[1], min(a, b))
1724  assert m[2] == b, (a, b, m[2])
1725  assert m[3] == min(a, b), (a, b, m[3])
1726  print('ok'); sys.stdout.flush()
1727 
1728 
1729  print('MAX...', end=''); sys.stdout.flush()
1730  assert isinstance(MAX, UrmCutlandProg), type(MAX)
1731  for inst in MAX:
1732  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1733 
1734  for a in range(50):
1735  for b in range(20):
1736  m = UrmCutland(init=(a, b))
1737  (i, nb) = m.run(MAX)
1738  assert i == len(MAX) + 1, (a, b, i, len(MAX), nb)
1739  assert nb <= len(MAX)*(min(a, b) + 1), (a, b, i, len(MAX), nb,
1740  len(MAX)*(min(a, b) + 1))
1741  assert len(m) == 3, (a, b, len(m))
1742  assert m[1] == max(a, b), (a, b, m[1], max(a, b))
1743  assert m[2] == b, (a, b, m[2])
1744  assert m[3] == min(a, b), (a, b, m[3])
1745  print('ok'); sys.stdout.flush()
1746 
1747 
1748  print('INC...', end=''); sys.stdout.flush()
1749  assert isinstance(INC, UrmCutlandProg), type(INC)
1750  for inst in INC:
1751  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1752 
1753  for n in range(100):
1754  m = UrmCutland(init=n)
1755  (i, nb) = m.run(INC)
1756  assert i == len(INC) + 1, (n, i, len(INC), nb)
1757  assert nb == 1, (n, nb)
1758  assert len(m) == 1, (n, len(m))
1759  assert m[1] == n + 1, (n, m[1])
1760 
1761  assert m[5] == 0, (n, m[5])
1762  assert len(m) == 5, (n, len(m))
1763  assert m[1] == n + 1, (n, m[1])
1764  assert m[2] == 0, (n, m[2])
1765  assert m[3] == 0, (n, m[3])
1766  assert m[4] == 0, (n, m[4])
1767  assert len(m) == 5, (n, len(m))
1768  print('ok'); sys.stdout.flush()
1769 
1770 
1771  print('DEC...', end=''); sys.stdout.flush()
1772  assert isinstance(DEC, UrmCutlandProg), type(DEC)
1773  for inst in DEC:
1774  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1775 
1776  m = UrmCutland(init=0)
1777  (i, nb) = m.run(DEC, nb=10000)
1778  assert nb == 10000, (i, nb)
1779 
1780  for n in range(1, 100):
1781  m = UrmCutland(init=n)
1782  (i, nb) = m.run(DEC)
1783  assert i == len(DEC) + 1, (n, i, len(DEC), nb)
1784  assert nb <= len(DEC)*n, (n, i, len(DEC), nb, len(DEC)*(min(a, b) + 1))
1785  assert len(m) == 3, (n, len(m))
1786  assert m[1] == n - 1, (n, m[1])
1787  assert m[2] == n, (n, m[2])
1788  assert m[3] == n, (n, m[3])
1789 
1790  assert m[5] == 0, (n, m[5])
1791  assert len(m) == 5, (n, len(m))
1792  assert m[1] == n - 1, (n, m[1])
1793  assert m[2] == n, (n, m[2])
1794  assert m[3] == n, (n, m[3])
1795  assert m[4] == 0, (n, m[4])
1796  assert len(m) == 5, (n, len(m))
1797  print('ok'); sys.stdout.flush()
1798 
1799 
1800  print('ADD...', end=''); sys.stdout.flush()
1801  assert isinstance(ADD, UrmCutlandProg), type(ADD)
1802  for inst in ADD:
1803  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1804 
1805  for a in range(50):
1806  for b in range(20):
1807  m = UrmCutland(init=(a, b))
1808  (i, nb) = m.run(ADD)
1809  assert i == len(ADD) + 1, (a, b, i, len(ADD), nb)
1810  assert nb <= len(ADD)*(b + 1), (a, b, i, len(ADD), nb, len(ADD)*(b + 1))
1811  assert len(m) == 3, (a, b, len(m))
1812  assert m[1] == a + b, (a, b, m[1], a + b)
1813  assert m[2] == b, (a, b, m[2])
1814  assert m[3] == b, (a, b, m[3])
1815  print('ok'); sys.stdout.flush()
1816 
1817 
1818  print('SUB...', end=''); sys.stdout.flush()
1819  assert isinstance(SUB, UrmCutlandProg), type(SUB)
1820  for inst in SUB:
1821  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1822 
1823  for a in range(20):
1824  for b in range(15):
1825  m = UrmCutland(init=(a, b))
1826  if a >= b:
1827  (i, nb) = m.run(SUB)
1828  assert i == len(SUB) + 1, (a, b, i, len(SUB), nb)
1829  assert nb < 100, (a, b, i, nb)
1830  assert nb <= len(SUB)*(a - b + 1), (a, b, i, len(SUB), nb,
1831  len(SUB)*(a - b + 1))
1832  assert len(m) == 3, (a, b, len(m))
1833  assert m[1] == a - b, (a, b, m[1], a - b)
1834  assert m[2] == a, (a, b, m[2])
1835  assert m[3] == a, (a, b, m[3])
1836  elif debug.assertspeed >= debug.ASSERT_NORMAL:
1837  (i, nb) = m.run(SUB, nb=1000)
1838  assert nb == 1000, (a, b, i, nb)
1839  if debug.assertspeed < debug.ASSERT_NORMAL:
1840  print(debug.assertspeed_str(), end='')
1841  print('ok'); sys.stdout.flush()
1842 
1843 
1844  print('MUL...', end=''); sys.stdout.flush()
1845  assert isinstance(MUL, UrmCutlandProg), type(MUL)
1846  for inst in MUL:
1847  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1848 
1849  for a in range(40 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
1850  for b in range(15 if debug.assertspeed >= debug.ASSERT_NORMAL else 10):
1851  m = UrmCutland(init=(a, b))
1852  (i, nb) = m.run(MUL)
1853  assert i == len(MUL) + 1, (a, b, i, len(MUL), nb)
1854  assert nb <= len(MUL)*((a + 1)*b + 1), (a, b, i, len(MUL), nb,
1855  len(MUL)*((a + 1)*b + 1))
1856  assert len(m) == 5, (a, b, len(m))
1857  assert m[1] == a*b, (a, b, m[1], a*b)
1858  assert m[2] == a, (a, b, m[2])
1859  if b == 0:
1860  assert m[3] == 0, (a, b, m[3])
1861  else:
1862  assert m[3] == a, (a, b, m[3])
1863  assert m[4] == b, (a, b, m[4])
1864  assert m[5] == b, (a, b, m[5])
1865  if debug.assertspeed < debug.ASSERT_NORMAL:
1866  print(debug.assertspeed_str(), end='')
1867  print('ok'); sys.stdout.flush()
1868 
1869 
1870  print('DIV...', end=''); sys.stdout.flush()
1871  assert isinstance(DIV, UrmCutlandProg), type(DIV)
1872  for inst in DIV:
1873  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1874 
1875  for a in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
1876  m = UrmCutland(init=(a, 0))
1877  if debug.assertspeed >= debug.ASSERT_NORMAL:
1878  (i, nb) = m.run(DIV, nb=5000)
1879  assert nb == 5000, (a, i, nb)
1880  for b in range(1, 20):
1881  m = UrmCutland(init=(a, b))
1882  (i, nb) = m.run(DIV)
1883  assert i == len(DIV) + 1, (a, b, i, len(DIV), nb)
1884  assert nb < 500, (a, b, i, nb)
1885  assert nb <= len(DIV)*(a + 1), (a, b, i, len(DIV), nb, len(DIV)*(a + 1))
1886  assert len(m) == 5, (a, b, len(m))
1887  assert m[1] == a//b, (a, b, m[1], a//b)
1888  assert m[2] == a%b, (a, b, m[2], a%b)
1889  assert m[3] == a, (a, b, m[3])
1890  assert m[4] == b, (a, b, m[4])
1891  assert m[5] == a, (a, b, m[5])
1892  if debug.assertspeed < debug.ASSERT_NORMAL:
1893  print(debug.assertspeed_str(), end='')
1894  print('ok'); sys.stdout.flush()
1895 
1896 
1897  print('POW...', end=''); sys.stdout.flush()
1898  assert isinstance(POW, UrmCutlandProg), type(POW)
1899  for inst in POW:
1900  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1901 
1902  for a in range(10 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
1903  for b in range(6):
1904  m = UrmCutland(init=(a, b))
1905  (i, nb) = m.run(POW)
1906  assert nb <= len(POW)*((a + 2)**(b + 1)), (a, b, i, len(POW), nb,
1907  len(POW)*((a + 1)**(b + 1)))
1908  assert i == len(POW) + 1, (a, b, i, len(POW), nb)
1909  assert len(m) == 7, (a, b, len(m))
1910  assert m[1] == a**b, (a, b, m[1], a**b)
1911  assert m[2] == a, (a, b, m[2])
1912  if b == 0:
1913  assert m[3] == 0, (a, b, m[3])
1914  assert m[4] == 0, (a, b, m[4])
1915  assert m[5] == 0, (a, b, m[5])
1916  else:
1917  if a == 0:
1918  assert m[3] == 0, (a, b, m[3])
1919  else:
1920  assert m[3] == a**(b - 1), (a, b, m[3], a**(b - 1))
1921  assert m[4] == a, (a, b, m[4])
1922  assert m[5] == a, (a, b, m[5])
1923  assert m[6] == b, (a, b, m[6])
1924  assert m[7] == b, (a, b, m[7])
1925  if debug.assertspeed < debug.ASSERT_NORMAL:
1926  print(debug.assertspeed_str(), end='')
1927  print('ok'); sys.stdout.flush()
1928 
1929 
1930  print('GCD...', end=''); sys.stdout.flush()
1931  assert isinstance(GCD, UrmCutlandProg), type(GCD)
1932  for inst in GCD:
1933  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1934 
1935  for a in range(50 if debug.assertspeed >= debug.ASSERT_NORMAL else 20):
1936  for b in range(20):
1937  m = UrmCutland(init=(a, b))
1938  if (a == 0) and (b == 0):
1939  (i, nb) = m.run(GCD, nb=10000)
1940  assert nb == 10000, (i, nb)
1941  else:
1942  (i, nb) = m.run(GCD)
1943  assert i == len(GCD) + 1, (a, b, i, len(GCD), nb)
1944  assert nb < 1000, (a, b, i, nb)
1945  assert nb <= len(GCD)*(max(a, b) + 2), (a, b, i, len(GCD), nb,
1946  len(GCD)*(max(a, b) + 2))
1947  assert len(m) == 5, (a, b, len(m))
1948  gcd_a_b = fractions.gcd(a, b)
1949  assert m[1] == gcd_a_b, (a, b, m[1], gcd_a_b)
1950  assert m[2] == 0, (a, b, m[2])
1951  if (a == 0) or (b == 0):
1952  assert m[3] == 0, (a, b, m[3])
1953  else:
1954  assert m[3] != 0, (a, b)
1955  assert gcd_a_b <= m[3], (a, b, m[3], gcd_a_b)
1956  assert m[3]%gcd_a_b == 0, (a, b, m[3], gcd_a_b,
1957  m[3]%gcd_a_b)
1958  assert m[3] <= max(a, b), (a, b, m[3])
1959  if b == 0:
1960  assert m[4] == 0, (a, b, m[4])
1961  else:
1962  assert m[4] == gcd_a_b, (a, b, m[4], gcd_a_b)
1963  assert m[5] == 0, (a, b, m[5])
1964  if debug.assertspeed < debug.ASSERT_NORMAL:
1965  print(debug.assertspeed_str(), end='')
1966  print('ok'); sys.stdout.flush()
1967 
1968 
1969  print('FIBONACCI2...', end=''); sys.stdout.flush()
1970  assert isinstance(FIBONACCI2, UrmCutlandProg), type(FIBONACCI2)
1971  for inst in FIBONACCI2:
1972  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1973 
1974  for n in range(20 if debug.assertspeed >= debug.ASSERT_NORMAL else 10):
1975  m = UrmCutland(init=n)
1976  (i, nb) = m.run(FIBONACCI2)
1977  assert i == len(FIBONACCI2) + 1, (n, i, len(FIBONACCI2), nb)
1978  assert nb <= len(FIBONACCI2)*(nat32.fibonacci(n + 1) + 1), \
1979  (n, i, len(FIBONACCI2),
1980  nb, nat32.fibonacci(n + 1),len(FIBONACCI2)*(nat32.fibonacci(n + 1) + 1))
1981  assert len(m) == 5, (n, len(m))
1982  assert m[1] == nat32.fibonacci(n), (n, m[1], nat32.fibonacci(n))
1983  assert m[2] == nat32.fibonacci(n + 1), (n, m[2], nat32.fibonacci(n + 1))
1984  assert m[3] == nat32.fibonacci(n), (n, m[3], nat32.fibonacci(n))
1985  assert m[4] == n, (n, m[4])
1986  assert m[5] == n, (n, m[5])
1987  if debug.assertspeed < debug.ASSERT_NORMAL:
1988  print(debug.assertspeed_str(), end='')
1989  print('ok'); sys.stdout.flush()
1990 
1991 
1992  print('FACTORIAL...', end=''); sys.stdout.flush()
1993  assert isinstance(FACTORIAL, UrmCutlandProg), type(FACTORIAL)
1994  for inst in FACTORIAL:
1995  assert (inst.inst() != T) or (inst.a() != inst.b()), inst
1996 
1997  for n in range(9 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
1998  m = UrmCutland(init=n)
1999  (i, nb) = m.run(FACTORIAL)
2000  assert i == len(FACTORIAL) + 1, (n, i, len(FACTORIAL), nb)
2001  assert nb <= len(FACTORIAL)*(math.factorial(n) + 1), \
2002  (n, i, len(FACTORIAL), nb, math.factorial(n),
2003  len(FACTORIAL)*(math.factorial(n) + 1))
2004  assert len(m) == 6, (n, len(m))
2005  assert m[1] == math.factorial(n), (n, m[1], math.factorial(n))
2006  assert m[2] == n, (n, m[2])
2007  if n == 0:
2008  assert m[3] == 0, (n, m[3])
2009  else:
2010  assert m[3] == math.factorial(n - 1), (n, m[3], math.factorial(n - 1))
2011  assert m[4] == n, (n, m[4])
2012  assert m[5] == n, (n, m[5])
2013  assert m[6] == n, (n, m[6])
2014  if debug.assertspeed < debug.ASSERT_NORMAL:
2015  print(debug.assertspeed_str(), end='')
2016  print('ok'); sys.stdout.flush()
2017  debug.test_end()
2018 
2019  main_test()
2020 ##\endcond MAINTEST