It is proved that the standard sequent calculus proof system of linear logic is equivalent to a natural deduction style proof system. The natural deduction system is used to investigate the pragmatic problems of type inference and type safety for a linear lambda calculus. Although terms do not have a single most-general type (for either the standard sequent presentation or the natural deduction formulation), there is a set of most-general types that may be computed using unification. The natural deduction system also facilitates the proof that the type of an expression is preserved by any evaluation step. An execution model and implementation is described, using a variant of the three-instruction machine. A novel feature of the implementation is that garbage-collected nonlinear memory is distinguished from linear memory, which does not require garbage collection and for which it is possible to do secure update in place.
展开▼
