SpringerLink
Log in

Structured Traversal of Search Trees in Constraint-Logic Object-Oriented Programming

  • Conference paper
  • First Online:
Declarative Programming and Knowledge Management (INAP 2019, WLP 2019, WFLP 2019)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 12057))

Abstract

In this paper, we propose an explicit, non-strict representation of search trees in constraint-logic object-oriented programming. Our search tree representation includes both the non-deterministic and deterministic behaviours of executing an application. Introducing such a representation facilitates the use of various search strategies. In order to demonstrate the applicability of our approach, we incorporate explicit search trees into the virtual machine of the constraint-logic object-oriented programming language Muli. We then exemplarily implement three search algorithms that traverse the search tree on-demand: depth-first search, breadth-first search, and iterative deepening depth-first search. In particular, the last two strategies allow for a complete search, which is novel in constraint-logic object-oriented programming and highlights our main contribution. Finally, we compare the implemented strategies using several benchmarks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 52.74
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Provided that the constraint system was still consistent. Otherwise, backtracking occurred until the next choice point that offered an unevaluated, feasible alternative.

  2. 2.

    Ubuntu 18.04.2 with 4.15.0 x86_64 GNU/Linux kernel; Intel Core i5-5200U CPU.

References

  1. Braßel, B., Hanus, M., Huch, F.: Encapsulating non-determinism in functional logic computations. J. Funct. Log. Program. 2004(6) (2004)

    Google Scholar 

  2. Dageförde, J.C.: Reference type logic variables in constraint-logic object-oriented programming. In: Silva, J. (ed.) WFLP 2018. LNCS, vol. 11285, pp. 131–144. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16202-3_8

    Chapter  Google Scholar 

  3. Dageförde, J.C., Kuchen, H.: An operational semantics for constraint-logic imperative programming. In: Seipel, D., Hanus, M., Abreu, S. (eds.) WFLP/WLP/INAP -2017. LNCS (LNAI), vol. 10997, pp. 64–80. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00801-7_5

    Chapter  Google Scholar 

  4. Dageförde, J.C., Kuchen, H.: A compiler and virtual machine for constraint-logic object-oriented programming with muli. J. Comput. Lang. 53, 63–78 (2019). https://doi.org/10.1016/j.cola.2019.05.001

    Article  Google Scholar 

  5. Dageförde, J.C., Kuchen, H.: Retrieval of individual solutions from encapsulated search with a potentially infinite search space. In: Proceedings of 34th SAC, pp. 1552–1561. Limassol, Cyprus (2019). https://doi.org/10.1145/3297280.3298912

  6. Danvy, O., Filinski, A.: Abstracting control. In: Proceedings of the 1990 ACM Conference on LISP and Functional Programming - LFP 1990, pp. 151–160. ACM Press (1990)

    Google Scholar 

  7. Hanus, M., Peemöller, B., Reck, F.: Search strategies for functional logic programming. In: Proceedings of ATPS 2012, pp. 61–74, GI LNI 199 (2012)

    Google Scholar 

  8. King, J.C.: Symbolic execution and program testing. Commun. ACM 19(7), 385–394 (1976). https://doi.org/10.1145/360248.360252

    Article  MathSciNet  MATH  Google Scholar 

  9. Kiselyov, O., Shan, C.: Embedded probabilistic programming. In: Taha, W.M. (ed.) DSL 2009. LNCS, vol. 5658, pp. 360–384. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03034-5_17

    Chapter  Google Scholar 

  10. Lindholm, T., Yellin, F., Bracha, G., Buckley, A.: The Java® Virtual Machine Specification - Java SE 8 Edition (2015). https://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf

  11. Majchrzak, T.A., Kuchen, H.: Automated test case generation based on coverage analysis. In: TASE 2009. IEEE (2009). https://doi.org/10.1109/TASE.2009.33

  12. van der Ploeg, A., Kiselyov, O.: Reflection without remorse: revealing a hidden sequence to speed up monadic reflection. In: ACM SIGPLAN Notices, vol. 49, no. 12, pp. 133–144 (2015)

    Google Scholar 

  13. Schrijvers, T., Stuckey, P., Wadler, P.: Monadic constraint programming. JFP 19(6), 663–697 (2009). https://doi.org/10.1017/s0956796809990086

    Article  MathSciNet  MATH  Google Scholar 

  14. Warren, D.H.D.: An abstract prolog instruction set, Technical repot, SRI International, Menlo Park (1983)

    Google Scholar 

Download references

Acknowledgements

The initial ideas that led to this work were conceived during the first author’s visit to the University of Kiel. The authors appreciate the valuable input of those that participated in the discussions; in particular, Sandra Dylus, Jan Christiansen, Jan Rasmus Tikovsky, and Michael Hanus.

Author information

Authors and Affiliations

  1. ERCIS, Leonardo-Campus 3, 48149, Münster, Germany

    Jan C. Dageförde

  2. Institut für Informatik, CAU Kiel, 24098, Kiel, Germany

    Finn Teegen

Authors
  1. Jan C. Dageförde
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Finn Teegen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jan C. Dageförde .

Editor information

Editors and Affiliations

  1. Brandenburgische Technische Universität Cottbus-Senftenberg, Cottbus, Germany

    Petra Hofstedt

  2. Universidade de Évora, Évora, Portugal

    Salvador Abreu

  3. hwtk Berlin, Berlin, Germany

    Ulrich John

  4. Westfälische Wilhelms-Universität Münster, Münster, Germany

    Herbert Kuchen

  5. Universität Würzburg, Würzburg, Germany

    Dietmar Seipel

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Dageförde, J.C., Teegen, F. (2020). Structured Traversal of Search Trees in Constraint-Logic Object-Oriented Programming. In: Hofstedt, P., Abreu, S., John, U., Kuchen, H., Seipel, D. (eds) Declarative Programming and Knowledge Management. INAP WLP WFLP 2019 2019 2019. Lecture Notes in Computer Science(), vol 12057. Springer, Cham. https://doi.org/10.1007/978-3-030-46714-2_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-46714-2_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-46713-5

  • Online ISBN: 978-3-030-46714-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation