High-order Virtual Machine (HVM) - GCのない純粋関数型ランタイム

• Turing MachineとLambda Calculusを組み合わせたInteraction Netという新しい計算モデル
• Rustの複雑な借用モデルの代わりに、Haskellの評価方式に近いlazy clone primitiveを使用
• Lazyであるため複製コストはほぼ無料に近く、Haskellと違ってラムダ内部で計算を共有できる（並列処理での利点が大きい）
• SIC(Symmetric Interaction Calculus)ベースのメモリモデルを採用し、HaskellなどでGraph Reductionと呼ばれていた方式で必要だったポインタ間接参照コストをかなりの部分で削減している（Optimalを見つけられる場合に有利）
• つまり、一般的な言語ランタイムと比べてGCがなく、並列処理とOptimal処理に強みがある

[alstjr7375]

クイックソートの実装です。
ラムダ計算を積極的に使っているからか、Lispと少し似て見えますね…？

// QuickSort  
(QSort p s Nil)          = Empty  
(QSort p s (Cons x Nil)) = (Single x)  
(QSort p s (Cons x xs))  =  
  (Split p s (Cons x xs) Nil Nil)  
  
// Splits list in two partitions  
(Split p s Nil min max) =  
  let s   = (>> s 1)  
  let min = (QSort (- p s) s min)  
  let max = (QSort (+ p s) s max)  
  (Concat min max)  
(Split p s (Cons x xs) min max) =  
  (Place p s (< p x) x xs min max)  
  
// Sorts and sums n random numbers  
(Main n) =  
  let list = (Randoms 1 (* 100000 n))  
  (Sum (QSort Pivot Pivot list))