Pointers in Recursion: Exploring the Tropics We translate the usual class of partialprimitive recursive functions to a pointer recursion framework, accessing actual input values via a pointer reading unitcost function. These pointer recursive functions classes are proven equivalent to the usual partialprimitive recursive functions. Complexitywise, this framework captures in a streamlined way most of the relevant subpolynomial classes. Pointer recursion with the safenormal tiering discipline of Bellantoni and Cook corresponds to polylogtime computation. We introduce a new, nonsize increasing tiering discipline, called tropical tiering. Tropical tiering and pointer recursion, used with some of the most common recursion schemes, capture the classes logspace, logspacepolylogtime, ptime, and NC. Finally, in a fashion reminiscent of the safe recursive functions, tropical tiering is expressed directly in the syntax of the function algebras, yielding the tropical recursive function algebras.

A Domain Theory for Statistical Probabilistic Programming We give an adequate denotational semantics for languages with recursive higherorder types, continuous probability distributions, and soft constraints. These are expressive languages for building Bayesian models of the kinds used in computational statistics and machine learning. Among them are untyped languages, similar to Church and WebPPL, because our semantics allows recursive mixedvariance datatypes. Our semantics justifies important program equivalences including commutativity.  :61,new semantic model is based on quasiBorel predomainsu0027. These are a mixture of chaincomplete partial orders (cpos) and quasiBorel spaces. QuasiBorel spaces are a recent model of probability theory that focuses on sets of admissible random elements. Probability is traditionally treated in cpo models using probabilistic powerdomains, but these are not known to be commutative on any class of cpos with higher order functions. By contrast, quasiBorel predomains do support both a commutative probabilistic powerdomain and higherorder functions. As we show, quasiBorel predomains form both a model of Fioreu0027s axiomatic domain theory and a model of Kocku0027s synthetic measure theory.