View source with raw comments or as raw
    1/*  Part of SWI-Prolog
    2
    3    Author:        Paulo Moura
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2015, Paulo Moura, Kyndi Inc., VU University Amsterdam
    7    All rights reserved.
    8
    9    Redistribution and use in source and binary forms, with or without
   10    modification, are permitted provided that the following conditions
   11    are met:
   12
   13    1. Redistributions of source code must retain the above copyright
   14       notice, this list of conditions and the following disclaimer.
   15
   16    2. Redistributions in binary form must reproduce the above copyright
   17       notice, this list of conditions and the following disclaimer in
   18       the documentation and/or other materials provided with the
   19       distribution.
   20
   21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   25    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   29    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   31    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   32    POSSIBILITY OF SUCH DAMAGE.
   33*/
   34
   35:- module(yall,
   36          [ (>>)/2, (>>)/3, (>>)/4, (>>)/5, (>>)/6, (>>)/7, (>>)/8, (>>)/9,
   37            (/)/2, (/)/3, (/)/4, (/)/5, (/)/6, (/)/7, (/)/8, (/)/9,
   38
   39            lambda_calls/2,                     % +LambdaExt, -Goal
   40            lambda_calls/3,                     % +Lambda, +Args, -Goal
   41            is_lambda/1                         % @Term
   42          ]).   43:- autoload(library(error),
   44	    [ instantiation_error/1,
   45	      must_be/2,
   46	      domain_error/2,
   47	      type_error/2
   48	    ]).   49:- autoload(library(lists),[append/3]).   50
   51
   52:- meta_predicate
   53    '>>'(?, 0),
   54    '>>'(?, :, ?),
   55    '>>'(?, :, ?, ?),
   56    '>>'(?, :, ?, ?, ?),
   57    '>>'(?, :, ?, ?, ?, ?),
   58    '>>'(?, :, ?, ?, ?, ?, ?),
   59    '>>'(?, :, ?, ?, ?, ?, ?, ?),
   60    '>>'(?, :, ?, ?, ?, ?, ?, ?, ?).   61
   62:- meta_predicate
   63    '/'(?, 0),
   64    '/'(?, 1, ?),
   65    '/'(?, 2, ?, ?),
   66    '/'(?, 3, ?, ?, ?),
   67    '/'(?, 4, ?, ?, ?, ?),
   68    '/'(?, 5, ?, ?, ?, ?, ?),
   69    '/'(?, 6, ?, ?, ?, ?, ?, ?),
   70    '/'(?, 7, ?, ?, ?, ?, ?, ?, ?).

Lambda expressions

Prolog realizes high-order programming with meta-calling. The core predicate of this is call/1, which simply calls its argument. This can be used to define higher-order predicates such as ignore/1 or forall/2. The call/N construct calls a closure with N-1 additional arguments. This is used to define higher-order predicates such as the maplist/N family or foldl/N.

The problem with higher order predicates based on call/N is that the additional arguments are always added to the end of the closure's argument list. This often requires defining trivial helper predicates to get the argument order right. For example, if you want to add a common postfix to a list of atoms you need to apply atom_concat(In,Postfix,Out), but maplist(x(PostFix),ListIn,ListOut) calls x(PostFix,In,Out). This is where this library comes in, which allows us to write

?- maplist([In,Out]>>atom_concat(In,'_p',Out), [a,b], ListOut).
ListOut = [a_p, b_p].

The {...} specifies which variables are shared between the lambda and the context. This allows us to write the code below. Without the {PostFix} a free variable would be passed to atom_concat/3.

add_postfix(PostFix, ListIn, ListOut) :-
    maplist({PostFix}/[In,Out]>>atom_concat(In,PostFix,Out),
            ListIn, ListOut).

This introduces the second application area of lambda expressions: the ability to stop binding variables in the context. This features shines when combined with bagof/3 or setof/3 where you normally have to specify the the variables in whose binding you are not interested using the Var^Goal construct (marking Var as existential quantified). Lambdas allow doing the reverse: specify the variables in which you are interested.

Lambda expressions use the syntax below

{...}/[...]>>Goal.

The {...} optional part is used for lambda-free variables. The order of variables doesn't matter hence the {...} set notation.

The [...] optional part lists lambda parameters. Here order of variables matters hence the list notation.

