Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
library(lambda) benchmarks around?
65 views
Skip to first unread message
Jan Burse
May 10, 2013, 9:17:34 AM5/10/13
to
Dear All,
These benchmarks would to some extend test the
speed of call/n but foremost they would test the
speed of lambda expressions such as (*) in Prolog.
I would be interested in benchmarks that are not
synthetic, but rather little toy examples that
test some aspect of lambda expressions.
Are there such benchmarks around?
Best Regards
(*)
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
These benchmarks would to some extend test the
speed of call/n but foremost they would test the
speed of lambda expressions such as (*) in Prolog.
I would be interested in benchmarks that are not
synthetic, but rather little toy examples that
test some aspect of lambda expressions.
Are there such benchmarks around?
Best Regards
(*)
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
Jan Burse
May 13, 2013, 11:37:59 AM5/13/13
to
Hi,
I guess we can distinguish two approaches to library(lambda).
Namely we might find:
- global-by-default: The variables in the body of the lambda
expression are local by default, if they are not mentioned
by an extra binder.
- local-by-default: The variables in the body of the lambda
expression are global by default, if they are not
mentioned by an extra binder.
Basically I would be interested in test cases that can be
formulated in both approches, so that some cross benchmarking
can be done.
Or the test cases would show the limits of either approach.
Bye
Jan Burse schrieb:
I guess we can distinguish two approaches to library(lambda).
Namely we might find:
- global-by-default: The variables in the body of the lambda
expression are local by default, if they are not mentioned
by an extra binder.
- local-by-default: The variables in the body of the lambda
expression are global by default, if they are not
mentioned by an extra binder.
Basically I would be interested in test cases that can be
formulated in both approches, so that some cross benchmarking
can be done.
Or the test cases would show the limits of either approach.
Bye
Jan Burse schrieb:
Jan Burse
May 21, 2013, 10:21:33 AM5/21/13
to
Dear All,
I have the feeling that global-by-default and local-by-default have
the same expressive power. I am not yet sure, but I have made
a converter which takes a mathematical lambda expression and turns
it into either global-by-default or local-by-default. And I have
then run an example that challenges the notion of a logical variable.
First the example. It is just church pairs. With normal Prolog
pattern matching and the ('.')/2 functor we would do it as
follows:
pair(X, Y, [X|Y]).
first([X|_], X).
second([_|Y], Y).
?- call(pair, A, B, H), first(H, R), second(H, S).
A = R,
B = S,
H = [R|S]
Now for the converters. The source code can be found at the end
of this post. It takes a mathematical lambda expression with
local declarations, where a lambda expression has the
following syntax:
abstraction --> binder "\" body_with_local.
body_with_local --> local "^" body_with_local
| body.
binder --> term.
local --> term.
It then does the following conversion:
Global-by-default:
It adds additional local declarations to assure
alpha conversion of binders and locals in the path
of a binder. The result uses (\)/2 and (^)/2 as
does the input.
Local-by-default:
It adds additional global declarations to minimize
alpha conversion of binders and locals in the path
of a binder. The result uses (\)/1, (+\)/2 and (^)/2
different from the input.
And here the final result. For the church pairs, their
relational version, we use the following mathematical
lambda expressions:
Pair = X\Y\ =(Z\T\call(Z,X,Y,T))
First = Z\call(Z,X\Y\ =(X))
Second = Z\call(Z,X\Y\ =(Y))
Lets look at the results of the conversion and how the
converted lambda expressions do perform:
Global-by-default:
Jekejeke Prolog, Development Environment 0.9.9
(c) 1985-2013, XLOG Technologies GmbH, Switzerland
?- convert(X\Y\ =(Z\T\call(Z,X,Y,T)), R).
R = X\T^Z^Y^Y\T^Z^ =(Z\T^T\call(Z,X,Y,T))
?- convert(Z\call(Z,X\Y\ =(X)), R).
R = Z\call(Z,X\Y^Y\ =(X))
?- convert(Z\call(Z,X\Y\ =(Y)), R).
R = Z\call(Z,X\Y\ =(Y))
?- Pair=X\T^Z^Y^Y\T^Z^ =(Z\T^T\call(Z,X,Y,T)),
First=Z\call(Z,X\Y^Y\ =(X)),
Second=Z\call(Z,X\Y\ =(Y)),
call(Pair,A,B,H), call(First,H,R), call(Second,H,S).
A = R,
B = S,
H = _B\_C^_C\call(_B,R,S,_C)
% Everthing is fine, the results A=R and B=S are logical!
Local-by-default:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
?- convert(X\Y\ =(Z\T\call(Z,X,Y,T)), R).
R = \X^([X]+\Y^ =([X,Y]+\Z^([Z,X,Y]+\T^call(Z,X,Y,T))))
?- convert(Z\call(Z,X\Y\ =(X)), R).
R = [Y,X]+\Z^call(Z,\X^([X]+\Y^ =(X)))
?- convert(Z\call(Z,X\Y\ =(Y)), R).
R = [X,Y]+\Z^call(Z,[Y]+\X^ \Y^ =(Y))
?- Pair = \X^([X]+\Y^ =([X,Y]+\Z^([Z,X,Y]+\T^call(Z,X,Y,T)))),
First = [Y,X]+\Z^call(Z,\X^([X]+\Y^ =(X))),
Second = [X,Y]+\Z^call(Z,[Y]+\X^ \Y^ =(Y)),
call(Pair, A, B, H), call(First, H, R), call(Second, H, S).
A = R,
B = S,
H = [R, S]+\_G1^ ([_G1, R, S]+\_G6^call(_G1, R, S, _G6)).
% Everthing is fine, the results A=R and B=S are logical!
Bottom line? Different to say. Global-by-default is a little bit
more expensive to implement, since in some implementation it needs
a variable set calculation under the hood (not shown here).
Local-by-default on the other hand might have growing terms in
the first argument of the (+\)/2 operator (not shown here). When
the benchmark set has been complete more can be said.
So maybe its just a matter of taste? Whereby I find both approaches
clumsy, manually doing the lambda expressions is error prone.
Unfortunately the converters are also not yet fool proof, for
example they don't warn when a variable is used as a binder and
a global at the same time in the input.
Finally what would be a proof that the converters together with
the corresponding library(lambda) work as expected?
Bye
P.S.:
Converter for Global-by-Default:
http://www.xlog.ch/jekejeke/lambda/inpath.p
Converter for Local-by-Default:
http://www.xlog.ch/jekejeke/lambda/inpath2.p
Jan Burse schrieb:
I have the feeling that global-by-default and local-by-default have
the same expressive power. I am not yet sure, but I have made
a converter which takes a mathematical lambda expression and turns
it into either global-by-default or local-by-default. And I have
then run an example that challenges the notion of a logical variable.
First the example. It is just church pairs. With normal Prolog
pattern matching and the ('.')/2 functor we would do it as
follows:
pair(X, Y, [X|Y]).
first([X|_], X).
second([_|Y], Y).
?- call(pair, A, B, H), first(H, R), second(H, S).
A = R,
B = S,
H = [R|S]
Now for the converters. The source code can be found at the end
of this post. It takes a mathematical lambda expression with
local declarations, where a lambda expression has the
following syntax:
abstraction --> binder "\" body_with_local.
body_with_local --> local "^" body_with_local
| body.
binder --> term.
local --> term.
It then does the following conversion:
Global-by-default:
It adds additional local declarations to assure
alpha conversion of binders and locals in the path
of a binder. The result uses (\)/2 and (^)/2 as
does the input.
Local-by-default:
It adds additional global declarations to minimize
alpha conversion of binders and locals in the path
of a binder. The result uses (\)/1, (+\)/2 and (^)/2
different from the input.
And here the final result. For the church pairs, their
relational version, we use the following mathematical
lambda expressions:
Pair = X\Y\ =(Z\T\call(Z,X,Y,T))
First = Z\call(Z,X\Y\ =(X))
Second = Z\call(Z,X\Y\ =(Y))
Lets look at the results of the conversion and how the
converted lambda expressions do perform:
Global-by-default:
Jekejeke Prolog, Development Environment 0.9.9
(c) 1985-2013, XLOG Technologies GmbH, Switzerland
?- convert(X\Y\ =(Z\T\call(Z,X,Y,T)), R).
R = X\T^Z^Y^Y\T^Z^ =(Z\T^T\call(Z,X,Y,T))
?- convert(Z\call(Z,X\Y\ =(X)), R).
R = Z\call(Z,X\Y^Y\ =(X))
?- convert(Z\call(Z,X\Y\ =(Y)), R).
R = Z\call(Z,X\Y\ =(Y))
?- Pair=X\T^Z^Y^Y\T^Z^ =(Z\T^T\call(Z,X,Y,T)),
First=Z\call(Z,X\Y^Y\ =(X)),
Second=Z\call(Z,X\Y\ =(Y)),
call(Pair,A,B,H), call(First,H,R), call(Second,H,S).
A = R,
B = S,
H = _B\_C^_C\call(_B,R,S,_C)
% Everthing is fine, the results A=R and B=S are logical!
Local-by-default:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
?- convert(X\Y\ =(Z\T\call(Z,X,Y,T)), R).
R = \X^([X]+\Y^ =([X,Y]+\Z^([Z,X,Y]+\T^call(Z,X,Y,T))))
?- convert(Z\call(Z,X\Y\ =(X)), R).
R = [Y,X]+\Z^call(Z,\X^([X]+\Y^ =(X)))
?- convert(Z\call(Z,X\Y\ =(Y)), R).
R = [X,Y]+\Z^call(Z,[Y]+\X^ \Y^ =(Y))
?- Pair = \X^([X]+\Y^ =([X,Y]+\Z^([Z,X,Y]+\T^call(Z,X,Y,T)))),
First = [Y,X]+\Z^call(Z,\X^([X]+\Y^ =(X))),
Second = [X,Y]+\Z^call(Z,[Y]+\X^ \Y^ =(Y)),
call(Pair, A, B, H), call(First, H, R), call(Second, H, S).
A = R,
B = S,
H = [R, S]+\_G1^ ([_G1, R, S]+\_G6^call(_G1, R, S, _G6)).
% Everthing is fine, the results A=R and B=S are logical!
Bottom line? Different to say. Global-by-default is a little bit
more expensive to implement, since in some implementation it needs
a variable set calculation under the hood (not shown here).
Local-by-default on the other hand might have growing terms in
the first argument of the (+\)/2 operator (not shown here). When
the benchmark set has been complete more can be said.
So maybe its just a matter of taste? Whereby I find both approaches
clumsy, manually doing the lambda expressions is error prone.
Unfortunately the converters are also not yet fool proof, for
example they don't warn when a variable is used as a binder and
a global at the same time in the input.
Finally what would be a proof that the converters together with
the corresponding library(lambda) work as expected?
Bye
P.S.:
Converter for Global-by-Default:
http://www.xlog.ch/jekejeke/lambda/inpath.p
Converter for Local-by-Default:
http://www.xlog.ch/jekejeke/lambda/inpath2.p
Jan Burse schrieb:
Graham Cooper
May 21, 2013, 11:02:14 PM5/21/13
to
handles PROLOG variable binding.
u Z Z.
u [ a b ] [ a B ] ?
_ _ _ _ VAR REF TERM
STACK: 1 - B - 32 -
STACK: 2 - Z1 - 1 - a
STACK: 3 - Z1 - 2 - b
B =
------------
It's missing what B binds to when I unify [a b] to [a B].
Z has it's REF value truncated into a Relative-Reverence.
u Z Z
1 2 3
u [a b] [a B]
1 [21 22] [31 32]
It tries to find B which was pushed at REF 32
but only sees the local positions 1 & 2.
This should be an easy fix BTW!
--------------
So the decision is to keep ABSOLUTE REFERENCES to terms/vars
or continue with RELATIVE REFERENCES.
The problem with Absolute References is the Stack will use more space
as the References grow.
s(s(s(s(s(s(0))))))) on the stack will look like
REF TERM
1 s
11 s
111 s
1111 s
11111 s
111111 s
1111111 0
and the problem with RELATIVE REFERENCES is to find the value of a VAR
you have to search from the Start of the Stack and concatenate all the
references which is time expensive.
It's best to keep the space complexity down and remove redundant data
and use RELATIVE REFERENCES.
---------
BTW you can compile lambda abstractions (into machine type code), used
to be called GCode Compiler.
Advantage - fast
Disadvantage - no runtime lambda expressions (LISP)
But I wonder why PROLOG would be the vehicle of choice to interpret
lambda abstractions, there is no unification needed for instantiation.
Herc
--
www.BLoCKPROLOG.com
Jan Burse
May 22, 2013, 2:10:18 AM5/22/13
to
Graham Cooper schrieb:
feature of global-by-default respectiely local-by-default.
The unification happens during copy term. When a new
version of the binder is made and it is unified with the
argument. Usually the binder is just a variable:
V\T
The (\)/n always initially succeeds, and the further
success only depends on the success of T[V/A]. Here is
an example:
?- trace.
Yes
?- call(X\write(X),1).
0 Call call(X \ write(X), 1) ?
1 Call \(X, write(X), 1) ?
2 Call write(1) ?
1 2 Exit write(1) ?
1 Exit \(X, write(X), 1) ?
0 Exit call(X \ write(X), 1) ?
Yes
But it is also possible to use terms, so that the
lambda expression would look as follows:
S\T
The (\)/n then only initially succeeds when a
new variant of the binder unifies with the argument.
Here is an example:
?- call(put(X)\write(X),put(1)).
0 Call call(put(X) \ write(X), put(1)) ?
1 Call \(put(X), write(X), put(1)) ?
2 Call write(1) ?
1 2 Exit write(1) ?
1 Exit \(put(X), write(X), put(1)) ?
0 Exit call(put(X) \ write(X), put(1)) ?
Yes
?- call(putnl(X)\write(X),put(1)).
0 Call call(putnl(X) \ write(X), put(1)) ?
1 Call \(putnl(X), write(X), put(1)) ?
1 Fail \(putnl(X), write(X), put(1)) ?
0 Fail call(putnl(X) \ write(X), put(1)) ?
No
To spin the idea further, the following higher
order (;)/2 comes handy. It is a generalization
of the normal disjunction (;)/2:
% Higher Order Disjunction
;(A,_,B) :- call(A,B).
;(_,A,B) :- call(A,B).
It can be used to dispatch messages when combined
with the binder unification. Here is an example:
?- call((put(X)\write(X);putnl(X)\(write(X),nl)),put(1)).
1Yes
?- call((put(X)\write(X);putnl(X)\(write(X),nl)),putnl(1)).
1
Yes
If a Prolog system has this kind of lambda expressions
and if they would be ultra performant, for example by
compiling the lambda expressions to auxiliary predicates,
they could be used to compile if-then-else expressions.
An if-then-else expression in a clause:
p(...) :- ... (A1 -> B1;
...
An -> Bn;
A) ...
Could be compiled into:
p(...) :- ... call(A1'\(A1'' -> B1);
...
An'\(An'' -> Bn);
A'\A'',X1,..,Xm) ...
But it would need a cut transparent call/n, (\)/n
and (;)/n to be faithful for a if-then-else rewriting.
But compiling lambda expressions to a clause or as
I suggest to a sets of clauses, has already been
done. It could profit from the clause indexing for
the unification of the binder with the argument.
See for example:
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#Hiord
and
Hiord: A Type-Free Higher-Order Logic Programming Language with
Predicate Abstraction
Daniel Cabeza, Manuel Hermenegildo, and James Lipton
ASIAN 2004
Bye
> But I wonder why PROLOG would be the vehicle of choice to interpret
> lambda abstractions, there is no unification needed for instantiation.
I have some examples where I would use the unification
> lambda abstractions, there is no unification needed for instantiation.
feature of global-by-default respectiely local-by-default.
The unification happens during copy term. When a new
version of the binder is made and it is unified with the
argument. Usually the binder is just a variable:
V\T
The (\)/n always initially succeeds, and the further
success only depends on the success of T[V/A]. Here is
an example:
?- trace.
Yes
?- call(X\write(X),1).
0 Call call(X \ write(X), 1) ?
1 Call \(X, write(X), 1) ?
2 Call write(1) ?
1 2 Exit write(1) ?
1 Exit \(X, write(X), 1) ?
0 Exit call(X \ write(X), 1) ?
Yes
But it is also possible to use terms, so that the
lambda expression would look as follows:
S\T
The (\)/n then only initially succeeds when a
new variant of the binder unifies with the argument.
Here is an example:
?- call(put(X)\write(X),put(1)).
0 Call call(put(X) \ write(X), put(1)) ?
1 Call \(put(X), write(X), put(1)) ?
2 Call write(1) ?
1 2 Exit write(1) ?
1 Exit \(put(X), write(X), put(1)) ?
0 Exit call(put(X) \ write(X), put(1)) ?
Yes
?- call(putnl(X)\write(X),put(1)).
0 Call call(putnl(X) \ write(X), put(1)) ?
1 Call \(putnl(X), write(X), put(1)) ?
1 Fail \(putnl(X), write(X), put(1)) ?
0 Fail call(putnl(X) \ write(X), put(1)) ?
No
To spin the idea further, the following higher
order (;)/2 comes handy. It is a generalization
of the normal disjunction (;)/2:
% Higher Order Disjunction
;(A,_,B) :- call(A,B).
;(_,A,B) :- call(A,B).
It can be used to dispatch messages when combined
with the binder unification. Here is an example:
?- call((put(X)\write(X);putnl(X)\(write(X),nl)),put(1)).
1Yes
?- call((put(X)\write(X);putnl(X)\(write(X),nl)),putnl(1)).
1
Yes
If a Prolog system has this kind of lambda expressions
and if they would be ultra performant, for example by
compiling the lambda expressions to auxiliary predicates,
they could be used to compile if-then-else expressions.
An if-then-else expression in a clause:
p(...) :- ... (A1 -> B1;
...
An -> Bn;
A) ...
Could be compiled into:
p(...) :- ... call(A1'\(A1'' -> B1);
...
An'\(An'' -> Bn);
A'\A'',X1,..,Xm) ...
But it would need a cut transparent call/n, (\)/n
and (;)/n to be faithful for a if-then-else rewriting.
But compiling lambda expressions to a clause or as
I suggest to a sets of clauses, has already been
done. It could profit from the clause indexing for
the unification of the binder with the argument.
See for example:
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#Hiord
and
Hiord: A Type-Free Higher-Order Logic Programming Language with
Predicate Abstraction
Daniel Cabeza, Manuel Hermenegildo, and James Lipton
ASIAN 2004
Bye
Jan Burse
May 22, 2013, 3:08:38 AM5/22/13
to
Jan Burse schrieb:
need a more elaborate definition of (;)/3
similar to how (;)/2 works under the hood.
Something along:
% Higher Order Disjunction
;(S\(A->B),C,D) :- ... full if-then-else ..
p(X) :- (X=no -> Y=[]; X=yes(L) -> Y=L;
throw(error(type_error(maybe,X),_))), write(Y).
Could be rewritten to, using the global Y (sic!):
p(X) :- call((no\(true -> Y=[]);
yes(L)\(true -> Y=L);
Z\throw(error(type_error(maybe,Z),_))),X), write(Y).
Which could be used to generate the following
auxiliary predicate, the global Y is now a parameter
since predicates can usually not have globals:
p(X) :- p_aux(X,Y), write(Y).
:- static p_aux/2.
:- set_predicate_property(p_aux/2, sys_noframe).
p_aux(no,T) :- sys_local_cut, T=[].
p_aux(yes(L),T) :- sys_local_cut, T=L.
p_aux(Z,_) :- throw(error(type_error(maybe,Z),_)).
The static, sys_noframe and sys_local_cut are
Jekejeke Prolog specific, and allow to implement
cut transparent predicates. Not really used here,
but just to show it.
But p_aux/2 can for example profit from first
argument indexing.
Bye
> Could be compiled into:
>
> p(...) :- ... call(A1'\(A1'' -> B1);
> ...
> An'\(An'' -> Bn);
> A'\A'',X1,..,Xm) ...
To make the above rewriting work, we would
>
> p(...) :- ... call(A1'\(A1'' -> B1);
> ...
> An'\(An'' -> Bn);
> A'\A'',X1,..,Xm) ...
need a more elaborate definition of (;)/3
similar to how (;)/2 works under the hood.
Something along:
% Higher Order Disjunction
;(S\(A->B),C,D) :- ... full if-then-else ..
;(A,_,B) :- call(A,B).
;(_,A,B) :- call(A,B).
Here is an example of the translation:
;(_,A,B) :- call(A,B).
p(X) :- (X=no -> Y=[]; X=yes(L) -> Y=L;
throw(error(type_error(maybe,X),_))), write(Y).
Could be rewritten to, using the global Y (sic!):
p(X) :- call((no\(true -> Y=[]);
yes(L)\(true -> Y=L);
Z\throw(error(type_error(maybe,Z),_))),X), write(Y).
Which could be used to generate the following
auxiliary predicate, the global Y is now a parameter
since predicates can usually not have globals:
p(X) :- p_aux(X,Y), write(Y).
:- static p_aux/2.
:- set_predicate_property(p_aux/2, sys_noframe).
p_aux(no,T) :- sys_local_cut, T=[].
p_aux(yes(L),T) :- sys_local_cut, T=L.
p_aux(Z,_) :- throw(error(type_error(maybe,Z),_)).
The static, sys_noframe and sys_local_cut are
Jekejeke Prolog specific, and allow to implement
cut transparent predicates. Not really used here,
but just to show it.
But p_aux/2 can for example profit from first
argument indexing.
Bye
Graham Cooper
May 22, 2013, 3:11:42 AM5/22/13
to
My Prolog interpreter is interpreted! (PHP)
so I'm focussing on the HTML Server Side processing.
e.g. giving Database Queries inside a HTML subset.
...
COMPOUND PROLOG QUERY <====> FORM LAYOUT
R.I.S.C.H.T.M.L. Reduced Instruction Set HTML
...
<col> clients ID SNAME FNAME ADDRESS
<rows> invoices INV ID SNAME FNAME </rows>
</col>
...
OUTPUT
_______________________
ID SNAME FNAME ADDRESS
2 TOM SMITH SYDNEY
INV ID SNAME FNAME
2 2 SMITH TOM
3 2 SMITH TOM
4 2 SMITH TOM
PAGE 1/434
<< < ID[V][_SEARCH_] > >>
-----------------------
Then I might look at solving simultaneous equations by adding GROUP_BY
(FOR ALL) functionality.
clients C SNAME FNAME AGE
____________________________________
clients 1 cooper gray 33
clients 2 willsandburk burt 44
clients 3 maths fun 33
cnt_PNT
sum_PNT
all_MEMBR
ave_STUFF
min_POS
max_POS
naf_NAF <- depth first may not complete...
FIRST
LAST
NEXT ?
PREV ?
e( tom, men )
e( fred , men )
e( tim , men )
e( cat , women )
e( cnt_M , grp_SET ) ?
==> e ( 3 , men )
......
e( cnt_M , grp_SET ) ?
==>
e [ cnt_M | grp_SET ]
--|-------|---------|
e [ 3 | men ]
e [ 1 | women ]
Then do a small Invoicing App maybe that webmasters can customise with
the <row> and <col> Forms!
Herc
--
www.BLOCKPROLOG.com
Jan Burse
May 22, 2013, 3:25:06 AM5/22/13
to
Graham Cooper schrieb:
set of predicates and aggregate predicates. It is not so
pronounced for local-by-default, but in global-by-default,
as I implement it, the same variable calculation as in set
of is used.
In the write-up of Ulrich Neumerkel one on the other hand
finds a suggestion to use the +\ extra binder in the
set of predicate. Not sure, but it could be that Logtalk
has already implemented that.
Bye
> Then I might look at solving simultaneous equations by adding GROUP_BY
> (FOR ALL) functionality.
There is a slight relationship between library(lambda) and
> (FOR ALL) functionality.
set of predicates and aggregate predicates. It is not so
pronounced for local-by-default, but in global-by-default,
as I implement it, the same variable calculation as in set
of is used.
In the write-up of Ulrich Neumerkel one on the other hand
finds a suggestion to use the +\ extra binder in the
set of predicate. Not sure, but it could be that Logtalk
has already implemented that.
Bye
pic...@alice.it
May 22, 2013, 1:04:23 PM5/22/13
to
The discussion about lambda expressions and Prolog is very interesting. The present message is motivated by curiosity, so please be patient.
--
FIRST, I was thinking that maplist/[2..n] could be modified to accept as first argument a term of the type Head :- Body, like in the following example:
?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
which would be translated into 3 subsequent goals:
1) assert(lambda(X, Y) :- Y is X+1).
2) maplist(lambda, [1, 2, 3], List).
3) retract(lambda(_, _)). % or better abolish(lambda/2)
In other words the predicate lambda/2 would be LOCAL to the call.
--
THEN I realized that another strategy without changing maplist/[2..n] would be to define a new call_with_local_definition/2 (ugly name) predicate such that:
?- call_with_local_definition(lambda(X, Y) :- Y is X+1, maplist(lambda, [1, 2, 3], List)).
Basically first parameter would be interpreted in "assert-mode" and then retracted (or better, abolished).
--
BUT FINALLY, I could find no good reasons for the above other than typing-less compared to:
?- setup_call_cleanup(assert(lambda(X, Y) :- Y is X+1), maplist(lambda, [1, 2, 3], List), abolish(lambda/2)).
Btw, in general this sort of predicate would be utilized for other purposes as well, like in the next example (which is currently not possible):
?- call_with_local_definition(:- use_module(library(random)), maplist(random, [1, 2, 3], [9, 8, 7], List)).
List = [1, 3, 5]
?- random(1, 9, X).
ERROR: Undefined procedure: random/3
I am not really sure to have understood whether lambdas add value to Prolog other than typing less.
Can somebody help me understand?
P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
Thank you.
Mauro
pic...@alice.it
May 22, 2013, 1:11:44 PM5/22/13
to
> If I remember correctly, it is currently possible to support this via
> set_prolog_flag/2 ...
OK that is not true. Just for reading F(x) as it were 'F'(x).
Mauro
Jan Burse
May 22, 2013, 4:02:39 PM5/22/13
to
pic...@alice.it schrieb:
are in the scope of this post archive the same via
copy_term/2. You can view this predicate also as:
copy_term(X,Y) :-
assertz(temp(X)),
temp(Y),
retract(temp(_)).
But copy_term/2 is not exactly implemented via assertz/1
and retract/1, often more direct and sometimes with better
structure sharing.
But there is one advantage of your approach, you pass
around an atom. Which is very easy to call. In the libraries
there is still an intermediate step, so that after the
copy_term/2 something more complex is called.
What is missing in your approach, is what you would
offer for global/local variables. What would be your
take here?
Bye
> ?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
>
> which would be translated into 3 subsequent goals:
>
> 1) assert(lambda(X, Y) :- Y is X+1).
> 2) maplist(lambda, [1, 2, 3], List).
> 3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
> In other words the predicate lambda/2 would be LOCAL to the call.
>
To some extend the libraries for lambda expressions that
>
> which would be translated into 3 subsequent goals:
>
> 1) assert(lambda(X, Y) :- Y is X+1).
> 2) maplist(lambda, [1, 2, 3], List).
> 3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
> In other words the predicate lambda/2 would be LOCAL to the call.
>
are in the scope of this post archive the same via
copy_term/2. You can view this predicate also as:
copy_term(X,Y) :-
assertz(temp(X)),
temp(Y),
retract(temp(_)).
But copy_term/2 is not exactly implemented via assertz/1
and retract/1, often more direct and sometimes with better
structure sharing.
But there is one advantage of your approach, you pass
around an atom. Which is very easy to call. In the libraries
there is still an intermediate step, so that after the
copy_term/2 something more complex is called.
What is missing in your approach, is what you would
offer for global/local variables. What would be your
take here?
Bye
Graham Cooper
May 22, 2013, 6:02:31 PM5/22/13
to
On May 23, 3:04 am, pico...@alice.it wrote:
> The discussion about lambda expressions and Prolog is very interesting. The present message is motivated by curiosity, so please be patient.
>
> --
>
> FIRST, I was thinking that maplist/[2..n] could be modified to accept as first argument a term of the type Head :- Body, like in the following example:
>
> ?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
>
> which would be translated into 3 subsequent goals:
>
> 1) assert(lambda(X, Y) :- Y is X+1).
> 2) maplist(lambda, [1, 2, 3], List).
> 3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
> In other words the predicate lambda/2 would be LOCAL to the call.
>
> --
>
> THEN I realized that another strategy without changing maplist/[2..n] would be to define a new call_with_local_definition/2 (ugly name) predicate such that:
>
> ?- call_with_local_definition(lambda(X, Y) :- Y is X+1, maplist(lambda, [1, 2, 3], List)).
>
> Basically first parameter would be interpreted in "assert-mode" and then retracted (or better, abolished).
>
> --
>
> BUT FINALLY, I could find no good reasons for the above other than typing-less compared to:
>
> ?- setup_call_cleanup(assert(lambda(X, Y) :- Y is X+1), maplist(lambda, [1, 2, 3], List), abolish(lambda/2)).
>
> Btw, in general this sort of predicate would be utilized for other purposes as well, like in the next example (which is currently not possible):
>
> ?- call_with_local_definition(:- use_module(library(random)), maplist(random, [1, 2, 3], [9, 8, 7], List)).
> List = [1, 3, 5]
> ?- random(1, 9, X).
> ERROR: Undefined procedure: random/3
>
> I am not really sure to have understood whether lambdas add value to Prolog other than typing less.
> Can somebody help me understand?
>
lambda is just
> The discussion about lambda expressions and Prolog is very interesting. The present message is motivated by curiosity, so please be patient.
>
> --
>
> FIRST, I was thinking that maplist/[2..n] could be modified to accept as first argument a term of the type Head :- Body, like in the following example:
>
> ?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
>
> which would be translated into 3 subsequent goals:
>
> 1) assert(lambda(X, Y) :- Y is X+1).
> 2) maplist(lambda, [1, 2, 3], List).
> 3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
> In other words the predicate lambda/2 would be LOCAL to the call.
>
> --
>
> THEN I realized that another strategy without changing maplist/[2..n] would be to define a new call_with_local_definition/2 (ugly name) predicate such that:
>
> ?- call_with_local_definition(lambda(X, Y) :- Y is X+1, maplist(lambda, [1, 2, 3], List)).
>
> Basically first parameter would be interpreted in "assert-mode" and then retracted (or better, abolished).
>
> --
>
> BUT FINALLY, I could find no good reasons for the above other than typing-less compared to:
>
> ?- setup_call_cleanup(assert(lambda(X, Y) :- Y is X+1), maplist(lambda, [1, 2, 3], List), abolish(lambda/2)).
>
> Btw, in general this sort of predicate would be utilized for other purposes as well, like in the next example (which is currently not possible):
>
> ?- call_with_local_definition(:- use_module(library(random)), maplist(random, [1, 2, 3], [9, 8, 7], List)).
> List = [1, 3, 5]
> ?- random(1, 9, X).
> ERROR: Undefined procedure: random/3
>
> I am not really sure to have understood whether lambdas add value to Prolog other than typing less.
> Can somebody help me understand?
>
function anon()
...
which was the cornerstone of LISP - dynamic function creation
But it's not much faster with LISP evaluators as that uses graph
reduction, what might speed up the more 3GL Prolog sections is a
template lambda compiler.
Prolog is more suited for SET-LEVEL Reasoning than sequence
manipulation.
IMO the List Processing and BAGOF, MAPCAR etc were added too soon.
AN ARRAY IN PROLOG
?- clients( ID , NAME , SURNAME )
clients 1 tom smith
clients 2 mary smith
clients 3 jack jones
It's like taking SQL and only outputting the first row, then compiling
the SET of results and piping them to LISP instead for single row at a
time evaluation!
All that's needed is an ALL junction to continue using set at a time
logic.
subset( A , B ) :- if( e(all_A,B) , e(A ,B) ).
then all the SQL Operands follow.
all_VAR , cnt_VAR , sum_VAR , min_VAR , max_VAR
...
i.e. Just Output all results in a TABLE and refer to that in native
Prolog with SET-OPERANDS instead of calling 3GL list processing.
>
> P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
> same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
> set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
>
Arity mismatch between GOAL and HEAD for 1!
It's the same as Quantifying over functions in logic.
A(F):x->y F(...)
which is then 2nd Order Logic.
It's not necessary if you define each functor individually
and then refer to them by a common leading functor.
ie.
instead of
?- X ( 1 , 2 , 3 )
use:
arith( add , A , B , C ) ) :- ...
arith( sub , A , B , C ) ) :- ...
arith( div , A , B , C ) ) :- ...
now you can call over a variable 'functor'.
?- arith( X , 1 , 2 , 3 )
X = add
-----
Same expressiveness as high order Prolog
with the restriction of a predefined fixed
set of operands.
======================
It also complicates the matching algorithm.
HEAD ---------- unify ---------- GOAL
f
/ \
/\ /\
t V t t
----------
draw the GOAL tree here..
f
/ \
/\ /\
t f t V
/\
f V
----------------
All possible variables are bound in the GOAL to terms,
which leaves the remaining vars as leaf nodes.
All the variables in the head are fresh so they are also leaf nodes, I
add 1 to each Variable name to distinguish them.
e.g.
GOAL VARS - V4, X4, T4
HEAD VARS - A5, X5
-----------------
The difference is GOAL VARS just become pointers if there's any
further VARIABLE matching
and HEAD VARS get bound.
i.e.
GOAL VARS are like putting tin cans on the leaves of a shrub.
HEAD VARS are like tin cans you pot grafts in!
HEAD
f
/ \
/\ /\
t V t t
V is bound to a graft of a predicate fragment from the GOAL
V=f
/\
f V
my tin can potting mix analogy is upside-down!
However! It would introduce a whole other level of trial and error
matching to have variable functors since they would be part variable
and part bound.
Herc
--
www.BLoCKPROLOG.com
Jan Burse
May 22, 2013, 7:17:54 PM5/22/13
to
Graham Cooper schrieb:
provides lambda expressions. call/n is simpler than
variable functors, since it doesn't change the data
structure of Prolog.
But it is more or less the same power what concerns
calling higher order goals. On the other hand matching
higher order terms is a different topic, that is not
addressed by a library(lambda) and call/n.
Benchmarking the matching of higher order terms would
need a different set of test cases than benchmarking
library(lambda). And it would probably be a good idea
to open a separate thread for that.
Bye
> However! It would introduce a whole other level of trial and error
> matching to have variable functors since they would be part variable
> and part bound.
Actually library(lambda) only assumes call/n and
> matching to have variable functors since they would be part variable
> and part bound.
provides lambda expressions. call/n is simpler than
variable functors, since it doesn't change the data
structure of Prolog.
But it is more or less the same power what concerns
calling higher order goals. On the other hand matching
higher order terms is a different topic, that is not
addressed by a library(lambda) and call/n.
Benchmarking the matching of higher order terms would
need a different set of test cases than benchmarking
library(lambda). And it would probably be a good idea
to open a separate thread for that.
Bye
Jan Burse
May 22, 2013, 7:23:39 PM5/22/13
to
Jan Burse schrieb:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
And here is a local-by-default library(lambda):
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
And here is a global-by-default library(lambda):
http://www.xlog.ch/jekejeke/lambda/lambda3.p
>
> But it is more or less the same power what concerns
> calling higher order goals. On the other hand matching
> higher order terms is a different topic, that is not
> addressed by a library(lambda) and call/n.
Here is a reference to call/n:
> But it is more or less the same power what concerns
> calling higher order goals. On the other hand matching
> higher order terms is a different topic, that is not
> addressed by a library(lambda) and call/n.
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
And here is a local-by-default library(lambda):
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
And here is a global-by-default library(lambda):
http://www.xlog.ch/jekejeke/lambda/lambda3.p
Ulrich Neumerkel
May 23, 2013, 10:17:57 AM5/23/13
to
pic...@alice.it writes:
>P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
>same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
>set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
Please note that call/N and (=..)/2 do not accomplish the same!
>P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
>same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
>set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
call/N permits to use some functor that gets further arguments
(called a continuation) whereas (=..)/2 (alone) restricts
the continuation to a fixed arity, most often zero.
You find frequently:
... Goal =.., [F,A,B], Goal, ...
which limits F to be an atom. Instead,
... call(F,A,B), ...
offers the full generality. Like in:
call(functor(F,c), 0).
Succeeds, unifying F with c.
call(call(call(atom_concat, pro), log), Atom).
Succeeds, unifying Atom with prolog.
Examples from 8.15.4.4, http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
In any case call/N gives you the higher-order functionality necessary
for higher-order programming. In (older) systems that support only
call/1 but not call/2..call/8, it can be trivially added by adding
rules for call/2 up to call/8 - thus showing that "there is no magic
involved".
Notations like F(A,B) open up a can of worms and magic that need to be
defined. Like the precise translation of this construct. Must F be an
atom? etc.
Ulrich Neumerkel
May 23, 2013, 10:43:24 AM5/23/13
to
pic...@alice.it writes:
>
>The discussion about lambda expressions and Prolog is very interesting. The present message is motivated by curiosity, so please be patient.
>
>--
>
>FIRST, I was thinking that maplist/[2..n] could be modified to accept as first argument a term of the type Head :- Body, like in the following example:
>
>?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
>
>which would be translated into 3 subsequent goals:
>
>1) assert(lambda(X, Y) :- Y is X+1).
>2) maplist(lambda, [1, 2, 3], List).
>3) retract(lambda(_, _)). % or better abolish(lambda/2)
This does not work for nested lambdas.
>
>The discussion about lambda expressions and Prolog is very interesting. The present message is motivated by curiosity, so please be patient.
>
>--
>
>FIRST, I was thinking that maplist/[2..n] could be modified to accept as first argument a term of the type Head :- Body, like in the following example:
>
>?- maplist(lambda(X, Y) :- Y is X+1, [1, 2, 3], List).
>
>which would be translated into 3 subsequent goals:
>
>1) assert(lambda(X, Y) :- Y is X+1).
>2) maplist(lambda, [1, 2, 3], List).
>3) retract(lambda(_, _)). % or better abolish(lambda/2)
pic...@alice.it
May 23, 2013, 1:48:38 PM5/23/13
to
> >
>
> >1) assert(lambda(X, Y) :- Y is X+1).
>
> >2) maplist(lambda, [1, 2, 3], List).
>
> >3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
>
>
> This does not work for nested lambdas.
Thank you very much.
pic...@alice.it
May 23, 2013, 2:08:01 PM5/23/13
to
>
>
> In any case call/N gives you the higher-order functionality necessary
>
> for higher-order programming. In (older) systems that support only
>
> call/1 but not call/2..call/8, it can be trivially added by adding
>
> rules for call/2 up to call/8 - thus showing that "there is no magic
>
> involved".
>
>
>
> Notations like F(A,B) open up a can of worms and magic that need to be
>
> defined. Like the precise translation of this construct. Must F be an
>
> atom? etc.
Very nicely explained.
>
> In any case call/N gives you the higher-order functionality necessary
>
> for higher-order programming. In (older) systems that support only
>
> call/1 but not call/2..call/8, it can be trivially added by adding
>
> rules for call/2 up to call/8 - thus showing that "there is no magic
>
> involved".
>
>
>
> Notations like F(A,B) open up a can of worms and magic that need to be
>
> defined. Like the precise translation of this construct. Must F be an
>
> atom? etc.
I have this further thought-experiment, which if I have understood well, should make sense:
Let's consider F(A,B) with F atom or callable, such that:
F = p --> F(A,B) = p(A,B) % i.e. F = p/0
or, for example,
F = p(C) --> F(A,B) = p(C)(A,B) --> p(C,A,B) % i.e. F = p/1
Now, the question is: should the main functor of F be required to be...
...instantiated?
here I think there would be no problem. as an illustration:
?- member(F, [p1, p2]), F(X). % this would call p1(X) and p2(X) on backtracking
...uninstantiated?
in this case one asks: which is the order of defined predicates? Is there any way to define predicate order, and can predicate order be any meaningful?
One naive possibility is the following:
?- use_module(mymodule), mymodule:_(X). % this would call all 1-arity predicates defined in module "mymodule", but... in which order? alphabetical, appearance...??
Thanks in advance.
Mauro
Ulrich Neumerkel
May 23, 2013, 3:49:48 PM5/23/13
to
( )
BTW, here, you need extra parentheses.
>> >2) maplist(lambda, [1, 2, 3], List).
>>
>> >3) retract(lambda(_, _)). % or better abolish(lambda/2)
>>
>>
>>
>> This does not work for nested lambdas.
>
>Could you please give me an example of nested lambda?
In the definition of your lambda, on it's right side, you have
again a maplist with a lambda.
..., maplist(\Xs^Ys^maplist(\X^Y^(Y is X+1),Ys,Xs),Xss,Yss), ...
BTW, here, you need extra parentheses.
>> >2) maplist(lambda, [1, 2, 3], List).
>>
>> >3) retract(lambda(_, _)). % or better abolish(lambda/2)
>>
>>
>>
>> This does not work for nested lambdas.
>
>Could you please give me an example of nested lambda?
again a maplist with a lambda.
..., maplist(\Xs^Ys^maplist(\X^Y^(Y is X+1),Ys,Xs),Xss,Yss), ...
Ulrich Neumerkel
May 23, 2013, 3:55:54 PM5/23/13
to
pic...@alice.it writes:
>Let's consider F(A,B) with F atom or callable, such that:
>
>F = p --> F(A,B) = p(A,B) % i.e. F = p/0
>
>or, for example,
>
>F = p(C) --> F(A,B) = p(C)(A,B) --> p(C,A,B) % i.e. F = p/1
You are making here a lot of assumptions as to how far Prolog's
>Let's consider F(A,B) with F atom or callable, such that:
>
>F = p --> F(A,B) = p(A,B) % i.e. F = p/0
>
>or, for example,
>
>F = p(C) --> F(A,B) = p(C)(A,B) --> p(C,A,B) % i.e. F = p/1
syntax should stretch that is practically impossible to fulfill. Instead write:
F = p(C) --> call(F,A,B) = call(p(C),A,B) --> p(C,A,B).
>Now, the question is: should the main functor of F be required to be...
>
>...instantiated?
always be instantiated. Otherwise you get an instantiation error.
If you remove that restriction, you are up into higher-order logic.
This has tremendous consequences, things are not longer decidable,
you can opt for some compromises there, but it all gets very nasty.
Graham Cooper
May 23, 2013, 6:39:15 PM5/23/13
to
e.g.
\i.(k=0,for(j=1,j<=i,j++){k+=f(j)},out(k)) 7
= f(1) + f(2) + f(3) + ...+ f(7)
------------------
Now replace f with another lambda.
\i.(k=0,for(j=1,j<=i,j++)
{k+= [\x.(x+x/3)j] },out(k)) 7
Herc
--
www.BLoCKPROLOG.com
the debugging continues...
Graham Cooper
May 23, 2013, 7:28:29 PM5/23/13
to
On May 24, 12:17 am, ulr...@mips.complang.tuwien.ac.at (Ulrich
Neumerkel) wrote:
over a finite domain of pre-defined functors.
It just takes 1 line per definition or each functor.
Variable substitution to emulate lambda graph reduction is a bit like
using GOTO Statements. That Level of operability is handled (BY JMP
#FF00) already!
Same with PROLOG, you HAVE a variable binding system already (BOTH
WAYS - much more advanced than one way variable instantiation).
If you need a speed improvement just Flag
[ 1 way GOAL->HEAD binding only! ]
that will do CALL functions easily!
-----------------
The PROBLEMS you are trying to solve stem from 2nd Order Logic but it
is simply PARAMETER REFERENCING! i.e. white box inspection of
formulas.
2.O.L. is intended for writing AXIOMS not THEOREMS (the code..)
That's why AXIOMS tend to CHEAT a little with the Syntax!
2OL
for all predicates p...
A(X) A(i) phi(... X ...) phi2(... Xi... )
It changes from 1.O.L. parameter number indexing (count the commas) to
variable 'NAME' referencing. Most Logicians don't seem to notice
they are defining a simpler class of theorems than their definitions
in 2.O.L. themselves.
-------------------------------
This can all be avoided in Native Prolog though.
You define CLASSES of operands.
e.g. in SET THEORY the 1 class is 'e'.
nat(0).
nat(s(X)) :- nat(X).
even(0).
even(s(s(X))) :- even(X).
odd(s(0)).
odd(s(s(X))) :- odd(X).
Pardon the primitive level of primitive functors here!
Then you define the CLASS.
e( A , nats ) :- nat(A).
e( A , evens ) :- even(A).
e( A , odds ) :- odd(A).
SETS = Plural (Simple no?)
--------------
This is the STARGATE!
From here you can do Hi Level (set at a time)
programs using the CLASS of names.
?- intersect( nats , odds )
will search through 0, s(0)
and output YES!
USE:
intersect(S,T) :- e(A,S),e(A,t).
---------------
The Key here is, though you can't see it in this example
is the internal referencing of nat(X) and odd(X) as
to WHICH PARAMETER *POSITION* are we using when we
refer to ... functor odd().
That's all pre-specified!
In 2.O.L. Axioms have to Declare By Name the internal parameter
positions when they QUALIFY OVER ALL THEOREMS. e.g "P" in f(..P..)
===============
Now returning to my ARITHMETIC example.
instead of
?- X ( 1 , 2 , 3 )
use:
arith( add , A , B , C ) ) :- ...
arith( sub , A , B , C ) ) :- ...
arith( div , A , B , C ) ) :- ...
now you can call over a variable 'functor'.
?- arith( X , 1 , 2 , 3 )
X = add
------------------------
This doesn't look as *Expressive* as Lambda abstractions but it works
extremely well.
arith( add , A , B , C ) ) :- C is A + B.
arith( sub , A , B , C ) ) :- C is A - B.
arith( div , A , B , C ) ) :- C is A / B.
1 LINE DEFINITION for each function.
-----------------------------------
INTO A CLASS FUNCTOR
--------------------
If you need to REFERENCE a different parameter in 2.O.L.
then you add a new CLASS member for each parameter position needed.
********
The Process is actually a little more involved...
class( ARG , EXPRESSION ) :- functor(..,...,..., ARG , ... ).
where EXPRESSION is a string of functors you define.
*********
?- arith( X , 1 , 2 , 3 )
X = add
WHAT MAKES 3 FROM 1 & 2 ?
PROLOG> ADD!
Try doing that in C!
----------
Herc
--
www.BLOCKPROLOG.com
the debugging years...
Neumerkel) wrote:
> pico...@alice.it writes:
> >P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
> >same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
> >set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
>
> Please note that call/N and (=..)/2 do not accomplish the same!
> call/N permits to use some functor that gets further arguments
> (called a continuation) whereas (=..)/2 (alone) restricts
> the continuation to a fixed arity, most often zero.
>
> You find frequently:
>
> ... Goal =.., [F,A,B], Goal, ...
>
> which limits F to be an atom. Instead,
>
> ... call(F,A,B), ...
>
> offers the full generality. Like in:
>
> call(functor(F,c), 0).
> Succeeds, unifying F with c.
>
> call(call(call(atom_concat, pro), log), Atom).
> Succeeds, unifying Atom with prolog.
>
> Examples from 8.15.4.4,http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
> >P.S.: I also would like to know why having a variable as functor is not accepted in ISO Prolog, where the
> >same can be accomplished via call/n or (=..)/2. If I remember correctly, it is currently possible to support this via
> >set_prolog_flag/2, but it would be nice to have that behavior in the standard. Any good reason against it?
>
> Please note that call/N and (=..)/2 do not accomplish the same!
> call/N permits to use some functor that gets further arguments
> (called a continuation) whereas (=..)/2 (alone) restricts
> the continuation to a fixed arity, most often zero.
>
> You find frequently:
>
> ... Goal =.., [F,A,B], Goal, ...
>
> which limits F to be an atom. Instead,
>
> ... call(F,A,B), ...
>
> offers the full generality. Like in:
>
> call(functor(F,c), 0).
> Succeeds, unifying F with c.
>
> call(call(call(atom_concat, pro), log), Atom).
> Succeeds, unifying Atom with prolog.
>
>
> In any case call/N gives you the higher-order functionality necessary
> for higher-order programming. In (older) systems that support only
> call/1 but not call/2..call/8, it can be trivially added by adding
> rules for call/2 up to call/8 - thus showing that "there is no magic
> involved".
>
> Notations like F(A,B) open up a can of worms and magic that need to be
> defined. Like the precise translation of this construct. Must F be an
> atom? etc.
>
Native Unify can handle High Order programming
> In any case call/N gives you the higher-order functionality necessary
> for higher-order programming. In (older) systems that support only
> call/1 but not call/2..call/8, it can be trivially added by adding
> rules for call/2 up to call/8 - thus showing that "there is no magic
> involved".
>
> Notations like F(A,B) open up a can of worms and magic that need to be
> defined. Like the precise translation of this construct. Must F be an
> atom? etc.
>
over a finite domain of pre-defined functors.
It just takes 1 line per definition or each functor.
Variable substitution to emulate lambda graph reduction is a bit like
using GOTO Statements. That Level of operability is handled (BY JMP
#FF00) already!
Same with PROLOG, you HAVE a variable binding system already (BOTH
WAYS - much more advanced than one way variable instantiation).
If you need a speed improvement just Flag
[ 1 way GOAL->HEAD binding only! ]
that will do CALL functions easily!
-----------------
The PROBLEMS you are trying to solve stem from 2nd Order Logic but it
is simply PARAMETER REFERENCING! i.e. white box inspection of
formulas.
2.O.L. is intended for writing AXIOMS not THEOREMS (the code..)
That's why AXIOMS tend to CHEAT a little with the Syntax!
2OL
for all predicates p...
A(X) A(i) phi(... X ...) phi2(... Xi... )
It changes from 1.O.L. parameter number indexing (count the commas) to
variable 'NAME' referencing. Most Logicians don't seem to notice
they are defining a simpler class of theorems than their definitions
in 2.O.L. themselves.
-------------------------------
This can all be avoided in Native Prolog though.
You define CLASSES of operands.
e.g. in SET THEORY the 1 class is 'e'.
nat(0).
nat(s(X)) :- nat(X).
even(0).
even(s(s(X))) :- even(X).
odd(s(0)).
odd(s(s(X))) :- odd(X).
Pardon the primitive level of primitive functors here!
Then you define the CLASS.
e( A , nats ) :- nat(A).
e( A , evens ) :- even(A).
e( A , odds ) :- odd(A).
SETS = Plural (Simple no?)
--------------
This is the STARGATE!
From here you can do Hi Level (set at a time)
programs using the CLASS of names.
?- intersect( nats , odds )
will search through 0, s(0)
and output YES!
USE:
intersect(S,T) :- e(A,S),e(A,t).
---------------
The Key here is, though you can't see it in this example
is the internal referencing of nat(X) and odd(X) as
to WHICH PARAMETER *POSITION* are we using when we
refer to ... functor odd().
That's all pre-specified!
In 2.O.L. Axioms have to Declare By Name the internal parameter
positions when they QUALIFY OVER ALL THEOREMS. e.g "P" in f(..P..)
===============
Now returning to my ARITHMETIC example.
instead of
?- X ( 1 , 2 , 3 )
use:
arith( add , A , B , C ) ) :- ...
arith( sub , A , B , C ) ) :- ...
arith( div , A , B , C ) ) :- ...
now you can call over a variable 'functor'.
?- arith( X , 1 , 2 , 3 )
X = add
This doesn't look as *Expressive* as Lambda abstractions but it works
extremely well.
arith( add , A , B , C ) ) :- C is A + B.
arith( sub , A , B , C ) ) :- C is A - B.
arith( div , A , B , C ) ) :- C is A / B.
1 LINE DEFINITION for each function.
-----------------------------------
INTO A CLASS FUNCTOR
--------------------
If you need to REFERENCE a different parameter in 2.O.L.
then you add a new CLASS member for each parameter position needed.
********
The Process is actually a little more involved...
class( ARG , EXPRESSION ) :- functor(..,...,..., ARG , ... ).
where EXPRESSION is a string of functors you define.
*********
?- arith( X , 1 , 2 , 3 )
X = add
PROLOG> ADD!
Try doing that in C!
----------
Herc
--
www.BLOCKPROLOG.com
the debugging years...
Graham Cooper
May 23, 2013, 9:36:56 PM5/23/13
to
High Order functions are of the form
f g a
= f(g) a
= b(a)
i.e. f outputs a function b and curries a.
------------------------
To do currying with lambda expressions you need
\x.( ... ) a b
--> \y.( ... ) b
i.e. the first lambda outputs another function (lambda expression)
\x.(...)a --> \y.(...)
A High Order lambda expression (function)
-------
My main problem with this is calling LIST processing routines to do
the native Prolog work of variable binding.
Lambda expressions, or simpler currying grammars can be expressed with
fixed arity grammars in horn clauses.
reduced(Y):- lambda( Y , Y , Y ).
\y.(y) y = y
etc.
Depends if these expressions are for coding or the interpreter to
use..
HTH! ;)
Herc
Graham Cooper
May 23, 2013, 10:01:34 PM5/23/13
to
lambda( terms(x,y,T) , EXPRESSION , ARG )
wont have any scope for x&y in expression..
unless all expressions declared their VARS first maybe.
---------------
lambda( terms(x,y,T) , expr(terms(a,b,x,y) , plus(x,y)) , ARG)
OK that wont work too well...
Use single argument lambda and currying should work.
lam( x , plus(x,2) , 4 ) = 6
and the grammar rules are like
exprression( plus(A,B) ) :- ....
-------------------
So PROLOG should be able to do high order functions
with a simplified lambda grammar + currying for
more than 1 arguments.
No List Processing needed!
Herc
--
www.BLoCKPROLOG.com
Jan Burse
May 24, 2013, 5:48:39 AM5/24/13
to
Dear All,
Another challenging conversion example. It will put
properties of a library(lambda) to the test:
1) Aliasing of ground variables across multiple invocations
of a lambda expression.
2) Alpha conversion of bound and local variables for a
single invocation of a lambda expression.
I am now using ('|')/2 instead of (\)/2 for global-by-default,
since this would clash with (\)/1 of local-by-default, and one
could not load both libraries. I have adapted the conversion
routine so that it yields ('|')/2 instead of (\)/2 for
global-by-default. The challenge is the fixpoint combinator.
So in mathematical lambda expressions we would have:
/* currys fixpoint combinator */
Y = F\call(X\call(F,call(X,X)),X\call(F,call(X,X))).
/* checking that something is a natural number */
Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)).
/* computing the factorial */
Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),M is N*J).
I guess property 1) is used to keep and pass around F in the
Y combinator. Further I guess property 2) is used in Nat and
Fact to avoid clashes, when F is reduced.
Here are the results:
local-by-default (output massaged):
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
?- Y = F\call(X\call(F,call(X,X)),X\call(F,call(X,X))),
convert(Y,R).
R = \F^call([F]+\X^call(F, call(X, X)),
[F]+\X^call(F, call(X, X))).
?- Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)), convert(Nat,R).
R = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F, H))).
?- Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),
M is N*J), convert(Fact,R).
R = \F^ ([F]+\N^ ([N, F]+\M^ (N=0, M is 1;N>0, ...is...,
..., ...))).
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Nat = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F,
H))), call(Y,Nat,3).
true.
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Nat = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F,
H))), call(Y,Nat,-1).
false.
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Fact = \F^ ([F]+\N^ ([N, F]+\M^ (N=0,M is 1;
N>0,H is N-1,call(F,H,J),M is N*J))), call(Y,Fact,10,R).
R = 3628800.
global-by-default (output massaged):
Jekejeke Prolog, Development Environment 0.9.9
(c) 1985-2013, XLOG Technologies GmbH, Switzerland
?- Y = F\call(X\call(F,call(X,X)),X\call(F,call(X,X))),
convert(Y,R).
R = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X)))))
?- Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)), convert(Nat,R).
R = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H))))
?- Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),M
is N*J), convert(Fact,R).
R = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H is
N-1,call(F,H,J),M is N*J))))
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(Y,Nat,3).
Yes
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(Y,Nat,-1).
No
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Fact = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H is
N-1,call(F,H,J),M is N*J)))), call(Y,Fact,10,R).
R = 3628800
Both local-by-default and global-by-default pass the test!
The curry fixpoint operator works astonishing well, I guess it
has to do that the inner call/2 is not evaluated call-by-value
in the Prolog setting of call/n.
Interestingly the curry fixpoint combinator based on call/n is
also polymorphic, works for an 1-ary predicate and for a 2-ary
predicate here. Didn't expect that.
Bye
Jan Burse schrieb:
Another challenging conversion example. It will put
properties of a library(lambda) to the test:
1) Aliasing of ground variables across multiple invocations
of a lambda expression.
2) Alpha conversion of bound and local variables for a
single invocation of a lambda expression.
I am now using ('|')/2 instead of (\)/2 for global-by-default,
since this would clash with (\)/1 of local-by-default, and one
could not load both libraries. I have adapted the conversion
routine so that it yields ('|')/2 instead of (\)/2 for
global-by-default. The challenge is the fixpoint combinator.
So in mathematical lambda expressions we would have:
/* currys fixpoint combinator */
Y = F\call(X\call(F,call(X,X)),X\call(F,call(X,X))).
/* checking that something is a natural number */
Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)).
/* computing the factorial */
Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),M is N*J).
I guess property 1) is used to keep and pass around F in the
Y combinator. Further I guess property 2) is used in Nat and
Fact to avoid clashes, when F is reduced.
Here are the results:
local-by-default (output massaged):
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
convert(Y,R).
R = \F^call([F]+\X^call(F, call(X, X)),
[F]+\X^call(F, call(X, X))).
?- Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)), convert(Nat,R).
R = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F, H))).
?- Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),
M is N*J), convert(Fact,R).
R = \F^ ([F]+\N^ ([N, F]+\M^ (N=0, M is 1;N>0, ...is...,
..., ...))).
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Nat = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F,
H))), call(Y,Nat,3).
true.
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Nat = \F^ ([F]+\N^ (N=0;N>0, H is N-1, call(F,
H))), call(Y,Nat,-1).
false.
?- Y = \F^call([F]+\X^call(F, call(X, X)), [F]+\X^call(F,
call(X, X))), Fact = \F^ ([F]+\N^ ([N, F]+\M^ (N=0,M is 1;
N>0,H is N-1,call(F,H,J),M is N*J))), call(Y,Fact,10,R).
R = 3628800.
global-by-default (output massaged):
Jekejeke Prolog, Development Environment 0.9.9
(c) 1985-2013, XLOG Technologies GmbH, Switzerland
convert(Y,R).
R = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X)))))
?- Nat = F\N\H^(N=0;N>0,H is N-1,call(F,H)), convert(Nat,R).
R = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H))))
?- Fact = F\N\M\H^J^(N=0,M is 1;N>0,H is N-1,call(F,H,J),M
is N*J), convert(Fact,R).
R = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H is
N-1,call(F,H,J),M is N*J))))
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(Y,Nat,3).
Yes
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(Y,Nat,-1).
No
?- Y = (F|X^call((X|call(F,call(X,X))),(X|call(F,call(X,X))))),
Fact = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H is
N-1,call(F,H,J),M is N*J)))), call(Y,Fact,10,R).
R = 3628800
Both local-by-default and global-by-default pass the test!
The curry fixpoint operator works astonishing well, I guess it
has to do that the inner call/2 is not evaluated call-by-value
in the Prolog setting of call/n.
Interestingly the curry fixpoint combinator based on call/n is
also polymorphic, works for an 1-ary predicate and for a 2-ary
predicate here. Didn't expect that.
Bye
Jan Burse schrieb:
Jan Burse
May 24, 2013, 7:47:22 AM5/24/13
to
Dear All,
Jan Burse schrieb:
a fixed arity. Indeed when I tried it I had to go along with multiple
definitions for a predicate named fix. Namely for the arity 1 and
2 I was forced to use separate definitions:
fix(F,N) :- call(F,fix(F),N).
fix(F,N,M) :- call(F,fix(F),N,M).
Only then I could run (output massaged):
?- Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(fix,Nat,3).
Yes
?- Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(fix,Nat,-1).
No
?- Fact = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H
is N-1,call(F,H,J),M is N*J)))), call(fix,Fact,10,R).
R = 3628800
That it is impossible to compile Y to a single arity is seen from
the two invocations call(Y,Nat,..) and call(Y,Fact,..,..) in the
uncompiled code. This cannot be satisfied by a compound closure
for Y with a single arity.
I guess this limitation is particular to a library(lambda)
based on the TC2 call/n.
Bye
Jan Burse schrieb:
> Interestingly the curry fixpoint combinator based on call/n is
> also polymorphic, works for an 1-ary predicate and for a 2-ary
> predicate here. Didn't expect that.
Conclusion is that we cannot compile Y into a single predicate with
> also polymorphic, works for an 1-ary predicate and for a 2-ary
> predicate here. Didn't expect that.
a fixed arity. Indeed when I tried it I had to go along with multiple
definitions for a predicate named fix. Namely for the arity 1 and
2 I was forced to use separate definitions:
fix(F,N) :- call(F,fix(F),N).
fix(F,N,M) :- call(F,fix(F),N,M).
Only then I could run (output massaged):
?- Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(fix,Nat,3).
Yes
?- Nat = (F|H^N^(N|H^(N=0;N>0,H is N-1,call(F,H)))),
call(fix,Nat,-1).
No
?- Fact = (F|J^H^M^N^(N|J^H^M^(M|J^H^(N=0,M is 1;N>0,H
is N-1,call(F,H,J),M is N*J)))), call(fix,Fact,10,R).
R = 3628800
That it is impossible to compile Y to a single arity is seen from
the two invocations call(Y,Nat,..) and call(Y,Fact,..,..) in the
uncompiled code. This cannot be satisfied by a compound closure
for Y with a single arity.
I guess this limitation is particular to a library(lambda)
based on the TC2 call/n.
Bye
Graham Cooper
May 24, 2013, 8:59:15 PM5/24/13
to
On May 24, 9:47 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> Dear All,
>
> Jan Burse schrieb:
>
> > Interestingly the curry fixpoint combinator based on call/n is
> > also polymorphic, works for an 1-ary predicate and for a 2-ary
> > predicate here. Didn't expect that.
>
> Conclusion is that we cannot compile Y into a single predicate with
> a fixed arity. Indeed when I tried it I had to go along with multiple
> definitions for a predicate named fix. Namely for the arity 1 and
> 2 I was forced to use separate definitions:
>
> fix(F,N) :- call(F,fix(F),N).
> fix(F,N,M) :- call(F,fix(F),N,M).
>
OK Y(f) = f(Y(f)) = f(f(Y(f)) = f(f(f(Y(f))))
> Dear All,
>
> Jan Burse schrieb:
>
> > Interestingly the curry fixpoint combinator based on call/n is
> > also polymorphic, works for an 1-ary predicate and for a 2-ary
> > predicate here. Didn't expect that.
>
> Conclusion is that we cannot compile Y into a single predicate with
> a fixed arity. Indeed when I tried it I had to go along with multiple
> definitions for a predicate named fix. Namely for the arity 1 and
> 2 I was forced to use separate definitions:
>
> fix(F,N) :- call(F,fix(F),N).
> fix(F,N,M) :- call(F,fix(F),N,M).
>
is usually of theoretical interest to handle recursion,
what is the reasoning behind it's implementation?
Herc
--
www.BLoCKPROLOG.com
pic...@alice.it
May 25, 2013, 5:22:50 AM5/25/13
to
Il giorno giovedì 23 maggio 2013 21:49:48 UTC+2, Ulrich Neumerkel ha scritto:
>
> >
>
> >> >
>
> >>
>
> >> >1) assert(lambda(X, Y) :- Y is X+1).
>
> ( )
>
>
>
> BTW, here, you need extra parentheses.
>
Not necessarily if Body has exactly 1 goal (the problem would be ,/2 not :-/2).
>
> >
>
> >> >
>
> >>
>
> >> >1) assert(lambda(X, Y) :- Y is X+1).
>
> ( )
>
>
>
> BTW, here, you need extra parentheses.
>
>
>
> >> >2) maplist(lambda, [1, 2, 3], List).
>
> >>
>
> >> >3) retract(lambda(_, _)). % or better abolish(lambda/2)
>
> >>
>
> >>
>
> >>
>
> >> This does not work for nested lambdas.
>
> >
>
> >Could you please give me an example of nested lambda?
>
>
>
> In the definition of your lambda, on it's right side, you have
>
> again a maplist with a lambda.
>
>
>
>
>
> ..., maplist(\Xs^Ys^maplist(\X^Y^(Y is X+1),Ys,Xs),Xss,Yss), ...
I am using SWI prolog.
-----
:- use_module(lambda).
mymaplist(Head :- Body, L1, L2) :-
functor(Head, Functor, Arity),
setup_call_cleanup(
assert(Head :- Body),
maplist(Functor, L1, L2),
abolish(Functor/Arity)
).
mymaplist(Closure, L1, L2) :-
maplist(Closure, L1, L2).
:- mymaplist(lambda1(X, Y):-Y is X+1, [1,2,3], Ys), write(Ys), nl.
:- maplist(\X^Y^(Y is X+1), [1,2,3], Ys), write(Ys), nl.
:- mymaplist(lambda2(Xs, Ys) :- mymaplist(lambda1(X, Y):-Y is X+1, Xs, Ys), [[1,2,3],[4,5],[6,7,8]],Yss), write(Yss), nl.
:- maplist(\Xs^Ys^maplist(\X^Y^(Y is X+1),Xs,Ys),[[1,2,3],[4,5],[6,7,8]],Yss), write(Yss), nl.
-------
The output is:
% lambda compiled into lambda 0.00 sec, 27 clauses
[2,3,4]
[2,3,4]
[[2,3,4],[5,6],[7,8,9]]
[[2,3,4],[5,6],[7,8,9]]
% .../prova.pl compiled 0.00 sec, 32 clauses
---
As you see both returns the same result.
It would be interesting if you could find situations in which mymaplist/n would not work.
Thank you very much.
Mauro DiNuzzo
Jan Burse
May 25, 2013, 9:37:21 AM5/25/13
to
Hi,
Graham Cooper schrieb:
desiderata of a library(lambda), which you might find
in real world applications very quickly:
> 1) Aliasing of ground variables across multiple invocations
> of a lambda expression.
>
> 2) Alpha conversion of bound and local variables for a
> single invocation of a lambda expression.
But the post also showed that a third phaenomenom is
involved, namely that lambda expressions can be polymorphic
in their closure index.
You find the closure index in the meta_predicate declarations.
It is part of the meta specifiers. The meaning is as
follows:
0: argument can be called via call/1
1: argument can be called via call/2
2: argument can be called via call/3
Etc..
So a lambda expression need not have a unique closure index,
it can have multiple closure indexes. Y being an example.
But there are already more simple ones, for example in
mathematical notation:
Swap12 = F\X\Y\call(F,Y,X)
The above is also polymorphic. It can have closure index
3, 4, 5, etc.. This can be converted into either local-by-default
or global-by-default.
local-by-default:
?- Swap12 = F\X\Y\call(F,Y,X), convert(Swap12 ,R).
R = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X)))
?- Swap12 = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X))),
call(Swap12,is,1+2,R).
% Swap12 used with closure index 3
R = 3.
?- Swap12 = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X))),
call(Swap12,append,A,B,[1,2,3]).
% Swap12 used with closure index 4
A = [1, 2, 3],
B = [] ;
A = [2, 3],
B = [1] ;
Etc..
global-by-default:
?- Swap12 = F\X\Y\call(F,Y,X), convert(Swap12 ,R).
R = (X|Y^(Y|call(Y,X)))
?- Swap12 = (F|Y^X^(X|Y^(Y|call(F,Y,X)))),
call(Swap12,is,1+2,R).
% Swap12 used with closure index 3
R = 3
?- Swap12 = (F|Y^X^(X|Y^(Y|call(F,Y,X)))),
call(Swap12,append,A,B,[1,2,3]).
% Swap12 used with closure index 4
A = [1,2,3],
B = [] ;
A = [2,3],
B = [1] ;
Etc..
This polymorphism you might also find intentionally or
unintentionally in real world applications. Especially if
you pass around lambda expressions.
You can also extend the capabilities to compose polymorphic
lambda expressions by yourself if you go on and on and
define more polymorphic connectives, aka monads etc..
Bye
Graham Cooper schrieb:
>> fix(F,N) :- call(F,fix(F),N).
>> > fix(F,N,M) :- call(F,fix(F),N,M).
>> >
>
> OK Y(f) = f(Y(f)) = f(f(Y(f)) = f(f(f(Y(f))))
>
> is usually of theoretical interest to handle recursion,
> what is the reasoning behind it's implementation?
I just used it to make a case for the following two
>> > fix(F,N,M) :- call(F,fix(F),N,M).
>> >
>
> OK Y(f) = f(Y(f)) = f(f(Y(f)) = f(f(f(Y(f))))
>
> is usually of theoretical interest to handle recursion,
> what is the reasoning behind it's implementation?
desiderata of a library(lambda), which you might find
in real world applications very quickly:
> 1) Aliasing of ground variables across multiple invocations
> of a lambda expression.
>
> 2) Alpha conversion of bound and local variables for a
> single invocation of a lambda expression.
involved, namely that lambda expressions can be polymorphic
in their closure index.
You find the closure index in the meta_predicate declarations.
It is part of the meta specifiers. The meaning is as
follows:
0: argument can be called via call/1
1: argument can be called via call/2
2: argument can be called via call/3
Etc..
So a lambda expression need not have a unique closure index,
it can have multiple closure indexes. Y being an example.
But there are already more simple ones, for example in
mathematical notation:
Swap12 = F\X\Y\call(F,Y,X)
The above is also polymorphic. It can have closure index
3, 4, 5, etc.. This can be converted into either local-by-default
or global-by-default.
local-by-default:
?- Swap12 = F\X\Y\call(F,Y,X), convert(Swap12 ,R).
R = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X)))
?- Swap12 = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X))),
call(Swap12,is,1+2,R).
% Swap12 used with closure index 3
R = 3.
?- Swap12 = \F^ ([F]+\X^ ([F, X]+\Y^call(F, Y, X))),
call(Swap12,append,A,B,[1,2,3]).
% Swap12 used with closure index 4
A = [1, 2, 3],
B = [] ;
A = [2, 3],
B = [1] ;
Etc..
global-by-default:
?- Swap12 = F\X\Y\call(F,Y,X), convert(Swap12 ,R).
R = (X|Y^(Y|call(Y,X)))
?- Swap12 = (F|Y^X^(X|Y^(Y|call(F,Y,X)))),
call(Swap12,is,1+2,R).
% Swap12 used with closure index 3
R = 3
?- Swap12 = (F|Y^X^(X|Y^(Y|call(F,Y,X)))),
call(Swap12,append,A,B,[1,2,3]).
% Swap12 used with closure index 4
A = [1,2,3],
B = [] ;
A = [2,3],
B = [1] ;
Etc..
This polymorphism you might also find intentionally or
unintentionally in real world applications. Especially if
you pass around lambda expressions.
You can also extend the capabilities to compose polymorphic
lambda expressions by yourself if you go on and on and
define more polymorphic connectives, aka monads etc..
Bye
Jan Burse
May 25, 2013, 9:50:13 AM5/25/13
to
pic...@alice.it schrieb:
any definition of map/3 etc.. These are all unchanged.
Instead it adds lambda expressions which can then
be passed to the unchanged map/3 etc.. definitions.
If you change map/3 etc.. you have one advantage.
These have all meta_predicate declarations, for
example you find:
:- meta_predicate map(2,?,?).
So you know the closure index of the lambda expression
you want compile. Actually the (:-)/2 syntax you use
doesn't say much about the closure index, it is found
in the head of (:-)/2.
Pray that it matches the call-site and that you
don't want to pass around a polymorphic closure.
You could also use a variant of Ulrich Neumerkl's
library and replace his (\)/1 and (^)/2 by your
(:-)/2. The result would be:
:-(Head,Body,X1) :- Head =.. [_,Arg1],
copy_term(rec(Arg1,Body),rec(X1,Goal)),
Goal.
:-(Head,Body,X1,X2) :- Head =.. [_,Arg1,Arg2],
copy_term(rec(Arg1,Arg2,Body),rec(X1,X2,Goal)),
Goal.
Etc..
Eh voila we have one more variant of a local-by-default
library(lambda), but which has no extra binder for
globals, nevertheless works fine where this is not
needed:
?- map((lambda(X,Y) :- Y is X+1),[1,2,3],R).
R = [2, 3, 4]
Bye
> As you see both returns the same result.
> It would be interesting if you could find situations in which mymaplist/n would not work.
The problem here is that a library(lambda) doesn't touch
> It would be interesting if you could find situations in which mymaplist/n would not work.
any definition of map/3 etc.. These are all unchanged.
Instead it adds lambda expressions which can then
be passed to the unchanged map/3 etc.. definitions.
If you change map/3 etc.. you have one advantage.
These have all meta_predicate declarations, for
example you find:
:- meta_predicate map(2,?,?).
So you know the closure index of the lambda expression
you want compile. Actually the (:-)/2 syntax you use
doesn't say much about the closure index, it is found
in the head of (:-)/2.
Pray that it matches the call-site and that you
don't want to pass around a polymorphic closure.
You could also use a variant of Ulrich Neumerkl's
library and replace his (\)/1 and (^)/2 by your
(:-)/2. The result would be:
:-(Head,Body,X1) :- Head =.. [_,Arg1],
copy_term(rec(Arg1,Body),rec(X1,Goal)),
Goal.
:-(Head,Body,X1,X2) :- Head =.. [_,Arg1,Arg2],
copy_term(rec(Arg1,Arg2,Body),rec(X1,X2,Goal)),
Goal.
Etc..
Eh voila we have one more variant of a local-by-default
library(lambda), but which has no extra binder for
globals, nevertheless works fine where this is not
needed:
?- map((lambda(X,Y) :- Y is X+1),[1,2,3],R).
R = [2, 3, 4]
Bye
Ulrich Neumerkel
May 25, 2013, 6:53:37 PM5/25/13
to
pic...@alice.it writes:
Try it out with an ISO-conforming system like GNU. There is only
a single system accepting this invalid syntax, see:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
As a consequence, there are also many other differences.
>Il giorno gioved=EC 23 maggio 2013 21:49:48 UTC+2, Ulrich Neumerkel ha scritto:
>> >> >1) assert(lambda(X, Y) :- Y is X+1).
>> ( )
>> BTW, here, you need extra parentheses.
>Not necessarily if Body has exactly 1 goal (the problem would be ,/2 not :-/2).
Above goal is invalid syntax, even if the system you use accepts it.
>> >> >1) assert(lambda(X, Y) :- Y is X+1).
>> ( )
>> BTW, here, you need extra parentheses.
>Not necessarily if Body has exactly 1 goal (the problem would be ,/2 not :-/2).
Try it out with an ISO-conforming system like GNU. There is only
a single system accepting this invalid syntax, see:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
As a consequence, there are also many other differences.
pic...@alice.it
May 26, 2013, 4:26:00 AM5/26/13
to
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>
Wow! Very interesting.
Sorry but I was not aware of your effort in Prolog standardization. Do you think Prolog systems are trying to comply with "strict" ISO? If not, why not?
If I understood correctly from your graphs, SICStus is the best among commercial and GNU among free systems, isn't it?
Thank you.
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>
Wow! Very interesting.
Sorry but I was not aware of your effort in Prolog standardization. Do you think Prolog systems are trying to comply with "strict" ISO? If not, why not?
If I understood correctly from your graphs, SICStus is the best among commercial and GNU among free systems, isn't it?
Thank you.
Jan Burse
May 26, 2013, 4:50:21 AM5/26/13
to
Ulrich Neumerkel schrieb:
Prolog parser is tolerant or not:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
?- X = var(p :- q).
X = var((p:-q)).
?- set_prolog_flag(iso,true).
?- X = var(p :- q).
ERROR: Syntax error: Unbalanced operator
ERROR: X = var(p :- q
ERROR: ** here **
ERROR: ) .
Don't you assume the flag being set in your test cases?
Bye
> Try it out with an ISO-conforming system like GNU. There is only
> a single system accepting this invalid syntax, see:
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>
> As a consequence, there are also many other differences.
It seems to be dependent on a flag, wherher the SWI
> a single system accepting this invalid syntax, see:
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>
> As a consequence, there are also many other differences.
Prolog parser is tolerant or not:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.3.15)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
X = var((p:-q)).
?- set_prolog_flag(iso,true).
?- X = var(p :- q).
ERROR: Syntax error: Unbalanced operator
ERROR: X = var(p :- q
ERROR: ** here **
ERROR: ) .
Don't you assume the flag being set in your test cases?
Bye
Jan Burse
May 26, 2013, 4:52:32 AM5/26/13
to
Jan Burse schrieb:
Syntax is closer to the ISO standard:
Unquoted commas and bars appearing as atoms are not allowed.
Instead of f(,,a) now write f(',',a). Unquoted commas can only be used
to separate arguments in functional notation and list notation, and as a
conjunction operator. Unquoted bars can only appear within lists to
separate head and tail, like [Head|Tail], and as infix operator for
alternation in grammar rules, like a --> b | c.
Within functional notation and list notation terms must have
priority below 1000. That means that rules and control constructs
appearing as arguments need bracketing. A term like [a :- b, c]. must
now be disambiguated to mean [(a :- b), c]. or [(a :- b, c)].
Operators appearing as operands must be bracketed. Instead of X ==
-, true. write X == (-), true. Currently, this is not entirely enforced.
Backslash-escaped newlines are interpreted according to the ISO
standard. See section 2.15.1.2.
http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%272.11%27,swi%28%27/doc/Manual/flags.html%27%29%29
> ?- set_prolog_flag(iso,true).
>
> ?- X = var(p :- q).
> ERROR: Syntax error: Unbalanced operator
> ERROR: X = var(p :- q
> ERROR: ** here **
> ERROR: ) .
>
> Don't you assume the flag being set in your test cases?
From the SWI documentation:
>
> ?- X = var(p :- q).
> ERROR: Syntax error: Unbalanced operator
> ERROR: X = var(p :- q
> ERROR: ** here **
> ERROR: ) .
>
> Don't you assume the flag being set in your test cases?
Syntax is closer to the ISO standard:
Unquoted commas and bars appearing as atoms are not allowed.
Instead of f(,,a) now write f(',',a). Unquoted commas can only be used
to separate arguments in functional notation and list notation, and as a
conjunction operator. Unquoted bars can only appear within lists to
separate head and tail, like [Head|Tail], and as infix operator for
alternation in grammar rules, like a --> b | c.
Within functional notation and list notation terms must have
priority below 1000. That means that rules and control constructs
appearing as arguments need bracketing. A term like [a :- b, c]. must
now be disambiguated to mean [(a :- b), c]. or [(a :- b, c)].
Operators appearing as operands must be bracketed. Instead of X ==
-, true. write X == (-), true. Currently, this is not entirely enforced.
Backslash-escaped newlines are interpreted according to the ISO
standard. See section 2.15.1.2.
http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%272.11%27,swi%28%27/doc/Manual/flags.html%27%29%29
Ulrich Neumerkel
May 26, 2013, 10:12:59 AM5/26/13
to
Jan Burse <janb...@fastmail.fm> writes:
>Ulrich Neumerkel schrieb:
>> Try it out with an ISO-conforming system like GNU. There is only
>> a single system accepting this invalid syntax, see:
>>
>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>>
>> As a consequence, there are also many other differences.
>
>It seems to be dependent on a flag, wherher the SWI
>Prolog parser is tolerant or not:
...
>Ulrich Neumerkel schrieb:
>> Try it out with an ISO-conforming system like GNU. There is only
>> a single system accepting this invalid syntax, see:
>>
>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>>
>> As a consequence, there are also many other differences.
>
>It seems to be dependent on a flag, wherher the SWI
>Prolog parser is tolerant or not:
>Don't you assume the flag being set in your test cases?
In above comparison, Prologs are called with unchanged flag
values ("default values"). Setting flags differently may be
of interest for testing strict conformance (5.1 e), but
prior to that "regular" conformance is important.
Ulrich Neumerkel
May 26, 2013, 10:28:20 AM5/26/13
to
pic...@alice.it writes:
>>
>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>>
...
a bit of an idea. BTW, also the standard itself moved here!
>If I understood correctly from your graphs, SICStus is the best among commercial and GNU among free systems, isn't it?
IF and B are very close too, the numerical value itself is a rough indicator.
>>
>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#75
>>
...
>Do you think Prolog systems are trying to comply with "strict" ISO? If not, why not?
You can answer this by looking at the line "recent improvements" which gives you
a bit of an idea. BTW, also the standard itself moved here!
>If I understood correctly from your graphs, SICStus is the best among commercial and GNU among free systems, isn't it?
Jan Burse
May 26, 2013, 12:30:53 PM5/26/13
to
Ulrich Neumerkel schrieb:
? X = 1 000 000.
X = 1000000.
?- set_prolog_flag(iso,on).
true.
?- X = 1 000 000.
X = 1000000.
You could add a new test case to your conformity assessment.
>> It seems to be dependent on a flag, wherher the SWI
>> >Prolog parser is tolerant or not:
> ...
>> >Don't you assume the flag being set in your test cases?
> In above comparison, Prologs are called with unchanged flag
> values ("default values"). Setting flags differently may be
> of interest for testing strict conformance (5.1 e), but
> prior to that "regular" conformance is important.
>
The flag is anyway only doing a few things. For example I get:
>> >Prolog parser is tolerant or not:
> ...
>> >Don't you assume the flag being set in your test cases?
> In above comparison, Prologs are called with unchanged flag
> values ("default values"). Setting flags differently may be
> of interest for testing strict conformance (5.1 e), but
> prior to that "regular" conformance is important.
>
? X = 1 000 000.
X = 1000000.
?- set_prolog_flag(iso,on).
true.
?- X = 1 000 000.
X = 1000000.
You could add a new test case to your conformity assessment.
Ulrich Neumerkel
May 26, 2013, 1:26:12 PM5/26/13
to
current syntax to permit to represent integers in
lines with a fixed number of characters. See for details:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#bignum
Jan Burse
May 26, 2013, 4:05:47 PM5/26/13
to
Hi,
Ulrich Neumerkel schrieb:
are in the scope of it. It says "Typographic conventions",
so I guess it is for printed matter and the like.
Otherwise I would come up with the wish that I could
write X is a⋅b, or X is a×b, and not only X is a*b.
Just to keep the Prolog ISO core committee busy.
Bye
Ulrich Neumerkel schrieb:
> This one has been discussed as a possible extension to
> current syntax to permit to represent integers in
> lines with a fixed number of characters. See for details:
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#bignum
>
Concerning ISO_31-0, I don't think programming languages
> current syntax to permit to represent integers in
> lines with a fixed number of characters. See for details:
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#bignum
>
are in the scope of it. It says "Typographic conventions",
so I guess it is for printed matter and the like.
Otherwise I would come up with the wish that I could
write X is a⋅b, or X is a×b, and not only X is a*b.
Just to keep the Prolog ISO core committee busy.
Bye
Jan Burse
May 26, 2013, 4:27:25 PM5/26/13
to
But anyhow, the space helps in breaking long lines.
No, it doesn't:
?- X = 1 000 000.
X = 1000000.
?- X = 1 000
| 000.
ERROR: Syntax error: Operator expected
ERROR: X = 1 000
ERROR: ** here **
ERROR: 000 .
Jan Burse schrieb:
No, it doesn't:
?- X = 1 000 000.
X = 1000000.
?- X = 1 000
| 000.
ERROR: X = 1 000
ERROR: ** here **
ERROR: 000 .
Jan Burse schrieb:
Ulrich Neumerkel
May 27, 2013, 6:54:30 AM5/27/13
to
Jan Burse <janb...@fastmail.fm> writes:
>But anyhow, the space helps in breaking long lines.
>
>No, it doesn't:
>
>?- X = 1 000 000.
>X = 1000000.
>
>?- X = 1 000
>| 000.
>ERROR: Syntax error: Operator expected
>ERROR: X = 1 000
>
>ERROR: ** here **
>ERROR: 000 .
Space is limited to exactly one occurrence.
>But anyhow, the space helps in breaking long lines.
>
>No, it doesn't:
>
>?- X = 1 000 000.
>X = 1000000.
>
>?- X = 1 000
>| 000.
>ERROR: Syntax error: Operator expected
>ERROR: X = 1 000
>
>ERROR: ** here **
>ERROR: 000 .
Your extension would require infinite lookahead.
If you want this, you have to write
1 000_ /* comments */ % more comments
000.
See the grammar given here:
>>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/#bignum
Jan Burse
May 27, 2013, 8:38:18 AM5/27/13
to
Ulrich Neumerkel schrieb:
operator there is no conflict, you just read your
number token, and then the next token as well (you do
this anyway to check for infix operators etc..) and
if the next token is a number token again, you
concatenate the stuff. This allows arbitrary layout
to break a number into pieces.
But already the one space syntax is in conflict
with Prolog extensions, such as lambda Prolog, where
juxtaposition is an operator, i.e the lambda calculus
application operator.
Bye
> Space is limited to exactly one occurrence.
>
> Your extension would require infinite lookahead.
Not really, since juxtaposition in Prolog is not an
>
> Your extension would require infinite lookahead.
operator there is no conflict, you just read your
number token, and then the next token as well (you do
this anyway to check for infix operators etc..) and
if the next token is a number token again, you
concatenate the stuff. This allows arbitrary layout
to break a number into pieces.
But already the one space syntax is in conflict
with Prolog extensions, such as lambda Prolog, where
juxtaposition is an operator, i.e the lambda calculus
application operator.
Bye
Jan Burse
May 27, 2013, 8:41:26 AM5/27/13
to
Jan Burse schrieb:
"-" in some Prolog systems. To detect "-" {layout
|comments} number, you also don't need infinite
lookahead (whatever this means!?). You handle this
in the parser based on the tokens you receive from
the scanner. Right?
> Ulrich Neumerkel schrieb:
>> Space is limited to exactly one occurrence.
>>
>> Your extension would require infinite lookahead.
>
> Not really, since juxtaposition in Prolog is not an
Its the same like you deal with the minus sign
>> Space is limited to exactly one occurrence.
>>
>> Your extension would require infinite lookahead.
>
> Not really, since juxtaposition in Prolog is not an
"-" in some Prolog systems. To detect "-" {layout
|comments} number, you also don't need infinite
lookahead (whatever this means!?). You handle this
in the parser based on the tokens you receive from
the scanner. Right?
Jan Burse
May 27, 2013, 8:56:25 AM5/27/13
to
Jan Burse schrieb:
scanner to give you the number tokens unmassaged.
So that leading zeros are not stripped, otherwise
your concatenation will give wrong results.
> Not really, since juxtaposition in Prolog is not an
> operator there is no conflict, you just read your
> number token, and then the next token as well (you do
> this anyway to check for infix operators etc..) and
> if the next token is a number token again, you
> concatenate the stuff. This allows arbitrary layout
> to break a number into pieces.
There is a little twist, you must instruct the
> operator there is no conflict, you just read your
> number token, and then the next token as well (you do
> this anyway to check for infix operators etc..) and
> if the next token is a number token again, you
> concatenate the stuff. This allows arbitrary layout
> to break a number into pieces.
scanner to give you the number tokens unmassaged.
So that leading zeros are not stripped, otherwise
your concatenation will give wrong results.
Ulrich Neumerkel
May 27, 2013, 10:22:19 AM5/27/13
to
the current definition, you know for sure that this is the
integer(123). With your extended definition you would have to
continue looking for the next token.
This is not so much about a concrete implementation. But about
the inherent overheads.
Tokens are defined in (* 6.4 *). The characters -1 are two
tokens, not one. However, a signfree integer is one token, at
least by the current definition.
Reading is defined as reading a term token wise up to an end
token (* 6.4.8 *). That is, should there be a sequence that
does fit into term (* 6.4 *), a syntax error must be produced.
Cases where implementations might disagree with this:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#3
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#24
Jan Burse
May 27, 2013, 11:27:14 AM5/27/13
to
Hi,
Ulrich Neumerkel schrieb:
a scanner (something defined by Lex for example),
and a parser (something define by Yacc for example)?
Then there is no overhead. You anyway look on the
parser level for the next token. You don't do
it on the scanner level.
For example when you parse the following:
1 + 2
You will be looking at the token '+' after you have
parsed the token '1'. But when you scan the token
'1', you usually stop at the space until the parser
asks the scanner for the next token.
So there is zero overhead in changing the parser
to accept for example:
?- X = 1 000 000.
X = 1000000.
Or:
?- X = 1 000
000.
X = 1000000.
You would not change the scanner, but only change
the parser. I pretty much sure about that, and would
offer you a swiss chocolate if it is impossible.
Well a minor change to the scanner is necessary,
you need to modify the scanner a little bit so that
it returns '000' when scanning '000' and not '0'.
Otherwise the concatenation would not work.
But for example the modification of the scanner
is not necessary in the Jekejeke Prolog scanner,
since it anyway returns all tokens as strings, and
postpones the number conversion.
Bye
P.S.: You wrote:
> Tokens are defined in (* 6.4 *). The characters -1 are two
> tokens, not one. However, a signfree integer is one token, at
> least by the current definition.
This invariant would go down the drain. Maybe with
some implication for predicates such as number_codes/2
etc.. Dunno.
Here is what SWI-Prolog already does:
?- number_codes(1000000,X).
X = [49, 48, 48, 48, 48, 48, 48].
?- number_codes(X,"1 000 000").
X = 1000000.
?- number_codes(X,"1 000\n000").
ERROR: number_chars/2: Syntax error: no_error
Not sure what no_error should mean...
Ulrich Neumerkel schrieb:
> This is not so much about a concrete implementation. But about
> the inherent overheads.
Can we agree that reading a Prolog text involves
> the inherent overheads.
a scanner (something defined by Lex for example),
and a parser (something define by Yacc for example)?
Then there is no overhead. You anyway look on the
parser level for the next token. You don't do
it on the scanner level.
For example when you parse the following:
1 + 2
You will be looking at the token '+' after you have
parsed the token '1'. But when you scan the token
'1', you usually stop at the space until the parser
asks the scanner for the next token.
So there is zero overhead in changing the parser
to accept for example:
?- X = 1 000 000.
X = 1000000.
?- X = 1 000
000.
X = 1000000.
the parser. I pretty much sure about that, and would
offer you a swiss chocolate if it is impossible.
Well a minor change to the scanner is necessary,
you need to modify the scanner a little bit so that
it returns '000' when scanning '000' and not '0'.
Otherwise the concatenation would not work.
But for example the modification of the scanner
is not necessary in the Jekejeke Prolog scanner,
since it anyway returns all tokens as strings, and
postpones the number conversion.
Bye
P.S.: You wrote:
> Tokens are defined in (* 6.4 *). The characters -1 are two
> tokens, not one. However, a signfree integer is one token, at
> least by the current definition.
some implication for predicates such as number_codes/2
etc.. Dunno.
Here is what SWI-Prolog already does:
?- number_codes(1000000,X).
X = [49, 48, 48, 48, 48, 48, 48].
?- number_codes(X,"1 000 000").
X = 1000000.
?- number_codes(X,"1 000\n000").
ERROR: number_chars/2: Syntax error: no_error
Not sure what no_error should mean...
Jan Burse
May 27, 2013, 11:31:52 AM5/27/13
to
Ulrich Neumerkel schrieb:
know about predicates like read_term/2 that wait for a
terminating period.
But I like your observation, yes allowing a newline inside
numbers, without a leading underscore, changes any read
predicate which doesn't await a terminating period.
Oki Doki
> Consider you are reading a Prolog text containing "123 ". With
> the current definition, you know for sure that this is the
> integer(123). With your extended definition you would have to
> continue looking for the next token.
What predicates in ISO can do a read of a token? I only
> the current definition, you know for sure that this is the
> integer(123). With your extended definition you would have to
> continue looking for the next token.
know about predicates like read_term/2 that wait for a
terminating period.
But I like your observation, yes allowing a newline inside
numbers, without a leading underscore, changes any read
predicate which doesn't await a terminating period.
Oki Doki
Ulrich Neumerkel
May 27, 2013, 11:42:38 AM5/27/13
to
Jan Burse <janb...@fastmail.fm> writes:
>Hi,
>
>Ulrich Neumerkel schrieb:
>> This is not so much about a concrete implementation. But about
>> the inherent overheads.
>
>Can we agree that reading a Prolog text involves
>a scanner (something defined by Lex for example),
>and a parser (something define by Yacc for example)?
According to 8.14.1.1 we have tokens, and the read-term.
>Hi,
>
>Ulrich Neumerkel schrieb:
>> This is not so much about a concrete implementation. But about
>> the inherent overheads.
>
>Can we agree that reading a Prolog text involves
>a scanner (something defined by Lex for example),
>and a parser (something define by Yacc for example)?
>Then there is no overhead. You anyway look on the
>parser level for the next token. You don't do
>it on the scanner level.
>
>For example when you parse the following:
>
> 1 + 2
>
>You will be looking at the token '+' after you have
>parsed the token '1'. But when you scan the token
>'1', you usually stop at the space until the parser
>asks the scanner for the next token.
Parsing according to 8.14.1.1 is: get a sequence
of characters which contain tokens up to the point
when you get the end token. Then, parse that
sequence of characters as a read-term. So there is
a tokenization phase but it does not create tokens.
Also Jekejeke does it that way:
Enter the text
)
)
)
.
Jekejeke continues to read, until it gets .
So it first tokenizes, and then parses. Or at least
this is my conclusion. Where am I wrong here?
>So there is zero overhead in changing the parser
>to accept for example:
entire term which ends with . But otherwise,
when reading a single token, there is the overhead
since you have to look ahead. You have to read
more text (= more overhead).
>You would not change the scanner, but only change
>the parser. I pretty much sure about that, and would
>offer you a swiss chocolate if it is impossible.
>
>Well a minor change to the scanner is necessary,
>you need to modify the scanner a little bit so that
>it returns '000' when scanning '000' and not '0'.
>Otherwise the concatenation would not work.
data.
>> Tokens are defined in (* 6.4 *). The characters -1 are two
>> tokens, not one. However, a signfree integer is one token, at
>> least by the current definition.
>
>This invariant would go down the drain. Maybe with
>some implication for predicates such as number_codes/2
>etc.. Dunno.
>
>Here is what SWI-Prolog already does:
>
> ?- number_codes(1000000,X).
> X = [49, 48, 48, 48, 48, 48, 48].
>
> ?- number_codes(X,"1 000 000").
> X = 1000000.
>
> ?- number_codes(X,"1 000\n000").
> ERROR: number_chars/2: Syntax error: no_error
>
>Not sure what no_error should mean...
Jan Burse
May 27, 2013, 2:43:27 PM5/27/13
to
Ulrich Neumerkel schrieb:
line. The problem is that the line might contain
errorneous tokens. So the syntax for lines is slightly
broader than the syntax for token sequences.
It actually uses a state machine to parse the line
up to the period. And keeps it as a string. It then
resets the position to zero, and starts the parsing.
The parser will invoke the scanner, which delivers
the tokens one by one each time it is called by
the parser from the string.
The scanner is not anymore 1-character lookahead,
it has the full line in the form of a string in
front of it. But the original state machine, since
it might work on a stream, is 1-character lookahead.
There is a devision of labour between the state
machine and the scanner. Although the state machine
uses a slightly broader syntax than the scanner,
it can also emit certain errors. Namely the state
machine already detects errors connected with EOF
and the terminating period, and the precence of at
least one token. But the goal is to parse as much
as possible, so that illegal tokens don't stop the
flow of lines:
end_of_clause
end_of_file
The scanner then detects errors concerning the
integrity of tokens, but doesn't do any conversion
what ever. Namely the following errors can be
generated:
end_of_file_in_block_comment /* in /*...*/ notation */
end_of_file_in_name /* in '...' notation */
end_of_file_in_variable /* in `...` notation */
end_of_file_in_string /* in "..." notation */
end_of_file_in_character /* in 0'... notation */
The parser then generates part of the rest of
the errors during parsing. Namely we find the
following errors that the parser can generate:
illegal_number
parenthesis_balance
cannot_start_term
end_of_clause_expected
brace_balance
bracket_balance
operator_clash
ref_not_readable
There is also a plug-in architecture in place.
The state-machine, the scanner and the parser
use a delegate, which is responsible for the
character classification. Unicode is realized
as such a plug-in. But it is also possible to
support other processor character sets, by just
plugging in a delegate. The delegate is also
responsible for converting escape sequences in
strings, therefore it generates it own set of
errors. Namely we find:
doubling_missing
illegal_escape
illegal_eol
illegal_layout
illegal_unicode
The ISO standard doesn't help in developing the
error codes for the state-machine, the scanner, the
parser and the plug-in. Since the ISO standard leaves
the error codes open. Where possible I tryed to use
error codes that are already found in SWI-Prolog.
But there might be differences between the two system
when exactly which errors is emitted.
Implementing the new number syntax would not generate
some overhead, since I would handle it in the parser,
supposedly it is the syntax with {layout|comment} between
number blocks. If it is the syntax with blank between
number blocks, I would adapt the state-machine and the
scanner, and the parser would be untouched. But the later
would also not incure some overhead, since the changes
in the state-machine usually don't incure some overhead,
and the lookahead of the scanner is neglible.
Bye
> Jekejeke continues to read, until it gets .
> So it first tokenizes, and then parses. Or at least
> this is my conclusion. Where am I wrong here?
Actually it doesn't tokenize when it detects the
> So it first tokenizes, and then parses. Or at least
> this is my conclusion. Where am I wrong here?
line. The problem is that the line might contain
errorneous tokens. So the syntax for lines is slightly
broader than the syntax for token sequences.
It actually uses a state machine to parse the line
up to the period. And keeps it as a string. It then
resets the position to zero, and starts the parsing.
The parser will invoke the scanner, which delivers
the tokens one by one each time it is called by
the parser from the string.
The scanner is not anymore 1-character lookahead,
it has the full line in the form of a string in
front of it. But the original state machine, since
it might work on a stream, is 1-character lookahead.
There is a devision of labour between the state
machine and the scanner. Although the state machine
uses a slightly broader syntax than the scanner,
it can also emit certain errors. Namely the state
machine already detects errors connected with EOF
and the terminating period, and the precence of at
least one token. But the goal is to parse as much
as possible, so that illegal tokens don't stop the
flow of lines:
end_of_clause
end_of_file
The scanner then detects errors concerning the
integrity of tokens, but doesn't do any conversion
what ever. Namely the following errors can be
generated:
end_of_file_in_block_comment /* in /*...*/ notation */
end_of_file_in_name /* in '...' notation */
end_of_file_in_variable /* in `...` notation */
end_of_file_in_string /* in "..." notation */
end_of_file_in_character /* in 0'... notation */
The parser then generates part of the rest of
the errors during parsing. Namely we find the
following errors that the parser can generate:
illegal_number
parenthesis_balance
cannot_start_term
end_of_clause_expected
brace_balance
bracket_balance
operator_clash
ref_not_readable
There is also a plug-in architecture in place.
The state-machine, the scanner and the parser
use a delegate, which is responsible for the
character classification. Unicode is realized
as such a plug-in. But it is also possible to
support other processor character sets, by just
plugging in a delegate. The delegate is also
responsible for converting escape sequences in
strings, therefore it generates it own set of
errors. Namely we find:
doubling_missing
illegal_escape
illegal_eol
illegal_layout
illegal_unicode
The ISO standard doesn't help in developing the
error codes for the state-machine, the scanner, the
parser and the plug-in. Since the ISO standard leaves
the error codes open. Where possible I tryed to use
error codes that are already found in SWI-Prolog.
But there might be differences between the two system
when exactly which errors is emitted.
Implementing the new number syntax would not generate
some overhead, since I would handle it in the parser,
supposedly it is the syntax with {layout|comment} between
number blocks. If it is the syntax with blank between
number blocks, I would adapt the state-machine and the
scanner, and the parser would be untouched. But the later
would also not incure some overhead, since the changes
in the state-machine usually don't incure some overhead,
and the lookahead of the scanner is neglible.
Bye
Jan Burse
May 27, 2013, 3:16:51 PM5/27/13
to
Jan Burse schrieb:
since the state machine works on character
classes. But here and then some codes are hard
coded, for example the period. We are still working
on it, to make it 100% plugable.
There are also some subtle assumptions involved, for
example the block comment characters need to be of class
graphic character and the line comment character needs
to be of class solo graphic character.
We are also using the plug-in and state-machine for
other languages, which have other comment conventions.
And there is another state-machine that can handle
XML based on the plug-in. There is a lot of code reuse
in the end and small libraries.
:-)
> character classification. Unicode is realized
> as such a plug-in. But it is also possible to
> support other processor character sets, by just
> plugging in a delegate. The delegate is also
The plugability of the state machine is possible
> as such a plug-in. But it is also possible to
> support other processor character sets, by just
> plugging in a delegate. The delegate is also
since the state machine works on character
classes. But here and then some codes are hard
coded, for example the period. We are still working
on it, to make it 100% plugable.
There are also some subtle assumptions involved, for
example the block comment characters need to be of class
graphic character and the line comment character needs
to be of class solo graphic character.
We are also using the plug-in and state-machine for
other languages, which have other comment conventions.
And there is another state-machine that can handle
XML based on the plug-in. There is a lot of code reuse
in the end and small libraries.
:-)
Ulrich Neumerkel
May 27, 2013, 3:38:39 PM5/27/13
to
Jan Burse <janb...@fastmail.fm> writes:
>Ulrich Neumerkel schrieb:
>> Jekejeke continues to read, until it gets .
>> So it first tokenizes, and then parses. Or at least
>> this is my conclusion. Where am I wrong here?
>
>Actually it doesn't tokenize when it detects the
>line. The problem is that the line might contain
>errorneous tokens. So the syntax for lines is slightly
>broader than the syntax for token sequences.
There are only a few tokenizer-errors, and it seems you
>Ulrich Neumerkel schrieb:
>> Jekejeke continues to read, until it gets .
>> So it first tokenizes, and then parses. Or at least
>> this is my conclusion. Where am I wrong here?
>
>Actually it doesn't tokenize when it detects the
>line. The problem is that the line might contain
>errorneous tokens. So the syntax for lines is slightly
>broader than the syntax for token sequences.
find them. Like
'
Where you promptly produce an error
Jan Burse
May 27, 2013, 4:11:03 PM5/27/13
to
Ulrich Neumerkel schrieb:
No, the error is not promptly produced. It is only
produce when the string is closed and later a termination
point is encountered, or when the end of file is reached.
You know from your assessment which Prolog systems
behave like that and which Prolog systems don't
behave like that. Seems like you are prentending
to be stupid.
But you can get out of the input of a read-term, be it
from your application program or during the top-level
by issuing an abort. Either in the GUI or via ^C and
a in the terminal.
The abort is the recommended way to get out an input
in Jekejeke Prolog. For application it can be catched
with sys_trap/3 and in the top level it doesn't lead
to an exit, but to a new read-term and continuation of
the top-level.
Bye
produce when the string is closed and later a termination
point is encountered, or when the end of file is reached.
You know from your assessment which Prolog systems
behave like that and which Prolog systems don't
behave like that. Seems like you are prentending
to be stupid.
But you can get out of the input of a read-term, be it
from your application program or during the top-level
by issuing an abort. Either in the GUI or via ^C and
a in the terminal.
The abort is the recommended way to get out an input
in Jekejeke Prolog. For application it can be catched
with sys_trap/3 and in the top level it doesn't lead
to an exit, but to a new read-term and continuation of
the top-level.
Bye
Jan Burse
May 27, 2013, 4:18:10 PM5/27/13
to
Jan Burse schrieb:
to produce an error message, that contains the verbatim
text of the input. I didn't wanted to show the error
by listing the parsed tokens. I wanted to show the error
in the input as a string. This is to show more precisely
for example errors inside tokens, such as string escape
errors etc..
But there are other designs possible. For example the
scanner and the state machine could be connected by
a small buffer that will maximally have the size of
the lookahead of the scanner. And the state machine
could be lazly called by the scanner.
Or the scanner and the state machine could be connected
via chunking mechanism. I am using this for the XML
parser. The XML parser delivers text in chunks which have
a maximal size. So that I can bound the buffer that is
needed for the statemachine.
Further there is a complication. The stream is not directly
accessed. There is another state machine, different from
the state machine for Prolog tokens, sitting on the
stream, which creates the illusion of a stream that consists
only of \n separeted lines independent of the mac, windows
and linux line separator conventions. But this state machine
is out of the box from Java:
http://docs.oracle.com/javase/7/docs/api/java/io/LineNumberReader.html
> It actually uses a state machine to parse the line
> up to the period. And keeps it as a string. It then
> resets the position to zero, and starts the parsing.
> The parser will invoke the scanner, which delivers
> the tokens one by one each time it is called by
> the parser from the string.
The main reason for the above design, is to be able
> up to the period. And keeps it as a string. It then
> resets the position to zero, and starts the parsing.
> The parser will invoke the scanner, which delivers
> the tokens one by one each time it is called by
> the parser from the string.
to produce an error message, that contains the verbatim
text of the input. I didn't wanted to show the error
by listing the parsed tokens. I wanted to show the error
in the input as a string. This is to show more precisely
for example errors inside tokens, such as string escape
errors etc..
But there are other designs possible. For example the
scanner and the state machine could be connected by
a small buffer that will maximally have the size of
the lookahead of the scanner. And the state machine
could be lazly called by the scanner.
Or the scanner and the state machine could be connected
via chunking mechanism. I am using this for the XML
parser. The XML parser delivers text in chunks which have
a maximal size. So that I can bound the buffer that is
needed for the statemachine.
Further there is a complication. The stream is not directly
accessed. There is another state machine, different from
the state machine for Prolog tokens, sitting on the
stream, which creates the illusion of a stream that consists
only of \n separeted lines independent of the mac, windows
and linux line separator conventions. But this state machine
is out of the box from Java:
http://docs.oracle.com/javase/7/docs/api/java/io/LineNumberReader.html
Jan Burse
May 27, 2013, 4:38:47 PM5/27/13
to
Jan Burse schrieb:
try it since release 0.9.6 or so. It will work as
follows:
?- '
Error: Illegal end of line in string.
'
^
It is done by the state-machine, which stops reading
the line. But the state-machine will not issue an
error. It is the scanner that will produce the error.
This was a requested by you Ulrich Neumerkel.
Bye
> No, the error is not promptly produced. It is only
> produce when the string is closed and later a termination
> point is encountered, or when the end of file is reached.
Oops, sorry. It has been recently changed. You can
> produce when the string is closed and later a termination
> point is encountered, or when the end of file is reached.
try it since release 0.9.6 or so. It will work as
follows:
?- '
Error: Illegal end of line in string.
'
^
It is done by the state-machine, which stops reading
the line. But the state-machine will not issue an
error. It is the scanner that will produce the error.
This was a requested by you Ulrich Neumerkel.
Bye
Jan Burse
May 27, 2013, 4:46:08 PM5/27/13
to
Jan Burse schrieb:
normalizes the string depending on the processor character
set. This is why the error "illegal_eol" is not listed
at the scanner site, but at the plug-in site.
> error. It is the scanner that will produce the error.
Or to be more precise, the plug-in delegate that
normalizes the string depending on the processor character
set. This is why the error "illegal_eol" is not listed
at the scanner site, but at the plug-in site.
0 new messages