A valid rule of β-conversion for the logic of partial functions

Title:

A valid rule of β-conversion for the logic of partial functions
Platné pravidlo β-konverze pro logiku dílčích funkcí

Creator:

Duží, Marie and Kosterec, Miloš

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:2dd01452-b493-4486-8bb1-b74dc3709a58
uuid:2dd01452-b493-4486-8bb1-b74dc3709a58

Subject:

β-reduction by name, β-reduction by value, λ-Closure, λτ-Closure, substitution, and validity

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

The goal of this paper is to examine the conditions of validity for the rule of β-conversion in TIL, which is a hyperintensional, typed λ-calculus of partial functions. The rule of β-reduction is a fundamental computational rule of the λ-calculi and functional programming languages. However, it is a well-known fact that the specification of this rule is ambiguous (see, e.g., Plotkin 1975 or Chang & Felleisen 2012). There are two procedurally non-equivalent ways of executing the rule, namely β-conversion ''by name'' and β-conversion ''by value''. In the λ-calculi conversion by name is usually applied, though it is known that such a conversion is not unconditionally valid when partial functions are involved. If a procedure that is typed to produce an argument value is improper by failing to produce one, conversion by name cannot be validly applied. On the other hand, conversion by value is valid even in the case of improperness. Moreover, we show that in a typed λ-calculus the specification of λ-closure is also not unambiguous. There is an interpretation of this specification under which β-reduction by name is not valid even when the argument procedure does not fail to produce a value. As a result, we present a universally valid rule of β-reduction by value. and Cílem této práce je zkoumat podmínky platnosti pravidla β-konverze v TIL, což je hyperintenzivní, psaný λ-kalkul dílčích funkcí. Pravidlo β-redukce je základním výpočtovým pravidlem λ-kalkulů a funkčních programovacích jazyků. Je však dobře známo, že specifikace tohoto pravidla je nejednoznačná (viz např. Plotkin 1975 nebo Chang & Felleisen 2012). Existují dva procedurálně neekvivalentní způsoby provedení pravidla, a to β-konverze '' podle názvu '' a ''β-konverze'' podle hodnoty'. V kontextu λ-kalkulů se obvykle používá konverze podle názvu, ačkoli je známo, že taková konverze není bezpodmínečně platná, pokud jde o dílčí funkce. Je-li zadaný postup, který má hodnotu parametru argumentu, nesprávný tím, že jej neproběhne, nemůže být konverzace podle názvu platně použita. Na druhé straně konverze hodnotou platí i v případě nevhodnosti. Navíc ukážeme, že v zadaném λ-kalku není specifikace uzavření λ jednoznačná. Existuje interpretace této specifikace, při níž není jméno p-redukce platné, ani když proces argumentu nedokáže vytvořit hodnotu. Výsledkem je obecně platné pravidlo β-redukce hodnotou .

Language:

Slovak

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Source:

Organon F: filozofický časopis | 2017 Volume:24 | Number:1

Harvested from:

CDK

Metadata only:

false