jonasn@ttds.UUCP (Jonas Nygren) (08/08/88)
I have made an implementation in Prolog of Backus functional programming
language, FP: CACM, vol 21, 8, pages 613-641. My interpretation has also been
flavored by Illinois Functional Programming (IFP), as presented in a
Byte(2/87) article.
The syntax of my implementation is as follows:
funcy(Input, CompoundTransformation, Output)
CompoundTransformation: T1 @ T2 @ T3
If a transformation is prefixed with a '^' the following atom/instance
is treated as a normal Prolog goal, the arguments are transformed if not
escaped. Data is passed through without transformation. See examples below.
The main change from Backus original definition is the order of evaluation
which has been changed to be left-to-right. Other changes are:
[a -> b ; c] changed to if(a,b,c) % if a then b else c
... @ each([id,3] @ *)
may here also be written ... @ each(id*3)
the same also applies for the other PFO's:
if, while, [..], insert, filter
Note: '@' is the 'pipe' symbol of FP
It must be stated that this implementation is grossly inefficient with
regard to performance but it allow you to experiment with FP. If you are
intrested in testing funcy/3 send me a mail and I will try to
mail it to you.
Question: Can anybody answer me whether it would be possible to do an
efficient implementation of funcy/3, @ a s o as Prolog built-ins
or is FP doomed to remain a toy?
J Nygren
---------------
Here follows some examples of my implementation of FP:
A short guide:
iota: 3 @ iota -> [1,2,3]
id: id -> id % the input
#N: #2 -> the second item of input
distl: [a,[1,2,3]] @ distl -> [[a,1],[a,2],[a,3]]
distr: [[1,2,3],a] @ distr -> [[1,a],[2,a],[3,a]]
trans: [[a,b,c],[1,2,3]] @ trans -> [[a,1],[b,2],[c,3]]
filter: [[1,2],[2,2],[3,2]] @ filter(=) -> [[2,2]]
each: [[1,2],[2,2],[3,2]] @ each(+) -> [3,4,5]
insert: [1,2,3,4] @ insert(+) -> 10 % 1+2+3+4
[..]: [8,4] @ [+,-,*,//] -> [12,4,32,2]
?- funcy(3,iota,X).
X = [1,2,3]
?- funcy(3,iota @ reverse,X).
X = [3,2,1]
?- funcy(5,(iota @ reverse @ each(id*3)),X).
X = [15,12,9,6,3]
?- funcy(3,[iota,iota],X).
X = [[1,2,3],[1,2,3]]
?- funcy(3,[iota,iota] @ inner_product,X).
X = 14
?- listing(inner_product).
/* inner_product/1 */
inner_product(trans @ each((*)) @ insert((+))).
yes
?- funcy(3,([iota,iota] @ outer2vec(=) @ dispmatrix(5)),_).
1 0 0
0 1 0
0 0 1
yes
?- funcy(3,([iota,iota] @ outer2vec(*) @ dispmatrix(5)),Out).
1 2 3
2 4 6
3 6 9
Out = [[[5,1],[10,2],[15,3]],[[5,2],[10,4],[15,6]],
[[5,3],[10,6],[15,9]]]
?- listing([outer2vec,dispmatrix,dispvec]).
/* outer2vec/3 */
outer2vec(In,Op,Out) :-
funcy(In,distr @ each(distl @ each(Op)),Out).
/* dispmatrix/3 */
dispmatrix(In,N,Out) :-
funcy(In,each(dispvec(N)) @ ^ nl @ ^ nl,Out).
/* dispvec/3 */
dispvec(In,TabLen,Out) :-
funcy(In,
[len @ iota @ each(id * TabLen),id] @
trans @
^ nl @
each(^ tabto(# 1) @ ^ write(# 2)),Out).
yes
% tabto is a built-in in AAIS Prolog.
?- funcy([2,3,1,6,3,8,3,2,5,8,4,5,6],(qsort @ dispvec(3)),_).
1 2 2 3 3 3 4 5 5 6 6 8 8
yes
?- listing(qsort).
/* qsort/1 */
qsort(if(len < 2,id,
[id,# 1] @
distr @
[filter((<)) @ each(# 1) @ qsort,
filter((=)) @ each(# 1),
filter((>)) @ each(# 1) @ qsort] @ cat)).
yes
?- ok@quintus.uucp (Richard A. O'Keefe) (08/10/88)
In article <1165@ttds.UUCP> jonasn@ttds.UUCP (Jonas Nygren) writes: >Question: Can anybody answer me whether it would be possible to do an > efficient implementation of funcy/3, @ a s o as Prolog built-ins > or is FP doomed to remain a toy? I don't know what '@ a s o ...' means. It shouldn't be any harder to base FP on Prolog than on Lisp, so you should be able to do about as well as the FP system described in the BSD UNIX manuals. It should be straightforward to just compile FP forms into Prolog, using the technique of partially executing an interpreter. However, that has two problems: FP only has one data structuring form, namely lists, so you'd be wasting space compared with "native" Prolog representations of data using compound terms, and the naive method tends to produce a lot of intermediate data structures. There's a fair literature on transforming FP programs to more efficient forms, all of which should be applicable. For example, if you form a list of pairs and then feed that into something which applies a binary function to each pair, you want to move the binary function into the code that generates the pairs, so that you can avoid storing them. If there is a fast implementation of FP anywhere, I'd like to hear of it.