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:- use_module(library(error)).   44:- use_module(library(lists)).   45
   46:- meta_predicate
   47    '>>'(?, 0),
   48    '>>'(?, :, ?),
   49    '>>'(?, :, ?, ?),
   50    '>>'(?, :, ?, ?, ?),
   51    '>>'(?, :, ?, ?, ?, ?),
   52    '>>'(?, :, ?, ?, ?, ?, ?),
   53    '>>'(?, :, ?, ?, ?, ?, ?, ?),
   54    '>>'(?, :, ?, ?, ?, ?, ?, ?, ?).   55
   56:- meta_predicate
   57    '/'(?, 0),
   58    '/'(?, 1, ?),
   59    '/'(?, 2, ?, ?),
   60    '/'(?, 3, ?, ?, ?),
   61    '/'(?, 4, ?, ?, ?, ?),
   62    '/'(?, 5, ?, ?, ?, ?, ?),
   63    '/'(?, 6, ?, ?, ?, ?, ?, ?),
   64    '/'(?, 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.
  161'>>'(Parms, Lambda) :-
  162    unify_lambda_parameters(Parms, [],
  163                            ExtraArgs, Lambda, LambdaCopy),
  164    Goal =.. [call, LambdaCopy| ExtraArgs],
  165    call(Goal).
  166
  167'>>'(Parms, Lambda, A1) :-
  168    unify_lambda_parameters(Parms, [A1],
  169                            ExtraArgs, Lambda, LambdaCopy),
  170    Goal =.. [call, LambdaCopy| ExtraArgs],
  171    call(Goal).
  172
  173'>>'(Parms, Lambda, A1, A2) :-
  174    unify_lambda_parameters(Parms, [A1,A2],
  175                            ExtraArgs, Lambda, LambdaCopy),
  176    Goal =.. [call, LambdaCopy| ExtraArgs],
  177    call(Goal).
  178
  179'>>'(Parms, Lambda, A1, A2, A3) :-
  180    unify_lambda_parameters(Parms, [A1,A2,A3],
  181                            ExtraArgs, Lambda, LambdaCopy),
  182    Goal =.. [call, LambdaCopy| ExtraArgs],
  183    call(Goal).
  184
  185'>>'(Parms, Lambda, A1, A2, A3, A4) :-
  186    unify_lambda_parameters(Parms, [A1,A2,A3,A4],
  187                            ExtraArgs, Lambda, LambdaCopy),
  188    Goal =.. [call, LambdaCopy| ExtraArgs],
  189    call(Goal).
  190
  191'>>'(Parms, Lambda, A1, A2, A3, A4, A5) :-
  192    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5],
  193                            ExtraArgs, Lambda, LambdaCopy),
  194    Goal =.. [call, LambdaCopy| ExtraArgs],
  195    call(Goal).
  196
  197'>>'(Parms, Lambda, A1, A2, A3, A4, A5, A6) :-
  198    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5,A6],
  199                            ExtraArgs, Lambda, LambdaCopy),
  200    Goal =.. [call, LambdaCopy| ExtraArgs],
  201    call(Goal).
  202
  203'>>'(Parms, Lambda, A1, A2, A3, A4, A5, A6, A7) :-
  204    unify_lambda_parameters(Parms, [A1,A2,A3,A4,A5,A6,A7],
  205                            ExtraArgs, Lambda, LambdaCopy),
  206    Goal =.. [call, LambdaCopy| ExtraArgs],
  207    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)
  242'/'(Free, Lambda) :-
  243    lambda_free(Free),
  244    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  245    call(LambdaCopy).
  246
  247'/'(Free, Lambda, A1) :-
  248    lambda_free(Free),
  249    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  250    call(LambdaCopy, A1).
  251
  252'/'(Free, Lambda, A1, A2) :-
  253    lambda_free(Free),
  254    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  255    call(LambdaCopy, A1, A2).
  256
  257'/'(Free, Lambda, A1, A2, A3) :-
  258    lambda_free(Free),
  259    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  260    call(LambdaCopy, A1, A2, A3).
  261
  262'/'(Free, Lambda, A1, A2, A3, A4) :-
  263    lambda_free(Free),
  264    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  265    call(LambdaCopy, A1, A2, A3, A4).
  266
  267'/'(Free, Lambda, A1, A2, A3, A4, A5) :-
  268    lambda_free(Free),
  269    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  270    call(LambdaCopy, A1, A2, A3, A4, A5).
  271
  272'/'(Free, Lambda, A1, A2, A3, A4, A5, A6) :-
  273    lambda_free(Free),
  274    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  275    call(LambdaCopy, A1, A2, A3, A4, A5, A6).
  276
  277'/'(Free, Lambda, A1, A2, A3, A4, A5, A6, A7) :-
  278    lambda_free(Free),
  279    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  280    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).
  292unify_lambda_parameters(Parms, _Args, _ExtraArgs, _Lambda, _LambdaCopy) :-
  293    var(Parms),
  294    !,
  295    instantiation_error(Parms).
  296unify_lambda_parameters(Free/Parms, Args, ExtraArgs, Lambda, LambdaCopy) :-
  297    !,
  298    lambda_free(Free),
  299    must_be(list, Parms),
  300    copy_term_nat(Free/Parms>>Lambda, Free/ParmsCopy>>LambdaCopy),
  301    unify_lambda_parameters_(ParmsCopy, Args, ExtraArgs,
  302                             Free/Parms>>Lambda).
  303unify_lambda_parameters(Parms, Args, ExtraArgs, Lambda, LambdaCopy) :-
  304    must_be(list, Parms),
  305    copy_term_nat(Parms>>Lambda, ParmsCopy>>LambdaCopy),
  306    unify_lambda_parameters_(ParmsCopy, Args, ExtraArgs,
  307                             Parms>>Lambda).
  308
  309unify_lambda_parameters_([], ExtraArgs, ExtraArgs, _) :- !.
  310unify_lambda_parameters_([Parm|Parms], [Arg|Args], ExtraArgs, Culprit) :-
  311    !,
  312    Parm = Arg,
  313    unify_lambda_parameters_(Parms, Args, ExtraArgs, Culprit).
  314unify_lambda_parameters_(_,_,_,Culprit) :-
  315    domain_error(lambda_parameters, Culprit).
  316
  317lambda_free(Free) :-
  318    var(Free),
  319    !,
  320    instantiation_error(Free).
  321lambda_free({_}) :- !.
  322lambda_free({}) :- !.
  323lambda_free(Free) :-
  324    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.
  333expand_lambda(Goal, Head) :-
  334    Goal =.. ['>>', Parms, Lambda| ExtraArgs],
  335    is_callable(Lambda),
  336    nonvar(Parms),
  337    lambda_functor(Parms>>Lambda, Functor),
  338    (   Parms = Free/ExtraArgs
  339    ->  is_lambda_free(Free),
  340        free_to_list(Free, FreeList)
  341    ;   Parms = ExtraArgs,
  342        FreeList = []
  343    ),
  344    append(FreeList, ExtraArgs, Args),
  345    Head =.. [Functor|Args],
  346    compile_aux_clause_if_new(Head, Lambda).
  347expand_lambda(Goal, Head) :-
  348    Goal =.. ['/', Free, Closure|ExtraArgs],
  349    is_lambda_free(Free),
  350    is_callable(Closure),
  351    free_to_list(Free, FreeList),
  352    lambda_functor(Free/Closure, Functor),
  353    append(FreeList, ExtraArgs, Args),
  354    Head =.. [Functor|Args],
  355    Closure =.. [ClosureFunctor|ClosureArgs],
  356    append(ClosureArgs, ExtraArgs, LambdaArgs),
  357    Lambda =.. [ClosureFunctor|LambdaArgs],
  358    compile_aux_clause_if_new(Head, Lambda).
  359
  360lambda_functor(Term, Functor) :-
  361    copy_term_nat(Term, Copy),
  362    variant_sha1(Copy, Functor0),
  363    atom_concat('__aux_yall_', Functor0, Functor).
  364
  365free_to_list({}, []).
  366free_to_list({VarsConj}, Vars) :-
  367    conjunction_to_list(VarsConj, Vars).
  368
  369conjunction_to_list(Term, [Term]) :-
  370    var(Term),
  371    !.
  372conjunction_to_list((Term, Conjunction), [Term|Terms]) :-
  373    !,
  374    conjunction_to_list(Conjunction, Terms).
  375conjunction_to_list(Term, [Term]).
  376
  377compile_aux_clause_if_new(Head, Lambda) :-
  378    prolog_load_context(module, Context),
  379    (   predicate_property(Context:Head, defined)
  380    ->  true
  381    ;   expand_goal(Lambda, LambdaExpanded),
  382        compile_aux_clauses([(Head :- LambdaExpanded)])
  383    ).
  384
  385lambda_like(Goal) :-
  386    compound(Goal),
  387    compound_name_arity(Goal, Name, Arity),
  388    lambda_functor(Name),
  389    Arity >= 2.
  390
  391lambda_functor(>>).
  392lambda_functor(/).
  393
  394:- dynamic system:goal_expansion/2.  395:- multifile system:goal_expansion/2.  396
  397system:goal_expansion(Goal, Head) :-
  398    lambda_like(Goal),
  399    prolog_load_context(source, _),
  400    \+ current_prolog_flag(xref, true),
  401    expand_lambda(Goal, Head).
 is_lambda(@Term) is semidet
