Functional notation

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

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.

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

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