As / and >> are standard infix operators, no new operators are added by this library. An advantage of this syntax is that we can simply unify a lambda expression with Free/Parameters>>Lambda to access each of its components. Spaces in the lambda expression are not a problem although the goal may need to be written between ()'s. Goals that are qualified by a module prefix also need to be wrapped inside parentheses.

Combined with library(apply_macros), library(yall) allows writing one-liners for many list operations that have the same performance as hand written code.

The module name, yall, stands for Yet Another Lambda Library.

This module implements Logtalk's lambda expressions syntax. The development of this module was sponsored by Kyndi, Inc.

author
- Paulo Moura and Jan Wielemaker */
To be done
- Extend optimization support
 +Parameters >> +Lambda
 >>(+Parameters, +Lambda, ?A1)
 >>(+Parameters, +Lambda, ?A1, ?A2)
 >>(+Parameters, +Lambda, ?A1, ?A2, ?A3)
 >>(+Parameters, +Lambda, ?A1, ?A2, ?A3, ?A4)
 >>(+Parameters, +Lambda, ?A1, ?A2, ?A3, ?A4, ?A5)
 >>(+Parameters, +Lambda, ?A1, ?A2, ?A3, ?A4, ?A5, ?A6)
 >>(+Parameters, +Lambda, ?A1, ?A2, ?A3, ?A4, ?A5, ?A6, ?A7)
Calls a copy of Lambda. This is similar to call(Lambda,A1,...), but arguments are reordered according to the list Parameters:
Arguments:
Parameters- is either a plain list of parameters or a term {Free}/List. Free represents variables that are shared between the context and the Lambda term. This is needed for compiling Lambda expressions.
  167'>>'(Parms, Lambda) :-
  168    unify_lambda_parameters(Parms, [],
  169                            ExtraArgs, Lambda, LambdaCopy),
  170    Goal =.. [call, LambdaCopy| ExtraArgs],
  171    call(Goal).
  172
  173'>>'(Parms, Lambda, A1) :-
  174    unify_lambda_parameters(Parms, [A1],
  175                            ExtraArgs, Lambda, LambdaCopy),
  176    Goal =.. [call, LambdaCopy| ExtraArgs],
  177    call(Goal).
  178
  179'>>'(Parms, Lambda, A1, A2) :-
  180    unify_lambda_parameters(Parms, [A1,A2],
  181                            ExtraArgs, Lambda, LambdaCopy),
  182    Goal =.. [call, LambdaCopy| ExtraArgs],
  183    call(Goal).
  184
  185'>>'(Parms, Lambda, A1, A2, A3) :-
  186    unify_lambda_parameters(Parms, [A1,A2,A3],
  187                            ExtraArgs, Lambda, LambdaCopy),
  188    Goal =.. [call, LambdaCopy| ExtraArgs],
  189    call(Goal).
  190
  191'>>'(Parms, Lambda, A1, A2, A3, A4) :-
  192    unify_lambda_parameters(Parms, [A1,A2,A3,A4],
  193                            ExtraArgs, Lambda, LambdaCopy),
  194    Goal =.. [call, LambdaCopy| ExtraArgs],
  195    call(Goal).
  196
  197'>>'(Parms, Lambda, A1, A2, A3, A4, A5) :-
  198    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5],
  199                            ExtraArgs, Lambda, LambdaCopy),
  200    Goal =.. [call, LambdaCopy| ExtraArgs],
  201    call(Goal).
  202
  203'>>'(Parms, Lambda, A1, A2, A3, A4, A5, A6) :-
  204    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5,A6],
  205                            ExtraArgs, Lambda, LambdaCopy),
  206    Goal =.. [call, LambdaCopy| ExtraArgs],
  207    call(Goal).
  208
  209'>>'(Parms, Lambda, A1, A2, A3, A4, A5, A6, A7) :-
  210    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5,A6,A7],
  211                            ExtraArgs, Lambda, LambdaCopy),
  212    Goal =.. [call, LambdaCopy| ExtraArgs],
  213    call(Goal).
 +Free / :Lambda
 /(+Free, :Lambda, ?A1)
 /(+Free, :Lambda, ?A1, ?A2)
 /(+Free, :Lambda, ?A1, ?A2, ?A3)
 /(+Free, :Lambda, ?A1, ?A2, ?A3, ?A4)
 /(+Free, :Lambda, ?A1, ?A2, ?A3, ?A4, ?A5)
 /(+Free, :Lambda, ?A1, ?A2, ?A3, ?A4, ?A5, ?A6)
 /(+Free, :Lambda, ?A1, ?A2, ?A3, ?A4, ?A5, ?A6, ?A7)
