以簡單的純功能語言實現摺疊而無需懶惰評估

我正在嘗試實現自動程序合成的簡單功能語言。數據結構是一個函數和值的圖形，可以編譯爲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）如果需要，從哪裏開始考慮將懶惰評估應用於這種簡單的語言。

來源

2012-04-15 zenna

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

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

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

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

來源

2012-04-15 22:46:51 none

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

來源

2012-04-15 22:49:40

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

以簡單的純功能語言實現摺疊而無需懶惰評估

回答

相關問題