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:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

Lightweight Higher-Order Rewriting in Haskell

verfasst von : Emil Axelsson, Andrea Vezzosi

Erschienen in: Trends in Functional Programming

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present a generic Haskell library for expressing rewrite rules with a safe treatment of variables and binders. Both sides of the rules are written as typed EDSL expressions, which leads to syntactically appealing rules and hides the underlying term representation. Matching is defined as an instance of Miller’s higher-order pattern unification and has the same complexity as first-order matching. The restrictions of pattern unification are captured in the types of the library, and we show by example that the library is capable of expressing useful simplifications that might be used in a compiler.

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
Nächstes Kapitel Towards a Theory of Reach
Fußnoten
3
Note the partial type annotation https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-39110-6_1/395096_1_En_1_IEq45_HTML.gif in https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-39110-6_1/395096_1_En_1_IEq46_HTML.gif . It is used to constrain the type parameter of the RHS without saying anything about the representation of the RHS. Partial type signatures require the recent https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-39110-6_1/395096_1_En_1_IEq47_HTML.gif extension to GHC. However, this extension is not strictly needed: an equivalent formulation of the RHS would be https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-39110-6_1/395096_1_En_1_IEq48_HTML.gif .
 
4
The property is almost true: it holds if we replace all wildcards in \(l\) with unique meta-variables.
 
Literatur
1.
Antoy, S., Hanus, M.: Declarative programming with function patterns. In: Hill, P.M. (ed.) LOPSTR 2005. LNCS, vol. 3901, pp. 6–22. Springer, Heidelberg (2006)CrossRef
2.
Axelsson, E., Claessen, K.: Using circular programs for higher-order syntax: functional pearl. In: Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, pp. 257–262. ACM, New York (2013)
3.
Axelsson, E., Claessen, K., Dévai, G., Horváth, Z., Keijzer, K., Lyckegård, B., Persson, A., Sheeran, M., Svenningsson, J., Vajda, A.: Feldspar: a domain specific language for digital signal processing algorithms. In: 8th IEEE/ACM International Conference on Formal Methods and Models for Codesign, pp. 169–178. IEEE (2010)
4.
Bahr, P., Hvitved, T.: Compositional data types. In: Proceedings of the Seventh ACM SIGPLAN Workshop on Generic Programming, pp. 83–94. ACM, New York (2011)
5.
Brown, N.C., Sampson, A.T.: Matching and modifying with generics. In: Draft Proceedings of Trends in Functional Programming, pp. 304–318 (2008)
6.
Carette, J., Kiselyov, O., Shan, C.C.: Finally tagless, partially evaluated: tagless staged interpreters for simpler typed languages. J. Funct. Programm. 19(5), 509–543 (2009)MathSciNetCrossRefMATH
7.
8.
Dévai, G.: Extended pattern matching for embedded languages. Annales Univ. Sci. Budapestiensis de Rolando Eötvös Nominatae, Sectio Comutatorica 36, 277–297 (2012)MATH
9.
10.
11.
Huet, G.: Résolution d’équations dans les langages d’ordre 1, 2,.., \(\omega \). Ph.D. thesis, Université Paris VII (1976)
12.
Miller, D.: A logic programming language with lambda-abstraction, function variables, and simple unification. J. logic Comput. 1(4), 497–536 (1991)MathSciNetCrossRefMATH
13.
Mohnen, M.: Context patterns in Haskell. In: Kluge, W. (ed.) IFL’96. LNCS, vol. 1268, pp. 41–57. Springer, Berlin, Heidelberg (1997)CrossRef
14.
Nadathur, G., Miller, D.: An overview of Lambda-Prolog. Technical report MS-CIS-88-40, University of Pennsylvania, Department of Computer and Information Science (1988)
15.
van Noort, T., Yakushev, A.R., Holdermans, S., Jeuring, J., Heeren, B., Magalhães, J.P.: A lightweight approach to datatype-generic rewriting. J. Funct. Programm. 20, 375–413 (2010)CrossRefMATH
16.
Norell, U.: Towards a practical programming language based on dependent type theory. Ph.D. thesis, Department of Computer Science and Engineering, Chalmers University of Technology, SE-412 96 Göteborg, Sweden, September 2007
17.
Oosterhof, N., Hölzenspies, P., Kuper, J.: Application patterns. In: van Eekelen, M. (ed.) Trends in Functional Programming, pp. 370–382. Tartu University Press, Tallinn (2005)
18.
Pfenning, F., Schürmann, C.: System description: twelf - a meta-logical framework for deductive systems. In: Ganzinger, H. (ed.) CADE 1999. LNCS (LNAI), vol. 1632, pp. 202–206. Springer, Heidelberg (1999)CrossRef
19.
Sculthorpe, N., Frisby, N., Gill, A.: The kansas university rewrite engine. J. Funct. Programm. 24, 434–473 (2014)MathSciNetCrossRef
20.
21.
22.
Wierzbicki, T.M.: Complexity of the higher order matching. In: Ganzinger, H. (ed.) CADE 1999. LNCS (LNAI), vol. 1632, pp. 82–96. Springer, Heidelberg (1999)CrossRef
23.
Metadaten
Titel
Lightweight Higher-Order Rewriting in Haskell
verfasst von
Emil Axelsson
Andrea Vezzosi
Copyright-Jahr
2016
Buch
Trends in Functional Programming

Print ISBN: 978-3-319-39109-0

Electronic ISBN: 978-3-319-39110-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-39110-6_1