% module: combinators.pl % date: March 10, 2005 % author: Douglas M. Auclair (DMA) % copyright (c) 2005, Cotillion Group, Inc. All rights reserved. % synopsis: Defines the functional equivalents of a subset of the % mathematical combinators and the rules of composition (or % application). :- module(combinators, [compose/3, phi_equivalent/2]). % modified: November 16, 2005, DMA % changed: Narrowed the exports (ski_string/3 was never used). % modified: May 11, 2005, DMA % changed: Changed name of X (single-basis) combinator to 'N', % imparting a nmonic of 'Nightingale' % modified: May 6, 2005, DMA % changed: Added X (single-basis) and J combinators. % modified: March 17, 2005, DMA % changed: Added transformations from other term types to phi-types. % foldl("kk", s, k, I_equiv0). % ``kx```skkx == ```sk``skkx % foldl("kk", s, s, I_equiv1). % ``kx```sksx == ```sk``sksx % ... but because we currently do not do any pruning, % \+ I_equiv0 = I_equiv1 holds, even though % for every X, I_equiv0(X) == I_equiv1(X) % so from the SK axioms I_equiv0 = I_equiv1 % but there it is. /* * so, thoughts on graph reduction. Turner's rules from * _An Introduction to Functional Programming Systems Using Haskell_ * by AJT Davie are as follows (with my slight additions): * * ``s`kx`ky => `k`xy * ``s`kxi => x * ``s`kxy => ``bxy where ```bxyz == `x`yz * ``sx`ky => ``cxy where ```cxyz == ``xzy * * but, simpler: * * `ix => x * ``kx_ => x * ```ki_x => x * ``sk_ => i * ```sk_x => x * * but, then again, these simplifications should only occur if * profiling warrants this rewrite. Let's leave it for now. */ /* * Some other, potentially useful, combinators. * * ```bxyz => `x`yz * ```cxyz => ``xzy * `mx => `xx (``sii == m; `mm does not halt) * `yx => `x`yx (so you've got normal-order recursion; * this is called theta in the Mockingbird * book) * ```vxyz => ``zxy (The list combinator: given k is fst and `ki * is snd, ``vxy is (cons x y) so ```vxyk => x * and ```vxy`ki => y) * ````dxyzw => ``xy`zw (so?) * ````jxyzw => ``xy``xwz (all combinators can be represented by j) ??? * ``lxy => `x`yy (``sll == y) ??? * ```rxyz => ``yzx * ``txy => `yx * * The above give us enough to express logic in combinators * (*choke* logic expressing combinators expressing logic!) * * k == true * `ki == false * ``v`kik == not * `rk == implies a => b == ~(a /\ ~b) * `r`ki == and * `tk == or (so ```tkkk == ```tkk`ki == ```tk`kik == k, right?) * ``cs``v`kik == equiv (bool -> bool -> bool) * * with the peano numbers: * * i == 0 * ``v`kip == sp * ``t`ki(sp) == p * `tk == 0? * * * so addition is: `y(\. ````tk``v`ki````t`ki) * => `y(\a.\b.\c. ````tkcb``v`ki``ab``t`kic) * => `y(\a.\b. ``s``s``s`k`tki`kb``s`k`v`ki``s`k`ab``s`k`t`kii) * etc (=> `y\a. ... ) * but then we have the normal-order stuff to deal with. * * Eureka! We can mixin supercombinators (prolog functors) with the * <> notation: "<+>" == phi(X, phi(Y, Ans, Ans = X + Y), true) * or simply add the symbols: "`+2" == where + is <+> above (with * map_reversed `+2 adds two to each cardinal element) and a max or * min is foldl with ">" and "<" */ :- use_module(library(lambda), [apply/3, test/2]). :- op(200, xfy, <-). % ensure file library(logic_syntax) is loaded into module(user) % before loading this module. compose(X, Y, Z) :- % Applies the X combinator to Y, giving Z phi_equivalent(X, phi(In, Ans, Phi)), findall(Ans, (In = Y, Phi), [Z]). % phi_equivalent/2 defines the combinators we care to use % first tier, bases: s, k, i, j, and n phi_equivalent(i, phi(In, In, true)). phi_equivalent(k, phi(In, phi(_, In, true), true)). phi_equivalent(s, phi(X, phi(Y, phi(Z, Ans, Phi), true), true)) :- Phi = (compose(X, Z, Phi0), compose(Y, Z, Phi1), compose(Phi0, Phi1, Ans)). phi_equivalent(j, phi(A, phi(B, phi(C, phi(D, Ans, Phi), true), true), true)) :- % There exists a Turing-complete JI-basis. Phi = (compose(A, B, Phi0), compose(A, D, Phi1), compose(Phi1, C, Phi2), compose(Phi0, Phi2, Ans)). phi_equivalent(n, phi(A, Ans, Phi)) :- % There exists a Turing-complete N-basis where N (a la Rosser) is % \x.xKSK. K == NNN, S = N(NN). If we choose N is \f.fS(\xyz.x) % (a la Fokker. side note: for N1 = \f.fS(\xyz.x) and N2 = % \f.fS(BKK) -> N1 == N2?), then K = NN and S = N(NN). There is a % slight trade-off in sizes and reduction steps between the two % defined single-combinator bases. We'll go with Rosser first. phi_equivalent(s, S), phi_equivalent(k, K), Phi = (compose(A, K, Phi0), compose(Phi0, S, Phi1), compose(Phi1, K, Ans)). % second tier: c and b phi_equivalent(c, phi(X, phi(Y, phi(Z, Ans, Phi), true), true)) :- Phi = (compose(X, Z, Phi0), compose(Phi0, Y, Ans)). phi_equivalent(b, phi(X, phi(Y, phi(Z, Ans, Phi), true), true)) :- Phi = (compose(Y, Z, Phi1), compose(X, Phi1, Ans)). % third tier, permuting combinators: r, t, and v phi_equivalent(r, phi(X, phi(Y, phi(Z, Ans, Phi), true), true)) :- Phi = (compose(Y, Z, Phi0), compose(Phi0, X, Ans)). phi_equivalent(t, phi(X, phi(Y, Ans, compose(Y, X, Ans)), true)). phi_equivalent(v, phi(X, phi(Y, phi(Z, Ans, Phi), true), true)) :- Phi = (compose(Z, X, Phi0), compose(Phi0, Y, Ans)). % forth tier, duplicating: w, l and m phi_equivalent(w, phi(A, phi(B, Ans, Phi), true)) :- Phi = (compose(A, B, Phi0), compose(Phi0, B, Ans)). phi_equivalent(m, phi(A, Ans, (compose(A, A, Ans)))). phi_equivalent(l, phi(A, phi(B, Ans, Phi), true)) :- Phi = (compose(B, B, Phi0), compose(A, Phi0, Ans)). % fifth tier, protosage: o, u phi_equivalent(o, phi(A, phi(B, Ans, Phi), true)) :- Phi = (compose(A, B, Phi0), compose(B, Phi0, Ans)). phi_equivalent(u, phi(A, phi(B, Ans, Phi), true)) :- Phi = (compose(A, A, Phi0), compose(Phi0, B, Phi1), compose(B, Phi1, Ans)). % Doug's special combinator: a combinator is applied to the results of % applying two arguments to each of two binary operators. This is % similar to E (= \abcdefg.a(bcd)(efg)), but in this case c == f % and d == g. phi_equivalent(p, phi(A, phi(B, phi(C, phi(D, phi(E, Ans, Phi), true), true), true), true)) :- Phi = (compose(B, D, Phia), compose(Phia, E, Phi1), compose(C, D, Phib), compose(Phib, E, Phi2), compose(A, Phi1, Compose), compose(Compose, Phi2, Ans)). % The ASCII-character representations of the above: phi_equivalent( 98, B) :- phi_equivalent(b, B). phi_equivalent( 99, C) :- phi_equivalent(c, C). phi_equivalent(105, I) :- phi_equivalent(i, I). phi_equivalent(106, J) :- phi_equivalent(j, J). phi_equivalent(107, K) :- phi_equivalent(k, K). phi_equivalent(108, L) :- phi_equivalent(l, L). phi_equivalent(109, M) :- phi_equivalent(m, M). phi_equivalent(111, O) :- phi_equivalent(o, O). phi_equivalent(112, P) :- phi_equivalent(p, P). phi_equivalent(114, R) :- phi_equivalent(r, R). phi_equivalent(115, S) :- phi_equivalent(s, S). phi_equivalent(116, T) :- phi_equivalent(t, T). phi_equivalent(117, U) :- phi_equivalent(u, U). phi_equivalent(118, V) :- phi_equivalent(v, V). phi_equivalent(119, W) :- phi_equivalent(w, W). phi_equivalent(120, X) :- phi_equivalent(x, X). % some trinary boolean operations ... instead of returning K or KI we % return the value that satisfies the condition. E.g.: 5 < 7 returns % 5 (it's the smaller value). We'll see the utility of these boolean % functionals, ... or not. % phi_equivalent(60, phi(X, phi(Y, Z, (X < Y -> Z = X; Z = Y)), true)). % phi_equivalent(62, phi(X, phi(Y, Z, (X > Y -> Z = X; Z = Y)), true)). % Oops! Changed my mind: these comparison operators DO return K for % true and KI for false ... fortunately the special form '?' converts % K to the result and KI to fail/0. phi_equivalent(60, phi(X, phi(Y, Z, Phi), true)) :- Phi = (X < Y -> phi_equivalent(k, Z); Z = phi(_, phi(A, A, true), true)). phi_equivalent(61, phi(X, phi(Y, Z, Phi), true)) :- Phi = (X = Y -> phi_equivalent(k, Z); Z = phi(_, phi(A, A, true), true)). phi_equivalent(62, phi(X, phi(Y, Z, Phi), true)) :- Phi = (X > Y -> phi_equivalent(k, Z); Z = phi(_, phi(A, A, true), true)). phi_equivalent(63, phi(Fn, phi(Arg, Ans, Phi), true)) :- % The '?' special form works with combinator boolean logic: a true % statement returns the result wrapped in a K combinator, and the % false one returns the result in KI. So, when we apply the result % of a boolean expression to _|_ (pronounced 'bottom'), we get back % either the result (for a true expression) or _|_ for false, in % which case it fails the final goal in the phi-term. Phi = (compose(Fn, Arg, Phi0), compose(Phi0, '_|_', Ans), \+ Ans = '_|_'). % and some arithmetic functionals ... you see that I'm using numbers % as numbers ... I'm not following convention by using Church numerals % or the Peano series ... too much work converting between integrals % used by the rest of Prolog and numbers represented by combinators! phi_equivalent(43, phi(X, phi(Y, Z, (Z is X + Y)), true)). phi_equivalent(42, phi(X, phi(Y, Z, (Z is X * Y)), true)). phi_equivalent(45, phi(X, phi(Y, Z, (Z is X - Y)), true)). phi_equivalent(47, phi(X, phi(Y, Z, (Z is X / Y)), true)). % and then a list-element prepend operator phi_equivalent(58, phi(Elt, phi(List, [Elt|List], true), true)). % transformations of terms into phi-terms: phi_equivalent(phi(A, B, C), phi(A, B, C)). % Of course, the phi-equivalent term of a phi-term is that phi-term. phi_equivalent(lambda(X, Function), phi(Y, Z, Apply)) :- % lambda is a phi with a special rule for activation Apply = lambda:apply(lambda(X, Function), Y, Z). phi_equivalent(psi(In, Test), phi(In, In, Test)). % psi is a phi that does not alter the input argument phi_equivalent(predicate(In, Test), phi(X, X, Tester)) :- % predicate/2 and psi/2 are the same thing, pretty much ... Tester = lambda:test(predicate(In, Test), X). phi_equivalent(complement(In, Test), phi(X, X, Tester)) :- % ditto for complement/2 Tester = lambda:test(complement(In, Test), X). phi_equivalent("", phi(X, X, true)). phi_equivalent([S|KI], PhiTerm) :- phi_term(Phi, [S|KI], Rest), query_opt(Query, Rest, ""), % ```tkb```v`kikb? (sorry, couldn't resist!) compose(Query, Phi, PhiTerm). % ... and now we define the grammar, a la unlambda: ski_string(PhiTerm) --> compose, phi_term(A), phi_term(B), { compose(A, B, PhiTerm) }. query_opt(Query) --> sp_opt, "?", sp_opt, !, { phi_equivalent(63, Query) }. query_opt(phi(X, X, true)) --> sp_opt. phi_term(Phi) --> ski_string(Phi) | combinator(Phi) | numeral(Phi). combinator(Phi) --> sp_opt, [Char], { phi_equivalent(Char, Phi) }. numeral(Num) --> sp_opt, digits(0, Num). digits(Accum, Ans) --> [Char], { is_digit(Char, Digit), NewAccum is Accum * 10 + Digit }, (digits(NewAccum, Ans) ; { Ans = Accum }). digits(Ans, Ans) --> []. is_digit(Char, Char - 48) :- Char <- "0123456789". compose --> sp_opt, "`". sp_opt --> sp | sp, sp_opt | epsilon. sp --> [32]. epsilon --> [].