2012-04-15 48 views
1

我正在嘗試實現自動程序合成的簡單功能語言。 數據結構是一個函數和值的圖形,可以編譯爲javascript。 以下圖形應該是摺疊功能。 funcApp節點連接到一個功能節點和一些有價值的節點,並將該功能應用於這些值。 arg0是列表,arg1是初始值(z)arg2是要應用的函數。以簡單的純功能語言實現摺疊而無需懶惰評估

enter image description here

這相當於folloiwng方案定義(雖然我的「語言」是不是計劃,它是圖)

(define (foldr f z xs) 
    (if (null? xs) 
     z 
     (f (car xs) (foldr f z (cdr xs))))) 

的問題是有,因爲沒有特殊運營商,一切,特別是if只是一個正常的功能。在這種形式下,程序永遠不會終止,而是達到最大堆棧深度,因爲總是計算else子句。

我認爲這個問題是通過懶惰的評估在某些語言中解決的。所以我的問題是:有沒有這種無限遞歸的fold的功能版本2)如果需要,從哪裏開始考慮將懶惰評估應用於這種簡單的語言。

+1

'if'是Scheme中的一種特殊形式,所以else表達式總是被評估* not *。這裏有什麼問題? – 2012-04-15 22:13:59

+0

我知道Scheme就是這種情況,我想我在最後一段 – zenna 2012-04-15 22:20:37

+1

中明確表達了我的問題,我不明白第一個問題。對2)的答案將是「特別處理」。 – 2012-04-15 22:24:36

回答

1

您可以將if-expression的兩個分支都編譯爲thunk,並根據條件調用相應的thunk。如果方案的正式定義是這樣寫的,我不會感到驚訝。

2

我認爲在粘合劑下評估(特別是評估lambda體)是非常罕見的,所以我認爲標準化解決嚴格語言的方法是引入lambda。我不知道方案的語法,但是在Haskell語法中,如果你想x是一個嚴格函數f的懶惰參數,你可以寫一些類似f (\() -> x)(並修改f適當地期望這樣的lambda表達式,並在那一刻你想要懶惰他們)。

+0

Scheme語法與Haskell語法非常相似,'(λ()x)'是一個thunk,並且在parens中圍繞一個thunk「調用」它,例如, '(someThunk)' – 2012-04-16 19:59:53