PCF extended with real numbers

被引:106
作者
Escardo, MH
机构
[1] Department of Computing, Imperial College, London Sw7 2BZ
关键词
D O I
10.1016/0304-3975(95)00250-2
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We extend the programming language PCF with a type for (total and partial) real numbers. By a partial leaf number we mean an element of a cpo of intervals, whose subspace of maximal elements (single-point intervals) is homeomorphic to the Euclidean real line. We show that partial real numbers can be considered as ''continuous words''. Concatenation of continuous words corresponds to refinement of partial information. The usual basic operations cons, head and tail used to explicitly or recursively define functions on words generalize to partial real numbers. We use this fact to give an operational semantics to the above referred extension of PCF. We prove that the operational semantics is sound and complete with respect to the denotational semantics. A program of real number type evaluates to a head-normal form iff its value is different from perpendicular to; if its value is different from perpendicular to then it successively evaluates to head-normal forms giving better and better partial results converging to its value.
引用
收藏
页码:79 / 115
页数:37
相关论文
共 43 条
[1]  
Abramsky S., 1990, Journal of Logic and Computation, V1, P5, DOI 10.1093/logcom/1.1.5
[2]  
Abramsky S., 1994, Handbook of Logic in Computer Science, V3, P1
[3]  
Abramsky S., 1987, Domain Theory and the Logic of Observable Properties
[4]  
Acioly BM, 1991, THESIS U FEDERAL RIO
[5]  
[Anonymous], 1992, HDB LOGIC COMPUTER S
[6]  
Bishop E., 1985, Constructive analysis, V279
[7]   ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS - NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES [J].
BLUM, L ;
SHUB, M ;
SMALE, S .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1989, 21 (01) :1-46
[8]  
BOEHM HJ, 1986, ACM S LISP FUNCTIONA
[9]  
DIGIANANTONIO P, 1993, THESIS U STUDI PISA
[10]   DYNAMICAL-SYSTEMS, MEASURES, AND FRACTALS VIA DOMAIN THEORY [J].
EDALAT, A .
INFORMATION AND COMPUTATION, 1995, 120 (01) :32-48