Sharing and Linear Logic with Restricted Access
摘要
The two Girard translations provide two different means of obtaining embeddings of Intuitionistic Logic into Linear Logic, corresponding to different lambda-calculus calling mechanisms. The translations, mapping \(A\rightarrow B\) respectively to \({!}{A}\multimap B\) and \({!}{(A\multimap B)}\) , have been shown to correspond respectively to call-by-name and call-by-value. In this work, we split the of-course modality of linear logic into two modalities, written “ \({!} \) ” and “ \(\bullet \) ”. Intuitively, the modality “ \({!} \) ” specifies a subproof that can be duplicated and erased, but may not necessarily be “accessed”, i.e. interacted with, while the combined modality “ \({!}{\bullet }\) ” specifies a subproof that can moreover be accessed. The resulting system, called \(\textsf{MSCLL}\) , enjoys cut-elimination and is conservative over \(\textsf{MELL}\) . We study how restricting access to subproofs provides ways to control sharing in evaluation strategies. For this, we introduce a term-assignment for an intuitionistic fragment of \(\textsf{MSCLL}\) , called the \(\lambda ^{{!}{\bullet }}\) -calculus, which we show to enjoy subject reduction, confluence, and strong normalization of the simply typed fragment. We propose three sound and complete translations that respectively simulate call-by-name, call-by-value, and a variant of call-by-name that shares the evaluation of its arguments (similarly as in call-by-need). The translations are extended to simulate the Bang-calculus, as well as weak reduction strategies.