Haskell'de saf λ fonksiyonunun normalleştirilmiş kaynağını bulmak mümkün mü?

Question

Saf bir λ fonksiyonunun, soyutlamalar ve uygulamalar dışındaki bir terim olmasına izin verin. JavaScript'te, argüman listesini toplayan değişken fonksiyonlara tüm soyutlamaları uygulayarak saf bir işlevin kaynak kodunu bulmak mümkündür. Yani bu mümkündür:

lambdaSource(function(x){return x(x)}) == "λx.(x x)" 

bu ana fikri üzerine lambdaSource kodunu bakın. Bu fonksiyon benim ilgi alanım için özellikle yararlı oldu çünkü mevcut JS motorlarını, benim tarafımdan kodlayabileceğim herhangi bir naif değerlendiriciden çok daha hızlı bir şekilde not edilmemiş lambda hesaplamaları normalleştirmek için kullanmamı sağlıyor. Üstelik ben λ-matematik fonksiyonları unsafeCoerce yardımıyla Haskell ifade edilebilir biliyorum:

(let (#) = unsafeCoerce in (\ f x -> (f # (f # (f # x))))) 

Çünkü variadic fonksiyonların eksikliği Haskell lambdaSource nasıl uygulanacağı bilmiyorum.

lambdaSource (\ f x -> f # (f # (f # x))) == "λ f x . f (f (f x))" 

: o böyle, Haskell üzerinde saf bir λ fonksiyonunun normalize kaynağını anlaması mümkün mü?

Answer 1

Evet, siz can, ancak işlevin türünün omurganızı sağlamanız gerekir, bu nedenle ULC için çalışmaz. Ayrıca tüm lecture notes'a bakın.

Ancak, Daniel Wagner, HOAS'ı kullanabileceğinizi söyledi. Burada HOA'ları benziyor something olmakla FOAS aslında, ve ihtiyacınız olan tüm değerlendirme (in terms of quote, in terms of reify & reflect) tarafından uygun normalleştirme geçerli:

Orada da başka bir fırsattır. pigworker da Jigger'in Haskell versiyonunu yazdı, ancak bulamıyorum. (Çok karmaşık olan) tek yönlü (bir önerme gerektirir) liftable terms kullanmaktır, ya da biz reify lambda onların PHOAS temsil içine terimler ve sonra PHOAS to FOAS dönüştürebilirsiniz:

Ayrıca tip teoride güvenle tipi yapabilirsiniz. İşte DÜZENLEME

bazı HOA'ları ilgili koddur: Bunun yerine bu Lam s, # s ve malzeme yazma, Ayrıca

{-# LANGUAGE GADTs, FlexibleInstances #-} 

infixl 5 # 

data Term a = Pure a | Lam (Term a -> Term a) | App (Term a) (Term a) 

(#) :: Term a -> Term a -> Term a 
Lam f # x = f x 
f  # x = App f x 

instance Show (Term String) where 
    show = go names where 
     names = map (:[]) ['a'..'z'] ++ map (++ ['\'']) names 

     go :: [String] -> Term String -> String 
     go ns (Pure n) = n 
     go (n:ns) (Lam f) = concat ["\\", n, " -> ", go ns (f (Pure n))] 
     go ns (App f x) = concat [go ns f, "(", go ns x, ")"] 

k :: Term a 
k = Lam $ \x -> Lam $ \y -> x 

s :: Term a 
s = Lam $ \f -> Lam $ \g -> Lam $ \x -> f # x # (g # x) 

omega :: Term a 
omega = (Lam $ \f -> f # f) # (Lam $ \f -> f # f) 

run t = t :: Term String 

main = do 
    print $ run $ s   -- \a -> \b -> \c -> a(c)(b(c)) 
    print $ run $ s # k # k -- \a -> a 
    -- print $ run $ omega -- bad idea 

, sen HOA'ları lambda terimlerin dize temsillerini ayrıştırabileceğiniz - HOAS şartlarını yazdırmaktan daha zor değil.