SASLOG : Eine funktional-logische Sprachintegration mit Lazy Evaluation und semantischer Unifikation

Abstract

SASLOG is a combined functional/logic programming language which contains SASL, a fully-lazy, higher-order functional language and the logic language Prolog. The integration is symmetric allowing functional terms to appear in the logic part and Prolog goals in the functional part. Exploiting the natural correspondence between backtracking and lazy streams yields an elegant solution to the problem of transferring alternative variable bindings to the calling functional part of the program. The evaluation of functional expressions in the logic part is driven by the extended unification algorithm which takes into account the semantics of function symbols. The rewriting approach to function evaluation is replaced by combinator graph reduction, thereby regaining computational efficiency and the structure sharing properties. The integration fits well to combinator graph reduction. So the instantiation of logic variables supports structure sharing. On the other hand we provide a solution to the reduction of functional expressions containing logic variables in different binding environments.