Shorthand for Free/[]>>Lambda. This is the same as applying call/N on Lambda, except that only variables appearing in Free are bound by the call. For example
p(1,a).
p(2,b).

?- {X}/p(X,Y).
X = 1;
X = 2.

This can in particularly be combined with bagof/3 and setof/3 to select particular variables to be concerned rather than using existential quantification (^/2) to exclude variables. For example, the two calls below are equivalent.

setof(X, Y^p(X,Y), Xs)
setof(X, {X}/p(X,_), Xs)
  248'/'(Free, Lambda) :-
  249    lambda_free(Free),
  250    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  251    call(LambdaCopy).
  252
  253'/'(Free, Lambda, A1) :-
  254    lambda_free(Free),
  255    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  256    call(LambdaCopy, A1).
  257
  258'/'(Free, Lambda, A1, A2) :-
  259    lambda_free(Free),
  260    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  261    call(LambdaCopy, A1, A2).
  262
  263'/'(Free, Lambda, A1, A2, A3) :-
  264    lambda_free(Free),
  265    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  266    call(LambdaCopy, A1, A2, A3).
  267
  268'/'(Free, Lambda, A1, A2, A3, A4) :-
  269    lambda_free(Free),
  270    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  271    call(LambdaCopy, A1, A2, A3, A4).
  272
  273'/'(Free, Lambda, A1, A2, A3, A4, A5) :-
  274    lambda_free(Free),
  275    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  276    call(LambdaCopy, A1, A2, A3, A4, A5).
  277
  278'/'(Free, Lambda, A1, A2, A3, A4, A5, A6) :-
  279    lambda_free(Free),
  280    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  281    call(LambdaCopy, A1, A2, A3, A4, A5, A6).
  282
  283'/'(Free, Lambda, A1, A2, A3, A4, A5, A6, A7) :-
  284    lambda_free(Free),
  285    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  286    call(LambdaCopy, A1, A2, A3, A4, A5, A6, A7).
 unify_lambda_parameters(+ParmsAndFree, +Args, -CallArgs, +Lambda, -LambdaCopy) is det
Arguments:
ParmsAndFree- is the first argumen of >>, either a list of parameters or a term {Free}/Params.
Args- is a list of input parameters, args 3.. from >>
CallArgs- are the calling arguments for the Lambda expression. I.e., we call call(LambdaCopy, CallArgs).
  298unify_lambda_parameters(Parms, _Args, _ExtraArgs, _Lambda, _LambdaCopy) :-
  299    var(Parms),
  300    !,
  301    instantiation_error(Parms).
  302unify_lambda_parameters(Free/Parms, Args, ExtraArgs, Lambda, LambdaCopy) :-
  303    !,
  304    lambda_free(Free),
  305    must_be(list, Parms),
  306    copy_term_nat(Free/Parms>>Lambda, Free/ParmsCopy>>LambdaCopy),
  307    unify_lambda_parameters_(ParmsCopy, Args, ExtraArgs,
  308                             Free/Parms>>Lambda).
  309unify_lambda_parameters(Parms, Args, ExtraArgs, Lambda, LambdaCopy) :-
  310    must_be(list, Parms),
  311    copy_term_nat(Parms>>Lambda, ParmsCopy>>LambdaCopy),
  312    unify_lambda_parameters_(ParmsCopy, Args, ExtraArgs,
  313                             Parms>>Lambda).
  314
  315unify_lambda_parameters_([], ExtraArgs, ExtraArgs, _) :- !.
  316unify_lambda_parameters_([Parm|Parms], [Arg|Args], ExtraArgs, Culprit) :-
  317    !,
  318    Parm = Arg,
  319    unify_lambda_parameters_(Parms, Args, ExtraArgs, Culprit).
  320unify_lambda_parameters_(_,_,_,Culprit) :-
  321    domain_error(lambda_parameters, Culprit).
  322
  323lambda_free(Free) :-
  324    var(Free),
  325    !,
  326    instantiation_error(Free).
  327lambda_free({_}) :- !.
  328lambda_free({}) :- !.
  329lambda_free(Free) :-
  330    type_error(lambda_free, Free).
 expand_lambda(+Goal, -Head) is semidet
