###
# Modern Albufeira Prolog Interpreter
#
# Warranty & Liability
# To the extent permitted by applicable law and unless explicitly
# otherwise agreed upon, XLOG Technologies AG makes no warranties
# regarding the provided information. XLOG Technologies AG assumes
# no liability that any problems might be solved with the information
# provided by XLOG Technologies AG.
#
# Rights & License
# All industrial property rights regarding the information - copyright
# and patent rights in particular - are the sole property of XLOG
# Technologies AG. If the company was not the originator of some
# excerpts, XLOG Technologies AG has at least obtained the right to
# reproduce, change and translate the information.
#
# Reproduction is restricted to the whole unaltered document. Reproduction
# of the information is only allowed for non-commercial uses. Selling,
# giving away or letting of the execution of the library is prohibited.
# The library can be distributed as part of your applications and libraries
# for execution provided this comment remains unchanged.
#
# Restrictions
# Only to be distributed with programs that add significant and primary
# functionality to the library. Not to be distributed with additional
# software intended to replace any components of the library.
#
# Trademarks
# Jekejeke is a registered trademark of XLOG Technologies AG.
##
import functools
from nova.core import (exec_build, stack_push,
equal_term, list_objects, objects_list, object_equals,
Compound, exec_unify, is_structure, union_find,
variable_serno, is_integer, is_float, is_special,
make_error, set, make_check, check_nonvar, copy_term,
is_variable, is_atom, deref, union_add, is_number,
Item, stack_peek, stack_pop, union_undo)
import math
################################################################
# @</2, @=</2, @>/2, @>=/2 and compare/3 #
################################################################
###
# X @< Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically less than Y, otherwise fails.
##
def test_less(args):
alpha = exec_build(args[0])
beta = exec_build(args[1])
return compare_term(alpha, beta) < 0
###
# X @=< Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically less or equal to Y, otherwise fails.
##
def test_lessequal(args):
alpha = exec_build(args[0])
beta = exec_build(args[1])
return compare_term(alpha, beta) <= 0
###
# X @>= Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically greater or equal to Y, otherwise fails.
##
def test_greaterequal(args):
alpha = exec_build(args[0])
beta = exec_build(args[1])
return compare_term(alpha, beta) >= 0
###
# X @> Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically greater than Y, otherwise fails.
##
def test_greater(args):
alpha = exec_build(args[0])
beta = exec_build(args[1])
return compare_term(alpha, beta) > 0
###
# compare(C, X, Y): [TC2 8.4.2]
# The predicate succeeds when C unifies with the result of comparing
# X to Y. The result is one of the following atoms <, = or >.
##
def test_compare(args):
beta = exec_build(args[1])
gamma = exec_build(args[2])
beta = compare_term(beta, gamma)
if beta < 0:
beta = "<"
elif beta == 0:
beta = "="
else:
beta = ">"
return exec_unify(args[0], beta)
###
# Determine the syntactic relationship between two Prolog terms.
# Can handle cyclic terms and deep recursion.
# Has left to right anomaly.
#
# @param alpha The first Prolog term.
# @param beta The second Prolog term.
# @return <0 for less, =0 for equal and >0 for greater
##
def compare_term(first, second):
stack = None
log = None
try:
while True:
first = deref(first)
second = deref(second)
if not is_structure(first):
if not object_equals(first, second):
break
elif not is_structure(second):
break
elif len(first.args) != len(second.args):
break
else:
first = union_find(first)
second = union_find(second)
if first is not second:
if first.functor != second.functor:
break
log = union_add(log, first, second)
if 0 != len(first.args) - 1:
item = Item(first, second, 0)
stack = stack_push(stack, item)
first = first.args[0]
second = second.args[0]
continue
item = stack_peek(stack)
if item is None:
return 0
else:
item.idx += 1
first = item.first.args[item.idx]
second = item.second.args[item.idx]
if item.idx == len(item.first.args) - 1:
stack_pop(stack)
return compare_truncated(first, second)
finally:
union_undo(log)
###
# Determine the syntactic relationship between truncated Prolog terms.
# Prolog compounds are truncated to their arity and functor.
#
# @param first The first Prolog term.
# @param second The second Prolog term.
# @return <0 for less, =0 for equal and >0 for greater
##
def compare_truncated(first, second):
i = compare_type(first)
k = i - compare_type(second)
if k != 0:
return k
if i == 0:
return variable_serno(first) - variable_serno(second)
elif i == 2:
return compare_atomic(first, second)
elif i == 3:
return compare_atomic(first, second)
elif i == 9:
return compare_atomic(first, second)
elif i == 10:
k = len(first.args) - len(second.args)
if k != 0:
return k
return compare_atomic(first.functor, second.functor)
else:
return 0
###
# Determine the compare type of a Prolog term.
#
# @param first The Prolog term.
# @return The compare type.
##
def compare_type(first):
if is_variable(first):
return 0
elif is_structure(first):
return 10
elif is_atom(first):
return 9
elif is_number(first):
if is_integer(first):
return 3
elif is_special(first):
if first == -math.inf:
return 1
elif first == math.inf:
return 4
elif math.isnan(first):
return 5
elif is_float(first):
return 2
elif first is False:
return 7
elif first is True:
return 8
elif first is None:
return 6
raise make_error(Compound("resource_error",
["not_supported"]))
###
# Determine the syntactic relationship between two Prolog atomics.
#
# @param first The first Prolog atomic.
# @param second The second Prolog atomic.
# @return -1 for less, 0 for equal and 1 for greater
##
def compare_atomic(first, second):
if first < second:
return -1
if first == second:
return 0
return 1
#######################################################################
# sort/2 and keysort/2 #
#######################################################################
###
# sort(L, R): [TC2 8.4.3]
# The predicate succeeds in R with the sorted list L.
##
def test_sort(args):
alpha = exec_build(args[0])
res = list_objects(alpha)
res.sort(key=functools.cmp_to_key(compare_term))
count = objects_dedup(res)
return exec_unify(args[1], objects_list(res, 0, count))
def objects_dedup(res):
j = 0
i = 0
while i < len(res):
alpha = res[i]
i += 1
while i < len(res) and equal_term(alpha, res[i]):
i += 1
res[j] = alpha
j += 1
return j
###
# keysort(L, R): [TC2 8.4.4]
# The predicate succeeds in R with the key sorted list L.
##
def test_keysort(args):
alpha = exec_build(args[0])
res = list_objects(alpha)
objects_pairs(res)
res.sort(key=functools.cmp_to_key(lambda first, second:
compare_term(get_key(first), get_key(second))))
return exec_unify(args[1], objects_list(res, 0, len(res)))
def objects_pairs(res):
i = 0
while i < len(res):
alpha = res[i]
if (is_structure(alpha) and
"-" == alpha.functor and
len(alpha.args) == 2):
pass
else:
check_nonvar(alpha)
alpha = copy_term(alpha)
raise make_error(Compound("type_error", ["pair", alpha]))
i += 1
def get_key(peek):
return peek.args[0]
#######################################################################
# Iso Lib Init #
#######################################################################
def main():
# term specials, syntactic comparison
set("@<", 2, make_check(test_less))
set("@=<", 2, make_check(test_lessequal))
set("@>=", 2, make_check(test_greaterequal))
set("@>", 2, make_check(test_greater))
set("compare", 3, make_check(test_compare))
# list specials, miscellaneous sorting
set("sort", 2, make_check(test_sort))
set("keysort", 2, make_check(test_keysort))