Browse Prior Art Database

Execution of Functional Programs

IP.com Disclosure Number: IPCOM000052058D
Original Publication Date: 1981-Apr-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 3 page(s) / 61K

Publishing Venue

IBM

Related People

Selinger, RD: AUTHOR

Abstract

The invention relates to a method and means for executing functional programs as defined by Backus [*]. The functional programs are executed on a Von Neuman sequential processor in which data is formatted in tag-type architecture utilizing nested sequence notation. In the Backus functional program, operations consist of either primitive functions or combining forms. The primitive functions are of the binary type and can be directly executed on existing CPU/ALU architectures. Primitive functions and combining forms are capable of being interleaved in the program stream. In this regard, each combining form consists of one or more logical operations.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Execution of Functional Programs

The invention relates to a method and means for executing functional programs as defined by Backus [*]. The functional programs are executed on a Von Neuman sequential processor in which data is formatted in tag-type architecture utilizing nested sequence notation. In the Backus functional program, operations consist of either primitive functions or combining forms. The primitive functions are of the binary type and can be directly executed on existing CPU/ALU architectures. Primitive functions and combining forms are capable of being interleaved in the program stream. In this regard, each combining form consists of one or more logical operations.

More particularly, a combining form controller may be added to a conventional CPU for processing functional programs. The controller includes one register containing the current logical operation being decoded, a decrementable second register defining 'combining form' processing duration through counting down the number of operations, and a microprocessor for executing the operation and regulating the register-to-register data movement.

Functional programs are compiled using a simple pre-ordered tree walk of the computation tree of the program. No operand or data addresses are used except for the call instruction. The data is represented using tag memory and descriptors for sequences. Once the data and program are translated, an interpreter can execute the program.

A logical machine uses a register to hold the input to a function and a separate register to hold the result. This enables all functions to operate transparently, independent of the combining forms. A state register may be utilized for the concurrent combining form. This controls the sequencing of the instructions as reflected by the program counter in the movement of data between input and result registers. A separate count register controls the duration of the combining forms and indicates when a particular combining form has terminated.

A CPU for interpreting functional programs may include a fairly conventional microprogram control unit with only one significant difference. The contents of the State Register are mapped to two...