True if Goal is a sufficiently instantiated Lambda expression that is compiled to the predicate Head. The predicate Head is added to the current compilation context using compile_aux_clauses/1.
  339expand_lambda(Goal, Head) :-
  340    Goal =.. ['>>', Parms, Lambda| ExtraArgs],
  341    is_callable(Lambda),
  342    nonvar(Parms),
  343    lambda_functor(Parms>>Lambda, Functor),
  344    (   Parms = Free/ExtraArgs
  345    ->  is_lambda_free(Free),
  346        free_to_list(Free, FreeList)
  347    ;   Parms = ExtraArgs,
  348        FreeList = []
  349    ),
  350    append(FreeList, ExtraArgs, Args),
  351    Head =.. [Functor|Args],
  352    compile_aux_clause_if_new(Head, Lambda).
  353expand_lambda(Goal, Head) :-
  354    Goal =.. ['/', Free, Closure|ExtraArgs],
  355    is_lambda_free(Free),
  356    is_callable(Closure),
  357    free_to_list(Free, FreeList),
  358    lambda_functor(Free/Closure, Functor),
  359    append(FreeList, ExtraArgs, Args),
  360    Head =.. [Functor|Args],
  361    Closure =.. [ClosureFunctor|ClosureArgs],
  362    append(ClosureArgs, ExtraArgs, LambdaArgs),
  363    Lambda =.. [ClosureFunctor|LambdaArgs],
  364    compile_aux_clause_if_new(Head, Lambda).
  365
  366lambda_functor(Term, Functor) :-
  367    copy_term_nat(Term, Copy),
  368    variant_sha1(Copy, Functor0),
  369    atom_concat('__aux_yall_', Functor0, Functor).
  370
  371free_to_list({}, []).
  372free_to_list({VarsConj}, Vars) :-
  373    conjunction_to_list(VarsConj, Vars).
  374
  375conjunction_to_list(Term, [Term]) :-
  376    var(Term),
  377    !.
  378conjunction_to_list((Term, Conjunction), [Term|Terms]) :-
  379    !,
  380    conjunction_to_list(Conjunction, Terms).
  381conjunction_to_list(Term, [Term]).
  382
  383compile_aux_clause_if_new(Head, Lambda) :-
  384    prolog_load_context(module, Context),
  385    (   predicate_property(Context:Head, defined)
  386    ->  true
  387    ;   expand_goal(Lambda, LambdaExpanded),
  388        compile_aux_clauses([(Head :- LambdaExpanded)])
  389    ).
  390
  391lambda_like(Goal) :-
  392    compound(Goal),
  393    compound_name_arity(Goal, Name, Arity),
  394    lambda_functor(Name),
  395    Arity >= 2.
  396
  397lambda_functor(>>).
  398lambda_functor(/).
  399
  400:- dynamic system:goal_expansion/2.  401:- multifile system:goal_expansion/2.  402
  403system:goal_expansion(Goal, Head) :-
  404    lambda_like(Goal),
  405    prolog_load_context(source, _),
  406    \+ current_prolog_flag(xref, true),
  407    expand_lambda(Goal, Head).
 is_lambda(@Term) is semidet
True if Term is a valid Lambda expression.
  413is_lambda(Term) :-
  414    compound(Term),
  415    compound_name_arguments(Term, Name, Args),
  416    is_lambda(Name, Args).
  417
  418is_lambda(>>, [Params,Lambda|_]) :-
  419    is_lamdba_params(Params),
  420    is_callable(Lambda).
  421is_lambda(/, [Free,Lambda|_]) :-
  422    is_lambda_free(Free),
  423    is_callable(Lambda).
  424
  425is_lamdba_params(Var) :-
  426    var(Var), !, fail.
  427is_lamdba_params(Free/Params) :-
  428    !,
  429    is_lambda_free(Free),
  430    is_list(Params).
  431is_lamdba_params(Params) :-
  432    is_list(Params).
  433
  434is_lambda_free(Free) :-
  435    nonvar(Free), !, (Free = {_} -> true ; Free == {}).
  436
  437is_callable(Term) :-
  438    strip_module(Term, _, Goal),
  439    callable(Goal).
 lambda_calls(+LambdaExpression, -Goal) is det
 lambda_calls(+LambdaExpression, +ExtraArgs, -Goal) is det
