Path: utzoo!utgpu!attcan!uunet!mcvax!enea!kth!draken!ttds!jonasn
From: jonasn@ttds.UUCP (Jonas Nygren)
Newsgroups: comp.lang.prolog
Subject: Funcy - an implementation of FP in Prolog. (long)
Message-ID: <1165@ttds.UUCP>
Date: 8 Aug 88 16:31:34 GMT
Reply-To: jonasn@ttds.UUCP (Jonas Nygren)
Organization: The Royal Inst. of Techn., Stockholm
Lines: 131


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