Functional notation
Author(s): Daniel Cabeza, Amadeo Casas, Manuel Hermenegildo, Jose F. Morales.This library package allows the use of functional notation in a Ciao module/program. It supports function application, predefined evaluable functors, functional definitions, quoting, and (combined with the lazy library) lazy evaluation. The extensions implemented by this library are also composable with higher-order features and can be combined with other Ciao packages such as constraints, assertions, etc.
The package provides syntactic sugar for defining and using predicates as if they were functions. However, they can still retain the power of predicates. Any function definition written using this package is in fact defining a predicate, and any predicate can be used as a function.
The predicate associated with a function has the same name and one more argument, meant as the place holder for the “result” of the function. In fact, this argument is just the one that will be syntactically connected to the surrounding goal or function, but it does not necessarily imply any directionality, i.e., it does not necessarily mean that this argument is an output or an input. This argument is by default added to the right, i.e., it is the last argument, but can be changed by using a declaration, as explained below.
Function applications
Any term preceded by the ~ /1 operator is a function application, as can be seen in the goal write(~arg(1,T)), which is strictly equivalent to the sequence arg(1,T,A), write(A). The declaration fun_return/1 allows using a predicate argument other than the last as the return argument. For example with :- fun_return functor(~,_,_) the expression ~functor(f,2) will be evaluated to the term f(_,_). This definition of the return argument can also be done on the fly in each invocation in the following way: ~functor(~,f,2).
Functors can be declared as evaluable by using the declaration fun_eval/1. This allows avoiding the need to use the ~ operator. Thus, :- fun_eval arg/2 allows writing write(arg(1,T)) instead of write(~arg(1,T)) as above. This declaration can be combined with the previous one: :- fun_eval functor(~,_,_).
Predefined evaluable functors
By using the declaration :- fun_eval arith(true), all the functors understood by is/2 will be also evaluated. This is active from the declaration downwards until a :- fun_eval arith(false) declaration or the end of the module is reached. Beware that arithmetic functors are used in some cases for other purposes than arithmetic: e.g. abolish(p/2). But this is not so disturbing as it may appear because this package is not active in declarations, except for the goal-including declarations initialization/1 and on_abort/1. Note that all the declarations introduced by this package, as is customary in Ciao, are local to the module where they are included.
In addition to functors declared with the declaration fun_eval/1, the package defines as evaluable the functors used for disjunctive and conditional expressions: | /2 and ? /2 (defined as operators). A disjunctive expression has the form (V1|V2), and its value when first evaluated is V1, and on backtracking V2. A conditional expression has the form (Cond ? V1), or more commonly (Cond ? V1 | V2), and its value, if the execution of Cond as a goal succeeds, is V1, otherwise in the first form it causes backtracking, and on the second form its value is V2. Note that due to the operator precedences, these expressions normally need to be surrounded by parenthesis. Also, a nested expression: (Cond1 ? V1 | Cond2 ? V2 | V3) is evaluated as (Cond1 ? V1 | (Cond2 ? V2 | V3)).
Functional definitions
A functional definition is composed of one or more functional clauses. A functional clause is written using the binary operator := /2, as in:
opposite(red) := green.which is equivalent to opposite(red,green). or
addlast(X,L) := ~append(L,[X]).which is equivalent to addlast(X,L,R) :- append(L,[X],R).
Functional clauses can also have a body, which is executed before the result value is computed. It can serve as a guard for the clause or to provide the equivalent of where-clauses in functional languages:
fact(0) := 1. fact(N) := N * ~fact(--N) :- N > 0.Note that guards can often be defined more compactly using conditional expressions:
fact(N) := N = 0 ? 1
| N > 0 ? N * ~fact(--N).
The declaration :- fun_eval defined(true) allows to locally define as evaluable functions being defined, so that the ~ operator does not need to be used within a functional definition for the functor being defined. For example, for the fact invocations in the previous definitions, which can now be written as, e.g. (we provide the full module definition): :- module(_,_,[fsyntax]). :- fun_eval arith(true). :- fun_eval defined(true). fact(0) := 1. fact(N) := N * fact(--N) :- N > 0. %% Or,alternatively: % % fact(N) := N=0 ? 1 % | N>0 ? N * fact(--N).
This behaviour is reverted using :- fun_eval defined(false).
The translation of functional clauses has the following properties:
- The translation produces steadfast predicates, that is, output arguments are unified after possible cuts.
- Defining recursive predicates in functional style maintains the tail recursion of the original predicate, thus allowing the usual compiler optimizations.
Some implementation details and a discussion of the recent combination of this library (which dates from Ciao version 0.2) with the lazy evaluation library can be found in [CCH06].
Quoting functors
Functors (either in functional or predicate clauses) can be prevented from being evaluated by using the ^ /1 prefix operator (read as “quote”), as in
:- fun_eval arith(true). pair(A,B) := ^(A-B).Note that this just prevents the evaluation of the principal functor of the enclosed term, not the possible occurrences of other evaluable functors inside.
Some scoping issues
When using function applications inside the goal arguments of meta-predicates, there is an ambiguity as they could be evaluated either in the scope of the outer execution or the in the scope of the inner execution. The chosen behavior is by default to evaluate function applications in the scope of the outer execution. If they should be evaluated in the inner scope, the goal containing the function application needs to be escaped with the ^^ /1 prefix operator, as in findall(X, (d(Y), ^^(X = ~f(Y)+1)), L) (which could also be written as findall(X, ^^ (d(Y), X = ~f(Y)+1), L)) and which expands into findall(X, (d(Y),f(Y,Z),T is Z+1,X=T), L). With no escaping the function application is evaluated in the scope of the outer execution, i.e., it expands to f(Y,Z), T is Z+1, findall(X, (d(Y),X=T), L).
Other functionality
In addition to the basic package fsyntax, a package functional is also provided, to allow programming with a more functional-flavored style. That package activates the declarations :- fun_eval arith(true) and :- fun_eval defined(true), and defines the . /2 operator for use in lists (but be careful: this period cannot be followed by a whitespace!) and the operator ++ /2 as a function for appending lists. The factorial example above can be written as follows using the functional package:
:- module(_,_,[functional]).
fact(N) := N=0 ? 1
| N>0 ? N * fact(--N).
Which is equivalent to:
:- module(_,_,[fsyntax]). :- fun_eval arith(true). :- fun_eval defined(true). fact(0) := 1. fact(N) := N * fact(--N) :- N > 0. %% Or,alternatively: % % fact(N) := N=0 ? 1 % | N>0 ? N * fact(--N).
See the end of this chapter for additional examples.
Combining with higher order
Ciao provides in its standard library the hiord package, which supports a form of higher-order untyped logic programming with predicate abstractions [CH99a,Cab04,CHL04]. Predicate abstractions are Ciao's translation to logic programming of the lambda expressions of functional programming: they define unnamed predicates which will be ultimately executed by a higher-order call, unifying its arguments appropriately. A function abstraction is provided as functional syntactic sugar for predicate abstractions:
Predicate abstraction: ”(X,Y) :- p(X,Z), q(Z,Y).
Function abstraction: ”(X) := ~q(~p(X)).
and function application is syntactic sugar over predicate application:
Predicate application: ..., P(X,Y), ... Function application: ..., Y = ~P(X), ...
The combination of this hiord package with the fsyntax and lazy packages (and, optionally, the type inference and checking provided by the Ciao preprocessor [HPBLG05]) basically provide the functionality present in modern functional languages (currying is not syntactically implemented, but its results can be obtained by deriving higher-order data from any other higher-order data (see [Cab04]), as well as some of the functionality of full higher-order logic programming.
At this moment, it is necessary to specify the :- fun_eval hiord(true) option to enable correct handling of function abstractions.
Usage and interface
- Library usage:
:- use_package(fsyntax). or :- module(...,...,[fsyntax]). - Imports:
- Packages:
prelude, nonpure, condcomp, assertions.
- Packages:
Other information
Some examples using functional syntax
We now illustrate some of the uses of the package through examples. The following example defines a simple unary function der(X) which returns the derivative of a polynomial arithmetic expression:
der(x) := 1. der(C) := 0 :- number(C). der(A + B) := der(A) + der(B). der(C * A) := C * der(A) :- number(C). der(x ** N) := N * x ** ~(N - 1) :- integer(N), N > 0.
Note that if we include the directive mentioned before which makes arithmetic functors evaluable then we would have to write the program in the following (clearly, less pleasant and more obfuscated) way:
:- fun_eval(arith(true)). der(x) := 1. der(C) := 0 :- number(C). der(^(A + B)) := ^(der(A) + der(B)). der(^(C * A)) := ^(C * der(A)) :- number(C). der(^(x ** N)) := ^(N * ^(x ** (N - 1))) :- integer(N), N > 0.
Both of the previous code fragments translate to the following code:
der(x, 1).
der(C, 0) :-
number(C).
der(A + B, X + Y) :-
der(A, X),
der(B, Y).
der(C * A, C * X) :-
number(C),
der(A, X).
der(x ** N, N * x ** N1) :-
integer(N),
N > 0,
N1 is N - 1.
Functional notation interacts well with other Ciao language features. For example, it provides compact and familiar notation for regular types and other properties:
:- module(_,_,[hiord,functional,assertions,regtypes,'bf/bfall']). :- regtype color/1. color := red | blue | green. :- regtype slist/1. slist := [] | [ _ | slist]. :- regtype list_of/1. list_of(T) := [] | [~T | list_of(T)].
where the functional clauses expand to (note the use of higher-order in the third example):
color(red). color(blue). color(green). list([]). list([_|T]) :- list(T). list_of(_, []). list_of(T, [X|Xs]) :- T(X), list_of(T, Xs).
Such types and properties are then admissible in the usual way in assertions, e.g.:
:- pred append/3 :: list * list * list. :- pred color_value/2 :: list(color) * int.
The combination of functional syntax and user-defined operators brings significant flexibility, as can be seen in the following definition of a list concatenation (append) operator (note that these are the definitions mentioned before which are active by default in the functional package):
:- op(600, xfy, (.)). :- op(650, xfy, (++)). :- fun_eval (++)/2. [] ++ L := L. X.Xs ++ L := X.(Xs ++ L).
This definition will be compiled exactly to the standard definition of append (and, thus, will be reversible). The functional syntax and user-defined operators allow writing for example Space = ' ', write("Hello" ++ Space ++ "world!") instead of the equivalent forms Space = ' ', write( append("Hello", append(Space, "world!"))) (if append/2 is defined as evaluable) or Space = ' ', append(Space, "world!", T1), append("Hello", T1, T2), write(T2).
As another example, we can define an array indexing operator for fixed-size, multi-dimensional arrays. Assume that arrays are built using nested structures whose main functor is a and whose arities are determined by the specified dimensions, i.e., a two-dimensional array A of dimensions [N,M] will be represented by the nested structure a(a(A11,...,A1M), a(A21,..,A2M), ..., a(AN1,..., ANM)), where A11,... ANM may be arbitrary terms (we ignore for simplicity arity limitations, solved in any case typically by further nesting with logarithmic access time). The following recursive definition defines the property fixed_array/2 and also the array access operator @:
fixed_array([N|Ms],A):-
functor(A,a,N),
rows(N,Ms,A).
fixed_array([N],A):-
functor(A,a,N).
rows(0,_,_).
rows(N,Ms,A) :-
N > 0,
arg(N,A,Arg),
array(Ms,Arg),
rows(N-1,Ms,A).
:- pred @(Array,Index,Elem) :: array * list(int) * int
# "@var{Elem} is the @var{Index}-th element of @var{Array}.".
:- op(55, xfx, '@').
:- fun_eval (@)/2.
V@[I] := ~arg(I,V). %% Or: V@[] := V.
V@[I|Js] := ~arg(I,V)@Js.
This allows writing, e.g., M = fixed_array([2,2]), M@[2,1] = 3 (which could also be expressed as fixed_array([2,2])@[2,1] = 3), where the call to the fixed_array property generates an empty 2 x 2 array M and M@[2,1] = 3 puts 3 in M[2,1]. This can be done in the top level:
?- M = ~fixed_array([2,2]), M@[2,1] = 3.provided the op and function declarations are loaded into the top level also. Another example of use is: A3@[N+1,M] = A1@[N-1,M] + A2@[N,M+2].
Such functionality can be grouped into a package as follows. The package main file (arrays.pl) might be:
:- package(arrays). :- include(arrays_ops). :- use_module(arrays_rt).where file arrays_ops.pl may contain:
:- use_package(functional). :- op(150,xfx,[@]). :- fun_eval '@'/2. :- op(500,yfx,<+>). :- fun_eval '<+>'/2. :- op(400,yfx,<*>). :- fun_eval '<*>'/2.The main file is arrays_rt.pl which would contain for example (note that it also uses arrays_ops.pl, and that is why the contents of arrays_ops.pl were not put directly in arrays.pl):
:- module(arrays_rt,_,[functional,hiord,assertions,regtypes,isomodes]).
:- include(arrays_ops).
:- doc(title,"Some simple array operations with syntactic support").
:- doc(author,"Pro Grammer").
:- doc(module,"This library implements a very simple set of
operations on arrays. The idea is to illustrate the use of
functional syntax (operators) by providing syntactic support for
invoking array operations such as element access, array (vector)
addition, etc.").
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Regtypes
%% :- doc(doinclude,array/1).
%% :- doc(doinclude,vector/1).
%% :- doc(doinclude,dim/1).
:- regtype array(A) #"@var{A} is a multi-dimensional array.".
% Should obviously be defined in more detail...
array(A) :- struct(A).
:- regtype dim(D) # "@var{D} represents the dimensions of an array.".
dim(D) :- list(D,int).
:- regtype vector(V) # "@var{V} is a one-dimensional fixed-size array.".
vector(V) :- fixed_array([N],V), int(N).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- pred fixed_array(Dim,Array) :: dim * array
# "@var{Array} is an array of fixed dimensions @var{Dim}.".
fixed_array([N|Ms],A):-
functor(A,a,N),
rows(N,Ms,A).
fixed_array([N],A):-
functor(A,a,N).
rows(0,_Ms,_A).
rows(N,Ms,A):-
N > 0,
arg(N,A,Arg),
fixed_array(Ms,Arg),
rows(N-1,Ms,A).
:- pred @(Array,Index,Elem):: array * dim * int
# "@var{Elem} is the @var{Index}-th element of @var{Array}.".
V@[I] := ~arg(I,V).
V@[I|Js] := ~arg(I,V)@Js.
:- pred <+>(V1,V2,V3) :: vector * vector * vector
# "@var{V3} is @var{V1} + @var{V2}.".
V1 <+> V2 := V3 :-
V1 = ~fixed_array([N]),
V2 = ~fixed_array([N]),
V3 = ~fixed_array([N]),
V3 = ~vecplus_(N,V1,V2).
vecplus_(0,_,_,_).
vecplus_(N,V1,V2,V3) :-
N > 0,
V3@[N] = V1@[N] + V2@[N],
vecplus_(N-1,V1,V2,V3).
:- pred <*>(V1,V2,V3) :: vector * vector * vector
# "@var{V3} is @var{V1} * @var{V2} (inner product).".
V1 <*> V2 := ~vecmul_(N,V1,V2,0) :-
V1 = ~fixed_array([N]),
V2 = ~fixed_array([N]).
vecmul_(0, _, _, Acc, Acc).
vecmul_(N, V1, V2, Acc, IP) :-
N > 0,
vecmul_( N-1, V1, V2, Acc + ( V1@[N] * V2@[N] ), IP).
A file using this package would be: :- module(_,_). :- use_package(library(fsyntax/examples/arrays)). main(M) :- V1 = a(1,3,4,5), V2 = a(5,4,3,1), I = 1, display(V2@[I+1]), M = V1 <*> ( V2 <+> V1 ).
Examples of combining with higher order
The following map and foldl definitions (from the hiordlib library) illustrate the combination of functional syntax and higher-order logic programming:
:- fun_eval map/2. :- meta_predicate map(_,pred(2),_). map([], _) := []. map([X|Xs], P) := [P(X) | map(Xs, P)]. :- fun_eval foldl/3. :- meta_predicate foldl(_,_,pred(3),_). foldl([], Seed, _Op) := Seed. foldl([X|Xs], Seed, Op) := ~Op(X,~foldl(Xs,Seed,Op)).
With this definition:
?- L = ~map([1,2,3], ( _(X,Y):- Y = f(X) ) ). L = [f(1),f(2),f(3)] ? ?- [f(1),f(2),f(3)] = ~map(L, ( _(X,f(X)) :- true ) ). L = [1,2,3] ?
Also, after running:
?- ["helloworld", "byeworld"] = map(["hello", "bye"], ++(X)).
(where (++)/2 corresponds to the above definition of append) X will be bound to "world", which is the only solution to the equation.
And when calling:
map(L, ++(X), ["hello.", "bye."]).
several values for L and X are returned through backtracking:
L = ["hello","bye"], X = "." ? ; L = ["hello.","bye."], X = [] ?
(remember to set the flag write_strings to on in these examples so that the top level prints strings as strings of characters instead of lists of ASCII codes).
Some additional examples using functional syntax
A definition of the Fibonacci function, written in functional notation:
:- module(_,_,[functional]).
fib(0) := 0.
fib(1) := 1.
fib(N) := fib(N-1) + fib(N-2) :- integer(N), N > 1.
write_fib(N):-
message(['The ',N,'. Fibonacci number is: ',~fib(N),'.']).
This is the factorial example, written in functional notation and including some assertions:
:- module(_,_,[assertions,nativeprops,functional]).
:- pred fact(+int,-int) + is_det.
:- pred fact(-int,+int) + non_det.
fact(N) := N=0 ? 1
| N>0 ? N * fact(--N).
And, the same example written using clpq constraints:
:- module(_,_,[assertions,nativeprops,fsyntax,clpqf]). :- fun_eval .=. /1. :- op(700,fx,[.=.]). :- fun_eval fact/1. :- pred fact(+int,-int) + is_det. :- pred fact(-int,-int) + non_det. fact( .=. 0) := .=. 1. fact(N) := .=. N*fact( .=. N-1 ) :- N .>. 0.which allows for example calling it “backwards:”
?- 24 = ~fact(X). X = 4 ?
A very simple example using lazy evaluation:
:- module(_,_,[functional,lazy]). :- use_module(library(lazy/lazy_lib), [take/3]). nums(N) := ~take(N,nums_from(0)). :- lazy fun_eval nums_from/1. nums_from(X) := [X | nums_from(X+1)].
A naive reverse example, using functional notation:
:- module(_, [nrev/2], [functional]). nrev( [] ) := []. nrev( [H|T] ) := ~conc( nrev(T),[H] ). conc( [], L ) := L. conc( [H|T], K ) := [ H | conc(T,K) ].
And the same example using some assertions:
:- module(_, [nrev/2], [assertions,fsyntax,nativeprops]).
:- entry nrev/2 : {list, ground} * var.
:- pred nrev(A,B) : list(A) => list(B)
+ ( not_fails, is_det, steps_o( exp(length(A),2) ) ).
nrev( [] ) := [].
nrev( [H|L] ) := ~conc( ~nrev(L),[H] ).
:- pred conc(A,_,_) + ( terminates, is_det, steps_o(length(A)) ).
conc( [], L ) := L.
conc( [H|L], K ) := [ H | ~conc(L,K) ].
Finally, a simple stream creation example where assertions are used to define a safety policy (that no file outside /tmp should be opened):
:- module(_,[create_streams/2],[fsyntax,assertions,regtypes]).
:- entry create_streams(A,B) : list(A,num).
create_streams([]) := [].
create_streams([N|NL]) := [ ~open_file(Fname,write) | ~create_streams(NL) ]
:-
app("/tmp/../",~number_codes(N),Fname).
% app("/tmp/",~number_codes(N),Fname).
app([],L) := L.
app([X|Xs],L) := [X|~app(Xs,L)].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% open_file library:
open_file(Fname,Mode) := ~open(File,Mode) :- atom_codes(File,Fname).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Safety policy:
:- check calls open_file(Fname,_,_) : safe_name(Fname).
:- regtype safe_name/1. safe_name("/tmp/" || L) :- list(L,alphnum_code).
:- regtype alphnum_code/1. alphnum_code := ~alph_code | ~num_code.
:- regtype alph_code/1. alph_code := 0'a | 0'b | 0'c | 0'd | 0'e | 0'f .
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Known bugs and planned improvements
- Assumes that is/2 is imported.
- Lazy functions declarations require translation priorities to move it to the lazy package.
- Detect automatically when hiord is being used, deprecate eval_hiord.
- I am not sure if shared variables are working for predicate abstractions.
- Find out if predicate abstractions are being fully translated at compile time (see output for hiordfun example).