True if Term is a valid Lambda expression.
  407is_lambda(Term) :-
  408    compound(Term),
  409    compound_name_arguments(Term, Name, Args),
  410    is_lambda(Name, Args).
  411
  412is_lambda(>>, [Params,Lambda|_]) :-
  413    is_lamdba_params(Params),
  414    is_callable(Lambda).
  415is_lambda(/, [Free,Lambda|_]) :-
  416    is_lambda_free(Free),
  417    is_callable(Lambda).
  418
  419is_lamdba_params(Var) :-
  420    var(Var), !, fail.
  421is_lamdba_params(Free/Params) :-
  422    !,
  423    is_lambda_free(Free),
  424    is_list(Params).
  425is_lamdba_params(Params) :-
  426    is_list(Params).
  427
  428is_lambda_free(Free) :-
  429    nonvar(Free), !, (Free = {_} -> true ; Free == {}).
  430
  431is_callable(Term) :-
  432    strip_module(Term, _, Goal),
  433    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.
  445lambda_calls(LambdaExtended, Goal) :-
  446    compound(LambdaExtended),
  447    compound_name_arguments(LambdaExtended, Name, [A1,A2|Extra]),
  448    lambda_functor(Name),
  449    compound_name_arguments(Lambda, Name, [A1,A2]),
  450    lambda_calls(Lambda, Extra, Goal).
  451
  452lambda_calls(Lambda, Extra, Goal) :-
  453    integer(Extra),
  454    !,
  455    length(ExtraVars, Extra),
  456    lambda_calls_(Lambda, ExtraVars, Goal).
  457lambda_calls(Lambda, Extra, Goal) :-
  458    must_be(list, Extra),
  459    lambda_calls_(Lambda, Extra, Goal).
  460
  461lambda_calls_(Params>>Lambda, Args, Goal) :-
  462    unify_lambda_parameters(Params, Args, ExtraArgs, Lambda, LambdaCopy),
  463    extend(LambdaCopy, ExtraArgs, Goal).
  464lambda_calls_(Free/Lambda, ExtraArgs, Goal) :-
  465    copy_term_nat(Free+Lambda, Free+LambdaCopy),
  466    extend(LambdaCopy, ExtraArgs, Goal).
  467
  468extend(Var, _, _) :-
  469    var(Var),
  470    !,
  471    instantiation_error(Var).
  472extend(Cyclic, _, _) :-
  473    cyclic_term(Cyclic),
  474    !,
  475    type_error(acyclic_term, Cyclic).
  476extend(M:Goal0, Extra, M:Goal) :-
  477    !,
  478    extend(Goal0, Extra, Goal).
  479extend(Goal0, Extra, Goal) :-
  480    atom(Goal0),
  481    !,
  482    Goal =.. [Goal0|Extra].
  483extend(Goal0, Extra, Goal) :-
  484    compound(Goal0),
  485    !,
  486    compound_name_arguments(Goal0, Name, Args0),
  487    append(Args0, Extra, Args),
  488    compound_name_arguments(Goal, Name, Args).
  489
  490
  491                 /*******************************
  492                 *     SYNTAX HIGHLIGHTING      *
  493                 *******************************/
  494
  495:- multifile prolog_colour:goal_colours/2.  496
  497yall_colours(Lambda, built_in-[classify,body(Goal)|ArgSpecs]) :-
  498    catch(lambda_calls(Lambda, Goal), _, fail),
  499    Lambda =.. [>>,_,_|Args],
  500    classify_extra(Args, ArgSpecs).
  501
  502classify_extra([], []).
  503classify_extra([_|T0], [classify|T]) :-
  504    classify_extra(T0, T).
  505
  506prolog_colour:goal_colours(Goal, Spec) :-
  507    lambda_like(Goal),
  508    yall_colours(Goal, Spec).
  509
  510
  511                 /*******************************
  512                 *          XREF SUPPORT        *
  513                 *******************************/
  514
  515:- multifile prolog:called_by/4.  516
  517prolog:called_by(Lambda, yall, _, [Goal]) :-
  518    lambda_like(Lambda),
  519    catch(lambda_calls(Lambda, Goal), _, fail).
  520
  521
  522                 /*******************************
  523                 *        SANDBOX SUPPORT       *
  524                 *******************************/
  525
  526:- multifile
  527    sandbox:safe_meta_predicate/1,
  528    sandbox:safe_meta/2.  529
  530sandbox:safe_meta_predicate(yall:(/)/2).
  531sandbox:safe_meta_predicate(yall:(/)/3).
  532sandbox:safe_meta_predicate(yall:(/)/4).
  533sandbox:safe_meta_predicate(yall:(/)/5).
  534sandbox:safe_meta_predicate(yall:(/)/6).
  535sandbox:safe_meta_predicate(yall:(/)/7).
  536
  537sandbox:safe_meta(yall:Lambda, [Goal]) :-
  538    compound(Lambda),
  539    compound_name_arity(Lambda, >>, Arity),
  540    Arity >= 2,
  541    lambda_calls(Lambda, Goal)