Paper Info
Title
A CUCH-machine: The automatic treatment of bound variables
Abstract
This paper describes a machine for reducing a ?-formula (explicitly given or implicitly by a system of recursive equations) to principal ß-?-normal form, with particular attention to the memory structures needed for the purpose, and with some important features: (1) any kind of collision is permitted; (2) the processing of subformulas which will be thrown away [e.g., ((?xy)x) in ((?yz)(?xy)x)] is avoided; (3) there is no need to introduce any fixed point operator like ?, etc. The machine structure entails: (1) some store to memorize as side-effects assignment statements with the r.h.s. of a given shape. (2) a number of stacks, one for every ? in the initial formula, partitioned naturally in classes (chains). These stacks admit as entries only words representing variables and they are peculiar in that the operations admitted on the top arewriting anderasing and the operations admitted on the pseudo-top arereading,read-protecting, andresetting readability (the last two operations are chain operations). This structure is critically motivated. (3) A workstack. (4) A pointerstack. The computation runs through four phases: ß-generation, ß-run, ?-generation, ?-run. Every generation- (run-) phase is rather recognition- (transformation-) oriented, but we found it more stimulating to emphasize technical similarities rather than methodological differences. Every phase is described and four examples are extensively developed.
Year
DOI
Venue
1972
10.1007/BF00995737
International Journal of Parallel Programming
Keywords
Field
DocType
normal form,side effect,fixed point
Assignment,Stack (abstract data type),Computer science,Collision,Readability,Theoretical computer science,Operator (computer programming),Fixed point,Recursion,Computation
Journal
Volume
Issue
Citations 
1
2
5
PageRank 
References 
Authors
3.29
3
2
Name
Order
Citations
PageRank
Corrado Böhm1487413.44
Mariangiola Dezani-Ciancaglini21615193.57