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 placeholder 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.

Note that arithmetic functors are used in some cases for purposes other than arithmetic, such as in, e.g., abolish(p/2). However, this is not as much of a problem as as it may appear because this package does not affect 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 in which they are included.

Experimentally, the arith flag can be set to the following values to enable constraint-based arithmetic:
  • :- fun_eval arith(clpfd): finite domains (requires the clpfd package)
  • :- fun_eval arith(clpq): CLP(Q) (requires the clpq package)
  • :- fun_eval arith(clpr): CLP(R) (requires the clpr package)

In addition to functors declared with the fun_eval/1 declaration, this 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 more 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, which basically activates flags that are commonly assumed in functional programming style. In paticular, this package activates the :- fun_eval arith(true) and :- fun_eval defined(true) declarations, 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]. Goal and predicate arguments in meta_predicates allow predicate abstractions, which are Ciao's translation to logic programming of the lambda expressions of functional programming: they define unnamed predicates which can be ultimately executed by a higher-order call, unifying its arguments appropriately.

The fsyntax package together with the :- fun_eval hiord(true) enables enhanced support for higher order predicates. First, it allows specifying higher-order terms using the {...} syntax in arbitrary term positions (fully statically without delayed meta-expansion). Second, it allows predicate abstractions with functional notation:

  • Predicate abstraction: P = {''(X,Y) :- p(X,Z), q(Z,Y)}.

  • Functional abstraction: P = {''(X) := ~q(~p(X))}.

and function application as syntactic sugar over predicate application:

  • Predicate application: ..., P(X,Y), ...

  • Functional 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 CiaoPP [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.


Usage and interface

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,sr/bfall]).

:- regtype color/1. color := red | blue | green.

:- regtype slist/1. slist := [] | [ _ | slist].

:- regtype list_of/2. 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 predicate get_elem/3:

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 get_elem(Array,Index,Elem):: array * list(int) * int
   # "@var{Elem} is the @var{Index}-th element of @var{Array}.".

get_elem(V,[])     := V.
get_elem(V,[I|Js]) := ~get_elem(~arg(I,V),Js).
Rather than using get_elem/3 directly, we will use :- push_prolog_flag(read_postfix_blocks, on) and fun_eval abbrev (see array_ops.pl later) to allow the more compact notation M[I1,...,In] as an abbreviation for ~get_elem(M,[I1,...,In]).

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 fun_eval 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).

% Postfix blocks enable X[I1,...In] syntax
:- push_prolog_flag(read_postfix_blocks, on).
:- op(40, yf, ['[]']). % (inside a list, otherwise the list is empty!)
:- fun_eval abbrev('\6\postfix_block'(X,Idx), ~get_elem(X,Idx)). % (X[I1,...,In])

:- 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,"The Ciao Development Team").

:- 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(int,D).

:- 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 get_elem(Array,Index,Elem):: array * dim * int
# "@var{Elem} is the @var{Index}-th element of @var{Array}.".

get_elem(V,[])     := V.
get_elem(V,[I|Js]) := ~get_elem(~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)).
:- use_module(engine(io_basic)).

main(M) :-
    V1 = a(1,3,4,5),
    V2 = a(5,4,3,1),
    I = 1,
    display(V2[I+1]), nl,
    M = V1 <*> ( V2 <+> V1 ).

foo(M) :-
    M = a(a(_,_),a(_,_)),
    M[1,2] = a,
    M[2,1] = a.

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]).

:- use_module(engine(messages_basic), [message/2]).

fib(0) := 0.
fib(1) := 1.
fib(N) := fib(N-1) + fib(N-2) :- integer(N), N > 1.

write_fib(N):-
    message(user, ['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).

The same example written using clpq constraints:

:- module(_,_,[assertions,nativeprops,fsyntax,clpq]).

:- 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 ?

The same example written using arithmetic functors evaluable with clpq (experimental fun_eval arith(clpq)):

:- module(_,_,[assertions,nativeprops,fsyntax,clpq]). % or clpr, clpfd

:- fun_eval arith(clpq). % or clpr, clpfd

:- 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. 

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]).

:- use_module(engine(stream_basic)).

:- entry create_streams(A,B) : list(num,A).

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(alphnum_code,L).
  
:- 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 .

:- regtype num_code/1.
num_code(0'0). num_code(0'1). num_code(0'2). num_code(0'3). num_code(0'4).
num_code(0'5). num_code(0'6). num_code(0'7). num_code(0'8). num_code(0'9).
num_code(0'.). num_code(0'e). num_code(0'E). num_code(0'+). num_code(0'-).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%