Algebraic Logic Functional programming language
Encyclopedia
Algebraic Logic Functional programming language also known as ALF is a programming language
which combines functional and logic programming
techniques. Its foundation is Horn clause
logic with equality which consists of predicates and Horn clauses for logic programming, and functions and equations for functional programming.
ALF was designed to be genuine integration of both programming paradigms, and thus any functional expression can be used in a goal literal and arbitrary predicates can occur in conditions of equations. ALF's operational semantics
is based on the resolution rule to solve literals and narrowing to evaluate functional expressions. In order to reduce the number of possible narrowing steps, a leftmost-innermost basic narrowing strategy is used which, it is claimed, can be efficiently implemented. Terms are simplified by rewriting before a narrowing step is applied and equations are rejected if the two sides have different constructors at the top. Rewriting and rejection are supposed to result in a large reduction of the search tree and produce an operational semantics that is more efficient than Prolog's resolution strategy. Similarly to Prolog, ALF uses a backtracking strategy corresponding to a depth-first search in the derivation tree.
The ALF system was designed to be an efficient implementation of the combination of resolution, narrowing, rewriting, and rejection. ALF programs are compiled into instructions of an abstract machine. The abstract machine is based on the Warren Abstract Machine
(WAM) with several extensions to implement narrowing and rewriting. In the current ALF implementation programs of this abstract machine are executed by an emulator written in C
.
In the Carnegie Mellon University
Artificial Intelligence
Repository, ALF is included as an AI programming language, in particular as a functional/logic programming language Prolog implementation. A user manual describing the language and the use of the system is available. The ALF System runs under Unix
and is free.
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
which combines functional and logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
techniques. Its foundation is Horn clause
Horn clause
In mathematical logic, a Horn clause is a clause with at most one positive literal. They are named after the logician Alfred Horn, who first pointed out the significance of such clauses in 1951...
logic with equality which consists of predicates and Horn clauses for logic programming, and functions and equations for functional programming.
ALF was designed to be genuine integration of both programming paradigms, and thus any functional expression can be used in a goal literal and arbitrary predicates can occur in conditions of equations. ALF's operational semantics
Operational semantics
In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
is based on the resolution rule to solve literals and narrowing to evaluate functional expressions. In order to reduce the number of possible narrowing steps, a leftmost-innermost basic narrowing strategy is used which, it is claimed, can be efficiently implemented. Terms are simplified by rewriting before a narrowing step is applied and equations are rejected if the two sides have different constructors at the top. Rewriting and rejection are supposed to result in a large reduction of the search tree and produce an operational semantics that is more efficient than Prolog's resolution strategy. Similarly to Prolog, ALF uses a backtracking strategy corresponding to a depth-first search in the derivation tree.
The ALF system was designed to be an efficient implementation of the combination of resolution, narrowing, rewriting, and rejection. ALF programs are compiled into instructions of an abstract machine. The abstract machine is based on the Warren Abstract Machine
Warren abstract machine
In 1983, David H. D. Warren designed an abstract machine for the execution of Prolog consisting of a memory architecture and an instruction set. This design became known as the Warren Abstract Machine and has become the de facto standard target for Prolog compilers.-Purpose:The purpose of...
(WAM) with several extensions to implement narrowing and rewriting. In the current ALF implementation programs of this abstract machine are executed by an emulator written in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
.
In the Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
Artificial Intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
Repository, ALF is included as an AI programming language, in particular as a functional/logic programming language Prolog implementation. A user manual describing the language and the use of the system is available. The ALF System runs under Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
and is free.
External links
- Publications of Michael Hanus, including many articles relevant to the design and theory of ALF
- Information about getting and installing the ALF system