Goal is the goal called if call/N is applied to LambdaExpression, where ExtraArgs are the additional arguments to call/N. ExtraArgs can be an integer or a list of concrete arguments. This predicate is used for cross-referencing and code highlighting.
  451lambda_calls(LambdaExtended, Goal) :-
  452    compound(LambdaExtended),
  453    compound_name_arguments(LambdaExtended, Name, [A1,A2|Extra]),
  454    lambda_functor(Name),
  455    compound_name_arguments(Lambda, Name, [A1,A2]),
  456    lambda_calls(Lambda, Extra, Goal).
  457
  458lambda_calls(Lambda, Extra, Goal) :-
  459    integer(Extra),
  460    !,
  461    length(ExtraVars, Extra),
  462    lambda_calls_(Lambda, ExtraVars, Goal).
  463lambda_calls(Lambda, Extra, Goal) :-
  464    must_be(list, Extra),
  465    lambda_calls_(Lambda, Extra, Goal).
  466
  467lambda_calls_(Params>>Lambda, Args, Goal) :-
  468    unify_lambda_parameters(Params, Args, ExtraArgs, Lambda, LambdaCopy),
  469    extend(LambdaCopy, ExtraArgs, Goal).
  470lambda_calls_(Free/Lambda, ExtraArgs, Goal) :-
  471    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  472    extend(LambdaCopy, ExtraArgs, Goal).
  473
  474extend(Var, _, _) :-
  475    var(Var),
  476    !,
  477    instantiation_error(Var).
  478extend(Cyclic, _, _) :-
  479    cyclic_term(Cyclic),
  480    !,
  481    type_error(acyclic_term, Cyclic).
  482extend(M:Goal0, Extra, M:Goal) :-
  483    !,
  484    extend(Goal0, Extra, Goal).
  485extend(Goal0, Extra, Goal) :-
  486    atom(Goal0),
  487    !,
  488    Goal =.. [Goal0|Extra].
  489extend(Goal0, Extra, Goal) :-
  490    compound(Goal0),
  491    !,
  492    compound_name_arguments(Goal0, Name, Args0),
  493    append(Args0, Extra, Args),
  494    compound_name_arguments(Goal, Name, Args).
  495
  496
  497                 /*******************************
  498                 *     SYNTAX HIGHLIGHTING      *
  499                 *******************************/
  500
  501:- multifile prolog_colour:goal_colours/2.  502
  503yall_colours(Lambda, built_in-[classify,body(Goal)|ArgSpecs]) :-
  504    catch(lambda_calls(Lambda, Goal), _, fail),
  505    Lambda =.. [>>,_,_|Args],
  506    classify_extra(Args, ArgSpecs).
  507
  508classify_extra([], []).
  509classify_extra([_|T0], [classify|T]) :-
  510    classify_extra(T0, T).
  511
  512prolog_colour:goal_colours(Goal, Spec) :-
  513    lambda_like(Goal),
  514    yall_colours(Goal, Spec).
  515
  516
  517                 /*******************************
  518                 *          XREF SUPPORT        *
  519                 *******************************/
  520
  521:- multifile prolog:called_by/4.  522
  523prolog:called_by(Lambda, yall, _, [Goal]) :-
  524    lambda_like(Lambda),
  525    catch(lambda_calls(Lambda, Goal), _, fail).
  526
  527
  528                 /*******************************
  529                 *        SANDBOX SUPPORT       *
  530                 *******************************/
  531
  532:- multifile
  533    sandbox:safe_meta_predicate/1,
  534    sandbox:safe_meta/2.  535
  536sandbox:safe_meta_predicate(yall:(/)/2).
  537sandbox:safe_meta_predicate(yall:(/)/3).
  538sandbox:safe_meta_predicate(yall:(/)/4).
  539sandbox:safe_meta_predicate(yall:(/)/5).
  540sandbox:safe_meta_predicate(yall:(/)/6).
  541sandbox:safe_meta_predicate(yall:(/)/7).
  542
  543sandbox:safe_meta(yall:Lambda, [Goal]) :-
  544    compound(Lambda),
  545    compound_name_arity(Lambda, >>, Arity),
  546    Arity >= 2,
  547    lambda_calls(Lambda, Goal)