Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Logic/Constraint Programming and Concurrency: The Hard-Won Lessons of the Fifth Generation Computer Project Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

An Interaction Net Encoding of Gödel’s System \(\mathcal {T}\)

Declarative Pearl

verfasst von : Ian Mackie, Shinya Sato

Erschienen in: Functional and Logic Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The graph rewriting system of interaction nets has been very successful for the implementation of the lambda calculus. In this paper we show how the ideas can be extended and simplified to encode Gödel’s System \(\mathcal {T}\)—the simply typed \(\lambda \)-calculus extended with numbers. Surprisingly, using some results about System \(\mathcal {T}\), we obtain a very simple system of interaction nets that is significantly more efficient than a direct encoding for the evaluation of programs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Probabilistic Inference by Program Transformation in Hakaru (System Description)
Nächstes Kapitel Space-Efficient Planar Acyclicity Constraints
Literatur
1.
Alves, S., Florido, M., Fernández, M., Mackie, I.: The power of linear functions. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 119–134. Springer, Heidelberg (2006)CrossRef
2.
Alves, S., Fernández, M., Florido, M., Mackie, I.: Gödel’s system T revisited. Theor. Comput. Sci. 411(11–13), 1484–1500 (2010)CrossRefMATH
3.
Asperti, A., Giovannetti, C., Naletto, A.: The Bologna optimal higher-order machine. J. Funct. Program. 6(6), 763–810 (1996)CrossRefMATH
4.
Barendregt, H.P.: The Lambda calculus: its syntax and semantics. Studies in Logic and the Foundations of Mathematics, vol. 103. North-Holland Publishing Company, Amsterdam (1984)MATH
5.
Cirstea, H., Kirchner, C.: The rewriting calculus - Part I and II. Logic J. Interest Group Pure Appl. Logics 9(3), 427–498 (2001)MathSciNetMATH
6.
Lago, U.D.: The geometry of linear higher-order recursion. In: Panangaden, P., (ed.) Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, LICS 2005, pp. 366–375. IEEE Computer Society Press, June 2005
7.
Girard, J.-Y., Lafont, Y., Taylor, P.: Proofs and Types. Cambridge Tracts in Theoretical Computer Science, vol. 7. Cambridge University Press, Cambridge (1989)MATH
8.
Gonthier, G., Abadi, M., Lévy, J.-J.: The geometry of optimal lambda reduction. In: Proceedings of the 19th ACM Symposium on Principles of Programming Languages (POPL 1992), pp. 15–26. ACM Press, January 1992
9.
Lafont, Y.: Interaction nets. In: Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL 1990), pp. 95–108. ACM Press (1990)
10.
Lamping, J.: An algorithm for optimal lambda calculus reduction. In: Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL 1990), pp. 16–30. ACM Press, January 1990
11.
Lévy, J.-J.: Optimal reductions in the lambda calculus. In: Hindley, J.P., Seldin, J.R., (eds.) To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pp. 159–191. Academic Press (1980)
12.
Lippi, S.: \(\lambda \)-calculus left reduction with interaction nets. Math. Struct. Comput. Sci. 12(6) (2002)
13.
Mackie, I.: YALE: yet another lambda evaluator based on interaction nets. In: Proceedings of the 3rd ACM SIGPLAN International Conference on Functional Programming (ICFP 1998), pp. 117–128. ACM Press, September 1998
14.
Mackie, I.: An interaction net implementation of closed reduction. In: Scholz, S.-B., Chitil, O. (eds.) IFL 2008. LNCS, vol. 5836, pp. 43–59. Springer, Heidelberg (2011)CrossRef
15.
Sinot, F.-R.: Call-by-name and call-by-value as token-passing interaction nets. In: Urzyczyn, P. (ed.) TLCA 2005. LNCS, vol. 3461, pp. 386–400. Springer, Heidelberg (2005)CrossRef
Metadaten
Titel
An Interaction Net Encoding of Gödel’s System 
verfasst von
Ian Mackie
Shinya Sato
Copyright-Jahr
2016
Buch
Functional and Logic Programming

Print ISBN: 978-3-319-29603-6

Electronic ISBN: 978-3-319-29604-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-29604-3_6