Improving the three instruction machine
Guy Argo · 1989
Recently Fairbairn and Wray presented a simple abstract machine for lazy functional languages called the Three Instruction Machine [FW87].The TIM is remarkable as it achieves respectable efficiency without the many optimisations required by the G-machine [Aug87, Joh87].In the first part of this paper, the original TIM is described.In the second part, optimisations to the TIM are developed which require no sophisticated compile-time information.These optimisations improve performance in several areas: heap consumption of standardfunctions, the representation of partial applications, the compilation ofjidl applications, and the sharing mechanism requiredfor laziness.In the third part, the G-TIM is developed, an improved TIM which is more amenable to optimisations based on sophisticated compile-time analysis.We demonstrate how the G-TIM can take advantage of sharing analysis, strictness analysis, path ana1y.C~ and lifetime analysis.The G-TIM improves on the ortgtnal TIM in several ways: an improved sharing mechanism, cheaper evaluation of basic values, economical representation of partial applications and stack allocation of argument frames.